TExMap.cxx

Go to the documentation of this file.
00001 // @(#)root/cont:$Id: TExMap.cxx 34226 2010-06-30 12:03:31Z brun $
00002 // Author: Fons Rademakers   26/05/99
00003 
00004 /*************************************************************************
00005  * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers.               *
00006  * All rights reserved.                                                  *
00007  *                                                                       *
00008  * For the licensing terms see $ROOTSYS/LICENSE.                         *
00009  * For the list of contributors see $ROOTSYS/README/CREDITS.             *
00010  *************************************************************************/
00011 
00012 //////////////////////////////////////////////////////////////////////////
00013 //                                                                      //
00014 // TExMap                                                               //
00015 //                                                                      //
00016 // This class stores a (key,value) pair using an external hash.         //
00017 // The (key,value) are Long64_t's and therefore can contain object      //
00018 // pointers or any longs. The map uses an open addressing hashing       //
00019 // method (linear probing).                                             //
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    // Create a TExMap.
00035 
00036    // needed for automatic resizing to guarantee that one slot is always empty
00037    if (mapSize < 4) mapSize = 5;
00038 
00039    switch (mapSize) {
00040       // Avoid calling NextPrime for the common case:
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    // Copy constructor.
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    // Assignement operator.
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    // Delete TExMap.
00082 
00083    delete [] fTable; fTable = 0;
00084 }
00085 
00086 //______________________________________________________________________________
00087 void TExMap::Add(ULong64_t hash, Long64_t key, Long64_t value)
00088 {
00089    // Add an (key,value) pair to the table. The key should be unique.
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    // Add an (key,value) pair to the table. The key should be unique.
00109    // If the 'slot' is open, use it to store the value,
00110    // otherwise revert to Add(hash,key,value)
00111    // This is usually used in conjuction with GetValue wiht 3 parameters:
00112    // if ((idx = (ULong64_t)fMap->GetValue(hash, key, slot)) != 0) {
00113    //    ...
00114    // } else {
00115    //    fMap->AddAt(slot,hash,key,value);
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    // Return a reference to the value belonging to the key with the
00136    // specified hash value. If the key does not exist it will be added.
00137    // NOTE: the reference will be invalidated an Expand() triggered by
00138    // an Add() or another operator() call.
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    // Delete all entries stored in the TExMap.
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    // Return the value belonging to specified key and hash value. If key not
00173    // found return 0.
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    // Return the value belonging to specified key and hash value. If key not
00194    // found return 0.
00195    // In 'slot', return the index of the slot used or the first empty slot.
00196    // (to be used with AddAt).
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    // Remove entry with specified key from the TExMap.
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    // Find an entry with specified hash and key in the TExMap.
00236    // Returns the slot of the key or the next empty slot.
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    // Rehash the map in case an entry has been removed.
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    // Expand the TExMap.
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    // Stream all objects in the collection to or from the I/O buffer.
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          // new custom streamer with slots indices stored (Long64_t version).
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          // new custom streamer with slots indices stored.
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          // old custom streamer that only allows slow dynamic rebuild of TExMap:
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       // new custom streamer stores slots indices
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    // Create TExMap iterator.
00393 }
00394 
00395 //______________________________________________________________________________
00396 TExMapIter &TExMapIter::operator=(const TExMapIter &rhs)
00397 {
00398    // Overloaded assignment operator.
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    // Get next entry from TExMap. Returns kFALSE at end of map.
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    // Get next entry from TExMap. Returns kFALSE at end of map.
00430 
00431    ULong64_t hash;
00432    return Next(hash, key, value);
00433 }

Generated on Tue Jul 5 14:11:37 2011 for ROOT_528-00b_version by  doxygen 1.5.1