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