Logo ROOT   6.18/05
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
14This class stores a (key,value) pair using an external hash.
15The (key,value) are Long64_t's and therefore can contain object
16pointers or any longs. The map uses an open addressing hashing
17method (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
53TExMap::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) {
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
87void 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
116void 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
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
305void 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
392TExMapIter::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}
#define b(i)
Definition: RSha256.hxx:100
int Int_t
Definition: RtypesCore.h:41
short Version_t
Definition: RtypesCore.h:61
unsigned int UInt_t
Definition: RtypesCore.h:42
const Bool_t kFALSE
Definition: RtypesCore.h:88
unsigned long ULong_t
Definition: RtypesCore.h:51
long Long_t
Definition: RtypesCore.h:50
bool Bool_t
Definition: RtypesCore.h:59
long long Long64_t
Definition: RtypesCore.h:69
unsigned long long ULong64_t
Definition: RtypesCore.h:70
const Bool_t kTRUE
Definition: RtypesCore.h:87
const char Option_t
Definition: RtypesCore.h:62
#define ClassImp(name)
Definition: Rtypes.h:365
Buffer base class used for serializing objects.
Definition: TBuffer.h:42
TExMapIter(const TExMap *map)
Create TExMap iterator.
Definition: TExMap.cxx:392
const TExMap * fMap
Definition: TExMap.h:88
Int_t fCursor
Definition: TExMap.h:89
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 Expand(Int_t newsize)
Expand the TExMap.
Definition: TExMap.cxx:278
Int_t fSize
Definition: TExMap.h:51
Int_t fTally
Definition: TExMap.h:52
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
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
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
TObject & operator=(const TObject &rhs)
TObject assignment operator.
Definition: TObject.h:268
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition: TObject.cxx:880
Long_t NextPrime(Long_t x)
TMath Base functions.
Definition: TMathBase.cxx:30
const Int_t n
Definition: legend1.C:16
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