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