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
17#include "RooFit.h"
18
19#include "TMath.h"
20#include "TCollection.h"
21#include "RooHashTable.h"
22#include "RooLinkedList.h"
23#include "RooAbsArg.h"
24#include "RooSetPair.h"
25
26using namespace std;
27
29;
30
31/**
32\file RooHashTable.cxx
33\class RooHashTable
34\ingroup Roofitcore
35
36RooHashTable implements a hash table for TObjects. The hashing can be
37done on the object addresses, object names, or using the objects
38internal hash method. This is a utility class for RooLinkedList
39that uses RooHashTable to speed up direct access to large collections.
40**/
41
42////////////////////////////////////////////////////////////////////////////////
43/// Construct a hash table with given capacity and hash method
44
46 _hashMethod(hashMethod)
47{
48 if (capacity <= 0) {
50 }
52 _arr = new RooLinkedList* [_size] ;
53 memset(_arr, 0, _size*sizeof(RooLinkedList*));
54
55 _usedSlots = 0 ;
56 _entries = 0 ;
57}
58
59
60
61////////////////////////////////////////////////////////////////////////////////
62/// Copy constructor
63
65 TObject(other),
66 _hashMethod(other._hashMethod),
67 _usedSlots(other._usedSlots),
68 _entries(other._entries),
69 _size(other._size)
70{
71 _arr = new RooLinkedList* [_size] ;
72 memset(_arr, 0, _size*sizeof(RooLinkedList*));
73 Int_t i ;
74 for (i=0 ; i<_size ; i++) {
75 if (other._arr[i]) {
76 _arr[i] = new RooLinkedList(*other._arr[i]) ;
77 }
78 }
79}
80
81
82
83////////////////////////////////////////////////////////////////////////////////
84/// Add given object to table. If hashArg is given, hash will be calculation
85/// on that rather than on 'arg'
86
87void RooHashTable::add(TObject* arg, TObject* hashArg)
88{
89 Int_t slot = hash(hashArg?hashArg:arg) % _size ;
90 if (!_arr[slot]) {
91 _arr[slot] = new RooLinkedList(0) ;
92 _arr[slot]->useNptr(kFALSE) ;
93 _usedSlots++ ;
94 }
95 _arr[slot]->Add(arg);
96 _entries++;
97}
98
99
100
101////////////////////////////////////////////////////////////////////////////////
102/// Remove given object from table. If hashArg is given, hash will be calculation
103/// on that rather than on 'arg'
104
106{
107 Int_t slot = hash(hashArg?hashArg:arg) % _size ;
108 if (_arr[slot]) {
109 if (_arr[slot]->Remove(arg)) {
110 _entries-- ;
111 if (_arr[slot]->GetSize()==0) {
112 delete _arr[slot] ;
113 _arr[slot] = 0 ;
114 _usedSlots-- ;
115 }
116 return kTRUE ;
117 }
118 }
119
120 if (_hashMethod != Name) return kFALSE;
121
122 // If we didn't find it by name, see if it might have been renamed
123 RooAbsArg* p = dynamic_cast<RooAbsArg*>(arg);
124 //cout << "RooHashTable::remove possibly renamed '" << arg->GetName() << "', kRenamedArg=" << (p&&p->namePtr()->TestBit(RooNameReg::kRenamedArg)) << endl;
125 if (p && !p->namePtr()->TestBit(RooNameReg::kRenamedArg)) return kFALSE;
126
127 // If so, check the whole list
128 Int_t i;
129 for (i=0 ; i<_size ; i++) {
130 if (i != slot && _arr[i] && _arr[i]->Remove(arg)) {
131 _entries-- ;
132 if (_arr[i]->GetSize()==0) {
133 delete _arr[i] ;
134 _arr[i] = 0 ;
135 _usedSlots-- ;
136 }
137 return kTRUE ;
138 }
139 }
140
141 return kFALSE ;
142}
143
144
145
146////////////////////////////////////////////////////////////////////////////////
147/// Calculate the average number of collisions (table slots with >1 filled entry)
148
150{
151 Int_t i,h[20] ;
152 for (i=0 ; i<20 ; i++) h[i]=0 ;
153
154 for (i=0 ; i<_size ; i++) {
155 if (_arr[i]) {
156 Int_t count = _arr[i]->GetSize() ;
157 if (count<20) {
158 h[count]++ ;
159 } else {
160 h[19]++ ;
161 }
162 } else {
163 h[0]++ ;
164 }
165 }
166
167 return 0 ;
168}
169
170
171
172////////////////////////////////////////////////////////////////////////////////
173/// Replace oldArg with newArg in the table. If oldHashArg is given, use that to calculate
174/// the hash associated with oldArg
175
176Bool_t RooHashTable::replace(const TObject* oldArg, const TObject* newArg, const TObject* oldHashArg)
177{
178 Int_t slot = hash(oldHashArg?oldHashArg:oldArg) % _size ;
179 if (_arr[slot]) {
180 Int_t newSlot = hash(newArg) % _size ;
181 if (newSlot == slot) {
182 return _arr[slot]->Replace(oldArg,newArg) ;
183 }
184 }
185
186 // We didn't find the oldArg or they have different slots.
187 if (remove((TObject*)oldArg,(TObject*)oldHashArg)) {
188 add((TObject*)newArg);
189 return kTRUE;
190 }
191 return kFALSE ;
192}
193
194
195
196////////////////////////////////////////////////////////////////////////////////
197/// Return the object with given name from the table.
198
199TObject* RooHashTable::find(const char* name) const
200{
201 if (_hashMethod != Name) assert(0) ;
202
203 Int_t slot = TMath::Hash(name) % _size ;
204 if (_arr[slot]) return _arr[slot]->find(name) ;
205 return 0;
206}
207
208
209
210////////////////////////////////////////////////////////////////////////////////
211
213{
214 if (_hashMethod != Name) assert(0) ;
215
216 Int_t slot = TMath::Hash(arg->GetName()) % _size ;
217 if (_arr[slot]) return _arr[slot]->findArg(arg) ;
218 return 0;
219}
220
221
222
223////////////////////////////////////////////////////////////////////////////////
224/// Return object with the given pointer from the table
225
226TObject* RooHashTable::find(const TObject* hashArg) const
227{
228 RooLinkedListElem* elem = findLinkTo(hashArg) ;
229 return elem ? elem->_arg : 0 ;
230}
231
232
233
234////////////////////////////////////////////////////////////////////////////////
235/// Return RooLinkedList element link to object 'hashArg'
236
238{
239 if (_hashMethod != Pointer) assert(0) ;
240
241 Int_t slot = hash(hashArg) % _size ;
242 RooLinkedList* lst = _arr[slot];
243 if (lst) {
244 RooFIter it = lst->fwdIterator() ;
245 TObject* obj;
246 while ((obj=it.next())) {
248 if (elem->_arg == hashArg) return elem ;
249 }
250 }
251 return 0;
252}
253
254
255
256////////////////////////////////////////////////////////////////////////////////
257/// Return RooSetPair with given pointers in table
258
260{
261 if (_hashMethod != Intrinsic) assert(0) ;
262
263 Int_t slot = RooSetPair(set1,set2).Hash() % _size ;
264 if (_arr[slot]) {
265 Int_t i ;
266 for (i=0 ; i<_arr[slot]->GetSize() ; i++) {
267 RooSetPair* pair = (RooSetPair*)_arr[slot]->At(i) ;
268 if (pair->_set1==set1 && pair->_set2==set2) {
269 return pair ;
270 }
271 }
272 }
273
274 return 0 ;
275}
276
277
278
279
280////////////////////////////////////////////////////////////////////////////////
281/// Destructor
282
284{
285 Int_t i ;
286 for (i=0 ; i<_size ; i++) {
287 if (_arr[i]) delete _arr[i] ;
288 }
289 delete[] _arr ;
290}
#define h(i)
Definition: RSha256.hxx:106
int Int_t
Definition: RtypesCore.h:43
const Bool_t kFALSE
Definition: RtypesCore.h:90
bool Bool_t
Definition: RtypesCore.h:61
double Double_t
Definition: RtypesCore.h:57
const Bool_t kTRUE
Definition: RtypesCore.h:89
#define ClassImp(name)
Definition: Rtypes.h:361
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:73
const TNamed * namePtr() const
Definition: RooAbsArg.h:499
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:35
Int_t GetSize() const
Definition: RooLinkedList.h:60
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:62
void useNptr(Bool_t flag)
Definition: RooLinkedList.h:92
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:187
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:1383