Logo ROOT   6.30.04
Reference Guide
 All Namespaces Files Pages
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:
40  ULong64_t fHash;
41  public:
42  Long64_t fKey;
43  Long64_t fValue;
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 
50  Assoc_t *fTable;
51  Int_t fSize;
52  Int_t fTally;
53 
54  Bool_t HighWaterMark() { return (Bool_t) (fTally >= ((3*fSize)/4)); }
55  Int_t FindElement(ULong64_t hash, Long64_t key);
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; }
72  Long64_t GetValue(ULong64_t hash, Long64_t key);
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 
78  Long64_t &operator()(ULong64_t hash, Long64_t key);
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;
89  Int_t fCursor;
90 
91 public:
92  TExMapIter(const TExMap *map);
93  TExMapIter(const TExMapIter& tei) : fMap(tei.fMap), fCursor(tei.fCursor) { }
94  TExMapIter& operator=(const TExMapIter&);
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