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