Logo ROOT  
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
TExMapIter::Reset
void Reset()
Definition: TExMap.h:100
TExMap::Assoc_t::fValue
Long64_t fValue
Definition: TExMap.h:43
TExMap::Assoc_t::InUse
Bool_t InUse() const
Definition: TExMap.h:46
Option_t
const char Option_t
Definition: RtypesCore.h:66
TExMap::Assoc_t::fKey
Long64_t fKey
Definition: TExMap.h:42
TExMapIter::operator=
TExMapIter & operator=(const TExMapIter &)
Overloaded assignment operator.
Definition: TExMap.cxx:399
TExMap::fSize
Int_t fSize
Definition: TExMap.h:51
TExMap::Add
void Add(Long64_t key, Long64_t value)
Definition: TExMap.h:66
Long64_t
long long Long64_t
Definition: RtypesCore.h:73
TExMap::Assoc_t::Clear
void Clear()
Definition: TExMap.h:47
Int_t
int Int_t
Definition: RtypesCore.h:45
TExMapIter::GetCollection
const TExMap * GetCollection() const
Definition: TExMap.h:97
TExMapIter::Next
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
TExMap::FindElement
Int_t FindElement(ULong64_t hash, Long64_t key)
Find an entry with specified hash and key in the TExMap.
Definition: TExMap.cxx:236
TExMap::GetSize
Int_t GetSize() const
Definition: TExMap.h:71
TExMap::Remove
void Remove(Long64_t key)
Definition: TExMap.h:76
TExMap::GetValue
Long64_t GetValue(ULong64_t hash, Long64_t key)
Return the value belonging to specified key and hash value.
Definition: TExMap.cxx:173
Bool_t
bool Bool_t
Definition: RtypesCore.h:63
bool
TExMap::fTally
Int_t fTally
Definition: TExMap.h:52
TExMap::operator()
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
TExMapIter::~TExMapIter
virtual ~TExMapIter()
Definition: TExMap.h:95
TExMap::Delete
void Delete(Option_t *opt="")
Delete all entries stored in the TExMap.
Definition: TExMap.cxx:163
TExMap::HighWaterMark
Bool_t HighWaterMark()
Definition: TExMap.h:54
TExMap::fTable
Assoc_t * fTable
Definition: TExMap.h:50
TExMapIter::TExMapIter
TExMapIter(const TExMapIter &tei)
Definition: TExMap.h:93
TExMapIter
Definition: TExMap.h:85
h
#define h(i)
Definition: RSha256.hxx:106
TExMapIter::fMap
const TExMap * fMap
Definition: TExMap.h:88
UInt_t
unsigned int UInt_t
Definition: RtypesCore.h:46
TExMap::GetValue
Long64_t GetValue(Long64_t key)
Definition: TExMap.h:73
TExMap::Capacity
Int_t Capacity() const
Definition: TExMap.h:69
TExMap::~TExMap
~TExMap()
Delete TExMap.
Definition: TExMap.cxx:79
TExMap::Assoc_t::fHash
ULong64_t fHash
Definition: TExMap.h:40
TExMap::Assoc_t
Definition: TExMap.h:38
TExMap::TExMap
TExMap(Int_t mapSize=100)
Create a TExMap.
Definition: TExMap.cxx:32
ULong64_t
unsigned long long ULong64_t
Definition: RtypesCore.h:74
TExMap::operator()
Long64_t & operator()(Long64_t key)
Definition: TExMap.h:79
TObject.h
TExMap::Expand
void Expand(Int_t newsize)
Expand the TExMap.
Definition: TExMap.cxx:278
TObject
Mother of all ROOT objects.
Definition: TObject.h:37
ClassDef
#define ClassDef(name, id)
Definition: Rtypes.h:325
TExMapIter::TExMapIter
TExMapIter(const TExMap *map)
Create TExMap iterator.
Definition: TExMap.cxx:392
TExMap::Assoc_t::GetHash
ULong64_t GetHash() const
Definition: TExMap.h:45
TExMap::AddAt
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::fCursor
Int_t fCursor
Definition: TExMap.h:89
TExMap::Remove
void Remove(ULong64_t hash, Long64_t key)
Remove entry with specified key from the TExMap.
Definition: TExMap.cxx:216
TExMap::operator=
TExMap & operator=(const TExMap &)
Assignment operator.
Definition: TExMap.cxx:64
TExMap::FixCollisions
void FixCollisions(Int_t index)
Rehash the map in case an entry has been removed.
Definition: TExMap.cxx:256
TExMap
This class stores a (key,value) pair using an external hash.
Definition: TExMap.h:33
TExMap::Add
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
TExMap::Assoc_t::SetHash
void SetHash(ULong64_t h)
Definition: TExMap.h:44
int