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