---

TValHashSetT.hh

#ifndef _T_VAL_HASH_SET_T_HH
#define _T_VAL_HASH_SET_T_HH

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


// Template class used to hold one key in a TValHashSetT object.

template <class K>
class TValHashSetEntryT
{
public:
  
  TValHashSetEntryT (const K& k)
    : key (k)
  {
  }
  
  TValHashSetEntryT *next;
  
  unsigned int hash;
  
  K key;
};


template <class K, class U>
class TValHashSetT
{
public:
  
  TValHashSetT ();
  
  TValHashSetT (const TValHashSetT<K,U> &set) { Copy (set); }
  
  ~TValHashSetT ();
  
  void Apply (void (*fn)(const K *, void *), void *d);
  
  void Clear ();
  
  bool Contains (const K& k);
  
  int Entries () { return myNumEntries; }
  
  bool Insert (const K& k);
  
  bool Remove (const K& k);
  
  void Shrink (bool flag) { myIsShrinkEnabled = flag; }
  
  TValHashSetT<K,U>& operator=(const TValHashSetT<K,U> &set);
  
private:
 
  void Copy (const TValHashSetT<K,U>& set);
  
  void Grow ();
  
  void ReHash (int new_num_buckets);

  void Shrink ();
  
  
  TValHashSetEntryT<K> **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 U>
const int TValHashSetT<K,U>::BUCKET_MULTIPLIER = 3;

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


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


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


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


template <class K, class U>
void TValHashSetT<K,U>::Clear ()
{
  TValHashSetEntryT<K> *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 = (TValHashSetEntryT<K> **)
        realloc (myBuckets, myNumBuckets * sizeof (myBuckets));
    }
}


template <class K, class U>
bool TValHashSetT<K,U>::Contains (const K& k)
{
  TValHashSetEntryT<K> *entry;
  unsigned int hash = U::Hash (k);
  
  entry = myBuckets[hash & myBucketMask];
  while (entry)
    {
      if (entry->hash == hash &&
          U::Equal (k, entry->key))
        return true;
      
      entry = entry->next;
    }
  
  return false;
}


template <class K, class U>
bool TValHashSetT<K,U>::Insert (const K& k)
{
  TValHashSetEntryT<K> *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 TValHashSetEntryT<K> (k);
  myBuckets[index] = entry;
  entry->next = old_entry;
  entry->hash = hash;
  
  myNumEntries++;
  if (myNumEntries >= myGrowSize)
    Grow ();
  
  return true;
}


template <class K, class U>
bool TValHashSetT<K,U>::Remove (const K& k)
{
  TValHashSetEntryT<K> *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 U>
TValHashSetT<K,U>& TValHashSetT<K,U>::operator=(const TValHashSetT<K,U> &set)
{
  /* Only copy if different objects. */
  if (&set != this)
    {
      bool shrink_enabled = myIsShrinkEnabled;

      myIsShrinkEnabled = false;
      Clear ();
      free (myBuckets);
      Copy (set);
      myIsShrinkEnabled = shrink_enabled;
    }
  
  return *this;
}


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


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


template <class K, class U>
void TValHashSetT<K,U>::ReHash (int new_num_buckets)
{
  TValHashSetEntryT<K> **orig_buckets = myBuckets;
  TValHashSetEntryT<K> *entry, *old_entry, *tmp_entry;
  int old_num_buckets = myNumBuckets, index;
  
  myBuckets = (TValHashSetEntryT<K> **)
    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 U>
void TValHashSetT<K,U>::Shrink ()
{
  ReHash (myNumBuckets >> 2);
  myShrinkSize >>= 2;
  myGrowSize >>= 2;
}

#endif // _T_VAL_HASH_SET_T_HH

---