Logo ROOT  
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 
22 RooLinkedList is an collection class for internal use, storing
23 a collection of RooAbsArg pointers in a doubly linked list.
24 It can optionally add a hash table to speed up random access
25 in large collections
26 Use 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 "RooAbsArg.h"
35 #include "RooMsgService.h"
36 
37 #include "Riostream.h"
38 #include "TBuffer.h"
39 #include "TROOT.h"
40 #include "ROOT/RMakeUnique.hxx"
41 
42 #include <algorithm>
43 #include <list>
44 #include <vector>
45 
46 using namespace std;
47 
49 ;
50 namespace RooLinkedListImplDetails {
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
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
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
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
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:
141  UInt_t _szmap[(maxsz - minsz) / szincr];
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 
157  {
158  _freelist.clear();
159  for (AddrMap::iterator it = _addrmap.begin(); _addrmap.end() != it; ++it)
160  delete it->second;
161  _addrmap.clear();
162  }
163 
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 
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 
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 
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(nullptr), _htableLink(nullptr), _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(nullptr), _htableLink(nullptr),
275  _name(other._name),
276  _useNptr(other._useNptr)
277 {
278  if (!_pool) _pool = new Pool;
279  _pool->acquire();
280  if (other._htableName) _htableName = std::make_unique<HashTableByName>(other._htableName->size()) ;
281  if (other._htableLink) _htableLink = std::make_unique<HashTableByLink>(other._htableLink->size()) ;
282  for (RooLinkedListElem* elem = other._first; elem; elem = elem->_next) {
283  Add(elem->_arg, elem->_refCount) ;
284  }
285 }
286 
287 ////////////////////////////////////////////////////////////////////////////////
288 /// cout << "RooLinkedList::createElem(" << this << ") obj = " << obj << " elem = " << elem << endl ;
289 
291 {
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  _htableName.reset(nullptr);
341  _htableLink.reset(nullptr);
342  }
343  } else {
344 
345  // (Re)create hash tables
346  _htableName = std::make_unique<HashTableByName>(size) ;
347  _htableLink = std::make_unique<HashTableByLink>(size) ;
348 
349  // Fill hash table with existing entries
350  RooLinkedListElem* ptr = _first ;
351  while(ptr) {
352  _htableName->insert({ptr->_arg->GetName(), ptr->_arg}) ;
353  _htableLink->insert({ptr->_arg, (TObject*)ptr}) ;
354  ptr = ptr->_next ;
355  }
356  }
357 }
358 
359 ////////////////////////////////////////////////////////////////////////////////
360 /// Destructor
361 
363 {
364  // Required since we overload TObject::Hash.
366 
367  _htableName.reset(nullptr);
368  _htableLink.reset(nullptr);
369 
370  Clear() ;
371  if (_pool->release()) {
372  delete _pool;
373  _pool = 0;
374  }
375 }
376 
377 ////////////////////////////////////////////////////////////////////////////////
378 /// Find the element link containing the given object
379 
381 {
382  if (_htableLink) {
383  auto found = _htableLink->find(arg);
384  if (found == _htableLink->end()) return nullptr;
385  return (RooLinkedListElem*)found->second;
386  }
387 
388  RooLinkedListElem* ptr = _first;
389  while(ptr) {
390  if (ptr->_arg == arg) {
391  return ptr ;
392  }
393  ptr = ptr->_next ;
394  }
395  return 0 ;
396 
397 }
398 
399 ////////////////////////////////////////////////////////////////////////////////
400 /// Insert object into collection with given reference count value
401 
402 void RooLinkedList::Add(TObject* arg, Int_t refCount)
403 {
404  if (!arg) return ;
405 
406  // Only use RooAbsArg::namePtr() in lookup-by-name if all elements have it
407  if (!dynamic_cast<RooAbsArg*>(arg)) _useNptr = kFALSE;
408 
409  // Add to hash table
410  if (_htableName) {
411 
412  // Expand capacity of hash table if #entries>#slots
413  if (static_cast<size_t>(_size) > _htableName->size()) {
415  }
416 
417  } else if (_hashThresh>0 && _size>_hashThresh) {
418 
420  }
421 
422  if (_last) {
423  // Append element at end of list
424  _last = createElement(arg,_last) ;
425  } else {
426  // Append first element, set first,last
427  _last = createElement(arg) ;
428  _first=_last ;
429  }
430 
431  if (_htableName){
432  //cout << "storing link " << _last << " with hash arg " << arg << endl ;
433  _htableName->insert({arg->GetName(), arg});
434  _htableLink->insert({arg, (TObject*)_last});
435  }
436 
437  _size++ ;
438  _last->_refCount = refCount ;
439 
440  _at.push_back(_last);
441 }
442 
443 ////////////////////////////////////////////////////////////////////////////////
444 /// Remove object from collection
445 
447 {
448  // Find link element
449  RooLinkedListElem* elem = findLink(arg) ;
450  if (!elem) return kFALSE ;
451 
452  // Remove from hash table
453  if (_htableName) {
454  _htableName->erase(arg->GetName()) ;
455  }
456  if (_htableLink) {
457  _htableLink->erase(arg) ;
458  }
459 
460  // Update first,last if necessary
461  if (elem==_first) _first=elem->_next ;
462  if (elem==_last) _last=elem->_prev ;
463 
464  // Remove from index array
465  auto at_elem_it = std::find(_at.begin(), _at.end(), elem);
466  _at.erase(at_elem_it);
467 
468  // Delete and shrink
469  _size-- ;
470  deleteElement(elem) ;
471  return kTRUE ;
472 }
473 
474 ////////////////////////////////////////////////////////////////////////////////
475 /// If one of the TObject we have a referenced to is deleted, remove the
476 /// reference.
477 
479 {
480  Remove(obj); // This is a nop if the obj is not in the collection.
481 }
482 
483 ////////////////////////////////////////////////////////////////////////////////
484 /// Return object stored in sequential position given by index.
485 /// If index is out of range, a null pointer is returned.
486 
488 {
489  // Check range
490  if (index<0 || index>=_size) return 0 ;
491 
492  return _at[index]->_arg;
493 //
494 //
495 // // Walk list
496 // RooLinkedListElem* ptr = _first;
497 // while(index--) ptr = ptr->_next ;
498 //
499 // // Return arg
500 // return ptr->_arg ;
501 }
502 
503 ////////////////////////////////////////////////////////////////////////////////
504 /// Replace object 'oldArg' in collection with new object 'newArg'.
505 /// If 'oldArg' is not found in collection kFALSE is returned
506 
507 Bool_t RooLinkedList::Replace(const TObject* oldArg, const TObject* newArg)
508 {
509  // Find existing element and replace arg
510  RooLinkedListElem* elem = findLink(oldArg) ;
511  if (!elem) return kFALSE ;
512 
513  if (_htableName) {
514  _htableName->erase(oldArg->GetName());
515  _htableName->insert({newArg->GetName(), newArg});
516  }
517  if (_htableLink) {
518  // Link is hashed by contents and may change slot in hash table
519  _htableLink->erase(oldArg) ;
520  _htableLink->insert({newArg, (TObject*)elem}) ;
521  }
522 
523  elem->_arg = (TObject*)newArg ;
524  return kTRUE ;
525 }
526 
527 ////////////////////////////////////////////////////////////////////////////////
528 /// Return pointer to obejct with given name. If no such object
529 /// is found return a null pointer
530 
532 {
533  return find(name) ;
534 }
535 
536 ////////////////////////////////////////////////////////////////////////////////
537 /// Find object in list. If list contains object return
538 /// (same) pointer to object, otherwise return null pointer
539 
541 {
542  RooLinkedListElem *elem = findLink((TObject*)obj) ;
543  return elem ? elem->_arg : 0 ;
544 }
545 
546 ////////////////////////////////////////////////////////////////////////////////
547 /// Remove all elements from collection
548 
550 {
551  for (RooLinkedListElem *elem = _first, *next; elem; elem = next) {
552  next = elem->_next ;
553  deleteElement(elem) ;
554  }
555  _first = 0 ;
556  _last = 0 ;
557  _size = 0 ;
558 
559  if (_htableName) {
560  _htableName = std::make_unique<HashTableByName>(_htableName->size()) ;
561  }
562  if (_htableLink) {
563  _htableLink = std::make_unique<HashTableByLink>(_htableLink->size()) ;
564  }
565 
566  // empty index array
567  _at.clear();
568 }
569 
570 ////////////////////////////////////////////////////////////////////////////////
571 /// Remove all elements in collection and delete all elements
572 /// NB: Collection does not own elements, this function should
573 /// be used judiciously by caller.
574 
576 {
577  RooLinkedListElem* elem = _first;
578  while(elem) {
579  RooLinkedListElem* next = elem->_next ;
580  delete elem->_arg ;
581  deleteElement(elem) ;
582  elem = next ;
583  }
584  _first = 0 ;
585  _last = 0 ;
586  _size = 0 ;
587 
588  if (_htableName) {
589  _htableName = std::make_unique<HashTableByName>(_htableName->size()) ;
590  }
591  if (_htableLink) {
592  _htableLink = std::make_unique<HashTableByLink>(_htableLink->size()) ;
593  }
594 
595  // empty index array
596  _at.clear();
597 }
598 
599 ////////////////////////////////////////////////////////////////////////////////
600 /// Return pointer to object with given name in collection.
601 /// If no such object is found, return null pointer.
602 
603 TObject* RooLinkedList::find(const char* name) const
604 {
605 
606  if (_htableName) {
607  RooAbsArg* a = (RooAbsArg*) (*_htableName)[name] ;
608  // RooHashTable::find could return false negative if element was renamed to 'name'.
609  // The list search means it won't return false positive, so can return here.
610  if (a) return a;
611  if (_useNptr) {
612  // See if it might have been renamed
613  const TNamed* nptr= RooNameReg::known(name);
614  //cout << "RooLinkedList::find: possibly renamed '" << name << "', kRenamedArg=" << (nptr&&nptr->TestBit(RooNameReg::kRenamedArg)) << endl;
615  if (nptr && nptr->TestBit(RooNameReg::kRenamedArg)) {
616  RooLinkedListElem* ptr = _first ;
617  while(ptr) {
618  if ((((RooAbsArg*)ptr->_arg)->namePtr() == nptr)) {
619  return ptr->_arg ;
620  }
621  ptr = ptr->_next ;
622  }
623  }
624  return 0 ;
625  }
626  //cout << "RooLinkedList::find: possibly renamed '" << name << "'" << endl;
627  }
628 
629  RooLinkedListElem* ptr = _first ;
630 
631  // The penalty for RooNameReg lookup seems to be outweighted by the faster search
632  // when the size list is longer than ~7, but let's be a bit conservative.
633  if (_useNptr && _size>9) {
634  const TNamed* nptr= RooNameReg::known(name);
635  if (!nptr) return 0;
636 
637  while(ptr) {
638  if ((((RooAbsArg*)ptr->_arg)->namePtr() == nptr)) {
639  return ptr->_arg ;
640  }
641  ptr = ptr->_next ;
642  }
643  return 0 ;
644  }
645 
646  while(ptr) {
647  if (!strcmp(ptr->_arg->GetName(),name)) {
648  return ptr->_arg ;
649  }
650  ptr = ptr->_next ;
651  }
652  return 0 ;
653 }
654 
655 ////////////////////////////////////////////////////////////////////////////////
656 /// Return pointer to object with given name in collection.
657 /// If no such object is found, return null pointer.
658 
660 {
661  if (_htableName) {
662  RooAbsArg* a = (RooAbsArg*) (*_htableName)[arg->GetName()] ;
663  if (a) return a;
664  //cout << "RooLinkedList::findArg: possibly renamed '" << arg->GetName() << "', kRenamedArg=" << arg->namePtr()->TestBit(RooNameReg::kRenamedArg) << endl;
665  // See if it might have been renamed
666  if (!arg->namePtr()->TestBit(RooNameReg::kRenamedArg)) return 0;
667  }
668 
669  RooLinkedListElem* ptr = _first ;
670  const TNamed* nptr = arg->namePtr();
671  while(ptr) {
672  if (((RooAbsArg*)(ptr->_arg))->namePtr() == nptr) {
673  return (RooAbsArg*) ptr->_arg ;
674  }
675  ptr = ptr->_next ;
676  }
677  return 0 ;
678 }
679 
680 ////////////////////////////////////////////////////////////////////////////////
681 /// Return position of given object in list. If object
682 /// is not contained in list, return -1
683 
685 {
686  RooLinkedListElem* ptr = _first;
687  Int_t idx(0) ;
688  while(ptr) {
689  if (ptr->_arg==arg) return idx ;
690  ptr = ptr->_next ;
691  idx++ ;
692  }
693  return -1 ;
694 }
695 
696 ////////////////////////////////////////////////////////////////////////////////
697 /// Return position of given object in list. If object
698 /// is not contained in list, return -1
699 
700 Int_t RooLinkedList::IndexOf(const char* name) const
701 {
702  RooLinkedListElem* ptr = _first;
703  Int_t idx(0) ;
704  while(ptr) {
705  if (strcmp(ptr->_arg->GetName(),name)==0) return idx ;
706  ptr = ptr->_next ;
707  idx++ ;
708  }
709  return -1 ;
710 }
711 
712 ////////////////////////////////////////////////////////////////////////////////
713 /// Print contents of list, defers to Print() function
714 /// of contained objects
715 
716 void RooLinkedList::Print(const char* opt) const
717 {
718  RooLinkedListElem* elem = _first ;
719  while(elem) {
720  cout << elem->_arg << " : " ;
721  elem->_arg->Print(opt) ;
722  elem = elem->_next ;
723  }
724 }
725 
726 ////////////////////////////////////////////////////////////////////////////////
727 /// Create a TIterator for this list.
728 /// \param forward Run in forward direction (default).
729 /// \return Pointer to a TIterator. The caller owns the pointer.
730 
732  auto iterImpl = std::make_unique<RooLinkedListIterImpl>(this, forward);
733  return new RooLinkedListIter(std::move(iterImpl));
734 }
735 
736 ////////////////////////////////////////////////////////////////////////////////
737 /// Create an iterator for this list.
738 /// \param forward Run in forward direction (default).
739 /// \return RooLinkedListIter (subclass of TIterator) over this list
740 
742  auto iterImpl = std::make_unique<RooLinkedListIterImpl>(this, forward);
743  return RooLinkedListIter(std::move(iterImpl));
744 }
745 
746 ////////////////////////////////////////////////////////////////////////////////
747 /// Create a one-time-use forward iterator for this list.
748 /// \return RooFIter that only supports next()
749 
751  auto iterImpl = std::make_unique<RooFIterForLinkedList>(this);
752  return RooFIter(std::move(iterImpl));
753 }
754 
755 ////////////////////////////////////////////////////////////////////////////////
756 
758 {
759  if (ascend) _first = mergesort_impl<true>(_first, _size, &_last);
760  else _first = mergesort_impl<false>(_first, _size, &_last);
761 
762  // rebuild index array
763  RooLinkedListElem* elem = _first;
764  for (auto it = _at.begin(); it != _at.end(); ++it, elem = elem->_next) {
765  *it = elem;
766  }
767 }
768 
769 ////////////////////////////////////////////////////////////////////////////////
770 /// length 0, 1 lists are sorted
771 
772 template <bool ascending>
774  RooLinkedListElem* l1, const unsigned sz, RooLinkedListElem** tail)
775 {
776  if (!l1 || sz < 2) {
777  // if desired, update the tail of the (newly merged sorted) list
778  if (tail) *tail = l1;
779  return l1;
780  }
781  if (sz <= 16) {
782  // for short lists, we sort in an array
783  std::vector<RooLinkedListElem *> arr(sz, nullptr);
784  for (int i = 0; l1; l1 = l1->_next, ++i) arr[i] = l1;
785  // straight insertion sort
786  {
787  int i = 1;
788  do {
789  int j = i - 1;
790  RooLinkedListElem *tmp = arr[i];
791  while (0 <= j) {
792  const bool inOrder = ascending ?
793  (tmp->_arg->Compare(arr[j]->_arg) <= 0) :
794  (arr[j]->_arg->Compare(tmp->_arg) <= 0);
795  if (!inOrder) break;
796  arr[j + 1] = arr[j];
797  --j;
798  }
799  arr[j + 1] = tmp;
800  ++i;
801  } while (int(sz) != i);
802  }
803  // link elements in array
804  arr[0]->_prev = arr[sz - 1]->_next = 0;
805  for (int i = 0; i < int(sz - 1); ++i) {
806  arr[i]->_next = arr[i + 1];
807  arr[i + 1]->_prev = arr[i];
808  }
809  if (tail) *tail = arr[sz - 1];
810  return arr[0];
811  }
812  // find middle of l1, and let a second list l2 start there
813  RooLinkedListElem *l2 = l1;
814  for (RooLinkedListElem *end = l2; end->_next; end = end->_next) {
815  end = end->_next;
816  l2 = l2->_next;
817  if (!end->_next) break;
818  }
819  // disconnect the two sublists
820  l2->_prev->_next = 0;
821  l2->_prev = 0;
822  // sort the two sublists (only recurse if we have to)
823  if (l1->_next) l1 = mergesort_impl<ascending>(l1, sz / 2);
824  if (l2->_next) l2 = mergesort_impl<ascending>(l2, sz - sz / 2);
825  // merge the two (sorted) sublists
826  // l: list head, t: list tail of merged list
827  RooLinkedListElem *l = (ascending ? (l1->_arg->Compare(l2->_arg) <= 0) :
828  (l2->_arg->Compare(l1->_arg) <= 0)) ? l1 : l2;
829  RooLinkedListElem *t = l;
830  if (l == l2) {
831  RooLinkedListElem* tmp = l1;
832  l1 = l2;
833  l2 = tmp;
834  }
835  l1 = l1->_next;
836  while (l1 && l2) {
837  const bool inOrder = ascending ? (l1->_arg->Compare(l2->_arg) <= 0) :
838  (l2->_arg->Compare(l1->_arg) <= 0);
839  if (!inOrder) {
840  // insert l2 just before l1
841  if (l1->_prev) {
842  l1->_prev->_next = l2;
843  l2->_prev = l1->_prev;
844  }
845  // swap l2 and l1
846  RooLinkedListElem *tmp = l1;
847  l1 = l2;
848  l2 = tmp;
849  }
850  // move forward in l1
851  t = l1;
852  l1 = l1->_next;
853  }
854  // attach l2 at t
855  if (l2) {
856  l2->_prev = t;
857  if (t) t->_next = l2;
858  }
859  // if desired, update the tail of the (newly merged sorted) list
860  if (tail) {
861  for (l1 = t; l1; l1 = l1->_next) t = l1;
862  *tail = t;
863  }
864  // return the head of the sorted list
865  return l;
866 }
867 // void Roo1DTable::Streamer(TBuffer &R__b)
868 // {
869 // // Stream an object of class Roo1DTable.
870 
871 // if (R__b.IsReading()) {
872 // R__b.ReadClassBuffer(Roo1DTable::Class(),this);
873 // } else {
874 // R__b.WriteClassBuffer(Roo1DTable::Class(),this);
875 // }
876 // }
877 
878 ////////////////////////////////////////////////////////////////////////////////
879 /// Custom streaming handling schema evolution w.r.t past implementations
880 
881 void RooLinkedList::Streamer(TBuffer &R__b)
882 {
883  if (R__b.IsReading()) {
884 
885  Version_t v = R__b.ReadVersion();
886  //R__b.ReadVersion();
887  TObject::Streamer(R__b);
888 
889  Int_t size ;
890  TObject* arg ;
891 
892  R__b >> size ;
893  while(size--) {
894  R__b >> arg ;
895  Add(arg) ;
896  }
897 
898  if (v > 1 && v < 4) {
899  R__b >> _name;
900  }
901 
902  } else {
903  R__b.WriteVersion(RooLinkedList::IsA());
904  TObject::Streamer(R__b);
905  R__b << _size ;
906 
907  RooLinkedListElem* ptr = _first;
908  while(ptr) {
909  R__b << ptr->_arg ;
910  ptr = ptr->_next ;
911  }
912 
913  R__b << _name ;
914  }
915 }
c
#define c(i)
Definition: RSha256.hxx:101
l
auto * l
Definition: textangle.C:4
RooLinkedList::RecursiveRemove
virtual void RecursiveRemove(TObject *obj)
If one of the TObject we have a referenced to is deleted, remove the reference.
Definition: RooLinkedList.cxx:478
RooLinkedList::find
TObject * find(const char *name) const
Return pointer to object with given name in collection.
Definition: RooLinkedList.cxx:603
RooLinkedList::createElement
RooLinkedListElem * createElement(TObject *obj, RooLinkedListElem *elem=0)
cout << "RooLinkedList::createElem(" << this << ") obj = " << obj << " elem = " << elem << endl ;
Definition: RooLinkedList.cxx:290
RooLinkedList::MakeIterator
TIterator * MakeIterator(Bool_t forward=kTRUE) const
Create a TIterator for this list.
Definition: RooLinkedList.cxx:731
RooLinkedListImplDetails::Pool::Chunk
RooLinkedListImplDetails::Chunk Chunk
a chunk of memory in the pool
Definition: RooLinkedList.cxx:122
fit1_py.fill
fill
Definition: fit1_py.py:6
RooLinkedListImplDetails::Chunk::_chunk
RooLinkedListElem * _chunk
chunk from which elements come
Definition: RooLinkedList.cxx:105
kTRUE
const Bool_t kTRUE
Definition: RtypesCore.h:100
TObject::TestBit
R__ALWAYS_INLINE Bool_t TestBit(UInt_t f) const
Definition: TObject.h:187
RooLinkedListIter.h
Version_t
short Version_t
Definition: RtypesCore.h:65
RooMsgService.h
RooLinkedList::_last
RooLinkedListElem * _last
Link to first element of list.
Definition: RooLinkedList.h:116
RooLinkedListImplDetails::Pool::updateCurSz
void updateCurSz(Int_t sz, Int_t incr)
adjust _cursz to current largest block
Definition: RooLinkedList.cxx:219
Option_t
const char Option_t
Definition: RtypesCore.h:66
RooFit.h
RooLinkedList::~RooLinkedList
virtual ~RooLinkedList()
Destructor.
Definition: RooLinkedList.cxx:362
RooFit::InputArguments
@ InputArguments
Definition: RooGlobalFunc.h:61
TObject::Print
virtual void Print(Option_t *option="") const
This method must be overridden when a class wants to print itself.
Definition: TObject.cxx:552
TBuffer::WriteVersion
virtual UInt_t WriteVersion(const TClass *cl, Bool_t useBcnt=kFALSE)=0
TObject::Compare
virtual Int_t Compare(const TObject *obj) const
Compare abstract method.
Definition: TObject.cxx:161
RooLinkedListImplDetails::Pool
Definition: RooLinkedList.cxx:114
ClassImp
#define ClassImp(name)
Definition: Rtypes.h:364
RooLinkedListImplDetails::Pool::push_free_elem
void push_free_elem(RooLinkedListElem *el)
push a free element back into the pool
Definition: RooLinkedList.cxx:182
RooLinkedListImplDetails::Chunk::chunkaddr
const void * chunkaddr() const
return address of chunk
Definition: RooLinkedList.cxx:80
coutE
#define coutE(a)
Definition: RooMsgService.h:33
RooAbsArg::namePtr
const TNamed * namePtr() const
De-duplicated pointer to this object's name.
Definition: RooAbsArg.h:543
RooLinkedListImplDetails::Pool::release
bool release()
release the pool, return true if the pool is unused
Definition: RooLinkedList.cxx:133
RooLinkedListImplDetails::Chunk::_freelist
RooLinkedListElem * _freelist
list of free elements
Definition: RooLinkedList.cxx:106
RooAbsArg.h
Int_t
int Int_t
Definition: RtypesCore.h:45
RooLinkedListImplDetails::Chunk::free
Int_t free() const
chunk free elements
Definition: RooLinkedList.cxx:70
RooLinkedListImplDetails::Pool::minsz
@ minsz
minimum chunk size (just below 1 << minsz bytes)
Definition: RooLinkedList.cxx:117
RooLinkedListImplDetails::Pool::_cursz
Int_t _cursz
Definition: RooLinkedList.cxx:142
RooLinkedListElem::release
void release()
Definition: RooLinkedListElem.h:51
RooLinkedList::fwdIterator
RooFIter fwdIterator() const
Create a one-time-use forward iterator for this list.
Definition: RooLinkedList.cxx:750
TBuffer
Buffer base class used for serializing objects.
Definition: TBuffer.h:43
RooLinkedListElem::_next
RooLinkedListElem * _next
Definition: RooLinkedListElem.h:91
RooLinkedListImplDetails::Pool::nextChunkSz
Int_t nextChunkSz() const
find size of next chunk to allocate (in a hopefully smart way)
Definition: RooLinkedList.cxx:231
RooLinkedListImplDetails
Definition: RooLinkedList.h:32
RooLinkedList::FindObject
TObject * FindObject(const char *name) const
Return pointer to obejct with given name.
Definition: RooLinkedList.cxx:531
RooLinkedListImplDetails::Chunk::capacity
Int_t capacity() const
chunk capacity
Definition: RooLinkedList.cxx:67
RooLinkedListImplDetails::Pool::_refCount
UInt_t _refCount
Definition: RooLinkedList.cxx:143
RooLinkedListElem::_refCount
Int_t _refCount
Definition: RooLinkedListElem.h:93
v
@ v
Definition: rootcling_impl.cxx:3664
RooLinkedList::Pool
RooLinkedListImplDetails::Pool Pool
memory pool for quick allocation of RooLinkedListElems
Definition: RooLinkedList.h:131
bool
TIterator
Iterator abstract base class.
Definition: TIterator.h:30
RooLinkedListImplDetails::Chunk::pop_free_elem
RooLinkedListElem * pop_free_elem()
pop a free element off the free list
Definition: RooLinkedList.cxx:85
RooLinkedList::Replace
Bool_t Replace(const TObject *oldArg, const TObject *newArg)
Replace object 'oldArg' in collection with new object 'newArg'.
Definition: RooLinkedList.cxx:507
TROOT.h
RooLinkedList::findArg
RooAbsArg * findArg(const RooAbsArg *) const
Return pointer to object with given name in collection.
Definition: RooLinkedList.cxx:659
RooLinkedListImplDetails::Chunk::~Chunk
~Chunk()
destructor
Definition: RooLinkedList.cxx:65
RooLinkedListElem
RooLinkedListElem is an link element for the RooLinkedList class.
Definition: RooLinkedListElem.h:30
RooLinkedList::At
TObject * At(int index) const
Return object stored in sequential position given by index.
Definition: RooLinkedList.cxx:487
TObject::GetName
virtual const char * GetName() const
Returns name of object.
Definition: TObject.cxx:359
RooLinkedList::_first
RooLinkedListElem * _first
Definition: RooLinkedList.h:115
RooLinkedListImplDetails::Pool::_szmap
UInt_t _szmap[(maxsz - minsz)/szincr]
Definition: RooLinkedList.cxx:141
RooLinkedListImplDetails::Chunk::Chunk
Chunk(const Chunk &)
forbid copying
RooLinkedListIter
A wrapper around TIterator derivatives.
Definition: RooLinkedListIter.h:204
RooLinkedList::operator=
RooLinkedList & operator=(const RooLinkedList &other)
Assignment operator, copy contents from 'other'.
Definition: RooLinkedList.cxx:309
TBuffer.h
RooLinkedList::RooLinkedList
RooLinkedList(Int_t htsize=0)
Definition: RooLinkedList.cxx:263
RooLinkedListImplDetails::Chunk::empty
bool empty() const
chunk empty?
Definition: RooLinkedList.cxx:78
size
size_t size(const MatrixT &matrix)
retrieve the size of a square matrix
RooLinkedList::mergesort_impl
static RooLinkedListElem * mergesort_impl(RooLinkedListElem *l1, const unsigned sz, RooLinkedListElem **tail=0)
length 0, 1 lists are sorted
Definition: RooLinkedList.cxx:773
RooLinkedListImplDetails::Pool::AddrMap
std::map< const void *, Chunk * > AddrMap
Definition: RooLinkedList.cxx:124
a
auto * a
Definition: textangle.C:12
TNamed
The TNamed class is the base class for all named ROOT classes.
Definition: TNamed.h:29
RooFIter
A one-time forward iterator working on RooLinkedList or RooAbsCollection.
Definition: RooLinkedListIter.h:40
kFALSE
const Bool_t kFALSE
Definition: RtypesCore.h:101
RooLinkedList
RooLinkedList is an collection class for internal use, storing a collection of RooAbsArg pointers in ...
Definition: RooLinkedList.h:37
RooLinkedList::Sort
void Sort(Bool_t ascend=kTRUE)
Definition: RooLinkedList.cxx:757
RooLinkedListElem::_prev
RooLinkedListElem * _prev
Definition: RooLinkedListElem.h:90
RooLinkedListImplDetails::Chunk::size
Int_t size() const
chunk occupied elements
Definition: RooLinkedList.cxx:72
RooLinkedList::_htableName
std::unique_ptr< HashTableByName > _htableName
Definition: RooLinkedList.h:120
RooLinkedListImplDetails::Chunk::push_free_elem
void push_free_elem(RooLinkedListElem *el)
push a free element back onto the freelist
Definition: RooLinkedList.cxx:96
RooLinkedList::Add
virtual void Add(TObject *arg)
Definition: RooLinkedList.h:64
RooLinkedList::iterator
RooLinkedListIter iterator(Bool_t forward=kTRUE) const
Create an iterator for this list.
Definition: RooLinkedList.cxx:741
RooLinkedListImplDetails::Pool::acquire
void acquire()
acquire the pool
Definition: RooLinkedList.cxx:131
RooLinkedList::setHashTableSize
void setHashTableSize(Int_t size)
Change the threshold for hash-table use to given size.
Definition: RooLinkedList.cxx:328
RooLinkedList::_at
std::vector< RooLinkedListElem * > _at
Definition: RooLinkedList.h:135
TBuffer::ReadVersion
virtual Version_t ReadVersion(UInt_t *start=0, UInt_t *bcnt=0, const TClass *cl=0)=0
RooLinkedList::_useNptr
Bool_t _useNptr
Definition: RooLinkedList.h:124
RooLinkedListImplDetails::Chunk::_free
Int_t _free
length of free list
Definition: RooLinkedList.cxx:104
unsigned int
RooLinkedListImplDetails::Chunk::operator=
Chunk & operator=(const Chunk &)
RooLinkedList::_size
Int_t _size
Definition: RooLinkedList.h:114
RooLinkedListImplDetails::Pool::ChunkList
std::list< Chunk * > ChunkList
Definition: RooLinkedList.cxx:123
TBuffer::IsReading
Bool_t IsReading() const
Definition: TBuffer.h:86
RooLinkedList::_hashThresh
Int_t _hashThresh
Definition: RooLinkedList.h:113
RooLinkedListImplDetails::Pool::~Pool
~Pool()
destructor
Definition: RooLinkedList.cxx:156
RooLinkedList::_pool
static Pool * _pool
shared memory pool for allocation of RooLinkedListElems
Definition: RooLinkedList.h:133
RooLinkedList::deleteElement
void deleteElement(RooLinkedListElem *)
Definition: RooLinkedList.cxx:299
RooLinkedList.h
RooLinkedListImplDetails::Chunk::szclass
int szclass() const
return size class
Definition: RooLinkedList.cxx:74
TMVA::DNN::forward
void forward(const LAYERDATA &prevLayerData, LAYERDATA &currLayerData)
apply the weights (and functions) in forward direction of the DNN
Definition: NeuralNet.icc:546
RooLinkedListImplDetails::Chunk::full
bool full() const
chunk full?
Definition: RooLinkedList.cxx:76
TObject
Mother of all ROOT objects.
Definition: TObject.h:37
RooLinkedList::Clear
void Clear(Option_t *o=0)
Remove all elements from collection.
Definition: RooLinkedList.cxx:549
RooLinkedListElem::_arg
TObject * _arg
Definition: RooLinkedListElem.h:92
RooLinkedListImplDetails::Pool::pop_free_elem
RooLinkedListElem * pop_free_elem()
pop a free element out of the pool
Definition: RooLinkedList.cxx:164
name
char name[80]
Definition: TGX11.cxx:110
RooLinkedList::_htableLink
std::unique_ptr< HashTableByLink > _htableLink
Hash table by name.
Definition: RooLinkedList.h:121
RooLinkedListImplDetails::Pool::szincr
@ szincr
size class increment (sz = 1 << (minsz + k * szincr))
Definition: RooLinkedList.cxx:119
RooNameReg::known
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:113
RooLinkedListImplDetails::Chunk::contains
bool contains(RooLinkedListElem *el) const
check if el is in this chunk
Definition: RooLinkedList.cxx:82
RooAbsArg
RooAbsArg is the common abstract base class for objects that represent a value and a "shape" in RooFi...
Definition: RooAbsArg.h:72
RooLinkedListImplDetails::Pool::maxsz
@ maxsz
maximum chunk size (just below 1 << maxsz bytes)
Definition: RooLinkedList.cxx:118
RooLinkedListImplDetails::Chunk::Chunk
Chunk(Int_t sz)
constructor
Definition: RooLinkedList.cxx:55
RMakeUnique.hxx
ROOT::CallRecursiveRemoveIfNeeded
void CallRecursiveRemoveIfNeeded(TObject &obj)
call RecursiveRemove for obj if gROOT is valid and obj.TestBit(kMustCleanup) is true.
Definition: TROOT.h:393
TNamed::GetName
virtual const char * GetName() const
Returns name of object.
Definition: TNamed.h:47
free
#define free
Definition: civetweb.c:1539
RooLinkedListImplDetails::Chunk
a chunk of memory in a pool for quick allocation of RooLinkedListElems
Definition: RooLinkedList.cxx:52
RooLinkedListImplDetails::Chunk::_sz
Int_t _sz
chunk capacity
Definition: RooLinkedList.cxx:103
Riostream.h
RooLinkedList::_name
TString _name
Hash table by link pointer.
Definition: RooLinkedList.h:123
RooLinkedList::IndexOf
Int_t IndexOf(const char *name) const
Return position of given object in list.
Definition: RooLinkedList.cxx:700
RooLinkedListElem::init
void init(TObject *arg, RooLinkedListElem *after=0)
Definition: RooLinkedListElem.h:37
RooNameReg::kRenamedArg
@ kRenamedArg
Definition: RooNameReg.h:37
RooLinkedListImplDetails::Pool::_freelist
ChunkList _freelist
Definition: RooLinkedList.cxx:140
RooLinkedList::Delete
void Delete(Option_t *o=0)
Remove all elements in collection and delete all elements NB: Collection does not own elements,...
Definition: RooLinkedList.cxx:575
RooLinkedList::findLink
RooLinkedListElem * findLink(const TObject *arg) const
Find the element link containing the given object.
Definition: RooLinkedList.cxx:380
RooLinkedList::Print
void Print(const char *opt) const
Print contents of list, defers to Print() function of contained objects.
Definition: RooLinkedList.cxx:716
RooLinkedList::Remove
virtual Bool_t Remove(TObject *arg)
Remove object from collection.
Definition: RooLinkedList.cxx:446
int
RooLinkedListImplDetails::Pool::_addrmap
AddrMap _addrmap
Definition: RooLinkedList.cxx:139