Logo ROOT   6.30.04
Reference Guide
 All Namespaces Files Pages
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:
56  THashTable(Int_t capacity = TCollection::kInitHashTableCapacity, Int_t rehash = 0);
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  TObject *FindObject(const char *name) const;
67  TObject *FindObject(const TObject *obj) const;
68  const TList *GetListForObject(const char *name) const;
69  const 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 Print(Option_t *option, Int_t recurse) const;
75  using TCollection::Print;
76  void Rehash(Int_t newCapacity, Bool_t checkObjValidity = kTRUE);
77  TObject *Remove(TObject *obj);
78  TObject *RemoveSlow(TObject *obj);
79  void SetRehashLevel(Int_t rehash) { fRehashLevel = rehash; }
80 
81  ClassDef(THashTable,0) //A hash table
82 };
83 
84 inline Float_t THashTable::AverageCollisions() const
85 {
86  if (fUsedSlots)
87  return ((Float_t)fEntries)/((Float_t)fUsedSlots);
88  else
89  return 0.0;
90 }
91 
92 inline Int_t THashTable::GetCheckedHashValue(TObject *obj) const
93 {
94  Int_t i = Int_t(obj->CheckedHash() % fSize); // need intermediary i for Linux g++
95  return i;
96 }
97 
98 inline Int_t THashTable::GetHashValue(const TObject *obj) const
99 {
100  Int_t i = Int_t(obj->Hash() % fSize); // need intermediary i for Linux g++
101  return i;
102 }
103 
104 
105 //////////////////////////////////////////////////////////////////////////
106 // //
107 // THashTableIter //
108 // //
109 // Iterator of hash table. //
110 // //
111 //////////////////////////////////////////////////////////////////////////
112 
113 class THashTableIter : public TIterator {
114 
115 private:
116  const THashTable *fTable; //hash table being iterated
117  Int_t fCursor; //current position in table
118  TListIter *fListCursor; //current position in collision list
119  Bool_t fDirection; //iteration direction
120 
121  THashTableIter() : fTable(0), fCursor(0), fListCursor(0), fDirection(kIterForward) { }
122  Int_t NextSlot();
123 
124 public:
125  THashTableIter(const THashTable *ht, Bool_t dir = kIterForward);
126  THashTableIter(const THashTableIter &iter);
127  ~THashTableIter();
128  TIterator &operator=(const TIterator &rhs);
129  THashTableIter &operator=(const THashTableIter &rhs);
130 
131  const TCollection *GetCollection() const { return fTable; }
132  TObject *Next();
133  void Reset();
134  Bool_t operator!=(const TIterator &aIter) const;
135  Bool_t operator!=(const THashTableIter &aIter) const;
136  TObject *operator*() const;
137 
138  ClassDef(THashTableIter,0) //Hash table iterator
139 };
140 
141 #endif