00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #include "TExMap.h"
00024 #include "TError.h"
00025 #include "TMathBase.h"
00026 #include <string.h>
00027
00028
00029 ClassImp(TExMap)
00030
00031
00032 TExMap::TExMap(Int_t mapSize)
00033 {
00034
00035
00036
00037 if (mapSize < 4) mapSize = 5;
00038
00039 switch (mapSize) {
00040
00041 case 5: fSize = 5; break;
00042 case 503: fSize = 503; break;
00043 default:
00044 fSize = (Int_t)TMath::NextPrime(mapSize);
00045 }
00046 fTable = new Assoc_t [fSize];
00047
00048 memset(fTable,0,sizeof(Assoc_t)*fSize);
00049 fTally = 0;
00050 }
00051
00052
00053 TExMap::TExMap(const TExMap &map) : TObject(map)
00054 {
00055
00056
00057 fSize = map.fSize;
00058 fTally = map.fTally;
00059 fTable = new Assoc_t [fSize];
00060 memcpy(fTable, map.fTable, fSize*sizeof(Assoc_t));
00061 }
00062
00063
00064 TExMap& TExMap::operator=(const TExMap &map)
00065 {
00066
00067
00068 if (this != &map) {
00069 TObject::operator=(map);
00070 fSize = map.fSize;
00071 fTally = map.fTally;
00072 fTable = new Assoc_t [fSize];
00073 memcpy(fTable, map.fTable, fSize*sizeof(Assoc_t));
00074 }
00075 return *this;
00076 }
00077
00078
00079 TExMap::~TExMap()
00080 {
00081
00082
00083 delete [] fTable; fTable = 0;
00084 }
00085
00086
00087 void TExMap::Add(ULong64_t hash, Long64_t key, Long64_t value)
00088 {
00089
00090
00091 if (!fTable) return;
00092
00093 Int_t slot = FindElement(hash, key);
00094 if (!fTable[slot].InUse()) {
00095 fTable[slot].SetHash(hash);
00096 fTable[slot].fKey = key;
00097 fTable[slot].fValue = value;
00098 fTally++;
00099 if (HighWaterMark())
00100 Expand(2 * fSize);
00101 } else
00102 Error("Add", "key %lld is not unique", key);
00103 }
00104
00105
00106 void TExMap::AddAt(UInt_t slot, ULong64_t hash, Long64_t key, Long64_t value)
00107 {
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118 if (!fTable) return;
00119
00120 if (!fTable[slot].InUse()) {
00121 fTable[slot].SetHash(hash);
00122 fTable[slot].fKey = key;
00123 fTable[slot].fValue = value;
00124 fTally++;
00125 if (HighWaterMark())
00126 Expand(2 * fSize);
00127 } else {
00128 Add(hash,key,value);
00129 }
00130 }
00131
00132
00133 Long64_t &TExMap::operator()(ULong64_t hash, Long64_t key)
00134 {
00135
00136
00137
00138
00139
00140 static Long64_t err;
00141 if (!fTable) {
00142 Error("operator()", "fTable==0, should never happen");
00143 return err;
00144 }
00145
00146 Int_t slot = FindElement(hash, key);
00147 if (!fTable[slot].InUse()) {
00148 fTable[slot].SetHash(hash);
00149 fTable[slot].fKey = key;
00150 fTable[slot].fValue = 0;
00151 fTally++;
00152 if (HighWaterMark()) {
00153 Expand(2 * fSize);
00154 slot = FindElement(hash, key);
00155 }
00156 }
00157 return fTable[slot].fValue;
00158 }
00159
00160
00161 void TExMap::Delete(Option_t *)
00162 {
00163
00164
00165 memset(fTable,0,sizeof(Assoc_t)*fSize);
00166 fTally = 0;
00167 }
00168
00169
00170 Long64_t TExMap::GetValue(ULong64_t hash, Long64_t key)
00171 {
00172
00173
00174
00175 if (!fTable) return 0;
00176
00177 hash |= 0x1;
00178 Int_t slot = Int_t(hash % fSize);
00179 Int_t firstSlot = slot;
00180 do {
00181 if (!fTable[slot].InUse()) return 0;
00182 if (key == fTable[slot].fKey) return fTable[slot].fValue;
00183 if (++slot == fSize) slot = 0;
00184 } while (firstSlot != slot);
00185
00186 Error("GetValue", "table full");
00187 return 0;
00188 }
00189
00190
00191 Long64_t TExMap::GetValue(ULong64_t hash, Long64_t key, UInt_t &slot)
00192 {
00193
00194
00195
00196
00197
00198 if (!fTable) { slot = 0; return 0; }
00199
00200 hash |= 0x1;
00201 slot = Int_t(hash % fSize);
00202 UInt_t firstSlot = slot;
00203 do {
00204 if (!fTable[slot].InUse()) return 0;
00205 if (key == fTable[slot].fKey) return fTable[slot].fValue;
00206 if (++slot == (UInt_t)fSize) slot = 0;
00207 } while (firstSlot != slot);
00208
00209 Error("GetValue", "table full");
00210 return 0;
00211 }
00212
00213
00214 void TExMap::Remove(ULong64_t hash, Long64_t key)
00215 {
00216
00217
00218 if (!fTable)
00219 return;
00220
00221 Int_t i = FindElement(hash, key);
00222 if (!fTable[i].InUse()) {
00223 Error("Remove", "key %lld not found at %d", key, i);
00224 return;
00225 }
00226
00227 fTable[i].Clear();
00228 FixCollisions(i);
00229 fTally--;
00230 }
00231
00232
00233 Int_t TExMap::FindElement(ULong64_t hash, Long64_t key)
00234 {
00235
00236
00237
00238 if (!fTable) return 0;
00239
00240 hash |= 0x1;
00241 Int_t slot = Int_t(hash % fSize);
00242 Int_t firstSlot = slot;
00243 do {
00244 if (!fTable[slot].InUse()) return slot;
00245 if (key == fTable[slot].fKey) return slot;
00246 if (++slot == fSize) slot = 0;
00247 } while (firstSlot != slot);
00248
00249 Error("FindElement", "table full");
00250 return 0;
00251 }
00252
00253
00254 void TExMap::FixCollisions(Int_t index)
00255 {
00256
00257
00258 Int_t oldIndex, nextIndex;
00259 Assoc_t nextObject;
00260
00261 for (oldIndex = index+1; ;oldIndex++) {
00262 if (oldIndex >= fSize)
00263 oldIndex = 0;
00264 nextObject = fTable[oldIndex];
00265 if (!nextObject.InUse())
00266 break;
00267 nextIndex = FindElement(nextObject.GetHash(), nextObject.fKey);
00268 if (nextIndex != oldIndex) {
00269 fTable[nextIndex] = nextObject;
00270 fTable[oldIndex].Clear();
00271 }
00272 }
00273 }
00274
00275
00276 void TExMap::Expand(Int_t newSize)
00277 {
00278
00279
00280 Int_t i;
00281 Assoc_t *oldTable = fTable;
00282 Int_t oldsize = fSize;
00283 newSize = (Int_t)TMath::NextPrime(newSize);
00284 fTable = new Assoc_t [newSize];
00285
00286 for (i = newSize; --i >= 0;) {
00287 fTable[i].Clear();
00288 }
00289
00290 fSize = newSize;
00291 for (i = 0; i < oldsize; i++)
00292 if (oldTable[i].InUse()) {
00293 Int_t slot = FindElement(oldTable[i].GetHash(), oldTable[i].fKey);
00294 if (!fTable[slot].InUse())
00295 fTable[slot] = oldTable[i];
00296 else
00297 Error("Expand", "slot %d not empty (should never happen)", slot);
00298 }
00299 delete [] oldTable;
00300 }
00301
00302
00303 void TExMap::Streamer(TBuffer &b)
00304 {
00305
00306
00307 Int_t i;
00308 UInt_t R__s, R__c;
00309
00310 if (b.IsReading()) {
00311 Version_t R__v = b.ReadVersion(&R__s, &R__c);
00312 TObject::Streamer(b);
00313
00314 if (R__v >= 3) {
00315
00316 Int_t size, tally;
00317 b >> size;
00318 Expand(size);
00319 b >> tally;
00320 Int_t slot;
00321 ULong64_t hash;
00322 Long64_t key, value;
00323 for (i = 0; i < tally; ++i) {
00324 b >> slot;
00325 b >> hash;
00326 b >> key;
00327 b >> value;
00328 Assoc_t *assoc = fTable + slot;
00329 assoc->SetHash(hash);
00330 assoc->fKey = key;
00331 assoc->fValue = value;
00332 }
00333 fTally = tally;
00334 } else if (R__v >= 2) {
00335
00336 Int_t size, tally;
00337 b >> size;
00338 Expand(size);
00339 b >> tally;
00340 Int_t slot;
00341 ULong_t hash;
00342 Long_t key, value;
00343 for (i = 0; i < tally; ++i) {
00344 b >> slot;
00345 b >> hash;
00346 b >> key;
00347 b >> value;
00348 Assoc_t* assoc = fTable + slot;
00349 assoc->SetHash(hash);
00350 assoc->fKey = key;
00351 assoc->fValue = value;
00352 }
00353 fTally = tally;
00354 } else {
00355
00356 Int_t n;
00357 b >> n;
00358 ULong_t hash;
00359 Long_t key, value;
00360 for (i = 0; i < n; i++) {
00361 b >> hash;
00362 b >> key;
00363 b >> value;
00364 Add(hash, key, value);
00365 }
00366 }
00367 b.CheckByteCount(R__s, R__c, TExMap::IsA());
00368 } else {
00369 R__c = b.WriteVersion(TExMap::IsA(), kTRUE);
00370
00371 TObject::Streamer(b);
00372 b << fSize;
00373 b << fTally;
00374
00375 for (i=0; i < fSize; i++) {
00376 if (!fTable[i].InUse()) continue;
00377 b << i;
00378 b << fTable[i].GetHash();
00379 b << fTable[i].fKey;
00380 b << fTable[i].fValue;
00381 }
00382 b.SetByteCount(R__c, kTRUE);
00383 }
00384 }
00385
00386
00387 ClassImp(TExMapIter)
00388
00389
00390 TExMapIter::TExMapIter(const TExMap *map) : fMap(map), fCursor(0)
00391 {
00392
00393 }
00394
00395
00396 TExMapIter &TExMapIter::operator=(const TExMapIter &rhs)
00397 {
00398
00399
00400 if (this != &rhs) {
00401 fMap = rhs.fMap;
00402 fCursor = rhs.fCursor;
00403 }
00404 return *this;
00405 }
00406
00407
00408 Bool_t TExMapIter::Next(ULong64_t &hash, Long64_t &key, Long64_t &value)
00409 {
00410
00411
00412 while (fCursor < fMap->fSize && !fMap->fTable[fCursor].InUse())
00413 fCursor++;
00414
00415 if (fCursor == fMap->fSize)
00416 return kFALSE;
00417
00418 hash = fMap->fTable[fCursor].GetHash();
00419 key = fMap->fTable[fCursor].fKey;
00420 value = fMap->fTable[fCursor].fValue;
00421 fCursor++;
00422
00423 return kTRUE;
00424 }
00425
00426
00427 Bool_t TExMapIter::Next(Long64_t &key, Long64_t &value)
00428 {
00429
00430
00431 ULong64_t hash;
00432 return Next(hash, key, value);
00433 }