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
14A doubly linked list.
15
16All classes inheriting from TObject can be
17inserted in a TList. Before being inserted into the list the object
18pointer is wrapped in a TObjLink object which contains, besides
19the object pointer also a previous and next pointer.
20
21There are several ways to iterate over a TList; in order of preference, if
22not 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~~~
70Methods 2, 3 and 4 can also easily iterate backwards using either
71a backward TIter (using argument kIterBackward) or by using
72LastLink() 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
83using 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
195void 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();
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
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
249void 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
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
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
329TObject *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
370TObject *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
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
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
561void 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
577TObject *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
627TObjLink *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
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
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
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
983std::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
1028Wrapper around a TObject so it can be stored in a TList.
1029*/
1030
1031////////////////////////////////////////////////////////////////////////////////
1032/// Insert a new link in the chain.
1033
1034void 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
1044Iterator 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) {
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) {
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 }
1124 if (fCursor) {
1125 auto next = fCursor = fCursor->NextSP();
1126 }
1127 } else {
1128 if (!fStarted) {
1129 fCursor = fList->fLast;
1130 fStarted = kTRUE;
1131 }
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
1192void 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}
#define b(i)
Definition: RSha256.hxx:100
int Int_t
Definition: RtypesCore.h:43
short Version_t
Definition: RtypesCore.h:63
unsigned char UChar_t
Definition: RtypesCore.h:36
unsigned int UInt_t
Definition: RtypesCore.h:44
const Bool_t kFALSE
Definition: RtypesCore.h:90
bool Bool_t
Definition: RtypesCore.h:61
const Bool_t kTRUE
Definition: RtypesCore.h:89
const char Option_t
Definition: RtypesCore.h:64
#define ClassImp(name)
Definition: Rtypes.h:361
#define R__COLLECTION_READ_LOCKGUARD(mutex)
Definition: TCollection.h:435
#define R__COLLECTION_WRITE_GUARD()
Definition: TCollection.h:125
#define R__COLLECTION_READ_GUARD()
Definition: TCollection.h:126
const Bool_t kIterForward
Definition: TCollection.h:40
#define R__COLLECTION_ITER_GUARD(collection)
Definition: TCollection.h:127
#define R__COLLECTION_WRITE_LOCKGUARD(mutex)
Definition: TCollection.h:438
char name[80]
Definition: TGX11.cxx:109
Buffer base class used for serializing objects.
Definition: TBuffer.h:42
Bool_t IsArgNull(const char *where, const TObject *obj) const
Returns true if object is a null pointer.
virtual const char * GetName() const
Return name of this collection.
TString fName
Definition: TCollection.h:147
Bool_t IsOwner() const
Definition: TCollection.h:188
static void GarbageCollect(TObject *obj)
Add to the list of things to be cleaned up.
virtual Int_t GetSize() const
Return the capacity of the collection, i.e.
Definition: TCollection.h:182
Iterator abstract base class.
Definition: TIterator.h:30
virtual TIterator & operator=(const TIterator &)
Definition: TIterator.h:37
Iterator of linked list.
Definition: TList.h:200
TObject * Next()
Return next object in the list. Returns 0 when no more objects in list.
Definition: TList.cxx:1112
const TList * fList
Definition: TList.h:205
TObjLinkPtr_t fCursor
Definition: TList.h:207
TObjLinkPtr_t fCurCursor
Definition: TList.h:206
void Reset()
Reset list iterator.
Definition: TList.cxx:1160
TListIter()
Definition: TList.h:211
void SetOption(Option_t *option)
Sets the object option stored in the list.
Definition: TList.cxx:1152
Bool_t fStarted
Definition: TList.h:209
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
Definition: TList.cxx:1169
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
Definition: TList.cxx:1076
Option_t * GetOption() const
Returns the object option stored in the list.
Definition: TList.cxx:1143
Bool_t fDirection
Definition: TList.h:208
A doubly linked list.
Definition: TList.h:44
Bool_t LnkCompare(const TObjLinkPtr_t &l1, const TObjLinkPtr_t &l2)
Compares the objects stored in the TObjLink objects.
Definition: TList.cxx:971
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
virtual void Add(TObject *obj)
Definition: TList.h:87
virtual TObject * After(const TObject *obj) const
Returns the object after object obj.
Definition: TList.cxx:329
virtual ~TList()
Delete the list.
Definition: TList.cxx:91
Bool_t fAscending
cache to speedup sequential calling of Before() and After() functions
Definition: TList.h:55
virtual TObject * Remove(TObject *obj)
Remove object from the list.
Definition: TList.cxx:821
virtual TObject ** GetObjectRef(const TObject *obj) const
Return address of pointer to obj.
Definition: TList.cxx:670
friend class TListIter
Definition: TList.h:46
virtual void AddAt(TObject *obj, Int_t idx)
Insert object at position idx in the list.
Definition: TList.cxx:305
TObjLink * FindLink(const TObject *obj, Int_t &idx) const
Returns the TObjLink object that contains object obj.
Definition: TList.cxx:627
Bool_t IsAscending()
Definition: TList.h:114
std::shared_ptr< TObjLink > TObjLinkPtr_t
Definition: TList.h:49
virtual void AddFirst(TObject *obj)
Add object at the beginning of the list.
Definition: TList.cxx:99
TObjLinkPtr_t fLast
pointer to first entry in linked list
Definition: TList.h:53
void InsertAfter(const TObjLinkPtr_t &newlink, const TObjLinkPtr_t &prev)
Insert a new link in the chain.
Definition: TList.cxx:1034
virtual void RemoveLast()
Remove the last object of the list.
Definition: TList.cxx:908
virtual TObject * FindObject(const char *name) const
Find an object in this list using its name.
Definition: TList.cxx:577
TObjLink * LinkAt(Int_t idx) const
sorting order (when calling Sort() or for TSortedList)
Definition: TList.cxx:704
virtual TObjLink * FirstLink() const
Definition: TList.h:108
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
TObjLinkPtr_t NewLink(TObject *obj, const TObjLinkPtr_t &prev=nullptr)
Return a new TObjLink.
Definition: TList.cxx:732
virtual TObject * Last() const
Return the last object in the list. Returns 0 when list is empty.
Definition: TList.cxx:692
virtual void AddAfter(const TObject *after, TObject *obj)
Insert object after object after in the list.
Definition: TList.cxx:249
TObjLinkPtr_t fFirst
Definition: TList.h:52
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
virtual void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the list.
Definition: TList.cxx:195
virtual TIterator * MakeIterator(Bool_t dir=kIterForward) const
Return a list iterator.
Definition: TList.cxx:721
TObjLinkWeakPtr_t fCache
pointer to last entry in linked list
Definition: TList.h:54
virtual TObject * Before(const TObject *obj) const
Returns the object before object obj.
Definition: TList.cxx:370
virtual void Delete(Option_t *option="")
Remove all objects from the list AND delete all heap based objects.
Definition: TList.cxx:469
virtual TObject * First() const
Return the first object in the list. Returns 0 when list is empty.
Definition: TList.cxx:658
virtual void AddLast(TObject *obj)
Add object at the end of the list.
Definition: TList.cxx:151
TObjLinkPtr_t * DoSort(TObjLinkPtr_t *head, Int_t n)
Sort linked list.
Definition: TList.cxx:983
virtual void Clear(Option_t *option="")
Remove all objects from the list.
Definition: TList.cxx:401
virtual void Sort(Bool_t order=kSortAscending)
Sort linked list.
Definition: TList.cxx:936
Mother of all ROOT objects.
Definition: TObject.h:37
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:483
R__ALWAYS_INLINE Bool_t TestBit(UInt_t f) const
Definition: TObject.h:187
virtual void RecursiveRemove(TObject *obj)
Recursively remove this object from a list.
Definition: TObject.cxx:572
@ kNotDeleted
object has not been deleted
Definition: TObject.h:78
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition: TObject.cxx:891
@ kCanDelete
if object in a list can be deleted
Definition: TObject.h:58
virtual void Changed()
const Int_t n
Definition: legend1.C:16
R__EXTERN TVirtualRWMutex * gCoreMutex
Definition: first.py:1
auto * m
Definition: textangle.C:8
auto * l
Definition: textangle.C:4