Logo ROOT  
Reference Guide
RooHashTable.cxx
Go to the documentation of this file.
1 /*****************************************************************************
2  * Project: RooFit *
3  * Package: RooFitCore *
4  * @(#)root/roofitcore:$Id$
5  * Authors: *
6  * WV, Wouter Verkerke, UC Santa Barbara, verkerke@slac.stanford.edu *
7  * DK, David Kirkby, UC Irvine, dkirkby@uci.edu *
8  * *
9  * Copyright (c) 2000-2005, Regents of the University of California *
10  * and Stanford University. All rights reserved. *
11  * *
12  * Redistribution and use in source and binary forms, *
13  * with or without modification, are permitted according to the terms *
14  * listed in LICENSE (http://roofit.sourceforge.net/license.txt) *
15  *****************************************************************************/
16 
18 
19 #include "RooFit.h"
20 
21 #include "TMath.h"
22 #include "TCollection.h"
23 #include "RooLinkedList.h"
24 #include "RooAbsArg.h"
25 #include "RooSetPair.h"
26 
27 using namespace std;
28 
30 ;
31 
32 /**
33 \file RooHashTable.cxx
34 \class RooHashTable
35 \ingroup Roofitcore
36 
37 RooHashTable implements a hash table for TObjects. The hashing can be
38 done on the object addresses, object names, or using the objects
39 internal hash method. This is a utility class for RooLinkedList
40 that uses RooHashTable to speed up direct access to large collections.
41 **/
42 
43 ////////////////////////////////////////////////////////////////////////////////
44 /// Construct a hash table with given capacity and hash method
45 
47  _hashMethod(hashMethod)
48 {
49  if (capacity <= 0) {
51  }
53  _arr = new RooLinkedList* [_size] ;
54  memset(_arr, 0, _size*sizeof(RooLinkedList*));
55 
56  _usedSlots = 0 ;
57  _entries = 0 ;
58 }
59 
60 
61 
62 ////////////////////////////////////////////////////////////////////////////////
63 /// Copy constructor
64 
66  TObject(other),
67  _hashMethod(other._hashMethod),
68  _usedSlots(other._usedSlots),
69  _entries(other._entries),
70  _size(other._size)
71 {
72  _arr = new RooLinkedList* [_size] ;
73  memset(_arr, 0, _size*sizeof(RooLinkedList*));
74  Int_t i ;
75  for (i=0 ; i<_size ; i++) {
76  if (other._arr[i]) {
77  _arr[i] = new RooLinkedList(*other._arr[i]) ;
78  }
79  }
80 }
81 
82 
83 
84 ////////////////////////////////////////////////////////////////////////////////
85 /// Add given object to table. If hashArg is given, hash will be calculation
86 /// on that rather than on 'arg'
87 
88 void RooHashTable::add(TObject* arg, TObject* hashArg)
89 {
90  Int_t slot = hash(hashArg?hashArg:arg) % _size ;
91  if (!_arr[slot]) {
92  _arr[slot] = new RooLinkedList(0) ;
93  _arr[slot]->useNptr(kFALSE) ;
94  _usedSlots++ ;
95  }
96  _arr[slot]->Add(arg);
97  _entries++;
98 }
99 
100 
101 
102 ////////////////////////////////////////////////////////////////////////////////
103 /// Remove given object from table. If hashArg is given, hash will be calculation
104 /// on that rather than on 'arg'
105 
107 {
108  Int_t slot = hash(hashArg?hashArg:arg) % _size ;
109  if (_arr[slot]) {
110  if (_arr[slot]->Remove(arg)) {
111  _entries-- ;
112  if (_arr[slot]->GetSize()==0) {
113  delete _arr[slot] ;
114  _arr[slot] = 0 ;
115  _usedSlots-- ;
116  }
117  return kTRUE ;
118  }
119  }
120 
121  if (_hashMethod != Name) return kFALSE;
122 
123  // If we didn't find it by name, see if it might have been renamed
124  RooAbsArg* p = dynamic_cast<RooAbsArg*>(arg);
125  //cout << "RooHashTable::remove possibly renamed '" << arg->GetName() << "', kRenamedArg=" << (p&&p->namePtr()->TestBit(RooNameReg::kRenamedArg)) << endl;
126  if (p && !p->namePtr()->TestBit(RooNameReg::kRenamedArg)) return kFALSE;
127 
128  // If so, check the whole list
129  Int_t i;
130  for (i=0 ; i<_size ; i++) {
131  if (i != slot && _arr[i] && _arr[i]->Remove(arg)) {
132  _entries-- ;
133  if (_arr[i]->GetSize()==0) {
134  delete _arr[i] ;
135  _arr[i] = 0 ;
136  _usedSlots-- ;
137  }
138  return kTRUE ;
139  }
140  }
141 
142  return kFALSE ;
143 }
144 
145 
146 
147 ////////////////////////////////////////////////////////////////////////////////
148 /// Calculate the average number of collisions (table slots with >1 filled entry)
149 
151 {
152  Int_t i,h[20] ;
153  for (i=0 ; i<20 ; i++) h[i]=0 ;
154 
155  for (i=0 ; i<_size ; i++) {
156  if (_arr[i]) {
157  Int_t count = _arr[i]->GetSize() ;
158  if (count<20) {
159  h[count]++ ;
160  } else {
161  h[19]++ ;
162  }
163  } else {
164  h[0]++ ;
165  }
166  }
167 
168  return 0 ;
169 }
170 
171 
172 
173 ////////////////////////////////////////////////////////////////////////////////
174 /// Replace oldArg with newArg in the table. If oldHashArg is given, use that to calculate
175 /// the hash associated with oldArg
176 
177 Bool_t RooHashTable::replace(const TObject* oldArg, const TObject* newArg, const TObject* oldHashArg)
178 {
179  Int_t slot = hash(oldHashArg?oldHashArg:oldArg) % _size ;
180  if (_arr[slot]) {
181  Int_t newSlot = hash(newArg) % _size ;
182  if (newSlot == slot) {
183  return _arr[slot]->Replace(oldArg,newArg) ;
184  }
185  }
186 
187  // We didn't find the oldArg or they have different slots.
188  if (remove((TObject*)oldArg,(TObject*)oldHashArg)) {
189  add((TObject*)newArg);
190  return kTRUE;
191  }
192  return kFALSE ;
193 }
194 
195 
196 
197 ////////////////////////////////////////////////////////////////////////////////
198 /// Return the object with given name from the table.
199 
200 TObject* RooHashTable::find(const char* name) const
201 {
202  if (_hashMethod != Name) assert(0) ;
203 
204  Int_t slot = TMath::Hash(name) % _size ;
205  if (_arr[slot]) return _arr[slot]->find(name) ;
206  return 0;
207 }
208 
209 
210 
211 ////////////////////////////////////////////////////////////////////////////////
212 
214 {
215  if (_hashMethod != Name) assert(0) ;
216 
217  Int_t slot = TMath::Hash(arg->GetName()) % _size ;
218  if (_arr[slot]) return _arr[slot]->findArg(arg) ;
219  return 0;
220 }
221 
222 
223 
224 ////////////////////////////////////////////////////////////////////////////////
225 /// Return object with the given pointer from the table
226 
227 TObject* RooHashTable::find(const TObject* hashArg) const
228 {
229  RooLinkedListElem* elem = findLinkTo(hashArg) ;
230  return elem ? elem->_arg : 0 ;
231 }
232 
233 
234 
235 ////////////////////////////////////////////////////////////////////////////////
236 /// Return RooLinkedList element link to object 'hashArg'
237 
239 {
240  if (_hashMethod != Pointer) assert(0) ;
241 
242  Int_t slot = hash(hashArg) % _size ;
243  RooLinkedList* lst = _arr[slot];
244  if (lst) {
245  RooFIter it = lst->fwdIterator() ;
246  TObject* obj;
247  while ((obj=it.next())) {
248  RooLinkedListElem* elem = (RooLinkedListElem*)obj ;
249  if (elem->_arg == hashArg) return elem ;
250  }
251  }
252  return 0;
253 }
254 
255 
256 
257 ////////////////////////////////////////////////////////////////////////////////
258 /// Return RooSetPair with given pointers in table
259 
260 RooSetPair* RooHashTable::findSetPair(const RooArgSet* set1, const RooArgSet* set2) const
261 {
262  if (_hashMethod != Intrinsic) assert(0) ;
263 
264  Int_t slot = RooSetPair(set1,set2).Hash() % _size ;
265  if (_arr[slot]) {
266  Int_t i ;
267  for (i=0 ; i<_arr[slot]->GetSize() ; i++) {
268  RooSetPair* pair = (RooSetPair*)_arr[slot]->At(i) ;
269  if (pair->_set1==set1 && pair->_set2==set2) {
270  return pair ;
271  }
272  }
273  }
274 
275  return 0 ;
276 }
277 
278 
279 
280 
281 ////////////////////////////////////////////////////////////////////////////////
282 /// Destructor
283 
285 {
286  Int_t i ;
287  for (i=0 ; i<_size ; i++) {
288  if (_arr[i]) delete _arr[i] ;
289  }
290  delete[] _arr ;
291 }
RooSetPair::_set2
RooArgSet * _set2
Definition: RooSetPair.h:38
RooLinkedList::find
TObject * find(const char *name) const
Return pointer to object with given name in collection.
Definition: RooLinkedList.cxx:603
RooHashTable::RooHashTable
RooHashTable(Int_t initSize=17, HashMethod hashMethod=Name)
Construct a hash table with given capacity and hash method.
Definition: RooHashTable.cxx:46
kTRUE
const Bool_t kTRUE
Definition: RtypesCore.h:100
RooHashTable::find
TObject * find(const char *name) const
Return the object with given name from the table.
Definition: RooHashTable.cxx:200
TObject::TestBit
R__ALWAYS_INLINE Bool_t TestBit(UInt_t f) const
Definition: TObject.h:187
RooHashTable::findArg
RooAbsArg * findArg(const RooAbsArg *arg) const
Definition: RooHashTable.cxx:213
RooHashTable::HashMethod
HashMethod
Definition: RooHashTable.h:33
RooHashTable::replace
Bool_t replace(const TObject *oldArg, const TObject *newArg, const TObject *oldHashArg=0)
Replace oldArg with newArg in the table.
Definition: RooHashTable.cxx:177
TMath::Max
Short_t Max(Short_t a, Short_t b)
Definition: TMathBase.h:212
RooHashTable::_usedSlots
Int_t _usedSlots
Definition: RooHashTable.h:66
RooFit.h
ClassImp
#define ClassImp(name)
Definition: Rtypes.h:364
TCollection.h
RooLinkedList::GetSize
Int_t GetSize() const
Definition: RooLinkedList.h:62
RooNameReg::kRenamedArg
@ kRenamedArg
Definition: RooNameReg.h:37
RooAbsArg::namePtr
const TNamed * namePtr() const
De-duplicated pointer to this object's name.
Definition: RooAbsArg.h:543
RooHashTable::remove
Bool_t remove(TObject *arg, TObject *hashArg=0)
Remove given object from table.
Definition: RooHashTable.cxx:106
RooAbsArg.h
Int_t
int Int_t
Definition: RtypesCore.h:45
RooHashTable::Intrinsic
@ Intrinsic
Definition: RooHashTable.h:33
RooLinkedList::fwdIterator
RooFIter fwdIterator() const
Create a one-time-use forward iterator for this list.
Definition: RooLinkedList.cxx:750
RooHashTable::add
void add(TObject *arg, TObject *hashArg=0)
Add given object to table.
Definition: RooHashTable.cxx:88
RooHashTable::_entries
Int_t _entries
Definition: RooHashTable.h:67
RooHashTable::_arr
RooLinkedList ** _arr
Definition: RooHashTable.h:69
bool
RooLinkedList::Replace
Bool_t Replace(const TObject *oldArg, const TObject *newArg)
Replace object 'oldArg' in collection with new object 'newArg'.
Definition: RooLinkedList.cxx:507
RooLinkedList::useNptr
void useNptr(Bool_t flag)
Definition: RooLinkedList.h:94
RooLinkedList::findArg
RooAbsArg * findArg(const RooAbsArg *) const
Return pointer to object with given name in collection.
Definition: RooLinkedList.cxx:659
RooLinkedListElem
RooLinkedListElem is an link element for the RooLinkedList class.
Definition: RooLinkedListElem.h:30
RooSetPair.h
RooHashTable::_hashMethod
HashMethod _hashMethod
Definition: RooHashTable.h:65
RooHashTable::hash
ULong_t hash(const TObject *arg) const
Definition: RooHashTable.h:55
RooSetPair
RooSetPair is a utility class that stores a pair of RooArgSets.
Definition: RooSetPair.h:26
TCollection::kInitHashTableCapacity
@ kInitHashTableCapacity
Definition: TCollection.h:157
RooHashTable::_size
Int_t _size
Definition: RooHashTable.h:68
h
#define h(i)
Definition: RSha256.hxx:106
RooHashTable
RooHashTable implements a hash table for TObjects.
Definition: RooHashTable.h:30
RooFIter
A one-time forward iterator working on RooLinkedList or RooAbsCollection.
Definition: RooLinkedListIter.h:40
kFALSE
const Bool_t kFALSE
Definition: RtypesCore.h:101
RooHashTable::findLinkTo
RooLinkedListElem * findLinkTo(const TObject *arg) const
Return RooLinkedList element link to object 'hashArg'.
Definition: RooHashTable.cxx:238
RooLinkedList
RooLinkedList is an collection class for internal use, storing a collection of RooAbsArg pointers in ...
Definition: RooLinkedList.h:37
TMath::NextPrime
Long_t NextPrime(Long_t x)
TMath Base functions.
Definition: TMathBase.cxx:30
RooFIter::next
RooAbsArg * next()
Return next element or nullptr if at end.
Definition: RooLinkedListIter.h:49
RooHashTable::Pointer
@ Pointer
Definition: RooHashTable.h:33
RooHashTable.h
RooLinkedList::Add
virtual void Add(TObject *arg)
Definition: RooLinkedList.h:64
RooSetPair::_set1
RooArgSet * _set1
Definition: RooSetPair.h:37
Double_t
double Double_t
Definition: RtypesCore.h:59
RooLinkedList.h
TObject
Mother of all ROOT objects.
Definition: TObject.h:37
RooLinkedListElem::_arg
TObject * _arg
Definition: RooLinkedListElem.h:92
RooHashTable::findSetPair
RooSetPair * findSetPair(const RooArgSet *set1, const RooArgSet *set2) const
Return RooSetPair with given pointers in table.
Definition: RooHashTable.cxx:260
name
char name[80]
Definition: TGX11.cxx:110
RooHashTable::~RooHashTable
virtual ~RooHashTable()
Destructor.
Definition: RooHashTable.cxx:284
RooAbsArg
RooAbsArg is the common abstract base class for objects that represent a value and a "shape" in RooFi...
Definition: RooAbsArg.h:72
TNamed::GetName
virtual const char * GetName() const
Returns name of object.
Definition: TNamed.h:47
TMath::Hash
ULong_t Hash(const void *txt, Int_t ntxt)
Calculates hash index from any char string.
Definition: TMath.cxx:1383
RooSetPair::Hash
virtual ULong_t Hash() const
Return hash value for this object.
Definition: RooSetPair.h:40
RooHashTable::avgCollisions
Double_t avgCollisions() const
Calculate the average number of collisions (table slots with >1 filled entry)
Definition: RooHashTable.cxx:150
RooHashTable::Name
@ Name
Definition: RooHashTable.h:33
TMath.h
RooArgSet
RooArgSet is a container object that can hold multiple RooAbsArg objects.
Definition: RooArgSet.h:33
int