Logo ROOT   6.10/09
Reference Guide
THashTable.cxx
Go to the documentation of this file.
1 // @(#)root/cont:$Id$
2 // Author: Fons Rademakers 27/09/95
3 
4 /*************************************************************************
5  * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers. *
6  * All rights reserved. *
7  * *
8  * For the licensing terms see $ROOTSYS/LICENSE. *
9  * For the list of contributors see $ROOTSYS/README/CREDITS. *
10  *************************************************************************/
11 
12 /** \class THashTable
13 \ingroup Containers
14 THashTable implements a hash table to store TObject's. The hash
15 value is calculated using the value returned by the TObject's
16 Hash() function. Each class inheriting from TObject can override
17 Hash() as it sees fit.
18 
19 THashTable does not preserve the insertion order of the objects.
20 If the insertion order is important AND fast retrieval is needed
21 use THashList instead.
22 */
23 
24 #include "THashTable.h"
25 #include "TObjectTable.h"
26 #include "TList.h"
27 #include "TError.h"
28 
30 
31 ////////////////////////////////////////////////////////////////////////////////
32 /// Create a THashTable object. Capacity is the initial hashtable capacity
33 /// (i.e. number of slots), by default kInitHashTableCapacity = 17, and
34 /// rehashlevel is the value at which a rehash will be triggered. I.e. when
35 /// the average size of the linked lists at a slot becomes longer than
36 /// rehashlevel then the hashtable will be resized and refilled to reduce
37 /// the collision rate to about 1. The higher the collision rate, i.e. the
38 /// longer the linked lists, the longer lookup will take. If rehashlevel=0
39 /// the table will NOT automatically be rehashed. Use Rehash() for manual
40 /// rehashing.
41 
42 THashTable::THashTable(Int_t capacity, Int_t rehashlevel)
43 {
44  if (capacity < 0) {
45  Warning("THashTable", "capacity (%d) < 0", capacity);
47  } else if (capacity == 0)
49 
51  fCont = new TList* [fSize];
52  memset(fCont, 0, fSize*sizeof(TList*));
53 
54  fEntries = 0;
55  fUsedSlots = 0;
56  if (rehashlevel < 2) rehashlevel = 0;
57  fRehashLevel = rehashlevel;
58 }
59 
60 ////////////////////////////////////////////////////////////////////////////////
61 /// Delete a hashtable. Objects are not deleted unless the THashTable is the
62 /// owner (set via SetOwner()).
63 
65 {
66  if (fCont) Clear();
67  delete [] fCont;
68  fCont = 0;
69  fSize = 0;
70 }
71 
72 ////////////////////////////////////////////////////////////////////////////////
73 /// Add object to the hash table. Its position in the table will be
74 /// determined by the value returned by its Hash() function.
75 
77 {
78  if (IsArgNull("Add", obj)) return;
79 
80  Int_t slot = GetHashValue(obj);
81  if (!fCont[slot]) {
82  fCont[slot] = new TList;
83  fUsedSlots++;
84  }
85  fCont[slot]->Add(obj);
86  fEntries++;
87 
90 }
91 
92 ////////////////////////////////////////////////////////////////////////////////
93 /// Add object to the hash table. Its position in the table will be
94 /// determined by the value returned by its Hash() function.
95 /// If and only if 'before' is in the same bucket as obj, obj is added
96 /// in front of 'before' within the bucket's list.
97 
98 void THashTable::AddBefore(const TObject *before, TObject *obj)
99 {
100  if (IsArgNull("Add", obj)) return;
101 
102  Int_t slot = GetHashValue(obj);
103  if (!fCont[slot]) {
104  fCont[slot] = new TList;
105  fUsedSlots++;
106  }
107  if (before && GetHashValue(before) == slot) {
108  fCont[slot]->AddBefore(before,obj);
109  } else {
110  fCont[slot]->Add(obj);
111  }
112  fEntries++;
113 
115  Rehash(fEntries);
116 }
117 
118 ////////////////////////////////////////////////////////////////////////////////
119 /// Add all objects from collection col to this collection.
120 /// Implemented for more efficient rehashing.
121 
123 {
124  // Hashing after AddAll can be much more expensive than
125  // hashing before, as we need to add more elements.
126  // We assume an ideal hash, i.e. fUsedSlots==fSize.
127  Int_t sumEntries=fEntries+col->GetEntries();
128  Bool_t rehashBefore=fRehashLevel && (sumEntries > fSize*fRehashLevel);
129  if (rehashBefore)
130  Rehash(sumEntries);
131 
132  // prevent Add from Rehashing
133  Int_t saveRehashLevel=fRehashLevel;
134  fRehashLevel=0;
135 
136  TCollection::AddAll(col);
137 
138  fRehashLevel=saveRehashLevel;
139  // If we didn't Rehash before, we might have to do it
140  // now, due to a non-perfect hash function.
141  if (!rehashBefore && fRehashLevel && AverageCollisions() > fRehashLevel)
142  Rehash(fEntries);
143 }
144 
145 ////////////////////////////////////////////////////////////////////////////////
146 /// Remove all objects from the table. Does not delete the objects
147 /// unless the THashTable is the owner (set via SetOwner()).
148 
150 {
151  for (int i = 0; i < fSize; i++) {
152  // option "nodelete" is passed when Clear is called from
153  // THashList::Clear() or THashList::Delete() or Rehash().
154  if (fCont[i]) {
155  if (IsOwner())
156  fCont[i]->SetOwner();
157  fCont[i]->Clear(option);
158  }
159  SafeDelete(fCont[i]);
160  }
161 
162  fEntries = 0;
163  fUsedSlots = 0;
164 }
165 
166 ////////////////////////////////////////////////////////////////////////////////
167 /// Returns the number of collisions for an object with a certain name
168 /// (i.e. number of objects in same slot in the hash table, i.e. length
169 /// of linked list).
170 
172 {
173  Int_t slot = GetHashValue(name);
174  if (fCont[slot]) return fCont[slot]->GetSize();
175  return 0;
176 }
177 
178 ////////////////////////////////////////////////////////////////////////////////
179 /// Returns the number of collisions for an object (i.e. number of objects
180 /// in same slot in the hash table, i.e. length of linked list).
181 
183 {
184  if (IsArgNull("Collisions", obj)) return 0;
185 
186  Int_t slot = GetHashValue(obj);
187  if (fCont[slot]) return fCont[slot]->GetSize();
188  return 0;
189 }
190 
191 ////////////////////////////////////////////////////////////////////////////////
192 /// Remove all objects from the table AND delete all heap based objects.
193 
195 {
196  for (int i = 0; i < fSize; i++)
197  if (fCont[i]) {
198  fCont[i]->Delete();
199  SafeDelete(fCont[i]);
200  }
201 
202  fEntries = 0;
203  fUsedSlots = 0;
204 }
205 
206 ////////////////////////////////////////////////////////////////////////////////
207 /// Find object using its name. Uses the hash value returned by the
208 /// TString::Hash() after converting name to a TString.
209 
211 {
212  Int_t slot = GetHashValue(name);
213  if (fCont[slot]) return fCont[slot]->FindObject(name);
214  return 0;
215 }
216 
217 ////////////////////////////////////////////////////////////////////////////////
218 /// Find object using its hash value (returned by its Hash() member).
219 
221 {
222  if (IsArgNull("FindObject", obj)) return 0;
223 
224  Int_t slot = GetHashValue(obj);
225  if (fCont[slot]) return fCont[slot]->FindObject(obj);
226  return 0;
227 }
228 
229 ////////////////////////////////////////////////////////////////////////////////
230 /// Return the TList corresponding to object's name based hash value.
231 /// One can iterate this list "manually" to find, e.g. objects with
232 /// the same name.
233 
234 const TList *THashTable::GetListForObject(const char *name) const
235 {
236  return fCont[GetHashValue(name)];
237 }
238 
239 ////////////////////////////////////////////////////////////////////////////////
240 /// Return the TList corresponding to object's hash value.
241 /// One can iterate this list "manually" to find, e.g. identical
242 /// objects.
243 
245 {
246  if (IsArgNull("GetListForObject", obj)) return 0;
247  return fCont[GetHashValue(obj)];
248 }
249 
250 ////////////////////////////////////////////////////////////////////////////////
251 /// Return address of pointer to obj
252 
254 {
255  if (IsArgNull("GetObjectRef", obj)) return 0;
256 
257  Int_t slot = GetHashValue(obj);
258  if (fCont[slot]) return fCont[slot]->GetObjectRef(obj);
259  return 0;
260 }
261 
262 ////////////////////////////////////////////////////////////////////////////////
263 /// Returns a hash table iterator.
264 
266 {
267  return new THashTableIter(this, dir);
268 }
269 
270 ////////////////////////////////////////////////////////////////////////////////
271 /// Rehash the hashtable. If the collision rate becomes too high (i.e.
272 /// the average size of the linked lists become too long) then lookup
273 /// efficiency decreases since relatively long lists have to be searched
274 /// every time. To improve performance rehash the hashtable. This resizes
275 /// the table to newCapacity slots and refills the table. Use
276 /// AverageCollisions() to check if you need to rehash. Set checkObjValidity
277 /// to kFALSE if you know that all objects in the table are still valid
278 /// (i.e. have not been deleted from the system in the meanwhile).
279 
280 void THashTable::Rehash(Int_t newCapacity, Bool_t checkObjValidity)
281 {
282  THashTable *ht = new THashTable(newCapacity);
283 
284  TIter next(this);
285  TObject *obj;
286 
287  if (checkObjValidity && TObject::GetObjectStat() && gObjectTable) {
288  while ((obj = next()))
289  if (gObjectTable->PtrIsValid(obj)) ht->Add(obj);
290  } else {
291  while ((obj = next()))
292  ht->Add(obj);
293  }
294 
295  Clear("nodelete");
296  delete [] fCont;
297  fCont = ht->fCont;
298  ht->fCont = 0;
299 
300  fSize = ht->fSize; // idem
301  fEntries = ht->fEntries;
302  fUsedSlots = ht->fUsedSlots;
303 
304  // this should not happen, but it will prevent an endless loop
305  // in case of a very bad hash function
307  fRehashLevel = (int)AverageCollisions() + 1;
308 
309  delete ht;
310 }
311 
312 ////////////////////////////////////////////////////////////////////////////////
313 /// Remove object from the hashtable.
314 
316 {
317  Int_t slot = GetHashValue(obj);
318  if (fCont[slot]) {
319  TObject *ob = fCont[slot]->Remove(obj);
320  if (ob) {
321  fEntries--;
322  if (fCont[slot]->GetSize() == 0) {
323  SafeDelete(fCont[slot]);
324  fUsedSlots--;
325  }
326  return ob;
327  }
328  }
329  return 0;
330 }
331 
332 ////////////////////////////////////////////////////////////////////////////////
333 /// Remove object from the hashtable without using the hash value.
334 
336 {
337  for (int i = 0; i < fSize; i++) {
338  if (fCont[i]) {
339  TObject *ob = fCont[i]->Remove(obj);
340  if (ob) {
341  fEntries--;
342  if (fCont[i]->GetSize() == 0) {
343  SafeDelete(fCont[i]);
344  fUsedSlots--;
345  }
346  return ob;
347  }
348  }
349  }
350  return 0;
351 }
352 
353 /** \class THashTableIter
354 Iterator of hash table.
355 */
356 
358 
359 ////////////////////////////////////////////////////////////////////////////////
360 /// Create a hashtable iterator. By default the iteration direction
361 /// is kIterForward. To go backward use kIterBackward.
362 
364 {
365  fTable = ht;
366  fDirection = dir;
367  fListCursor = 0;
368  Reset();
369 }
370 
371 ////////////////////////////////////////////////////////////////////////////////
372 /// Copy ctor.
373 
375 {
376  fTable = iter.fTable;
377  fDirection = iter.fDirection;
378  fCursor = iter.fCursor;
379  fListCursor = 0;
380  if (iter.fListCursor) {
382  if (fListCursor)
383  fListCursor->operator=(*iter.fListCursor);
384  }
385 }
386 
387 ////////////////////////////////////////////////////////////////////////////////
388 /// Overridden assignment operator.
389 
391 {
392  if (this != &rhs && rhs.IsA() == THashTableIter::Class()) {
393  const THashTableIter &rhs1 = (const THashTableIter &)rhs;
394  fTable = rhs1.fTable;
395  fDirection = rhs1.fDirection;
396  fCursor = rhs1.fCursor;
397  if (rhs1.fListCursor) {
399  if (fListCursor)
400  fListCursor->operator=(*rhs1.fListCursor);
401  }
402  }
403  return *this;
404 }
405 
406 ////////////////////////////////////////////////////////////////////////////////
407 /// Overloaded assignment operator.
408 
410 {
411  if (this != &rhs) {
412  fTable = rhs.fTable;
413  fDirection = rhs.fDirection;
414  fCursor = rhs.fCursor;
415  if (rhs.fListCursor) {
417  if (fListCursor)
418  fListCursor->operator=(*rhs.fListCursor);
419  }
420  }
421  return *this;
422 }
423 
424 ////////////////////////////////////////////////////////////////////////////////
425 /// Delete hashtable iterator.
426 
428 {
429  delete fListCursor;
430 }
431 
432 ////////////////////////////////////////////////////////////////////////////////
433 /// Return next object in hashtable. Returns 0 when no more objects in table.
434 
436 {
437  while (kTRUE) {
438  if (!fListCursor) {
439  int slot = NextSlot();
440  if (slot == -1) return 0;
442  }
443 
444  TObject *obj = fListCursor->Next();
445  if (obj) return obj;
446 
448  }
449 }
450 
451 ////////////////////////////////////////////////////////////////////////////////
452 /// Returns index of next slot in table containing list to be iterated.
453 
455 {
456  if (fDirection == kIterForward) {
457  for ( ; fCursor < fTable->Capacity() && fTable->fCont[fCursor] == 0;
458  fCursor++) { }
459 
460  if (fCursor < fTable->Capacity())
461  return fCursor++;
462 
463  } else {
464  for ( ; fCursor >= 0 && fTable->fCont[fCursor] == 0;
465  fCursor--) { }
466 
467  if (fCursor >= 0)
468  return fCursor--;
469  }
470  return -1;
471 }
472 
473 ////////////////////////////////////////////////////////////////////////////////
474 /// Reset the hashtable iterator. Either to beginning or end, depending on
475 /// the initial iteration direction.
476 
478 {
479  if (fDirection == kIterForward)
480  fCursor = 0;
481  else
482  fCursor = fTable->Capacity() - 1;
484 }
485 
486 ////////////////////////////////////////////////////////////////////////////////
487 /// This operator compares two TIterator objects.
488 
490 {
491  if (aIter.IsA() == THashTableIter::Class()) {
492  const THashTableIter &iter(dynamic_cast<const THashTableIter &>(aIter));
493  return (fListCursor != iter.fListCursor);
494  }
495  return false; // for base class we don't implement a comparison
496 }
497 
498 ////////////////////////////////////////////////////////////////////////////////
499 /// This operator compares two THashTableIter objects.
500 
502 {
503  return (fListCursor != aIter.fListCursor);
504 }
505 
506 ////////////////////////////////////////////////////////////////////////////////
507 /// Return pointer to current object or nullptr.
508 
510 {
511  return (fListCursor ? fListCursor->operator*() : nullptr);
512 }
virtual void Delete(Option_t *option="")
Remove all objects from the list AND delete all heap based objects.
Definition: TList.cxx:409
virtual void AddAll(const TCollection *col)
Add all objects from collection col to this collection.
Definition: THashTable.cxx:122
void AddBefore(const TObject *before, TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:98
void Reset()
Reset the hashtable iterator.
Definition: THashTable.cxx:477
TList ** fCont
Definition: THashTable.h:40
TObject ** GetObjectRef(const TObject *obj) const
Return address of pointer to obj.
Definition: THashTable.cxx:253
const char Option_t
Definition: RtypesCore.h:62
virtual void SetOwner(Bool_t enable=kTRUE)
Set whether this collection is the owner (enable==true) of its content.
Bool_t IsArgNull(const char *where, const TObject *obj) const
Returns true if object is a null pointer.
virtual Int_t GetEntries() const
Definition: TCollection.h:86
virtual void AddAll(const TCollection *col)
Add all objects from collection col to this collection.
Definition: TCollection.cxx:58
void Rehash(Int_t newCapacity, Bool_t checkObjValidity=kTRUE)
Rehash the hashtable.
Definition: THashTable.cxx:280
Float_t AverageCollisions() const
Definition: THashTable.h:79
Int_t fUsedSlots
Definition: THashTable.h:42
const TList * GetListForObject(const char *name) const
Return the TList corresponding to object&#39;s name based hash value.
Definition: THashTable.cxx:234
int Int_t
Definition: RtypesCore.h:41
bool Bool_t
Definition: RtypesCore.h:59
TObject * RemoveSlow(TObject *obj)
Remove object from the hashtable without using the hash value.
Definition: THashTable.cxx:335
TObject * Next()
Return next object in the list. Returns 0 when no more objects in list.
Definition: TList.cxx:937
TListIter * fListCursor
Definition: THashTable.h:107
const THashTable * fTable
Definition: THashTable.h:105
Iterator abstract base class.
Definition: TIterator.h:30
Iterator of linked list.
Definition: TList.h:183
virtual TObject * FindObject(const char *name) const
Find an object in this list using its name.
Definition: TList.cxx:501
THashTable(const THashTable &)
friend class THashTableIter
Definition: THashTable.h:37
#define SafeDelete(p)
Definition: RConfig.h:499
Iterator of hash table.
Definition: THashTable.h:102
THashTable implements a hash table to store TObject&#39;s.
Definition: THashTable.h:35
void Class()
Definition: Class.C:29
void Clear(Option_t *option="")
Remove all objects from the table.
Definition: THashTable.cxx:149
const Bool_t kIterForward
Definition: TCollection.h:37
Bool_t IsOwner() const
Definition: TCollection.h:95
Int_t NextSlot()
Returns index of next slot in table containing list to be iterated.
Definition: THashTable.cxx:454
~THashTableIter()
Delete hashtable iterator.
Definition: THashTable.cxx:427
TObject * operator*() const
Return pointer to current object or nullptr.
Definition: THashTable.cxx:509
Bool_t fDirection
Definition: THashTable.h:108
A doubly linked list.
Definition: TList.h:43
Int_t fEntries
Definition: THashTable.h:41
const TCollection * GetCollection() const
Definition: TList.h:205
virtual TIterator * MakeIterator(Bool_t dir=kIterForward) const =0
virtual TObject * Remove(TObject *obj)
Remove object from the list.
Definition: TList.cxx:679
Collection abstract base class.
Definition: TCollection.h:42
virtual ~THashTable()
Delete a hashtable.
Definition: THashTable.cxx:64
Bool_t PtrIsValid(TObject *obj)
Definition: TObjectTable.h:78
Int_t fSize
Definition: TCollection.h:57
void Reset(Detail::TBranchProxy *x)
void Warning(const char *location, const char *msgfmt,...)
static Bool_t GetObjectStat()
Get status of object stat flag.
Definition: TObject.cxx:947
virtual void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the list.
Definition: TList.cxx:177
TIterator * MakeIterator(Bool_t dir=kIterForward) const
Returns a hash table iterator.
Definition: THashTable.cxx:265
R__EXTERN TObjectTable * gObjectTable
Definition: TObjectTable.h:82
Int_t Collisions(const char *name) const
Returns the number of collisions for an object with a certain name (i.e.
Definition: THashTable.cxx:171
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
Definition: THashTable.cxx:390
TObject * FindObject(const char *name) const
Find object using its name.
Definition: THashTable.cxx:210
#define ClassImp(name)
Definition: Rtypes.h:336
Int_t GetSize() const
Definition: THashTable.h:69
void Add(TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:76
virtual void Clear(Option_t *option="")
Remove all objects from the list.
Definition: TList.cxx:353
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
void Delete(Option_t *option="")
Remove all objects from the table AND delete all heap based objects.
Definition: THashTable.cxx:194
Int_t fRehashLevel
Definition: THashTable.h:43
virtual void Add(TObject *obj)
Definition: TList.h:77
Short_t Max(Short_t a, Short_t b)
Definition: TMathBase.h:200
Int_t Capacity() const
Definition: TCollection.h:74
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
Definition: THashTable.cxx:489
TObject * Next()
Return next object in hashtable. Returns 0 when no more objects in table.
Definition: THashTable.cxx:435
virtual Int_t GetSize() const
Definition: TCollection.h:89
const Bool_t kTRUE
Definition: RtypesCore.h:91
Int_t GetHashValue(const TObject *obj) const
Definition: THashTable.h:87
virtual TObject ** GetObjectRef(const TObject *obj) const
Return address of pointer to obj.
Definition: TList.cxx:570
TObject * Remove(TObject *obj)
Remove object from the hashtable.
Definition: THashTable.cxx:315