Logo ROOT  
Reference Guide
 
Loading...
Searching...
No Matches
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 = nullptr;
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 nullptr;
246}
247
248////////////////////////////////////////////////////////////////////////////////
249/// Find object using its hash value (returned by its Hash() member).
250
252{
253 if (IsArgNull("FindObject", obj)) return nullptr;
254
255 Int_t slot = GetHashValue(obj);
256
258
259 if (fCont[slot]) return fCont[slot]->FindObject(obj);
260 return nullptr;
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 nullptr;
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 nullptr;
299
300 Int_t slot = GetHashValue(obj);
301
303
304 if (fCont[slot]) return fCont[slot]->GetObjectRef(obj);
305 return nullptr;
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
329{
330 if (strstr(option,"details")==nullptr) {
331 TCollection::Print(option,recurse);
332 return;
333 }
334
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 = nullptr;
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
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 nullptr;
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 nullptr;
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 = nullptr;
478 Reset();
479}
480
481////////////////////////////////////////////////////////////////////////////////
482/// Copy ctor.
483
485{
486 fTable = iter.fTable;
487 fDirection = iter.fDirection;
488 fCursor = iter.fCursor;
489 fListCursor = nullptr;
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 nullptr;
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];
576 fCursor++) { }
577
578 if (fCursor < fTable->Capacity())
579 return fCursor++;
580
581 } else {
582 for ( ; fCursor >= 0 && !fTable->fCont[fCursor];
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}
#define SafeDelete(p)
Definition RConfig.hxx:540
int Int_t
Definition RtypesCore.h:45
constexpr Bool_t kTRUE
Definition RtypesCore.h:100
const char Option_t
Definition RtypesCore.h:66
#define ClassImp(name)
Definition Rtypes.h:377
#define R__COLLECTION_READ_LOCKGUARD(mutex)
const Bool_t kIterForward
Definition TCollection.h:42
#define R__COLLECTION_WRITE_LOCKGUARD(mutex)
Option_t Option_t option
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t cursor
char name[80]
Definition TGX11.cxx:110
R__EXTERN TObjectTable * gObjectTable
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
Int_t Capacity() const
virtual void AddAll(const TCollection *col)
Add all objects from collection col to this collection.
virtual Int_t GetEntries() const
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
void Print(Option_t *option="") const override
Default print for collections, calls Print(option, 1).
virtual Int_t GetSize() const
Return the capacity of the collection, i.e.
Iterator of hash table.
Definition THashTable.h:114
Bool_t operator!=(const TIterator &aIter) const override
This operator compares two TIterator objects.
const THashTable * fTable
Definition THashTable.h:117
~THashTableIter()
Delete hashtable iterator.
void Reset() override
Reset the hashtable iterator.
TObject * operator*() const override
Return pointer to current object or nullptr.
Bool_t fDirection
Definition THashTable.h:120
TObject * Next() override
Return next object in hashtable. Returns 0 when no more objects in table.
TIterator & operator=(const TIterator &rhs) override
Overridden assignment operator.
Int_t NextSlot()
Returns index of next slot in table containing list to be iterated.
static TClass * Class()
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
void Add(TObject *obj) override
Add object to the hash table.
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.
Int_t fUsedSlots
Definition THashTable.h:42
void AddImpl(Int_t slot, TObject *object)
Helper function doing the actual add to the table give a slot and object.
TList ** fCont
Definition THashTable.h:40
TObject * Remove(TObject *obj) override
Remove object from the hashtable.
void Rehash(Int_t newCapacity, Bool_t checkObjValidity=kTRUE)
Rehash the hashtable.
TObject * RemoveSlow(TObject *obj)
Remove object from the hashtable without using the hash value.
TIterator * MakeIterator(Bool_t dir=kIterForward) const override
Returns a hash table iterator.
TObject ** GetObjectRef(const TObject *obj) const override
Return address of pointer to obj.
THashTable(const THashTable &)=delete
void AddBefore(const TObject *before, TObject *obj)
Add object to the hash table.
void AddAll(const TCollection *col) override
Add all objects from collection col to this collection.
TObject * FindObject(const char *name) const override
Find object using its name.
Int_t fEntries
Definition THashTable.h:41
Int_t GetSize() const override
Return the capacity of the collection, i.e.
Definition THashTable.h:73
void Clear(Option_t *option="") override
Remove all objects from the table.
Int_t Collisions(const char *name) const
Returns the number of collisions for an object with a certain name (i.e.
void Print(Option_t *option, Int_t recurse) const override
Print the collection header and its elements.
Int_t fRehashLevel
Definition THashTable.h:43
void Delete(Option_t *option="") override
Remove all objects from the table AND delete all heap based objects.
virtual ~THashTable()
Delete a hashtable.
Int_t GetCheckedHashValue(TObject *obj) const
Definition THashTable.h:93
Int_t GetHashValue(const TObject *obj) const
Definition THashTable.h:99
Iterator abstract base class.
Definition TIterator.h:30
virtual TClass * IsA() const
Definition TIterator.h:48
Iterator of linked list.
Definition TList.h:191
const TCollection * GetCollection() const override
Definition TList.h:219
TObject * Next() override
Return next object in the list. Returns 0 when no more objects in list.
Definition TList.cxx:1111
A doubly linked list.
Definition TList.h:38
void Clear(Option_t *option="") override
Remove all objects from the list.
Definition TList.cxx:402
TObject ** GetObjectRef(const TObject *obj) const override
Return address of pointer to obj.
Definition TList.cxx:671
TObject * FindObject(const char *name) const override
Find an object in this list using its name.
Definition TList.cxx:578
void Add(TObject *obj) override
Definition TList.h:81
TObject * Remove(TObject *obj) override
Remove object from the list.
Definition TList.cxx:822
void AddBefore(const TObject *before, TObject *obj) override
Insert object before object before in the list.
Definition TList.cxx:196
void Delete(Option_t *option="") override
Remove all objects from the list AND delete all heap based objects.
Definition TList.cxx:470
Bool_t PtrIsValid(TObject *obj)
Mother of all ROOT objects.
Definition TObject.h:41
virtual void Warning(const char *method, const char *msgfmt,...) const
Issue warning message.
Definition TObject.cxx:956
static Bool_t GetObjectStat()
Get status of object stat flag.
Definition TObject.cxx:1044
virtual void Fatal(const char *method, const char *msgfmt,...) const
Issue fatal error message.
Definition TObject.cxx:998
static Int_t IncreaseDirLevel()
Increase the indentation level for ls().
Definition TROOT.cxx:2826
static void IndentLevel()
Functions used by ls() to indent an object hierarchy.
Definition TROOT.cxx:2834
static Int_t DecreaseDirLevel()
Decrease the indentation level for ls().
Definition TROOT.cxx:2713
R__EXTERN TVirtualRWMutex * gCoreMutex
Short_t Max(Short_t a, Short_t b)
Returns the largest of a and b.
Definition TMathBase.h:250
Long_t NextPrime(Long_t x)