include/root/RooLinkedList.h

0001 /*****************************************************************************
0002  * Project: RooFit                                                           *
0003  * Package: RooFitCore                                                       *
0004  *    File: $Id: RooLinkedList.h,v 1.15 2007/05/11 09:11:30 verkerke Exp $
0005  * Authors:                                                                  *
0006  *   WV, Wouter Verkerke, UC Santa Barbara, verkerke@slac.stanford.edu       *
0007  *   DK, David Kirkby,    UC Irvine,         dkirkby@uci.edu                 *
0008  *                                                                           *
0009  * Copyright (c) 2000-2005, Regents of the University of California          *
0010  *                          and Stanford University. All rights reserved.    *
0011  *                                                                           *
0012  * Redistribution and use in source and binary forms,                        *
0013  * with or without modification, are permitted according to the terms        *
0014  * listed in LICENSE (http://roofit.sourceforge.net/license.txt)             *
0015  *****************************************************************************/
0016 #ifndef ROO_LINKED_LIST
0017 #define ROO_LINKED_LIST
0018
0019 #include "TObject.h"
0020 #include "RooLinkedListElem.h"
0021 #include "TString.h"
0022
0023 #include <vector>
0024 #include <memory>
0025 #include <unordered_map>
0026
0027 class RooLinkedListIter ;
0028 class RooLinkedListIterImpl ;
0029 class RooFIter;
0030 class TIterator ;
0031 class RooAbsArg ;
0032
0033 /// \cond ROOFIT_INTERNAL
0034
0035 template<class T>
0036 class RooSTLRefCountList;
0037
0038 namespace RooLinkedListImplDetails {
0039     class Chunk;
0040     class Pool;
0041 }
0042
0043 /// \endcond
0044
0045 class RooLinkedList : public TObject {
0046 public:
0047   // Constructor
0048   RooLinkedList(Int_t htsize=0) ;
0049
0050   // Copy constructor
0051   RooLinkedList(const RooLinkedList& other) ;
0052
0053   TObject* Clone(const char* =nullptr) const override {
0054     return new RooLinkedList(*this) ;
0055   }
0056
0057   // Assignment operator
0058   RooLinkedList& operator=(const RooLinkedList& other) ;
0059
0060   Int_t getHashTableSize() const {
0061     // Return size of hash table
0062     return _htableName ? _htableName->size() : 0 ;
0063   }
0064
0065   void setHashTableSize(Int_t size) ;
0066
0067   // Destructor
0068   ~RooLinkedList() override ;
0069
0070   Int_t GetSize() const { return _size ; }
0071   std::size_t size() const { return _size ; }
0072   bool empty() const { return _size == 0 ; }
0073
0074   virtual void Add(TObject* arg) { Add(arg,1) ; }
0075   virtual bool Remove(TObject* arg) ;
0076   TObject* At(int index) const ;
0077   bool Replace(const TObject* oldArg, const TObject* newArg) ;
0078   TIterator* MakeIterator(bool forward = true) const ;
0079   RooLinkedListIter iterator(bool forward = true) const ;
0080   RooFIter fwdIterator() const ;
0081   RooLinkedListIterImpl begin() const;
0082   RooLinkedListIterImpl end() const;
0083   RooLinkedListIterImpl rbegin() const;
0084   RooLinkedListIterImpl rend() const;
0085
0086   void Clear(Option_t *o=nullptr) override ;
0087   void Delete(Option_t *o=nullptr) override ;
0088   TObject* find(const char* name) const ;
0089   RooAbsArg* findArg(const RooAbsArg*) const ;
0090   TObject* FindObject(const char* name) const override ;
0091   TObject* FindObject(const TObject* obj) const override ;
0092   Int_t IndexOf(const char* name) const ;
0093   Int_t IndexOf(const TObject* arg) const ;
0094   TObject* First() const {
0095     return _first ? _first->_arg : nullptr ;
0096   }
0097
0098   void RecursiveRemove(TObject *obj) override;
0099
0100   void Print(const char* opt) const override ;
0101   void Sort(bool ascend=true) ;
0102
0103   // const char* GetName() const { return "" ; /*_name.Data() ; */ }
0104   // void SetName(const char* /*name*/) { /*_name = name ; */ }
0105   const char* GetName() const override { return _name.Data() ;  }
0106   void SetName(const char* name) { _name = name ;  }
0107
0108    void useNptr(bool flag) { _useNptr = flag ; }
0109    // needed for using it in THashList/THashTable
0110
0111    ULong_t  Hash() const override { return _name.Hash(); }
0112
0113 protected:
0114
0115   RooLinkedListElem* createElement(TObject* obj, RooLinkedListElem* elem=nullptr) ;
0116   void deleteElement(RooLinkedListElem*) ;
0117
0118   /// \cond ROOFIT_INTERNAL
0119   template<class T> friend class RooSTLRefCountList;
0120   /// \endcond
0121   friend class RooLinkedListIterImpl ;
0122   friend class RooFIterForLinkedList ;
0123
0124   virtual void Add(TObject* arg, Int_t refCount) ;
0125
0126   RooLinkedListElem* findLink(const TObject* arg) const ;
0127
0128   Int_t _hashThresh ;          ///<  Size threshold for hashing
0129   Int_t _size ;                ///<  Current size of list
0130   RooLinkedListElem*  _first ; ///<! Link to first element of list
0131   RooLinkedListElem*  _last ;  ///<! Link to last element of list
0132
0133   using HashTableByName = std::unordered_map<std::string,TObject const*>;
0134   using HashTableByLink = std::unordered_map<TObject const*,TObject const*>;
0135   std::unique_ptr<HashTableByName> _htableName; ///<! Hash table by name
0136   std::unique_ptr<HashTableByLink> _htableLink; ///<! Hash table by link pointer
0137
0138   TString             _name ;
0139   bool              _useNptr ; ///<!
0140
0141 private:
0142   template <bool ascending>
0143   static RooLinkedListElem* mergesort_impl(RooLinkedListElem* l1,
0144      const unsigned sz, RooLinkedListElem** tail = nullptr);
0145   /// memory pool for quick allocation of RooLinkedListElems
0146   typedef RooLinkedListImplDetails::Pool Pool;
0147   /// shared memory pool for allocation of RooLinkedListElems
0148   static Pool* _pool; //!
0149
0150   std::vector<RooLinkedListElem *> _at; ///<! index list for quick index through ::At
0151
0152   ClassDefOverride(RooLinkedList,3) // Doubly linked list for storage of RooAbsArg objects
0153 };
0154
0155 #endif