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
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
43{
44 fTable = new THashTable(capacity, rehash);
45}
46
47////////////////////////////////////////////////////////////////////////////////
48/// For backward compatibility only. Use other ctor.
49
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
64
65////////////////////////////////////////////////////////////////////////////////
66/// Add object at the beginning of the list.
67
75
76////////////////////////////////////////////////////////////////////////////////
77/// Add object at the beginning of the list and also store option.
78/// Storing an option is useful when one wants to change the behaviour
79/// of an object a little without having to create a complete new
80/// copy of the object. This feature is used, for example, by the Draw()
81/// method. It allows the same object to be drawn in different ways.
82
90
91////////////////////////////////////////////////////////////////////////////////
92/// Add object at the end of the list.
93
101
102////////////////////////////////////////////////////////////////////////////////
103/// Add object at the end of the list and also store option.
104/// Storing an option is useful when one wants to change the behaviour
105/// of an object a little without having to create a complete new
106/// copy of the object. This feature is used, for example, by the Draw()
107/// method. It allows the same object to be drawn in different ways.
108
110{
112
113 TList::AddLast(obj, opt);
114 fTable->Add(obj);
115}
116
117////////////////////////////////////////////////////////////////////////////////
118/// Insert object before object before in the list.
119
127
128////////////////////////////////////////////////////////////////////////////////
129/// Insert object before object before in the list.
130
138
139////////////////////////////////////////////////////////////////////////////////
140/// Insert object after object after in the list.
141
149
150////////////////////////////////////////////////////////////////////////////////
151/// Insert object after object after in the list.
152
160
161////////////////////////////////////////////////////////////////////////////////
162/// Insert object at location idx in the list.
163
165{
167
168 TList::AddAt(obj, idx);
169 fTable->Add(obj);
170}
171
172////////////////////////////////////////////////////////////////////////////////
173/// Return the average collision rate. The higher the number the longer
174/// the linked lists in the hashtable, the slower the lookup. If the number
175/// is high, or lookup noticeably too slow, perform a Rehash().
176
183
184////////////////////////////////////////////////////////////////////////////////
185/// Remove all objects from the list. Does not delete the objects unless
186/// the THashList is the owner (set via SetOwner()).
187
189{
191
192 fTable->Clear("nodelete"); // clear table so not more lookups
193 if (IsOwner())
195 else
197}
198
199////////////////////////////////////////////////////////////////////////////////
200/// Remove all objects from the list AND delete all heap based objects.
201/// If option="slow" then keep list consistent during delete. This allows
202/// recursive list operations during the delete (e.g. during the dtor
203/// of an object in this list one can still access the list to search for
204/// other not yet deleted objects).
205
207{
209
210 Bool_t slow = option ? (!strcmp(option, "slow") ? kTRUE : kFALSE) : kFALSE;
211
212 if (!slow) {
213 fTable->Clear("nodelete"); // clear table so no more lookups
214 TList::Delete(option); // this deletes the objects
215 } else {
216 TList removeDirectory; // need to deregister these from their directory
217
218 while (fFirst) {
219 auto tlk = fFirst;
220 fFirst = fFirst->NextSP();
221 fSize--;
222 // remove object from table
223 fTable->Remove(tlk->GetObject());
224
225 // delete only heap objects
226 auto obj = tlk->GetObject();
227 // In case somebody else access it.
228 tlk->SetObject(nullptr);
229 if (obj && ROOT::Detail::HasBeenDeleted(obj))
230 Error("Delete", "A list is accessing an object (%p) already deleted (list name = %s)",
231 obj, GetName());
232 else if (obj && obj->IsOnHeap())
234 else if (obj && obj->IsA()->GetDirectoryAutoAdd())
235 removeDirectory.Add(obj);
236
237 // tlk reference count goes down 1.
238 }
239 fFirst.reset();
240 fLast.reset();
241 fCache.reset();
242 fSize = 0;
243
244 // These objects cannot expect to have a valid TDirectory anymore;
245 // e.g. because *this is the TDirectory's list of objects. Even if
246 // not, they are supposed to be deleted, so we can as well unregister
247 // them from their directory, even if they are stack-based:
249 TObject* dirRem = nullptr;
250 while ((dirRem = iRemDir())) {
251 (*dirRem->IsA()->GetDirectoryAutoAdd())(dirRem, nullptr);
252 }
253 Changed();
254 }
255}
256
257////////////////////////////////////////////////////////////////////////////////
258/// Find object using its name. Uses the hash value returned by the
259/// TString::Hash() after converting name to a TString.
260
267
268////////////////////////////////////////////////////////////////////////////////
269/// Find object using its hash value (returned by its Hash() member).
270
277
278////////////////////////////////////////////////////////////////////////////////
279/// Return the THashTable's list (bucket) in which obj can be found based on
280/// its hash; see THashTable::GetListForObject().
281
288
289////////////////////////////////////////////////////////////////////////////////
290/// Return the THashTable's list (bucket) in which obj can be found based on
291/// its hash; see THashTable::GetListForObject().
292
299
300////////////////////////////////////////////////////////////////////////////////
301/// Remove object from this collection and recursively remove the object
302/// from all other objects (and collections).
303/// This function overrides TCollection::RecursiveRemove that calls
304/// the Remove function. THashList::Remove cannot be called because
305/// it uses the hash value of the hash table. This hash value
306/// is not available anymore when RecursiveRemove is called from
307/// the TObject destructor.
308
310{
311 if (!obj || fSize == 0)
312 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 // If we need to enabling this read lock, we need to move the fSize check afterwards.
319 // TList::RecursiveRemove has the same pattern.
320 // R__COLLECTION_READ_LOCKGUARD(ROOT::gCoreMutex);
321
322 if (obj->HasInconsistentHash()) {
324
325 // Remove obj in the list itself
326 TObject *object = TList::Remove(obj);
327 if (object)
328 fTable->RemoveSlow(object);
329
330 } else if (fTable->FindObject(obj)) {
332
333 // Remove obj in the list itself
334 TObject *object = TList::Remove(obj);
335 if (object)
336 fTable->Remove(object);
337 }
338
339 // Scan again the list and invoke RecursiveRemove for all objects
340 // We need to make sure to go through all the node even those
341 // marked as empty by another thread (Eventhough we hold the
342 // read lock if one of the call to RecursiveRemove request
343 // the write lock then the read lock will be suspended and
344 // another thread can modify the list; thanks to the shared_pointer
345 // forward-and-backward links, our view of the list is still intact
346 // but might contains node will nullptr payload)
347 auto lnk = fFirst;
348 decltype(lnk) next;
349 while (lnk.get()) {
350 next = lnk->NextSP();
351 TObject *ob = lnk->GetObject();
353 ob->RecursiveRemove(obj);
354 }
355 lnk = next;
356 }
357}
358
359////////////////////////////////////////////////////////////////////////////////
360/// Rehash the hashlist. If the collision rate becomes too high (i.e.
361/// the average size of the linked lists become too long) then lookup
362/// efficiency decreases since relatively long lists have to be searched
363/// every time. To improve performance rehash the hashtable. This resizes
364/// the table to newCapacity slots and refills the table. Use
365/// AverageCollisions() to check if you need to rehash.
366
373
374////////////////////////////////////////////////////////////////////////////////
375/// Remove object from the list.
376
378{
380 if (!obj || !fTable->FindObject(obj)) return nullptr;
381
383 TList::Remove(obj);
384 return fTable->Remove(obj);
385}
386
387////////////////////////////////////////////////////////////////////////////////
388/// Remove object via its objlink from the list.
389
391{
392 if (!lnk) return nullptr;
393
395 TObject *obj = lnk->GetObject();
396
398 return fTable->Remove(obj);
399}
400
401////////////////////////////////////////////////////////////////////////////////
402/// Set this collection to use a RW lock upon access, making it thread safe.
403/// Return the previous state.
404///
405/// Note: To test whether the usage is enabled do:
406/// collection->TestBit(TCollection::kUseRWLock);
407
#define SafeDelete(p)
Definition RConfig.hxx:533
float Float_t
Float 4 bytes (float)
Definition RtypesCore.h:71
constexpr Bool_t kFALSE
Definition RtypesCore.h:108
constexpr Bool_t kTRUE
Definition RtypesCore.h:107
const char Option_t
Option string (const char)
Definition RtypesCore.h:80
#define R__COLLECTION_READ_LOCKGUARD(mutex)
ROOT::Detail::TRangeCast< T, true > TRangeDynCast
TRangeDynCast is an adapter class that allows the typed iteration through a TCollection.
#define R__COLLECTION_WRITE_LOCKGUARD(mutex)
Option_t Option_t option
char name[80]
Definition TGX11.cxx:110
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.
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:68
void Rehash(Int_t newCapacity)
Rehash the hashlist.
virtual ~THashList()
Delete a hashlist.
Definition THashList.cxx:59
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:94
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:247
void Clear(Option_t *option="") override
Remove all objects from the list.
Definition TList.cxx:399
void AddAt(TObject *obj, Int_t idx) override
Insert object at position idx in the list.
Definition TList.cxx:303
TObject * Remove(TObject *obj) override
Remove object from the list.
Definition TList.cxx:819
void AddLast(TObject *obj) override
Add object at the end of the list.
Definition TList.cxx:149
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:193
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:467
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:97
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:361
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition TObject.cxx:1071
virtual void Changed()
R__ALWAYS_INLINE bool HasBeenDeleted(const TObject *obj)
Check if the TObject's memory has been deleted.
Definition TObject.h:405
R__EXTERN TVirtualRWMutex * gCoreMutex