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 
30 class TList;
31 class TListIter;
32 class THashTableIter;
33 
34 
35 class THashTable : public TCollection {
36 
37 friend class THashTableIter;
38 
39 private:
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 
45  Int_t GetCheckedHashValue(TObject *obj) const;
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&); // not implemented
53  THashTable& operator=(const THashTable&); // not implemented
54 
55 public:
57  virtual ~THashTable();
58  void Add(TObject *obj);
59  void AddBefore(const TObject *before, TObject *obj);
60  virtual void AddAll(const TCollection *col);
61  Float_t AverageCollisions() const;
62  void Clear(Option_t *option="");
63  Int_t Collisions(const char *name) const;
64  Int_t Collisions(TObject *obj) const;
65  void Delete(Option_t *option="");
66  Bool_t Empty() const { return fEntries == 0; }
67  TObject *FindObject(const char *name) const;
68  TObject *FindObject(const TObject *obj) const;
69  const TList *GetListForObject(const char *name) const;
70  const TList *GetListForObject(const TObject *obj) const;
71  TObject **GetObjectRef(const TObject *obj) const;
72  Int_t GetRehashLevel() const { return fRehashLevel; }
73  Int_t GetSize() const { return fEntries; }
75  void Print(Option_t *option, Int_t recurse) const;
76  using TCollection::Print;
77  void Rehash(Int_t newCapacity, Bool_t checkObjValidity = kTRUE);
78  TObject *Remove(TObject *obj);
79  TObject *RemoveSlow(TObject *obj);
80  void SetRehashLevel(Int_t rehash) { fRehashLevel = rehash; }
81 
82  ClassDef(THashTable,0) //A hash table
83 };
84 
86 {
87  if (fUsedSlots)
88  return ((Float_t)fEntries)/((Float_t)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 
99 inline 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 
114 class THashTableIter : public TIterator {
115 
116 private:
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 
125 public:
126  THashTableIter(const THashTable *ht, Bool_t dir = kIterForward);
127  THashTableIter(const THashTableIter &iter);
128  ~THashTableIter();
129  TIterator &operator=(const TIterator &rhs);
131 
132  const TCollection *GetCollection() const { return fTable; }
133  TObject *Next();
134  void Reset();
135  Bool_t operator!=(const TIterator &aIter) const;
136  Bool_t operator!=(const THashTableIter &aIter) const;
137  TObject *operator*() const;
138 
139  ClassDef(THashTableIter,0) //Hash table iterator
140 };
141 
142 #endif
THashTable::SetRehashLevel
void SetRehashLevel(Int_t rehash)
Definition: THashTable.h:80
kTRUE
const Bool_t kTRUE
Definition: RtypesCore.h:91
TCollection::Print
virtual void Print(Option_t *option="") const
Default print for collections, calls Print(option, 1).
Definition: TCollection.cxx:476
THashTable::GetCheckedHashValue
Int_t GetCheckedHashValue(TObject *obj) const
Definition: THashTable.h:93
THashTable::GetSize
Int_t GetSize() const
Return the capacity of the collection, i.e.
Definition: THashTable.h:73
Option_t
const char Option_t
Definition: RtypesCore.h:66
THashTableIter::fCursor
Int_t fCursor
Definition: THashTable.h:118
Hash
UInt_t Hash(const TString &s)
Definition: TString.h:486
THashTable::GetHashValue
Int_t GetHashValue(const TObject *obj) const
Definition: THashTable.h:99
THashTable::Add
void Add(TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:92
THashTable::Collisions
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
THashTable::~THashTable
virtual ~THashTable()
Delete a hashtable.
Definition: THashTable.cxx:65
TCollection::kInitHashTableCapacity
@ kInitHashTableCapacity
Definition: TCollection.h:157
TCollection.h
THashTable::fRehashLevel
Int_t fRehashLevel
Definition: THashTable.h:43
THashTable::Clear
void Clear(Option_t *option="")
Remove all objects from the table.
Definition: THashTable.cxx:167
THashTableIter::Reset
void Reset()
Reset the hashtable iterator.
Definition: THashTable.cxx:595
THashTable::Empty
Bool_t Empty() const
Definition: THashTable.h:66
Float_t
float Float_t
Definition: RtypesCore.h:57
TGeant4Unit::s
static constexpr double s
Definition: TGeant4SystemOfUnits.h:162
Int_t
int Int_t
Definition: RtypesCore.h:45
THashTableIter::fDirection
Bool_t fDirection
Definition: THashTable.h:120
TObject::CheckedHash
ULong_t CheckedHash()
Check and record whether this class has a consistent Hash/RecursiveRemove setup (*) and then return t...
Definition: TObject.h:296
THashTable::fCont
TList ** fCont
Definition: THashTable.h:40
TObject::Hash
virtual ULong_t Hash() const
Return hash value for this object.
Definition: TObject.cxx:435
THashTable::MakeIterator
TIterator * MakeIterator(Bool_t dir=kIterForward) const
Returns a hash table iterator.
Definition: THashTable.cxx:311
TString
Basic string class.
Definition: TString.h:136
THashTable::GetRehashLevel
Int_t GetRehashLevel() const
Definition: THashTable.h:72
Bool_t
bool Bool_t
Definition: RtypesCore.h:63
THashTable::Delete
void Delete(Option_t *option="")
Remove all objects from the table AND delete all heap based objects.
Definition: THashTable.cxx:220
THashTableIter::fTable
const THashTable * fTable
Definition: THashTable.h:117
TString.h
bool
TIterator
Iterator abstract base class.
Definition: TIterator.h:30
TListIter
Iterator of linked list.
Definition: TList.h:200
THashTableIter::fListCursor
TListIter * fListCursor
Definition: THashTable.h:119
kIterForward
const Bool_t kIterForward
Definition: TCollection.h:40
THashTableIter::THashTableIter
THashTableIter()
Definition: THashTable.h:122
THashTable::AverageCollisions
Float_t AverageCollisions() const
Definition: THashTable.h:85
THashTable::RemoveSlow
TObject * RemoveSlow(TObject *obj)
Remove object from the hashtable without using the hash value.
Definition: THashTable.cxx:442
THashTable
THashTable implements a hash table to store TObject's.
Definition: THashTable.h:35
THashTableIter::~THashTableIter
~THashTableIter()
Delete hashtable iterator.
Definition: THashTable.cxx:541
THashTable::FindObject
TObject * FindObject(const char *name) const
Find object using its name.
Definition: THashTable.cxx:238
THashTable::AddBefore
void AddBefore(const TObject *before, TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:112
TCollection::fSize
Int_t fSize
Definition: TCollection.h:148
THashTable::GetObjectRef
TObject ** GetObjectRef(const TObject *obj) const
Return address of pointer to obj.
Definition: THashTable.cxx:296
THashTableIter::operator*
TObject * operator*() const
Return pointer to current object or nullptr.
Definition: THashTable.cxx:627
THashTableIter::NextSlot
Int_t NextSlot()
Returns index of next slot in table containing list to be iterated.
Definition: THashTable.cxx:570
THashTable::AddImpl
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
THashTable::Remove
TObject * Remove(TObject *obj)
Remove object from the hashtable.
Definition: THashTable.cxx:417
THashTable::Print
virtual void Print(Option_t *option="") const
Default print for collections, calls Print(option, 1).
Definition: TCollection.cxx:476
THashTable::Rehash
void Rehash(Int_t newCapacity, Bool_t checkObjValidity=kTRUE)
Rehash the hashtable.
Definition: THashTable.cxx:365
THashTable::THashTable
THashTable(const THashTable &)
THashTable::GetListForObject
const TList * GetListForObject(const char *name) const
Return the TList corresponding to object's name based hash value.
Definition: THashTable.cxx:268
THashTableIter::operator=
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
Definition: THashTable.cxx:500
TObject
Mother of all ROOT objects.
Definition: TObject.h:37
THashTableIter
Iterator of hash table.
Definition: THashTable.h:114
ClassDef
#define ClassDef(name, id)
Definition: Rtypes.h:325
name
char name[80]
Definition: TGX11.cxx:110
THashTable::fUsedSlots
Int_t fUsedSlots
Definition: THashTable.h:42
THashTableIter::GetCollection
const TCollection * GetCollection() const
Definition: THashTable.h:132
TCollection
Collection abstract base class.
Definition: TCollection.h:63
THashTable::operator=
THashTable & operator=(const THashTable &)
THashTableIter::Next
TObject * Next()
Return next object in hashtable. Returns 0 when no more objects in table.
Definition: THashTable.cxx:549
THashTable::GetHashValue
Int_t GetHashValue(const char *str) const
Definition: THashTable.h:48
THashTable::AddAll
virtual void AddAll(const TCollection *col)
Add all objects from collection col to this collection.
Definition: THashTable.cxx:138
THashTable::fEntries
Int_t fEntries
Definition: THashTable.h:41
THashTableIter::operator!=
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
Definition: THashTable.cxx:607
TList
A doubly linked list.
Definition: TList.h:44
int
THashTable::GetHashValue
Int_t GetHashValue(TString &s) const
Definition: THashTable.h:47