Logo ROOT   master
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 #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 
43 THashList::THashList(Int_t capacity, Int_t rehash)
44 {
45  fTable = new THashTable(capacity, rehash);
46 }
47 
48 ////////////////////////////////////////////////////////////////////////////////
49 /// For backward compatibility only. Use other ctor.
50 
52 {
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 
121 void 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 
143 void 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 
262 TObject *THashList::FindObject(const char *name) const
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 
283 const TList *THashList::GetListForObject(const char *name) const
284 {
286 
287  return fTable->GetListForObject(name);
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 
294 const TList *THashList::GetListForObject(const TObject *obj) const
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 
368 void 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 }
virtual void AddAt(TObject *obj, Int_t idx)
Insert object at position idx in the list.
Definition: TList.cxx:305
void AddFirst(TObject *obj)
Add object at the beginning of the list.
Definition: THashList.cxx:69
virtual void Delete(Option_t *option="")
Remove all objects from the list AND delete all heap based objects.
Definition: TList.cxx:469
void AddLast(TObject *obj)
Add object at the end of the list.
Definition: THashList.cxx:95
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
void AddBefore(const TObject *before, TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:112
float Float_t
Definition: RtypesCore.h:55
const char Option_t
Definition: RtypesCore.h:64
TObjLinkPtr_t fFirst
Definition: TList.h:52
virtual void AddFirst(TObject *obj)
Add object at the beginning of the list.
Definition: TList.cxx:99
void Rehash(Int_t newCapacity, Bool_t checkObjValidity=kTRUE)
Rehash the hashtable.
Definition: THashTable.cxx:362
Float_t AverageCollisions() const
Definition: THashTable.h:84
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
R__ALWAYS_INLINE Bool_t TestBit(UInt_t f) const
Definition: TObject.h:172
const TList * GetListForObject(const char *name) const
Return the TList corresponding to object's name based hash value.
Definition: THashTable.cxx:265
TObject * RemoveSlow(TObject *obj)
Remove object from the hashtable without using the hash value.
Definition: THashTable.cxx:439
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
THashTable * fTable
Definition: THashList.h:37
virtual void AddLast(TObject *obj)
Add object at the end of the list.
Definition: TList.cxx:151
TObjLinkWeakPtr_t fCache
pointer to last entry in linked list
Definition: TList.h:54
virtual void RecursiveRemove(TObject *obj)
Recursively remove this object from a list.
Definition: TObject.cxx:572
THashTable implements a hash table to store TObject's.
Definition: THashTable.h:35
THashList implements a hybrid collection class consisting of a hash table and a list to store TObject...
Definition: THashList.h:34
virtual void Changed()
void Clear(Option_t *option="")
Remove all objects from the table.
Definition: THashTable.cxx:167
#define R__COLLECTION_READ_LOCKGUARD(mutex)
Definition: TCollection.h:435
R__EXTERN TVirtualRWMutex * gCoreMutex
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
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
A doubly linked list.
Definition: TList.h:44
THashList(const THashList &)
void Clear(Option_t *option="")
Remove all objects from the list.
Definition: THashList.cxx:189
void AddAt(TObject *obj, Int_t idx)
Insert object at location idx in the list.
Definition: THashList.cxx:165
virtual TObject * Remove(TObject *obj)
Remove object from the list.
Definition: TList.cxx:821
TObject * Remove(TObject *obj)
Remove object from the list.
Definition: THashList.cxx:378
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition: TObject.cxx:888
void AddAfter(const TObject *after, TObject *obj)
Insert object after object after in the list.
Definition: THashList.cxx:143
virtual void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the list.
Definition: TList.cxx:195
const Bool_t kFALSE
Definition: RtypesCore.h:90
void Rehash(Int_t newCapacity)
Rehash the hashlist.
Definition: THashList.cxx:368
static void GarbageCollect(TObject *obj)
Add to the list of things to be cleaned up.
virtual ~THashList()
Delete a hashlist.
Definition: THashList.cxx:60
#define SafeDelete(p)
Definition: RConfig.hxx:543
TObject * FindObject(const char *name) const
Find object using its name.
Definition: THashTable.cxx:238
#define ClassImp(name)
Definition: Rtypes.h:361
void Add(TObject *obj)
Add object to the hash table.
Definition: THashTable.cxx:92
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
virtual void Clear(Option_t *option="")
Remove all objects from the list.
Definition: TList.cxx:401
virtual void AddAfter(const TObject *after, TObject *obj)
Insert object after object after in the list.
Definition: TList.cxx:249
Mother of all ROOT objects.
Definition: TObject.h:37
virtual void Add(TObject *obj)
Definition: TList.h:87
object has not been deleted
Definition: TObject.h:78
#define R__COLLECTION_WRITE_LOCKGUARD(mutex)
Definition: TCollection.h:438
const Bool_t kTRUE
Definition: RtypesCore.h:89
char name[80]
Definition: TGX11.cxx:109
virtual const char * GetName() const
Return name of this collection.
TObjLinkPtr_t fLast
pointer to first entry in linked list
Definition: TList.h:53
TObject * Remove(TObject *obj)
Remove object from the hashtable.
Definition: THashTable.cxx:414