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          AddBefore(const TObject *before, TObject *obj);
0060    void          AddAll(const TCollection *col) override;
0061    Float_t       AverageCollisions() const;
0062    void          Clear(Option_t *option="") override;
0063    Int_t         Collisions(const char *name) const;
0064    Int_t         Collisions(TObject *obj) const;
0065    void          Delete(Option_t *option="") override;
0066    Bool_t        Empty() const { return fEntries == 0; }
0067    TObject      *FindObject(const char *name) const override;
0068    TObject      *FindObject(const TObject *obj) const override;
0069    const TList  *GetListForObject(const char *name) const;
0070    const TList  *GetListForObject(const TObject *obj) const;
0071    TObject     **GetObjectRef(const TObject *obj) const override;
0072    Int_t         GetRehashLevel() const { return fRehashLevel; }
0073    Int_t         GetSize() const override { return fEntries; }
0074    TIterator    *MakeIterator(Bool_t dir = kIterForward) const override;
0075    using         TCollection::Print;
0076    void          Print(Option_t *option, Int_t recurse) const override;
0077    void          Rehash(Int_t newCapacity, Bool_t checkObjValidity = kTRUE);
0078    TObject      *Remove(TObject *obj) override;
0079    TObject      *RemoveSlow(TObject *obj);
0080    void          SetRehashLevel(Int_t rehash) { fRehashLevel = rehash; }
0081
0082    ClassDefOverride(THashTable,0)  //A hash table
0083 };
0084
0085 inline Float_t THashTable::AverageCollisions() const
0086 {
0087    if (fUsedSlots)
0088       return ((Float_t)fEntries)/((Float_t)fUsedSlots);
0089    else
0090       return 0.0;
0091 }
0092
0093 inline Int_t THashTable::GetCheckedHashValue(TObject *obj) const
0094 {
0095    Int_t i = Int_t(obj->CheckedHash() % fSize); // need intermediary i for Linux g++
0096    return i;
0097 }
0098
0099 inline Int_t THashTable::GetHashValue(const TObject *obj) const
0100 {
0101    Int_t i = Int_t(obj->Hash() % fSize);  // need intermediary i for Linux g++
0102    return i;
0103 }
0104
0105
0106 //////////////////////////////////////////////////////////////////////////
0107 //                                                                      //
0108 // THashTableIter                                                       //
0109 //                                                                      //
0110 // Iterator of hash table.                                              //
0111 //                                                                      //
0112 //////////////////////////////////////////////////////////////////////////
0113
0114 class THashTableIter : public TIterator {
0115
0116 private:
0117    const THashTable *fTable;       //hash table being iterated
0118    Int_t             fCursor;      //current position in table
0119    TListIter        *fListCursor;  //current position in collision list
0120    Bool_t            fDirection;   //iteration direction
0121
0122    THashTableIter() : fTable(nullptr), fCursor(0), fListCursor(nullptr), fDirection(kIterForward) { }
0123    Int_t             NextSlot();
0124
0125 public:
0126    THashTableIter(const THashTable *ht, Bool_t dir = kIterForward);
0127    THashTableIter(const THashTableIter &iter);
0128    ~THashTableIter();
0129    TIterator      &operator=(const TIterator &rhs) override;
0130    THashTableIter &operator=(const THashTableIter &rhs);
0131
0132    const TCollection *GetCollection() const override { return fTable; }
0133    TObject           *Next() override;
0134    void               Reset() override;
0135    Bool_t             operator!=(const TIterator &aIter) const override;
0136    Bool_t             operator!=(const THashTableIter &aIter) const;
0137    TObject           *operator*() const override;
0138
0139    ClassDefOverride(THashTableIter,0)  //Hash table iterator
0140 };
0141
0142 #endif