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
46using std::cout, std::endl;
47
49
50/// \cond ROOFIT_INTERNAL
51
52namespace RooLinkedListImplDetails {
53 /// a chunk of memory in a pool for quick allocation of RooLinkedListElems
54 class Chunk {
55 public:
56 /// constructor
57 Chunk(Int_t sz) :
58 _sz(sz), _free(capacity()),
59 _chunk(new RooLinkedListElem[_free]), _freelist(_chunk)
60 {
61 //cout << "RLLID::Chunk ctor(" << this << ") of size " << _free << " list elements" << endl ;
62 // initialise free list
63 for (Int_t i = 0; i < _free; ++i)
64 _chunk[i]._next = (i + 1 < _free) ? &_chunk[i + 1] : nullptr;
65 }
66 /// forbid copying
67 Chunk(const Chunk&) = delete;
68 // forbid assignment
69 Chunk& operator=(const Chunk&) = delete;
70 /// destructor
71 ~Chunk() { delete[] _chunk; }
72 /// chunk capacity
73 Int_t capacity() const
74 { return (1 << _sz) / sizeof(RooLinkedListElem); }
75 /// chunk free elements
76 Int_t free() const { return _free; }
77 /// chunk occupied elements
78 Int_t size() const { return capacity() - free(); }
79 /// return size class
80 int szclass() const { return _sz; }
81 /// chunk full?
82 bool full() const { return !free(); }
83 /// chunk empty?
84 bool empty() const { return capacity() == free(); }
85 /// return address of chunk
86 const void* chunkaddr() const { return _chunk; }
87 /// check if el is in this chunk
88 bool contains(RooLinkedListElem* el) const
89 { return _chunk <= el && el < &_chunk[capacity()]; }
90 /// pop a free element off the free list
91 RooLinkedListElem* pop_free_elem()
92 {
93 if (!_freelist) return nullptr;
94 RooLinkedListElem* retVal = _freelist;
95 _freelist = retVal->_next;
96 retVal->_arg = nullptr; retVal->_refCount = 0;
97 retVal->_prev = retVal->_next = nullptr;
98 --_free;
99 return retVal;
100 }
101 /// push a free element back onto the freelist
102 void push_free_elem(RooLinkedListElem* el)
103 {
104 el->_next = _freelist;
105 _freelist = el;
106 ++_free;
107 }
108 private:
109 Int_t _sz; ///< chunk capacity
110 Int_t _free; ///< length of free list
111 RooLinkedListElem* _chunk; ///< chunk from which elements come
112 RooLinkedListElem* _freelist; ///< list of free elements
113 };
114
115 class Pool {
116 private:
117 enum {
118 minsz = 7, ///< minimum chunk size (just below 1 << minsz bytes)
119 maxsz = 18, ///< maximum chunk size (just below 1 << maxsz bytes)
120 szincr = 1 ///< size class increment (sz = 1 << (minsz + k * szincr))
121 };
122 /// a chunk of memory in the pool
123 typedef RooLinkedListImplDetails::Chunk Chunk;
124 typedef std::list<Chunk*> ChunkList;
125 typedef std::map<const void*, Chunk*> AddrMap;
126 public:
127 /// constructor
128 Pool();
129 /// destructor
130 ~Pool();
131 /// acquire the pool
132 inline void acquire() { ++_refCount; }
133 /// release the pool, return true if the pool is unused
134 inline bool release() { return 0 == --_refCount; }
135 /// pop a free element out of the pool
136 RooLinkedListElem* pop_free_elem();
137 /// push a free element back into the pool
138 void push_free_elem(RooLinkedListElem* el);
139 private:
140 AddrMap _addrmap;
141 ChunkList _freelist;
142 UInt_t _szmap[(maxsz - minsz) / szincr];
143 Int_t _cursz = minsz;
144 UInt_t _refCount = 0;
145
146 /// adjust _cursz to current largest block
147 void updateCurSz(Int_t sz, Int_t incr);
148 /// find size of next chunk to allocate (in a hopefully smart way)
149 Int_t nextChunkSz() const;
150 };
151
152 Pool::Pool()
153 {
154 std::fill(_szmap, _szmap + ((maxsz - minsz) / szincr), 0);
155 }
156
157 Pool::~Pool()
158 {
159 _freelist.clear();
160 for (AddrMap::iterator it = _addrmap.begin(); _addrmap.end() != it; ++it)
161 delete it->second;
162 _addrmap.clear();
163 }
164
165 RooLinkedListElem* Pool::pop_free_elem()
166 {
167 if (_freelist.empty()) {
168 // allocate and register new chunk and put it on the freelist
169 const Int_t sz = nextChunkSz();
170 Chunk *c = new Chunk(sz);
171 _addrmap[c->chunkaddr()] = c;
172 _freelist.push_back(c);
173 updateCurSz(sz, +1);
174 }
175 // get free element from first chunk on _freelist
176 Chunk* c = _freelist.front();
177 RooLinkedListElem* retVal = c->pop_free_elem();
178 // full chunks are removed from _freelist
179 if (c->full()) _freelist.pop_front();
180 return retVal;
181 }
182
183 void Pool::push_free_elem(RooLinkedListElem* el)
184 {
185 // find from which chunk el came
186 AddrMap::iterator ci = _addrmap.end();
187 if (!_addrmap.empty()) {
188 ci = _addrmap.lower_bound(el);
189 if (ci == _addrmap.end()) {
190 // point beyond last element, so get last one
191 ci = (++_addrmap.rbegin()).base();
192 } else {
193 // valid ci, check if we need to decrement ci because el isn't the
194 // first element in the chunk
195 if (_addrmap.begin() != ci && ci->first != el) --ci;
196 }
197 }
198 // either empty addressmap, or ci should now point to the chunk which might
199 // contain el
200 if (_addrmap.empty() || !ci->second->contains(el)) {
201 // el is not in any chunk we know about, so just delete it
202 delete el;
203 return;
204 }
205 Chunk *c = ci->second;
206 const bool moveToFreelist = c->full();
207 c->push_free_elem(el);
208 if (c->empty()) {
209 // delete chunk if all empty
210 ChunkList::iterator it = std::find( _freelist.begin(), _freelist.end(), c);
211 if (_freelist.end() != it) _freelist.erase(it);
212 _addrmap.erase(ci->first);
213 updateCurSz(c->szclass(), -1);
214 delete c;
215 } else if (moveToFreelist) {
216 _freelist.push_back(c);
217 }
218 }
219
220 void Pool::updateCurSz(Int_t sz, Int_t incr)
221 {
222 _szmap[(sz - minsz) / szincr] += incr;
223 _cursz = minsz;
224 for (int i = (maxsz - minsz) / szincr; i--; ) {
225 if (_szmap[i]) {
226 _cursz += i * szincr;
227 break;
228 }
229 }
230 }
231
232 Int_t Pool::nextChunkSz() const
233 {
234 // no chunks with space available, figure out chunk size
235 Int_t sz = _cursz;
236 if (_addrmap.empty()) {
237 // if we start allocating chunks, we start from minsz
238 sz = minsz;
239 } else {
240 if (minsz >= sz) {
241 // minimal sized chunks are always grown
242 sz = minsz + szincr;
243 } else {
244 if (1 != _addrmap.size()) {
245 // if we have more than one completely filled chunk, grow
246 sz += szincr;
247 } else {
248 // just one chunk left, try shrinking chunk size
249 sz -= szincr;
250 }
251 }
252 }
253 // clamp size to allowed range
254 if (sz > maxsz) sz = maxsz;
255 if (sz < minsz) sz = minsz;
256 return sz;
257 }
258}
259
260/// \endcond
261
263
264////////////////////////////////////////////////////////////////////////////////
265
267 _hashThresh(htsize), _size(0), _first(nullptr), _last(nullptr), _htableName(nullptr), _htableLink(nullptr), _useNptr(true)
268{
269 if (!_pool) _pool = new Pool;
270 _pool->acquire();
271}
272
273////////////////////////////////////////////////////////////////////////////////
274/// Copy constructor
275
277 TObject(other), _hashThresh(other._hashThresh), _size(0), _first(nullptr), _last(nullptr), _htableName(nullptr), _htableLink(nullptr),
278 _name(other._name),
279 _useNptr(other._useNptr)
280{
281 if (!_pool) _pool = new Pool;
282 _pool->acquire();
283 if (other._htableName) _htableName = std::make_unique<HashTableByName>(other._htableName->size()) ;
284 if (other._htableLink) _htableLink = std::make_unique<HashTableByLink>(other._htableLink->size()) ;
285 for (RooLinkedListElem* elem = other._first; elem; elem = elem->_next) {
286 Add(elem->_arg, elem->_refCount) ;
287 }
288}
289
290////////////////////////////////////////////////////////////////////////////////
291/// cout << "RooLinkedList::createElem(" << this << ") obj = " << obj << " elem = " << elem << endl ;
292
294{
295 RooLinkedListElem* ret = _pool->pop_free_elem();
296 ret->init(obj, elem);
297 return ret ;
298}
299
300////////////////////////////////////////////////////////////////////////////////
301
303{
304 elem->release() ;
305 _pool->push_free_elem(elem);
306 //delete elem ;
307}
308
309////////////////////////////////////////////////////////////////////////////////
310/// Assignment operator, copy contents from 'other'
311
313{
314 // Prevent self-assignment
315 if (&other==this) return *this ;
316
317 // remove old elements
318 Clear();
319 // Copy elements
320 for (RooLinkedListElem* elem = other._first; elem; elem = elem->_next) {
321 Add(elem->_arg) ;
322 }
323
324 return *this ;
325}
326
327////////////////////////////////////////////////////////////////////////////////
328/// Change the threshold for hash-table use to given size.
329/// If a hash table exists when this method is called, it is regenerated.
330
332{
333 if (size<0) {
334 coutE(InputArguments) << "RooLinkedList::setHashTable() ERROR size must be positive" << endl ;
335 return ;
336 }
337 if (size==0) {
338 if (!_htableName) {
339 // No hash table present
340 return ;
341 } else {
342 // Remove existing hash table
343 _htableName.reset();
344 _htableLink.reset();
345 }
346 } else {
347
348 // (Re)create hash tables
349 _htableName = std::make_unique<HashTableByName>(size) ;
350 _htableLink = std::make_unique<HashTableByLink>(size) ;
351
352 // Fill hash table with existing entries
354 while(ptr) {
355 _htableName->insert({ptr->_arg->GetName(), ptr->_arg}) ;
356 _htableLink->insert({ptr->_arg, reinterpret_cast<TObject*>(ptr)}) ;
357 ptr = ptr->_next ;
358 }
359 }
360}
361
362////////////////////////////////////////////////////////////////////////////////
363/// Destructor
364
366{
367 // Required since we overload TObject::Hash.
369
370 _htableName.reset();
371 _htableLink.reset();
372
373 Clear() ;
374 if (_pool->release()) {
375 delete _pool;
376 _pool = nullptr;
377 }
378}
379
380////////////////////////////////////////////////////////////////////////////////
381/// Find the element link containing the given object
382
384{
385 if (_htableLink) {
386 auto found = _htableLink->find(arg);
387 if (found == _htableLink->end()) return nullptr;
388 return const_cast<RooLinkedListElem *>(reinterpret_cast<RooLinkedListElem const*>(found->second));
389 }
390
392 while(ptr) {
393 if (ptr->_arg == arg) {
394 return ptr ;
395 }
396 ptr = ptr->_next ;
397 }
398 return nullptr ;
399
400}
401
402////////////////////////////////////////////////////////////////////////////////
403/// Insert object into collection with given reference count value
404
405void RooLinkedList::Add(TObject* arg, Int_t refCount)
406{
407 if (!arg) return ;
408
409 // Only use RooAbsArg::namePtr() in lookup-by-name if all elements have it
410 if (!dynamic_cast<RooAbsArg*>(arg) && !dynamic_cast<RooAbsData*>(arg)) _useNptr = false;
411
412 // Add to hash table
413 if (_htableName) {
414
415 // Expand capacity of hash table if #entries>#slots
416 if (static_cast<size_t>(_size) > _htableName->size()) {
418 }
419
420 } else if (_hashThresh>0 && _size>_hashThresh) {
421
423 }
424
425 if (_last) {
426 // Append element at end of list
427 _last = createElement(arg,_last) ;
428 } else {
429 // Append first element, set first,last
430 _last = createElement(arg) ;
431 _first=_last ;
432 }
433
434 if (_htableName){
435 //cout << "storing link " << _last << " with hash arg " << arg << endl ;
436 _htableName->insert({arg->GetName(), arg});
437 _htableLink->insert({arg, reinterpret_cast<TObject *>(_last)});
438 }
439
440 _size++ ;
441 _last->_refCount = refCount ;
442
443 _at.push_back(_last);
444}
445
446////////////////////////////////////////////////////////////////////////////////
447/// Remove object from collection
448
450{
451 // Find link element
452 RooLinkedListElem* elem = findLink(arg) ;
453 if (!elem) return false ;
454
455 // Remove from hash table
456 if (_htableName) {
457 _htableName->erase(arg->GetName()) ;
458 }
459 if (_htableLink) {
460 _htableLink->erase(arg) ;
461 }
462
463 // Update first,last if necessary
464 if (elem==_first) _first=elem->_next ;
465 if (elem==_last) _last=elem->_prev ;
466
467 // Remove from index array
468 auto at_elem_it = std::find(_at.begin(), _at.end(), elem);
469 _at.erase(at_elem_it);
470
471 // Delete and shrink
472 _size-- ;
473 deleteElement(elem) ;
474 return true ;
475}
476
477////////////////////////////////////////////////////////////////////////////////
478/// If one of the TObject we have a referenced to is deleted, remove the
479/// reference.
480
482{
483 Remove(obj); // This is a nop if the obj is not in the collection.
484}
485
486////////////////////////////////////////////////////////////////////////////////
487/// Return object stored in sequential position given by index.
488/// If index is out of range, a null pointer is returned.
489
491{
492 // Check range
493 if (index<0 || index>=_size) return nullptr ;
494
495 return _at[index]->_arg;
496//
497//
498// // Walk list
499// RooLinkedListElem* ptr = _first;
500// while(index--) ptr = ptr->_next ;
501//
502// // Return arg
503// return ptr->_arg ;
504}
505
506////////////////////////////////////////////////////////////////////////////////
507/// Replace object 'oldArg' in collection with new object 'newArg'.
508/// If 'oldArg' is not found in collection false is returned
509
510bool RooLinkedList::Replace(const TObject* oldArg, const TObject* newArg)
511{
512 // Find existing element and replace arg
513 RooLinkedListElem* elem = findLink(oldArg) ;
514 if (!elem) return false ;
515
516 if (_htableName) {
517 _htableName->erase(oldArg->GetName());
518 _htableName->insert({newArg->GetName(), newArg});
519 }
520 if (_htableLink) {
521 // Link is hashed by contents and may change slot in hash table
522 _htableLink->erase(oldArg) ;
523 _htableLink->insert({newArg, reinterpret_cast<TObject*>(elem)}) ;
524 }
525
526 elem->_arg = const_cast<TObject*>(newArg);
527 return true ;
528}
529
530////////////////////////////////////////////////////////////////////////////////
531/// Return pointer to object with given name. If no such object
532/// is found return a null pointer.
533
535{
536 return find(name) ;
537}
538
539////////////////////////////////////////////////////////////////////////////////
540/// Find object in list. If list contains object return
541/// (same) pointer to object, otherwise return null pointer
542
544{
545 RooLinkedListElem *elem = findLink(const_cast<TObject*>(obj));
546 return elem ? elem->_arg : nullptr ;
547}
548
549////////////////////////////////////////////////////////////////////////////////
550/// Remove all elements from collection
551
553{
554 for (RooLinkedListElem *elem = _first, *next; elem; elem = next) {
555 next = elem->_next ;
556 deleteElement(elem) ;
557 }
558 _first = nullptr ;
559 _last = nullptr ;
560 _size = 0 ;
561
562 if (_htableName) {
563 _htableName = std::make_unique<HashTableByName>(_htableName->size()) ;
564 }
565 if (_htableLink) {
566 _htableLink = std::make_unique<HashTableByLink>(_htableLink->size()) ;
567 }
568
569 // empty index array
570 _at.clear();
571}
572
573////////////////////////////////////////////////////////////////////////////////
574/// Remove all elements in collection and delete all elements
575/// NB: Collection does not own elements, this function should
576/// be used judiciously by caller.
577
579{
581 while(elem) {
582 RooLinkedListElem* next = elem->_next ;
583 delete elem->_arg ;
584 deleteElement(elem) ;
585 elem = next ;
586 }
587 _first = nullptr ;
588 _last = nullptr ;
589 _size = 0 ;
590
591 if (_htableName) {
592 _htableName = std::make_unique<HashTableByName>(_htableName->size()) ;
593 }
594 if (_htableLink) {
595 _htableLink = std::make_unique<HashTableByLink>(_htableLink->size()) ;
596 }
597
598 // empty index array
599 _at.clear();
600}
601
602////////////////////////////////////////////////////////////////////////////////
603/// Return pointer to object with given name in collection.
604/// If no such object is found, return null pointer.
605
607{
608
609 if (_htableName) {
610 auto found = _htableName->find(name);
611 TObject *a = found != _htableName->end() ? const_cast<TObject*>(found->second) : nullptr;
612 // RooHashTable::find could return false negative if element was renamed to 'name'.
613 // The list search means it won't return false positive, so can return here.
614 if (a) return a;
615 if (_useNptr) {
616 // See if it might have been renamed
617 const TNamed* nptr= RooNameReg::known(name);
618 //cout << "RooLinkedList::find: possibly renamed '" << name << "', kRenamedArg=" << (nptr&&nptr->TestBit(RooNameReg::kRenamedArg)) << endl;
619 if (nptr && nptr->TestBit(RooNameReg::kRenamedArg)) {
621 while(ptr) {
622 if ( (dynamic_cast<RooAbsArg*>(ptr->_arg) && static_cast<RooAbsArg*>(ptr->_arg)->namePtr() == nptr) ||
623 (dynamic_cast<RooAbsData*>(ptr->_arg) && static_cast<RooAbsData*>(ptr->_arg)->namePtr() == nptr)) {
624 return ptr->_arg ;
625 }
626 ptr = ptr->_next ;
627 }
628 }
629 return nullptr ;
630 }
631 //cout << "RooLinkedList::find: possibly renamed '" << name << "'" << endl;
632 }
633
635
636 // The penalty for RooNameReg lookup seems to be outweighted by the faster search
637 // when the size list is longer than ~7, but let's be a bit conservative.
638 if (_useNptr && _size>9) {
639 const TNamed* nptr= RooNameReg::known(name);
640 if (!nptr) return nullptr;
641
642 while(ptr) {
643 if ( (dynamic_cast<RooAbsArg*>(ptr->_arg) && static_cast<RooAbsArg*>(ptr->_arg)->namePtr() == nptr) ||
644 (dynamic_cast<RooAbsData*>(ptr->_arg) && static_cast<RooAbsData*>(ptr->_arg)->namePtr() == nptr)) {
645 return ptr->_arg ;
646 }
647 ptr = ptr->_next ;
648 }
649 return nullptr ;
650 }
651
652 while(ptr) {
653 if (!strcmp(ptr->_arg->GetName(),name)) {
654 return ptr->_arg ;
655 }
656 ptr = ptr->_next ;
657 }
658 return nullptr ;
659}
660
661////////////////////////////////////////////////////////////////////////////////
662/// Return pointer to object with given name in collection.
663/// If no such object is found, return null pointer.
664
666{
667 if (_htableName) {
668 RooAbsArg* a = const_cast<RooAbsArg *>(static_cast<RooAbsArg const*>((*_htableName)[arg->GetName()]));
669 if (a) return a;
670 //cout << "RooLinkedList::findArg: possibly renamed '" << arg->GetName() << "', kRenamedArg=" << arg->namePtr()->TestBit(RooNameReg::kRenamedArg) << endl;
671 // See if it might have been renamed
672 if (!arg->namePtr()->TestBit(RooNameReg::kRenamedArg)) return nullptr;
673 }
674
676 const TNamed* nptr = arg->namePtr();
677 while(ptr) {
678 if ((static_cast<RooAbsArg*>(ptr->_arg))->namePtr() == nptr) {
679 return static_cast<RooAbsArg*>(ptr->_arg) ;
680 }
681 ptr = ptr->_next ;
682 }
683 return nullptr ;
684}
685
686////////////////////////////////////////////////////////////////////////////////
687/// Return position of given object in list. If object
688/// is not contained in list, return -1
689
691{
693 Int_t idx(0) ;
694 while(ptr) {
695 if (ptr->_arg==arg) return idx ;
696 ptr = ptr->_next ;
697 idx++ ;
698 }
699 return -1 ;
700}
701
702////////////////////////////////////////////////////////////////////////////////
703/// Return position of given object in list. If object
704/// is not contained in list, return -1
705
707{
709 Int_t idx(0) ;
710 while(ptr) {
711 if (strcmp(ptr->_arg->GetName(),name)==0) return idx ;
712 ptr = ptr->_next ;
713 idx++ ;
714 }
715 return -1 ;
716}
717
718////////////////////////////////////////////////////////////////////////////////
719/// Print contents of list, defers to Print() function
720/// of contained objects
721
722void RooLinkedList::Print(const char* opt) const
723{
724 RooLinkedListElem* elem = _first ;
725 while(elem) {
726 cout << elem->_arg << " : " ;
727 elem->_arg->Print(opt) ;
728 elem = elem->_next ;
729 }
730}
731
732////////////////////////////////////////////////////////////////////////////////
733/// Create a TIterator for this list.
734/// \param forward Run in forward direction (default).
735/// \return Pointer to a TIterator. The caller owns the pointer.
736
738 auto iterImpl = std::make_unique<RooLinkedListIterImpl>(this, forward);
739 return new RooLinkedListIter(std::move(iterImpl));
740}
741
742////////////////////////////////////////////////////////////////////////////////
743/// Create an iterator for this list.
744/// \param forward Run in forward direction (default).
745/// \return RooLinkedListIter (subclass of TIterator) over this list
746
748 auto iterImpl = std::make_unique<RooLinkedListIterImpl>(this, forward);
749 return RooLinkedListIter(std::move(iterImpl));
750}
751
752////////////////////////////////////////////////////////////////////////////////
753/// Create a one-time-use forward iterator for this list.
754/// \return RooFIter that only supports next()
755
757 auto iterImpl = std::make_unique<RooFIterForLinkedList>(this);
758 return RooFIter(std::move(iterImpl));
759}
760
762 return {this, true};
763}
764
766 return {this, nullptr, true};
767}
768
770 return {this, false};
771}
772
774 return {this, nullptr, false};
775}
776
777////////////////////////////////////////////////////////////////////////////////
778
779void RooLinkedList::Sort(bool ascend)
780{
781 if (ascend) _first = mergesort_impl<true>(_first, _size, &_last);
782 else _first = mergesort_impl<false>(_first, _size, &_last);
783
784 // rebuild index array
786 for (auto it = _at.begin(); it != _at.end(); ++it, elem = elem->_next) {
787 *it = elem;
788 }
789}
790
791////////////////////////////////////////////////////////////////////////////////
792/// length 0, 1 lists are sorted
793
794template <bool ascending>
796 RooLinkedListElem* l1, const unsigned sz, RooLinkedListElem** tail)
797{
798 if (!l1 || sz < 2) {
799 // if desired, update the tail of the (newly merged sorted) list
800 if (tail) *tail = l1;
801 return l1;
802 }
803 if (sz <= 16) {
804 // for short lists, we sort in an array
805 std::vector<RooLinkedListElem *> arr(sz, nullptr);
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 = nullptr;
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 = nullptr;
843 l2->_prev = nullptr;
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
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 {
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}
#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)
bool _first
!
Definition RooNLLVar.h:46
int Int_t
Definition RtypesCore.h:45
short Version_t
Definition RtypesCore.h:65
const char Option_t
Definition RtypesCore.h:66
#define ClassImp(name)
Definition Rtypes.h:377
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:1539
Common abstract base class for objects that represent a value and a "shape" in RooFit.
Definition RooAbsArg.h:77
const TNamed * namePtr() const
De-duplicated pointer to this object's name.
Definition RooAbsArg.h:561
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:297
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
void init(TObject *arg, RooLinkedListElem *after=nullptr)
RooLinkedListElem * _prev
Link to previous element in list.
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)
cout << "RooLinkedList::createElem(" << this << ") obj = " << obj << " elem = " << elem << endl ;
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
virtual Version_t ReadVersion(UInt_t *start=nullptr, UInt_t *bcnt=nullptr, const TClass *cl=nullptr)=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
const char * GetName() const override
Returns name of object.
Definition TNamed.h:47
Mother of all ROOT objects.
Definition TObject.h:41
virtual const char * GetName() const
Returns name of object.
Definition TObject.cxx:439
R__ALWAYS_INLINE Bool_t TestBit(UInt_t f) const
Definition TObject.h:199
virtual void Streamer(TBuffer &)
Stream an object of class TObject.
Definition TObject.cxx:888
virtual Int_t Compare(const TObject *obj) const
Compare abstract method.
Definition TObject.cxx:238
virtual void Print(Option_t *option="") const
This method must be overridden when a class wants to print itself.
Definition TObject.cxx:636
void CallRecursiveRemoveIfNeeded(TObject &obj)
call RecursiveRemove for obj if gROOT is valid and obj.TestBit(kMustCleanup) is true.
Definition TROOT.h:396
TLine l
Definition textangle.C:4