Logo ROOT  
Reference Guide
 
Loading...
Searching...
No Matches
RooLinkedList.cxx
Go to the documentation of this file.
1/*****************************************************************************
2 * Project: RooFit *
3 * Package: RooFitCore *
4 * @(#)root/roofitcore:$Id$
5 * Authors: *
6 * WV, Wouter Verkerke, UC Santa Barbara, verkerke@slac.stanford.edu *
7 * DK, David Kirkby, UC Irvine, dkirkby@uci.edu *
8 * *
9 * Copyright (c) 2000-2005, Regents of the University of California *
10 * and Stanford University. All rights reserved. *
11 * *
12 * Redistribution and use in source and binary forms, *
13 * with or without modification, are permitted according to the terms *
14 * listed in LICENSE (http://roofit.sourceforge.net/license.txt) *
15 *****************************************************************************/
16
17/**
18\file RooLinkedList.cxx
19\class RooLinkedList
20\ingroup Roofitcore
21
22Collection class for internal use, storing
23a collection of RooAbsArg pointers in a doubly linked list.
24It can optionally add a hash table to speed up random access
25in large collections
26Use RooAbsCollection derived objects for public use
27(e.g. RooArgSet or RooArgList)
28**/
29
30#include "RooLinkedList.h"
31
32#include "RooLinkedListIter.h"
33#include "RooAbsArg.h"
34#include "RooAbsData.h"
35#include "RooMsgService.h"
36
37#include "Riostream.h"
38#include "TBuffer.h"
39#include "TROOT.h"
40
41#include <algorithm>
42#include <list>
43#include <memory>
44#include <vector>
45
46
47/// \cond ROOFIT_INTERNAL
48
50 /// a chunk of memory in a pool for quick allocation of RooLinkedListElems
51 class Chunk {
52 public:
53 /// constructor
54 Chunk(Int_t sz) :
55 _sz(sz), _free(capacity()),
57 {
58 //cout << "RLLID::Chunk ctor(" << this << ") of size " << _free << " list elements" << std::endl ;
59 // initialise free list
60 for (Int_t i = 0; i < _free; ++i)
61 _chunk[i]._next = (i + 1 < _free) ? &_chunk[i + 1] : nullptr;
62 }
63 /// forbid copying
64 Chunk(const Chunk&) = delete;
65 // forbid assignment
66 Chunk& operator=(const Chunk&) = delete;
67 /// destructor
68 ~Chunk() { delete[] _chunk; }
69 /// chunk capacity
70 Int_t capacity() const
71 { return (1 << _sz) / sizeof(RooLinkedListElem); }
72 /// chunk free elements
73 Int_t free() const { return _free; }
74 /// chunk occupied elements
75 Int_t size() const { return capacity() - free(); }
76 /// return size class
77 int szclass() const { return _sz; }
78 /// chunk full?
79 bool full() const { return !free(); }
80 /// chunk empty?
81 bool empty() const { return capacity() == free(); }
82 /// return address of chunk
83 const void* chunkaddr() const { return _chunk; }
84 /// check if el is in this chunk
85 bool contains(RooLinkedListElem* el) const
86 { return _chunk <= el && el < &_chunk[capacity()]; }
87 /// pop a free element off the free list
89 {
90 if (!_freelist) return nullptr;
92 _freelist = retVal->_next;
93 retVal->_arg = nullptr; retVal->_refCount = 0;
94 retVal->_prev = retVal->_next = nullptr;
95 --_free;
96 return retVal;
97 }
98 /// push a free element back onto the freelist
100 {
101 el->_next = _freelist;
102 _freelist = el;
103 ++_free;
104 }
105 private:
106 Int_t _sz; ///< chunk capacity
107 Int_t _free; ///< length of free list
108 RooLinkedListElem* _chunk; ///< chunk from which elements come
109 RooLinkedListElem* _freelist; ///< list of free elements
110 };
111
112 class Pool {
113 private:
114 enum {
115 minsz = 7, ///< minimum chunk size (just below 1 << minsz bytes)
116 maxsz = 18, ///< maximum chunk size (just below 1 << maxsz bytes)
117 szincr = 1 ///< size class increment (sz = 1 << (minsz + k * szincr))
118 };
119 /// a chunk of memory in the pool
120 typedef RooLinkedListImplDetails::Chunk Chunk;
121 typedef std::list<Chunk*> ChunkList;
122 typedef std::map<const void*, Chunk*> AddrMap;
123 public:
124 /// constructor
125 Pool();
126 /// destructor
127 ~Pool();
128 /// acquire the pool
129 inline void acquire() { ++_refCount; }
130 /// release the pool, return true if the pool is unused
131 inline bool release() { return 0 == --_refCount; }
132 /// pop a free element out of the pool
134 /// push a free element back into the pool
136 private:
141 UInt_t _refCount = 0;
142
143 /// adjust _cursz to current largest block
145 /// find size of next chunk to allocate (in a hopefully smart way)
146 Int_t nextChunkSz() const;
147 };
148
149 Pool::Pool()
150 {
151 std::fill(_szmap, _szmap + ((maxsz - minsz) / szincr), 0);
152 }
153
154 Pool::~Pool()
155 {
156 _freelist.clear();
157 for (AddrMap::iterator it = _addrmap.begin(); _addrmap.end() != it; ++it)
158 delete it->second;
159 _addrmap.clear();
160 }
161
162 RooLinkedListElem* Pool::pop_free_elem()
163 {
164 if (_freelist.empty()) {
165 // allocate and register new chunk and put it on the freelist
166 const Int_t sz = nextChunkSz();
167 Chunk *c = new Chunk(sz);
168 _addrmap[c->chunkaddr()] = c;
169 _freelist.push_back(c);
170 updateCurSz(sz, +1);
171 }
172 // get free element from first chunk on _freelist
173 Chunk* c = _freelist.front();
174 RooLinkedListElem* retVal = c->pop_free_elem();
175 // full chunks are removed from _freelist
176 if (c->full()) _freelist.pop_front();
177 return retVal;
178 }
179
180 void Pool::push_free_elem(RooLinkedListElem* el)
181 {
182 // find from which chunk el came
184 if (!_addrmap.empty()) {
185 ci = _addrmap.lower_bound(el);
186 if (ci == _addrmap.end()) {
187 // point beyond last element, so get last one
188 ci = (++_addrmap.rbegin()).base();
189 } else {
190 // valid ci, check if we need to decrement ci because el isn't the
191 // first element in the chunk
192 if (_addrmap.begin() != ci && ci->first != el) --ci;
193 }
194 }
195 // either empty addressmap, or ci should now point to the chunk which might
196 // contain el
197 if (_addrmap.empty() || !ci->second->contains(el)) {
198 // el is not in any chunk we know about, so just delete it
199 delete el;
200 return;
201 }
202 Chunk *c = ci->second;
203 const bool moveToFreelist = c->full();
204 c->push_free_elem(el);
205 if (c->empty()) {
206 // delete chunk if all empty
207 ChunkList::iterator it = std::find( _freelist.begin(), _freelist.end(), c);
208 if (_freelist.end() != it) _freelist.erase(it);
209 _addrmap.erase(ci->first);
210 updateCurSz(c->szclass(), -1);
211 delete c;
212 } else if (moveToFreelist) {
213 _freelist.push_back(c);
214 }
215 }
216
217 void Pool::updateCurSz(Int_t sz, Int_t incr)
218 {
219 _szmap[(sz - minsz) / szincr] += incr;
220 _cursz = minsz;
221 for (int i = (maxsz - minsz) / szincr; i--; ) {
222 if (_szmap[i]) {
223 _cursz += i * szincr;
224 break;
225 }
226 }
227 }
228
229 Int_t Pool::nextChunkSz() const
230 {
231 // no chunks with space available, figure out chunk size
232 Int_t sz = _cursz;
233 if (_addrmap.empty()) {
234 // if we start allocating chunks, we start from minsz
235 sz = minsz;
236 } else {
237 if (minsz >= sz) {
238 // minimal sized chunks are always grown
239 sz = minsz + szincr;
240 } else {
241 if (1 != _addrmap.size()) {
242 // if we have more than one completely filled chunk, grow
243 sz += szincr;
244 } else {
245 // just one chunk left, try shrinking chunk size
246 sz -= szincr;
247 }
248 }
249 }
250 // clamp size to allowed range
251 if (sz > maxsz) sz = maxsz;
252 if (sz < minsz) sz = minsz;
253 return sz;
254 }
255}
256
257/// \endcond
258
260
261////////////////////////////////////////////////////////////////////////////////
262
264 _hashThresh(htsize), _size(0), _first(nullptr), _last(nullptr), _htableName(nullptr), _htableLink(nullptr), _useNptr(true)
265{
266 if (!_pool) _pool = new Pool;
267 _pool->acquire();
268}
269
270////////////////////////////////////////////////////////////////////////////////
271/// Copy constructor
272
274 TObject(other), _hashThresh(other._hashThresh), _size(0), _first(nullptr), _last(nullptr), _htableName(nullptr), _htableLink(nullptr),
275 _name(other._name),
276 _useNptr(other._useNptr)
277{
278 if (!_pool) _pool = new Pool;
279 _pool->acquire();
280 if (other._htableName) _htableName = std::make_unique<HashTableByName>(other._htableName->size()) ;
281 if (other._htableLink) _htableLink = std::make_unique<HashTableByLink>(other._htableLink->size()) ;
282 for (RooLinkedListElem* elem = other._first; elem; elem = elem->_next) {
283 Add(elem->_arg, elem->_refCount) ;
284 }
285}
286
287////////////////////////////////////////////////////////////////////////////////
288/// std::cout << "RooLinkedList::createElem(" << this << ") obj = " << obj << " elem = " << elem << std::endl ;
289
291{
292 RooLinkedListElem* ret = _pool->pop_free_elem();
293 ret->init(obj, elem);
294 return ret ;
295}
296
297////////////////////////////////////////////////////////////////////////////////
298
300{
301 elem->release() ;
302 _pool->push_free_elem(elem);
303 //delete elem ;
304}
305
306////////////////////////////////////////////////////////////////////////////////
307/// Assignment operator, copy contents from 'other'
308
310{
311 // Prevent self-assignment
312 if (&other==this) return *this ;
313
314 // remove old elements
315 Clear();
316 // Copy elements
317 for (RooLinkedListElem* elem = other._first; elem; elem = elem->_next) {
318 Add(elem->_arg) ;
319 }
320
321 return *this ;
322}
323
324////////////////////////////////////////////////////////////////////////////////
325/// Change the threshold for hash-table use to given size.
326/// If a hash table exists when this method is called, it is regenerated.
327
329{
330 if (size < 0) {
331 coutE(InputArguments) << "RooLinkedList::setHashTable() ERROR size must be positive" << std::endl;
332 return;
333 }
334 if (size == 0) {
335 // Remove existing hash table
336 _htableName.reset();
337 _htableLink.reset();
338 return;
339 }
340
341 if (!_htableName) {
342 // (Re)create hash tables
343 _htableName = std::make_unique<HashTableByName>(size);
344 _htableLink = std::make_unique<HashTableByLink>(size);
345 }
346
347 _htableName->reserve(size);
348 _htableLink->reserve(size);
349}
350
351////////////////////////////////////////////////////////////////////////////////
352/// Destructor
353
355{
356 // Required since we overload TObject::Hash.
358
359 _htableName.reset();
360 _htableLink.reset();
361
362 Clear() ;
363 if (_pool->release()) {
364 delete _pool;
365 _pool = nullptr;
366 }
367}
368
369////////////////////////////////////////////////////////////////////////////////
370/// Find the element link containing the given object
371
373{
374 if (_htableLink) {
375 auto found = _htableLink->find(arg);
376 if (found == _htableLink->end()) return nullptr;
377 return const_cast<RooLinkedListElem *>(reinterpret_cast<RooLinkedListElem const*>(found->second));
378 }
379
381 while(ptr) {
382 if (ptr->_arg == arg) {
383 return ptr ;
384 }
385 ptr = ptr->_next ;
386 }
387 return nullptr ;
388
389}
390
391////////////////////////////////////////////////////////////////////////////////
392/// Insert object into collection with given reference count value
393
394void RooLinkedList::Add(TObject* arg, Int_t refCount)
395{
396 if (!arg) return ;
397
398 // Only use RooAbsArg::namePtr() in lookup-by-name if all elements have it
399 if (!dynamic_cast<RooAbsArg*>(arg) && !dynamic_cast<RooAbsData*>(arg)) _useNptr = false;
400
401 // Add to hash table
402 if (_htableName) {
403
404 // Expand capacity of hash table if #entries>#slots
405 if (static_cast<size_t>(_size) > _htableName->size()) {
407 }
408
409 } else if (_hashThresh>0 && _size>_hashThresh) {
410
412 }
413
414 if (_last) {
415 // Append element at end of list
416 _last = createElement(arg,_last) ;
417 } else {
418 // Append first element, set first,last
419 _last = createElement(arg) ;
420 _first=_last ;
421 }
422
423 if (_htableName){
424 //cout << "storing link " << _last << " with hash arg " << arg << std::endl ;
425 _htableName->insert({arg->GetName(), arg});
426 _htableLink->insert({arg, reinterpret_cast<TObject *>(_last)});
427 }
428
429 _size++ ;
430 _last->_refCount = refCount ;
431
432 _at.push_back(_last);
433}
434
435////////////////////////////////////////////////////////////////////////////////
436/// Remove object from collection
437
439{
440 // Find link element
442 if (!elem) return false ;
443
444 // Remove from hash table
445 if (_htableName) {
446 _htableName->erase(arg->GetName()) ;
447 }
448 if (_htableLink) {
449 _htableLink->erase(arg) ;
450 }
451
452 // Update first,last if necessary
453 if (elem==_first) _first=elem->_next ;
454 if (elem==_last) _last=elem->_prev ;
455
456 // Remove from index array
457 auto at_elem_it = std::find(_at.begin(), _at.end(), elem);
458 _at.erase(at_elem_it);
459
460 // Delete and shrink
461 _size-- ;
463 return true ;
464}
465
466////////////////////////////////////////////////////////////////////////////////
467/// If one of the TObject we have a referenced to is deleted, remove the
468/// reference.
469
471{
472 Remove(obj); // This is a nop if the obj is not in the collection.
473}
474
475////////////////////////////////////////////////////////////////////////////////
476/// Return object stored in sequential position given by index.
477/// If index is out of range, a null pointer is returned.
478
480{
481 // Check range
482 if (index<0 || index>=_size) return nullptr ;
483
484 return _at[index]->_arg;
485//
486//
487// // Walk list
488// RooLinkedListElem* ptr = _first;
489// while(index--) ptr = ptr->_next ;
490//
491// // Return arg
492// return ptr->_arg ;
493}
494
495////////////////////////////////////////////////////////////////////////////////
496/// Replace object 'oldArg' in collection with new object 'newArg'.
497/// If 'oldArg' is not found in collection false is returned
498
500{
501 // Find existing element and replace arg
503 if (!elem) return false ;
504
505 if (_htableName) {
506 _htableName->erase(oldArg->GetName());
507 _htableName->insert({newArg->GetName(), newArg});
508 }
509 if (_htableLink) {
510 // Link is hashed by contents and may change slot in hash table
511 _htableLink->erase(oldArg) ;
512 _htableLink->insert({newArg, reinterpret_cast<TObject*>(elem)}) ;
513 }
514
515 elem->_arg = const_cast<TObject*>(newArg);
516 return true ;
517}
518
519////////////////////////////////////////////////////////////////////////////////
520/// Return pointer to object with given name. If no such object
521/// is found return a null pointer.
522
524{
525 return find(name) ;
526}
527
528////////////////////////////////////////////////////////////////////////////////
529/// Find object in list. If list contains object return
530/// (same) pointer to object, otherwise return null pointer
531
533{
534 RooLinkedListElem *elem = findLink(const_cast<TObject*>(obj));
535 return elem ? elem->_arg : nullptr ;
536}
537
538////////////////////////////////////////////////////////////////////////////////
539/// Remove all elements from collection
540
542{
543 for (RooLinkedListElem *elem = _first, *next; elem; elem = next) {
544 next = elem->_next ;
546 }
547 _first = nullptr ;
548 _last = nullptr ;
549 _size = 0 ;
550
551 if (_htableName) {
552 _htableName = std::make_unique<HashTableByName>(_htableName->size()) ;
553 }
554 if (_htableLink) {
555 _htableLink = std::make_unique<HashTableByLink>(_htableLink->size()) ;
556 }
557
558 // empty index array
559 _at.clear();
560}
561
562////////////////////////////////////////////////////////////////////////////////
563/// Remove all elements in collection and delete all elements
564/// NB: Collection does not own elements, this function should
565/// be used judiciously by caller.
566
568{
570 while(elem) {
571 RooLinkedListElem* next = elem->_next ;
572 delete elem->_arg ;
574 elem = next ;
575 }
576 _first = nullptr ;
577 _last = nullptr ;
578 _size = 0 ;
579
580 if (_htableName) {
581 _htableName = std::make_unique<HashTableByName>(_htableName->size()) ;
582 }
583 if (_htableLink) {
584 _htableLink = std::make_unique<HashTableByLink>(_htableLink->size()) ;
585 }
586
587 // empty index array
588 _at.clear();
589}
590
591////////////////////////////////////////////////////////////////////////////////
592/// Return pointer to object with given name in collection.
593/// If no such object is found, return null pointer.
594
596{
597
598 if (_htableName) {
599 auto found = _htableName->find(name);
600 TObject *a = found != _htableName->end() ? const_cast<TObject*>(found->second) : nullptr;
601 // RooHashTable::find could return false negative if element was renamed to 'name'.
602 // The list search means it won't return false positive, so can return here.
603 if (a) return a;
604 if (_useNptr) {
605 // See if it might have been renamed
607 //cout << "RooLinkedList::find: possibly renamed '" << name << "', kRenamedArg=" << (nptr&&nptr->TestBit(RooNameReg::kRenamedArg)) << std::endl;
608 if (nptr && nptr->TestBit(RooNameReg::kRenamedArg)) {
610 while(ptr) {
611 if ( (dynamic_cast<RooAbsArg*>(ptr->_arg) && static_cast<RooAbsArg*>(ptr->_arg)->namePtr() == nptr) ||
612 (dynamic_cast<RooAbsData*>(ptr->_arg) && static_cast<RooAbsData*>(ptr->_arg)->namePtr() == nptr)) {
613 return ptr->_arg ;
614 }
615 ptr = ptr->_next ;
616 }
617 }
618 return nullptr ;
619 }
620 //cout << "RooLinkedList::find: possibly renamed '" << name << "'" << std::endl;
621 }
622
624
625 // The penalty for RooNameReg lookup seems to be outweighted by the faster search
626 // when the size list is longer than ~7, but let's be a bit conservative.
627 if (_useNptr && _size>9) {
629 if (!nptr) return nullptr;
630
631 while(ptr) {
632 if ( (dynamic_cast<RooAbsArg*>(ptr->_arg) && static_cast<RooAbsArg*>(ptr->_arg)->namePtr() == nptr) ||
633 (dynamic_cast<RooAbsData*>(ptr->_arg) && static_cast<RooAbsData*>(ptr->_arg)->namePtr() == nptr)) {
634 return ptr->_arg ;
635 }
636 ptr = ptr->_next ;
637 }
638 return nullptr ;
639 }
640
641 while(ptr) {
642 if (!strcmp(ptr->_arg->GetName(),name)) {
643 return ptr->_arg ;
644 }
645 ptr = ptr->_next ;
646 }
647 return nullptr ;
648}
649
650////////////////////////////////////////////////////////////////////////////////
651/// Return pointer to object with given name in collection.
652/// If no such object is found, return null pointer.
653
655{
656 if (_htableName) {
657 RooAbsArg* a = const_cast<RooAbsArg *>(static_cast<RooAbsArg const*>((*_htableName)[arg->GetName()]));
658 if (a) return a;
659 //cout << "RooLinkedList::findArg: possibly renamed '" << arg->GetName() << "', kRenamedArg=" << arg->namePtr()->TestBit(RooNameReg::kRenamedArg) << std::endl;
660 // See if it might have been renamed
661 if (!arg->namePtr()->TestBit(RooNameReg::kRenamedArg)) return nullptr;
662 }
663
665 const TNamed* nptr = arg->namePtr();
666 while(ptr) {
667 if ((static_cast<RooAbsArg*>(ptr->_arg))->namePtr() == nptr) {
668 return static_cast<RooAbsArg*>(ptr->_arg) ;
669 }
670 ptr = ptr->_next ;
671 }
672 return nullptr ;
673}
674
675////////////////////////////////////////////////////////////////////////////////
676/// Return position of given object in list. If object
677/// is not contained in list, return -1
678
680{
682 Int_t idx(0) ;
683 while(ptr) {
684 if (ptr->_arg==arg) return idx ;
685 ptr = ptr->_next ;
686 idx++ ;
687 }
688 return -1 ;
689}
690
691////////////////////////////////////////////////////////////////////////////////
692/// Return position of given object in list. If object
693/// is not contained in list, return -1
694
696{
698 Int_t idx(0) ;
699 while(ptr) {
700 if (strcmp(ptr->_arg->GetName(),name)==0) return idx ;
701 ptr = ptr->_next ;
702 idx++ ;
703 }
704 return -1 ;
705}
706
707////////////////////////////////////////////////////////////////////////////////
708/// Print contents of list, defers to Print() function
709/// of contained objects
710
711void RooLinkedList::Print(const char* opt) const
712{
714 while(elem) {
715 std::cout << elem->_arg << " : " ;
716 elem->_arg->Print(opt) ;
717 elem = elem->_next ;
718 }
719}
720
721////////////////////////////////////////////////////////////////////////////////
722/// Create a TIterator for this list.
723/// \param forward Run in forward direction (default).
724/// \return Pointer to a TIterator. The caller owns the pointer.
725
727 auto iterImpl = std::make_unique<RooLinkedListIterImpl>(this, forward);
728 return new RooLinkedListIter(std::move(iterImpl));
729}
730
731////////////////////////////////////////////////////////////////////////////////
732/// Create an iterator for this list.
733/// \param forward Run in forward direction (default).
734/// \return RooLinkedListIter (subclass of TIterator) over this list
735
737 auto iterImpl = std::make_unique<RooLinkedListIterImpl>(this, forward);
738 return RooLinkedListIter(std::move(iterImpl));
739}
740
741////////////////////////////////////////////////////////////////////////////////
742/// Create a one-time-use forward iterator for this list.
743/// \return RooFIter that only supports next()
744
746 auto iterImpl = std::make_unique<RooFIterForLinkedList>(this);
747 return RooFIter(std::move(iterImpl));
748}
749
751 return {this, true};
752}
753
755 return {this, nullptr, true};
756}
757
759 return {this, false};
760}
761
763 return {this, nullptr, false};
764}
765
766////////////////////////////////////////////////////////////////////////////////
767
769{
772
773 // rebuild index array
775 for (auto it = _at.begin(); it != _at.end(); ++it, elem = elem->_next) {
776 *it = elem;
777 }
778}
779
780////////////////////////////////////////////////////////////////////////////////
781/// length 0, 1 lists are sorted
782
783template <bool ascending>
785 RooLinkedListElem* l1, const unsigned sz, RooLinkedListElem** tail)
786{
787 if (!l1 || sz < 2) {
788 // if desired, update the tail of the (newly merged sorted) list
789 if (tail) *tail = l1;
790 return l1;
791 }
792 if (sz <= 16) {
793 // for short lists, we sort in an array
794 std::vector<RooLinkedListElem *> arr(sz, nullptr);
795 for (int i = 0; l1; l1 = l1->_next, ++i) arr[i] = l1;
796 // straight insertion sort
797 {
798 int i = 1;
799 do {
800 int j = i - 1;
801 RooLinkedListElem *tmp = arr[i];
802 while (0 <= j) {
803 const bool inOrder = ascending ?
804 (tmp->_arg->Compare(arr[j]->_arg) <= 0) :
805 (arr[j]->_arg->Compare(tmp->_arg) <= 0);
806 if (!inOrder) break;
807 arr[j + 1] = arr[j];
808 --j;
809 }
810 arr[j + 1] = tmp;
811 ++i;
812 } while (int(sz) != i);
813 }
814 // link elements in array
815 arr[0]->_prev = arr[sz - 1]->_next = nullptr;
816 for (int i = 0; i < int(sz - 1); ++i) {
817 arr[i]->_next = arr[i + 1];
818 arr[i + 1]->_prev = arr[i];
819 }
820 if (tail) *tail = arr[sz - 1];
821 return arr[0];
822 }
823 // find middle of l1, and let a second list l2 start there
825 for (RooLinkedListElem *end = l2; end->_next; end = end->_next) {
826 end = end->_next;
827 l2 = l2->_next;
828 if (!end->_next) break;
829 }
830 // disconnect the two sublists
831 l2->_prev->_next = nullptr;
832 l2->_prev = nullptr;
833 // sort the two sublists (only recurse if we have to)
834 if (l1->_next) l1 = mergesort_impl<ascending>(l1, sz / 2);
835 if (l2->_next) l2 = mergesort_impl<ascending>(l2, sz - sz / 2);
836 // merge the two (sorted) sublists
837 // l: list head, t: list tail of merged list
838 RooLinkedListElem *l = (ascending ? (l1->_arg->Compare(l2->_arg) <= 0) :
839 (l2->_arg->Compare(l1->_arg) <= 0)) ? l1 : l2;
840 RooLinkedListElem *t = l;
841 if (l == l2) {
842 RooLinkedListElem* tmp = l1;
843 l1 = l2;
844 l2 = tmp;
845 }
846 l1 = l1->_next;
847 while (l1 && l2) {
848 const bool inOrder = ascending ? (l1->_arg->Compare(l2->_arg) <= 0) :
849 (l2->_arg->Compare(l1->_arg) <= 0);
850 if (!inOrder) {
851 // insert l2 just before l1
852 if (l1->_prev) {
853 l1->_prev->_next = l2;
854 l2->_prev = l1->_prev;
855 }
856 // swap l2 and l1
857 RooLinkedListElem *tmp = l1;
858 l1 = l2;
859 l2 = tmp;
860 }
861 // move forward in l1
862 t = l1;
863 l1 = l1->_next;
864 }
865 // attach l2 at t
866 if (l2) {
867 l2->_prev = t;
868 if (t) t->_next = l2;
869 }
870 // if desired, update the tail of the (newly merged sorted) list
871 if (tail) {
872 for (l1 = t; l1; l1 = l1->_next) t = l1;
873 *tail = t;
874 }
875 // return the head of the sorted list
876 return l;
877}
878// void Roo1DTable::Streamer(TBuffer &R__b)
879// {
880// // Stream an object of class Roo1DTable.
881
882// if (R__b.IsReading()) {
883// R__b.ReadClassBuffer(Roo1DTable::Class(),this);
884// } else {
885// R__b.WriteClassBuffer(Roo1DTable::Class(),this);
886// }
887// }
888
889////////////////////////////////////////////////////////////////////////////////
890/// Custom streaming handling schema evolution w.r.t past implementations
891
893{
894 if (R__b.IsReading()) {
895
896 Version_t v = R__b.ReadVersion();
897 //R__b.ReadVersion();
899
900 Int_t size ;
901 TObject* arg ;
902
903 R__b >> size ;
904 while(size--) {
905 R__b >> arg ;
906 Add(arg) ;
907 }
908
909 if (v > 1 && v < 4) {
910 R__b >> _name;
911 }
912
913 } else {
914 R__b.WriteVersion(RooLinkedList::IsA());
916 R__b << _size ;
917
919 while(ptr) {
920 R__b << ptr->_arg ;
921 ptr = ptr->_next ;
922 }
923
924 R__b << _name ;
925 }
926}
#define c(i)
Definition RSha256.hxx:101
#define a(i)
Definition RSha256.hxx:99
size_t size(const MatrixT &matrix)
retrieve the size of a square matrix
#define coutE(a)
int Int_t
Signed integer 4 bytes (int)
Definition RtypesCore.h:59
short Version_t
Class version identifier (short)
Definition RtypesCore.h:79
const char Option_t
Option string (const char)
Definition RtypesCore.h:80
ROOT::Detail::TRangeCast< T, true > TRangeDynCast
TRangeDynCast is an adapter class that allows the typed iteration through a TCollection.
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t index
char name[80]
Definition TGX11.cxx:110
Binding & operator=(OUT(*fun)(void))
#define free
Definition civetweb.c:1578
const_iterator begin() const
const_iterator end() const
Common abstract base class for objects that represent a value and a "shape" in RooFit.
Definition RooAbsArg.h:76
const TNamed * namePtr() const
De-duplicated pointer to this object's name.
Definition RooAbsArg.h:502
Abstract base class for binned and unbinned datasets.
Definition RooAbsData.h:57
const TNamed * namePtr() const
De-duplicated pointer to this object's name.
Definition RooAbsData.h:302
A one-time forward iterator working on RooLinkedList or RooAbsCollection.
Link element for the RooLinkedList class.
TObject * _arg
Link to contents.
Int_t _refCount
! Reference count
RooLinkedListElem * _next
Link to next element in list.
Implementation of the actual iterator on RooLinkedLists.
A wrapper around TIterator derivatives.
Collection class for internal use, storing a collection of RooAbsArg pointers in a doubly linked list...
RooLinkedListIterImpl rend() const
TObject * At(int index) const
Return object stored in sequential position given by index.
RooLinkedListIter iterator(bool forward=true) const
Create an iterator for this list.
static Pool * _pool
shared memory pool for allocation of RooLinkedListElems
~RooLinkedList() override
Destructor.
RooLinkedListIterImpl end() const
RooLinkedListImplDetails::Pool Pool
memory pool for quick allocation of RooLinkedListElems
std::vector< RooLinkedListElem * > _at
! index list for quick index through At
std::unique_ptr< HashTableByName > _htableName
! Hash table by name
void RecursiveRemove(TObject *obj) override
If one of the TObject we have a referenced to is deleted, remove the reference.
bool Replace(const TObject *oldArg, const TObject *newArg)
Replace object 'oldArg' in collection with new object 'newArg'.
RooLinkedList(Int_t htsize=0)
void Print(const char *opt) const override
Print contents of list, defers to Print() function of contained objects.
std::unique_ptr< HashTableByLink > _htableLink
! Hash table by link pointer
RooFIter fwdIterator() const
Create a one-time-use forward iterator for this list.
void deleteElement(RooLinkedListElem *)
RooLinkedListElem * findLink(const TObject *arg) const
Find the element link containing the given object.
void Streamer(TBuffer &) override
Custom streaming handling schema evolution w.r.t past implementations.
RooLinkedListIterImpl rbegin() const
std::size_t size() const
TClass * IsA() const override
Int_t _hashThresh
Size threshold for hashing.
RooLinkedListElem * createElement(TObject *obj, RooLinkedListElem *elem=nullptr)
std::cout << "RooLinkedList::createElem(" << this << ") obj = " << obj << " elem = " << elem << std::...
RooAbsArg * findArg(const RooAbsArg *) const
Return pointer to object with given name in collection.
void Delete(Option_t *o=nullptr) override
Remove all elements in collection and delete all elements NB: Collection does not own elements,...
TObject * find(const char *name) const
Return pointer to object with given name in collection.
RooLinkedList & operator=(const RooLinkedList &other)
Assignment operator, copy contents from 'other'.
virtual void Add(TObject *arg)
Int_t _size
Current size of list.
RooLinkedListIterImpl begin() const
RooLinkedListElem * _last
! Link to last element of list
void setHashTableSize(Int_t size)
Change the threshold for hash-table use to given size.
TObject * FindObject(const char *name) const override
Return pointer to object with given name.
RooLinkedListElem * _first
! Link to first element of list
TIterator * MakeIterator(bool forward=true) const
Create a TIterator for this list.
void Clear(Option_t *o=nullptr) override
Remove all elements from collection.
static RooLinkedListElem * mergesort_impl(RooLinkedListElem *l1, const unsigned sz, RooLinkedListElem **tail=nullptr)
length 0, 1 lists are sorted
void Sort(bool ascend=true)
Int_t IndexOf(const char *name) const
Return position of given object in list.
virtual bool Remove(TObject *arg)
Remove object from collection.
@ kRenamedArg
TNamed flag to indicate that some RooAbsArg has been renamed (flag set in new name)
Definition RooNameReg.h:46
static const TNamed * known(const char *stringPtr)
If the name is already known, return its TNamed pointer. Otherwise return 0 (don't register the name)...
Buffer base class used for serializing objects.
Definition TBuffer.h:43
Iterator abstract base class.
Definition TIterator.h:30
The TNamed class is the base class for all named ROOT classes.
Definition TNamed.h:29
const char * GetName() const override
Returns name of object.
Definition TNamed.h:49
Mother of all ROOT objects.
Definition TObject.h:41
virtual const char * GetName() const
Returns name of object.
Definition TObject.cxx:457
virtual void Streamer(TBuffer &)
Stream an object of class TObject.
Definition TObject.cxx:972
void CallRecursiveRemoveIfNeeded(TObject &obj)
call RecursiveRemove for obj if gROOT is valid and obj.TestBit(kMustCleanup) is true.
Definition TROOT.h:400
TLine l
Definition textangle.C:4