Logo ROOT   6.18/05
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
27using namespace std;
28
30;
31
32/**
33\file RooHashTable.cxx
34\class RooHashTable
35\ingroup Roofitcore
36
37RooHashTable implements a hash table for TObjects. The hashing can be
38done on the object addresses, object names, or using the objects
39internal hash method. This is a utility class for RooLinkedList
40that 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
88void 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
177Bool_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
200TObject* 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
227TObject* 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())) {
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
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}
#define h(i)
Definition: RSha256.hxx:106
int Int_t
Definition: RtypesCore.h:41
const Bool_t kFALSE
Definition: RtypesCore.h:88
bool Bool_t
Definition: RtypesCore.h:59
double Double_t
Definition: RtypesCore.h:55
const Bool_t kTRUE
Definition: RtypesCore.h:87
#define ClassImp(name)
Definition: Rtypes.h:365
char name[80]
Definition: TGX11.cxx:109
RooAbsArg is the common abstract base class for objects that represent a value (of arbitrary type) an...
Definition: RooAbsArg.h:70
const TNamed * namePtr() const
Definition: RooAbsArg.h:506
RooArgSet is a container object that can hold multiple RooAbsArg objects.
Definition: RooArgSet.h:28
A one-time forward iterator working on RooLinkedList or RooAbsCollection.
RooAbsArg * next()
Return next element or nullptr if at end.
RooHashTable implements a hash table for TObjects.
Definition: RooHashTable.h:28
RooLinkedList ** _arr
Definition: RooHashTable.h:67
Bool_t remove(TObject *arg, TObject *hashArg=0)
Remove given object from table.
RooLinkedListElem * findLinkTo(const TObject *arg) const
Return RooLinkedList element link to object 'hashArg'.
Int_t _entries
Definition: RooHashTable.h:65
HashMethod _hashMethod
Definition: RooHashTable.h:63
Bool_t replace(const TObject *oldArg, const TObject *newArg, const TObject *oldHashArg=0)
Replace oldArg with newArg in the table.
ULong_t hash(const TObject *arg) const
Definition: RooHashTable.h:53
RooSetPair * findSetPair(const RooArgSet *set1, const RooArgSet *set2) const
Return RooSetPair with given pointers in table.
TObject * find(const char *name) const
Return the object with given name from the table.
virtual ~RooHashTable()
Destructor.
RooHashTable(Int_t initSize=17, HashMethod hashMethod=Name)
Construct a hash table with given capacity and hash method.
Int_t _usedSlots
Definition: RooHashTable.h:64
Double_t avgCollisions() const
Calculate the average number of collisions (table slots with >1 filled entry)
void add(TObject *arg, TObject *hashArg=0)
Add given object to table.
RooAbsArg * findArg(const RooAbsArg *arg) const
RooLinkedListElem is an link element for the RooLinkedList class.
RooLinkedList is an collection class for internal use, storing a collection of RooAbsArg pointers in ...
Definition: RooLinkedList.h:36
Int_t GetSize() const
Definition: RooLinkedList.h:61
RooFIter fwdIterator() const
Create a one-time-use forward iterator for this list.
RooAbsArg * findArg(const RooAbsArg *) const
Return pointer to object with given name in collection.
TObject * find(const char *name) const
Return pointer to object with given name in collection.
virtual void Add(TObject *arg)
Definition: RooLinkedList.h:63
void useNptr(Bool_t flag)
Definition: RooLinkedList.h:93
Bool_t Replace(const TObject *oldArg, const TObject *newArg)
Replace object 'oldArg' in collection with new object 'newArg'.
RooSetPair is a utility class that stores a pair of RooArgSets.
Definition: RooSetPair.h:26
RooArgSet * _set1
Definition: RooSetPair.h:37
virtual ULong_t Hash() const
Return hash value for this object.
Definition: RooSetPair.h:40
RooArgSet * _set2
Definition: RooSetPair.h:38
@ kInitHashTableCapacity
Definition: TCollection.h:157
virtual const char * GetName() const
Returns name of object.
Definition: TNamed.h:47
Mother of all ROOT objects.
Definition: TObject.h:37
R__ALWAYS_INLINE Bool_t TestBit(UInt_t f) const
Definition: TObject.h:172
Long_t NextPrime(Long_t x)
TMath Base functions.
Definition: TMathBase.cxx:30
Short_t Max(Short_t a, Short_t b)
Definition: TMathBase.h:212
ULong_t Hash(const void *txt, Int_t ntxt)
Calculates hash index from any char string.
Definition: TMath.cxx:1390