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
22RooLinkedList is an collection 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 "RooFit.h"
33#include "RooLinkedListIter.h"
34#include "RooHashTable.h"
35#include "RooAbsArg.h"
36#include "RooMsgService.h"
37
38#include "Riostream.h"
39#include "TBuffer.h"
40#include "TROOT.h"
41#include "ROOT/RMakeUnique.hxx"
42
43#include <algorithm>
44#include <list>
45
46using namespace std;
47
49;
51 /// a chunk of memory in a pool for quick allocation of RooLinkedListElems
52 class Chunk {
53 public:
54 /// constructor
55 Chunk(Int_t sz) :
56 _sz(sz), _free(capacity()),
57 _chunk(new RooLinkedListElem[_free]), _freelist(_chunk)
58 {
59 //cout << "RLLID::Chunk ctor(" << this << ") of size " << _free << " list elements" << endl ;
60 // initialise free list
61 for (Int_t i = 0; i < _free; ++i)
62 _chunk[i]._next = (i + 1 < _free) ? &_chunk[i + 1] : 0;
63 }
64 /// destructor
65 ~Chunk() { delete[] _chunk; }
66 /// chunk capacity
67 Int_t capacity() const
68 { return (1 << _sz) / sizeof(RooLinkedListElem); }
69 /// chunk free elements
70 Int_t free() const { return _free; }
71 /// chunk occupied elements
72 Int_t size() const { return capacity() - free(); }
73 /// return size class
74 int szclass() const { return _sz; }
75 /// chunk full?
76 bool full() const { return !free(); }
77 /// chunk empty?
78 bool empty() const { return capacity() == free(); }
79 /// return address of chunk
80 const void* chunkaddr() const { return _chunk; }
81 /// check if el is in this chunk
82 bool contains(RooLinkedListElem* el) const
83 { return _chunk <= el && el < &_chunk[capacity()]; }
84 /// pop a free element off the free list
85 RooLinkedListElem* pop_free_elem()
86 {
87 if (!_freelist) return 0;
88 RooLinkedListElem* retVal = _freelist;
89 _freelist = retVal->_next;
90 retVal->_arg = 0; retVal->_refCount = 0;
91 retVal->_prev = retVal->_next = 0;
92 --_free;
93 return retVal;
94 }
95 /// push a free element back onto the freelist
96 void push_free_elem(RooLinkedListElem* el)
97 {
98 el->_next = _freelist;
99 _freelist = el;
100 ++_free;
101 }
102 private:
103 Int_t _sz; ///< chunk capacity
104 Int_t _free; ///< length of free list
105 RooLinkedListElem* _chunk; ///< chunk from which elements come
106 RooLinkedListElem* _freelist; ///< list of free elements
107
108 /// forbid copying
109 Chunk(const Chunk&);
110 // forbid assignment
111 Chunk& operator=(const Chunk&);
112 };
113
114 class Pool {
115 private:
116 enum {
117 minsz = 7, ///< minimum chunk size (just below 1 << minsz bytes)
118 maxsz = 18, ///< maximum chunk size (just below 1 << maxsz bytes)
119 szincr = 1 ///< size class increment (sz = 1 << (minsz + k * szincr))
120 };
121 /// a chunk of memory in the pool
122 typedef RooLinkedListImplDetails::Chunk Chunk;
123 typedef std::list<Chunk*> ChunkList;
124 typedef std::map<const void*, Chunk*> AddrMap;
125 public:
126 /// constructor
127 Pool();
128 /// destructor
129 ~Pool();
130 /// acquire the pool
131 inline void acquire() { ++_refCount; }
132 /// release the pool, return true if the pool is unused
133 inline bool release() { return 0 == --_refCount; }
134 /// pop a free element out of the pool
135 RooLinkedListElem* pop_free_elem();
136 /// push a free element back into the pool
137 void push_free_elem(RooLinkedListElem* el);
138 private:
139 AddrMap _addrmap;
140 ChunkList _freelist;
141 UInt_t _szmap[(maxsz - minsz) / szincr];
142 Int_t _cursz;
143 UInt_t _refCount;
144
145 /// adjust _cursz to current largest block
146 void updateCurSz(Int_t sz, Int_t incr);
147 /// find size of next chunk to allocate (in a hopefully smart way)
148 Int_t nextChunkSz() const;
149 };
150
151 Pool::Pool() : _cursz(minsz), _refCount(0)
152 {
153 std::fill(_szmap, _szmap + ((maxsz - minsz) / szincr), 0);
154 }
155
156 Pool::~Pool()
157 {
158 _freelist.clear();
159 for (AddrMap::iterator it = _addrmap.begin(); _addrmap.end() != it; ++it)
160 delete it->second;
161 _addrmap.clear();
162 }
163
164 RooLinkedListElem* Pool::pop_free_elem()
165 {
166 if (_freelist.empty()) {
167 // allocate and register new chunk and put it on the freelist
168 const Int_t sz = nextChunkSz();
169 Chunk *c = new Chunk(sz);
170 _addrmap[c->chunkaddr()] = c;
171 _freelist.push_back(c);
172 updateCurSz(sz, +1);
173 }
174 // get free element from first chunk on _freelist
175 Chunk* c = _freelist.front();
176 RooLinkedListElem* retVal = c->pop_free_elem();
177 // full chunks are removed from _freelist
178 if (c->full()) _freelist.pop_front();
179 return retVal;
180 }
181
182 void Pool::push_free_elem(RooLinkedListElem* el)
183 {
184 // find from which chunk el came
185 AddrMap::iterator ci = _addrmap.end();
186 if (!_addrmap.empty()) {
187 ci = _addrmap.lower_bound(el);
188 if (ci == _addrmap.end()) {
189 // point beyond last element, so get last one
190 ci = (++_addrmap.rbegin()).base();
191 } else {
192 // valid ci, check if we need to decrement ci because el isn't the
193 // first element in the chunk
194 if (_addrmap.begin() != ci && ci->first != el) --ci;
195 }
196 }
197 // either empty addressmap, or ci should now point to the chunk which might
198 // contain el
199 if (_addrmap.empty() || !ci->second->contains(el)) {
200 // el is not in any chunk we know about, so just delete it
201 delete el;
202 return;
203 }
204 Chunk *c = ci->second;
205 const bool moveToFreelist = c->full();
206 c->push_free_elem(el);
207 if (c->empty()) {
208 // delete chunk if all empty
209 ChunkList::iterator it = std::find( _freelist.begin(), _freelist.end(), c);
210 if (_freelist.end() != it) _freelist.erase(it);
211 _addrmap.erase(ci->first);
212 updateCurSz(c->szclass(), -1);
213 delete c;
214 } else if (moveToFreelist) {
215 _freelist.push_back(c);
216 }
217 }
218
219 void Pool::updateCurSz(Int_t sz, Int_t incr)
220 {
221 _szmap[(sz - minsz) / szincr] += incr;
222 _cursz = minsz;
223 for (int i = (maxsz - minsz) / szincr; i--; ) {
224 if (_szmap[i]) {
225 _cursz += i * szincr;
226 break;
227 }
228 }
229 }
230
231 Int_t Pool::nextChunkSz() const
232 {
233 // no chunks with space available, figure out chunk size
234 Int_t sz = _cursz;
235 if (_addrmap.empty()) {
236 // if we start allocating chunks, we start from minsz
237 sz = minsz;
238 } else {
239 if (minsz >= sz) {
240 // minimal sized chunks are always grown
241 sz = minsz + szincr;
242 } else {
243 if (1 != _addrmap.size()) {
244 // if we have more than one completely filled chunk, grow
245 sz += szincr;
246 } else {
247 // just one chunk left, try shrinking chunk size
248 sz -= szincr;
249 }
250 }
251 }
252 // clamp size to allowed range
253 if (sz > maxsz) sz = maxsz;
254 if (sz < minsz) sz = minsz;
255 return sz;
256 }
257}
258
260
261////////////////////////////////////////////////////////////////////////////////
262
264 _hashThresh(htsize), _size(0), _first(0), _last(0), _htableName(0), _htableLink(0), _useNptr(kTRUE)
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(0), _last(0), _htableName(0), _htableLink(0),
275 _name(other._name),
276 _useNptr(other._useNptr)
277{
278 if (!_pool) _pool = new Pool;
279 _pool->acquire();
280 if (other._htableName) _htableName = new RooHashTable(other._htableName->size()) ;
282 for (RooLinkedListElem* elem = other._first; elem; elem = elem->_next) {
283 Add(elem->_arg, elem->_refCount) ;
284 }
285}
286
287////////////////////////////////////////////////////////////////////////////////
288/// cout << "RooLinkedList::createElem(" << this << ") obj = " << obj << " elem = " << elem << 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" << endl ;
332 return ;
333 }
334 if (size==0) {
335 if (!_htableName) {
336 // No hash table present
337 return ;
338 } else {
339 // Remove existing hash table
340 delete _htableName ;
341 delete _htableLink ;
342 _htableName = 0 ;
343 _htableLink = 0 ;
344 }
345 } else {
346
347 // (Re)create hash tables
348 if (_htableName) delete _htableName ;
349 _htableName = new RooHashTable(size) ;
350
351 if (_htableLink) delete _htableLink ;
353
354 // Fill hash table with existing entries
356 while(ptr) {
357 _htableName->add(ptr->_arg) ;
358 _htableLink->add((TObject*)ptr,ptr->_arg) ;
359 ptr = ptr->_next ;
360 }
361 }
362}
363
364////////////////////////////////////////////////////////////////////////////////
365/// Destructor
366
368{
369 // Required since we overload TObject::Hash.
371
372 if (_htableName) {
373 delete _htableName;
374 _htableName = 0;
375 }
376 if (_htableLink) {
377 delete _htableLink ;
378 _htableLink=0 ;
379 }
380
381 Clear() ;
382 if (_pool->release()) {
383 delete _pool;
384 _pool = 0;
385 }
386}
387
388////////////////////////////////////////////////////////////////////////////////
389/// Find the element link containing the given object
390
392{
393 if (_htableLink) {
394 return _htableLink->findLinkTo(arg) ;
395 }
396
398 while(ptr) {
399 if (ptr->_arg == arg) {
400 return ptr ;
401 }
402 ptr = ptr->_next ;
403 }
404 return 0 ;
405
406}
407
408////////////////////////////////////////////////////////////////////////////////
409/// Insert object into collection with given reference count value
410
411void RooLinkedList::Add(TObject* arg, Int_t refCount)
412{
413 if (!arg) return ;
414
415 // Only use RooAbsArg::namePtr() in lookup-by-name if all elements have it
416 if (!dynamic_cast<RooAbsArg*>(arg)) _useNptr = kFALSE;
417
418 // Add to hash table
419 if (_htableName) {
420
421 // Expand capacity of hash table if #entries>#slots
422 if (_size > _htableName->size()) {
424 }
425
426 } else if (_hashThresh>0 && _size>_hashThresh) {
427
429 }
430
431 if (_last) {
432 // Append element at end of list
433 _last = createElement(arg,_last) ;
434 } else {
435 // Append first element, set first,last
436 _last = createElement(arg) ;
437 _first=_last ;
438 }
439
440 if (_htableName){
441 //cout << "storing link " << _last << " with hash arg " << arg << endl ;
442 _htableName->add(arg) ;
443 _htableLink->add((TObject*)_last,arg) ;
444 }
445
446 _size++ ;
447 _last->_refCount = refCount ;
448
449 _at.push_back(_last);
450}
451
452////////////////////////////////////////////////////////////////////////////////
453/// Remove object from collection
454
456{
457 // Find link element
458 RooLinkedListElem* elem = findLink(arg) ;
459 if (!elem) return kFALSE ;
460
461 // Remove from hash table
462 if (_htableName) {
463 _htableName->remove(arg) ;
464 }
465 if (_htableLink) {
466 _htableLink->remove((TObject*)elem,arg) ;
467 }
468
469 // Update first,last if necessary
470 if (elem==_first) _first=elem->_next ;
471 if (elem==_last) _last=elem->_prev ;
472
473 // Remove from index array
474 auto at_elem_it = std::find(_at.begin(), _at.end(), elem);
475 _at.erase(at_elem_it);
476
477 // Delete and shrink
478 _size-- ;
479 deleteElement(elem) ;
480 return kTRUE ;
481}
482
483////////////////////////////////////////////////////////////////////////////////
484/// If one of the TObject we have a referenced to is deleted, remove the
485/// reference.
486
488{
489 Remove(obj); // This is a nop if the obj is not in the collection.
490}
491
492////////////////////////////////////////////////////////////////////////////////
493/// Return object stored in sequential position given by index.
494/// If index is out of range, a null pointer is returned.
495
497{
498 // Check range
499 if (index<0 || index>=_size) return 0 ;
500
501 return _at[index]->_arg;
502//
503//
504// // Walk list
505// RooLinkedListElem* ptr = _first;
506// while(index--) ptr = ptr->_next ;
507//
508// // Return arg
509// return ptr->_arg ;
510}
511
512////////////////////////////////////////////////////////////////////////////////
513/// Replace object 'oldArg' in collection with new object 'newArg'.
514/// If 'oldArg' is not found in collection kFALSE is returned
515
516Bool_t RooLinkedList::Replace(const TObject* oldArg, const TObject* newArg)
517{
518 // Find existing element and replace arg
519 RooLinkedListElem* elem = findLink(oldArg) ;
520 if (!elem) return kFALSE ;
521
522 if (_htableName) {
523 _htableName->replace(oldArg,newArg) ;
524 }
525 if (_htableLink) {
526 // Link is hashed by contents and may change slot in hash table
527 _htableLink->remove((TObject*)elem,(TObject*)oldArg) ;
528 _htableLink->add((TObject*)elem,(TObject*)newArg) ;
529 }
530
531 elem->_arg = (TObject*)newArg ;
532 return kTRUE ;
533}
534
535////////////////////////////////////////////////////////////////////////////////
536/// Return pointer to obejct with given name. If no such object
537/// is found return a null pointer
538
540{
541 return find(name) ;
542}
543
544////////////////////////////////////////////////////////////////////////////////
545/// Find object in list. If list contains object return
546/// (same) pointer to object, otherwise return null pointer
547
549{
550 RooLinkedListElem *elem = findLink((TObject*)obj) ;
551 return elem ? elem->_arg : 0 ;
552}
553
554////////////////////////////////////////////////////////////////////////////////
555/// Remove all elements from collection
556
558{
559 for (RooLinkedListElem *elem = _first, *next; elem; elem = next) {
560 next = elem->_next ;
561 deleteElement(elem) ;
562 }
563 _first = 0 ;
564 _last = 0 ;
565 _size = 0 ;
566
567 if (_htableName) {
568 Int_t hsize = _htableName->size() ;
569 delete _htableName ;
570 _htableName = new RooHashTable(hsize) ;
571 }
572 if (_htableLink) {
573 Int_t hsize = _htableLink->size() ;
574 delete _htableLink ;
576 }
577
578 // empty index array
579 _at.clear();
580}
581
582////////////////////////////////////////////////////////////////////////////////
583/// Remove all elements in collection and delete all elements
584/// NB: Collection does not own elements, this function should
585/// be used judiciously by caller.
586
588{
590 while(elem) {
591 RooLinkedListElem* next = elem->_next ;
592 delete elem->_arg ;
593 deleteElement(elem) ;
594 elem = next ;
595 }
596 _first = 0 ;
597 _last = 0 ;
598 _size = 0 ;
599
600 if (_htableName) {
601 Int_t hsize = _htableName->size() ;
602 delete _htableName ;
603 _htableName = new RooHashTable(hsize) ;
604 }
605 if (_htableLink) {
606 Int_t hsize = _htableLink->size() ;
607 delete _htableLink ;
609 }
610
611 // empty index array
612 _at.clear();
613}
614
615////////////////////////////////////////////////////////////////////////////////
616/// Return pointer to object with given name in collection.
617/// If no such object is found, return null pointer.
618
619TObject* RooLinkedList::find(const char* name) const
620{
621
622 if (_htableName) {
624 // RooHashTable::find could return false negative if element was renamed to 'name'.
625 // The list search means it won't return false positive, so can return here.
626 if (a) return a;
627 if (_useNptr) {
628 // See if it might have been renamed
629 const TNamed* nptr= RooNameReg::known(name);
630 //cout << "RooLinkedList::find: possibly renamed '" << name << "', kRenamedArg=" << (nptr&&nptr->TestBit(RooNameReg::kRenamedArg)) << endl;
631 if (nptr && nptr->TestBit(RooNameReg::kRenamedArg)) {
633 while(ptr) {
634 if ((((RooAbsArg*)ptr->_arg)->namePtr() == nptr)) {
635 return ptr->_arg ;
636 }
637 ptr = ptr->_next ;
638 }
639 }
640 return 0 ;
641 }
642 //cout << "RooLinkedList::find: possibly renamed '" << name << "'" << endl;
643 }
644
646
647 // The penalty for RooNameReg lookup seems to be outweighted by the faster search
648 // when the size list is longer than ~7, but let's be a bit conservative.
649 if (_useNptr && _size>9) {
650 const TNamed* nptr= RooNameReg::known(name);
651 if (!nptr) return 0;
652
653 while(ptr) {
654 if ((((RooAbsArg*)ptr->_arg)->namePtr() == nptr)) {
655 return ptr->_arg ;
656 }
657 ptr = ptr->_next ;
658 }
659 return 0 ;
660 }
661
662 while(ptr) {
663 if (!strcmp(ptr->_arg->GetName(),name)) {
664 return ptr->_arg ;
665 }
666 ptr = ptr->_next ;
667 }
668 return 0 ;
669}
670
671////////////////////////////////////////////////////////////////////////////////
672/// Return pointer to object with given name in collection.
673/// If no such object is found, return null pointer.
674
676{
677 if (_htableName) {
679 if (a) return a;
680 //cout << "RooLinkedList::findArg: possibly renamed '" << arg->GetName() << "', kRenamedArg=" << arg->namePtr()->TestBit(RooNameReg::kRenamedArg) << endl;
681 // See if it might have been renamed
682 if (!arg->namePtr()->TestBit(RooNameReg::kRenamedArg)) return 0;
683 }
684
686 const TNamed* nptr = arg->namePtr();
687 while(ptr) {
688 if (((RooAbsArg*)(ptr->_arg))->namePtr() == nptr) {
689 return (RooAbsArg*) ptr->_arg ;
690 }
691 ptr = ptr->_next ;
692 }
693 return 0 ;
694}
695
696////////////////////////////////////////////////////////////////////////////////
697/// Return position of given object in list. If object
698/// is not contained in list, return -1
699
701{
703 Int_t idx(0) ;
704 while(ptr) {
705 if (ptr->_arg==arg) return idx ;
706 ptr = ptr->_next ;
707 idx++ ;
708 }
709 return -1 ;
710}
711
712////////////////////////////////////////////////////////////////////////////////
713/// Return position of given object in list. If object
714/// is not contained in list, return -1
715
717{
719 Int_t idx(0) ;
720 while(ptr) {
721 if (strcmp(ptr->_arg->GetName(),name)==0) return idx ;
722 ptr = ptr->_next ;
723 idx++ ;
724 }
725 return -1 ;
726}
727
728////////////////////////////////////////////////////////////////////////////////
729/// Print contents of list, defers to Print() function
730/// of contained objects
731
732void RooLinkedList::Print(const char* opt) const
733{
734 RooLinkedListElem* elem = _first ;
735 while(elem) {
736 cout << elem->_arg << " : " ;
737 elem->_arg->Print(opt) ;
738 elem = elem->_next ;
739 }
740}
741
742////////////////////////////////////////////////////////////////////////////////
743/// Create a TIterator for this list.
744/// \param forward Run in forward direction (default).
745/// \return Pointer to a TIterator. The caller owns the pointer.
746
748 auto iterImpl = std::make_unique<RooLinkedListIterImpl>(this, forward);
749 return new RooLinkedListIter(std::move(iterImpl));
750}
751
752////////////////////////////////////////////////////////////////////////////////
753/// Create an iterator for this list.
754/// \param forward Run in forward direction (default).
755/// \return RooLinkedListIter (subclass of TIterator) over this list
756
758 auto iterImpl = std::make_unique<RooLinkedListIterImpl>(this, forward);
759 return RooLinkedListIter(std::move(iterImpl));
760}
761
762////////////////////////////////////////////////////////////////////////////////
763/// Create a one-time-use forward iterator for this list.
764/// \return RooFIter that only supports next()
765
767 auto iterImpl = std::make_unique<RooFIterForLinkedList>(this);
768 return RooFIter(std::move(iterImpl));
769}
770
771////////////////////////////////////////////////////////////////////////////////
772
774{
775 if (ascend) _first = mergesort_impl<true>(_first, _size, &_last);
776 else _first = mergesort_impl<false>(_first, _size, &_last);
777
778 // rebuild index array
780 for (auto it = _at.begin(); it != _at.end(); ++it, elem = elem->_next) {
781 *it = elem;
782 }
783}
784
785////////////////////////////////////////////////////////////////////////////////
786/// length 0, 1 lists are sorted
787
788template <bool ascending>
790 RooLinkedListElem* l1, const unsigned sz, RooLinkedListElem** tail)
791{
792 if (!l1 || sz < 2) {
793 // if desired, update the tail of the (newly merged sorted) list
794 if (tail) *tail = l1;
795 return l1;
796 }
797 if (sz <= 16) {
798 // for short lists, we sort in an array
799#if !defined(_WIN32) && !defined(R__SOLARIS_CC50)
800 RooLinkedListElem *arr[sz];
801#else // _WIN32 && Solaris
802 // apparently, MSVC is not clever enough to figure out that sz cannot be
803 // zero and is at most sixteen, so we allocate a fixed size array on the
804 // stack instead
805 RooLinkedListElem *arr[16];
806#endif // _WIN32
807 for (int i = 0; l1; l1 = l1->_next, ++i) arr[i] = l1;
808 // straight insertion sort
809 {
810 int i = 1;
811 do {
812 int j = i - 1;
813 RooLinkedListElem *tmp = arr[i];
814 while (0 <= j) {
815 const bool inOrder = ascending ?
816 (tmp->_arg->Compare(arr[j]->_arg) <= 0) :
817 (arr[j]->_arg->Compare(tmp->_arg) <= 0);
818 if (!inOrder) break;
819 arr[j + 1] = arr[j];
820 --j;
821 }
822 arr[j + 1] = tmp;
823 ++i;
824 } while (int(sz) != i);
825 }
826 // link elements in array
827 arr[0]->_prev = arr[sz - 1]->_next = 0;
828 for (int i = 0; i < int(sz - 1); ++i) {
829 arr[i]->_next = arr[i + 1];
830 arr[i + 1]->_prev = arr[i];
831 }
832 if (tail) *tail = arr[sz - 1];
833 return arr[0];
834 }
835 // find middle of l1, and let a second list l2 start there
836 RooLinkedListElem *l2 = l1;
837 for (RooLinkedListElem *end = l2; end->_next; end = end->_next) {
838 end = end->_next;
839 l2 = l2->_next;
840 if (!end->_next) break;
841 }
842 // disconnect the two sublists
843 l2->_prev->_next = 0;
844 l2->_prev = 0;
845 // sort the two sublists (only recurse if we have to)
846 if (l1->_next) l1 = mergesort_impl<ascending>(l1, sz / 2);
847 if (l2->_next) l2 = mergesort_impl<ascending>(l2, sz - sz / 2);
848 // merge the two (sorted) sublists
849 // l: list head, t: list tail of merged list
850 RooLinkedListElem *l = (ascending ? (l1->_arg->Compare(l2->_arg) <= 0) :
851 (l2->_arg->Compare(l1->_arg) <= 0)) ? l1 : l2;
852 RooLinkedListElem *t = l;
853 if (l == l2) {
854 RooLinkedListElem* tmp = l1;
855 l1 = l2;
856 l2 = tmp;
857 }
858 l1 = l1->_next;
859 while (l1 && l2) {
860 const bool inOrder = ascending ? (l1->_arg->Compare(l2->_arg) <= 0) :
861 (l2->_arg->Compare(l1->_arg) <= 0);
862 if (!inOrder) {
863 // insert l2 just before l1
864 if (l1->_prev) {
865 l1->_prev->_next = l2;
866 l2->_prev = l1->_prev;
867 }
868 // swap l2 and l1
869 RooLinkedListElem *tmp = l1;
870 l1 = l2;
871 l2 = tmp;
872 }
873 // move forward in l1
874 t = l1;
875 l1 = l1->_next;
876 }
877 // attach l2 at t
878 if (l2) {
879 l2->_prev = t;
880 if (t) t->_next = l2;
881 }
882 // if desired, update the tail of the (newly merged sorted) list
883 if (tail) {
884 for (l1 = t; l1; l1 = l1->_next) t = l1;
885 *tail = t;
886 }
887 // return the head of the sorted list
888 return l;
889}
890// void Roo1DTable::Streamer(TBuffer &R__b)
891// {
892// // Stream an object of class Roo1DTable.
893
894// if (R__b.IsReading()) {
895// R__b.ReadClassBuffer(Roo1DTable::Class(),this);
896// } else {
897// R__b.WriteClassBuffer(Roo1DTable::Class(),this);
898// }
899// }
900
901////////////////////////////////////////////////////////////////////////////////
902/// Custom streaming handling schema evolution w.r.t past implementations
903
904void RooLinkedList::Streamer(TBuffer &R__b)
905{
906 if (R__b.IsReading()) {
907
908 Version_t v = R__b.ReadVersion();
909 //R__b.ReadVersion();
910 TObject::Streamer(R__b);
911
912 Int_t size ;
913 TObject* arg ;
914
915 R__b >> size ;
916 while(size--) {
917 R__b >> arg ;
918 Add(arg) ;
919 }
920
921 if (v > 1 && v < 4) {
922 R__b >> _name;
923 }
924
925 } else {
926 R__b.WriteVersion(RooLinkedList::IsA());
927 TObject::Streamer(R__b);
928 R__b << _size ;
929
931 while(ptr) {
932 R__b << ptr->_arg ;
933 ptr = ptr->_next ;
934 }
935
936 R__b << _name ;
937 }
938}
939
#define c(i)
Definition RSha256.hxx:101
#define a(i)
Definition RSha256.hxx:99
#define coutE(a)
int Int_t
Definition RtypesCore.h:45
short Version_t
Definition RtypesCore.h:65
const Bool_t kFALSE
Definition RtypesCore.h:92
const Bool_t kTRUE
Definition RtypesCore.h:91
const char Option_t
Definition RtypesCore.h:66
#define ClassImp(name)
Definition Rtypes.h:364
char name[80]
Definition TGX11.cxx:110
Binding & operator=(OUT(*fun)(void))
#define free
Definition civetweb.c:1539
RooAbsArg is the common abstract base class for objects that represent a value and a "shape" in RooFi...
Definition RooAbsArg.h:72
const TNamed * namePtr() const
Definition RooAbsArg.h:550
A one-time forward iterator working on RooLinkedList or RooAbsCollection.
RooHashTable implements a hash table for TObjects.
Bool_t remove(TObject *arg, TObject *hashArg=0)
Remove given object from table.
Int_t size() const
RooLinkedListElem * findLinkTo(const TObject *arg) const
Return RooLinkedList element link to object 'hashArg'.
Bool_t replace(const TObject *oldArg, const TObject *newArg, const TObject *oldHashArg=0)
Replace oldArg with newArg in the table.
TObject * find(const char *name) const
Return the object with given name from the table.
void add(TObject *arg, TObject *hashArg=0)
Add given object to table.
RooAbsArg * findArg(const RooAbsArg *arg) const
RooLinkedListElem is an link element for the RooLinkedList class.
void init(TObject *arg, RooLinkedListElem *after=0)
RooLinkedListElem * _prev
RooLinkedListElem * _next
A wrapper around TIterator derivatives.
RooLinkedList is an collection class for internal use, storing a collection of RooAbsArg pointers in ...
TObject * FindObject(const char *name) const
Return pointer to obejct with given name.
static Pool * _pool
shared memory pool for allocation of RooLinkedListElems
TString _name
Hash table by link pointer.
RooLinkedListImplDetails::Pool Pool
memory pool for quick allocation of RooLinkedListElems
std::vector< RooLinkedListElem * > _at
RooLinkedListIter iterator(Bool_t forward=kTRUE) const
Create an iterator for this list.
RooHashTable * _htableName
Link to last element of list.
RooLinkedListElem * createElement(TObject *obj, RooLinkedListElem *elem=0)
cout << "RooLinkedList::createElem(" << this << ") obj = " << obj << " elem = " << elem << endl ;
RooLinkedList(Int_t htsize=0)
RooHashTable * _htableLink
Hash table by name.
void Sort(Bool_t ascend=kTRUE)
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 Print(const char *opt) const
Print contents of list, defers to Print() function of contained objects.
TIterator * MakeIterator(Bool_t forward=kTRUE) const
Create a TIterator for this list.
static RooLinkedListElem * mergesort_impl(RooLinkedListElem *l1, const unsigned sz, RooLinkedListElem **tail=0)
length 0, 1 lists are sorted
TObject * At(Int_t index) const
Return object stored in sequential position given by index.
RooAbsArg * findArg(const RooAbsArg *) const
Return pointer to object with given name in collection.
void Delete(Option_t *o=0)
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 RecursiveRemove(TObject *obj)
If one of the TObject we have a referenced to is deleted, remove the reference.
virtual void Add(TObject *arg)
RooLinkedListElem * _last
Link to first element of list.
void setHashTableSize(Int_t size)
Change the threshold for hash-table use to given size.
void Clear(Option_t *o=0)
Remove all elements from collection.
Bool_t Replace(const TObject *oldArg, const TObject *newArg)
Replace object 'oldArg' in collection with new object 'newArg'.
RooLinkedListElem * _first
virtual Bool_t Remove(TObject *arg)
Remove object from collection.
Int_t IndexOf(const char *name) const
Return position of given object in list.
virtual ~RooLinkedList()
Destructor.
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
virtual Version_t ReadVersion(UInt_t *start=0, UInt_t *bcnt=0, const TClass *cl=0)=0
Bool_t IsReading() const
Definition TBuffer.h:86
virtual UInt_t WriteVersion(const TClass *cl, Bool_t useBcnt=kFALSE)=0
Iterator abstract base class.
Definition TIterator.h:30
The TNamed class is the base class for all named ROOT classes.
Definition TNamed.h:29
Mother of all ROOT objects.
Definition TObject.h:37
virtual const char * GetName() const
Returns name of object.
Definition TObject.cxx:359
R__ALWAYS_INLINE Bool_t TestBit(UInt_t f) const
Definition TObject.h:187
virtual Int_t Compare(const TObject *obj) const
Compare abstract method.
Definition TObject.cxx:161
virtual void Print(Option_t *option="") const
This method must be overridden when a class wants to print itself.
Definition TObject.cxx:552
void CallRecursiveRemoveIfNeeded(TObject &obj)
call RecursiveRemove for obj if gROOT is valid and obj.TestBit(kMustCleanup) is true.
Definition TROOT.h:395
auto * l
Definition textangle.C:4