Logo ROOT   6.08/07
Reference Guide
THashList.cxx
Go to the documentation of this file.
1 // @(#)root/cont:$Id$
2 // Author: Fons Rademakers 10/08/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 /** \class THashList
13 \ingroup Containers
14 THashList implements a hybrid collection class consisting of a
15 hash table and a list to store TObject's. The hash table is used for
16 quick access and lookup of objects while the list allows the objects
17 to be ordered. The hash value is calculated using the value returned
18 by the TObject's Hash() function. Each class inheriting from TObject
19 can override Hash() as it sees fit.
20 */
21 
22 #include "THashList.h"
23 #include "THashTable.h"
24 
25 
27 
28 ////////////////////////////////////////////////////////////////////////////////
29 /// Create a THashList object. Capacity is the initial hashtable capacity
30 /// (i.e. number of slots), by default kInitHashTableCapacity = 17, and
31 /// rehash is the value at which a rehash will be triggered. I.e. when the
32 /// average size of the linked lists at a slot becomes longer than rehash
33 /// then the hashtable will be resized and refilled to reduce the collision
34 /// rate to about 1. The higher the collision rate, i.e. the longer the
35 /// linked lists, the longer lookup will take. If rehash=0 the table will
36 /// NOT automatically be rehashed. Use Rehash() for manual rehashing.
37 ///
38 /// WARNING !!!
39 /// If the name of an object in the HashList is modified, The hashlist
40 /// must be Rehashed
41 
42 THashList::THashList(Int_t capacity, Int_t rehash)
43 {
44  fTable = new THashTable(capacity, rehash);
45 }
46 
47 ////////////////////////////////////////////////////////////////////////////////
48 /// For backward compatibility only. Use other ctor.
49 
51 {
52  fTable = new THashTable(capacity, rehash);
53 }
54 
55 ////////////////////////////////////////////////////////////////////////////////
56 /// Delete a hashlist. Objects are not deleted unless the THashList is the
57 /// owner (set via SetOwner()).
58 
60 {
61  Clear();
63 }
64 
65 ////////////////////////////////////////////////////////////////////////////////
66 /// Add object at the beginning of the list.
67 
69 {
70  TList::AddFirst(obj);
71  fTable->Add(obj);
72 }
73 
74 ////////////////////////////////////////////////////////////////////////////////
75 /// Add object at the beginning of the list and also store option.
76 /// Storing an option is useful when one wants to change the behaviour
77 /// of an object a little without having to create a complete new
78 /// copy of the object. This feature is used, for example, by the Draw()
79 /// method. It allows the same object to be drawn in different ways.
80 
82 {
83  TList::AddFirst(obj, opt);
84  fTable->Add(obj);
85 }
86 
87 ////////////////////////////////////////////////////////////////////////////////
88 /// Add object at the end of the list.
89 
91 {
92  TList::AddLast(obj);
93  fTable->Add(obj);
94 }
95 
96 ////////////////////////////////////////////////////////////////////////////////
97 /// Add object at the end of the list and also store option.
98 /// Storing an option is useful when one wants to change the behaviour
99 /// of an object a little without having to create a complete new
100 /// copy of the object. This feature is used, for example, by the Draw()
101 /// method. It allows the same object to be drawn in different ways.
102 
104 {
105  TList::AddLast(obj, opt);
106  fTable->Add(obj);
107 }
108 
109 ////////////////////////////////////////////////////////////////////////////////
110 /// Insert object before object before in the list.
111 
112 void THashList::AddBefore(const TObject *before, TObject *obj)
113 {
114  TList::AddBefore(before, obj);
115  fTable->AddBefore(before, obj);
116 }
117 
118 ////////////////////////////////////////////////////////////////////////////////
119 /// Insert object before object before in the list.
120 
122 {
123  TList::AddBefore(before, obj);
124  fTable->AddBefore(before->GetObject(), obj);
125 }
126 
127 ////////////////////////////////////////////////////////////////////////////////
128 /// Insert object after object after in the list.
129 
130 void THashList::AddAfter(const TObject *after, TObject *obj)
131 {
132  TList::AddAfter(after, obj);
133  fTable->Add(obj);
134 }
135 
136 ////////////////////////////////////////////////////////////////////////////////
137 /// Insert object after object after in the list.
138 
140 {
141  TList::AddAfter(after, obj);
142  fTable->Add(obj);
143 }
144 
145 ////////////////////////////////////////////////////////////////////////////////
146 /// Insert object at location idx in the list.
147 
149 {
150  TList::AddAt(obj, idx);
151  fTable->Add(obj);
152 }
153 
154 ////////////////////////////////////////////////////////////////////////////////
155 /// Return the average collision rate. The higher the number the longer
156 /// the linked lists in the hashtable, the slower the lookup. If the number
157 /// is high, or lookup noticeably too slow, perform a Rehash().
158 
160 {
161  return fTable->AverageCollisions();
162 }
163 
164 ////////////////////////////////////////////////////////////////////////////////
165 /// Remove all objects from the list. Does not delete the objects unless
166 /// the THashList is the owner (set via SetOwner()).
167 
169 {
170  fTable->Clear("nodelete"); // clear table so not more lookups
171  if (IsOwner())
172  TList::Delete(option);
173  else
174  TList::Clear(option);
175 }
176 
177 ////////////////////////////////////////////////////////////////////////////////
178 /// Remove all objects from the list AND delete all heap based objects.
179 /// If option="slow" then keep list consistent during delete. This allows
180 /// recursive list operations during the delete (e.g. during the dtor
181 /// of an object in this list one can still access the list to search for
182 /// other not yet deleted objects).
183 
185 {
186  Bool_t slow = option ? (!strcmp(option, "slow") ? kTRUE : kFALSE) : kFALSE;
187 
188  if (!slow) {
189  fTable->Clear("nodelete"); // clear table so no more lookups
190  TList::Delete(option); // this deletes the objects
191  } else {
192  while (fFirst) {
193  TObjLink *tlk = fFirst;
194  fFirst = fFirst->Next();
195  fSize--;
196  // remove object from table
197  fTable->Remove(tlk->GetObject());
198  // delete only heap objects
199  if (tlk->GetObject() && tlk->GetObject()->IsOnHeap())
201 
202  delete tlk;
203  }
204  fFirst = fLast = fCache = 0;
205  fSize = 0;
206  }
207 }
208 
209 ////////////////////////////////////////////////////////////////////////////////
210 /// Find object using its name. Uses the hash value returned by the
211 /// TString::Hash() after converting name to a TString.
212 
213 TObject *THashList::FindObject(const char *name) const
214 {
215  return fTable->FindObject(name);
216 }
217 
218 ////////////////////////////////////////////////////////////////////////////////
219 /// Find object using its hash value (returned by its Hash() member).
220 
222 {
223  return fTable->FindObject(obj);
224 }
225 
226 ////////////////////////////////////////////////////////////////////////////////
227 /// Return the THashTable's list (bucket) in which obj can be found based on
228 /// its hash; see THashTable::GetListForObject().
229 
230 const TList *THashList::GetListForObject(const char *name) const
231 {
232  return fTable->GetListForObject(name);
233 }
234 
235 ////////////////////////////////////////////////////////////////////////////////
236 /// Return the THashTable's list (bucket) in which obj can be found based on
237 /// its hash; see THashTable::GetListForObject().
238 
239 const TList *THashList::GetListForObject(const TObject *obj) const
240 {
241  return fTable->GetListForObject(obj);
242 }
243 
244 ////////////////////////////////////////////////////////////////////////////////
245 /// Remove object from this collection and recursively remove the object
246 /// from all other objects (and collections).
247 /// This function overrides TCollection::RecursiveRemove that calls
248 /// the Remove function. THashList::Remove cannot be called because
249 /// it uses the hash value of the hash table. This hash value
250 /// is not available anymore when RecursiveRemove is called from
251 /// the TObject destructor.
252 
254 {
255  if (!obj) return;
256 
257  // Remove obj in the list itself
258  TObject *object = TList::Remove(obj);
259  if (object) fTable->RemoveSlow(object);
260 
261  // Scan again the list and invoke RecursiveRemove for all objects
262  TIter next(this);
263 
264  while ((object = next())) {
265  if (object->TestBit(kNotDeleted)) object->RecursiveRemove(obj);
266  }
267 }
268 
269 ////////////////////////////////////////////////////////////////////////////////
270 /// Rehash the hashlist. If the collision rate becomes too high (i.e.
271 /// the average size of the linked lists become too long) then lookup
272 /// efficiency decreases since relatively long lists have to be searched
273 /// every time. To improve performance rehash the hashtable. This resizes
274 /// the table to newCapacity slots and refills the table. Use
275 /// AverageCollisions() to check if you need to rehash.
276 
277 void THashList::Rehash(Int_t newCapacity)
278 {
279  fTable->Rehash(newCapacity);
280 }
281 
282 ////////////////////////////////////////////////////////////////////////////////
283 /// Remove object from the list.
284 
286 {
287  if (!obj || !fTable->FindObject(obj)) return 0;
288 
289  TList::Remove(obj);
290  return fTable->Remove(obj);
291 }
292 
293 ////////////////////////////////////////////////////////////////////////////////
294 /// Remove object via its objlink from the list.
295 
297 {
298  if (!lnk) return 0;
299 
300  TObject *obj = lnk->GetObject();
301 
302  TList::Remove(lnk);
303  return fTable->Remove(obj);
304 }
virtual void AddAt(TObject *obj, Int_t idx)
Insert object at position idx in the list.
Definition: TList.cxx:269
object has not been deleted
Definition: TObject.h:69
void AddFirst(TObject *obj)
Add object at the beginning of the list.
Definition: THashList.cxx:68
virtual void Delete(Option_t *option="")
Remove all objects from the list AND delete all heap based objects.
Definition: TList.cxx:405
void AddLast(TObject *obj)
Add object at the end of the list.
Definition: THashList.cxx:90
void AddBefore(const TObject *before, TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:98
float Float_t
Definition: RtypesCore.h:53
const char Option_t
Definition: RtypesCore.h:62
Bool_t TestBit(UInt_t f) const
Definition: TObject.h:157
virtual void AddFirst(TObject *obj)
Add object at the beginning of the list.
Definition: TList.cxx:93
void Rehash(Int_t newCapacity, Bool_t checkObjValidity=kTRUE)
Rehash the hashtable.
Definition: THashTable.cxx:280
Float_t AverageCollisions() const
Definition: THashTable.h:83
void Delete(Option_t *option="")
Remove all objects from the list AND delete all heap based objects.
Definition: THashList.cxx:184
Float_t AverageCollisions() const
Return the average collision rate.
Definition: THashList.cxx:159
const TList * GetListForObject(const char *name) const
Return the TList corresponding to object's name based hash value.
Definition: THashTable.cxx:234
int Int_t
Definition: RtypesCore.h:41
bool Bool_t
Definition: RtypesCore.h:59
const Bool_t kFALSE
Definition: Rtypes.h:92
TObject * RemoveSlow(TObject *obj)
Remove object from the hashtable without using the hash value.
Definition: THashTable.cxx:335
TObject * FindObject(const char *name) const
Find object using its name.
Definition: THashList.cxx:213
void RecursiveRemove(TObject *obj)
Remove object from this collection and recursively remove the object from all other objects (and coll...
Definition: THashList.cxx:253
THashTable * fTable
Definition: THashList.h:39
virtual void AddLast(TObject *obj)
Add object at the end of the list.
Definition: TList.cxx:137
virtual void RecursiveRemove(TObject *obj)
Recursively remove this object from a list.
Definition: TObject.cxx:617
#define SafeDelete(p)
Definition: RConfig.h:507
THashTable implements a hash table to store TObject's.
Definition: THashTable.h:39
THashList implements a hybrid collection class consisting of a hash table and a list to store TObject...
Definition: THashList.h:36
void Clear(Option_t *option="")
Remove all objects from the table.
Definition: THashTable.cxx:149
Bool_t IsOwner() const
Definition: TCollection.h:101
const TList * GetListForObject(const char *name) const
Return the THashTable's list (bucket) in which obj can be found based on its hash; see THashTable::Ge...
Definition: THashList.cxx:230
A doubly linked list.
Definition: TList.h:47
THashList(const THashList &)
void Clear(Option_t *option="")
Remove all objects from the list.
Definition: THashList.cxx:168
void AddAt(TObject *obj, Int_t idx)
Insert object at location idx in the list.
Definition: THashList.cxx:148
virtual TObject * Remove(TObject *obj)
Remove object from the list.
Definition: TList.cxx:675
TObject * Remove(TObject *obj)
Remove object from the list.
Definition: THashList.cxx:285
TObjLink * fLast
pointer to first entry in linked list
Definition: TList.h:53
void AddAfter(const TObject *after, TObject *obj)
Insert object after object after in the list.
Definition: THashList.cxx:130
Int_t fSize
Definition: TCollection.h:63
virtual void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the list.
Definition: TList.cxx:173
TObjLink * fFirst
Definition: TList.h:52
void Rehash(Int_t newCapacity)
Rehash the hashlist.
Definition: THashList.cxx:277
static void GarbageCollect(TObject *obj)
Add to the list of things to be cleaned up.
virtual ~THashList()
Delete a hashlist.
Definition: THashList.cxx:59
TObject * FindObject(const char *name) const
Find object using its name.
Definition: THashTable.cxx:210
Bool_t IsOnHeap() const
Definition: TObject.h:119
#define ClassImp(name)
Definition: Rtypes.h:279
void Add(TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:76
void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the list.
Definition: THashList.cxx:112
virtual void Clear(Option_t *option="")
Remove all objects from the list.
Definition: TList.cxx:349
virtual void AddAfter(const TObject *after, TObject *obj)
Insert object after object after in the list.
Definition: TList.cxx:221
Mother of all ROOT objects.
Definition: TObject.h:37
TObjLink * fCache
pointer to last entry in linked list
Definition: TList.h:54
const Bool_t kTRUE
Definition: Rtypes.h:91
char name[80]
Definition: TGX11.cxx:109
TObject * Remove(TObject *obj)
Remove object from the hashtable.
Definition: THashTable.cxx:315