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 #ifndef ROOT_TCollection
28 #include "TCollection.h"
29 #endif
30 #ifndef ROOT_TString
31 #include "TString.h"
32 #endif
33
34 class TList;
35 class TListIter;
36 class THashTableIter;
37
38
39 class THashTable : public TCollection {
40
41 friend class THashTableIter;
42
43 private:
44 TList **fCont; //Hash table (table of lists)
45 Int_t fEntries; //Number of objects in table
46 Int_t fUsedSlots; //Number of used slots
47 Int_t fRehashLevel; //Average collision rate which triggers rehash
48
49 Int_t GetHashValue(const TObject *obj) const;
50 Int_t GetHashValue(TString &s) const { return s.Hash() % fSize; }
51 Int_t GetHashValue(const char *str) const { return ::Hash(str) % fSize; }
52
53 THashTable(const THashTable&); // not implemented
54 THashTable& operator=(const THashTable&); // not implemented
55
56 public:
57 THashTable(Int_t capacity = TCollection::kInitHashTableCapacity, Int_t rehash = 0);
58 virtual ~THashTable();
59 void Add(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 TObject *FindObject(const char *name) const;
67 TObject *FindObject(const TObject *obj) const;
68 TList *GetListForObject(const char *name) const;
69 TList *GetListForObject(const TObject *obj) const;
70 TObject **GetObjectRef(const TObject *obj) const;
71 Int_t GetRehashLevel() const { return fRehashLevel; }
72 Int_t GetSize() const { return fEntries; }
73 TIterator *MakeIterator(Bool_t dir = kIterForward) const;
74 void Rehash(Int_t newCapacity, Bool_t checkObjValidity = kTRUE);
75 TObject *Remove(TObject *obj);
76 TObject *RemoveSlow(TObject *obj);
77 void SetRehashLevel(Int_t rehash) { fRehashLevel = rehash; }
78
79 ClassDef(THashTable,0) //A hash table
80 };
81
82 inline Float_t THashTable::AverageCollisions() const
83 {
84 if (fUsedSlots)
85 return ((Float_t)fEntries)/fUsedSlots;
86 else
87 return 0.0;
88 }
89
90 inline Int_t THashTable::GetHashValue(const TObject *obj) const
91 {
92 Int_t i = Int_t(obj->Hash() % fSize); // need intermediary i for Linux g++
93 return i;
94 }
95
96
97 //////////////////////////////////////////////////////////////////////////
98 // //
99 // THashTableIter //
100 // //
101 // Iterator of hash table. //
102 // //
103 //////////////////////////////////////////////////////////////////////////
104
105 class THashTableIter : public TIterator {
106
107 private:
108 const THashTable *fTable; //hash table being iterated
109 Int_t fCursor; //current position in table
110 TListIter *fListCursor; //current position in collision list
111 Bool_t fDirection; //iteration direction
112
113 THashTableIter() : fTable(0), fCursor(0), fListCursor(0), fDirection(kIterForward) { }
114 Int_t NextSlot();
115
116 public:
117 THashTableIter(const THashTable *ht, Bool_t dir = kIterForward);
118 THashTableIter(const THashTableIter &iter);
119 ~THashTableIter();
120 TIterator &operator=(const TIterator &rhs);
121 THashTableIter &operator=(const THashTableIter &rhs);
122
123 const TCollection *GetCollection() const { return fTable; }
124 TObject *Next();
125 void Reset();
126 Bool_t operator!=(const TIterator &aIter) const;
127 Bool_t operator!=(const THashTableIter &aIter) const;
128 TObject *operator*() const;
129
130 ClassDef(THashTableIter,0) //Hash table iterator
131 };
132
133 #endif
134