include/root/THashTable.h

0001 // @(#)root/cont:$Id$
0002 // Author: Fons Rademakers   27/09/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_THashTable
0013 #define ROOT_THashTable
0014
0015
0016 //////////////////////////////////////////////////////////////////////////
0017 //                                                                      //
0018 // THashTable                                                           //
0019 //                                                                      //
0020 // THashTable implements a hash table to store TObject's. The hash      //
0021 // value is calculated using the value returned by the TObject's        //
0022 // Hash() function. Each class inheriting from TObject can override     //
0023 // Hash() as it sees fit.                                               //
0024 //                                                                      //
0025 //////////////////////////////////////////////////////////////////////////
0026
0027 #include "TCollection.h"
0028 #include "TString.h"
0029
0030 class TList;
0031 class TListIter;
0032 class THashTableIter;
0033
0034
0035 class THashTable : public TCollection {
0036
0037 friend class  THashTableIter;
0038
0039 private:
0040    TList     **fCont;          //Hash table (table of lists)
0041    Int_t       fEntries;       //Number of objects in table
0042    Int_t       fUsedSlots;     //Number of used slots
0043    Int_t       fRehashLevel;   //Average collision rate which triggers rehash
0044
0045    Int_t       GetCheckedHashValue(TObject *obj) const;
0046    Int_t       GetHashValue(const TObject *obj) const;
0047    Int_t       GetHashValue(TString &s) const { return s.Hash() % fSize; }
0048    Int_t       GetHashValue(const char *str) const { return ::Hash(str) % fSize; }
0049
0050    void        AddImpl(Int_t slot, TObject *object);
0051
0052    THashTable(const THashTable&) = delete;
0053    THashTable& operator=(const THashTable&) = delete;
0054
0055 public:
0056    THashTable(Int_t capacity = TCollection::kInitHashTableCapacity, Int_t rehash = 0);
0057    virtual       ~THashTable();
0058    void          Add(TObject *obj) override;
0059    void          Add(TObject *obj, Option_t *) override { Add(obj); };
0060    void          AddBefore(const TObject *before, TObject *obj);
0061    void          AddAll(const TCollection *col) override;
0062    Float_t       AverageCollisions() const;
0063    void          Clear(Option_t *option="") override;
0064    Int_t         Collisions(const char *name) const;
0065    Int_t         Collisions(TObject *obj) const;
0066    void          Delete(Option_t *option="") override;
0067    Bool_t        Empty() const { return fEntries == 0; }
0068    TObject      *FindObject(const char *name) const override;
0069    TObject      *FindObject(const TObject *obj) const override;
0070    const TList  *GetListForObject(const char *name) const;
0071    const TList  *GetListForObject(const TObject *obj) const;
0072    TObject     **GetObjectRef(const TObject *obj) const override;
0073    Int_t         GetRehashLevel() const { return fRehashLevel; }
0074    Int_t         GetSize() const override { return fEntries; }
0075    TIterator    *MakeIterator(Bool_t dir = kIterForward) const override;
0076    using         TCollection::Print;
0077    void          Print(Option_t *option, Int_t recurse) const override;
0078    void          Rehash(Int_t newCapacity, Bool_t checkObjValidity = kTRUE);
0079    TObject      *Remove(TObject *obj) override;
0080    TObject      *RemoveSlow(TObject *obj);
0081    void          SetRehashLevel(Int_t rehash) { fRehashLevel = rehash; }
0082
0083    ClassDefOverride(THashTable,0)  //A hash table
0084 };
0085
0086 inline Float_t THashTable::AverageCollisions() const
0087 {
0088    if (fUsedSlots)
0089       return ((Float_t)fEntries)/((Float_t)fUsedSlots);
0090    else
0091       return 0.0;
0092 }
0093
0094 inline Int_t THashTable::GetCheckedHashValue(TObject *obj) const
0095 {
0096    Int_t i = Int_t(obj->CheckedHash() % fSize); // need intermediary i for Linux g++
0097    return i;
0098 }
0099
0100 inline Int_t THashTable::GetHashValue(const TObject *obj) const
0101 {
0102    Int_t i = Int_t(obj->Hash() % fSize);  // need intermediary i for Linux g++
0103    return i;
0104 }
0105
0106
0107 //////////////////////////////////////////////////////////////////////////
0108 //                                                                      //
0109 // THashTableIter                                                       //
0110 //                                                                      //
0111 // Iterator of hash table.                                              //
0112 //                                                                      //
0113 //////////////////////////////////////////////////////////////////////////
0114
0115 class THashTableIter : public TIterator {
0116
0117 private:
0118    const THashTable *fTable;       //hash table being iterated
0119    Int_t             fCursor;      //current position in table
0120    TListIter        *fListCursor;  //current position in collision list
0121    Bool_t            fDirection;   //iteration direction
0122
0123    THashTableIter() : fTable(nullptr), fCursor(0), fListCursor(nullptr), fDirection(kIterForward) { }
0124    Int_t             NextSlot();
0125
0126 public:
0127    THashTableIter(const THashTable *ht, Bool_t dir = kIterForward);
0128    THashTableIter(const THashTableIter &iter);
0129    ~THashTableIter();
0130    TIterator      &operator=(const TIterator &rhs) override;
0131    THashTableIter &operator=(const THashTableIter &rhs);
0132
0133    const TCollection *GetCollection() const override { return fTable; }
0134    TObject           *Next() override;
0135    void               Reset() override;
0136    Bool_t             operator!=(const TIterator &aIter) const override;
0137    Bool_t             operator!=(const THashTableIter &aIter) const;
0138    TObject           *operator*() const override;
0139
0140    ClassDefOverride(THashTableIter,0)  //Hash table iterator
0141 };
0142
0143 #endif