TExMap.cxx

Go to the documentation of this file.

// @(#)root/cont:$Id$
// Author: Fons Rademakers   26/05/99
 
/*************************************************************************
 * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers.               *
 * All rights reserved.                                                  *
 *                                                                       *
 * For the licensing terms see $ROOTSYS/LICENSE.                         *
 * For the list of contributors see $ROOTSYS/README/CREDITS.             *
 *************************************************************************/
 
/** \class TExMap
 
This class stores a (key,value) pair using an external hash.
The (key,value) are Long64_t's and therefore can contain object
pointers or any longs. The map uses an open addressing hashing
method (linear probing).
*/
 
#include "TExMap.h"
#include "TBuffer.h"
#include "TError.h"
#include "TMathBase.h"
#include <string.h>
 
 
ClassImp(TExMap);
 
////////////////////////////////////////////////////////////////////////////////
/// Create a TExMap.
 
TExMap::TExMap(Int_t mapSize)
{
   // needed for automatic resizing to guarantee that one slot is always empty
   if (mapSize < 4) mapSize = 5;
 
   switch (mapSize) {
      // Avoid calling NextPrime for the common case:
      case   5: fSize = 5; break;
      case 503: fSize = 503; break;
      default:
         fSize  = (Int_t)TMath::NextPrime(mapSize);
   }
   fTable = new Assoc_t [fSize];
 
   memset(fTable,0,sizeof(Assoc_t)*fSize);
   fTally = 0;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Copy constructor.
 
TExMap::TExMap(const TExMap &map) : TObject(map)
{
   fSize  = map.fSize;
   fTally = map.fTally;
   fTable = new Assoc_t [fSize];
   memcpy(fTable, map.fTable, fSize*sizeof(Assoc_t));
}
 
////////////////////////////////////////////////////////////////////////////////
/// Assignment operator.
 
TExMap& TExMap::operator=(const TExMap &map)
{
   if (this != &map) {
      TObject::operator=(map);
      fSize  = map.fSize;
      fTally = map.fTally;
      fTable = new Assoc_t [fSize];
      memcpy(fTable, map.fTable, fSize*sizeof(Assoc_t));
   }
   return *this;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Delete TExMap.
 
TExMap::~TExMap()
{
   delete [] fTable; fTable = 0;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Add an (key,value) pair to the table. The key should be unique.
 
void TExMap::Add(ULong64_t hash, Long64_t key, Long64_t value)
{
   if (!fTable) return;
 
   Int_t slot = FindElement(hash, key);
   if (!fTable[slot].InUse()) {
      fTable[slot].SetHash(hash);
      fTable[slot].fKey = key;
      fTable[slot].fValue = value;
      fTally++;
      if (HighWaterMark())
         Expand(2 * fSize);
   } else
      Error("Add", "key %lld is not unique", key);
}
 
////////////////////////////////////////////////////////////////////////////////
/// Add an (key,value) pair to the table. The key should be unique.
/// If the 'slot' is open, use it to store the value,
/// otherwise revert to Add(hash,key,value)
/// This is usually used in conjunction with GetValue with 3 parameters:
/// ~~~ {.cpp}
/// if ((idx = (ULong64_t)fMap->GetValue(hash, key, slot)) != 0) {
///    ...
/// } else {
///    fMap->AddAt(slot,hash,key,value);
/// }
/// ~~~
 
void TExMap::AddAt(UInt_t slot, ULong64_t hash, Long64_t key, Long64_t value)
{
   if (!fTable) return;
 
   if (!fTable[slot].InUse()) {
      fTable[slot].SetHash(hash);
      fTable[slot].fKey = key;
      fTable[slot].fValue = value;
      fTally++;
      if (HighWaterMark())
         Expand(2 * fSize);
   } else {
      Add(hash,key,value);
   }
}
 
////////////////////////////////////////////////////////////////////////////////
/// Return a reference to the value belonging to the key with the
/// specified hash value. If the key does not exist it will be added.
/// NOTE: the reference will be invalidated an Expand() triggered by
/// an Add() or another operator() call.
 
Long64_t &TExMap::operator()(ULong64_t hash, Long64_t key)
{
   static Long64_t err;
   if (!fTable) {
      Error("operator()", "fTable==0, should never happen");
      return err;
   }
 
   Int_t slot = FindElement(hash, key);
   if (!fTable[slot].InUse()) {
      fTable[slot].SetHash(hash);
      fTable[slot].fKey = key;
      fTable[slot].fValue = 0;
      fTally++;
      if (HighWaterMark()) {
         Expand(2 * fSize);
         slot = FindElement(hash, key);
      }
   }
   return fTable[slot].fValue;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Delete all entries stored in the TExMap.
 
void TExMap::Delete(Option_t *)
{
   memset(fTable,0,sizeof(Assoc_t)*fSize);
   fTally = 0;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Return the value belonging to specified key and hash value. If key not
/// found return 0.
 
Long64_t TExMap::GetValue(ULong64_t hash, Long64_t key)
{
   if (!fTable) return 0;
 
   hash |= 0x1;
   Int_t slot = Int_t(hash % fSize);
   Int_t firstSlot = slot;
   do {
      if (!fTable[slot].InUse()) return 0;
      if (key == fTable[slot].fKey) return fTable[slot].fValue;
      if (++slot == fSize) slot = 0;
   } while (firstSlot != slot);
 
   Error("GetValue", "table full");
   return 0;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Return the value belonging to specified key and hash value. If key not
/// found return 0.
/// In 'slot', return the index of the slot used or the first empty slot.
/// (to be used with AddAt).
 
Long64_t TExMap::GetValue(ULong64_t hash, Long64_t key, UInt_t &slot)
{
   if (!fTable) { slot = 0; return 0; }
 
   hash |= 0x1;
   slot = Int_t(hash % fSize);
   UInt_t firstSlot = slot;
   do {
      if (!fTable[slot].InUse()) return 0;
      if (key == fTable[slot].fKey) return fTable[slot].fValue;
      if (++slot == (UInt_t)fSize) slot = 0;
   } while (firstSlot != slot);
 
   Error("GetValue", "table full");
   return 0;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Remove entry with specified key from the TExMap.
 
void TExMap::Remove(ULong64_t hash, Long64_t key)
{
   if (!fTable)
      return;
 
   Int_t i = FindElement(hash, key);
   if (!fTable[i].InUse()) {
      Error("Remove", "key %lld not found at %d", key, i);
      return;
   }
 
   fTable[i].Clear();
   FixCollisions(i);
   fTally--;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Find an entry with specified hash and key in the TExMap.
/// Returns the slot of the key or the next empty slot.
 
Int_t TExMap::FindElement(ULong64_t hash, Long64_t key)
{
   if (!fTable) return 0;
 
   hash |= 0x1;
   Int_t slot = Int_t(hash % fSize);
   Int_t firstSlot = slot;
   do {
      if (!fTable[slot].InUse()) return slot;
      if (key == fTable[slot].fKey) return slot;
      if (++slot == fSize) slot = 0;
   } while (firstSlot != slot);
 
   Error("FindElement", "table full");
   return 0;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Rehash the map in case an entry has been removed.
 
void TExMap::FixCollisions(Int_t index)
{
   Int_t oldIndex, nextIndex;
   Assoc_t nextObject;
 
   for (oldIndex = index+1; ;oldIndex++) {
      if (oldIndex >= fSize)
         oldIndex = 0;
      nextObject = fTable[oldIndex];
      if (!nextObject.InUse())
         break;
      nextIndex = FindElement(nextObject.GetHash(), nextObject.fKey);
      if (nextIndex != oldIndex) {
         fTable[nextIndex] = nextObject;
         fTable[oldIndex].Clear();
      }
   }
}
 
////////////////////////////////////////////////////////////////////////////////
/// Expand the TExMap.
 
void TExMap::Expand(Int_t newSize)
{
   Int_t i;
   Assoc_t *oldTable = fTable;
   Int_t oldsize = fSize;
   newSize = (Int_t)TMath::NextPrime(newSize);
   fTable  = new Assoc_t [newSize];
 
   for (i = newSize; --i >= 0;) {
      fTable[i].Clear();
   }
 
   fSize = newSize;
   for (i = 0; i < oldsize; i++)
      if (oldTable[i].InUse()) {
         Int_t slot = FindElement(oldTable[i].GetHash(), oldTable[i].fKey);
         if (!fTable[slot].InUse())
            fTable[slot] = oldTable[i];
         else
            Error("Expand", "slot %d not empty (should never happen)", slot);
      }
   delete [] oldTable;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Stream all objects in the collection to or from the I/O buffer.
 
void TExMap::Streamer(TBuffer &b)
{
   Int_t i;
   UInt_t R__s, R__c;
 
   if (b.IsReading()) {
      Version_t R__v = b.ReadVersion(&R__s, &R__c);
      TObject::Streamer(b);
 
      if (R__v >= 3) {
         // new custom streamer with slots indices stored (Long64_t version).
         Int_t size, tally;
         b >> size;
         Expand(size);
         b >> tally;
         Int_t slot;
         ULong64_t hash;
         Long64_t key, value;
         for (i = 0; i < tally; ++i) {
            b >> slot;
            b >> hash;
            b >> key;
            b >> value;
            Assoc_t *assoc = fTable + slot;
            assoc->SetHash(hash);
            assoc->fKey = key;
            assoc->fValue = value;
         }
         fTally = tally;
      } else if (R__v >= 2) {
         // new custom streamer with slots indices stored.
         Int_t size, tally;
         b >> size;
         Expand(size);
         b >> tally;
         Int_t slot;
         ULong_t hash;
         Long_t key, value;
         for (i = 0; i < tally; ++i) {
            b >> slot;
            b >> hash;
            b >> key;
            b >> value;
            Assoc_t* assoc = fTable + slot;
            assoc->SetHash(hash);
            assoc->fKey = key;
            assoc->fValue = value;
         }
         fTally = tally;
      } else {
         // old custom streamer that only allows slow dynamic rebuild of TExMap:
         Int_t n;
         b >> n;
         ULong_t hash;
         Long_t key, value;
         for (i = 0; i < n; i++) {
            b >> hash;
            b >> key;
            b >> value;
            Add(hash, key, value);
         }
      }
      b.CheckByteCount(R__s, R__c, TExMap::IsA());
   } else {
      R__c = b.WriteVersion(TExMap::IsA(), kTRUE);
      // new custom streamer stores slots indices
      TObject::Streamer(b);
      b << fSize;
      b << fTally;
 
      for (i=0; i < fSize; i++) {
         if (!fTable[i].InUse()) continue;
         b << i;
         b << fTable[i].GetHash();
         b << fTable[i].fKey;
         b << fTable[i].fValue;
      }
      b.SetByteCount(R__c, kTRUE);
   }
}
 
 
ClassImp(TExMapIter);
 
////////////////////////////////////////////////////////////////////////////////
/// Create TExMap iterator.
 
TExMapIter::TExMapIter(const TExMap *map) : fMap(map), fCursor(0)
{
}
 
////////////////////////////////////////////////////////////////////////////////
/// Overloaded assignment operator.
 
TExMapIter &TExMapIter::operator=(const TExMapIter &rhs)
{
   if (this != &rhs) {
      fMap    = rhs.fMap;
      fCursor = rhs.fCursor;
   }
   return *this;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Get next entry from TExMap. Returns kFALSE at end of map.
 
Bool_t TExMapIter::Next(ULong64_t &hash, Long64_t &key, Long64_t &value)
{
   while (fCursor < fMap->fSize && !fMap->fTable[fCursor].InUse())
      fCursor++;
 
   if (fCursor == fMap->fSize)
      return kFALSE;
 
   hash  = fMap->fTable[fCursor].GetHash();
   key   = fMap->fTable[fCursor].fKey;
   value = fMap->fTable[fCursor].fValue;
   fCursor++;
 
   return kTRUE;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Get next entry from TExMap. Returns kFALSE at end of map.
 
Bool_t TExMapIter::Next(Long64_t &key, Long64_t &value)
{
   ULong64_t hash;
   return Next(hash, key, value);
}