Logo ROOT  
Reference Guide
 
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
194void TList::AddBefore(const TObject *before, TObject *obj)
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
248void TList::AddAfter(const TObject *after, TObject *obj)
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:
548 TIter iRemDir(&removeDirectory);
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
612 TObjLink *lnk = FirstLink();
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
678 TObjLink *lnk = FirstLink();
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
721{
724
725 return new TListIter(this, dir);
726}
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();
777 if (ob && !ROOT::Detail::HasBeenDeleted(ob)) {
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();
788 if (ob && !ROOT::Detail::HasBeenDeleted(ob)) {
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
1033void TList::InsertAfter(const TObjLinkPtr_t &newlink, const TObjLinkPtr_t &prev)
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*/
1045
1047
1048////////////////////////////////////////////////////////////////////////////////
1049/// Create a new list iterator. By default the iteration direction
1050/// is kIterForward. To go backward use kIterBackward.
1051
1053 : fList(l), fCurCursor(nullptr), fCursor(nullptr), fDirection(dir), fStarted(kFALSE)
1054{
1056}
1057
1058////////////////////////////////////////////////////////////////////////////////
1059/// Copy ctor.
1060
1062{
1064
1065 fList = iter.fList;
1066 fCurCursor = iter.fCurCursor;
1067 fCursor = iter.fCursor;
1068 fDirection = iter.fDirection;
1069 fStarted = iter.fStarted;
1070}
1071
1072////////////////////////////////////////////////////////////////////////////////
1073/// Overridden assignment operator.
1074
1076{
1077
1078 const TListIter *rhs1 = dynamic_cast<const TListIter *>(&rhs);
1079 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) {
1097 fList = rhs.fList;
1098 fCurCursor = rhs.fCurCursor;
1099 fCursor = rhs.fCursor;
1100 fDirection = rhs.fDirection;
1101 fStarted = rhs.fStarted;
1102 }
1103 return *this;
1104}
1105
1106////////////////////////////////////////////////////////////////////////////////
1107/// Return next object in the list. Returns 0 when no more objects in list.
1108
1110{
1111 if (!fList) return nullptr;
1112
1114
1115 if (fDirection == kIterForward) {
1116 if (!fStarted) {
1117 fCursor = fList->fFirst;
1118 fStarted = kTRUE;
1119 }
1121 if (fCursor) {
1122 auto next = fCursor = fCursor->NextSP();
1123 }
1124 } else {
1125 if (!fStarted) {
1126 fCursor = fList->fLast;
1127 fStarted = kTRUE;
1128 }
1130 if (fCursor) fCursor = fCursor->PrevSP();
1131 }
1132
1133 if (fCurCursor) return fCurCursor->GetObject();
1134 return nullptr;
1135}
1136
1137////////////////////////////////////////////////////////////////////////////////
1138/// Returns the object option stored in the list.
1139
1141{
1142 if (fCurCursor) return fCurCursor->GetOption();
1143 return "";
1144}
1145
1146////////////////////////////////////////////////////////////////////////////////
1147/// Sets the object option stored in the list.
1148
1150{
1151 if (fCurCursor) fCurCursor->SetOption(option);
1152}
1153
1154////////////////////////////////////////////////////////////////////////////////
1155/// Reset list iterator.
1156
1158{
1160 fStarted = kFALSE;
1161}
1162
1163////////////////////////////////////////////////////////////////////////////////
1164/// This operator compares two TIterator objects.
1165
1167{
1168 if (IsA() == aIter.IsA()) {
1169 // We compared equal only two iterator of the same type.
1170 // Since this is a function of TListIter, we consequently know that
1171 // both this and aIter are of type inheriting from TListIter.
1172 const TListIter &iter(dynamic_cast<const TListIter &>(aIter));
1173 return (fCurCursor != iter.fCurCursor);
1174 }
1175 return false; // for base class we don't implement a comparison
1176}
1177
1178////////////////////////////////////////////////////////////////////////////////
1179/// This operator compares two TListIter objects.
1180
1182{
1183 return (fCurCursor != aIter.fCurCursor);
1184}
1185
1186////////////////////////////////////////////////////////////////////////////////
1187/// Stream all objects in the collection to or from the I/O buffer.
1188
1190{
1192
1193 Int_t nobjects;
1194 UChar_t nch;
1195 Int_t nbig;
1196 TObject *obj;
1197 UInt_t R__s, R__c;
1198
1199 if (b.IsReading()) {
1200 Clear(); // Get rid of old data if any.
1201 Version_t v = b.ReadVersion(&R__s, &R__c);
1202 if (v > 3) {
1204 fName.Streamer(b);
1205 b >> nobjects;
1206 std::string readOption;
1207 for (Int_t i = 0; i < nobjects; i++) {
1208 b >> obj;
1209 b >> nch;
1210 if (v > 4 && nch == 255) {
1211 b >> nbig;
1212 } else {
1213 nbig = nch;
1214 }
1215 readOption.resize(nbig,'\0');
1216 b.ReadFastArray((char*) readOption.data(),nbig);
1217 if (obj) { // obj can be null if the class had a custom streamer and we do not have the shared library nor a streamerInfo.
1218 if (nch) {
1219 Add(obj,readOption.c_str());
1220 } else {
1221 Add(obj);
1222 }
1223 }
1224 }
1225 b.CheckByteCount(R__s, R__c,TList::IsA());
1226 return;
1227 }
1228
1229 // process old versions when TList::Streamer was in TCollection::Streamer
1230 if (v > 2)
1232 if (v > 1)
1233 fName.Streamer(b);
1234 b >> nobjects;
1235 for (Int_t i = 0; i < nobjects; i++) {
1236 b >> obj;
1237 Add(obj);
1238 }
1239 b.CheckByteCount(R__s, R__c,TList::IsA());
1240
1241 } else {
1243
1244 R__c = b.WriteVersion(TList::IsA(), kTRUE);
1246 fName.Streamer(b);
1247 nobjects = GetSize();
1248 b << nobjects;
1249
1250 TObjLink *lnk = fFirst.get();
1251 while (lnk) {
1252 obj = lnk->GetObject();
1253 b << obj;
1254
1255 nbig = strlen(lnk->GetAddOption());
1256 if (nbig > 254) {
1257 nch = 255;
1258 b << nch;
1259 b << nbig;
1260 } else {
1261 nch = UChar_t(nbig);
1262 b << nch;
1263 }
1264 b.WriteFastArray(lnk->GetAddOption(),nbig);
1265
1266 lnk = lnk->Next();
1267 }
1268 b.SetByteCount(R__c, kTRUE);
1269 }
1270}
#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:382
#define R__COLLECTION_READ_LOCKGUARD(mutex)
#define R__COLLECTION_WRITE_GUARD()
#define R__COLLECTION_READ_GUARD()
const Bool_t kIterForward
Definition TCollection.h:42
#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
ROOT::DirAutoAdd_t GetDirectoryAutoAdd() const
Return the wrapper around the directory auto add function.
Definition TClass.cxx:7556
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
virtual TClass * IsA() const
Definition TIterator.h:48
Iterator of linked list.
Definition TList.h:191
Option_t * GetOption() const override
Returns the object option stored in the list.
Definition TList.cxx:1140
void Reset() override
Reset list iterator.
Definition TList.cxx:1157
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:1109
TListIter()
Definition TList.h:202
TIterator & operator=(const TIterator &rhs) override
Overridden assignment operator.
Definition TList.cxx:1075
void SetOption(Option_t *option)
Sets the object option stored in the list.
Definition TList.cxx:1149
Bool_t fStarted
Definition TList.h:200
Bool_t operator!=(const TIterator &aIter) const override
This operator compares two TIterator objects.
Definition TList.cxx:1166
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:1189
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 Bool_t IsEqual(const TObject *obj) const
Default equal comparison (objects are equal if they have the same address in memory).
Definition TObject.cxx:582
virtual void RecursiveRemove(TObject *obj)
Recursively remove this object from a list.
Definition TObject.cxx:677
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
virtual TClass * IsA() const
Definition TObject.h:243
@ 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