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