Logo ROOT  
Reference Guide
TList.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 TList
13 \ingroup Containers
14 A doubly linked list.
15 
16 All classes inheriting from TObject can be
17 inserted in a TList. Before being inserted into the list the object
18 pointer is wrapped in a TObjLink object which contains, besides
19 the object pointer also a previous and next pointer.
20 
21 There are several ways to iterate over a TList; in order of preference, if
22 not forced by other constraints:
23  0. (Preferred way) Using the C++ range-based `for` or `begin()` / `end()`:
24 ~~~ {.cpp}
25  for(const auto&& obj: *GetListOfPrimitives())
26  obj->Write();
27 ~~~
28  1. Using the R__FOR_EACH macro:
29 ~~~ {.cpp}
30  GetListOfPrimitives()->R__FOR_EACH(TObject,Paint)(option);
31 ~~~
32  2. Using the TList iterator TListIter (via the wrapper class TIter):
33 ~~~ {.cpp}
34  TIter next(GetListOfPrimitives());
35  while (TObject *obj = next())
36  obj->Draw(next.GetOption());
37 ~~~
38  3. Using the TList iterator TListIter and std::for_each algorithm:
39 ~~~ {.cpp}
40  // A function object, which will be applied to each element
41  // of the given range.
42  struct STestFunctor {
43  bool operator()(TObject *aObj) {
44  ...
45  return true;
46  }
47  }
48  ...
49  ...
50  TIter iter(mylist);
51  for_each( iter.Begin(), TIter::End(), STestFunctor() );
52 ~~~
53  4. Using the TObjLink list entries (that wrap the TObject*):
54 ~~~ {.cpp}
55  TObjLink *lnk = GetListOfPrimitives()->FirstLink();
56  while (lnk) {
57  lnk->GetObject()->Draw(lnk->GetOption());
58  lnk = lnk->Next();
59  }
60 ~~~
61  5. Using the TList's After() and Before() member functions:
62 ~~~ {.cpp}
63  TFree *idcur = this;
64  while (idcur) {
65  ...
66  ...
67  idcur = (TFree*)GetListOfFree()->After(idcur);
68  }
69 ~~~
70 Methods 2, 3 and 4 can also easily iterate backwards using either
71 a backward TIter (using argument kIterBackward) or by using
72 LastLink() and lnk->Prev() or by using the Before() member.
73 */
74 
75 #include "TList.h"
76 #include "TClass.h"
77 #include "TROOT.h"
78 #include "TVirtualMutex.h"
79 #include "TBuffer.h"
80 
81 #include <string>
82 
83 using namespace std;
84 
86 
87 ////////////////////////////////////////////////////////////////////////////////
88 /// Delete the list. Objects are not deleted unless the TList is the
89 /// owner (set via SetOwner()).
90 
92 {
93  Clear();
94 }
95 
96 ////////////////////////////////////////////////////////////////////////////////
97 /// Add object at the beginning of the list.
98 
100 {
102 
103  if (IsArgNull("AddFirst", obj)) return;
104 
106 
107  if (!fFirst) {
108  fFirst = NewLink(obj);
109  fLast = fFirst;
110  } else {
111  auto t = NewLink(obj);
112  t->fNext = fFirst;
113  fFirst->fPrev = t;
114  fFirst = t;
115  }
116  fSize++;
117  Changed();
118 }
119 
120 ////////////////////////////////////////////////////////////////////////////////
121 /// Add object at the beginning of the list and also store option.
122 /// Storing an option is useful when one wants to change the behaviour
123 /// of an object a little without having to create a complete new
124 /// copy of the object. This feature is used, for example, by the Draw()
125 /// method. It allows the same object to be drawn in different ways.
126 
128 {
130 
131  if (IsArgNull("AddFirst", obj)) return;
132 
134 
135  if (!fFirst) {
136  fFirst = NewOptLink(obj, opt);
137  fLast = fFirst;
138  } else {
139  auto t = NewOptLink(obj, opt);
140  t->fNext = fFirst;
141  fFirst->fPrev = t;
142  fFirst = t;
143  }
144  fSize++;
145  Changed();
146 }
147 
148 ////////////////////////////////////////////////////////////////////////////////
149 /// Add object at the end of the list.
150 
152 {
154 
155  if (IsArgNull("AddLast", obj)) return;
156 
158 
159  if (!fFirst) {
160  fFirst = NewLink(obj);
161  fLast = fFirst;
162  } else
163  fLast = NewLink(obj, fLast);
164  fSize++;
165  Changed();
166 }
167 
168 ////////////////////////////////////////////////////////////////////////////////
169 /// Add object at the end of the list and also store option.
170 /// Storing an option is useful when one wants to change the behaviour
171 /// of an object a little without having to create a complete new
172 /// copy of the object. This feature is used, for example, by the Draw()
173 /// method. It allows the same object to be drawn in different ways.
174 
176 {
178 
179  if (IsArgNull("AddLast", obj)) return;
180 
182 
183  if (!fFirst) {
184  fFirst = NewOptLink(obj, opt);
185  fLast = fFirst;
186  } else
187  fLast = NewOptLink(obj, opt, fLast);
188  fSize++;
189  Changed();
190 }
191 
192 ////////////////////////////////////////////////////////////////////////////////
193 /// Insert object before object before in the list.
194 
195 void TList::AddBefore(const TObject *before, TObject *obj)
196 {
198 
199  if (IsArgNull("AddBefore", obj)) return;
200 
202 
203  if (!before)
204  TList::AddFirst(obj);
205  else {
206  Int_t idx;
207  TObjLink *t = FindLink(before, idx);
208  if (!t) {
209  Error("AddBefore", "before not found, object not added");
210  return;
211  }
212  if (t == fFirst.get())
213  TList::AddFirst(obj);
214  else {
215  NewLink(obj, t->fPrev.lock());
216  fSize++;
217  Changed();
218  }
219  }
220 }
221 
222 ////////////////////////////////////////////////////////////////////////////////
223 /// Insert object before the specified ObjLink object. If before = 0 then add
224 /// to the head of the list. An ObjLink can be obtained by looping over a list
225 /// using the above describe iterator method 3.
226 
227 void TList::AddBefore(TObjLink *before, TObject *obj)
228 {
230 
231  if (IsArgNull("AddBefore", obj)) return;
232 
233  if (!before)
234  TList::AddFirst(obj);
235  else {
236  if (before == fFirst.get())
237  TList::AddFirst(obj);
238  else {
239  NewLink(obj, before->fPrev.lock());
240  fSize++;
241  Changed();
242  }
243  }
244 }
245 
246 ////////////////////////////////////////////////////////////////////////////////
247 /// Insert object after object after in the list.
248 
249 void TList::AddAfter(const TObject *after, TObject *obj)
250 {
252 
253  if (IsArgNull("AddAfter", obj)) return;
254 
256 
257  if (!after)
258  TList::AddLast(obj);
259  else {
260  Int_t idx;
261  TObjLink *t = FindLink(after, idx);
262  if (!t) {
263  Error("AddAfter", "after not found, object not added");
264  return;
265  }
266  if (t == fLast.get())
267  TList::AddLast(obj);
268  else {
269  NewLink(obj, t->shared_from_this());
270  fSize++;
271  Changed();
272  }
273  }
274 }
275 
276 ////////////////////////////////////////////////////////////////////////////////
277 /// Insert object after the specified ObjLink object. If after = 0 then add
278 /// to the tail of the list. An ObjLink can be obtained by looping over a list
279 /// using the above describe iterator method 3.
280 
281 void TList::AddAfter(TObjLink *after, TObject *obj)
282 {
284 
285  if (IsArgNull("AddAfter", obj)) return;
286 
288 
289  if (!after)
290  TList::AddLast(obj);
291  else {
292  if (after == fLast.get())
293  TList::AddLast(obj);
294  else {
295  NewLink(obj, after->shared_from_this());
296  fSize++;
297  Changed();
298  }
299  }
300 }
301 
302 ////////////////////////////////////////////////////////////////////////////////
303 /// Insert object at position idx in the list.
304 
305 void TList::AddAt(TObject *obj, Int_t idx)
306 {
308 
309  if (IsArgNull("AddAt", obj)) return;
310 
312 
313  TObjLink *lnk = LinkAt(idx);
314  if (!lnk)
315  TList::AddLast(obj);
316  else if (lnk == fFirst.get())
317  TList::AddFirst(obj);
318  else {
319  NewLink(obj, lnk->fPrev.lock());
320  fSize++;
321  Changed();
322  }
323 }
324 
325 ////////////////////////////////////////////////////////////////////////////////
326 /// Returns the object after object obj. Obj is found using the
327 /// object's IsEqual() method. Returns 0 if obj is last in list.
328 
329 TObject *TList::After(const TObject *obj) const
330 {
332 
333  TObjLink *t;
334 
336 
337  auto cached = fCache.lock();
338  if (cached.get() && cached->GetObject() && cached->GetObject()->IsEqual(obj)) {
339  t = cached.get();
340  ((TList*)this)->fCache = cached->fNext; //cast const away, fCache should be mutable
341  } else {
342  Int_t idx;
343  t = FindLink(obj, idx);
344  if (t) ((TList*)this)->fCache = t->fNext;
345  }
346 
347  if (t && t->Next())
348  return t->Next()->GetObject();
349  else
350  return 0;
351 }
352 
353 ////////////////////////////////////////////////////////////////////////////////
354 /// Returns the object at position idx. Returns 0 if idx is out of range.
355 
357 {
360 
361  TObjLink *lnk = LinkAt(idx);
362  if (lnk) return lnk->GetObject();
363  return 0;
364 }
365 
366 ////////////////////////////////////////////////////////////////////////////////
367 /// Returns the object before object obj. Obj is found using the
368 /// object's IsEqual() method. Returns 0 if obj is first in list.
369 
370 TObject *TList::Before(const TObject *obj) const
371 {
374 
375  TObjLink *t;
376 
377  auto cached = fCache.lock();
378  if (cached.get() && cached->GetObject() && cached->GetObject()->IsEqual(obj)) {
379  t = cached.get();
380  ((TList*)this)->fCache = cached->fPrev; //cast const away, fCache should be mutable
381  } else {
382  Int_t idx;
383  t = FindLink(obj, idx);
384  if (t) ((TList*)this)->fCache = t->fPrev;
385  }
386 
387  if (t && t->Prev())
388  return t->Prev()->GetObject();
389  else
390  return 0;
391 }
392 
393 ////////////////////////////////////////////////////////////////////////////////
394 /// Remove all objects from the list. Does not delete the objects
395 /// unless the TList is the owner (set via SetOwner()) and option
396 /// "nodelete" is not set.
397 /// If option="nodelete" then don't delete any heap objects that were
398 /// marked with the kCanDelete bit, otherwise these objects will be
399 /// deleted (this option is used by THashTable::Clear()).
400 
401 void TList::Clear(Option_t *option)
402 {
405 
406  Bool_t nodel = option ? (!strcmp(option, "nodelete") ? kTRUE : kFALSE) : kFALSE;
407 
408  if (!nodel && IsOwner()) {
409  Delete(option);
410  return;
411  }
412 
413  // In some case, for example TParallelCoord, a list (the pad's list of
414  // primitives) will contain both the container and the containees
415  // (the TParallelCoordVar) but if the Clear is being called from
416  // the destructor of the container of this list, one of the first
417  // thing done will be the remove the container (the pad) for the
418  // list (of Primitives of the canvas) that was connecting it
419  // (indirectly) to the list of cleanups.
420  // Note: The Code in TParallelCoordVar was changed (circa June 2017),
421  // to no longer have this behavior and thus rely on this code (by moving
422  // from using Draw to Paint) but the structure might still exist elsewhere
423  // so we keep this comment here.
424 
425  // To preserve this connection (without introducing one when there was none),
426  // we re-use fCache to inform RecursiveRemove of the node currently
427  // being cleared/deleted.
428  while (fFirst) {
429  auto tlk = fFirst;
430  fFirst = fFirst->fNext;
431  fSize--;
432 
433 
434  // Make node available to RecursiveRemove
435  tlk->fNext.reset();
436  tlk->fPrev.reset();
437  fCache = tlk;
438 
439  // delete only heap objects marked OK to clear
440  auto obj = tlk->GetObject();
441  if (!nodel && obj) {
442  if (!obj->TestBit(kNotDeleted)) {
443  Error("Clear", "A list is accessing an object (%p) already deleted (list name = %s)",
444  obj, GetName());
445  } else if (obj->IsOnHeap()) {
446  if (obj->TestBit(kCanDelete)) {
447  if (obj->TestBit(kNotDeleted)) {
449  }
450  }
451  }
452  }
453  // delete tlk;
454  }
455  fFirst.reset();
456  fLast.reset();
457  fCache.reset();
458  fSize = 0;
459  Changed();
460 }
461 
462 ////////////////////////////////////////////////////////////////////////////////
463 /// Remove all objects from the list AND delete all heap based objects.
464 /// If option="slow" then keep list consistent during delete. This allows
465 /// recursive list operations during the delete (e.g. during the dtor
466 /// of an object in this list one can still access the list to search for
467 /// other not yet deleted objects).
468 
469 void TList::Delete(Option_t *option)
470 {
473 
474  Bool_t slow = option ? (!strcmp(option, "slow") ? kTRUE : kFALSE) : kFALSE;
475 
476  TList removeDirectory; // need to deregister these from their directory
477 
478  if (slow) {
479 
480  // In some case, for example TParallelCoord, a list (the pad's list of
481  // primitives) will contain both the container and the containees
482  // (the TParallelCoorVar) but if the Clear is being called from
483  // the destructor of the container of this list, one of the first
484  // thing done will be the remove the container (the pad) for the
485  // list (of Primitives of the canvas) that was connecting it
486  // (indirectly) to the list of cleanups.
487 
488  // To preserve this connection (without introducing one when there was none),
489  // we re-use fCache to inform RecursiveRemove of the node currently
490  // being cleared/deleted.
491  while (fFirst) {
492  auto tlk = fFirst;
493  fFirst = fFirst->fNext;
494  fSize--;
495 
496  // Make node available to RecursiveRemove
497  tlk->fNext.reset();
498  tlk->fPrev.reset();
499  fCache = tlk;
500 
501  // delete only heap objects
502  auto obj = tlk->GetObject();
503  if (obj && !obj->TestBit(kNotDeleted))
504  Error("Delete", "A list is accessing an object (%p) already deleted (list name = %s)",
505  obj, GetName());
506  else if (obj && obj->IsOnHeap())
508  else if (obj && obj->IsA()->GetDirectoryAutoAdd())
509  removeDirectory.Add(obj);
510 
511  // delete tlk;
512  }
513 
514  fFirst.reset();
515  fLast.reset();
516  fCache.reset();
517  fSize = 0;
518 
519  } else {
520 
521  auto first = fFirst; //pointer to first entry in linked list
522  fFirst.reset();
523  fLast.reset();
524  fCache.reset();
525  fSize = 0;
526  while (first) {
527  auto tlk = first;
528  first = first->fNext;
529  // delete only heap objects
530  auto obj = tlk->GetObject();
531  tlk->SetObject(nullptr);
532  if (obj && !obj->TestBit(kNotDeleted))
533  Error("Delete", "A list is accessing an object (%p) already deleted (list name = %s)",
534  obj, GetName());
535  else if (obj && obj->IsOnHeap())
537  else if (obj && obj->IsA()->GetDirectoryAutoAdd())
538  removeDirectory.Add(obj);
539 
540  // The formerly first token, when tlk goes out of scope has no more references
541  // because of the fFirst.reset()
542  }
543  }
544 
545  // These objects cannot expect to have a valid TDirectory anymore;
546  // e.g. because *this is the TDirectory's list of objects. Even if
547  // not, they are supposed to be deleted, so we can as well unregister
548  // them from their directory, even if they are stack-based:
549  TIter iRemDir(&removeDirectory);
550  TObject* dirRem = 0;
551  while ((dirRem = iRemDir())) {
552  (*dirRem->IsA()->GetDirectoryAutoAdd())(dirRem, 0);
553  }
554  Changed();
555 }
556 
557 #if 0
558 ////////////////////////////////////////////////////////////////////////////////
559 /// Delete a TObjLink object.
560 
561 void TList::DeleteLink(TObjLink *lnk)
562 {
564 
565  lnk->fNext = lnk->fPrev = 0;
566  lnk->fObject = 0;
567  delete lnk;
568 }
569 #endif
570 
571 ////////////////////////////////////////////////////////////////////////////////
572 /// Find an object in this list using its name. Requires a sequential
573 /// scan till the object has been found. Returns 0 if object with specified
574 /// name is not found. This method overrides the generic FindObject()
575 /// of TCollection for efficiency reasons.
576 
577 TObject *TList::FindObject(const char *name) const
578 {
580 
581  if (!name)
582  return nullptr;
583 
585 
586  for (TObjLink *lnk = FirstLink(); lnk != nullptr; lnk = lnk->Next()) {
587  if (TObject *obj = lnk->GetObject()) {
588  const char *objname = obj->GetName();
589  if (objname && strcmp(name, objname) == 0)
590  return obj;
591  }
592  }
593 
594  return nullptr;
595 }
596 
597 ////////////////////////////////////////////////////////////////////////////////
598 /// Find an object in this list using the object's IsEqual()
599 /// member function. Requires a sequential scan till the object has
600 /// been found. Returns 0 if object is not found.
601 /// This method overrides the generic FindObject() of TCollection for
602 /// efficiency reasons.
603 
605 {
607 
608  if (!obj)
609  return nullptr;
610 
612 
613  TObjLink *lnk = FirstLink();
614 
615  while (lnk) {
616  TObject *ob = lnk->GetObject();
617  if (ob->IsEqual(obj)) return ob;
618  lnk = lnk->Next();
619  }
620  return nullptr;
621 }
622 
623 ////////////////////////////////////////////////////////////////////////////////
624 /// Returns the TObjLink object that contains object obj. In idx it returns
625 /// the position of the object in the list.
626 
627 TObjLink *TList::FindLink(const TObject *obj, Int_t &idx) const
628 {
630 
631  if (!obj)
632  return nullptr;
633 
635 
636  if (!fFirst) return 0;
637 
638  TObject *object;
639  TObjLink *lnk = fFirst.get();
640  idx = 0;
641 
642  while (lnk) {
643  object = lnk->GetObject();
644  if (object) {
645  if (object->TestBit(kNotDeleted)) {
646  if (object->IsEqual(obj)) return lnk;
647  }
648  }
649  lnk = lnk->Next();
650  idx++;
651  }
652  return 0;
653 }
654 
655 ////////////////////////////////////////////////////////////////////////////////
656 /// Return the first object in the list. Returns 0 when list is empty.
657 
659 {
662 
663  if (fFirst) return fFirst->GetObject();
664  return 0;
665 }
666 
667 ////////////////////////////////////////////////////////////////////////////////
668 /// Return address of pointer to obj
669 
671 {
673 
674  if (!obj)
675  return nullptr;
676 
678 
679  TObjLink *lnk = FirstLink();
680 
681  while (lnk) {
682  TObject *ob = lnk->GetObject();
683  if (ob->IsEqual(obj)) return lnk->GetObjectRef();
684  lnk = lnk->Next();
685  }
686  return 0;
687 }
688 
689 ////////////////////////////////////////////////////////////////////////////////
690 /// Return the last object in the list. Returns 0 when list is empty.
691 
693 {
696 
697  if (fLast) return fLast->GetObject();
698  return 0;
699 }
700 
701 ////////////////////////////////////////////////////////////////////////////////
702 /// Return the TObjLink object at index idx.
703 
705 {
708 
709  Int_t i = 0;
710  TObjLink *lnk = fFirst.get();
711  while (i < idx && lnk) {
712  i++;
713  lnk = lnk->Next();
714  }
715  return lnk;
716 }
717 
718 ////////////////////////////////////////////////////////////////////////////////
719 /// Return a list iterator.
720 
722 {
725 
726  return new TListIter(this, dir);
727 }
728 
729 ////////////////////////////////////////////////////////////////////////////////
730 /// Return a new TObjLink.
731 
733 {
736 
737  auto newlink = std::make_shared<TObjLink>(obj);
738  if (prev) {
739  InsertAfter(newlink, prev);
740  }
741  return newlink;
742 }
743 
744 ////////////////////////////////////////////////////////////////////////////////
745 /// Return a new TObjOptLink (a TObjLink that also stores the option).
746 
748 {
751 
752  auto newlink = std::make_shared<TObjOptLink>(obj, opt);
753  if (prev) {
754  InsertAfter(newlink, prev);
755  }
756  return newlink;
757 }
758 
759 ////////////////////////////////////////////////////////////////////////////////
760 /// Remove object from this collection and recursively remove the object
761 /// from all other objects (and collections).
762 
764 {
766 
767  if (!obj) return;
768 
769  // When fCache is set and has no previous and next node, it represents
770  // the node being cleared and/or deleted.
771  {
772  auto cached = fCache.lock();
773  if (cached && cached->fNext.get() == nullptr && cached->fPrev.lock().get() == nullptr) {
774  TObject *ob = cached->GetObject();
775  if (ob && ob->TestBit(kNotDeleted)) {
776  ob->RecursiveRemove(obj);
777  }
778  }
779  }
780 
781  if (!fFirst.get())
782  return;
783 
784  auto lnk = fFirst;
785  decltype(lnk) next;
786  while (lnk.get()) {
787  next = lnk->fNext;
788  TObject *ob = lnk->GetObject();
789  if (ob && ob->TestBit(kNotDeleted)) {
790  if (ob->IsEqual(obj)) {
791  lnk->SetObject(nullptr);
792  if (lnk == fFirst) {
793  fFirst = next;
794  if (lnk == fLast)
795  fLast = fFirst;
796  else
797  fFirst->fPrev.reset();
798  // DeleteLink(lnk);
799  } else if (lnk == fLast) {
800  fLast = lnk->fPrev.lock();
801  fLast->fNext.reset();
802  // DeleteLink(lnk);
803  } else {
804  lnk->Prev()->fNext = next;
805  lnk->Next()->fPrev = lnk->fPrev;
806  // DeleteLink(lnk);
807  }
808  fSize--;
809  fCache.reset();
810  Changed();
811  } else
812  ob->RecursiveRemove(obj);
813  }
814  lnk = next;
815  }
816 }
817 
818 ////////////////////////////////////////////////////////////////////////////////
819 /// Remove object from the list.
820 
822 {
824 
825  if (!obj) return 0;
826 
827  Int_t idx;
828  TObjLink *lnk = FindLink(obj, idx);
829 
830  if (!lnk) return 0;
831 
832  // return object found, which may be (pointer wise) different than the
833  // input object (depending on what IsEqual() is doing)
834 
836 
837  TObject *ob = lnk->GetObject();
838  lnk->SetObject(nullptr);
839  if (lnk == fFirst.get()) {
840  fFirst = lnk->fNext;
841  // lnk is still alive as we have either fLast
842  // or the 'new' fFirst->fPrev pointing to it.
843  if (lnk == fLast.get()) {
844  fLast.reset();
845  fFirst.reset();
846  } else
847  fFirst->fPrev.reset();
848  //DeleteLink(lnk);
849  } else if (lnk == fLast.get()) {
850  fLast = lnk->fPrev.lock();
851  fLast->fNext.reset();
852  //DeleteLink(lnk);
853  } else {
854  lnk->Next()->fPrev = lnk->fPrev;
855  lnk->Prev()->fNext = lnk->fNext;
856  //DeleteLink(lnk);
857  }
858  fSize--;
859  fCache.reset();
860  Changed();
861 
862  return ob;
863 }
864 
865 ////////////////////////////////////////////////////////////////////////////////
866 /// Remove object link (and therefore the object it contains)
867 /// from the list.
868 
870 {
872 
873  if (!lnk) return 0;
874 
876 
877  TObject *obj = lnk->GetObject();
878  lnk->SetObject(nullptr);
879  if (lnk == fFirst.get()) {
880  fFirst = lnk->fNext;
881  // lnk is still alive as we have either fLast
882  // or the 'new' fFirst->fPrev pointing to it.
883  if (lnk == fLast.get()) {
884  fLast.reset();
885  fFirst.reset();
886  } else
887  fFirst->fPrev.reset();
888  // DeleteLink(lnk);
889  } else if (lnk == fLast.get()) {
890  fLast = lnk->fPrev.lock();
891  fLast->fNext.reset();
892  // DeleteLink(lnk);
893  } else {
894  lnk->Next()->fPrev = lnk->fPrev;
895  lnk->Prev()->fNext = lnk->fNext;
896  // DeleteLink(lnk);
897  }
898  fSize--;
899  fCache.reset();
900  Changed();
901 
902  return obj;
903 }
904 
905 ////////////////////////////////////////////////////////////////////////////////
906 /// Remove the last object of the list.
907 
909 {
912 
913  TObjLink *lnk = fLast.get();
914  if (!lnk) return;
915 
916  lnk->SetObject(nullptr);
917  if (lnk == fFirst.get()) {
918  fFirst.reset();
919  fLast.reset();
920  } else {
921  fLast = lnk->fPrev.lock();
922  fLast->fNext.reset();
923  }
924  // DeleteLink(lnk);
925 
926  fSize--;
927  fCache.reset();
928  Changed();
929 }
930 
931 ////////////////////////////////////////////////////////////////////////////////
932 /// Sort linked list. Real sorting is done in private function DoSort().
933 /// The list can only be sorted when is contains objects of a sortable
934 /// class.
935 
936 void TList::Sort(Bool_t order)
937 {
940 
941  if (!fFirst) return;
942 
943  fAscending = order;
944 
945  if (!fFirst->GetObject()->IsSortable()) {
946  Error("Sort", "objects in list are not sortable");
947  return;
948  }
949 
950  DoSort(&fFirst, fSize);
951 
952  // correct back links
953  std::shared_ptr<TObjLink> ol, lnk = fFirst;
954 
955  if (lnk.get()) lnk->fPrev.reset();
956  while ((ol = lnk)) {
957  lnk = lnk->fNext;
958  if (lnk)
959  lnk->fPrev = ol;
960  else
961  fLast = ol;
962  }
963  fSorted = kTRUE;
964 }
965 
966 ////////////////////////////////////////////////////////////////////////////////
967 /// Compares the objects stored in the TObjLink objects.
968 /// Depending on the flag IsAscending() the function returns
969 /// true if the object in l1 <= l2 (ascending) or l2 <= l1 (descending).
970 
972 {
973  Int_t cmp = l1->GetObject()->Compare(l2->GetObject());
974 
975  if ((IsAscending() && cmp <=0) || (!IsAscending() && cmp > 0))
976  return kTRUE;
977  return kFALSE;
978 }
979 
980 ////////////////////////////////////////////////////////////////////////////////
981 /// Sort linked list.
982 
983 std::shared_ptr<TObjLink> *TList::DoSort(std::shared_ptr<TObjLink> *head, Int_t n)
984 {
987 
988  std::shared_ptr<TObjLink> p1, p2, *h2, *t2;
989 
990  switch (n) {
991  case 0:
992  return head;
993 
994  case 1:
995  return &((*head)->fNext);
996 
997  case 2:
998  p2 = (p1 = *head)->fNext;
999  if (LnkCompare(p1, p2)) return &(p2->fNext);
1000  p1->fNext = (*head = p2)->fNext;
1001  return &((p2->fNext = p1)->fNext);
1002  }
1003 
1004  int m;
1005  n -= m = n / 2;
1006 
1007  t2 = DoSort(h2 = DoSort(head, n), m);
1008 
1009  if (LnkCompare((p1 = *head), (p2 = *h2))) {
1010  do {
1011  if (!--n) return *h2 = p2, t2;
1012  } while (LnkCompare((p1 = *(head = &(p1->fNext))), p2));
1013  }
1014 
1015  while (1) {
1016  *head = p2;
1017  do {
1018  if (!--m) return *h2 = *t2, *t2 = p1, h2;
1019  } while (!LnkCompare(p1, (p2 = *(head = &(p2->fNext)))));
1020  *head = p1;
1021  do {
1022  if (!--n) return *h2 = p2, t2;
1023  } while (LnkCompare((p1 = *(head = &(p1->fNext))), p2));
1024  }
1025 }
1026 
1027 /** \class TObjLink
1028 Wrapper around a TObject so it can be stored in a TList.
1029 */
1030 
1031 ////////////////////////////////////////////////////////////////////////////////
1032 /// Insert a new link in the chain.
1033 
1034 void TList::InsertAfter(const TObjLinkPtr_t &newlink, const TObjLinkPtr_t &prev)
1035 {
1036  newlink->fNext = prev->fNext;
1037  newlink->fPrev = prev;
1038  prev->fNext = newlink;
1039  if (newlink->fNext)
1040  newlink->fNext->fPrev = newlink;
1041 }
1042 
1043 /** \class TListIter
1044 Iterator of linked list.
1045 */
1046 
1048 
1049 ////////////////////////////////////////////////////////////////////////////////
1050 /// Create a new list iterator. By default the iteration direction
1051 /// is kIterForward. To go backward use kIterBackward.
1052 
1054  : fList(l), fCurCursor(0), fCursor(0), fDirection(dir), fStarted(kFALSE)
1055 {
1057 }
1058 
1059 ////////////////////////////////////////////////////////////////////////////////
1060 /// Copy ctor.
1061 
1063 {
1065 
1066  fList = iter.fList;
1067  fCurCursor = iter.fCurCursor;
1068  fCursor = iter.fCursor;
1069  fDirection = iter.fDirection;
1070  fStarted = iter.fStarted;
1071 }
1072 
1073 ////////////////////////////////////////////////////////////////////////////////
1074 /// Overridden assignment operator.
1075 
1077 {
1078 
1079  const TListIter *rhs1 = dynamic_cast<const TListIter *>(&rhs);
1080  if (this != &rhs && rhs1) {
1082  TIterator::operator=(rhs);
1083  fList = rhs1->fList;
1084  fCurCursor = rhs1->fCurCursor;
1085  fCursor = rhs1->fCursor;
1086  fDirection = rhs1->fDirection;
1087  fStarted = rhs1->fStarted;
1088  }
1089  return *this;
1090 }
1091 
1092 ////////////////////////////////////////////////////////////////////////////////
1093 /// Overloaded assignment operator.
1094 
1096 {
1097  if (this != &rhs) {
1099  TIterator::operator=(rhs);
1100  fList = rhs.fList;
1101  fCurCursor = rhs.fCurCursor;
1102  fCursor = rhs.fCursor;
1103  fDirection = rhs.fDirection;
1104  fStarted = rhs.fStarted;
1105  }
1106  return *this;
1107 }
1108 
1109 ////////////////////////////////////////////////////////////////////////////////
1110 /// Return next object in the list. Returns 0 when no more objects in list.
1111 
1113 {
1114  if (!fList) return 0;
1115 
1117 
1118  if (fDirection == kIterForward) {
1119  if (!fStarted) {
1120  fCursor = fList->fFirst;
1121  fStarted = kTRUE;
1122  }
1123  fCurCursor = fCursor;
1124  if (fCursor) {
1125  auto next = fCursor = fCursor->NextSP();
1126  }
1127  } else {
1128  if (!fStarted) {
1129  fCursor = fList->fLast;
1130  fStarted = kTRUE;
1131  }
1132  fCurCursor = fCursor;
1133  if (fCursor) fCursor = fCursor->PrevSP();
1134  }
1135 
1136  if (fCurCursor) return fCurCursor->GetObject();
1137  return 0;
1138 }
1139 
1140 ////////////////////////////////////////////////////////////////////////////////
1141 /// Returns the object option stored in the list.
1142 
1144 {
1145  if (fCurCursor) return fCurCursor->GetOption();
1146  return "";
1147 }
1148 
1149 ////////////////////////////////////////////////////////////////////////////////
1150 /// Sets the object option stored in the list.
1151 
1153 {
1154  if (fCurCursor) fCurCursor->SetOption(option);
1155 }
1156 
1157 ////////////////////////////////////////////////////////////////////////////////
1158 /// Reset list iterator.
1159 
1161 {
1163  fStarted = kFALSE;
1164 }
1165 
1166 ////////////////////////////////////////////////////////////////////////////////
1167 /// This operator compares two TIterator objects.
1168 
1170 {
1171  if (IsA() == aIter.IsA()) {
1172  // We compared equal only two iterator of the same type.
1173  // Since this is a function of TListIter, we consequently know that
1174  // both this and aIter are of type inheriting from TListIter.
1175  const TListIter &iter(dynamic_cast<const TListIter &>(aIter));
1176  return (fCurCursor != iter.fCurCursor);
1177  }
1178  return false; // for base class we don't implement a comparison
1179 }
1180 
1181 ////////////////////////////////////////////////////////////////////////////////
1182 /// This operator compares two TListIter objects.
1183 
1185 {
1186  return (fCurCursor != aIter.fCurCursor);
1187 }
1188 
1189 ////////////////////////////////////////////////////////////////////////////////
1190 /// Stream all objects in the collection to or from the I/O buffer.
1191 
1192 void TList::Streamer(TBuffer &b)
1193 {
1195 
1196  Int_t nobjects;
1197  UChar_t nch;
1198  Int_t nbig;
1199  TObject *obj;
1200  UInt_t R__s, R__c;
1201 
1202  if (b.IsReading()) {
1203  Clear(); // Get rid of old data if any.
1204  Version_t v = b.ReadVersion(&R__s, &R__c);
1205  if (v > 3) {
1206  TObject::Streamer(b);
1207  fName.Streamer(b);
1208  b >> nobjects;
1209  string readOption;
1210  for (Int_t i = 0; i < nobjects; i++) {
1211  b >> obj;
1212  b >> nch;
1213  if (v > 4 && nch == 255) {
1214  b >> nbig;
1215  } else {
1216  nbig = nch;
1217  }
1218  readOption.resize(nbig,'\0');
1219  b.ReadFastArray((char*) readOption.data(),nbig);
1220  if (obj) { // obj can be null if the class had a custom streamer and we do not have the shared library nor a streamerInfo.
1221  if (nch) {
1222  Add(obj,readOption.c_str());
1223  } else {
1224  Add(obj);
1225  }
1226  }
1227  }
1228  b.CheckByteCount(R__s, R__c,TList::IsA());
1229  return;
1230  }
1231 
1232  // process old versions when TList::Streamer was in TCollection::Streamer
1233  if (v > 2)
1234  TObject::Streamer(b);
1235  if (v > 1)
1236  fName.Streamer(b);
1237  b >> nobjects;
1238  for (Int_t i = 0; i < nobjects; i++) {
1239  b >> obj;
1240  Add(obj);
1241  }
1242  b.CheckByteCount(R__s, R__c,TList::IsA());
1243 
1244  } else {
1246 
1247  R__c = b.WriteVersion(TList::IsA(), kTRUE);
1248  TObject::Streamer(b);
1249  fName.Streamer(b);
1250  nobjects = GetSize();
1251  b << nobjects;
1252 
1253  TObjLink *lnk = fFirst.get();
1254  while (lnk) {
1255  obj = lnk->GetObject();
1256  b << obj;
1257 
1258  nbig = strlen(lnk->GetAddOption());
1259  if (nbig > 254) {
1260  nch = 255;
1261  b << nch;
1262  b << nbig;
1263  } else {
1264  nch = UChar_t(nbig);
1265  b << nch;
1266  }
1267  b.WriteFastArray(lnk->GetAddOption(),nbig);
1268 
1269  lnk = lnk->Next();
1270  }
1271  b.SetByteCount(R__c, kTRUE);
1272  }
1273 }
TListIter::fDirection
Bool_t fDirection
Definition: TList.h:208
l
auto * l
Definition: textangle.C:4
TList::AddAt
virtual void AddAt(TObject *obj, Int_t idx)
Insert object at position idx in the list.
Definition: TList.cxx:305
m
auto * m
Definition: textangle.C:8
R__COLLECTION_WRITE_LOCKGUARD
#define R__COLLECTION_WRITE_LOCKGUARD(mutex)
Definition: TCollection.h:438
n
const Int_t n
Definition: legend1.C:16
first
Definition: first.py:1
TList::InsertAfter
void InsertAfter(const TObjLinkPtr_t &newlink, const TObjLinkPtr_t &prev)
Insert a new link in the chain.
Definition: TList.cxx:1034
TList::GetObjectRef
virtual TObject ** GetObjectRef(const TObject *obj) const
Return address of pointer to obj.
Definition: TList.cxx:670
TList::RemoveLast
virtual void RemoveLast()
Remove the last object of the list.
Definition: TList.cxx:908
kTRUE
const Bool_t kTRUE
Definition: RtypesCore.h:91
TObject::TestBit
R__ALWAYS_INLINE Bool_t TestBit(UInt_t f) const
Definition: TObject.h:172
Version_t
short Version_t
Definition: RtypesCore.h:65
TList::AddFirst
virtual void AddFirst(TObject *obj)
Add object at the beginning of the list.
Definition: TList.cxx:99
TListIter::SetOption
void SetOption(Option_t *option)
Sets the object option stored in the list.
Definition: TList.cxx:1152
kCanDelete
@ kCanDelete
Definition: TObject.h:339
TList::FindObject
virtual TObject * FindObject(const char *name) const
Find an object in this list using its name.
Definition: TList.cxx:577
TList::Delete
virtual void Delete(Option_t *option="")
Remove all objects from the list AND delete all heap based objects.
Definition: TList.cxx:469
R__COLLECTION_READ_GUARD
#define R__COLLECTION_READ_GUARD()
Definition: TCollection.h:126
ClassImp
#define ClassImp(name)
Definition: Rtypes.h:364
R__COLLECTION_READ_LOCKGUARD
#define R__COLLECTION_READ_LOCKGUARD(mutex)
Definition: TCollection.h:435
TList::fFirst
TObjLinkPtr_t fFirst
Definition: TList.h:52
TListIter::GetOption
Option_t * GetOption() const
Returns the object option stored in the list.
Definition: TList.cxx:1143
TList::LinkAt
TObjLink * LinkAt(Int_t idx) const
sorting order (when calling Sort() or for TSortedList)
Definition: TList.cxx:704
TClass.h
TList.h
TList::Last
virtual TObject * Last() const
Return the last object in the list. Returns 0 when list is empty.
Definition: TList.cxx:692
TCollection::fName
TString fName
Definition: TCollection.h:147
TListIter::fCurCursor
TObjLinkPtr_t fCurCursor
Definition: TList.h:206
ROOT::gCoreMutex
R__EXTERN TVirtualRWMutex * gCoreMutex
Definition: TVirtualRWMutex.h:38
TBuffer
Definition: TBuffer.h:43
TList::AddLast
virtual void AddLast(TObject *obj)
Add object at the end of the list.
Definition: TList.cxx:151
TList::LnkCompare
Bool_t LnkCompare(const TObjLinkPtr_t &l1, const TObjLinkPtr_t &l2)
Compares the objects stored in the TObjLink objects.
Definition: TList.cxx:971
TListIter::operator!=
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
Definition: TList.cxx:1169
v
@ v
Definition: rootcling_impl.cxx:3635
b
#define b(i)
Definition: RSha256.hxx:118
TObject::RecursiveRemove
virtual void RecursiveRemove(TObject *obj)
Recursively remove this object from a list.
Definition: TObject.cxx:574
bool
TIterator
Definition: TIterator.h:30
TListIter
Definition: TList.h:197
object
TList::Sort
virtual void Sort(Bool_t order=kSortAscending)
Sort linked list.
Definition: TList.cxx:936
TROOT.h
kIterForward
const Bool_t kIterForward
Definition: TCollection.h:40
TListIter::Next
TObject * Next()
Return next object in the list. Returns 0 when no more objects in list.
Definition: TList.cxx:1112
TList::First
virtual TObject * First() const
Return the first object in the list. Returns 0 when list is empty.
Definition: TList.cxx:658
TList::MakeIterator
virtual TIterator * MakeIterator(Bool_t dir=kIterForward) const
Return a list iterator.
Definition: TList.cxx:721
TList::At
virtual TObject * At(Int_t idx) const
Returns the object at position idx. Returns 0 if idx is out of range.
Definition: TList.cxx:356
TList::After
virtual TObject * After(const TObject *obj) const
Returns the object after object obj.
Definition: TList.cxx:329
Option_t
const typedef char Option_t
Definition: RtypesCore.h:66
TList::~TList
virtual ~TList()
Delete the list.
Definition: TList.cxx:91
TBuffer.h
TListIter::fCursor
TObjLinkPtr_t fCursor
Definition: TList.h:207
TCollection::GarbageCollect
static void GarbageCollect(TObject *obj)
Add to the list of things to be cleaned up.
Definition: TCollection.cxx:725
TList::Before
virtual TObject * Before(const TObject *obj) const
Returns the object before object obj.
Definition: TList.cxx:370
TList::NewOptLink
TObjLinkPtr_t NewOptLink(TObject *obj, Option_t *opt, const TObjLinkPtr_t &prev=nullptr)
Return a new TObjOptLink (a TObjLink that also stores the option).
Definition: TList.cxx:747
TList::AddBefore
virtual void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the list.
Definition: TList.cxx:195
kFALSE
const Bool_t kFALSE
Definition: RtypesCore.h:92
TList::TObjLinkPtr_t
std::shared_ptr< TObjLink > TObjLinkPtr_t
Definition: TList.h:49
TObject::IsEqual
virtual Bool_t IsEqual(const TObject *obj) const
Default equal comparison (objects are equal if they have the same address in memory).
Definition: TObject.cxx:485
TListIter::Reset
void Reset()
Reset list iterator.
Definition: TList.cxx:1160
TListIter::fList
const TList * fList
Definition: TList.h:205
TVirtualMutex.h
unsigned int
TList::DoSort
TObjLinkPtr_t * DoSort(TObjLinkPtr_t *head, Int_t n)
Sort linked list.
Definition: TList.cxx:983
TList::AddAfter
virtual void AddAfter(const TObject *after, TObject *obj)
Insert object after object after in the list.
Definition: TList.cxx:249
TIterator::operator=
virtual TIterator & operator=(const TIterator &)
Definition: TIterator.h:37
TList::Remove
virtual TObject * Remove(TObject *obj)
Remove object from the list.
Definition: TList.cxx:821
TCollection::GetSize
virtual Int_t GetSize() const
Return the capacity of the collection, i.e.
Definition: TCollection.h:182
UChar_t
unsigned char UChar_t
Definition: RtypesCore.h:38
TList::Add
virtual void Add(TObject *obj)
Definition: TList.h:87
TObject
Definition: TObject.h:37
TList::fLast
TObjLinkPtr_t fLast
pointer to first entry in linked list
Definition: TList.h:53
TList::Clear
virtual void Clear(Option_t *option="")
Remove all objects from the list.
Definition: TList.cxx:401
name
char name[80]
Definition: TGX11.cxx:110
TIter
Definition: TCollection.h:233
fSize
size_t fSize
Definition: DeclareConverters.h:342
R__COLLECTION_WRITE_GUARD
#define R__COLLECTION_WRITE_GUARD()
Definition: TCollection.h:125
fFirst
T1 fFirst
Definition: X11Events.mm:86
TList::FindLink
TObjLink * FindLink(const TObject *obj, Int_t &idx) const
Returns the TObjLink object that contains object obj.
Definition: TList.cxx:627
TList::NewLink
TObjLinkPtr_t NewLink(TObject *obj, const TObjLinkPtr_t &prev=nullptr)
Return a new TObjLink.
Definition: TList.cxx:732
TListIter::fStarted
Bool_t fStarted
Definition: TList.h:209
TList::RecursiveRemove
virtual void RecursiveRemove(TObject *obj)
Remove object from this collection and recursively remove the object from all other objects (and coll...
Definition: TList.cxx:763
TListIter::operator=
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
Definition: TList.cxx:1076
TListIter::TListIter
TListIter()
Definition: TList.h:211
R__COLLECTION_ITER_GUARD
#define R__COLLECTION_ITER_GUARD(collection)
Definition: TCollection.h:127
TList
Definition: TList.h:44
int
Error
void Error(const char *location, const char *msgfmt,...)
Use this function in case an error occurred.
Definition: TError.cxx:188