Logo ROOT   6.19/01
Reference Guide
TExMap.cxx
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 /** \class TExMap
13 
14 This class stores a (key,value) pair using an external hash.
15 The (key,value) are Long64_t's and therefore can contain object
16 pointers or any longs. The map uses an open addressing hashing
17 method (linear probing).
18 */
19 
20 #include "TExMap.h"
21 #include "TBuffer.h"
22 #include "TError.h"
23 #include "TMathBase.h"
24 #include <string.h>
25 
26 
28 
29 ////////////////////////////////////////////////////////////////////////////////
30 /// Create a TExMap.
31 
33 {
34  // needed for automatic resizing to guarantee that one slot is always empty
35  if (mapSize < 4) mapSize = 5;
36 
37  switch (mapSize) {
38  // Avoid calling NextPrime for the common case:
39  case 5: fSize = 5; break;
40  case 503: fSize = 503; break;
41  default:
42  fSize = (Int_t)TMath::NextPrime(mapSize);
43  }
44  fTable = new Assoc_t [fSize];
45 
46  memset(fTable,0,sizeof(Assoc_t)*fSize);
47  fTally = 0;
48 }
49 
50 ////////////////////////////////////////////////////////////////////////////////
51 /// Copy constructor.
52 
53 TExMap::TExMap(const TExMap &map) : TObject(map)
54 {
55  fSize = map.fSize;
56  fTally = map.fTally;
57  fTable = new Assoc_t [fSize];
58  memcpy(fTable, map.fTable, fSize*sizeof(Assoc_t));
59 }
60 
61 ////////////////////////////////////////////////////////////////////////////////
62 /// Assignment operator.
63 
65 {
66  if (this != &map) {
67  TObject::operator=(map);
68  fSize = map.fSize;
69  fTally = map.fTally;
70  fTable = new Assoc_t [fSize];
71  memcpy(fTable, map.fTable, fSize*sizeof(Assoc_t));
72  }
73  return *this;
74 }
75 
76 ////////////////////////////////////////////////////////////////////////////////
77 /// Delete TExMap.
78 
80 {
81  delete [] fTable; fTable = 0;
82 }
83 
84 ////////////////////////////////////////////////////////////////////////////////
85 /// Add an (key,value) pair to the table. The key should be unique.
86 
87 void TExMap::Add(ULong64_t hash, Long64_t key, Long64_t value)
88 {
89  if (!fTable) return;
90 
91  Int_t slot = FindElement(hash, key);
92  if (!fTable[slot].InUse()) {
93  fTable[slot].SetHash(hash);
94  fTable[slot].fKey = key;
95  fTable[slot].fValue = value;
96  fTally++;
97  if (HighWaterMark())
98  Expand(2 * fSize);
99  } else
100  Error("Add", "key %lld is not unique", key);
101 }
102 
103 ////////////////////////////////////////////////////////////////////////////////
104 /// Add an (key,value) pair to the table. The key should be unique.
105 /// If the 'slot' is open, use it to store the value,
106 /// otherwise revert to Add(hash,key,value)
107 /// This is usually used in conjunction with GetValue with 3 parameters:
108 /// ~~~ {.cpp}
109 /// if ((idx = (ULong64_t)fMap->GetValue(hash, key, slot)) != 0) {
110 /// ...
111 /// } else {
112 /// fMap->AddAt(slot,hash,key,value);
113 /// }
114 /// ~~~
115 
116 void TExMap::AddAt(UInt_t slot, ULong64_t hash, Long64_t key, Long64_t value)
117 {
118  if (!fTable) return;
119 
120  if (!fTable[slot].InUse()) {
121  fTable[slot].SetHash(hash);
122  fTable[slot].fKey = key;
123  fTable[slot].fValue = value;
124  fTally++;
125  if (HighWaterMark())
126  Expand(2 * fSize);
127  } else {
128  Add(hash,key,value);
129  }
130 }
131 
132 ////////////////////////////////////////////////////////////////////////////////
133 /// Return a reference to the value belonging to the key with the
134 /// specified hash value. If the key does not exist it will be added.
135 /// NOTE: the reference will be invalidated an Expand() triggered by
136 /// an Add() or another operator() call.
137 
139 {
140  static Long64_t err;
141  if (!fTable) {
142  Error("operator()", "fTable==0, should never happen");
143  return err;
144  }
145 
146  Int_t slot = FindElement(hash, key);
147  if (!fTable[slot].InUse()) {
148  fTable[slot].SetHash(hash);
149  fTable[slot].fKey = key;
150  fTable[slot].fValue = 0;
151  fTally++;
152  if (HighWaterMark()) {
153  Expand(2 * fSize);
154  slot = FindElement(hash, key);
155  }
156  }
157  return fTable[slot].fValue;
158 }
159 
160 ////////////////////////////////////////////////////////////////////////////////
161 /// Delete all entries stored in the TExMap.
162 
164 {
165  memset(fTable,0,sizeof(Assoc_t)*fSize);
166  fTally = 0;
167 }
168 
169 ////////////////////////////////////////////////////////////////////////////////
170 /// Return the value belonging to specified key and hash value. If key not
171 /// found return 0.
172 
174 {
175  if (!fTable) return 0;
176 
177  hash |= 0x1;
178  Int_t slot = Int_t(hash % fSize);
179  Int_t firstSlot = slot;
180  do {
181  if (!fTable[slot].InUse()) return 0;
182  if (key == fTable[slot].fKey) return fTable[slot].fValue;
183  if (++slot == fSize) slot = 0;
184  } while (firstSlot != slot);
185 
186  Error("GetValue", "table full");
187  return 0;
188 }
189 
190 ////////////////////////////////////////////////////////////////////////////////
191 /// Return the value belonging to specified key and hash value. If key not
192 /// found return 0.
193 /// In 'slot', return the index of the slot used or the first empty slot.
194 /// (to be used with AddAt).
195 
197 {
198  if (!fTable) { slot = 0; return 0; }
199 
200  hash |= 0x1;
201  slot = Int_t(hash % fSize);
202  UInt_t firstSlot = slot;
203  do {
204  if (!fTable[slot].InUse()) return 0;
205  if (key == fTable[slot].fKey) return fTable[slot].fValue;
206  if (++slot == (UInt_t)fSize) slot = 0;
207  } while (firstSlot != slot);
208 
209  Error("GetValue", "table full");
210  return 0;
211 }
212 
213 ////////////////////////////////////////////////////////////////////////////////
214 /// Remove entry with specified key from the TExMap.
215 
217 {
218  if (!fTable)
219  return;
220 
221  Int_t i = FindElement(hash, key);
222  if (!fTable[i].InUse()) {
223  Error("Remove", "key %lld not found at %d", key, i);
224  return;
225  }
226 
227  fTable[i].Clear();
228  FixCollisions(i);
229  fTally--;
230 }
231 
232 ////////////////////////////////////////////////////////////////////////////////
233 /// Find an entry with specified hash and key in the TExMap.
234 /// Returns the slot of the key or the next empty slot.
235 
237 {
238  if (!fTable) return 0;
239 
240  hash |= 0x1;
241  Int_t slot = Int_t(hash % fSize);
242  Int_t firstSlot = slot;
243  do {
244  if (!fTable[slot].InUse()) return slot;
245  if (key == fTable[slot].fKey) return slot;
246  if (++slot == fSize) slot = 0;
247  } while (firstSlot != slot);
248 
249  Error("FindElement", "table full");
250  return 0;
251 }
252 
253 ////////////////////////////////////////////////////////////////////////////////
254 /// Rehash the map in case an entry has been removed.
255 
257 {
258  Int_t oldIndex, nextIndex;
259  Assoc_t nextObject;
260 
261  for (oldIndex = index+1; ;oldIndex++) {
262  if (oldIndex >= fSize)
263  oldIndex = 0;
264  nextObject = fTable[oldIndex];
265  if (!nextObject.InUse())
266  break;
267  nextIndex = FindElement(nextObject.GetHash(), nextObject.fKey);
268  if (nextIndex != oldIndex) {
269  fTable[nextIndex] = nextObject;
270  fTable[oldIndex].Clear();
271  }
272  }
273 }
274 
275 ////////////////////////////////////////////////////////////////////////////////
276 /// Expand the TExMap.
277 
278 void TExMap::Expand(Int_t newSize)
279 {
280  Int_t i;
281  Assoc_t *oldTable = fTable;
282  Int_t oldsize = fSize;
283  newSize = (Int_t)TMath::NextPrime(newSize);
284  fTable = new Assoc_t [newSize];
285 
286  for (i = newSize; --i >= 0;) {
287  fTable[i].Clear();
288  }
289 
290  fSize = newSize;
291  for (i = 0; i < oldsize; i++)
292  if (oldTable[i].InUse()) {
293  Int_t slot = FindElement(oldTable[i].GetHash(), oldTable[i].fKey);
294  if (!fTable[slot].InUse())
295  fTable[slot] = oldTable[i];
296  else
297  Error("Expand", "slot %d not empty (should never happen)", slot);
298  }
299  delete [] oldTable;
300 }
301 
302 ////////////////////////////////////////////////////////////////////////////////
303 /// Stream all objects in the collection to or from the I/O buffer.
304 
305 void TExMap::Streamer(TBuffer &b)
306 {
307  Int_t i;
308  UInt_t R__s, R__c;
309 
310  if (b.IsReading()) {
311  Version_t R__v = b.ReadVersion(&R__s, &R__c);
312  TObject::Streamer(b);
313 
314  if (R__v >= 3) {
315  // new custom streamer with slots indices stored (Long64_t version).
316  Int_t size, tally;
317  b >> size;
318  Expand(size);
319  b >> tally;
320  Int_t slot;
321  ULong64_t hash;
322  Long64_t key, value;
323  for (i = 0; i < tally; ++i) {
324  b >> slot;
325  b >> hash;
326  b >> key;
327  b >> value;
328  Assoc_t *assoc = fTable + slot;
329  assoc->SetHash(hash);
330  assoc->fKey = key;
331  assoc->fValue = value;
332  }
333  fTally = tally;
334  } else if (R__v >= 2) {
335  // new custom streamer with slots indices stored.
336  Int_t size, tally;
337  b >> size;
338  Expand(size);
339  b >> tally;
340  Int_t slot;
341  ULong_t hash;
342  Long_t key, value;
343  for (i = 0; i < tally; ++i) {
344  b >> slot;
345  b >> hash;
346  b >> key;
347  b >> value;
348  Assoc_t* assoc = fTable + slot;
349  assoc->SetHash(hash);
350  assoc->fKey = key;
351  assoc->fValue = value;
352  }
353  fTally = tally;
354  } else {
355  // old custom streamer that only allows slow dynamic rebuild of TExMap:
356  Int_t n;
357  b >> n;
358  ULong_t hash;
359  Long_t key, value;
360  for (i = 0; i < n; i++) {
361  b >> hash;
362  b >> key;
363  b >> value;
364  Add(hash, key, value);
365  }
366  }
367  b.CheckByteCount(R__s, R__c, TExMap::IsA());
368  } else {
369  R__c = b.WriteVersion(TExMap::IsA(), kTRUE);
370  // new custom streamer stores slots indices
371  TObject::Streamer(b);
372  b << fSize;
373  b << fTally;
374 
375  for (i=0; i < fSize; i++) {
376  if (!fTable[i].InUse()) continue;
377  b << i;
378  b << fTable[i].GetHash();
379  b << fTable[i].fKey;
380  b << fTable[i].fValue;
381  }
382  b.SetByteCount(R__c, kTRUE);
383  }
384 }
385 
386 
388 
389 ////////////////////////////////////////////////////////////////////////////////
390 /// Create TExMap iterator.
391 
392 TExMapIter::TExMapIter(const TExMap *map) : fMap(map), fCursor(0)
393 {
394 }
395 
396 ////////////////////////////////////////////////////////////////////////////////
397 /// Overloaded assignment operator.
398 
400 {
401  if (this != &rhs) {
402  fMap = rhs.fMap;
403  fCursor = rhs.fCursor;
404  }
405  return *this;
406 }
407 
408 ////////////////////////////////////////////////////////////////////////////////
409 /// Get next entry from TExMap. Returns kFALSE at end of map.
410 
412 {
413  while (fCursor < fMap->fSize && !fMap->fTable[fCursor].InUse())
414  fCursor++;
415 
416  if (fCursor == fMap->fSize)
417  return kFALSE;
418 
419  hash = fMap->fTable[fCursor].GetHash();
420  key = fMap->fTable[fCursor].fKey;
421  value = fMap->fTable[fCursor].fValue;
422  fCursor++;
423 
424  return kTRUE;
425 }
426 
427 ////////////////////////////////////////////////////////////////////////////////
428 /// Get next entry from TExMap. Returns kFALSE at end of map.
429 
431 {
432  ULong64_t hash;
433  return Next(hash, key, value);
434 }
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
short Version_t
Definition: RtypesCore.h:61
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
Buffer base class used for serializing objects.
Definition: TBuffer.h:42
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
void SetHash(ULong64_t h)
Definition: TExMap.h:44
ULong64_t GetHash() const
Definition: TExMap.h:45
TObject & operator=(const TObject &rhs)
TObject assignment operator.
Definition: TObject.h:268
~TExMap()
Delete TExMap.
Definition: TExMap.cxx:79
Long64_t GetValue(ULong64_t hash, Long64_t key)
Return the value belonging to specified key and hash value.
Definition: TExMap.cxx:173
unsigned int UInt_t
Definition: RtypesCore.h:42
Int_t fTally
Definition: TExMap.h:52
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition: TObject.cxx:880
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
const Bool_t kFALSE
Definition: RtypesCore.h:88
TExMap & operator=(const TExMap &)
Assignment operator.
Definition: TExMap.cxx:64
long Long_t
Definition: RtypesCore.h:50
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
#define ClassImp(name)
Definition: Rtypes.h:365
Bool_t InUse() const
Definition: TExMap.h:46
unsigned long long ULong64_t
Definition: RtypesCore.h:70
unsigned long ULong_t
Definition: RtypesCore.h:51
Mother of all ROOT objects.
Definition: TObject.h:37
Long_t NextPrime(Long_t x)
TMath Base functionsDefine the functions Min, Max, Abs, Sign, Range for all types.
Definition: TMathBase.cxx:30
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
you should not use this method at all Int_t Int_t Double_t Double_t Double_t Int_t Double_t Double_t Double_t Double_t b
Definition: TRolke.cxx:630
void Clear()
Definition: TExMap.h:47
TExMap(Int_t mapSize=100)
Create a TExMap.
Definition: TExMap.cxx:32
const Bool_t kTRUE
Definition: RtypesCore.h:87
const Int_t n
Definition: legend1.C:16
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