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