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
14 A doubly linked list.
15 
16 All classes inheriting from TObject can be
17 inserted in a TList. Before being inserted into the list the object
18 pointer is wrapped in a TObjLink object which contains, besides
19 the object pointer also a previous and next pointer.
20 
21 There are several ways to iterate over a TList; in order of preference, if
22 not 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 ~~~
71 Methods 3, 4 and 5 can also easily iterate backwards using either
72 a backward TIter (using argument kIterBackward) or by using
73 LastLink() 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 
84 using 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 
196 void 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++;
218  Changed();
219  }
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 
228 void TList::AddBefore(TObjLink *before, TObject *obj)
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 
250 void 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 
282 void TList::AddAfter(TObjLink *after, TObject *obj)
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 
306 void TList::AddAt(TObject *obj, Int_t idx)
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 
330 TObject *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 
371 TObject *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 
402 void TList::Clear(Option_t *option)
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 
470 void TList::Delete(Option_t *option)
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 
562 void 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 
578 TObject *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 
628 TObjLink *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 
639  TObject *object;
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 
937 void TList::Sort(Bool_t order)
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 
951  DoSort(&fFirst, fSize);
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 
984 std::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
1029 Wrapper around a TObject so it can be stored in a TList.
1030 */
1031 
1032 ////////////////////////////////////////////////////////////////////////////////
1033 /// Insert a new link in the chain.
1034 
1035 void 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
1045 Iterator 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  TIterator::operator=(rhs);
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  TIterator::operator=(rhs);
1101  fList = rhs.fList;
1102  fCurCursor = rhs.fCurCursor;
1103  fCursor = rhs.fCursor;
1104  fDirection = rhs.fDirection;
1105  fStarted = rhs.fStarted;
1106  }
1107  return *this;
1108 }
1109 
1110 ////////////////////////////////////////////////////////////////////////////////
1111 /// Return next object in the list. Returns 0 when no more objects in list.
1112 
1114 {
1115  if (!fList) return 0;
1116 
1118 
1119  if (fDirection == kIterForward) {
1120  if (!fStarted) {
1121  fCursor = fList->fFirst;
1122  fStarted = kTRUE;
1123  }
1124  fCurCursor = fCursor;
1125  if (fCursor) {
1126  auto next = fCursor = fCursor->NextSP();
1127  }
1128  } else {
1129  if (!fStarted) {
1130  fCursor = fList->fLast;
1131  fStarted = kTRUE;
1132  }
1133  fCurCursor = fCursor;
1134  if (fCursor) fCursor = fCursor->PrevSP();
1135  }
1136 
1137  if (fCurCursor) return fCurCursor->GetObject();
1138  return 0;
1139 }
1140 
1141 ////////////////////////////////////////////////////////////////////////////////
1142 /// Returns the object option stored in the list.
1143 
1145 {
1146  if (fCurCursor) return fCurCursor->GetOption();
1147  return "";
1148 }
1149 
1150 ////////////////////////////////////////////////////////////////////////////////
1151 /// Sets the object option stored in the list.
1152 
1154 {
1155  if (fCurCursor) fCurCursor->SetOption(option);
1156 }
1157 
1158 ////////////////////////////////////////////////////////////////////////////////
1159 /// Reset list iterator.
1160 
1162 {
1164  fStarted = kFALSE;
1165 }
1166 
1167 ////////////////////////////////////////////////////////////////////////////////
1168 /// This operator compares two TIterator objects.
1169 
1171 {
1172  if (IsA() == aIter.IsA()) {
1173  // We compared equal only two iterator of the same type.
1174  // Since this is a function of TListIter, we consequently know that
1175  // both this and aIter are of type inheriting from TListIter.
1176  const TListIter &iter(dynamic_cast<const TListIter &>(aIter));
1177  return (fCurCursor != iter.fCurCursor);
1178  }
1179  return false; // for base class we don't implement a comparison
1180 }
1181 
1182 ////////////////////////////////////////////////////////////////////////////////
1183 /// This operator compares two TListIter objects.
1184 
1186 {
1187  return (fCurCursor != aIter.fCurCursor);
1188 }
1189 
1190 ////////////////////////////////////////////////////////////////////////////////
1191 /// Stream all objects in the collection to or from the I/O buffer.
1192 
1193 void TList::Streamer(TBuffer &b)
1194 {
1196 
1197  Int_t nobjects;
1198  UChar_t nch;
1199  Int_t nbig;
1200  TObject *obj;
1201  UInt_t R__s, R__c;
1202 
1203  if (b.IsReading()) {
1204  Clear(); // Get rid of old data if any.
1205  Version_t v = b.ReadVersion(&R__s, &R__c);
1206  if (v > 3) {
1207  TObject::Streamer(b);
1208  fName.Streamer(b);
1209  b >> nobjects;
1210  string readOption;
1211  for (Int_t i = 0; i < nobjects; i++) {
1212  b >> obj;
1213  b >> nch;
1214  if (v > 4 && nch == 255) {
1215  b >> nbig;
1216  } else {
1217  nbig = nch;
1218  }
1219  readOption.resize(nbig,'\0');
1220  b.ReadFastArray((char*) readOption.data(),nbig);
1221  if (obj) { // obj can be null if the class had a custom streamer and we do not have the shared library nor a streamerInfo.
1222  if (nch) {
1223  Add(obj,readOption.c_str());
1224  } else {
1225  Add(obj);
1226  }
1227  }
1228  }
1229  b.CheckByteCount(R__s, R__c,TList::IsA());
1230  return;
1231  }
1232 
1233  // process old versions when TList::Streamer was in TCollection::Streamer
1234  if (v > 2)
1235  TObject::Streamer(b);
1236  if (v > 1)
1237  fName.Streamer(b);
1238  b >> nobjects;
1239  for (Int_t i = 0; i < nobjects; i++) {
1240  b >> obj;
1241  Add(obj);
1242  }
1243  b.CheckByteCount(R__s, R__c,TList::IsA());
1244 
1245  } else {
1247 
1248  R__c = b.WriteVersion(TList::IsA(), kTRUE);
1249  TObject::Streamer(b);
1250  fName.Streamer(b);
1251  nobjects = GetSize();
1252  b << nobjects;
1253 
1254  TObjLink *lnk = fFirst.get();
1255  while (lnk) {
1256  obj = lnk->GetObject();
1257  b << obj;
1258 
1259  nbig = strlen(lnk->GetAddOption());
1260  if (nbig > 254) {
1261  nch = 255;
1262  b << nch;
1263  b << nbig;
1264  } else {
1265  nch = UChar_t(nbig);
1266  b << nch;
1267  }
1268  b.WriteFastArray(lnk->GetAddOption(),nbig);
1269 
1270  lnk = lnk->Next();
1271  }
1272  b.SetByteCount(R__c, kTRUE);
1273  }
1274 }
TListIter::fDirection
Bool_t fDirection
Definition: TList.h:208
l
auto * l
Definition: textangle.C:4
TList::AddAt
virtual void AddAt(TObject *obj, Int_t idx)
Insert object at position idx in the list.
Definition: TList.cxx:306
m
auto * m
Definition: textangle.C:8
R__COLLECTION_WRITE_LOCKGUARD
#define R__COLLECTION_WRITE_LOCKGUARD(mutex)
Definition: TCollection.h:438
n
const Int_t n
Definition: legend1.C:16
first
Definition: first.py:1
TList::InsertAfter
void InsertAfter(const TObjLinkPtr_t &newlink, const TObjLinkPtr_t &prev)
Insert a new link in the chain.
Definition: TList.cxx:1035
TList::GetObjectRef
virtual TObject ** GetObjectRef(const TObject *obj) const
Return address of pointer to obj.
Definition: TList.cxx:671
TList::RemoveLast
virtual void RemoveLast()
Remove the last object of the list.
Definition: TList.cxx:909
kTRUE
const Bool_t kTRUE
Definition: RtypesCore.h:91
TObject::TestBit
R__ALWAYS_INLINE Bool_t TestBit(UInt_t f) const
Definition: TObject.h:172
Version_t
short Version_t
Definition: RtypesCore.h:65
TList::AddFirst
virtual void AddFirst(TObject *obj)
Add object at the beginning of the list.
Definition: TList.cxx:100
TListIter::SetOption
void SetOption(Option_t *option)
Sets the object option stored in the list.
Definition: TList.cxx:1153
kCanDelete
@ kCanDelete
Definition: TObject.h:339
Option_t
const char Option_t
Definition: RtypesCore.h:66
TList::FindObject
virtual TObject * FindObject(const char *name) const
Find an object in this list using its name.
Definition: TList.cxx:578
TList::Delete
virtual void Delete(Option_t *option="")
Remove all objects from the list AND delete all heap based objects.
Definition: TList.cxx:470
R__COLLECTION_READ_GUARD
#define R__COLLECTION_READ_GUARD()
Definition: TCollection.h:126
ClassImp
#define ClassImp(name)
Definition: Rtypes.h:364
R__COLLECTION_READ_LOCKGUARD
#define R__COLLECTION_READ_LOCKGUARD(mutex)
Definition: TCollection.h:435
TList::fFirst
TObjLinkPtr_t fFirst
Definition: TList.h:52
TListIter::GetOption
Option_t * GetOption() const
Returns the object option stored in the list.
Definition: TList.cxx:1144
TList::LinkAt
TObjLink * LinkAt(Int_t idx) const
sorting order (when calling Sort() or for TSortedList)
Definition: TList.cxx:705
TClass.h
TList.h
TList::Last
virtual TObject * Last() const
Return the last object in the list. Returns 0 when list is empty.
Definition: TList.cxx:693
TCollection::fName
TString fName
Definition: TCollection.h:147
TListIter::fCurCursor
TObjLinkPtr_t fCurCursor
Definition: TList.h:206
ROOT::gCoreMutex
R__EXTERN TVirtualRWMutex * gCoreMutex
Definition: TVirtualRWMutex.h:32
TBuffer
Buffer base class used for serializing objects.
Definition: TBuffer.h:43
TList::AddLast
virtual void AddLast(TObject *obj)
Add object at the end of the list.
Definition: TList.cxx:152
TList::LnkCompare
Bool_t LnkCompare(const TObjLinkPtr_t &l1, const TObjLinkPtr_t &l2)
Compares the objects stored in the TObjLink objects.
Definition: TList.cxx:972
TListIter::operator!=
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
Definition: TList.cxx:1170
v
@ v
Definition: rootcling_impl.cxx:3635
b
#define b(i)
Definition: RSha256.hxx:100
TObject::RecursiveRemove
virtual void RecursiveRemove(TObject *obj)
Recursively remove this object from a list.
Definition: TObject.cxx:574
bool
TIterator
Iterator abstract base class.
Definition: TIterator.h:30
TListIter
Iterator of linked list.
Definition: TList.h:200
object
TList::Sort
virtual void Sort(Bool_t order=kSortAscending)
Sort linked list.
Definition: TList.cxx:937
TROOT.h
kIterForward
const Bool_t kIterForward
Definition: TCollection.h:40
TListIter::Next
TObject * Next()
Return next object in the list. Returns 0 when no more objects in list.
Definition: TList.cxx:1113
TList::First
virtual TObject * First() const
Return the first object in the list. Returns 0 when list is empty.
Definition: TList.cxx:659
TList::MakeIterator
virtual TIterator * MakeIterator(Bool_t dir=kIterForward) const
Return a list iterator.
Definition: TList.cxx:722
TList::At
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
TList::After
virtual TObject * After(const TObject *obj) const
Returns the object after object obj.
Definition: TList.cxx:330
TList::~TList
virtual ~TList()
Delete the list.
Definition: TList.cxx:92
TBuffer.h
TListIter::fCursor
TObjLinkPtr_t fCursor
Definition: TList.h:207
TCollection::GarbageCollect
static void GarbageCollect(TObject *obj)
Add to the list of things to be cleaned up.
Definition: TCollection.cxx:725
TList::Before
virtual TObject * Before(const TObject *obj) const
Returns the object before object obj.
Definition: TList.cxx:371
TList::NewOptLink
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
TList::AddBefore
virtual void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the list.
Definition: TList.cxx:196
kFALSE
const Bool_t kFALSE
Definition: RtypesCore.h:92
TList::TObjLinkPtr_t
std::shared_ptr< TObjLink > TObjLinkPtr_t
Definition: TList.h:49
TObject::IsEqual
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
TListIter::Reset
void Reset()
Reset list iterator.
Definition: TList.cxx:1161
TListIter::fList
const TList * fList
Definition: TList.h:205
TVirtualMutex.h
unsigned int
TList::DoSort
TObjLinkPtr_t * DoSort(TObjLinkPtr_t *head, Int_t n)
Sort linked list.
Definition: TList.cxx:984
TList::AddAfter
virtual void AddAfter(const TObject *after, TObject *obj)
Insert object after object after in the list.
Definition: TList.cxx:250
TIterator::operator=
virtual TIterator & operator=(const TIterator &)
Definition: TIterator.h:37
TList::Remove
virtual TObject * Remove(TObject *obj)
Remove object from the list.
Definition: TList.cxx:822
TCollection::GetSize
virtual Int_t GetSize() const
Return the capacity of the collection, i.e.
Definition: TCollection.h:182
UChar_t
unsigned char UChar_t
Definition: RtypesCore.h:38
TList::Add
virtual void Add(TObject *obj)
Definition: TList.h:87
TObject
Mother of all ROOT objects.
Definition: TObject.h:37
TList::fLast
TObjLinkPtr_t fLast
pointer to first entry in linked list
Definition: TList.h:53
TList::Clear
virtual void Clear(Option_t *option="")
Remove all objects from the list.
Definition: TList.cxx:402
name
char name[80]
Definition: TGX11.cxx:110
TIter
Definition: TCollection.h:233
fSize
size_t fSize
Definition: DeclareConverters.h:342
R__COLLECTION_WRITE_GUARD
#define R__COLLECTION_WRITE_GUARD()
Definition: TCollection.h:125
fFirst
T1 fFirst
Definition: X11Events.mm:86
TList::FindLink
TObjLink * FindLink(const TObject *obj, Int_t &idx) const
Returns the TObjLink object that contains object obj.
Definition: TList.cxx:628
TList::NewLink
TObjLinkPtr_t NewLink(TObject *obj, const TObjLinkPtr_t &prev=nullptr)
Return a new TObjLink.
Definition: TList.cxx:733
TListIter::fStarted
Bool_t fStarted
Definition: TList.h:209
TList::RecursiveRemove
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
TListIter::operator=
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
Definition: TList.cxx:1077
TListIter::TListIter
TListIter()
Definition: TList.h:211
R__COLLECTION_ITER_GUARD
#define R__COLLECTION_ITER_GUARD(collection)
Definition: TCollection.h:127
TList
A doubly linked list.
Definition: TList.h:44
int
Error
void Error(const char *location, const char *msgfmt,...)
Use this function in case an error occurred.
Definition: TError.cxx:187