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 // Nothing to add because `refCount` would be zero.
61 if(initialCount == 0) return;
62
63 auto foundItem = findByPointer(obj);
64
65 if (foundItem != _storage.end()) {
66 _refCount[foundItem - _storage.begin()] += initialCount;
67 }
68 else {
69 if(!_orderedStorage.empty()) {
71 }
72 _storage.push_back(obj);
73 _refCount.push_back(initialCount);
74 }
75 }
76
77
78 ///Return ref count of item that iterator points to.
79 std::size_t refCount(typename Container_t::const_iterator item) const {
80 assert(_storage.size() == _refCount.size());
81
82 return item != _storage.end() ? _refCount[item - _storage.begin()] : 0;
83 }
84
85
86 ///Return ref count of item with given address.
87 template<typename Obj_t>
88 std::size_t refCount(const Obj_t * obj) const {
89 return refCount(findByPointer(obj));
90 }
91
92 ///Iterator over contained objects.
93 typename Container_t::const_iterator begin() const {
94 return _storage.begin();
95 }
96
97 ///End of contained objects.
98 typename Container_t::const_iterator end() const {
99 return _storage.end();
100 }
101
102 /// Retrieve an element from the list.
103 typename Container_t::value_type operator[](std::size_t index) const {
104 return _storage[index];
105 }
106
107
108 ///Direct reference to container of objects held by this list.
110 return _storage;
111 }
112
113
114 ///Number of contained objects (neglecting the ref count).
115 std::size_t size() const {
116 assert(_storage.size() == _refCount.size());
117
118 return _storage.size();
119 }
120
121 void reserve(std::size_t amount) {
122 _storage.reserve(amount);
123 _refCount.reserve(amount);
124 _orderedStorage.reserve(amount);
125 }
126
127
128 ///Check if empty.
129 bool empty() const {
130 return _storage.empty();
131 }
132
133
134 ///Find an item by comparing its adress.
135 template<typename Obj_t>
136 typename Container_t::const_iterator findByPointer(const Obj_t * item) const {
137 return std::find(_storage.begin(), _storage.end(), item);
138 }
139
140
141 ///Find an item by comparing strings returned by RooAbsArg::GetName()
142 typename Container_t::const_iterator findByName(const char * name) const {
143 //If this turns out to be a bottleneck,
144 //one could use the RooNameReg to obtain the pointer to the arg's name and compare these
145 const std::string theName(name);
146 auto byName = [&theName](const T * element) {
147 return element->GetName() == theName;
148 };
149
150 return std::find_if(_storage.begin(), _storage.end(), byName);
151 }
152
153
154 ///Find an item by comparing RooAbsArg::namePtr() adresses.
155 T* findByNamePointer(const T * item) const {
157 auto nptr = item->namePtr();
158 auto byNamePointer = [nptr](const T * element) {
159 return element->namePtr() == nptr;
160 };
161
162 auto found = std::find_if(_storage.begin(), _storage.end(), byNamePointer);
163 return found != _storage.end() ? *found : nullptr;
164 } else {
165 //As the collection is guaranteed to be sorted by namePtr() adress, we
166 //can use a binary search to look for `item` in this collection.
167 auto first = lowerBoundByNamePointer(item);
168 if(first == _orderedStorage.end()) return nullptr;
169 if(item->namePtr() != (*first)->namePtr()) return nullptr;
170 return *first;
171 }
172 }
173
174
175 ///Check if list contains an item using findByPointer().
176 template<typename Obj_t>
177 bool containsByPointer(const Obj_t * obj) const {
178 return findByPointer(obj) != _storage.end();
179 }
180
181
182 ///Check if list contains an item using findByNamePointer().
183 bool containsByNamePtr(const T * obj) const {
184 return findByNamePointer(obj);
185 }
186
187
188 ///Check if list contains an item using findByName().
189 bool containsSameName(const char * name) const {
190 return findByName(name) != _storage.end();
191 }
192
193
194 ///Decrease ref count of given object. Shrink list if ref count reaches 0.
195 ///\param obj Decrease ref count of given object. Compare by pointer.
196 ///\param force If true, remove irrespective of ref count.
197 ///Returns by how much the `refCount` for the element to be removed was
198 ///decreased (zero if nothing was removed). If `force == false`, it can
199 ///only be zero or one, if `force == true`, it can be the full `refCount`
200 ///for that element.
201 int Remove(const T * obj, bool force = false) {
202 auto item = findByPointer(obj);
203
204 if (item != _storage.end()) {
205 const std::size_t pos = item - _storage.begin();
206
207 const UInt_t origRefCount = _refCount[pos];
208
209 if (force || --_refCount[pos] == 0) {
210 //gcc4.x doesn't know how to erase at the position of a const_iterator
211 //Therefore, erase at begin + pos instead of 'item'
212 _storage.erase(_storage.begin() + pos);
213 _refCount.erase(_refCount.begin() + pos);
214 if(!_orderedStorage.empty()) {
215 // For the ordered storage, we could find by name pointer address
216 // with binary search, but this will not work anymore if one of the
217 // object pointers in this collection is dangling (can happen in
218 // RooFit...). However, the linear search by object address is
219 // acceptable, because we already do a linear search through
220 // _storage at the beginning of Remove().
221 _orderedStorage.erase(std::find(_orderedStorage.begin(), _orderedStorage.end(), obj));
222 }
223 return origRefCount;
224 }
225 return 1;
226 }
227
228 return 0;
229 }
230
231
232 ///Replace an element with a new value, keeping the same `refCount`. Will
233 ///return the `refCount` for that element if the replacement succeeded,
234 ///otherwise returns zero in case the `oldObj` could not be found in the
235 ///collection.
236 int Replace(const T * oldObj, T * newObj) {
237 auto item = findByPointer(oldObj);
238
239 if (item != _storage.end()) {
240 const std::size_t pos = item - _storage.begin();
241 _storage[pos] = newObj;
242 // The content has changed, so the ordered-by-name storage was invalidated.
243 _orderedStorage.clear();
244 return _refCount[pos];
245 }
246
247 return 0;
248 }
249
250
251 ///Remove from list irrespective of ref count.
252 void RemoveAll(const T * obj) {
253 Remove(obj, true);
254 }
255
256
257 private:
258 //Return an iterator to the last element in this sorted collection with a
259 //RooAbsArg::namePtr() adress smaller than for `item`.
260 typename std::vector<T*>::const_iterator lowerBoundByNamePointer(const T * item) const {
261
262 //If the _orderedStorage has not been initialized yet or needs resorting
263 //for other reasons, (re-)initialize it now.
265
266 return std::lower_bound(_orderedStorage.begin(), _orderedStorage.end(), item->namePtr(),
267 [](const auto& x, TNamed const* npt) -> bool {
268 return x->namePtr() < npt;
269 });
270 }
271
273 //If an RooAbsArg in this collection was renamed, the collection might
274 //not be sorted correctly anymore! The solution: every time any RooAbsArg
275 //is renamed, the RooNameReg::renameCounter gets incremented. The
276 //RooSTLRefCountList keeps track at which value of the counter it has
277 //been sorted last. If the counter increased in the meantime, a
278 //re-sorting is due.
280 }
281
283 _orderedStorage.clear();
284 _orderedStorage.reserve(_storage.size());
285 for(std::size_t i = 0; i < _storage.size(); ++i) {
286 _orderedStorage.push_back(_storage[i]);
287 }
288 std::sort(_orderedStorage.begin(), _orderedStorage.end(),
289 [](auto& a, auto& b) {
290 return a->namePtr() != b->namePtr() ? a->namePtr() < b->namePtr() : a < b;
291 });
293 }
294
296 std::vector<UInt_t> _refCount;
297 mutable std::vector<T*> _orderedStorage; //!
298 mutable unsigned long _renameCounterForLastSorting = 0; ///<!
299
300 // It is expensive to access the RooNameReg instance to get the counter for
301 // the renaming operations. That's why we have out own static pointer to
302 // the counter.
303 static std::size_t const* _renameCounter;
304
306};
307
308template<class T>
309std::size_t const* RooSTLRefCountList<T>::_renameCounter = nullptr;
310
311class RooAbsArg;
312class RooRefCountList;
313
314namespace RooFit {
315namespace STLRefCountListHelpers {
316 /// Converter from the old RooRefCountList to RooSTLRefCountList.
318}
319}
320
321#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:72
static const std::size_t & renameCounter()
renamed in this RooFit process.
Definition: RooNameReg.cxx:115
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.
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
int Replace(const T *oldObj, T *newObj)
Replace an element with a new value, keeping the same refCount.
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.
int Remove(const T *obj, bool force=false)
Decrease ref count of given object.
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
TArc a
Definition: textangle.C:12