---

TValHashMapT.hh

#ifndef _T_VAL_HASH_MAP_T_HH
#define _T_VAL_HASH_MAP_T_HH

#include <stdio.h>
#include <stdlib.h>
#include "TMemoryException.hh"


// Template class used to hold one key, value pair in a TValHashMapT object.

template <class K, class V>
class TValHashMapEntryT
{
public:
  
  TValHashMapEntryT (const K& k, const V& v)
    : key (k),
      value (v)
  {
  }
  
  TValHashMapEntryT *next;
  
  unsigned int hash;
  
  K key;
  
  V value;
};


template <class K, class V, class U>
class TValHashMapT
{
public:
  
  TValHashMapT ();
  
  inline TValHashMapT (const TValHashMapT<K,V,U> &map) { Copy (map); }
  
  ~TValHashMapT ();
  
  void Apply (void (*fn)(const K *, V *, void *), void *d);
  
  void Clear ();
  
  inline bool Contains (const K& k) { return Find (k); }
  
  inline int Entries () { return myNumEntries; }

  bool FindValue (const K& k, V& v);
  
  bool Insert (const K& k, const V& v);
  
  bool Remove (const K& k);
  
  inline void Shrink (bool flag) { myIsShrinkEnabled = flag; }
  
  V& operator[](const K& k);
  
  TValHashMapT<K,V,U>& operator=(const TValHashMapT<K,V,U> &map);
  
private:

  void Copy (const TValHashMapT<K,V,U>& map);
  
  V* Find (const K& k);
  
  void Grow ();
  
  void ReHash (int new_num_buckets);

  void Shrink ();
  
  
  TValHashMapEntryT<K,V> **myBuckets;
  
  int myNumBuckets;
  
  int myBucketMask;
  
  int myShrinkSize;
  
  int myGrowSize;
  
  int myNumEntries;
  
  bool myIsShrinkEnabled;
  
  static const int BUCKET_MULTIPLIER;
  
  static const int NUM_BUCKETS;
};


template <class K, class V, class U>
const int TValHashMapT<K,V,U>::BUCKET_MULTIPLIER = 3;

template <class K, class V, class U>
const int TValHashMapT<K,V,U>::NUM_BUCKETS = 4;


template <class K, class V, class U>
TValHashMapT<K,V,U>::TValHashMapT ()
  : myNumBuckets (NUM_BUCKETS),
    myBucketMask (NUM_BUCKETS - 1),
    myGrowSize (NUM_BUCKETS * BUCKET_MULTIPLIER),
    myNumEntries (0),
    myIsShrinkEnabled (true)
{
  myBuckets = (TValHashMapEntryT<K,V> **)
    calloc (myNumBuckets, sizeof (myBuckets));
  
  if (! myBuckets)
    throw TMemoryException ();
}


template <class K, class V, class U>
TValHashMapT<K,V,U>::~TValHashMapT ()
{
  myIsShrinkEnabled = false;
  Clear ();
  free (myBuckets);
}


template <class K, class V, class U>
void TValHashMapT<K,V,U>::Apply (void (*fn)(const K *, V *, void *), void *d)
{
  TValHashMapEntryT<K,V> *entry;
  
  for (int i = 0; i < myNumBuckets; i++)
    {
      entry = myBuckets[i];
      while (entry)
        {
          fn (&entry->key, &entry->value, d);
          entry = entry->next;
        }
    }
}


template <class K, class V, class U>
void TValHashMapT<K,V,U>::Clear ()
{
  TValHashMapEntryT<K,V> *entry, *tmp_entry;
  
  if (myNumEntries)
    {
      for (int i = 0; i < myNumBuckets; i++)
        {
          entry = myBuckets[i];
          while (entry)
            {
              tmp_entry = entry;
              entry = entry->next;
              delete tmp_entry;
            }
          
          myBuckets[i] = 0;
        }
      
      myNumEntries = 0;
    }
  
  if (myIsShrinkEnabled)
    {
      myNumBuckets = NUM_BUCKETS;
      myBucketMask = NUM_BUCKETS - 1;
      myGrowSize = NUM_BUCKETS * BUCKET_MULTIPLIER;
      
      myBuckets = (TValHashMapEntryT<K,V> **)
        realloc (myBuckets, myNumBuckets * sizeof (myBuckets));
    }
}


template <class K, class V, class U>
bool TValHashMapT<K,V,U>::FindValue (const K& k, V& v)
{
  V *value = Find (k);
  if (value)
    {
      v = *value;
      return true;
    }
  
  return false;
}


template <class K, class V, class U>
bool TValHashMapT<K,V,U>::Insert (const K& k, const V& v)
{
  TValHashMapEntryT<K,V> *entry, *old_entry;
  unsigned int hash = U::Hash (k);
  int index = hash & myBucketMask;
  
  entry = old_entry = myBuckets[index];
  while (entry)
    {
      if (entry->hash == hash &&
          U::Equal (k, entry->key))
        return false;
      
      entry = entry->next;
    }
  
  entry = new TValHashMapEntryT<K,V> (k, v);
  myBuckets[index] = entry;
  entry->next = old_entry;
  entry->hash = hash;
  
  myNumEntries++;
  if (myNumEntries >= myGrowSize)
    Grow ();
  
  return true;
}


