Logo ROOT   6.08/07
Reference Guide
TExMap.h
Go to the documentation of this file.
1 // @(#)root/cont:$Id$
2 // Author: Fons Rademakers 26/05/99
3 
4 /*************************************************************************
5  * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers. *
6  * All rights reserved. *
7  * *
8  * For the licensing terms see $ROOTSYS/LICENSE. *
9  * For the list of contributors see $ROOTSYS/README/CREDITS. *
10  *************************************************************************/
11 
12 #ifndef ROOT_TExMap
13 #define ROOT_TExMap
14 
15 
16 //////////////////////////////////////////////////////////////////////////
17 // //
18 // TExMap //
19 // //
20 // This class stores a (key,value) pair using an external hash. //
21 // The (key,value) are Long64_t's and therefore can contain object //
22 // pointers or any longs. The map uses an open addressing hashing //
23 // method (linear probing). //
24 // //
25 //////////////////////////////////////////////////////////////////////////
26 
27 
28 #ifndef ROOT_TObject
29 #include "TObject.h"
30 #endif
31 
32 class TExMapIter;
33 
34 
35 class TExMap : public TObject {
36 
37 friend class TExMapIter;
38 
39 private:
40  struct Assoc_t {
41  private:
43  public:
46  void SetHash(ULong64_t h) { fHash = (h | 1); } // bit(0) is "1" when in use
47  ULong64_t GetHash() const { return fHash; }
48  Bool_t InUse() const { return fHash & 1; }
49  void Clear() { fHash = 0x0; }
50  };
51 
55 
56  Bool_t HighWaterMark() { return (Bool_t) (fTally >= ((3*fSize)/4)); }
58  void FixCollisions(Int_t index);
59 
60 
61 public:
62  TExMap(Int_t mapSize = 100);
63  TExMap(const TExMap &map);
64  TExMap& operator=(const TExMap&);
65  ~TExMap();
66 
67  void Add(ULong64_t hash, Long64_t key, Long64_t value);
68  void Add(Long64_t key, Long64_t value) { Add(key, key, value); }
69  void AddAt(UInt_t slot, ULong64_t hash, Long64_t key, Long64_t value);
70  void Delete(Option_t *opt = "");
71  Int_t Capacity() const { return fSize; }
72  void Expand(Int_t newsize);
73  Int_t GetSize() const { return fTally; }
75  Long64_t GetValue(Long64_t key) { return GetValue(key, key); }
76  Long64_t GetValue(ULong64_t hash, Long64_t key, UInt_t &slot);
77  void Remove(ULong64_t hash, Long64_t key);
78  void Remove(Long64_t key) { Remove(key, key); }
79 
81  Long64_t &operator()(Long64_t key) { return operator()(key, key); }
82 
83  ClassDef(TExMap,3) //Map with external hash
84 };
85 
86 
87 class TExMapIter {
88 
89 private:
90  const TExMap *fMap;
92 
93 public:
94  TExMapIter(const TExMap *map);
95  TExMapIter(const TExMapIter& tei) : fMap(tei.fMap), fCursor(tei.fCursor) { }
97  virtual ~TExMapIter() { }
98 
99  const TExMap *GetCollection() const { return fMap; }
100  Bool_t Next(ULong64_t &hash, Long64_t &key, Long64_t &value);
101  Bool_t Next(Long64_t &key, Long64_t &value);
102  void Reset() { fCursor = 0; }
103 
104  ClassDef(TExMapIter,0) // TExMap iterator
105 };
106 
107 #endif
const TExMap * fMap
Definition: TExMap.h:90
void Add(ULong64_t hash, Long64_t key, Long64_t value)
Add an (key,value) pair to the table. The key should be unique.
Definition: TExMap.cxx:87
void Remove(ULong64_t hash, Long64_t key)
Remove entry with specified key from the TExMap.
Definition: TExMap.cxx:216
long long Long64_t
Definition: RtypesCore.h:69
Int_t GetSize() const
Definition: TExMap.h:73
const char Option_t
Definition: RtypesCore.h:62
Int_t FindElement(ULong64_t hash, Long64_t key)
Find an entry with specified hash and key in the TExMap.
Definition: TExMap.cxx:236
TH1 * h
Definition: legend2.C:5
int Int_t
Definition: RtypesCore.h:41
bool Bool_t
Definition: RtypesCore.h:59
Long64_t fKey
Definition: TExMap.h:44
Int_t fCursor
Definition: TExMap.h:91
Assoc_t * fTable
Definition: TExMap.h:52
Int_t fSize
Definition: TExMap.h:53
#define ClassDef(name, id)
Definition: Rtypes.h:254
void Add(Long64_t key, Long64_t value)
Definition: TExMap.h:68
void SetHash(ULong64_t h)
Definition: TExMap.h:46
ULong64_t GetHash() const
Definition: TExMap.h:47
ULong64_t fHash
Definition: TExMap.h:42
Int_t Capacity() const
Definition: TExMap.h:71
~TExMap()
Delete TExMap.
Definition: TExMap.cxx:79
void Remove(Long64_t key)
Definition: TExMap.h:78
Long64_t GetValue(ULong64_t hash, Long64_t key)
Return the value belonging to specified key and hash value.
Definition: TExMap.cxx:173
void Reset()
Definition: TExMap.h:102
Long64_t & operator()(Long64_t key)
Definition: TExMap.h:81
unsigned int UInt_t
Definition: RtypesCore.h:42
Int_t fTally
Definition: TExMap.h:54
Long64_t & operator()(ULong64_t hash, Long64_t key)
Return a reference to the value belonging to the key with the specified hash value.
Definition: TExMap.cxx:138
Bool_t HighWaterMark()
Definition: TExMap.h:56
void Delete(Option_t *opt="")
Delete all entries stored in the TExMap.
Definition: TExMap.cxx:163
TExMap & operator=(const TExMap &)
Assignment operator.
Definition: TExMap.cxx:64
void FixCollisions(Int_t index)
Rehash the map in case an entry has been removed.
Definition: TExMap.cxx:256
Long64_t fValue
Definition: TExMap.h:45
Bool_t InUse() const
Definition: TExMap.h:48
unsigned long long ULong64_t
Definition: RtypesCore.h:70
Mother of all ROOT objects.
Definition: TObject.h:37
const TExMap * GetCollection() const
Definition: TExMap.h:99
virtual ~TExMapIter()
Definition: TExMap.h:97
Long64_t GetValue(Long64_t key)
Definition: TExMap.h:75
void Clear()
Definition: TExMap.h:49
TExMap(Int_t mapSize=100)
Create a TExMap.
Definition: TExMap.cxx:32
friend class TExMapIter
Definition: TExMap.h:37
This class stores a (key,value) pair using an external hash.
Definition: TExMap.h:35
void Expand(Int_t newsize)
Expand the TExMap.
Definition: TExMap.cxx:278
void AddAt(UInt_t slot, ULong64_t hash, Long64_t key, Long64_t value)
Add an (key,value) pair to the table.
Definition: TExMap.cxx:116
TExMapIter(const TExMapIter &tei)
Definition: TExMap.h:95