Logo ROOT   6.18/05
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
14THashList implements a hybrid collection class consisting of a
15hash table and a list to store TObject's. The hash table is used for
16quick access and lookup of objects while the list allows the objects
17to be ordered. The hash value is calculated using the value returned
18by the TObject's Hash() function. Each class inheriting from TObject
19can override Hash() as it sees fit.
20*/
21
22#include "THashList.h"
23#include "THashTable.h"
24#include "TClass.h"
25
26
28
29////////////////////////////////////////////////////////////////////////////////
30/// Create a THashList object. Capacity is the initial hashtable capacity
31/// (i.e. number of slots), by default kInitHashTableCapacity = 17, and
32/// rehash is the value at which a rehash will be triggered. I.e. when the
33/// average size of the linked lists at a slot becomes longer than rehash
34/// then the hashtable will be resized and refilled to reduce the collision
35/// rate to about 1. The higher the collision rate, i.e. the longer the
36/// linked lists, the longer lookup will take. If rehash=0 the table will
37/// NOT automatically be rehashed. Use Rehash() for manual rehashing.
38///
39/// WARNING !!!
40/// If the name of an object in the HashList is modified, The hashlist
41/// must be Rehashed
42
44{
45 fTable = new THashTable(capacity, rehash);
46}
47
48////////////////////////////////////////////////////////////////////////////////
49/// For backward compatibility only. Use other ctor.
50
53 fTable = new THashTable(capacity, rehash);
54}
55
56////////////////////////////////////////////////////////////////////////////////
57/// Delete a hashlist. Objects are not deleted unless the THashList is the
58/// owner (set via SetOwner()).
59
61{
62 Clear();
64}
65
66////////////////////////////////////////////////////////////////////////////////
67/// Add object at the beginning of the list.
68
70{
72
73 TList::AddFirst(obj);
74 fTable->Add(obj);
75}
76
77////////////////////////////////////////////////////////////////////////////////
78/// Add object at the beginning of the list and also store option.
79/// Storing an option is useful when one wants to change the behaviour
80/// of an object a little without having to create a complete new
81/// copy of the object. This feature is used, for example, by the Draw()
82/// method. It allows the same object to be drawn in different ways.
83
85{
87
88 TList::AddFirst(obj, opt);
89 fTable->Add(obj);
90}
91
92////////////////////////////////////////////////////////////////////////////////
93/// Add object at the end of the list.
94
96{
98
99 TList::AddLast(obj);
100 fTable->Add(obj);
101}
102
103////////////////////////////////////////////////////////////////////////////////
104/// Add object at the end of the list and also store option.
105/// Storing an option is useful when one wants to change the behaviour
106/// of an object a little without having to create a complete new
107/// copy of the object. This feature is used, for example, by the Draw()
108/// method. It allows the same object to be drawn in different ways.
109
111{
113
114 TList::AddLast(obj, opt);
115 fTable->Add(obj);
116}
117
118////////////////////////////////////////////////////////////////////////////////
119/// Insert object before object before in the list.
120
121void THashList::AddBefore(const TObject *before, TObject *obj)
122{
124
125 TList::AddBefore(before, obj);
126 fTable->AddBefore(before, obj);
127}
128
129////////////////////////////////////////////////////////////////////////////////
130/// Insert object before object before in the list.
131
133{
135
136 TList::AddBefore(before, obj);
137 fTable->AddBefore(before->GetObject(), obj);
138}
139
140////////////////////////////////////////////////////////////////////////////////
141/// Insert object after object after in the list.
142
143void THashList::AddAfter(const TObject *after, TObject *obj)
144{
146
147 TList::AddAfter(after, obj);
148 fTable->Add(obj);
149}
150
151////////////////////////////////////////////////////////////////////////////////
152/// Insert object after object after in the list.
153
155{
157
158 TList::AddAfter(after, obj);
159 fTable->Add(obj);
160}
161
162////////////////////////////////////////////////////////////////////////////////
163/// Insert object at location idx in the list.
164
166{
168
169 TList::AddAt(obj, idx);
170 fTable->Add(obj);
171}
172
173////////////////////////////////////////////////////////////////////////////////
174/// Return the average collision rate. The higher the number the longer
175/// the linked lists in the hashtable, the slower the lookup. If the number
176/// is high, or lookup noticeably too slow, perform a Rehash().
177
179{
181
182 return fTable->AverageCollisions();
183}
184
185////////////////////////////////////////////////////////////////////////////////
186/// Remove all objects from the list. Does not delete the objects unless
187/// the THashList is the owner (set via SetOwner()).
188
190{
192
193 fTable->Clear("nodelete"); // clear table so not more lookups
194 if (IsOwner())
195 TList::Delete(option);
196 else
197 TList::Clear(option);
198}
199
200////////////////////////////////////////////////////////////////////////////////
201/// Remove all objects from the list AND delete all heap based objects.
202/// If option="slow" then keep list consistent during delete. This allows
203/// recursive list operations during the delete (e.g. during the dtor
204/// of an object in this list one can still access the list to search for
205/// other not yet deleted objects).
206
208{
210
211 Bool_t slow = option ? (!strcmp(option, "slow") ? kTRUE : kFALSE) : kFALSE;
212
213 if (!slow) {
214 fTable->Clear("nodelete"); // clear table so no more lookups
215 TList::Delete(option); // this deletes the objects
216 } else {
217 TList removeDirectory; // need to deregister these from their directory
218
219 while (fFirst) {
220 auto tlk = fFirst;
221 fFirst = fFirst->NextSP();
222 fSize--;
223 // remove object from table
224 fTable->Remove(tlk->GetObject());
225
226 // delete only heap objects
227 auto obj = tlk->GetObject();
228 // In case somebody else access it.
229 tlk->SetObject(nullptr);
230 if (obj && !obj->TestBit(kNotDeleted))
231 Error("Delete", "A list is accessing an object (%p) already deleted (list name = %s)",
232 obj, GetName());
233 else if (obj && obj->IsOnHeap())
235 else if (obj && obj->IsA()->GetDirectoryAutoAdd())
236 removeDirectory.Add(obj);
237
238 // tlk reference count goes down 1.
239 }
240 fFirst.reset();
241 fLast.reset();
242 fCache.reset();
243 fSize = 0;
244
245 // These objects cannot expect to have a valid TDirectory anymore;
246 // e.g. because *this is the TDirectory's list of objects. Even if
247 // not, they are supposed to be deleted, so we can as well unregister
248 // them from their directory, even if they are stack-based:
249 TIter iRemDir(&removeDirectory);
250 TObject* dirRem = 0;
251 while ((dirRem = iRemDir())) {
252 (*dirRem->IsA()->GetDirectoryAutoAdd())(dirRem, 0);
253 }
254 Changed();
255 }
256}
257
258////////////////////////////////////////////////////////////////////////////////
259/// Find object using its name. Uses the hash value returned by the
260/// TString::Hash() after converting name to a TString.
261
263{
265
266 return fTable->FindObject(name);
267}
268
269////////////////////////////////////////////////////////////////////////////////
270/// Find object using its hash value (returned by its Hash() member).
271
273{
275
276 return fTable->FindObject(obj);
277}
278
279////////////////////////////////////////////////////////////////////////////////
280/// Return the THashTable's list (bucket) in which obj can be found based on
281/// its hash; see THashTable::GetListForObject().
282
283const TList *THashList::GetListForObject(const char *name) const
284{
286
288}
289
290////////////////////////////////////////////////////////////////////////////////
291/// Return the THashTable's list (bucket) in which obj can be found based on
292/// its hash; see THashTable::GetListForObject().
293
295{
297
298 return fTable->GetListForObject(obj);
299}
300
301////////////////////////////////////////////////////////////////////////////////
302/// Remove object from this collection and recursively remove the object
303/// from all other objects (and collections).
304/// This function overrides TCollection::RecursiveRemove that calls
305/// the Remove function. THashList::Remove cannot be called because
306/// it uses the hash value of the hash table. This hash value
307/// is not available anymore when RecursiveRemove is called from
308/// the TObject destructor.
309
311{
312 if (!obj) return;
313
314 // It might not be safe to rely on TROOT::RecursiveRemove to take the readlock in case user code
315 // is calling directly gROOT->GetListOfCleanups()->RecursiveRemove(...)
316 // However this can become a significant bottleneck if there are a very large number of
317 // TDirectory object.
318 // R__COLLECTION_READ_LOCKGUARD(ROOT::gCoreMutex);
319
320 if (obj->HasInconsistentHash()) {
322
323 // Remove obj in the list itself
324 TObject *object = TList::Remove(obj);
325 if (object)
326 fTable->RemoveSlow(object);
327
328 } else if (fTable->FindObject(obj)) {
330
331 // Remove obj in the list itself
332 TObject *object = TList::Remove(obj);
333 if (object)
334 fTable->Remove(object);
335 }
336
337 if (!fFirst.get())
338 return;
339
340 // Scan again the list and invoke RecursiveRemove for all objects
341 // We need to make sure to go through all the node even those
342 // marked as empty by another thread (Eventhough we hold the
343 // read lock if one of the call to RecursiveRemove request
344 // the write lock then the read lock will be suspended and
345 // another thread can modify the list; thanks to the shared_pointer
346 // forward-and-backward links, our view of the list is still intact
347 // but might contains node will nullptr payload)
348 auto lnk = fFirst;
349 decltype(lnk) next;
350 while (lnk.get()) {
351 next = lnk->NextSP();
352 TObject *ob = lnk->GetObject();
353 if (ob && ob->TestBit(kNotDeleted)) {
354 ob->RecursiveRemove(obj);
355 }
356 lnk = next;
357 }
358}
359
360////////////////////////////////////////////////////////////////////////////////
361/// Rehash the hashlist. If the collision rate becomes too high (i.e.
362/// the average size of the linked lists become too long) then lookup
363/// efficiency decreases since relatively long lists have to be searched
364/// every time. To improve performance rehash the hashtable. This resizes
365/// the table to newCapacity slots and refills the table. Use
366/// AverageCollisions() to check if you need to rehash.
367
368void THashList::Rehash(Int_t newCapacity)
369{
371
372 fTable->Rehash(newCapacity);
373}
374
375////////////////////////////////////////////////////////////////////////////////
376/// Remove object from the list.
377
379{
381 if (!obj || !fTable->FindObject(obj)) return 0;
382
384 TList::Remove(obj);
385 return fTable->Remove(obj);
386}
387
388////////////////////////////////////////////////////////////////////////////////
389/// Remove object via its objlink from the list.
390
392{
393 if (!lnk) return 0;
394
396 TObject *obj = lnk->GetObject();
397
398 TList::Remove(lnk);
399 return fTable->Remove(obj);
400}
401
402////////////////////////////////////////////////////////////////////////////////
403/// Set this collection to use a RW lock upon access, making it thread safe.
404/// Return the previous state.
405///
406/// Note: To test whether the usage is enabled do:
407/// collection->TestBit(TCollection::kUseRWLock);
408
410{
411 fTable->UseRWLock();
412 return TCollection::UseRWLock();
413}
#define SafeDelete(p)
Definition: RConfig.hxx:543
int Int_t
Definition: RtypesCore.h:41
const Bool_t kFALSE
Definition: RtypesCore.h:88
bool Bool_t
Definition: RtypesCore.h:59
float Float_t
Definition: RtypesCore.h:53
const Bool_t kTRUE
Definition: RtypesCore.h:87
const char Option_t
Definition: RtypesCore.h:62
#define ClassImp(name)
Definition: Rtypes.h:365
#define R__COLLECTION_READ_LOCKGUARD(mutex)
Definition: TCollection.h:435
#define R__COLLECTION_WRITE_LOCKGUARD(mutex)
Definition: TCollection.h:438
char name[80]
Definition: TGX11.cxx:109
virtual const char * GetName() const
Return name of this collection.
virtual bool UseRWLock()
Set this collection to use a RW lock upon access, making it thread safe.
Bool_t IsOwner() const
Definition: TCollection.h:188
static void GarbageCollect(TObject *obj)
Add to the list of things to be cleaned up.
THashList implements a hybrid collection class consisting of a hash table and a list to store TObject...
Definition: THashList.h:34
TObject * FindObject(const char *name) const
Find object using its name.
Definition: THashList.cxx:262
void RecursiveRemove(TObject *obj)
Remove object from this collection and recursively remove the object from all other objects (and coll...
Definition: THashList.cxx:310
void Rehash(Int_t newCapacity)
Rehash the hashlist.
Definition: THashList.cxx:368
virtual ~THashList()
Delete a hashlist.
Definition: THashList.cxx:60
void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the list.
Definition: THashList.cxx:121
bool UseRWLock()
Set this collection to use a RW lock upon access, making it thread safe.
Definition: THashList.cxx:409
THashTable * fTable
Definition: THashList.h:37
void AddAt(TObject *obj, Int_t idx)
Insert object at location idx in the list.
Definition: THashList.cxx:165
TObject * Remove(TObject *obj)
Remove object from the list.
Definition: THashList.cxx:378
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:283
THashList(const THashList &)
void Clear(Option_t *option="")
Remove all objects from the list.
Definition: THashList.cxx:189
void AddFirst(TObject *obj)
Add object at the beginning of the list.
Definition: THashList.cxx:69
void Delete(Option_t *option="")
Remove all objects from the list AND delete all heap based objects.
Definition: THashList.cxx:207
Float_t AverageCollisions() const
Return the average collision rate.
Definition: THashList.cxx:178
void AddAfter(const TObject *after, TObject *obj)
Insert object after object after in the list.
Definition: THashList.cxx:143
void AddLast(TObject *obj)
Add object at the end of the list.
Definition: THashList.cxx:95
THashTable implements a hash table to store TObject's.
Definition: THashTable.h:35
Float_t AverageCollisions() const
Definition: THashTable.h:84
TObject * Remove(TObject *obj)
Remove object from the hashtable.
Definition: THashTable.cxx:417
const TList * GetListForObject(const char *name) const
Return the TList corresponding to object's name based hash value.
Definition: THashTable.cxx:268
void Add(TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:92
void Rehash(Int_t newCapacity, Bool_t checkObjValidity=kTRUE)
Rehash the hashtable.
Definition: THashTable.cxx:365
TObject * RemoveSlow(TObject *obj)
Remove object from the hashtable without using the hash value.
Definition: THashTable.cxx:442
void AddBefore(const TObject *before, TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:112
TObject * FindObject(const char *name) const
Find object using its name.
Definition: THashTable.cxx:238
void Clear(Option_t *option="")
Remove all objects from the table.
Definition: THashTable.cxx:167
A doubly linked list.
Definition: TList.h:44
virtual void Add(TObject *obj)
Definition: TList.h:87
virtual TObject * Remove(TObject *obj)
Remove object from the list.
Definition: TList.cxx:819
virtual void AddAt(TObject *obj, Int_t idx)
Insert object at position idx in the list.
Definition: TList.cxx:303
virtual void AddFirst(TObject *obj)
Add object at the beginning of the list.
Definition: TList.cxx:97
TObjLinkPtr_t fLast
pointer to first entry in linked list
Definition: TList.h:53
virtual void AddAfter(const TObject *after, TObject *obj)
Insert object after object after in the list.
Definition: TList.cxx:247
TObjLinkPtr_t fFirst
Definition: TList.h:52
virtual void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the list.
Definition: TList.cxx:193
TObjLinkWeakPtr_t fCache
pointer to last entry in linked list
Definition: TList.h:54
virtual void Delete(Option_t *option="")
Remove all objects from the list AND delete all heap based objects.
Definition: TList.cxx:467
virtual void AddLast(TObject *obj)
Add object at the end of the list.
Definition: TList.cxx:149
virtual void Clear(Option_t *option="")
Remove all objects from the list.
Definition: TList.cxx:399
Mother of all ROOT objects.
Definition: TObject.h:37
Bool_t HasInconsistentHash() const
Return true is the type of this object is known to have an inconsistent setup for Hash and RecursiveR...
Definition: TObject.h:330
@ kNotDeleted
object has not been deleted
Definition: TObject.h:78
R__ALWAYS_INLINE Bool_t TestBit(UInt_t f) const
Definition: TObject.h:172
virtual void RecursiveRemove(TObject *obj)
Recursively remove this object from a list.
Definition: TObject.cxx:572
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition: TObject.cxx:880
virtual void Changed()
R__EXTERN TVirtualRWMutex * gCoreMutex