Logo ROOT   6.12/07
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 #include "TROOT.h"
29 
31 
32 ////////////////////////////////////////////////////////////////////////////////
33 /// Create a THashTable object. Capacity is the initial hashtable capacity
34 /// (i.e. number of slots), by default kInitHashTableCapacity = 17, and
35 /// rehashlevel is the value at which a rehash will be triggered. I.e. when
36 /// the average size of the linked lists at a slot becomes longer than
37 /// rehashlevel then the hashtable will be resized and refilled to reduce
38 /// the collision rate to about 1. The higher the collision rate, i.e. the
39 /// longer the linked lists, the longer lookup will take. If rehashlevel=0
40 /// the table will NOT automatically be rehashed. Use Rehash() for manual
41 /// rehashing.
42 
43 THashTable::THashTable(Int_t capacity, Int_t rehashlevel)
44 {
45  if (capacity < 0) {
46  Warning("THashTable", "capacity (%d) < 0", capacity);
48  } else if (capacity == 0)
50 
52  fCont = new TList* [fSize];
53  memset(fCont, 0, fSize*sizeof(TList*));
54 
55  fEntries = 0;
56  fUsedSlots = 0;
57  if (rehashlevel < 2) rehashlevel = 0;
58  fRehashLevel = rehashlevel;
59 }
60 
61 ////////////////////////////////////////////////////////////////////////////////
62 /// Delete a hashtable. Objects are not deleted unless the THashTable is the
63 /// owner (set via SetOwner()).
64 
66 {
67  if (fCont) Clear();
68  delete [] fCont;
69  fCont = 0;
70  fSize = 0;
71 }
72 
73 ////////////////////////////////////////////////////////////////////////////////
74 /// Add object to the hash table. Its position in the table will be
75 /// determined by the value returned by its Hash() function.
76 
78 {
79  if (IsArgNull("Add", obj)) return;
80 
81  Int_t slot = GetCheckedHashValue(obj);
82 
84  if (!fCont[slot]) {
85  fCont[slot] = new TList;
86  fUsedSlots++;
87  }
88  fCont[slot]->Add(obj);
89  fEntries++;
90 
93 }
94 
95 ////////////////////////////////////////////////////////////////////////////////
96 /// Add object to the hash table. Its position in the table will be
97 /// determined by the value returned by its Hash() function.
98 /// If and only if 'before' is in the same bucket as obj, obj is added
99 /// in front of 'before' within the bucket's list.
100 
101 void THashTable::AddBefore(const TObject *before, TObject *obj)
102 {
103  if (IsArgNull("Add", obj)) return;
104 
105  Int_t slot = GetCheckedHashValue(obj);
106 
108  if (!fCont[slot]) {
109  fCont[slot] = new TList;
110  fUsedSlots++;
111  }
112  if (before && GetHashValue(before) == slot) {
113  fCont[slot]->AddBefore(before,obj);
114  } else {
115  fCont[slot]->Add(obj);
116  }
117  fEntries++;
118 
120  Rehash(fEntries);
121 }
122 
123 ////////////////////////////////////////////////////////////////////////////////
124 /// Add all objects from collection col to this collection.
125 /// Implemented for more efficient rehashing.
126 
128 {
130 
131  // Hashing after AddAll can be much more expensive than
132  // hashing before, as we need to add more elements.
133  // We assume an ideal hash, i.e. fUsedSlots==fSize.
134  Int_t sumEntries=fEntries+col->GetEntries();
135  Bool_t rehashBefore=fRehashLevel && (sumEntries > fSize*fRehashLevel);
136  if (rehashBefore)
137  Rehash(sumEntries);
138 
139  // prevent Add from Rehashing
140  Int_t saveRehashLevel=fRehashLevel;
141  fRehashLevel=0;
142 
143  TCollection::AddAll(col);
144 
145  fRehashLevel=saveRehashLevel;
146  // If we didn't Rehash before, we might have to do it
147  // now, due to a non-perfect hash function.
148  if (!rehashBefore && fRehashLevel && AverageCollisions() > fRehashLevel)
149  Rehash(fEntries);
150 }
151 
152 ////////////////////////////////////////////////////////////////////////////////
153 /// Remove all objects from the table. Does not delete the objects
154 /// unless the THashTable is the owner (set via SetOwner()).
155 
157 {
159 
160  for (int i = 0; i < fSize; i++) {
161  // option "nodelete" is passed when Clear is called from
162  // THashList::Clear() or THashList::Delete() or Rehash().
163  if (fCont[i]) {
164  if (IsOwner())
165  fCont[i]->SetOwner();
166  fCont[i]->Clear(option);
167  }
168  SafeDelete(fCont[i]);
169  }
170 
171  fEntries = 0;
172  fUsedSlots = 0;
173 }
174 
175 ////////////////////////////////////////////////////////////////////////////////
176 /// Returns the number of collisions for an object with a certain name
177 /// (i.e. number of objects in same slot in the hash table, i.e. length
178 /// of linked list).
179 
181 {
182  Int_t slot = GetHashValue(name);
183 
185 
186  if (fCont[slot]) return fCont[slot]->GetSize();
187  return 0;
188 }
189 
190 ////////////////////////////////////////////////////////////////////////////////
191 /// Returns the number of collisions for an object (i.e. number of objects
192 /// in same slot in the hash table, i.e. length of linked list).
193 
195 {
196  if (IsArgNull("Collisions", obj)) return 0;
197 
198  Int_t slot = GetHashValue(obj);
199 
201 
202  if (fCont[slot]) return fCont[slot]->GetSize();
203  return 0;
204 }
205 
206 ////////////////////////////////////////////////////////////////////////////////
207 /// Remove all objects from the table AND delete all heap based objects.
208 
210 {
212 
213  for (int i = 0; i < fSize; i++)
214  if (fCont[i]) {
215  fCont[i]->Delete();
216  SafeDelete(fCont[i]);
217  }
218 
219  fEntries = 0;
220  fUsedSlots = 0;
221 }
222 
223 ////////////////////////////////////////////////////////////////////////////////
224 /// Find object using its name. Uses the hash value returned by the
225 /// TString::Hash() after converting name to a TString.
226 
228 {
229  Int_t slot = GetHashValue(name);
230 
232 
233  if (fCont[slot]) return fCont[slot]->FindObject(name);
234  return 0;
235 }
236 
237 ////////////////////////////////////////////////////////////////////////////////
238 /// Find object using its hash value (returned by its Hash() member).
239 
241 {
242  if (IsArgNull("FindObject", obj)) return 0;
243 
244  Int_t slot = GetHashValue(obj);
245  if (fCont[slot]) return fCont[slot]->FindObject(obj);
246  return 0;
247 }
248 
249 ////////////////////////////////////////////////////////////////////////////////
250 /// Return the TList corresponding to object's name based hash value.
251 /// One can iterate this list "manually" to find, e.g. objects with
252 /// the same name.
253 
254 const TList *THashTable::GetListForObject(const char *name) const
255 {
256  Int_t slot = GetHashValue(name);
257 
259 
260  return fCont[slot];
261 }
262 
263 ////////////////////////////////////////////////////////////////////////////////
264 /// Return the TList corresponding to object's hash value.
265 /// One can iterate this list "manually" to find, e.g. identical
266 /// objects.
267 
269 {
270  if (IsArgNull("GetListForObject", obj)) return 0;
271 
272  Int_t slot = GetHashValue(obj);
273 
275 
276  return fCont[slot];
277 }
278 
279 ////////////////////////////////////////////////////////////////////////////////
280 /// Return address of pointer to obj
281 
283 {
284  if (IsArgNull("GetObjectRef", obj)) return 0;
285 
286  Int_t slot = GetHashValue(obj);
287 
289 
290  if (fCont[slot]) return fCont[slot]->GetObjectRef(obj);
291  return 0;
292 }
293 
294 ////////////////////////////////////////////////////////////////////////////////
295 /// Returns a hash table iterator.
296 
298 {
299  return new THashTableIter(this, dir);
300 }
301 
302 ////////////////////////////////////////////////////////////////////////////
303 /// Print the collection header and its elements.
304 ///
305 /// If recurse is non-zero, descend into printing of
306 /// collection-entries with recurse - 1.
307 /// This means, if recurse is negative, the recursion is infinite.
308 ///
309 /// If option contains "details", Print will show the content of
310 /// each of the hash-slots.
311 ///
312 /// Option is passed recursively.
313 
314 void THashTable::Print(Option_t *option, Int_t recurse) const
315 {
316  if (strstr(option,"details")==nullptr) {
317  TCollection::Print(option,recurse);
318  return;
319  }
320 
321  PrintCollectionHeader(option);
322 
323  if (recurse != 0)
324  {
326  for (Int_t cursor = 0; cursor < Capacity();
327  cursor++) {
328  printf("Slot #%d:\n",cursor);
329  if (fCont[cursor])
330  fCont[cursor]->Print();
331  else {
333  printf("empty\n");
334  }
335 
336  }
338  }
339 }
340 
341 ////////////////////////////////////////////////////////////////////////////////
342 /// Rehash the hashtable. If the collision rate becomes too high (i.e.
343 /// the average size of the linked lists become too long) then lookup
344 /// efficiency decreases since relatively long lists have to be searched
345 /// every time. To improve performance rehash the hashtable. This resizes
346 /// the table to newCapacity slots and refills the table. Use
347 /// AverageCollisions() to check if you need to rehash. Set checkObjValidity
348 /// to kFALSE if you know that all objects in the table are still valid
349 /// (i.e. have not been deleted from the system in the meanwhile).
350 
351 void THashTable::Rehash(Int_t newCapacity, Bool_t checkObjValidity)
352 {
353  THashTable *ht = new THashTable(newCapacity);
354 
356 
357  TIter next(this);
358  TObject *obj;
359 
360  auto initialSize = GetEntries();
361 
362  if (checkObjValidity && TObject::GetObjectStat() && gObjectTable) {
363  while ((obj = next()))
364  if (gObjectTable->PtrIsValid(obj)) ht->Add(obj);
365  } else {
366  while ((obj = next()))
367  ht->Add(obj);
368  }
369 
370  if (initialSize != GetEntries()) {
371  // Somehow in the process of copy the pointer from one hash to
372  // other we ended up inducing the addition of more element to
373  // the table. Most likely those elements have not been copied ....
374  // i.e. Adding *during* the Rehashing is illegal and fatal.
375 
376  Fatal("Rehash",
377  "During the rehash of %p one or more element was added or removed. The initalize size was %d and now it is %d",
378  this, initialSize, GetEntries());
379 
380  }
381 
382  Clear("nodelete");
383  delete [] fCont;
384  fCont = ht->fCont;
385  ht->fCont = 0;
386 
387  fSize = ht->fSize; // idem
388  fEntries = ht->fEntries;
389  fUsedSlots = ht->fUsedSlots;
390 
391  // this should not happen, but it will prevent an endless loop
392  // in case of a very bad hash function
394  fRehashLevel = (int)AverageCollisions() + 1;
395 
396  delete ht;
397 }
398 
399 ////////////////////////////////////////////////////////////////////////////////
400 /// Remove object from the hashtable.
401 
403 {
404  Int_t slot = GetHashValue(obj);
405 
407 
408  if (fCont[slot]) {
410 
411  TObject *ob = fCont[slot]->Remove(obj);
412  if (ob) {
413  fEntries--;
414  if (fCont[slot]->GetSize() == 0) {
415  SafeDelete(fCont[slot]);
416  fUsedSlots--;
417  }
418  return ob;
419  }
420  }
421  return 0;
422 }
423 
424 ////////////////////////////////////////////////////////////////////////////////
425 /// Remove object from the hashtable without using the hash value.
426 
428 {
429 
431 
432  for (int i = 0; i < fSize; i++) {
433  if (fCont[i]) {
434  TObject *ob = fCont[i]->Remove(obj);
435  if (ob) {
436  fEntries--;
437  if (fCont[i]->GetSize() == 0) {
438  SafeDelete(fCont[i]);
439  fUsedSlots--;
440  }
441  return ob;
442  }
443  }
444  }
445  return 0;
446 }
447 
448 /** \class THashTableIter
449 Iterator of hash table.
450 */
451 
453 
454 ////////////////////////////////////////////////////////////////////////////////
455 /// Create a hashtable iterator. By default the iteration direction
456 /// is kIterForward. To go backward use kIterBackward.
457 
459 {
460  fTable = ht;
461  fDirection = dir;
462  fListCursor = 0;
463  Reset();
464 }
465 
466 ////////////////////////////////////////////////////////////////////////////////
467 /// Copy ctor.
468 
470 {
471  fTable = iter.fTable;
472  fDirection = iter.fDirection;
473  fCursor = iter.fCursor;
474  fListCursor = 0;
475  if (iter.fListCursor) {
477  if (fListCursor)
478  fListCursor->operator=(*iter.fListCursor);
479  }
480 }
481 
482 ////////////////////////////////////////////////////////////////////////////////
483 /// Overridden assignment operator.
484 
486 {
487  if (this != &rhs && rhs.IsA() == THashTableIter::Class()) {
488  const THashTableIter &rhs1 = (const THashTableIter &)rhs;
489  fTable = rhs1.fTable;
490  fDirection = rhs1.fDirection;
491  fCursor = rhs1.fCursor;
492  if (rhs1.fListCursor) {
493  // R__COLLECTION_READ_LOCKGUARD(ROOT::gCoreMutex);
494 
496  if (fListCursor)
497  fListCursor->operator=(*rhs1.fListCursor);
498  }
499  }
500  return *this;
501 }
502 
503 ////////////////////////////////////////////////////////////////////////////////
504 /// Overloaded assignment operator.
505 
507 {
508  if (this != &rhs) {
509  fTable = rhs.fTable;
510  fDirection = rhs.fDirection;
511  fCursor = rhs.fCursor;
512  if (rhs.fListCursor) {
513  // R__COLLECTION_READ_LOCKGUARD(ROOT::gCoreMutex);
514 
516  if (fListCursor)
517  fListCursor->operator=(*rhs.fListCursor);
518  }
519  }
520  return *this;
521 }
522 
523 ////////////////////////////////////////////////////////////////////////////////
524 /// Delete hashtable iterator.
525 
527 {
528  delete fListCursor;
529 }
530 
531 ////////////////////////////////////////////////////////////////////////////////
532 /// Return next object in hashtable. Returns 0 when no more objects in table.
533 
535 {
536  // R__COLLECTION_READ_LOCKGUARD(ROOT::gCoreMutex);
537 
538  while (kTRUE) {
539  if (!fListCursor) {
540  int slot = NextSlot();
541  if (slot == -1) return 0;
543  }
544 
545  TObject *obj = fListCursor->Next();
546  if (obj) return obj;
547 
549  }
550 }
551 
552 ////////////////////////////////////////////////////////////////////////////////
553 /// Returns index of next slot in table containing list to be iterated.
554 
556 {
557  // R__COLLECTION_READ_LOCKGUARD(ROOT::gCoreMutex);
558 
559  if (fDirection == kIterForward) {
560  for ( ; fCursor < fTable->Capacity() && fTable->fCont[fCursor] == 0;
561  fCursor++) { }
562 
563  if (fCursor < fTable->Capacity())
564  return fCursor++;
565 
566  } else {
567  for ( ; fCursor >= 0 && fTable->fCont[fCursor] == 0;
568  fCursor--) { }
569 
570  if (fCursor >= 0)
571  return fCursor--;
572  }
573  return -1;
574 }
575 
576 ////////////////////////////////////////////////////////////////////////////////
577 /// Reset the hashtable iterator. Either to beginning or end, depending on
578 /// the initial iteration direction.
579 
581 {
582  if (fDirection == kIterForward)
583  fCursor = 0;
584  else
585  fCursor = fTable->Capacity() - 1;
587 }
588 
589 ////////////////////////////////////////////////////////////////////////////////
590 /// This operator compares two TIterator objects.
591 
593 {
594  if (aIter.IsA() == THashTableIter::Class()) {
595  const THashTableIter &iter(dynamic_cast<const THashTableIter &>(aIter));
596  return (fListCursor != iter.fListCursor);
597  }
598  return false; // for base class we don't implement a comparison
599 }
600 
601 ////////////////////////////////////////////////////////////////////////////////
602 /// This operator compares two THashTableIter objects.
603 
605 {
606  return (fListCursor != aIter.fListCursor);
607 }
608 
609 ////////////////////////////////////////////////////////////////////////////////
610 /// Return pointer to current object or nullptr.
611 
613 {
614  return (fListCursor ? fListCursor->operator*() : nullptr);
615 }
static Int_t DecreaseDirLevel()
Decrease the indentation level for ls().
Definition: TROOT.cxx:2683
virtual void Delete(Option_t *option="")
Remove all objects from the list AND delete all heap based objects.
Definition: TList.cxx:467
virtual void AddAll(const TCollection *col)
Add all objects from collection col to this collection.
Definition: THashTable.cxx:127
void AddBefore(const TObject *before, TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:101
void Reset()
Reset the hashtable iterator.
Definition: THashTable.cxx:580
TList ** fCont
Definition: THashTable.h:40
TObject ** GetObjectRef(const TObject *obj) const
Return address of pointer to obj.
Definition: THashTable.cxx:282
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:177
virtual void AddAll(const TCollection *col)
Add all objects from collection col to this collection.
void Rehash(Int_t newCapacity, Bool_t checkObjValidity=kTRUE)
Rehash the hashtable.
Definition: THashTable.cxx:351
Float_t AverageCollisions() const
Definition: THashTable.h:82
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:254
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:427
TObject * Next()
Return next object in the list. Returns 0 when no more objects in list.
Definition: TList.cxx:1109
TListIter * fListCursor
Definition: THashTable.h:116
const THashTable * fTable
Definition: THashTable.h:114
Iterator abstract base class.
Definition: TIterator.h:30
Iterator of linked list.
Definition: TList.h:197
virtual TObject * FindObject(const char *name) const
Delete a TObjLink object.
Definition: TList.cxx:574
THashTable(const THashTable &)
friend class THashTableIter
Definition: THashTable.h:37
#define SafeDelete(p)
Definition: RConfig.h:509
Iterator of hash table.
Definition: THashTable.h:111
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:156
#define R__COLLECTION_READ_LOCKGUARD(mutex)
Definition: TCollection.h:433
R__EXTERN TVirtualRWMutex * gCoreMutex
const Bool_t kIterForward
Definition: TCollection.h:40
Bool_t IsOwner() const
Definition: TCollection.h:186
Int_t NextSlot()
Returns index of next slot in table containing list to be iterated.
Definition: THashTable.cxx:555
~THashTableIter()
Delete hashtable iterator.
Definition: THashTable.cxx:526
TObject * operator*() const
Return pointer to current object or nullptr.
Definition: THashTable.cxx:612
Bool_t fDirection
Definition: THashTable.h:117
A doubly linked list.
Definition: TList.h:44
Int_t fEntries
Definition: THashTable.h:41
const TCollection * GetCollection() const
Definition: TList.h:221
virtual TIterator * MakeIterator(Bool_t dir=kIterForward) const =0
virtual TObject * Remove(TObject *obj)
Remove object from the list.
Definition: TList.cxx:818
Collection abstract base class.
Definition: TCollection.h:63
virtual ~THashTable()
Delete a hashtable.
Definition: THashTable.cxx:65
Bool_t PtrIsValid(TObject *obj)
Definition: TObjectTable.h:78
static void IndentLevel()
Functions used by ls() to indent an object hierarchy.
Definition: TROOT.cxx:2746
void Reset(Detail::TBranchProxy *x)
static Bool_t GetObjectStat()
Get status of object stat flag.
Definition: TObject.cxx:954
virtual void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the list.
Definition: TList.cxx:193
TIterator * MakeIterator(Bool_t dir=kIterForward) const
Returns a hash table iterator.
Definition: THashTable.cxx:297
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:180
void Print(Option_t *option, Int_t recurse) const
Print the collection header and its elements.
Definition: THashTable.cxx:314
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
Definition: THashTable.cxx:485
TObject * FindObject(const char *name) const
Find object using its name.
Definition: THashTable.cxx:227
#define ClassImp(name)
Definition: Rtypes.h:359
Int_t GetSize() const
Definition: THashTable.h:70
void Add(TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:77
virtual void Clear(Option_t *option="")
Remove all objects from the list.
Definition: TList.cxx:399
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:209
static Int_t IncreaseDirLevel()
Increase the indentation level for ls().
Definition: TROOT.cxx:2738
Int_t GetCheckedHashValue(TObject *obj) const
Definition: THashTable.h:90
virtual void PrintCollectionHeader(Option_t *option) const
Print the collection header.
Int_t fRehashLevel
Definition: THashTable.h:43
virtual void Add(TObject *obj)
Definition: TList.h:87
Short_t Max(Short_t a, Short_t b)
Definition: TMathBase.h:200
Int_t Capacity() const
Definition: TCollection.h:165
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
Definition: THashTable.cxx:592
TObject * Next()
Return next object in hashtable. Returns 0 when no more objects in table.
Definition: THashTable.cxx:534
#define R__COLLECTION_WRITE_LOCKGUARD(mutex)
Definition: TCollection.h:436
virtual void Fatal(const char *method, const char *msgfmt,...) const
Issue fatal error message.
Definition: TObject.cxx:908
virtual void Print(Option_t *option="") const
Default print for collections, calls Print(option, 1).
virtual Int_t GetSize() const
Definition: TCollection.h:180
const Bool_t kTRUE
Definition: RtypesCore.h:87
Int_t GetHashValue(const TObject *obj) const
Definition: THashTable.h:96
virtual TObject ** GetObjectRef(const TObject *obj) const
Return address of pointer to obj.
Definition: TList.cxx:667
char name[80]
Definition: TGX11.cxx:109
virtual void Warning(const char *method, const char *msgfmt,...) const
Issue warning message.
Definition: TObject.cxx:866
TObject * Remove(TObject *obj)
Remove object from the hashtable.
Definition: THashTable.cxx:402