Logo ROOT  
Reference Guide
 
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
Loading...
Searching...
No Matches
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(TObject *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
85
86////////////////////////////////////////////////////////////////////////////////
87/// Delete the list. Objects are not deleted unless the TList is the
88/// owner (set via SetOwner()).
89
91{
92 Clear();
93}
94
95////////////////////////////////////////////////////////////////////////////////
96/// Add object at the beginning of the list.
97
99{
101
102 if (IsArgNull("AddFirst", obj)) return;
103
105
106 if (!fFirst) {
107 fFirst = NewLink(obj);
108 fLast = fFirst;
109 } else {
110 auto t = NewLink(obj);
111 t->fNext = fFirst;
112 fFirst->fPrev = t;
113 fFirst = t;
114 }
115 fSize++;
116 Changed();
117}
118
119////////////////////////////////////////////////////////////////////////////////
120/// Add object at the beginning of the list and also store option.
121/// Storing an option is useful when one wants to change the behaviour
122/// of an object a little without having to create a complete new
123/// copy of the object. This feature is used, for example, by the Draw()
124/// method. It allows the same object to be drawn in different ways.
125
127{
129
130 if (IsArgNull("AddFirst", obj)) return;
131
133
134 if (!fFirst) {
135 fFirst = NewOptLink(obj, opt);
136 fLast = fFirst;
137 } else {
138 auto t = NewOptLink(obj, opt);
139 t->fNext = fFirst;
140 fFirst->fPrev = t;
141 fFirst = t;
142 }
143 fSize++;
144 Changed();
145}
146
147////////////////////////////////////////////////////////////////////////////////
148/// Add object at the end of the list.
149
151{
153
154 if (IsArgNull("AddLast", obj)) return;
155
157
158 if (!fFirst) {
159 fFirst = NewLink(obj);
160 fLast = fFirst;
161 } else
162 fLast = NewLink(obj, fLast);
163 fSize++;
164 Changed();
165}
166
167////////////////////////////////////////////////////////////////////////////////
168/// Add object at the end of the list and also store option.
169/// Storing an option is useful when one wants to change the behaviour
170/// of an object a little without having to create a complete new
171/// copy of the object. This feature is used, for example, by the Draw()
172/// method. It allows the same object to be drawn in different ways.
173
175{
177
178 if (IsArgNull("AddLast", obj)) return;
179
181
182 if (!fFirst) {
183 fFirst = NewOptLink(obj, opt);
184 fLast = fFirst;
185 } else
186 fLast = NewOptLink(obj, opt, fLast);
187 fSize++;
188 Changed();
189}
190
191////////////////////////////////////////////////////////////////////////////////
192/// Insert object before object before in the list.
193
195{
197
198 if (IsArgNull("AddBefore", obj)) return;
199
201
202 if (!before)
203 TList::AddFirst(obj);
204 else {
205 Int_t idx;
206 TObjLink *t = FindLink(before, idx);
207 if (!t) {
208 Error("AddBefore", "before not found, object not added");
209 return;
210 }
211 if (t == fFirst.get())
212 TList::AddFirst(obj);
213 else {
214 NewLink(obj, t->fPrev.lock());
215 fSize++;
218 }
219}
220
221////////////////////////////////////////////////////////////////////////////////
222/// Insert object before the specified ObjLink object. If before = 0 then add
223/// to the head of the list. An ObjLink can be obtained by looping over a list
224/// using the above describe iterator method 3.
225
227{
229
230 if (IsArgNull("AddBefore", obj)) return;
231
232 if (!before)
233 TList::AddFirst(obj);
234 else {
235 if (before == fFirst.get())
236 TList::AddFirst(obj);
237 else {
238 NewLink(obj, before->fPrev.lock());
239 fSize++;
240 Changed();
241 }
242 }
243}
244
245////////////////////////////////////////////////////////////////////////////////
246/// Insert object after object after in the list.
247
249{
251
252 if (IsArgNull("AddAfter", obj)) return;
253
255
256 if (!after)
257 TList::AddLast(obj);
258 else {
259 Int_t idx;
260 TObjLink *t = FindLink(after, idx);
261 if (!t) {
262 Error("AddAfter", "after not found, object not added");
263 return;
264 }
265 if (t == fLast.get())
266 TList::AddLast(obj);
267 else {
268 NewLink(obj, t->shared_from_this());
269 fSize++;
270 Changed();
271 }
272 }
273}
274
275////////////////////////////////////////////////////////////////////////////////
276/// Insert object after the specified ObjLink object. If after = 0 then add
277/// to the tail of the list. An ObjLink can be obtained by looping over a list
278/// using the above describe iterator method 3.
279
281{
283
284 if (IsArgNull("AddAfter", obj)) return;
285
287
288 if (!after)
289 TList::AddLast(obj);
290 else {
291 if (after == fLast.get())
292 TList::AddLast(obj);
293 else {
294 NewLink(obj, after->shared_from_this());
295 fSize++;
296 Changed();
297 }
298 }
299}
300
301////////////////////////////////////////////////////////////////////////////////
302/// Insert object at position idx in the list.
303
305{
307
308 if (IsArgNull("AddAt", obj)) return;
309
311
312 TObjLink *lnk = LinkAt(idx);
313 if (!lnk)
314 TList::AddLast(obj);
315 else if (lnk == fFirst.get())
316 TList::AddFirst(obj);
317 else {
318 NewLink(obj, lnk->fPrev.lock());
319 fSize++;
320 Changed();
321 }
322}
323
324////////////////////////////////////////////////////////////////////////////////
325/// Returns the object after object obj. Obj is found using the
326/// object's IsEqual() method. Returns 0 if obj is last in list.
327
328TObject *TList::After(const TObject *obj) const
329{
331
332 TObjLink *t;
333
335
336 auto cached = fCache.lock();
337 if (cached.get() && cached->GetObject() && cached->GetObject()->IsEqual(obj)) {
338 t = cached.get();
339 ((TList*)this)->fCache = cached->fNext; //cast const away, fCache should be mutable
340 } else {
341 Int_t idx;
342 t = FindLink(obj, idx);
343 if (t) ((TList*)this)->fCache = t->fNext;
344 }
345
346 if (t && t->Next())
347 return t->Next()->GetObject();
348 else
349 return nullptr;
350}
351
352////////////////////////////////////////////////////////////////////////////////
353/// Returns the object at position idx. Returns 0 if idx is out of range.
354
356{
359
360 TObjLink *lnk = LinkAt(idx);
361 if (lnk) return lnk->GetObject();
362 return nullptr;
363}
364
365////////////////////////////////////////////////////////////////////////////////
366/// Returns the object before object obj. Obj is found using the
367/// object's IsEqual() method. Returns 0 if obj is first in list.
368
369TObject *TList::Before(const TObject *obj) const
370{
373
374 TObjLink *t;
375
376 auto cached = fCache.lock();
377 if (cached.get() && cached->GetObject() && cached->GetObject()->IsEqual(obj)) {
378 t = cached.get();
379 ((TList*)this)->fCache = cached->fPrev; //cast const away, fCache should be mutable
380 } else {
381 Int_t idx;
382 t = FindLink(obj, idx);
383 if (t) ((TList*)this)->fCache = t->fPrev;
384 }
385
386 if (t && t->Prev())
387 return t->Prev()->GetObject();
388 else
389 return nullptr;
390}
391
392////////////////////////////////////////////////////////////////////////////////
393/// Remove all objects from the list. Does not delete the objects
394/// unless the TList is the owner (set via SetOwner()) and option
395/// "nodelete" is not set.
396/// If option="nodelete" then don't delete any heap objects that were
397/// marked with the kCanDelete bit, otherwise these objects will be
398/// deleted (this option is used by THashTable::Clear()).
399
401{
404
405 Bool_t nodel = option ? (!strcmp(option, "nodelete") ? kTRUE : kFALSE) : kFALSE;
406
407 if (!nodel && IsOwner()) {
408 Delete(option);
409 return;
410 }
411
412 // In some case, for example TParallelCoord, a list (the pad's list of
413 // primitives) will contain both the container and the containees
414 // (the TParallelCoordVar) but if the Clear is being called from
415 // the destructor of the container of this list, one of the first
416 // thing done will be the remove the container (the pad) for the
417 // list (of Primitives of the canvas) that was connecting it
418 // (indirectly) to the list of cleanups.
419 // Note: The Code in TParallelCoordVar was changed (circa June 2017),
420 // to no longer have this behavior and thus rely on this code (by moving
421 // from using Draw to Paint) but the structure might still exist elsewhere
422 // so we keep this comment here.
423
424 // To preserve this connection (without introducing one when there was none),
425 // we re-use fCache to inform RecursiveRemove of the node currently
426 // being cleared/deleted.
427 while (fFirst) {
428 auto tlk = fFirst;
429 fFirst = fFirst->fNext;
430 fSize--;
431
432
433 // Make node available to RecursiveRemove
434 tlk->fNext.reset();
435 tlk->fPrev.reset();
436 fCache = tlk;
437
438 // delete only heap objects marked OK to clear
439 auto obj = tlk->GetObject();
440 if (!nodel && obj) {
442 Error("Clear", "A list is accessing an object (%p) already deleted (list name = %s)",
443 obj, GetName());
444 } else if (obj->IsOnHeap()) {
445 if (obj->TestBit(kCanDelete)) {
448 }
449 }
450 }
451 }
452 // delete tlk;
453 }
454 fFirst.reset();
455 fLast.reset();
456 fCache.reset();
457 fSize = 0;
458 Changed();
459}
460
461////////////////////////////////////////////////////////////////////////////////
462/// Remove all objects from the list AND delete all heap based objects.
463/// If option="slow" then keep list consistent during delete. This allows
464/// recursive list operations during the delete (e.g. during the dtor
465/// of an object in this list one can still access the list to search for
466/// other not yet deleted objects).
467
469{
472
473 Bool_t slow = option ? (!strcmp(option, "slow") ? kTRUE : kFALSE) : kFALSE;
474
475 TList removeDirectory; // need to deregister these from their directory
476
477 if (slow) {
478
479 // In some case, for example TParallelCoord, a list (the pad's list of
480 // primitives) will contain both the container and the containees
481 // (the TParallelCoorVar) but if the Clear is being called from
482 // the destructor of the container of this list, one of the first
483 // thing done will be the remove the container (the pad) for the
484 // list (of Primitives of the canvas) that was connecting it
485 // (indirectly) to the list of cleanups.
486
487 // To preserve this connection (without introducing one when there was none),
488 // we re-use fCache to inform RecursiveRemove of the node currently
489 // being cleared/deleted.
490 while (fFirst) {
491 auto tlk = fFirst;
492 fFirst = fFirst->fNext;
493 fSize--;
494
495 // Make node available to RecursiveRemove
496 tlk->fNext.reset();
497 tlk->fPrev.reset();
498 fCache = tlk;
499
500 // delete only heap objects
501 auto obj = tlk->GetObject();
502 if (obj && ROOT::Detail::HasBeenDeleted(obj))
503 Error("Delete", "A list is accessing an object (%p) already deleted (list name = %s)",
504 obj, GetName());
505 else if (obj && obj->IsOnHeap())
507 else if (obj && obj->IsA()->GetDirectoryAutoAdd())
508 removeDirectory.Add(obj);
509
510 // delete tlk;
511 }
512
513 fFirst.reset();
514 fLast.reset();
515 fCache.reset();
516 fSize = 0;
517
518 } else {
519
520 auto first = fFirst; //pointer to first entry in linked list
521 fFirst.reset();
522 fLast.reset();
523 fCache.reset();
524 fSize = 0;
525 while (first) {
526 auto tlk = first;
527 first = first->fNext;
528 // delete only heap objects
529 auto obj = tlk->GetObject();
530 tlk->SetObject(nullptr);
531 if (obj && ROOT::Detail::HasBeenDeleted(obj))
532 Error("Delete", "A list is accessing an object (%p) already deleted (list name = %s)",
533 obj, GetName());
534 else if (obj && obj->IsOnHeap())
536 else if (obj && obj->IsA()->GetDirectoryAutoAdd())
537 removeDirectory.Add(obj);
538
539 // The formerly first token, when tlk goes out of scope has no more references
540 // because of the fFirst.reset()
541 }
542 }
543
544 // These objects cannot expect to have a valid TDirectory anymore;
545 // e.g. because *this is the TDirectory's list of objects. Even if
546 // not, they are supposed to be deleted, so we can as well unregister
547 // them from their directory, even if they are stack-based:
549 TObject* dirRem = nullptr;
550 while ((dirRem = iRemDir())) {
551 (*dirRem->IsA()->GetDirectoryAutoAdd())(dirRem, nullptr);
552 }
553 Changed();
554}
555
556#if 0
557////////////////////////////////////////////////////////////////////////////////
558/// Delete a TObjLink object.
559
560void TList::DeleteLink(TObjLink *lnk)
561{
563
564 lnk->fNext = lnk->fPrev = 0;
565 lnk->fObject = 0;
566 delete lnk;
567}
568#endif
569
570////////////////////////////////////////////////////////////////////////////////
571/// Find an object in this list using its name. Requires a sequential
572/// scan till the object has been found. Returns 0 if object with specified
573/// name is not found. This method overrides the generic FindObject()
574/// of TCollection for efficiency reasons.
575
576TObject *TList::FindObject(const char *name) const
577{
579
580 if (!name)
581 return nullptr;
582
584
585 for (TObjLink *lnk = FirstLink(); lnk != nullptr; lnk = lnk->Next()) {
586 if (TObject *obj = lnk->GetObject()) {
587 const char *objname = obj->GetName();
588 if (objname && strcmp(name, objname) == 0)
589 return obj;
590 }
591 }
592
593 return nullptr;
594}
595
596////////////////////////////////////////////////////////////////////////////////
597/// Find an object in this list using the object's IsEqual()
598/// member function. Requires a sequential scan till the object has
599/// been found. Returns 0 if object is not found.
600/// This method overrides the generic FindObject() of TCollection for
601/// efficiency reasons.
602
604{
606
607 if (!obj)
608 return nullptr;
609
611
613
614 while (lnk) {
615 TObject *ob = lnk->GetObject();
616 if (ob->IsEqual(obj)) return ob;
617 lnk = lnk->Next();
618 }
619 return nullptr;
620}
621
622////////////////////////////////////////////////////////////////////////////////
623/// Returns the TObjLink object that contains object obj. In idx it returns
624/// the position of the object in the list.
625
626TObjLink *TList::FindLink(const TObject *obj, Int_t &idx) const
627{
629
630 if (!obj)
631 return nullptr;
632
634
635 if (!fFirst) return nullptr;
636
638 TObjLink *lnk = fFirst.get();
639 idx = 0;
640
641 while (lnk) {
642 object = lnk->GetObject();
643 if (object) {
644 if (!ROOT::Detail::HasBeenDeleted(object)) {
645 if (object->IsEqual(obj)) return lnk;
646 }
647 }
648 lnk = lnk->Next();
649 idx++;
650 }
651 return nullptr;
652}
653
654////////////////////////////////////////////////////////////////////////////////
655/// Return the first object in the list. Returns 0 when list is empty.
656
658{
661
662 if (fFirst) return fFirst->GetObject();
663 return nullptr;
664}
665
666////////////////////////////////////////////////////////////////////////////////
667/// Return address of pointer to obj
668
670{
672
673 if (!obj)
674 return nullptr;
675
677
679
680 while (lnk) {
681 TObject *ob = lnk->GetObject();
682 if (ob->IsEqual(obj)) return lnk->GetObjectRef();
683 lnk = lnk->Next();
684 }
685 return nullptr;
686}
687
688////////////////////////////////////////////////////////////////////////////////
689/// Return the last object in the list. Returns 0 when list is empty.
690
692{
695
696 if (fLast) return fLast->GetObject();
697 return nullptr;
698}
699
700////////////////////////////////////////////////////////////////////////////////
701/// Return the TObjLink object at index idx.
702
704{
707
708 Int_t i = 0;
709 TObjLink *lnk = fFirst.get();
710 while (i < idx && lnk) {
711 i++;
712 lnk = lnk->Next();
713 }
714 return lnk;
715}
716
717////////////////////////////////////////////////////////////////////////////////
718/// Return a list iterator.
719
727
728////////////////////////////////////////////////////////////////////////////////
729/// Return a new TObjLink.
730
732{
735
736 auto newlink = std::make_shared<TObjLink>(obj);
737 if (prev) {
738 InsertAfter(newlink, prev);
739 }
740 return newlink;
741}
742
743////////////////////////////////////////////////////////////////////////////////
744/// Return a new TObjOptLink (a TObjLink that also stores the option).
745
747{
750
751 auto newlink = std::make_shared<TObjOptLink>(obj, opt);
752 if (prev) {
753 InsertAfter(newlink, prev);
754 }
755 return newlink;
756}
757
758////////////////////////////////////////////////////////////////////////////////
759/// Remove object from this collection and recursively remove the object
760/// from all other objects (and collections).
761
763{
764 // Note, we can assume that the Collection Read lock is held, see
765 // THashList::RecursiveRemove for a more complete discussion.
766 if (!obj || (fSize == 0 && fCache.expired()))
767 return;
768
770
771 // When fCache is set and has no previous and next node, it represents
772 // the node being cleared and/or deleted.
773 {
774 auto cached = fCache.lock();
775 if (cached && cached->fNext.get() == nullptr && cached->fPrev.lock().get() == nullptr) {
776 TObject *ob = cached->GetObject();
778 ob->RecursiveRemove(obj);
779 }
780 }
781 }
782
783 auto lnk = fFirst;
784 decltype(lnk) next;
785 while (lnk.get()) {
786 next = lnk->fNext;
787 TObject *ob = lnk->GetObject();
789 if (ob->IsEqual(obj)) {
790 lnk->SetObject(nullptr);
791 if (lnk == fFirst) {
792 fFirst = next;
793 if (lnk == fLast)
794 fLast = fFirst;
795 else
796 fFirst->fPrev.reset();
797 // DeleteLink(lnk);
798 } else if (lnk == fLast) {
799 fLast = lnk->fPrev.lock();
800 fLast->fNext.reset();
801 // DeleteLink(lnk);
802 } else {
803 lnk->Prev()->fNext = next;
804 lnk->Next()->fPrev = lnk->fPrev;
805 // DeleteLink(lnk);
806 }
807 fSize--;
808 fCache.reset();
809 Changed();
810 } else
811 ob->RecursiveRemove(obj);
812 }
813 lnk = next;
814 }
815}
816
817////////////////////////////////////////////////////////////////////////////////
818/// Remove object from the list.
819
821{
823
824 if (!obj) return nullptr;
825
826 Int_t idx;
827 TObjLink *lnk = FindLink(obj, idx);
828
829 if (!lnk) return nullptr;
830
831 // return object found, which may be (pointer wise) different than the
832 // input object (depending on what IsEqual() is doing)
833
835
836 TObject *ob = lnk->GetObject();
837 lnk->SetObject(nullptr);
838 if (lnk == fFirst.get()) {
839 fFirst = lnk->fNext;
840 // lnk is still alive as we have either fLast
841 // or the 'new' fFirst->fPrev pointing to it.
842 if (lnk == fLast.get()) {
843 fLast.reset();
844 fFirst.reset();
845 } else
846 fFirst->fPrev.reset();
847 //DeleteLink(lnk);
848 } else if (lnk == fLast.get()) {
849 fLast = lnk->fPrev.lock();
850 fLast->fNext.reset();
851 //DeleteLink(lnk);
852 } else {
853 lnk->Next()->fPrev = lnk->fPrev;
854 lnk->Prev()->fNext = lnk->fNext;
855 //DeleteLink(lnk);
856 }
857 fSize--;
858 fCache.reset();
859 Changed();
860
861 return ob;
862}
863
864////////////////////////////////////////////////////////////////////////////////
865/// Remove object link (and therefore the object it contains)
866/// from the list.
867
869{
871
872 if (!lnk) return nullptr;
873
875
876 TObject *obj = lnk->GetObject();
877 lnk->SetObject(nullptr);
878 if (lnk == fFirst.get()) {
879 fFirst = lnk->fNext;
880 // lnk is still alive as we have either fLast
881 // or the 'new' fFirst->fPrev pointing to it.
882 if (lnk == fLast.get()) {
883 fLast.reset();
884 fFirst.reset();
885 } else
886 fFirst->fPrev.reset();
887 // DeleteLink(lnk);
888 } else if (lnk == fLast.get()) {
889 fLast = lnk->fPrev.lock();
890 fLast->fNext.reset();
891 // DeleteLink(lnk);
892 } else {
893 lnk->Next()->fPrev = lnk->fPrev;
894 lnk->Prev()->fNext = lnk->fNext;
895 // DeleteLink(lnk);
896 }
897 fSize--;
898 fCache.reset();
899 Changed();
900
901 return obj;
902}
903
904////////////////////////////////////////////////////////////////////////////////
905/// Remove the last object of the list.
906
908{
911
912 TObjLink *lnk = fLast.get();
913 if (!lnk) return;
914
915 lnk->SetObject(nullptr);
916 if (lnk == fFirst.get()) {
917 fFirst.reset();
918 fLast.reset();
919 } else {
920 fLast = lnk->fPrev.lock();
921 fLast->fNext.reset();
922 }
923 // DeleteLink(lnk);
924
925 fSize--;
926 fCache.reset();
927 Changed();
928}
929
930////////////////////////////////////////////////////////////////////////////////
931/// Sort linked list. Real sorting is done in private function DoSort().
932/// The list can only be sorted when is contains objects of a sortable
933/// class.
934
936{
939
940 if (!fFirst) return;
941
942 fAscending = order;
943
944 if (!fFirst->GetObject()->IsSortable()) {
945 Error("Sort", "objects in list are not sortable");
946 return;
947 }
948
950
951 // correct back links
952 std::shared_ptr<TObjLink> ol, lnk = fFirst;
953
954 if (lnk.get()) lnk->fPrev.reset();
955 while ((ol = lnk)) {
956 lnk = lnk->fNext;
957 if (lnk)
958 lnk->fPrev = ol;
959 else
960 fLast = ol;
961 }
962 fSorted = kTRUE;
963}
964
965////////////////////////////////////////////////////////////////////////////////
966/// Compares the objects stored in the TObjLink objects.
967/// Depending on the flag IsAscending() the function returns
968/// true if the object in l1 <= l2 (ascending) or l2 <= l1 (descending).
969
971{
972 Int_t cmp = l1->GetObject()->Compare(l2->GetObject());
973
974 if ((IsAscending() && cmp <=0) || (!IsAscending() && cmp > 0))
975 return kTRUE;
976 return kFALSE;
977}
978
979////////////////////////////////////////////////////////////////////////////////
980/// Sort linked list.
981
982std::shared_ptr<TObjLink> *TList::DoSort(std::shared_ptr<TObjLink> *head, Int_t n)
983{
986
987 std::shared_ptr<TObjLink> p1, p2, *h2, *t2;
988
989 switch (n) {
990 case 0:
991 return head;
992
993 case 1:
994 return &((*head)->fNext);
995
996 case 2:
997 p2 = (p1 = *head)->fNext;
998 if (LnkCompare(p1, p2)) return &(p2->fNext);
999 p1->fNext = (*head = p2)->fNext;
1000 return &((p2->fNext = p1)->fNext);
1001 }
1002
1003 int m;
1004 n -= m = n / 2;
1005
1006 t2 = DoSort(h2 = DoSort(head, n), m);
1007
1008 if (LnkCompare((p1 = *head), (p2 = *h2))) {
1009 do {
1010 if (!--n) return *h2 = p2, t2;
1011 } while (LnkCompare((p1 = *(head = &(p1->fNext))), p2));
1012 }
1013
1014 while (1) {
1015 *head = p2;
1016 do {
1017 if (!--m) return *h2 = *t2, *t2 = p1, h2;
1018 } while (!LnkCompare(p1, (p2 = *(head = &(p2->fNext)))));
1019 *head = p1;
1020 do {
1021 if (!--n) return *h2 = p2, t2;
1022 } while (LnkCompare((p1 = *(head = &(p1->fNext))), p2));
1023 }
1024}
1025
1026/** \class TObjLink
1027Wrapper around a TObject so it can be stored in a TList.
1028*/
1029
1030////////////////////////////////////////////////////////////////////////////////
1031/// Insert a new link in the chain.
1032
1034{
1035 newlink->fNext = prev->fNext;
1036 newlink->fPrev = prev;
1037 prev->fNext = newlink;
1038 if (newlink->fNext)
1039 newlink->fNext->fPrev = newlink;
1040}
1041
1042/** \class TListIter
1043Iterator of linked list.
1044\see TList documentation for examples on how to loop with this
1045iterator, and TCollection documentation for more modern alternatives
1046that dynamically cast the derived class.
1047*/
1048
1050
1051////////////////////////////////////////////////////////////////////////////////
1052/// Create a new list iterator. By default the iteration direction
1053/// is kIterForward. To go backward use kIterBackward.
1054
1056 : fList(l), fCurCursor(nullptr), fCursor(nullptr), fDirection(dir), fStarted(kFALSE)
1057{
1059}
1060
1061////////////////////////////////////////////////////////////////////////////////
1062/// Copy ctor.
1063
1065{
1067
1068 fList = iter.fList;
1069 fCurCursor = iter.fCurCursor;
1070 fCursor = iter.fCursor;
1071 fDirection = iter.fDirection;
1072 fStarted = iter.fStarted;
1073}
1074
1075////////////////////////////////////////////////////////////////////////////////
1076/// Overridden assignment operator.
1077
1079{
1080
1081 const TListIter *rhs1 = dynamic_cast<const TListIter *>(&rhs);
1082 if (this != &rhs && rhs1) {
1084 fList = rhs1->fList;
1085 fCurCursor = rhs1->fCurCursor;
1086 fCursor = rhs1->fCursor;
1087 fDirection = rhs1->fDirection;
1088 fStarted = rhs1->fStarted;
1089 }
1090 return *this;
1091}
1092
1093////////////////////////////////////////////////////////////////////////////////
1094/// Overloaded assignment operator.
1095
1097{
1098 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 nullptr;
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 nullptr;
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
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
1193{
1195
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) {
1207 fName.Streamer(b);
1208 b >> nobjects;
1209 std::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)
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);
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
short Version_t
Definition RtypesCore.h:65
unsigned char UChar_t
Definition RtypesCore.h:38
constexpr Bool_t kFALSE
Definition RtypesCore.h:94
constexpr Bool_t kTRUE
Definition RtypesCore.h:93
const char Option_t
Definition RtypesCore.h:66
#define ClassImp(name)
Definition Rtypes.h:374
#define R__COLLECTION_READ_LOCKGUARD(mutex)
#define R__COLLECTION_WRITE_GUARD()
#define R__COLLECTION_READ_GUARD()
const Bool_t kIterForward
Definition TCollection.h:42
ROOT::Detail::TRangeCast< T, true > TRangeDynCast
TRangeDynCast is an adapter class that allows the typed iteration through a TCollection.
#define R__COLLECTION_ITER_GUARD(collection)
#define R__COLLECTION_WRITE_LOCKGUARD(mutex)
Option_t Option_t option
char name[80]
Definition TGX11.cxx:110
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.
const char * GetName() const override
Return name of this collection.
TString fName
Bool_t IsOwner() const
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.
Iterator abstract base class.
Definition TIterator.h:30
Iterator of linked list.
Definition TList.h:191
Option_t * GetOption() const override
Returns the object option stored in the list.
Definition TList.cxx:1143
void Reset() override
Reset list iterator.
Definition TList.cxx:1160
const TList * fList
Definition TList.h:196
TObjLinkPtr_t fCursor
Definition TList.h:198
TObjLinkPtr_t fCurCursor
Definition TList.h:197
TObject * Next() override
Return next object in the list. Returns 0 when no more objects in list.
Definition TList.cxx:1112
TListIter()
Definition TList.h:202
TIterator & operator=(const TIterator &rhs) override
Overridden assignment operator.
Definition TList.cxx:1078
void SetOption(Option_t *option)
Sets the object option stored in the list.
Definition TList.cxx:1152
Bool_t fStarted
Definition TList.h:200
Bool_t operator!=(const TIterator &aIter) const override
This operator compares two TIterator objects.
Definition TList.cxx:1169
TClass * IsA() const override
Definition TList.h:228
Bool_t fDirection
Definition TList.h:199
A doubly linked list.
Definition TList.h:38
Bool_t LnkCompare(const TObjLinkPtr_t &l1, const TObjLinkPtr_t &l2)
Compares the objects stored in the TObjLink objects.
Definition TList.cxx:970
void Streamer(TBuffer &) override
Stream all objects in the collection to or from the I/O buffer.
Definition TList.cxx:1192
void AddAfter(const TObject *after, TObject *obj) override
Insert object after object after in the list.
Definition TList.cxx:248
TObject * After(const TObject *obj) const override
Returns the object after object obj.
Definition TList.cxx:328
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:746
void Clear(Option_t *option="") override
Remove all objects from the list.
Definition TList.cxx:400
TObject ** GetObjectRef(const TObject *obj) const override
Return address of pointer to obj.
Definition TList.cxx:669
virtual ~TList()
Delete the list.
Definition TList.cxx:90
Bool_t fAscending
cache to speedup sequential calling of Before() and After() functions
Definition TList.h:49
void AddAt(TObject *obj, Int_t idx) override
Insert object at position idx in the list.
Definition TList.cxx:304
friend class TListIter
Definition TList.h:40
TObject * Before(const TObject *obj) const override
Returns the object before object obj.
Definition TList.cxx:369
TObject * FindObject(const char *name) const override
Find an object in this list using its name.
Definition TList.cxx:576
void RecursiveRemove(TObject *obj) override
Remove object from this collection and recursively remove the object from all other objects (and coll...
Definition TList.cxx:762
TObjLink * FindLink(const TObject *obj, Int_t &idx) const
Returns the TObjLink object that contains object obj.
Definition TList.cxx:626
void Add(TObject *obj) override
Definition TList.h:81
TObject * Remove(TObject *obj) override
Remove object from the list.
Definition TList.cxx:820
void AddLast(TObject *obj) override
Add object at the end of the list.
Definition TList.cxx:150
TObject * Last() const override
Return the last object in the list. Returns 0 when list is empty.
Definition TList.cxx:691
Bool_t IsAscending()
Definition TList.h:108
std::shared_ptr< TObjLink > TObjLinkPtr_t
Definition TList.h:43
TObject * First() const override
Return the first object in the list. Returns 0 when list is empty.
Definition TList.cxx:657
TObjLinkPtr_t fLast
pointer to first entry in linked list
Definition TList.h:47
void InsertAfter(const TObjLinkPtr_t &newlink, const TObjLinkPtr_t &prev)
Insert a new link in the chain.
Definition TList.cxx:1033
TIterator * MakeIterator(Bool_t dir=kIterForward) const override
Return a list iterator.
Definition TList.cxx:720
void AddBefore(const TObject *before, TObject *obj) override
Insert object before object before in the list.
Definition TList.cxx:194
TObjLink * LinkAt(Int_t idx) const
sorting order (when calling Sort() or for TSortedList)
Definition TList.cxx:703
virtual TObjLink * FirstLink() const
Definition TList.h:102
TObjLinkPtr_t NewLink(TObject *obj, const TObjLinkPtr_t &prev=nullptr)
Return a new TObjLink.
Definition TList.cxx:731
TObjLinkPtr_t fFirst
Definition TList.h:46
void Delete(Option_t *option="") override
Remove all objects from the list AND delete all heap based objects.
Definition TList.cxx:468
TObjLinkWeakPtr_t fCache
pointer to last entry in linked list
Definition TList.h:48
TClass * IsA() const override
Definition TList.h:110
TObject * At(Int_t idx) const override
Returns the object at position idx. Returns 0 if idx is out of range.
Definition TList.cxx:355
void RemoveLast() override
Remove the last object of the list.
Definition TList.cxx:907
TObjLinkPtr_t * DoSort(TObjLinkPtr_t *head, Int_t n)
Sort linked list.
Definition TList.cxx:982
void AddFirst(TObject *obj) override
Add object at the beginning of the list.
Definition TList.cxx:98
virtual void Sort(Bool_t order=kSortAscending)
Sort linked list.
Definition TList.cxx:935
Mother of all ROOT objects.
Definition TObject.h:41
virtual void Streamer(TBuffer &)
Stream an object of class TObject.
Definition TObject.cxx:906
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition TObject.cxx:1005
@ kCanDelete
if object in a list can be deleted
Definition TObject.h:62
virtual void Changed()
virtual void Streamer(TBuffer &)
Stream a string object.
Definition TString.cxx:1412
const Int_t n
Definition legend1.C:16
R__ALWAYS_INLINE bool HasBeenDeleted(const TObject *obj)
Check if the TObject's memory has been deleted.
Definition TObject.h:402
R__EXTERN TVirtualRWMutex * gCoreMutex
TMarker m
Definition textangle.C:8
TLine l
Definition textangle.C:4