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