include/root/TCollection.h

0001 // @(#)root/cont:$Id$
0002 // Author: Fons Rademakers   13/08/95
0003
0004 /*************************************************************************
0005  * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers.               *
0006  * All rights reserved.                                                  *
0007  *                                                                       *
0008  * For the licensing terms see $ROOTSYS/LICENSE.                         *
0009  * For the list of contributors see $ROOTSYS/README/CREDITS.             *
0010  *************************************************************************/
0011
0012 #ifndef ROOT_TCollection
0013 #define ROOT_TCollection
0014
0015
0016 //////////////////////////////////////////////////////////////////////////
0017 //                                                                      //
0018 // TCollection                                                          //
0019 //                                                                      //
0020 // Collection abstract base class. This class inherits from TObject     //
0021 // because we want to be able to have collections of collections.       //
0022 //                                                                      //
0023 //////////////////////////////////////////////////////////////////////////
0024
0025 #include "TObject.h"
0026
0027 #include "TIterator.h"
0028
0029 #include "TString.h"
0030
0031 #include "TVirtualRWMutex.h"
0032
0033 #include "ROOT/RRangeCast.hxx"
0034
0035 #include <cassert>
0036
0037 class TClass;
0038 class TObjectTable;
0039 class TVirtualMutex;
0040 class TIter;
0041
0042 const Bool_t kIterForward  = kTRUE;
0043 const Bool_t kIterBackward = !kIterForward;
0044
0045 R__EXTERN TVirtualMutex *gCollectionMutex;
0046
0047 // #define R__CHECK_COLLECTION_MULTI_ACCESS
0048
0049 // When R__CHECK_COLLECTION_MULTI_ACCESS is turned on (defined),
0050 // the normal (not locked) ROOT TCollections are instrumented with a
0051 // pseudo read-write lock which does not halt the execution but detects
0052 // and report concurrent access to the same collections.
0053 // Multiple readers are allowed.
0054 // Multiple concurrent writer is reported as a Conflict
0055 // Readers access while a write is running is reported as Conflict
0056 // Re-entrant writing call by the same Writer thread are allowed.
0057 // Entering a writing section by a single Reader thread is allowed.
0058
0059 #ifdef R__CHECK_COLLECTION_MULTI_ACCESS
0060 #include <atomic>
0061 #include <thread>
0062 #include <unordered_multiset>
0063 #endif
0064
0065 class TCollection : public TObject {
0066
0067 #ifdef R__CHECK_COLLECTION_MULTI_ACCESS
0068 public:
0069    class TErrorLock {
0070       // Warn when multiple thread try to acquire the same 'lock'
0071       std::atomic<std::thread::id> fWriteCurrent;
0072       std::atomic<size_t> fWriteCurrentRecurse;
0073       std::atomic<size_t> fReadCurrentRecurse;
0074       std::unordered_multiset<std::thread::id> fReadSet;
0075       std::atomic_flag fSpinLockFlag;
0076
0077       void Lock(const TCollection *collection, const char *function);
0078
0079       void Unlock();
0080
0081       void ReadLock(const TCollection *collection, const char *function);
0082
0083       void ReadUnlock();
0084
0085       void ConflictReport(std::thread::id holder, const char *accesstype, const TCollection *collection,
0086                           const char *function);
0087
0088    public:
0089       TErrorLock() : fWriteCurrent(), fWriteCurrentRecurse(0), fReadCurrentRecurse(0)
0090       {
0091          std::atomic_flag_clear(&fSpinLockFlag);
0092       }
0093
0094       class WriteGuard {
0095          TErrorLock *fLock;
0096
0097       public:
0098          WriteGuard(TErrorLock &lock, const TCollection *collection, const char *function) : fLock(&lock)
0099          {
0100             fLock->Lock(collection, function);
0101          }
0102          ~WriteGuard() { fLock->Unlock(); }
0103       };
0104
0105       class ReadGuard {
0106          TErrorLock *fLock;
0107
0108       public:
0109          ReadGuard(TErrorLock &lock, const TCollection *collection, const char *function) : fLock(&lock)
0110          {
0111             fLock->ReadLock(collection, function);
0112          }
0113          ~ReadGuard() { fLock->ReadUnlock(); }
0114       };
0115    };
0116
0117    mutable TErrorLock fLock; //! Special 'lock' to detect multiple access to a collection.
0118
0119 #define R__COLLECTION_WRITE_GUARD() TCollection::TErrorLock::WriteGuard wg(fLock, this, __PRETTY_FUNCTION__)
0120 #define R__COLLECTION_READ_GUARD() TCollection::TErrorLock::ReadGuard rg(fLock, this, __PRETTY_FUNCTION__)
0121
0122 #define R__COLLECTION_ITER_GUARD(collection) \
0123    TCollection::TErrorLock::ReadGuard rg(collection->fLock, collection, __PRETTY_FUNCTION__)
0124
0125 #else
0126
0127 #define R__COLLECTION_WRITE_GUARD()
0128 #define R__COLLECTION_READ_GUARD()
0129 #define R__COLLECTION_ITER_GUARD(collection)
0130
0131 #endif
0132
0133 private:
0134    static TCollection  *fgCurrentCollection;  //used by macro R__FOR_EACH
0135    static TObjectTable *fgGarbageCollection;  //used by garbage collector
0136    static Bool_t        fgEmptyingGarbage;    //used by garbage collector
0137    static Int_t         fgGarbageStack;       //used by garbage collector
0138
0139    TCollection(const TCollection &) = delete;    //private and not-implemented, collections
0140    void operator=(const TCollection &) = delete; //are too complex to be automatically copied
0141
0142 protected:
0143    enum EStatusBits {
0144       kIsOwner   = BIT(14),
0145       // BIT(15) is used by TClonesArray and TMap
0146       kUseRWLock = BIT(16)
0147    };
0148
0149    TString   fName;               //name of the collection
0150    Int_t     fSize;               //number of elements in collection
0151
0152    TCollection() : fName(), fSize(0) { }
0153
0154    virtual void        PrintCollectionHeader(Option_t* option) const;
0155    virtual const char* GetCollectionEntryName(TObject* entry) const;
0156    virtual void        PrintCollectionEntry(TObject* entry, Option_t* option, Int_t recurse) const;
0157
0158 public:
0159    enum { kInitCapacity = 16, kInitHashTableCapacity = 17 };
0160
0161    virtual            ~TCollection();
0162    virtual void       Add(TObject *obj) = 0;
0163    void               AddVector(TObject *obj1, ...);
0164    virtual void       AddAll(const TCollection *col);
0165    Bool_t             AssertClass(TClass *cl) const;
0166    void               Browse(TBrowser *b) override;
0167    Int_t              Capacity() const { return fSize; }
0168    void               Clear(Option_t *option="") override = 0;
0169    TObject           *Clone(const char *newname="") const override;
0170    Int_t              Compare(const TObject *obj) const override;
0171    Bool_t             Contains(const char *name) const { return FindObject(name) != nullptr; }
0172    Bool_t             Contains(const TObject *obj) const { return FindObject(obj) != nullptr; }
0173    void               Delete(Option_t *option="") override = 0;
0174    void               Draw(Option_t *option="") override;
0175    void               Dump() const override;
0176    TObject           *FindObject(const char *name) const override;
0177    TObject           *operator()(const char *name) const;
0178    TObject           *FindObject(const TObject *obj) const override;
0179    virtual Int_t      GetEntries() const { return GetSize(); }
0180    const char        *GetName() const override;
0181    virtual TObject  **GetObjectRef(const TObject *obj) const = 0;
0182    /// Return the *capacity* of the collection, i.e. the current total amount of space that has been allocated so far.
0183    /// Same as `Capacity`. Use `GetEntries` to get the number of elements currently in the collection.
0184    virtual Int_t      GetSize() const { return fSize; }
0185    virtual Int_t      GrowBy(Int_t delta) const;
0186    ULong_t            Hash() const override { return fName.Hash(); }
0187    Bool_t             IsArgNull(const char *where, const TObject *obj) const;
0188    virtual Bool_t     IsEmpty() const { return GetSize() <= 0; }
0189    Bool_t             IsFolder() const override { return kTRUE; }
0190    Bool_t             IsOwner() const { return TestBit(kIsOwner); }
0191    Bool_t             IsSortable() const override { return kTRUE; }
0192    void               ls(Option_t *option="") const override;
0193    Bool_t             Notify() override;
0194    virtual TIterator *MakeIterator(Bool_t dir = kIterForward) const = 0;
0195    virtual TIterator *MakeReverseIterator() const { return MakeIterator(kIterBackward); }
0196    void               Paint(Option_t *option="") override;
0197    void               Print(Option_t *option="") const override;
0198    virtual void       Print(Option_t *option, Int_t recurse) const;
0199    virtual void       Print(Option_t *option, const char* wildcard, Int_t recurse=1) const;
0200    virtual void       Print(Option_t *option, TPRegexp& regexp, Int_t recurse=1) const;
0201    void               RecursiveRemove(TObject *obj) override;
0202    virtual TObject   *Remove(TObject *obj) = 0;
0203    virtual void       RemoveAll(TCollection *col);
0204    void               RemoveAll() { Clear(); }
0205    void               SetCurrentCollection();
0206    void               SetName(const char *name) { fName = name; }
0207    virtual void       SetOwner(Bool_t enable = kTRUE);
0208    virtual bool       UseRWLock(Bool_t enable = true);
0209    Int_t              Write(const char *name = nullptr, Int_t option = 0, Int_t bufsize = 0) override;
0210    Int_t              Write(const char *name = nullptr, Int_t option = 0, Int_t bufsize = 0) const override;
0211
0212    R__ALWAYS_INLINE Bool_t IsUsingRWLock() const { return TestBit(TCollection::kUseRWLock); }
0213
0214    static TCollection  *GetCurrentCollection();
0215    static void          StartGarbageCollection();
0216    static void          GarbageCollect(TObject *obj);
0217    static void          EmptyGarbageCollection();
0218
0219    TIter begin() const;
0220    TIter end() const;
0221
0222    ClassDefOverride(TCollection,3)  //Collection abstract base class
0223 };
0224
0225
0226 //////////////////////////////////////////////////////////////////////////
0227 //                                                                      //
0228 // TIter                                                                //
0229 //                                                                      //
0230 // Iterator wrapper. Type of iterator used depends on type of           //
0231 // collection.                                                          //
0232 //                                                                      //
0233 //////////////////////////////////////////////////////////////////////////
0234
0235 class TIter {
0236
0237 private:
0238    TIterator    *fIterator{nullptr};         //collection iterator
0239
0240 protected:
0241    TIter() : fIterator(nullptr) { }
0242
0243 public:
0244    TIter(const TCollection *col, Bool_t dir = kIterForward)
0245          : fIterator(col ? col->MakeIterator(dir) : nullptr) { }
0246    TIter(TIterator *it) : fIterator(it) { }
0247    TIter(const TIter &iter);
0248    TIter &operator=(const TIter &rhs);
0249    virtual ~TIter() { SafeDelete(fIterator); }
0250    TObject           *operator()() { return Next(); }
0251    TObject           *Next() { return fIterator ? fIterator->Next() : nullptr; }
0252    const TCollection *GetCollection() const { return fIterator ? fIterator->GetCollection() : nullptr; }
0253    Option_t          *GetOption() const { return fIterator ? fIterator->GetOption() : ""; }
0254    void               Reset() { if (fIterator) fIterator->Reset(); }
0255    TIter             &operator++() { Next(); return *this; }
0256    Bool_t             operator==(const TIter &aIter) const {
0257       if (fIterator == nullptr)
0258          return aIter.fIterator == nullptr || **aIter.fIterator == nullptr;
0259       if (aIter.fIterator == nullptr)
0260          return fIterator == nullptr || **fIterator == nullptr;
0261       return *fIterator == *aIter.fIterator;
0262    }
0263    Bool_t             operator!=(const TIter &aIter) const {
0264       return !(*this == aIter);
0265    }
0266    TIter &operator=(TIterator *iter)
0267    {
0268       if (fIterator)
0269          delete fIterator;
0270       fIterator = iter;
0271       return *this;
0272    }
0273    TObject           *operator*() const { return fIterator ? *(*fIterator): nullptr; }
0274    TIter             &Begin();
0275    static TIter       End();
0276
0277    ClassDef(TIter,0)  //Iterator wrapper
0278 };
0279
0280 template <class T>
0281 class TIterCategory: public TIter, public std::iterator_traits<typename T::Iterator_t> {
0282
0283 public:
0284    TIterCategory(const TCollection *col, Bool_t dir = kIterForward) : TIter(col, dir) { }
0285    TIterCategory(TIterator *it) : TIter(it) { }
0286    virtual ~TIterCategory() { }
0287    TIterCategory &Begin() { TIter::Begin(); return *this; }
0288    static TIterCategory End() { return TIterCategory(static_cast<TIterator*>(nullptr)); }
0289 };
0290
0291
0292 inline TIter TCollection::begin() const { return ++(TIter(this)); }
0293 inline TIter TCollection::end() const { return TIter::End(); }
0294
0295 namespace ROOT {
0296 namespace Internal {
0297
0298 const TCollection &EmptyCollection();
0299 bool ContaineeInheritsFrom(TClass *cl, TClass *base);
0300
0301 } // namespace Internal
0302
0303 /// Special implementation of ROOT::RRangeCast for TCollection, including a
0304 /// check that the cast target type inherits from TObject and a new constructor
0305 /// that takes the TCollection by pointer.
0306 /// \tparam T The new type to convert to.
0307 /// \tparam isDynamic If `true`, `dynamic_cast` is used, otherwise `static_cast` is used.
0308 namespace Detail {
0309
0310 template <typename T, bool isDynamic>
0311 class TRangeCast : public ROOT::RRangeCast<T*, isDynamic, TCollection const&> {
0312 public:
0313    TRangeCast(TCollection const& col) : ROOT::RRangeCast<T*, isDynamic, TCollection const&>{col} {
0314       static_assert(std::is_base_of<TObject, T>::value, "Containee type must inherit from TObject");
0315    }
0316    TRangeCast(TCollection const* col) : TRangeCast{col != nullptr ? *col : ROOT::Internal::EmptyCollection()} {}
0317 };
0318
0319 /// @brief TRangeStaticCast is an adapter class that allows the typed iteration
0320 /// through a TCollection. This requires the collection to contain elements
0321 /// of the type requested (or a derived class). Any deviation from this expectation
0322 /// will only be caught/reported by an assert in debug builds.
0323 ///
0324 /// This is best used with a TClonesArray, for other cases prefered TRangeDynCast.
0325 ///
0326 /// The typical use is:
0327 /// ```{.cpp}
0328 ///    for(auto bcl : TRangeStaticCast<TBaseClass>( *tbaseClassClonesArrayPtr )) {
0329 ///        ... use bcl as a TBaseClass*
0330 ///    }
0331 ///    for(auto bcl : TRangeStaticCast<TBaseClass>( tbaseClassClonesArrayPtr )) {
0332 ///        ... use bcl as a TBaseClass*
0333 ///    }
0334 /// ```
0335 /// \tparam T The new type to convert to.
0336 template <typename T>
0337 using TRangeStaticCast = TRangeCast<T, false>;
0338
0339 } // namespace Detail
0340 } // namespace ROOT
0341
0342 /// @brief TRangeDynCast is an adapter class that allows the typed iteration
0343 /// through a TCollection.
0344 ///
0345 /// The typical use is:
0346 /// ```{.cpp}
0347 ///    for(auto bcl : TRangeDynCast<TBaseClass>( *cl->GetListOfBases() )) {
0348 ///        if (!bcl) continue;
0349 ///        ... use bcl as a TBaseClass*
0350 ///    }
0351 ///    for(auto bcl : TRangeDynCast<TBaseClass>( cl->GetListOfBases() )) {
0352 ///        if (!bcl) continue;
0353 ///        ... use bcl as a TBaseClass*
0354 ///    }
0355 /// ```
0356 /// \tparam T The new type to convert to.
0357 template <typename T>
0358 using TRangeDynCast = ROOT::Detail::TRangeCast<T, true>;
0359
0360 #define R__COLL_COND_MUTEX(mutex) this->IsUsingRWLock() ? mutex : nullptr
0361
0362 #define R__COLLECTION_READ_LOCKGUARD(mutex) ::ROOT::TReadLockGuard _R__UNIQUE_(R__readguard)(R__COLL_COND_MUTEX(mutex))
0363 #define R__COLLECTION_READ_LOCKGUARD_NAMED(name,mutex) ::ROOT::TReadLockGuard _NAME2_(R__readguard,name)(R__COLL_COND_MUTEX(mutex))
0364
0365 #define R__COLLECTION_WRITE_LOCKGUARD(mutex) ::ROOT::TWriteLockGuard _R__UNIQUE_(R__readguard)(R__COLL_COND_MUTEX(mutex))
0366 #define R__COLLECTION_WRITE_LOCKGUARD_NAMED(name,mutex) ::ROOT::TWriteLockGuard _NAME2_(R__readguard,name)(R__COLL_COND_MUTEX(mutex))
0367
0368 //---- R__FOR_EACH macro -------------------------------------------------------
0369
0370 // Macro to loop over all elements of a list of type "type" while executing
0371 // procedure "proc" on each element
0372
0373 #define R__FOR_EACH(type,proc) \
0374     SetCurrentCollection(); \
0375     TIter _NAME3_(nxt_,type,proc)(TCollection::GetCurrentCollection()); \
0376     type *_NAME3_(obj_,type,proc); \
0377     while ((_NAME3_(obj_,type,proc) = (type*) _NAME3_(nxt_,type,proc)())) \
0378        _NAME3_(obj_,type,proc)->proc
0379
0380 #endif