Logo ROOT   6.21/01
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 "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 
45 using namespace std;
46 
48 ;
49 namespace RooLinkedListImplDetails {
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
354  RooLinkedListElem* ptr = _first ;
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 
396  RooLinkedListElem* ptr = _first;
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 
410 void 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 
515 Bool_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 {
588  RooLinkedListElem* elem = _first;
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 
618 TObject* 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)) {
631  RooLinkedListElem* ptr = _first ;
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 
644  RooLinkedListElem* ptr = _first ;
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) {
677  RooAbsArg* a = (RooAbsArg*) _htableName->findArg(arg) ;
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 
684  RooLinkedListElem* ptr = _first ;
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 {
701  RooLinkedListElem* ptr = _first;
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 
715 Int_t RooLinkedList::IndexOf(const char* name) const
716 {
717  RooLinkedListElem* ptr = _first;
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 
731 void 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
778  RooLinkedListElem* elem = _first;
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 
787 template <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 
903 void 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 
929  RooLinkedListElem* ptr = _first;
930  while(ptr) {
931  R__b << ptr->_arg ;
932  ptr = ptr->_next ;
933  }
934 
935  R__b << _name ;
936  }
937 }
938 
Bool_t IsReading() const
Definition: TBuffer.h:85
Int_t IndexOf(const char *name) const
Return position of given object in list.
#define coutE(a)
Definition: RooMsgService.h:34
static RooLinkedListElem * mergesort_impl(RooLinkedListElem *l1, const unsigned sz, RooLinkedListElem **tail=0)
length 0, 1 lists are sorted
TObject * FindObject(const char *name) const
Return pointer to obejct with given name.
RooHashTable * _htableLink
Hash table by name.
short Version_t
Definition: RtypesCore.h:61
void CallRecursiveRemoveIfNeeded(TObject &obj)
call RecursiveRemove for obj if gROOT is valid and obj.TestBit(kMustCleanup) is true.
Definition: TROOT.h:404
virtual Bool_t Remove(TObject *arg)
Remove object from collection.
void setHashTableSize(Int_t size)
Change the threshold for hash-table use to given size.
const char Option_t
Definition: RtypesCore.h:62
TObject * find(const char *name) const
Return pointer to object with given name in collection.
fill
Definition: fit1_py.py:6
Buffer base class used for serializing objects.
Definition: TBuffer.h:42
R__ALWAYS_INLINE Bool_t TestBit(UInt_t f) const
Definition: TObject.h:172
RooFIter fwdIterator() const
Create a one-time-use forward iterator for this list.
int Int_t
Definition: RtypesCore.h:41
bool Bool_t
Definition: RtypesCore.h:59
Bool_t replace(const TObject *oldArg, const TObject *newArg, const TObject *oldHashArg=0)
Replace oldArg with newArg in the table.
STL namespace.
virtual void Print(Option_t *option="") const
This method must be overridden when a class wants to print itself.
Definition: TObject.cxx:550
virtual UInt_t WriteVersion(const TClass *cl, Bool_t useBcnt=kFALSE)=0
RooLinkedListImplDetails::Pool Pool
memory pool for quick allocation of RooLinkedListElems
void Clear(Option_t *o=0)
Remove all elements from collection.
Iterator abstract base class.
Definition: TIterator.h:30
void Sort(Bool_t ascend=kTRUE)
Bool_t Replace(const TObject *oldArg, const TObject *newArg)
Replace object &#39;oldArg&#39; in collection with new object &#39;newArg&#39;.
RooLinkedListIter iterator(Bool_t forward=kTRUE) const
Create an iterator for this list.
virtual void RecursiveRemove(TObject *obj)
If one of the TObject we have a referenced to is deleted, remove the reference.
RooLinkedListElem * findLinkTo(const TObject *arg) const
Return RooLinkedList element link to object &#39;hashArg&#39;.
std::vector< RooLinkedListElem * > _at
RooLinkedListElem * _next
RooLinkedListElem * _first
The TNamed class is the base class for all named ROOT classes.
Definition: TNamed.h:29
TString _name
Hash table by link pointer.
RooHashTable implements a hash table for TObjects.
Definition: RooHashTable.h:28
RooLinkedListElem * findLink(const TObject *arg) const
Find the element link containing the given object.
static const TNamed * known(const char *stringPtr)
If the name is already known, return its TNamed pointer. Otherwise return 0 (don&#39;t register the name)...
Definition: RooNameReg.cxx:113
virtual void Add(TObject *arg)
Definition: RooLinkedList.h:63
void add(TObject *arg, TObject *hashArg=0)
Add given object to table.
RooLinkedListElem * _prev
auto * a
Definition: textangle.C:12
RooLinkedList(Int_t htsize=0)
TObject * At(Int_t index) const
Return object stored in sequential position given by index.
unsigned int UInt_t
Definition: RtypesCore.h:42
virtual Int_t Compare(const TObject *obj) const
Compare abstract method.
Definition: TObject.cxx:159
TObject * find(const char *name) const
Return the object with given name from the table.
Bool_t remove(TObject *arg, TObject *hashArg=0)
Remove given object from table.
const Bool_t kFALSE
Definition: RtypesCore.h:88
RooLinkedList is an collection class for internal use, storing a collection of RooAbsArg pointers in ...
Definition: RooLinkedList.h:36
void Delete(Option_t *o=0)
Remove all elements in collection and delete all elements NB: Collection does not own elements...
#define ClassImp(name)
Definition: Rtypes.h:365
#define free
Definition: civetweb.c:1539
Int_t size() const
Definition: RooHashTable.h:48
void forward(const LAYERDATA &prevLayerData, LAYERDATA &currLayerData)
apply the weights (and functions) in forward direction of the DNN
Definition: NeuralNet.icc:546
TIterator * MakeIterator(Bool_t forward=kTRUE) const
Create a TIterator for this list.
RooLinkedList & operator=(const RooLinkedList &other)
Assignment operator, copy contents from &#39;other&#39;.
Binding & operator=(OUT(*fun)(void))
Mother of all ROOT objects.
Definition: TObject.h:37
RooLinkedListElem * _last
Link to first element of list.
void deleteElement(RooLinkedListElem *)
static Pool * _pool
shared memory pool for allocation of RooLinkedListElems
auto * l
Definition: textangle.C:4
void Print(const char *opt) const
Print contents of list, defers to Print() function of contained objects.
virtual ~RooLinkedList()
Destructor.
#define c(i)
Definition: RSha256.hxx:101
RooAbsArg * findArg(const RooAbsArg *) const
Return pointer to object with given name in collection.
RooLinkedListElem is an link element for the RooLinkedList class.
RooAbsArg * findArg(const RooAbsArg *arg) const
RooAbsArg is the common abstract base class for objects that represent a value (of arbitrary type) an...
Definition: RooAbsArg.h:71
RooLinkedListElem * createElement(TObject *obj, RooLinkedListElem *elem=0)
cout << "RooLinkedList::createElem(" << this << ") obj = " << obj << " elem = " << elem << endl ; ...
virtual const char * GetName() const
Returns name of object.
Definition: TObject.cxx:357
const Bool_t kTRUE
Definition: RtypesCore.h:87
A wrapper around TIterator derivatives.
char name[80]
Definition: TGX11.cxx:109
const TNamed * namePtr() const
Definition: RooAbsArg.h:478
virtual Version_t ReadVersion(UInt_t *start=0, UInt_t *bcnt=0, const TClass *cl=0)=0
A one-time forward iterator working on RooLinkedList or RooAbsCollection.
RooHashTable * _htableName
Link to last element of list.
void init(TObject *arg, RooLinkedListElem *after=0)