Logo ROOT   6.12/07
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 
17 #include "RooFit.h"
18 
19 #include "TMath.h"
20 #include "TMath.h"
21 #include "TCollection.h"
22 #include "RooHashTable.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 }
virtual const char * GetName() const
Returns name of object.
Definition: TNamed.h:47
Double_t avgCollisions() const
Calculate the average number of collisions (table slots with >1 filled entry)
Int_t _entries
Definition: RooHashTable.h:65
TH1 * h
Definition: legend2.C:5
TObject * find(const char *name) const
Return pointer to object with given name in collection.
RooHashTable(Int_t initSize=17, HashMethod hashMethod=Name)
Construct a hash table with given capacity and hash method.
R__ALWAYS_INLINE Bool_t TestBit(UInt_t f) const
Definition: TObject.h:172
RooFIter fwdIterator() const
int Int_t
Definition: RtypesCore.h:41
bool Bool_t
Definition: RtypesCore.h:59
Bool_t replace(const TObject *oldArg, const TObject *newArg, const TObject *oldHashArg=0)
Replace oldArg with newArg in the table.
STL namespace.
Int_t _usedSlots
Definition: RooHashTable.h:64
Int_t GetSize() const
Definition: RooLinkedList.h:60
Bool_t Replace(const TObject *oldArg, const TObject *newArg)
Replace object &#39;oldArg&#39; in collection with new object &#39;newArg&#39;.
virtual ULong_t Hash() const
Return hash value for this object.
Definition: RooSetPair.h:40
RooLinkedListElem * findLinkTo(const TObject *arg) const
Return RooLinkedList element link to object &#39;hashArg&#39;.
RooArgSet * _set1
Definition: RooSetPair.h:37
RooHashTable implements a hash table for TObjects.
Definition: RooHashTable.h:28
void useNptr(Bool_t flag)
Definition: RooLinkedList.h:92
RooArgSet * _set2
Definition: RooSetPair.h:38
virtual void Add(TObject *arg)
Definition: RooLinkedList.h:62
void add(TObject *arg, TObject *hashArg=0)
Add given object to table.
RooSetPair * findSetPair(const RooArgSet *set1, const RooArgSet *set2) const
Return RooSetPair with given pointers in table.
HashMethod _hashMethod
Definition: RooHashTable.h:63
TObject * find(const char *name) const
Return the object with given name from the table.
Bool_t remove(TObject *arg, TObject *hashArg=0)
Remove given object from table.
ULong_t Hash(const void *txt, Int_t ntxt)
Calculates hash index from any char string.
Definition: TMath.cxx:1378
virtual ~RooHashTable()
Destructor.
RooAbsArg * next()
const Bool_t kFALSE
Definition: RtypesCore.h:88
RooLinkedList is an collection class for internal use, storing a collection of RooAbsArg pointers in ...
Definition: RooLinkedList.h:35
#define ClassImp(name)
Definition: Rtypes.h:359
double Double_t
Definition: RtypesCore.h:55
Mother of all ROOT objects.
Definition: TObject.h:37
Long_t NextPrime(Long_t x)
TMath Base functionsDefine the functions Min, Max, Abs, Sign, Range for all types.
Definition: TMathBase.cxx:30
RooLinkedList ** _arr
Definition: RooHashTable.h:67
Short_t Max(Short_t a, Short_t b)
Definition: TMathBase.h:200
ULong_t hash(const TObject *arg) const
Definition: RooHashTable.h:53
RooAbsArg * findArg(const RooAbsArg *) const
Return pointer to object with given name in collection.
RooLinkedListElem is an link element for the RooLinkedList class.
RooAbsArg * findArg(const RooAbsArg *arg) const
RooAbsArg is the common abstract base class for objects that represent a value (of arbitrary type) an...
Definition: RooAbsArg.h:66
RooSetPair is a utility class that stores a pair of RooArgSets.
Definition: RooSetPair.h:26
const Bool_t kTRUE
Definition: RtypesCore.h:87
char name[80]
Definition: TGX11.cxx:109
const TNamed * namePtr() const
Definition: RooAbsArg.h:461