include/root/TExMap.h

0001 // @(#)root/cont:$Id$
0002 // Author: Fons Rademakers   26/05/99
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_TExMap
0013 #define ROOT_TExMap
0014
0015
0016 //////////////////////////////////////////////////////////////////////////
0017 //                                                                      //
0018 // TExMap                                                               //
0019 //                                                                      //
0020 // This class stores a (key,value) pair using an external hash.         //
0021 // The (key,value) are Long64_t's and therefore can contain object      //
0022 // pointers or any longs. The map uses an open addressing hashing       //
0023 // method (linear probing).                                             //
0024 //                                                                      //
0025 //////////////////////////////////////////////////////////////////////////
0026
0027
0028 #include "TObject.h"
0029
0030 class TExMapIter;
0031
0032
0033 class TExMap : public TObject {
0034
0035 friend class TExMapIter;
0036
0037 private:
0038    struct Assoc_t {
0039    private:
0040       ULong64_t  fHash;
0041    public:
0042       Long64_t   fKey;
0043       Long64_t   fValue;
0044       void       SetHash(ULong64_t h) { fHash = (h | 1); } // bit(0) is "1" when in use
0045       ULong64_t  GetHash() const { return fHash; }
0046       Bool_t     InUse() const { return fHash & 1; }
0047       void       Clear() { fHash = 0x0; }
0048    };
0049
0050    Assoc_t    *fTable;
0051    Int_t       fSize;
0052    Int_t       fTally;
0053
0054    Bool_t      HighWaterMark() { return (Bool_t) (fTally >= ((3*fSize)/4)); }
0055    Int_t       FindElement(ULong64_t hash, Long64_t key);
0056    void        FixCollisions(Int_t index);
0057
0058
0059 public:
0060    TExMap(Int_t mapSize = 100);
0061    TExMap(const TExMap &map);
0062    TExMap& operator=(const TExMap&);
0063    ~TExMap();
0064
0065    void      Add(ULong64_t hash, Long64_t key, Long64_t value);
0066    void      Add(Long64_t key, Long64_t value) { Add(key, key, value); }
0067    void      AddAt(UInt_t slot, ULong64_t hash, Long64_t key, Long64_t value);
0068    void      Delete(Option_t *opt = "") override;
0069    Int_t     Capacity() const { return fSize; }
0070    void      Expand(Int_t newsize);
0071    Int_t     GetSize() const { return fTally; }
0072    Long64_t  GetValue(ULong64_t hash, Long64_t key);
0073    Long64_t  GetValue(Long64_t key) { return GetValue(key, key); }
0074    Long64_t  GetValue(ULong64_t hash, Long64_t key, UInt_t &slot);
0075    void      Remove(ULong64_t hash, Long64_t key);
0076    void      Remove(Long64_t key) { Remove(key, key); }
0077
0078    Long64_t &operator()(ULong64_t hash, Long64_t key);
0079    Long64_t &operator()(Long64_t key) { return operator()(key, key); }
0080
0081    ClassDefOverride(TExMap,3)  //Map with external hash
0082 };
0083
0084
0085 class TExMapIter {
0086
0087 private:
0088    const TExMap   *fMap;
0089    Int_t           fCursor;
0090
0091 public:
0092    TExMapIter(const TExMap *map);
0093    TExMapIter(const TExMapIter& tei) : fMap(tei.fMap), fCursor(tei.fCursor) { }
0094    TExMapIter& operator=(const TExMapIter&);
0095    virtual ~TExMapIter() { }
0096
0097    const TExMap  *GetCollection() const { return fMap; }
0098    Bool_t         Next(ULong64_t &hash, Long64_t &key, Long64_t &value);
0099    Bool_t         Next(Long64_t &key, Long64_t &value);
0100    void           Reset() { fCursor = 0; }
0101
0102    ClassDef(TExMapIter,0)  // TExMap iterator
0103 };
0104
0105 #endif