source: Sophya/trunk/SophyaLib/BaseTools/hashtable.h@ 1670

// This may look like C code, but it is really -*- C++ -*-

// This is a hash table. Some implementations of the STL have one, like the
// Modena Standard Library.

#ifndef HASHTABLE_H_SEEN
#define HASHTABLE_H_SEEN

#include "machdefs.h"
#include "pexceptions.h"

namespace SOPHYA {

template <class T, class K>
struct HashtableEntry {
  uint_4         hash;
  K              key;
  T              value;
  HashtableEntry<T,K> *next;
};


template <class T, class K>
class Hashtable {
public:
  typedef uint_4 (*HashFunction)(K const& key);

  Hashtable(uint_4 initialCapacity, float loadFactor) {
    Init(initialCapacity,loadFactor);
  }
  
  Hashtable(int initialCapacity) {
    Init(initialCapacity, 0.75);
  }
  
  Hashtable() {
    Init(101, 0.75);
  }

  ~Hashtable() {
    for (int i = count ; i-- > 0 ;) {
      for (HashtableEntry<T,K>* e = table[i] ; e != NULL ; ) {
        HashtableEntry<T,K>* ee = e->next;
        delete e;
        e = ee;
      }
    }
    delete[] table;
  }

  void setHash(HashFunction f) {
    hf = f;
  }

  uint_4 size() {
    return count;
  }

  bool contains(T const& value) {
    for (int i = count ; i-- > 0 ;) {
      for (HashtableEntry<T,K>* e = table[i] ; e != NULL ; e = e->next) {
        if (e->value == value) {
          return true;
        }
      }
    }
    return false;
  }
  
  bool containsKey(K const& key) {
    uint_4 hash = hf(key);
    uint_4 index = (hash & 0x7FFFFFFF) % length;
    for (HashtableEntry<T,K>* e = table[index] ; e != NULL ; e = e->next) {
      if ((e->hash == hash) && e->key == key) {
        return true;
      }
    }
    return false;
  }
  
  T const& get(K const& key) {
    uint_4 hash = hf(key);
    uint_4 index = (hash & 0x7FFFFFFF) % length;
    for (HashtableEntry<T,K>* e = table[index] ; e != NULL ; e = e->next) {
      if ((e->hash == hash) && e->key == key) {
        return e->value;
      }
    }
    throw(NotFoundExc("Hashtable::get"));
  }
  
  
  void put(K const& key, T const& value) {
    // Makes sure the key is not already in the hashtable.
    uint_4 hash = hf(key);
    uint_4 index = (hash & 0x7FFFFFFF) % length;
    for (HashtableEntry<T,K>* e = table[index] ; e != NULL ; e = e->next) {
      if ((e->hash == hash) && e-> key == key) {
        //T const& old = e.value;
        e->value = value;
        //return old;
      }
    }
    
    if (count >= threshold) {
      // Rehash the table if the threshold is exceeded
      rehash();
      return;// put(key, value);
    } 

    // Creates the new entry.
    HashtableEntry<T,K>* e = new HashtableEntry<T,K>;
    e->hash = hash;
    e->key = key;
    e->value = value;
    e->next = table[index];
    table[index] = e;
    count++;
    //return null;
  }
  
  
  void remove(K const& key) {
    uint_4 hash = hf(key);
    uint_4 index = (hash & 0x7FFFFFFF) % tab.length;
    for (HashtableEntry<T,K>* e = table[index], prev = null ; e != null ; prev = e, e = e->next) {
      if ((e>hash == hash) && e>key == key) {
        if (prev != NULL) {
          prev->next = e->next;
        } else {
          table[index] = e->next;
        }
        count--;
        //return e.value;
      }
    }
    //return null;
  }
  
private:
  
  void Init(uint_4 initialCapacity, float loadFactor) {
    if ((initialCapacity == 0) || (loadFactor <= 0.0)) {
      throw ParmError("Hashtable::Hashtable");
    }
    this->loadFactor = loadFactor;
    this->length = initialCapacity;
    this->count = 0;
    table = new (HashtableEntry<T,K>*[initialCapacity]);
    for (int i=0; i<length; i++) table[i] = NULL;
    threshold = (uint_4)(initialCapacity * loadFactor);
    hf = defaultHash;
  }

  static uint_4 defaultHash(K const& key) {
    if (sizeof(K) <= sizeof(void*))
      return (uint_4)(uint_8)(key);
    else
      return (uint_4)(uint_8)(&key);
  }

  void rehash() {
    uint_4 oldCapacity = length;
    HashtableEntry<T,K>** oldTable = table;

    uint_4 newCapacity = oldCapacity * 2 + 1;
    HashtableEntry<T,K>** newTable = new (HashtableEntry<T,K>*[newCapacity]);

    threshold = (int)(newCapacity * loadFactor);
    table = newTable;
    length = newCapacity;

    for (int i = oldCapacity ; i-- > 0 ;) {
      for (HashtableEntry<T,K>* old = oldTable[i] ; old != NULL ; ) {
        HashtableEntry<T,K>* e = old;
        old = old->next;
        
        int index = (e->hash & 0x7FFFFFFF) % newCapacity;
        e->next = newTable[index];
        newTable[index] = e;
      }
    }
    delete[] oldTable;
  }
  
  HashtableEntry<T,K>  **table;
  uint_4         length;
  uint_4         count;
  uint_4         threshold;
  float          loadFactor;
  HashFunction   hf;
};
}

#endif