Logo ROOT  
Reference Guide
RooSTLRefCountList.h
Go to the documentation of this file.
1// Author: Stephan Hageboeck, CERN, 12/2018
2/*****************************************************************************
3 * Project: RooFit *
4 * Authors: *
5 * WV, Wouter Verkerke, UC Santa Barbara, verkerke@slac.stanford.edu *
6 * DK, David Kirkby, UC Irvine, dkirkby@uci.edu *
7 * *
8 * Copyright (c) 2000-2005, Regents of the University of California *
9 * and Stanford University. All rights reserved. *
10 * *
11 * Redistribution and use in source and binary forms, *
12 * with or without modification, are permitted according to the terms *
13 * listed in LICENSE (http://roofit.sourceforge.net/license.txt) *
14 *****************************************************************************/
15
16#ifndef ROOFIT_ROOFITCORE_INC_ROOSTLREFCOUNTLIST_H_
17#define ROOFIT_ROOFITCORE_INC_ROOSTLREFCOUNTLIST_H_
18
19#include "RooNameReg.h"
20
21#include "Rtypes.h"
22
23#include <vector>
24#include <string>
25#include <algorithm>
26#include <cassert>
27
28
29/**
30 * \class RooSTLRefCountList
31 * The RooSTLRefCountList is a simple collection of **pointers** to the template objects with
32 * reference counters.
33 * The pointees are not owned, hence not deleted when removed from the collection.
34 * Objects can be searched for either by pointer or by name (confusion possible when
35 * objects with same name are present). This replicates the behaviour of the RooRefCountList.
36 */
37
38template <class T>
40 public:
41 using Container_t = std::vector<T*>;
42
43 static constexpr std::size_t minSizeForNamePointerOrdering = 7;
44
46 // The static _renameCounter member gets connected to the RooNameReg as
47 // soon as the first RooSTLRefCountList instance is constructed.
48 if(_renameCounter == nullptr) _renameCounter =
50 }
54
56
57 ///Add an object or increase refCount if it is already present. Only compares
58 ///pointers to check for existing objects
59 void Add(T * obj, std::size_t initialCount = 1) {
60 auto foundItem = findByPointer(obj);
61
62 if (foundItem != _storage.end()) {
63 _refCount[foundItem - _storage.begin()] += initialCount;
64 }
65 else {
66 if(!_orderedStorage.empty()) {
68 }
69 _storage.push_back(obj);
70 _refCount.push_back(initialCount);
71 }
72 }
73
74
75 ///Return ref count of item that iterator points to.
76 std::size_t refCount(typename Container_t::const_iterator item) const {
77 assert(_storage.size() == _refCount.size());
78
79 return item != _storage.end() ? _refCount[item - _storage.begin()] : 0;
80 }
81
82
83 ///Return ref count of item with given address.
84 template<typename Obj_t>
85 std::size_t refCount(const Obj_t * obj) const {
86 return refCount(findByPointer(obj));
87 }
88
89 ///Iterator over contained objects.
90 typename Container_t::const_iterator begin() const {
91 return _storage.begin();
92 }
93
94 ///End of contained objects.
95 typename Container_t::const_iterator end() const {
96 return _storage.end();
97 }
98
99 /// Retrieve an element from the list.
100 typename Container_t::value_type operator[](std::size_t index) const {
101 return _storage[index];
102 }
103
104
105 ///Direct reference to container of objects held by this list.
107 return _storage;
108 }
109
110
111 ///Number of contained objects (neglecting the ref count).
112 std::size_t size() const {
113 assert(_storage.size() == _refCount.size());
114
115 return _storage.size();
116 }
117
118 void reserve(std::size_t amount) {
119 _storage.reserve(amount);
120 _refCount.reserve(amount);
121 _orderedStorage.reserve(amount);
122 }
123
124
125 ///Check if empty.
126 bool empty() const {
127 return _storage.empty();
128 }
129
130
131 ///Find an item by comparing its adress.
132 template<typename Obj_t>
133 typename Container_t::const_iterator findByPointer(const Obj_t * item) const {
134 return std::find(_storage.begin(), _storage.end(), item);
135 }
136
137
138 ///Find an item by comparing strings returned by RooAbsArg::GetName()
139 typename Container_t::const_iterator findByName(const char * name) const {
140 //If this turns out to be a bottleneck,
141 //one could use the RooNameReg to obtain the pointer to the arg's name and compare these
142 const std::string theName(name);
143 auto byName = [&theName](const T * element) {
144 return element->GetName() == theName;
145 };
146
147 return std::find_if(_storage.begin(), _storage.end(), byName);
148 }
149
150
151 ///Find an item by comparing RooAbsArg::namePtr() adresses.
152 T* findByNamePointer(const T * item) const {
154 auto nptr = item->namePtr();
155 auto byNamePointer = [nptr](const T * element) {
156 return element->namePtr() == nptr;
157 };
158
159 auto found = std::find_if(_storage.begin(), _storage.end(), byNamePointer);
160 return found != _storage.end() ? *found : nullptr;
161 } else {
162 //As the collection is guaranteed to be sorted by namePtr() adress, we
163 //can use a binary search to look for `item` in this collection.
164 auto first = lowerBoundByNamePointer(item);
165 if(first == _orderedStorage.end()) return nullptr;
166 if(item->namePtr() != (*first)->namePtr()) return nullptr;
167 return *first;
168 }
169 }
170
171
172 ///Check if list contains an item using findByPointer().
173 template<typename Obj_t>
174 bool containsByPointer(const Obj_t * obj) const {
175 return findByPointer(obj) != _storage.end();
176 }
177
178
179 ///Check if list contains an item using findByNamePointer().
180 bool containsByNamePtr(const T * obj) const {
181 return findByNamePointer(obj);
182 }
183
184
185 ///Check if list contains an item using findByName().
186 bool containsSameName(const char * name) const {
187 return findByName(name) != _storage.end();
188 }
189
190
191 ///Decrease ref count of given object. Shrink list if ref count reaches 0.
192 ///\param obj Decrease ref count of given object. Compare by pointer.
193 ///\param force If true, remove irrespective of ref count.
194 void Remove(const T * obj, bool force = false) {
195 auto item = findByPointer(obj);
196
197 if (item != _storage.end()) {
198 const std::size_t pos = item - _storage.begin();
199
200 if (force || --_refCount[pos] == 0) {
201 //gcc4.x doesn't know how to erase at the position of a const_iterator
202 //Therefore, erase at begin + pos instead of 'item'
203 _storage.erase(_storage.begin() + pos);
204 _refCount.erase(_refCount.begin() + pos);
205 if(!_orderedStorage.empty()) {
206 // For the ordered storage, we could find by name pointer address
207 // with binary search, but this will not work anymore if one of the
208 // object pointers in this collection is dangling (can happen in
209 // RooFit...). However, the linear search by object address is
210 // acceptable, because we already do a linear search through
211 // _storage at the beginning of Remove().
212 _orderedStorage.erase(std::find(_orderedStorage.begin(), _orderedStorage.end(), obj));
213 }
214 }
215 }
216 }
217
218
219 ///Remove from list irrespective of ref count.
220 void RemoveAll(const T * obj) {
221 Remove(obj, true);
222 }
223
224
225 private:
226 //Return an iterator to the last element in this sorted collection with a
227 //RooAbsArg::namePtr() adress smaller than for `item`.
228 typename std::vector<T*>::const_iterator lowerBoundByNamePointer(const T * item) const {
229
230 //If the _orderedStorage has not been initialized yet or needs resorting
231 //for other reasons, (re-)initialize it now.
233
234 return std::lower_bound(_orderedStorage.begin(), _orderedStorage.end(), item->namePtr(),
235 [](const auto& x, TNamed const* npt) -> bool {
236 return x->namePtr() < npt;
237 });
238 }
239
241 //If an RooAbsArg in this collection was renamed, the collection might
242 //not be sorted correctly anymore! The solution: every time any RooAbsArg
243 //is renamed, the RooNameReg::renameCounter gets incremented. The
244 //RooSTLRefCountList keeps track at which value of the counter it has
245 //been sorted last. If the counter increased in the meantime, a
246 //re-sorting is due.
248 }
249
251 _orderedStorage.clear();
252 _orderedStorage.reserve(_storage.size());
253 for(std::size_t i = 0; i < _storage.size(); ++i) {
254 _orderedStorage.push_back(_storage[i]);
255 }
256 std::sort(_orderedStorage.begin(), _orderedStorage.end(),
257 [](auto& a, auto& b) {
258 return a->namePtr() != b->namePtr() ? a->namePtr() < b->namePtr() : a < b;
259 });
261 }
262
264 std::vector<UInt_t> _refCount;
265 mutable std::vector<T*> _orderedStorage; //!
266 mutable unsigned long _renameCounterForLastSorting = 0; ///<!
267
268 // It is expensive to access the RooNameReg instance to get the counter for
269 // the renaming operations. That's why we have out own static pointer to
270 // the counter.
271 static std::size_t const* _renameCounter;
272
274};
275
276template<class T>
277std::size_t const* RooSTLRefCountList<T>::_renameCounter = nullptr;
278
279class RooAbsArg;
280class RooRefCountList;
281
282namespace RooFit {
283namespace STLRefCountListHelpers {
284 /// Converter from the old RooRefCountList to RooSTLRefCountList.
286}
287}
288
289#endif /* ROOFIT_ROOFITCORE_INC_ROOSTLREFCOUNTLIST_H_ */
#define ClassDef(name, id)
Definition: Rtypes.h:335
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t Float_t Float_t b
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t index
char name[80]
Definition: TGX11.cxx:110
RooAbsArg is the common abstract base class for objects that represent a value and a "shape" in RooFi...
Definition: RooAbsArg.h:77
static const std::size_t & renameCounter()
renamed in this RooFit process.
Definition: RooNameReg.cxx:136
A RooRefCountList is a RooLinkedList that keeps a reference counter with each added node.
The RooSTLRefCountList is a simple collection of pointers to the template objects with reference coun...
void initializeOrderedStorage() const
std::size_t refCount(typename Container_t::const_iterator item) const
Return ref count of item that iterator points to.
bool containsSameName(const char *name) const
Check if list contains an item using findByName().
bool orderedStorageNeedsSorting() const
std::vector< T * >::const_iterator lowerBoundByNamePointer(const T *item) const
bool containsByPointer(const Obj_t *obj) const
Check if list contains an item using findByPointer().
std::size_t refCount(const Obj_t *obj) const
Return ref count of item with given address.
T * findByNamePointer(const T *item) const
Find an item by comparing RooAbsArg::namePtr() adresses.
const Container_t & containedObjects() const
Direct reference to container of objects held by this list.
void Remove(const T *obj, bool force=false)
Decrease ref count of given object.
Container_t::const_iterator begin() const
Iterator over contained objects.
unsigned long _renameCounterForLastSorting
!
std::vector< T * > Container_t
void Add(T *obj, std::size_t initialCount=1)
Add an object or increase refCount if it is already present.
std::vector< T * > _orderedStorage
RooSTLRefCountList & operator=(RooSTLRefCountList &&)=default
Container_t::value_type operator[](std::size_t index) const
Retrieve an element from the list.
static std::size_t const * _renameCounter
RooSTLRefCountList & operator=(const RooSTLRefCountList &)=default
RooSTLRefCountList(const RooSTLRefCountList &)=default
Container_t::const_iterator end() const
End of contained objects.
bool empty() const
Check if empty.
static constexpr std::size_t minSizeForNamePointerOrdering
std::vector< UInt_t > _refCount
Container_t::const_iterator findByName(const char *name) const
Find an item by comparing strings returned by RooAbsArg::GetName()
std::size_t size() const
Number of contained objects (neglecting the ref count).
Container_t::const_iterator findByPointer(const Obj_t *item) const
Find an item by comparing its adress.
void RemoveAll(const T *obj)
Remove from list irrespective of ref count.
void reserve(std::size_t amount)
bool containsByNamePtr(const T *obj) const
Check if list contains an item using findByNamePointer().
The TNamed class is the base class for all named ROOT classes.
Definition: TNamed.h:29
Double_t x[n]
Definition: legend1.C:17
double T(double x)
Definition: ChebyshevPol.h:34
RooSTLRefCountList< RooAbsArg > convert(const RooRefCountList &old)
Converter from the old RooRefCountList to RooSTLRefCountList.
The namespace RooFit contains mostly switches that change the behaviour of functions of PDFs (or othe...
Definition: Common.h:18
Definition: first.py:1
auto * a
Definition: textangle.C:12