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