Logo ROOT   6.10/09
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 GetHashValue(const TObject *obj) const;
46  Int_t GetHashValue(TString &s) const { return s.Hash() % fSize; }
47  Int_t GetHashValue(const char *str) const { return ::Hash(str) % fSize; }
48 
49  THashTable(const THashTable&); // not implemented
50  THashTable& operator=(const THashTable&); // not implemented
51 
52 public:
54  virtual ~THashTable();
55  void Add(TObject *obj);
56  void AddBefore(const TObject *before, TObject *obj);
57  virtual void AddAll(const TCollection *col);
58  Float_t AverageCollisions() const;
59  void Clear(Option_t *option="");
60  Int_t Collisions(const char *name) const;
61  Int_t Collisions(TObject *obj) const;
62  void Delete(Option_t *option="");
63  TObject *FindObject(const char *name) const;
64  TObject *FindObject(const TObject *obj) const;
65  const TList *GetListForObject(const char *name) const;
66  const TList *GetListForObject(const TObject *obj) const;
67  TObject **GetObjectRef(const TObject *obj) const;
68  Int_t GetRehashLevel() const { return fRehashLevel; }
69  Int_t GetSize() const { return fEntries; }
71  void Rehash(Int_t newCapacity, Bool_t checkObjValidity = kTRUE);
72  TObject *Remove(TObject *obj);
73  TObject *RemoveSlow(TObject *obj);
74  void SetRehashLevel(Int_t rehash) { fRehashLevel = rehash; }
75 
76  ClassDef(THashTable,0) //A hash table
77 };
78 
80 {
81  if (fUsedSlots)
82  return ((Float_t)fEntries)/fUsedSlots;
83  else
84  return 0.0;
85 }
86 
87 inline Int_t THashTable::GetHashValue(const TObject *obj) const
88 {
89  Int_t i = Int_t(obj->Hash() % fSize); // need intermediary i for Linux g++
90  return i;
91 }
92 
93 
94 //////////////////////////////////////////////////////////////////////////
95 // //
96 // THashTableIter //
97 // //
98 // Iterator of hash table. //
99 // //
100 //////////////////////////////////////////////////////////////////////////
101 
102 class THashTableIter : public TIterator {
103 
104 private:
105  const THashTable *fTable; //hash table being iterated
106  Int_t fCursor; //current position in table
107  TListIter *fListCursor; //current position in collision list
108  Bool_t fDirection; //iteration direction
109 
110  THashTableIter() : fTable(0), fCursor(0), fListCursor(0), fDirection(kIterForward) { }
111  Int_t NextSlot();
112 
113 public:
114  THashTableIter(const THashTable *ht, Bool_t dir = kIterForward);
115  THashTableIter(const THashTableIter &iter);
116  ~THashTableIter();
117  TIterator &operator=(const TIterator &rhs);
119 
120  const TCollection *GetCollection() const { return fTable; }
121  TObject *Next();
122  void Reset();
123  Bool_t operator!=(const TIterator &aIter) const;
124  Bool_t operator!=(const THashTableIter &aIter) const;
125  TObject *operator*() const;
126 
127  ClassDef(THashTableIter,0) //Hash table iterator
128 };
129 
130 #endif
virtual ULong_t Hash() const
Return hash value for this object.
Definition: TObject.cxx:426
UInt_t Hash(const TString &s)
Definition: TString.h:464
virtual void AddAll(const TCollection *col)
Add all objects from collection col to this collection.
Definition: THashTable.cxx:122
void AddBefore(const TObject *before, TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:98
TList ** fCont
Definition: THashTable.h:40
float Float_t
Definition: RtypesCore.h:53
TObject ** GetObjectRef(const TObject *obj) const
Return address of pointer to obj.
Definition: THashTable.cxx:253
const char Option_t
Definition: RtypesCore.h:62
Int_t GetRehashLevel() const
Definition: THashTable.h:68
void Rehash(Int_t newCapacity, Bool_t checkObjValidity=kTRUE)
Rehash the hashtable.
Definition: THashTable.cxx:280
Float_t AverageCollisions() const
Definition: THashTable.h:79
Int_t fUsedSlots
Definition: THashTable.h:42
const TList * GetListForObject(const char *name) const
Return the TList corresponding to object's name based hash value.
Definition: THashTable.cxx:234
Basic string class.
Definition: TString.h:129
int Int_t
Definition: RtypesCore.h:41
bool Bool_t
Definition: RtypesCore.h:59
TObject * RemoveSlow(TObject *obj)
Remove object from the hashtable without using the hash value.
Definition: THashTable.cxx:335
THashTable & operator=(const THashTable &)
TListIter * fListCursor
Definition: THashTable.h:107
const THashTable * fTable
Definition: THashTable.h:105
Iterator abstract base class.
Definition: TIterator.h:30
Iterator of linked list.
Definition: TList.h:183
UInt_t Hash(ECaseCompare cmp=kExact) const
Return hash value.
Definition: TString.cxx:616
THashTable(const THashTable &)
friend class THashTableIter
Definition: THashTable.h:37
Iterator of hash table.
Definition: THashTable.h:102
THashTable implements a hash table to store TObject's.
Definition: THashTable.h:35
#define ClassDef(name, id)
Definition: Rtypes.h:297
void Clear(Option_t *option="")
Remove all objects from the table.
Definition: THashTable.cxx:149
void SetRehashLevel(Int_t rehash)
Definition: THashTable.h:74
const Bool_t kIterForward
Definition: TCollection.h:37
Bool_t operator!=(const TDatime &d1, const TDatime &d2)
Definition: TDatime.h:104
Bool_t fDirection
Definition: THashTable.h:108
A doubly linked list.
Definition: TList.h:43
Int_t fEntries
Definition: THashTable.h:41
TTime operator*(const TTime &t1, const TTime &t2)
Definition: TTime.h:85
Collection abstract base class.
Definition: TCollection.h:42
virtual ~THashTable()
Delete a hashtable.
Definition: THashTable.cxx:64
Int_t fSize
Definition: TCollection.h:57
Int_t GetHashValue(const char *str) const
Definition: THashTable.h:47
void Reset(Detail::TBranchProxy *x)
TIterator * MakeIterator(Bool_t dir=kIterForward) const
Returns a hash table iterator.
Definition: THashTable.cxx:265
Int_t Collisions(const char *name) const
Returns the number of collisions for an object with a certain name (i.e.
Definition: THashTable.cxx:171
TObject * FindObject(const char *name) const
Find object using its name.
Definition: THashTable.cxx:210
Int_t GetSize() const
Definition: THashTable.h:69
Int_t GetHashValue(TString &s) const
Definition: THashTable.h:46
const TCollection * GetCollection() const
Definition: THashTable.h:120
void Add(TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:76
Mother of all ROOT objects.
Definition: TObject.h:37
void Delete(Option_t *option="")
Remove all objects from the table AND delete all heap based objects.
Definition: THashTable.cxx:194
Int_t fRehashLevel
Definition: THashTable.h:43
const Bool_t kTRUE
Definition: RtypesCore.h:91
Int_t GetHashValue(const TObject *obj) const
Definition: THashTable.h:87
TObject * Remove(TObject *obj)
Remove object from the hashtable.
Definition: THashTable.cxx:315