template <class K, class V, class U>
bool TValHashMapT<K,V,U>::Remove (const K& k)
{
  TValHashMapEntryT<K,V> *entry, *prev = 0;
  unsigned int hash = U::Hash (k);
  int index = hash & myBucketMask;
  
  entry = myBuckets[index];
  while (entry)
    {
      if (entry->hash == hash &&
          U::Equal (k, entry->key))
        {
          if (entry == myBuckets[index])
            myBuckets[index] = entry->next;
          else
            prev->next = entry->next;
          
          delete (entry);
          myNumEntries--;
          if (myIsShrinkEnabled && myNumBuckets > NUM_BUCKETS &&
              myNumEntries <= myShrinkSize)
            Shrink ();
          
          return true;
        }
      
      prev = entry;
      entry = entry->next;
    }
  
  return false;
}


template <class K, class V, class U>
V& TValHashMapT<K,V,U>::operator[](const K& k)
{
  V *v = Find (k);
  
  if (v)
    return *v;
  else
    {
      V some_value;
      Insert (k, some_value);
      return *(Find (k));
    }
}


template <class K, class V, class U>
TValHashMapT<K,V,U>&
TValHashMapT<K,V,U>::operator=(const TValHashMapT<K,V,U> &map)
{
  /* Only copy if different objects. */
  if (&map != this)
    {
      bool shrink_enabled = myIsShrinkEnabled;
      
      myIsShrinkEnabled = false;
      Clear ();
      free (myBuckets);
      Copy (map);
      myIsShrinkEnabled = shrink_enabled;
    }
  
  return *this;
}


template <class K, class V, class U>
void TValHashMapT<K,V,U>::Copy (const TValHashMapT<K,V,U>& map)
{
  TValHashMapEntryT<K,V> *orig_entry, *new_entry, *old_entry;
  
  myNumBuckets = map.myNumBuckets;
  myBucketMask = map.myBucketMask;
  myShrinkSize = map.myShrinkSize;
  myGrowSize = map.myGrowSize;
  myNumEntries = map.myNumEntries;
  myIsShrinkEnabled = map.myIsShrinkEnabled;
  
  myBuckets = (TValHashMapEntryT<K,V> **)
    calloc (myNumBuckets, sizeof (myBuckets));
  
  if (! myBuckets)
    throw TMemoryException ();
  
  for (int i = 0; i < myNumBuckets; i++)
    {
      orig_entry = map.myBuckets[i];
      while (orig_entry)
        {
          old_entry = myBuckets[i];
          new_entry = new TValHashMapEntryT<K,V> (orig_entry->key,
                                                  orig_entry->value);
          new_entry->next = old_entry;
          new_entry->hash = orig_entry->hash;
          myBuckets[i] = new_entry;
          orig_entry = orig_entry->next;
        }
    }
}


template <class K, class V, class U>
V* TValHashMapT<K,V,U>::Find (const K& k)
{
  TValHashMapEntryT<K,V> *entry;
  unsigned int hash = U::Hash (k);
  
  entry = myBuckets[hash & myBucketMask];
  while (entry)
    {
      if (entry->hash == hash &&
          U::Equal (k, entry->key))
        return &entry->value;
      
      entry = entry->next;
    }
  
  return 0;
}


template <class K, class V, class U>
void TValHashMapT<K,V,U>::Grow ()
{
  ReHash (myNumBuckets << 2);
  myShrinkSize = (myNumBuckets * BUCKET_MULTIPLIER) >> 4;
  myGrowSize <<= 2;
}


template <class K, class V, class U>
void TValHashMapT<K,V,U>::ReHash (int new_num_buckets)
{
  TValHashMapEntryT<K,V> **orig_buckets = myBuckets;
  TValHashMapEntryT<K,V> *entry, *old_entry, *tmp_entry;
  int old_num_buckets = myNumBuckets, index;
  
  myBuckets = (TValHashMapEntryT<K,V> **)
    calloc (new_num_buckets, sizeof (myBuckets));
  
  if (! myBuckets)
    throw TMemoryException ();
  
  myNumBuckets = new_num_buckets;
  myBucketMask = new_num_buckets - 1;
  
  for (int i = 0; i < old_num_buckets; i++)
    {
      entry = orig_buckets[i];
      while (entry)
        {
          tmp_entry = entry;
          entry = entry->next;
          index = tmp_entry->hash & myBucketMask;
          old_entry = myBuckets[index];
          myBuckets[index] = tmp_entry;
          tmp_entry->next = old_entry;    
        }
    }
  
  free (orig_buckets);
}


template <class K, class V, class U>
void TValHashMapT<K,V,U>::Shrink ()
{
  ReHash (myNumBuckets >> 2);
  myShrinkSize >>= 2;
  myGrowSize >>= 2;
}

#endif // _T_VAL_HASH_MAP_T_HH

---