Logo ROOT  
Reference Guide
 
Loading...
Searching...
No Matches
RooSTLRefCountList.h
Go to the documentation of this file.
1/// \cond ROOFIT_INTERNAL
2
3// Author: Stephan Hageboeck, CERN, 12/2018
4/*****************************************************************************
5 * Project: RooFit *
6 * Authors: *
7 * WV, Wouter Verkerke, UC Santa Barbara, verkerke@slac.stanford.edu *
8 * DK, David Kirkby, UC Irvine, dkirkby@uci.edu *
9 * *
10 * Copyright (c) 2000-2005, Regents of the University of California *
11 * and Stanford University. All rights reserved. *
12 * *
13 * Redistribution and use in source and binary forms, *
14 * with or without modification, are permitted according to the terms *
15 * listed in LICENSE (http://roofit.sourceforge.net/license.txt) *
16 *****************************************************************************/
17
18#ifndef ROOFIT_ROOFITCORE_INC_ROOSTLREFCOUNTLIST_H_
19#define ROOFIT_ROOFITCORE_INC_ROOSTLREFCOUNTLIST_H_
20
21#include "RooNameReg.h"
22
23#include "Rtypes.h"
24
25#include <vector>
26#include <string>
27#include <algorithm>
28#include <cassert>
29
30class RooLinkedList;
31
32/**
33 * \class RooSTLRefCountList
34 * The RooSTLRefCountList is a simple collection of **pointers** to the template objects with
35 * reference counters.
36 * The pointees are not owned, hence not deleted when removed from the collection.
37 * Objects can be searched for either by pointer or by name (confusion possible when
38 * objects with same name are present). This replicates the behaviour of the RooRefCountList.
39 */
40
41template <class T>
43 public:
44 using Container_t = std::vector<T*>;
45
46 static constexpr std::size_t minSizeForNamePointerOrdering = 7;
47
49 // The static _renameCounter member gets connected to the RooNameReg as
50 // soon as the first RooSTLRefCountList instance is constructed.
51 if(_renameCounter == nullptr) _renameCounter =
53 }
54 RooSTLRefCountList(const RooSTLRefCountList&) = default;
57
58 virtual ~RooSTLRefCountList() {}
59
60 ///Add an object or increase refCount if it is already present. Only compares
61 ///pointers to check for existing objects
62 void Add(T * obj, std::size_t initialCount = 1) {
63 // Nothing to add because `refCount` would be zero.
64 if(initialCount == 0) return;
65
66 auto foundItem = findByPointer(obj);
67
68 if (foundItem != _storage.end()) {
69 _refCount[foundItem - _storage.begin()] += initialCount;
70 }
71 else {
72 if(!_orderedStorage.empty()) {
73 _orderedStorage.insert(lowerBoundByNamePointer(obj), obj);
74 }
75 _storage.push_back(obj);
76 _refCount.push_back(initialCount);
77 }
78 }
79
80
81 ///Return ref count of item that iterator points to.
82 std::size_t refCount(typename Container_t::const_iterator item) const {
83 assert(_storage.size() == _refCount.size());
84
85 return item != _storage.end() ? _refCount[item - _storage.begin()] : 0;
86 }
87
88
89 ///Return ref count of item with given address.
90 template<typename Obj_t>
91 std::size_t refCount(const Obj_t * obj) const {
92 return refCount(findByPointer(obj));
93 }
94
95 ///Iterator over contained objects.
96 typename Container_t::const_iterator begin() const {
97 return _storage.begin();
98 }
99
100 ///End of contained objects.
101 typename Container_t::const_iterator end() const {
102 return _storage.end();
103 }
104
105 /// Retrieve an element from the list.
106 typename Container_t::value_type operator[](std::size_t index) const {
107 return _storage[index];
108 }
109
110
111 ///Direct reference to container of objects held by this list.
112 const Container_t& containedObjects() const {
113 return _storage;
114 }
115
116
117 ///Number of contained objects (neglecting the ref count).
118 std::size_t size() const {
119 assert(_storage.size() == _refCount.size());
120
121 return _storage.size();
122 }
123
124 void reserve(std::size_t amount) {
125 _storage.reserve(amount);
126 _refCount.reserve(amount);
127 _orderedStorage.reserve(amount);
128 }
129
130
131 ///Check if empty.
132 bool empty() const {
133 return _storage.empty();
134 }
135
136
137 ///Find an item by comparing its address.
138 template<typename Obj_t>
139 typename Container_t::const_iterator findByPointer(const Obj_t * item) const {
140 return std::find(_storage.begin(), _storage.end(), item);
141 }
142
143
144 ///Find an item by comparing strings returned by RooAbsArg::GetName()
145 typename Container_t::const_iterator findByName(const char * name) const {
146 //If this turns out to be a bottleneck,
147 //one could use the RooNameReg to obtain the pointer to the arg's name and compare these
148 const std::string theName(name);
149 auto byName = [&theName](const T * element) {
150 return element->GetName() == theName;
151 };
152
153 return std::find_if(_storage.begin(), _storage.end(), byName);
154 }
155
156
157 ///Find an item by comparing RooAbsArg::namePtr() addresses.
158 inline T* findByNamePointer(const T * item) const {
159 return findByNamePointer(item->namePtr());
160 }
161
162 T* findByNamePointer(TNamed const* namePtr) const {
163 if(size() < minSizeForNamePointerOrdering) {
164 auto byNamePointer = [namePtr](const T * element) {
165 return element->namePtr() == namePtr;
166 };
167
168 auto found = std::find_if(_storage.begin(), _storage.end(), byNamePointer);
169 return found != _storage.end() ? *found : nullptr;
170 } else {
171 //As the collection is guaranteed to be sorted by namePtr() address, we
172 //can use a binary search to look for `item` in this collection.
173 auto first = lowerBoundByNamePointer(namePtr);
174 if(first == _orderedStorage.end()) return nullptr;
175 if(namePtr != (*first)->namePtr()) return nullptr;
176 return *first;
177 }
178 }
179
180
181 ///Check if list contains an item using findByPointer().
182 template<typename Obj_t>
183 bool containsByPointer(const Obj_t * obj) const {
184 return findByPointer(obj) != _storage.end();
185 }
186
187
188 ///Check if list contains an item using findByNamePointer().
189 bool containsByNamePtr(const T * obj) const {
190 return findByNamePointer(obj);
191 }
192
193
194 ///Check if list contains an item using findByName().
195 bool containsSameName(const char * name) const {
196 return findByName(name) != _storage.end();
197 }
198
199
200 ///Decrease ref count of given object. Shrink list if ref count reaches 0.
201 ///\param obj Decrease ref count of given object. Compare by pointer.
202 ///\param force If true, remove irrespective of ref count.
203 ///Returns by how much the `refCount` for the element to be removed was
204 ///decreased (zero if nothing was removed). If `force == false`, it can
205 ///only be zero or one, if `force == true`, it can be the full `refCount`
206 ///for that element.
207 int Remove(const T * obj, bool force = false) {
208 auto item = findByPointer(obj);
209
210 if (item != _storage.end()) {
211 const std::size_t pos = item - _storage.begin();
212
213 const UInt_t origRefCount = _refCount[pos];
214
215 if (force || --_refCount[pos] == 0) {
216 //gcc4.x doesn't know how to erase at the position of a const_iterator
217 //Therefore, erase at begin + pos instead of 'item'
218 _storage.erase(_storage.begin() + pos);
219 _refCount.erase(_refCount.begin() + pos);
220 if(!_orderedStorage.empty()) {
221 // For the ordered storage, we could find by name pointer address
222 // with binary search, but this will not work anymore if one of the
223 // object pointers in this collection is dangling (can happen in
224 // RooFit...). However, the linear search by object address is
225 // acceptable, because we already do a linear search through
226 // _storage at the beginning of Remove().
227 _orderedStorage.erase(std::find(_orderedStorage.begin(), _orderedStorage.end(), obj));
228 }
229 return origRefCount;
230 }
231 return 1;
232 }
233
234 return 0;
235 }
236
237
238 ///Replace an element with a new value, keeping the same `refCount`. Will
239 ///return the `refCount` for that element if the replacement succeeded,
240 ///otherwise returns zero in case the `oldObj` could not be found in the
241 ///collection.
242 int Replace(const T * oldObj, T * newObj) {
243 auto item = findByPointer(oldObj);
244
245 if (item != _storage.end()) {
246 const std::size_t pos = item - _storage.begin();
247 _storage[pos] = newObj;
248 // The content has changed, so the ordered-by-name storage was invalidated.
249 _orderedStorage.clear();
250 return _refCount[pos];
251 }
252
253 return 0;
254 }
255
256
257 ///Remove from list irrespective of ref count.
258 void RemoveAll(const T * obj) {
259 Remove(obj, true);
260 }
261
263
264 private:
265 //Return an iterator to the last element in this sorted collection with a
266 //RooAbsArg::namePtr() address smaller than for `item`.
267 inline typename std::vector<T*>::const_iterator lowerBoundByNamePointer(const T * item) const {
268 return lowerBoundByNamePointer(item->namePtr());
269 }
270
271 typename std::vector<T*>::const_iterator lowerBoundByNamePointer(TNamed const* namePtr) const {
272
273 //If the _orderedStorage has not been initialized yet or needs resorting
274 //for other reasons, (re-)initialize it now.
275 if(orderedStorageNeedsSorting() || _orderedStorage.size() != _storage.size()) initializeOrderedStorage();
276
277 return std::lower_bound(_orderedStorage.begin(), _orderedStorage.end(), namePtr,
278 [](const auto& x, TNamed const* npt) -> bool {
279 return x->namePtr() < npt;
280 });
281 }
282
283 bool orderedStorageNeedsSorting() const {
284 //If an RooAbsArg in this collection was renamed, the collection might
285 //not be sorted correctly anymore! The solution: every time any RooAbsArg
286 //is renamed, the RooNameReg::renameCounter gets incremented. The
287 //RooSTLRefCountList keeps track at which value of the counter it has
288 //been sorted last. If the counter increased in the meantime, a
289 //re-sorting is due.
290 return _renameCounterForLastSorting != *_renameCounter;
291 }
292
293 void initializeOrderedStorage() const {
294 _orderedStorage.clear();
295 _orderedStorage.reserve(_storage.size());
296 for(std::size_t i = 0; i < _storage.size(); ++i) {
297 _orderedStorage.push_back(_storage[i]);
298 }
299 std::sort(_orderedStorage.begin(), _orderedStorage.end(),
300 [](auto& a, auto& b) {
301 return a->namePtr() != b->namePtr() ? a->namePtr() < b->namePtr() : a < b;
302 });
303 _renameCounterForLastSorting = *_renameCounter;
304 }
305
306 Container_t _storage;
307 std::vector<UInt_t> _refCount;
308 mutable std::vector<T*> _orderedStorage; //!
309 mutable unsigned long _renameCounterForLastSorting = 0; ///<!
310
311 // It is expensive to access the RooNameReg instance to get the counter for
312 // the renaming operations. That's why we have out own static pointer to
313 // the counter.
314 static std::size_t const* _renameCounter;
315
317};
318
319template<class T>
320std::size_t const* RooSTLRefCountList<T>::_renameCounter = nullptr;
321
322#endif /* ROOFIT_ROOFITCORE_INC_ROOSTLREFCOUNTLIST_H_ */
323
324/// \endcond
#define b(i)
Definition RSha256.hxx:100
#define a(i)
Definition RSha256.hxx:99
size_t size(const MatrixT &matrix)
retrieve the size of a square matrix
unsigned int UInt_t
Definition RtypesCore.h:46
#define ClassDef(name, id)
Definition Rtypes.h:337
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
Binding & operator=(OUT(*fun)(void))
Collection class for internal use, storing a collection of RooAbsArg pointers in a doubly linked list...
static const std::size_t & renameCounter()
renamed in this RooFit process.
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)
void convert(R1 const &, R2 const)
TMatrixT< Element > & Add(TMatrixT< Element > &target, Element scalar, const TMatrixT< Element > &source)
Modify addition: target += scalar * source.