Logo ROOT   6.19/01
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 #include "TObject.h"
29 
30 class TExMapIter;
31 
32 
33 class TExMap : public TObject {
34 
35 friend class TExMapIter;
36 
37 private:
38  struct Assoc_t {
39  private:
41  public:
44  void SetHash(ULong64_t h) { fHash = (h | 1); } // bit(0) is "1" when in use
45  ULong64_t GetHash() const { return fHash; }
46  Bool_t InUse() const { return fHash & 1; }
47  void Clear() { fHash = 0x0; }
48  };
49 
53 
54  Bool_t HighWaterMark() { return (Bool_t) (fTally >= ((3*fSize)/4)); }
56  void FixCollisions(Int_t index);
57 
58 
59 public:
60  TExMap(Int_t mapSize = 100);
61  TExMap(const TExMap &map);
62  TExMap& operator=(const TExMap&);
63  ~TExMap();
64 
65  void Add(ULong64_t hash, Long64_t key, Long64_t value);
66  void Add(Long64_t key, Long64_t value) { Add(key, key, value); }
67  void AddAt(UInt_t slot, ULong64_t hash, Long64_t key, Long64_t value);
68  void Delete(Option_t *opt = "");
69  Int_t Capacity() const { return fSize; }
70  void Expand(Int_t newsize);
71  Int_t GetSize() const { return fTally; }
73  Long64_t GetValue(Long64_t key) { return GetValue(key, key); }
74  Long64_t GetValue(ULong64_t hash, Long64_t key, UInt_t &slot);
75  void Remove(ULong64_t hash, Long64_t key);
76  void Remove(Long64_t key) { Remove(key, key); }
77 
79  Long64_t &operator()(Long64_t key) { return operator()(key, key); }
80 
81  ClassDef(TExMap,3) //Map with external hash
82 };
83 
84 
85 class TExMapIter {
86 
87 private:
88  const TExMap *fMap;
90 
91 public:
92  TExMapIter(const TExMap *map);
93  TExMapIter(const TExMapIter& tei) : fMap(tei.fMap), fCursor(tei.fCursor) { }
95  virtual ~TExMapIter() { }
96 
97  const TExMap *GetCollection() const { return fMap; }
98  Bool_t Next(ULong64_t &hash, Long64_t &key, Long64_t &value);
99  Bool_t Next(Long64_t &key, Long64_t &value);
100  void Reset() { fCursor = 0; }
101 
102  ClassDef(TExMapIter,0) // TExMap iterator
103 };
104 
105 #endif
const TExMap * fMap
Definition: TExMap.h:88
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:71
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
int Int_t
Definition: RtypesCore.h:41
bool Bool_t
Definition: RtypesCore.h:59
Long64_t fKey
Definition: TExMap.h:42
Int_t fCursor
Definition: TExMap.h:89
Assoc_t * fTable
Definition: TExMap.h:50
Int_t fSize
Definition: TExMap.h:51
TExMapIter(const TExMap *map)
Create TExMap iterator.
Definition: TExMap.cxx:392
#define ClassDef(name, id)
Definition: Rtypes.h:326
void Add(Long64_t key, Long64_t value)
Definition: TExMap.h:66
void SetHash(ULong64_t h)
Definition: TExMap.h:44
ULong64_t GetHash() const
Definition: TExMap.h:45
ULong64_t fHash
Definition: TExMap.h:40
Int_t Capacity() const
Definition: TExMap.h:69
~TExMap()
Delete TExMap.
Definition: TExMap.cxx:79
void Remove(Long64_t key)
Definition: TExMap.h:76
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:100
Long64_t & operator()(Long64_t key)
Definition: TExMap.h:79
unsigned int UInt_t
Definition: RtypesCore.h:42
Int_t fTally
Definition: TExMap.h:52
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:54
void Delete(Option_t *opt="")
Delete all entries stored in the TExMap.
Definition: TExMap.cxx:163
#define h(i)
Definition: RSha256.hxx:106
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
TExMapIter & operator=(const TExMapIter &)
Overloaded assignment operator.
Definition: TExMap.cxx:399
Long64_t fValue
Definition: TExMap.h:43
Bool_t InUse() const
Definition: TExMap.h:46
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:97
Bool_t Next(ULong64_t &hash, Long64_t &key, Long64_t &value)
Get next entry from TExMap. Returns kFALSE at end of map.
Definition: TExMap.cxx:411
virtual ~TExMapIter()
Definition: TExMap.h:95
Long64_t GetValue(Long64_t key)
Definition: TExMap.h:73
void Clear()
Definition: TExMap.h:47
TExMap(Int_t mapSize=100)
Create a TExMap.
Definition: TExMap.cxx:32
This class stores a (key,value) pair using an external hash.
Definition: TExMap.h:33
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:93