Logo ROOT  
Reference Guide
 
Loading...
Searching...
No Matches
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())
196 else
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 && ROOT::Detail::HasBeenDeleted(obj))
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 = nullptr;
251 while ((dirRem = iRemDir())) {
252 (*dirRem->IsA()->GetDirectoryAutoAdd())(dirRem, nullptr);
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 || fSize == 0)
313 return;
314
315 // It might not be safe to rely on TROOT::RecursiveRemove to take the readlock in case user code
316 // is calling directly gROOT->GetListOfCleanups()->RecursiveRemove(...)
317 // However this can become a significant bottleneck if there are a very large number of
318 // TDirectory object.
319 // If we need to enabling this read lock, we need to move the fSize check afterwards.
320 // TList::RecursiveRemove has the same pattern.
321 // R__COLLECTION_READ_LOCKGUARD(ROOT::gCoreMutex);
322
323 if (obj->HasInconsistentHash()) {
325
326 // Remove obj in the list itself
327 TObject *object = TList::Remove(obj);
328 if (object)
329 fTable->RemoveSlow(object);
330
331 } else if (fTable->FindObject(obj)) {
333
334 // Remove obj in the list itself
335 TObject *object = TList::Remove(obj);
336 if (object)
337 fTable->Remove(object);
338 }
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 && !ROOT::Detail::HasBeenDeleted(ob)) {
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 nullptr;
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 nullptr;
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(enable);
412 return TCollection::UseRWLock(enable);
413}
#define SafeDelete(p)
Definition RConfig.hxx:542
float Float_t
Definition RtypesCore.h:57
constexpr Bool_t kFALSE
Definition RtypesCore.h:101
constexpr Bool_t kTRUE
Definition RtypesCore.h:100
const char Option_t
Definition RtypesCore.h:66
#define ClassImp(name)
Definition Rtypes.h:377
#define R__COLLECTION_READ_LOCKGUARD(mutex)
#define R__COLLECTION_WRITE_LOCKGUARD(mutex)
Option_t Option_t option
char name[80]
Definition TGX11.cxx:110
ROOT::DirAutoAdd_t GetDirectoryAutoAdd() const
Return the wrapper around the directory auto add function.
Definition TClass.cxx:7487
virtual bool UseRWLock(Bool_t enable=true)
Set this collection to use a RW lock upon access, making it thread safe.
const char * GetName() const override
Return name of this collection.
Bool_t IsOwner() const
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
void Delete(Option_t *option="") override
Remove all objects from the list AND delete all heap based objects.
void AddBefore(const TObject *before, TObject *obj) override
Insert object before object before in the list.
void Clear(Option_t *option="") override
Remove all objects from the list.
void AddFirst(TObject *obj) override
Add object at the beginning of the list.
Definition THashList.cxx:69
void Rehash(Int_t newCapacity)
Rehash the hashlist.
virtual ~THashList()
Delete a hashlist.
Definition THashList.cxx:60
void AddAfter(const TObject *after, TObject *obj) override
Insert object after object after in the list.
THashTable * fTable
Definition THashList.h:37
void RecursiveRemove(TObject *obj) override
Remove object from this collection and recursively remove the object from all other objects (and coll...
void AddAt(TObject *obj, Int_t idx) override
Insert object at location idx in the list.
THashList(const THashList &)=delete
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...
bool UseRWLock(Bool_t enable=true) override
Set this collection to use a RW lock upon access, making it thread safe.
Float_t AverageCollisions() const
Return the average collision rate.
TObject * Remove(TObject *obj) override
Remove object from the list.
TObject * FindObject(const char *name) const override
Find object using its name.
void AddLast(TObject *obj) override
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:85
void Add(TObject *obj) override
Add object to the hash table.
const TList * GetListForObject(const char *name) const
Return the TList corresponding to object's name based hash value.
TObject * Remove(TObject *obj) override
Remove object from the hashtable.
void Rehash(Int_t newCapacity, Bool_t checkObjValidity=kTRUE)
Rehash the hashtable.
TObject * RemoveSlow(TObject *obj)
Remove object from the hashtable without using the hash value.
void AddBefore(const TObject *before, TObject *obj)
Add object to the hash table.
TObject * FindObject(const char *name) const override
Find object using its name.
void Clear(Option_t *option="") override
Remove all objects from the table.
A doubly linked list.
Definition TList.h:38
void AddAfter(const TObject *after, TObject *obj) override
Insert object after object after in the list.
Definition TList.cxx:248
void Clear(Option_t *option="") override
Remove all objects from the list.
Definition TList.cxx:400
void AddAt(TObject *obj, Int_t idx) override
Insert object at position idx in the list.
Definition TList.cxx:304
void Add(TObject *obj) override
Definition TList.h:81
TObject * Remove(TObject *obj) override
Remove object from the list.
Definition TList.cxx:820
void AddLast(TObject *obj) override
Add object at the end of the list.
Definition TList.cxx:150
TObjLinkPtr_t fLast
pointer to first entry in linked list
Definition TList.h:47
void AddBefore(const TObject *before, TObject *obj) override
Insert object before object before in the list.
Definition TList.cxx:194
TObjLinkPtr_t fFirst
Definition TList.h:46
void Delete(Option_t *option="") override
Remove all objects from the list AND delete all heap based objects.
Definition TList.cxx:468
TObjLinkWeakPtr_t fCache
pointer to last entry in linked list
Definition TList.h:48
void AddFirst(TObject *obj) override
Add object at the beginning of the list.
Definition TList.cxx:98
Mother of all ROOT objects.
Definition TObject.h:41
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:360
virtual void RecursiveRemove(TObject *obj)
Recursively remove this object from a list.
Definition TObject.cxx:659
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition TObject.cxx:976
virtual TClass * IsA() const
Definition TObject.h:245
virtual void Changed()
R__ALWAYS_INLINE bool HasBeenDeleted(const TObject *obj)
Check if the TObject's memory has been deleted.
Definition TObject.h:404
R__EXTERN TVirtualRWMutex * gCoreMutex