Logo ROOT  
Reference Guide
THashTable.h
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#ifndef ROOT_THashTable
13#define ROOT_THashTable
14
15
16//////////////////////////////////////////////////////////////////////////
17// //
18// THashTable //
19// //
20// THashTable implements a hash table to store TObject's. The hash //
21// value is calculated using the value returned by the TObject's //
22// Hash() function. Each class inheriting from TObject can override //
23// Hash() as it sees fit. //
24// //
25//////////////////////////////////////////////////////////////////////////
26
27#include "TCollection.h"
28#include "TString.h"
29
30class TList;
31class TListIter;
32class THashTableIter;
33
34
35class THashTable : public TCollection {
36
37friend class THashTableIter;
38
39private:
40 TList **fCont; //Hash table (table of lists)
41 Int_t fEntries; //Number of objects in table
42 Int_t fUsedSlots; //Number of used slots
43 Int_t fRehashLevel; //Average collision rate which triggers rehash
44
46 Int_t GetHashValue(const TObject *obj) const;
47 Int_t GetHashValue(TString &s) const { return s.Hash() % fSize; }
48 Int_t GetHashValue(const char *str) const { return ::Hash(str) % fSize; }
49
50 void AddImpl(Int_t slot, TObject *object);
51
52 THashTable(const THashTable&) = delete;
53 THashTable& operator=(const THashTable&) = delete;
54
55public:
57 virtual ~THashTable();
58 void Add(TObject *obj) override;
59 void AddBefore(const TObject *before, TObject *obj);
60 void AddAll(const TCollection *col) override;
62 void Clear(Option_t *option="") override;
63 Int_t Collisions(const char *name) const;
64 Int_t Collisions(TObject *obj) const;
65 void Delete(Option_t *option="") override;
66 Bool_t Empty() const { return fEntries == 0; }
67 TObject *FindObject(const char *name) const override;
68 TObject *FindObject(const TObject *obj) const override;
69 const TList *GetListForObject(const char *name) const;
70 const TList *GetListForObject(const TObject *obj) const;
71 TObject **GetObjectRef(const TObject *obj) const override;
72 Int_t GetRehashLevel() const { return fRehashLevel; }
73 Int_t GetSize() const override { return fEntries; }
74 TIterator *MakeIterator(Bool_t dir = kIterForward) const override;
76 void Print(Option_t *option, Int_t recurse) const override;
77 void Rehash(Int_t newCapacity, Bool_t checkObjValidity = kTRUE);
78 TObject *Remove(TObject *obj) override;
80 void SetRehashLevel(Int_t rehash) { fRehashLevel = rehash; }
81
82 ClassDefOverride(THashTable,0) //A hash table
83};
84
86{
87 if (fUsedSlots)
89 else
90 return 0.0;
91}
92
94{
95 Int_t i = Int_t(obj->CheckedHash() % fSize); // need intermediary i for Linux g++
96 return i;
97}
98
99inline Int_t THashTable::GetHashValue(const TObject *obj) const
100{
101 Int_t i = Int_t(obj->Hash() % fSize); // need intermediary i for Linux g++
102 return i;
103}
104
105
106//////////////////////////////////////////////////////////////////////////
107// //
108// THashTableIter //
109// //
110// Iterator of hash table. //
111// //
112//////////////////////////////////////////////////////////////////////////
113
114class THashTableIter : public TIterator {
115
116private:
117 const THashTable *fTable; //hash table being iterated
118 Int_t fCursor; //current position in table
119 TListIter *fListCursor; //current position in collision list
120 Bool_t fDirection; //iteration direction
121
123 Int_t NextSlot();
124
125public:
127 THashTableIter(const THashTableIter &iter);
129 TIterator &operator=(const TIterator &rhs) override;
131
132 const TCollection *GetCollection() const override { return fTable; }
133 TObject *Next() override;
134 void Reset() override;
135 Bool_t operator!=(const TIterator &aIter) const override;
136 Bool_t operator!=(const THashTableIter &aIter) const;
137 TObject *operator*() const override;
138
139 ClassDefOverride(THashTableIter,0) //Hash table iterator
140};
141
142#endif
bool Bool_t
Definition: RtypesCore.h:63
int Int_t
Definition: RtypesCore.h:45
float Float_t
Definition: RtypesCore.h:57
const Bool_t kTRUE
Definition: RtypesCore.h:100
const char Option_t
Definition: RtypesCore.h:66
#define ClassDefOverride(name, id)
Definition: Rtypes.h:339
const Bool_t kIterForward
Definition: TCollection.h:42
Option_t Option_t option
char name[80]
Definition: TGX11.cxx:110
UInt_t Hash(const TString &s)
Definition: TString.h:486
Collection abstract base class.
Definition: TCollection.h:65
@ kInitHashTableCapacity
Definition: TCollection.h:159
void Print(Option_t *option="") const override
Default print for collections, calls Print(option, 1).
Iterator of hash table.
Definition: THashTable.h:114
Bool_t operator!=(const TIterator &aIter) const override
This operator compares two TIterator objects.
Definition: THashTable.cxx:607
const THashTable * fTable
Definition: THashTable.h:117
~THashTableIter()
Delete hashtable iterator.
Definition: THashTable.cxx:541
void Reset() override
Reset the hashtable iterator.
Definition: THashTable.cxx:595
TObject * operator*() const override
Return pointer to current object or nullptr.
Definition: THashTable.cxx:627
const TCollection * GetCollection() const override
Definition: THashTable.h:132
Bool_t fDirection
Definition: THashTable.h:120
TObject * Next() override
Return next object in hashtable. Returns 0 when no more objects in table.
Definition: THashTable.cxx:549
TIterator & operator=(const TIterator &rhs) override
Overridden assignment operator.
Definition: THashTable.cxx:500
Int_t NextSlot()
Returns index of next slot in table containing list to be iterated.
Definition: THashTable.cxx:570
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
THashTable & operator=(const THashTable &)=delete
void Add(TObject *obj) override
Add object to the hash table.
Definition: THashTable.cxx:92
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
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
TObject * Remove(TObject *obj) override
Remove object from the hashtable.
Definition: THashTable.cxx:417
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
TIterator * MakeIterator(Bool_t dir=kIterForward) const override
Returns a hash table iterator.
Definition: THashTable.cxx:311
TObject ** GetObjectRef(const TObject *obj) const override
Return address of pointer to obj.
Definition: THashTable.cxx:296
THashTable(const THashTable &)=delete
void AddBefore(const TObject *before, TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:112
void AddAll(const TCollection *col) override
Add all objects from collection col to this collection.
Definition: THashTable.cxx:138
TObject * FindObject(const char *name) const override
Find object using its name.
Definition: THashTable.cxx:238
Int_t fEntries
Definition: THashTable.h:41
Int_t GetSize() const override
Return the capacity of the collection, i.e.
Definition: THashTable.h:73
Int_t GetRehashLevel() const
Definition: THashTable.h:72
Int_t GetHashValue(TString &s) const
Definition: THashTable.h:47
void Clear(Option_t *option="") override
Remove all objects from the table.
Definition: THashTable.cxx:167
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
void SetRehashLevel(Int_t rehash)
Definition: THashTable.h:80
Int_t GetHashValue(const char *str) const
Definition: THashTable.h:48
void Print(Option_t *option, Int_t recurse) const override
Print the collection header and its elements.
Definition: THashTable.cxx:328
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.
Definition: THashTable.cxx:220
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
Bool_t Empty() const
Definition: THashTable.h:66
Iterator abstract base class.
Definition: TIterator.h:30
Iterator of linked list.
Definition: TList.h:191
A doubly linked list.
Definition: TList.h:38
Mother of all ROOT objects.
Definition: TObject.h:37
ULong_t CheckedHash()
Check and record whether this class has a consistent Hash/RecursiveRemove setup (*) and then return t...
Definition: TObject.h:311
virtual ULong_t Hash() const
Return hash value for this object.
Definition: TObject.cxx:435
Basic string class.
Definition: TString.h:136
static constexpr double s