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
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
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;
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
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
113{
114 if (IsArgNull("Add", obj)) return;
115
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();
147 if (rehashBefore)
148 Rehash(sumEntries);
149
150 // prevent Add from Rehashing
152 fRehashLevel=0;
153
155
157 // If we didn't Rehash before, we might have to do it
158 // now, due to a non-perfect hash function.
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{
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{
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{
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) {
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
366{
368
370
371 TIter next(this);
372 TObject *obj;
373
374 auto initialSize = GetEntries();
375
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;
404 fUsedSlots = ht->fUsedSlots;
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) {
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
467
468////////////////////////////////////////////////////////////////////////////////
469/// Create a hashtable iterator. By default the iteration direction
470/// is kIterForward. To go backward use kIterBackward.
471
473{
474 fTable = ht;
475 fDirection = dir;
476 fListCursor = nullptr;
477 Reset();
478}
479
480////////////////////////////////////////////////////////////////////////////////
481/// Copy ctor.
482
484{
485 fTable = iter.fTable;
486 fDirection = iter.fDirection;
487 fCursor = iter.fCursor;
488 fListCursor = nullptr;
489 if (iter.fListCursor) {
490 fListCursor = (TListIter *)iter.fListCursor->GetCollection()->MakeIterator();
491 if (fListCursor)
492 fListCursor->operator=(*iter.fListCursor);
493 }
494}
495
496////////////////////////////////////////////////////////////////////////////////
497/// Overridden assignment operator.
498
500{
501 if (this != &rhs && rhs.IsA() == THashTableIter::Class()) {
502 const THashTableIter &rhs1 = (const THashTableIter &)rhs;
503 fTable = rhs1.fTable;
504 fDirection = rhs1.fDirection;
505 fCursor = rhs1.fCursor;
506 if (rhs1.fListCursor) {
507 // R__COLLECTION_READ_LOCKGUARD(ROOT::gCoreMutex);
508
509 fListCursor = (TListIter *)rhs1.fListCursor->GetCollection()->MakeIterator();
510 if (fListCursor)
511 fListCursor->operator=(*rhs1.fListCursor);
512 }
513 }
514 return *this;
515}
516
517////////////////////////////////////////////////////////////////////////////////
518/// Overloaded assignment operator.
519
521{
522 if (this != &rhs) {
523 fTable = rhs.fTable;
524 fDirection = rhs.fDirection;
525 fCursor = rhs.fCursor;
526 if (rhs.fListCursor) {
527 // R__COLLECTION_READ_LOCKGUARD(ROOT::gCoreMutex);
528
529 fListCursor = (TListIter *)rhs.fListCursor->GetCollection()->MakeIterator();
530 if (fListCursor)
531 fListCursor->operator=(*rhs.fListCursor);
532 }
533 }
534 return *this;
535}
536
537////////////////////////////////////////////////////////////////////////////////
538/// Delete hashtable iterator.
539
544
545////////////////////////////////////////////////////////////////////////////////
546/// Return next object in hashtable. Returns 0 when no more objects in table.
547
549{
550 // R__COLLECTION_READ_LOCKGUARD(ROOT::gCoreMutex);
551
552 while (kTRUE) {
553 if (!fListCursor) {
554 int slot = NextSlot();
555 if (slot == -1) return nullptr;
557 }
558
559 TObject *obj = fListCursor->Next();
560 if (obj) return obj;
561
563 }
564}
565
566////////////////////////////////////////////////////////////////////////////////
567/// Returns index of next slot in table containing list to be iterated.
568
570{
571 // R__COLLECTION_READ_LOCKGUARD(ROOT::gCoreMutex);
572
573 if (fDirection == kIterForward) {
574 for ( ; fCursor < fTable->Capacity() && !fTable->fCont[fCursor];
575 fCursor++) { }
576
577 if (fCursor < fTable->Capacity())
578 return fCursor++;
579
580 } else {
581 for ( ; fCursor >= 0 && !fTable->fCont[fCursor];
582 fCursor--) { }
583
584 if (fCursor >= 0)
585 return fCursor--;
586 }
587 return -1;
588}
589
590////////////////////////////////////////////////////////////////////////////////
591/// Reset the hashtable iterator. Either to beginning or end, depending on
592/// the initial iteration direction.
593
595{
597 fCursor = 0;
598 else
599 fCursor = fTable->Capacity() - 1;
601}
602
603////////////////////////////////////////////////////////////////////////////////
604/// This operator compares two TIterator objects.
605
607{
608 if (aIter.IsA() == THashTableIter::Class()) {
609 const THashTableIter &iter(dynamic_cast<const THashTableIter &>(aIter));
610 return (fListCursor != iter.fListCursor);
611 }
612 return false; // for base class we don't implement a comparison
613}
614
615////////////////////////////////////////////////////////////////////////////////
616/// This operator compares two THashTableIter objects.
617
619{
620 return (fListCursor != aIter.fListCursor);
621}
622
623////////////////////////////////////////////////////////////////////////////////
624/// Return pointer to current object or nullptr.
625
627{
628 return (fListCursor ? fListCursor->operator*() : nullptr);
629}
#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 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:1110
A doubly linked list.
Definition TList.h:38
void Clear(Option_t *option="") override
Remove all objects from the list.
Definition TList.cxx:399
TObject ** GetObjectRef(const TObject *obj) const override
Return address of pointer to obj.
Definition TList.cxx:668
TObject * FindObject(const char *name) const override
Find an object in this list using its name.
Definition TList.cxx:575
void Add(TObject *obj) override
Definition TList.h:81
TObject * Remove(TObject *obj) override
Remove object from the list.
Definition TList.cxx:819
void AddBefore(const TObject *before, TObject *obj) override
Insert object before object before in the list.
Definition TList.cxx:193
void Delete(Option_t *option="") override
Remove all objects from the list AND delete all heap based objects.
Definition TList.cxx:467
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:1057
static Bool_t GetObjectStat()
Get status of object stat flag.
Definition TObject.cxx:1154
virtual void Fatal(const char *method, const char *msgfmt,...) const
Issue fatal error message.
Definition TObject.cxx:1099
static Int_t IncreaseDirLevel()
Increase the indentation level for ls().
Definition TROOT.cxx:2890
static void IndentLevel()
Functions used by ls() to indent an object hierarchy.
Definition TROOT.cxx:2898
static Int_t DecreaseDirLevel()
Decrease the indentation level for ls().
Definition TROOT.cxx:2748
R__EXTERN TVirtualRWMutex * gCoreMutex
Long_t NextPrime(Long_t x)