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