hash.h

Go to the documentation of this file.

/****************************************************************************/
/*                                                                          */
/*  Copyright (c) 1994-2002                                                 */
/*  Jeremy Levitt                                                           */
/*                                                                          */
/****************************************************************************/
#ifndef _hash_h_
#define _hash_h_

#include <iostream>

#ifndef NULL
#define NULL 0
#endif

//#include <ext/stl_hash_fun.h>

namespace CVCL {
using std::pair;

template <class _Key> 
        static size_t hash(_Key e) { return 1;}
template <class _Key> 
        static size_t equal_to(_Key x, _Key y) { return x==y;}
        //static size_t mfun(Expr x, Expr y) { return x==y;}

const int HASH_TABLE_SIZE = 1024;
const int HASH_TABLE_GROW_THRESHOLD = 1;
const int HASH_TABLE_GROW_FACTOR = 2;
typedef void *void_pointer;

template <class _Key, class _Data> class Hash_Table;
template <class _Key, class _Data> class Hash_Entry;
template <class _Key, class _Data> class Hash_Ptr;

//iterator
template <class _Key, class _Data>
struct _Hashtable_iterator;

template <class _Key, class _Data>
struct _Hashtable_const_iterator;

template <class _Key, class _Data>
struct _Hashtable_iterator {
  typedef Hash_Table<_Key,_Data>
          _Hashtable;
  typedef _Hashtable_iterator<_Key, _Data>
          iterator;
  typedef _Hashtable_const_iterator<_Key, _Data>
          const_iterator;
  typedef Hash_Entry<_Key, _Data> _Node;

  //typedef forward_iterator_tag iterator_category;
  //typedef _Val value_type;
  //typedef ptrdiff_t difference_type;
  //typedef size_t size_type;
  typedef pair<const _Key,_Data>& reference;
  typedef pair<const _Key,_Data>* pointer;

  _Node* _M_cur;
  _Hashtable* _M_ht;

  _Hashtable_iterator(_Node* __n, _Hashtable* __tab) 
    : _M_cur(__n), _M_ht(__tab) {}
  _Hashtable_iterator() {}
  reference operator*() const { return _M_cur->Val(); }
  pointer operator->() const { return &(operator*()); }
  iterator& operator++(){
            //const _Node* _old = _M_cur;
                _M_cur = _M_cur->Next();
                //if (!_M_cur)
                //      _M_cur = _old;
                return *this;
  }
  //iterator operator++(int);
  bool operator==(const iterator& __it) const
    { return _M_cur == __it._M_cur; }
  bool operator!=(const iterator& __it) const
    { return _M_cur != __it._M_cur; }
};


template <class _Key, class _Data>
struct _Hashtable_const_iterator {
  typedef Hash_Table<_Key,_Data>
          _Hashtable;
  typedef _Hashtable_iterator<_Key,_Data> iterator;
  typedef _Hashtable_const_iterator<_Key,_Data>
          const_iterator;
  typedef Hash_Entry<_Key,_Data> _Node;

  //typedef forward_iterator_tag iterator_category;
  //typedef _Val value_type;
  //typedef ptrdiff_t difference_type;
  //typedef size_t size_type;
  typedef const pair<const _Key,_Data>& reference;
  typedef const pair<const _Key,_Data>* pointer;

  const _Node* _M_cur;
  const _Hashtable* _M_ht;

  _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
    : _M_cur(__n), _M_ht(__tab) {
                //cout << "Hashtable_const_iterator. " << endl; 
        }
  _Hashtable_const_iterator() {}
  _Hashtable_const_iterator(const iterator& __it) 
    : _M_cur(__it._M_cur), _M_ht(__it._M_ht) {}
  reference operator*() const {
          //cout << "hashtable-const-iterator: * " << endl;
        pair<_Key,_Data> tmp(_M_cur->Val());
        //return _M_cur->Val(); 
        return tmp;
        }
  pointer operator->() const { //cout << "hashtable-const-iterator: -> " << endl;
          return &(operator*()); }
  const_iterator& operator++(){
            //const _Node* _old = _M_cur;
          //cout << "hashtable-const-iterator: ++ " << endl;
                _M_cur = _M_cur->Next();
                //if (!_M_cur)
                //      _M_cur = _old;
                return *this;
  }
  //const_iterator operator++(int);
  bool operator==(const const_iterator& __it) const 
    { //cout << "hashtable-const-iterator: == " << endl;
          return _M_cur == __it._M_cur; }
  bool operator!=(const const_iterator& __it) const 
    { //cout << "hashtable-const-iterator: != " << endl;
          return _M_cur != __it._M_cur; }
};

//end iterator

/****************************************************************************/
/*  class Hash_Entry                                                        */
/****************************************************************************/
template <class _Key, class _Data>
class Hash_Entry {
        //friend class ExprMap;
private:
  _Key _key;
  _Data _data;
  pair<const _Key,_Data> _val;
  Hash_Entry *_next;
  //Hash_Entry(const _Data &data):
  //_Key(0), _data(data), _next(NULL){}
  Hash_Entry(const _Key &key, const _Data &data) : 
  _key(key), _data(data), _val(make_pair(key,data)), _next(NULL) {}
  Hash_Entry(const Hash_Entry &rhs) : 
  _key(rhs._key), _data(rhs._data), _val(make_pair(rhs._key,rhs._data)), _next(NULL) {}
  ~Hash_Entry() {}
  friend class Hash_Table<_Key, _Data>;
  
public:
  Hash_Entry* Next() const { return _next; } 
  _Key Key() const { return _key; }
  _Data& Data() { return _data; }
  pair<const _Key,_Data> Val() const {
          //cout << "hashtable-hashentry-val(): key " << _key << " , data: " << _data << endl;
                pair<const _Key,_Data> val1 = make_pair(_key,_data);
          //cout << "key: " << val1.first << ", data: " << val1.second << endl;
          return val1;}
  bool operator==(const Hash_Entry he){
          if( (_key == he.Key()) && (_data == he.Data()))
                  return true;
          else
                  return false;
  }
  bool operator!=(const Hash_Entry he){
          if( (_key == he.Key()) && (_data == he.Data()))
                  return false;
          else
                  return true;
  }

  //IF_DEBUG(
    void Print();
  //)
};


/****************************************************************************/
/*  class Hash_Table                                                        */
/****************************************************************************/
template <class _Key, class _Data>
class Hash_Table {
        //friend class ExprMap;
private:
  Hash_Entry<_Key, _Data> **_hashTbl;
  //int (*_hashFunc)(const _Key);               // must return a positive int
  size_t (*_hashFunc)(const _Key);
  //int (*_matchFunc)(const _Key, const _Key);  // return (k1==k2) ? 1 : 0
  size_t (*_matchFunc)(const _Key, const _Key);
  int _size;
  int _growThreshold;
  int _growFactor;
  int _numEntries;
  Hash_Entry<_Key, _Data>** Find_Hash_Entry(const _Key&) const;
  void Copy(const Hash_Table &rhs);
  void Resize(int size);
  void Destroy();
  friend class Hash_Ptr<_Key, _Data>;
  //friend class Expr;

public:
        
        //Hash_Table(): _hashFunc(hash<_Key>), _matchFunc(equal_to<_Key>),
                //_size(HASH_TABLE_SIZE),
                //_growThreshold(HASH_TABLE_GROW_THRESHOLD), 
        //      _growFactor(HASH_TABLE_GROW_FACTOR), _numEntries(0)
        //{cout << "hashtable-hashtable():" << endl;}
        
  //Hash_Table(int (*hashFunction)(const _Key),
        //     int (*matchFunc)(const _Key, const _Key),
        Hash_Table(size_t (*hashFunction)(const _Key),
           size_t (*matchFunc)(const _Key, const _Key),
       int size = HASH_TABLE_SIZE, int threshold = HASH_TABLE_GROW_THRESHOLD,
       int factor = HASH_TABLE_GROW_FACTOR);
  Hash_Table(const Hash_Table &hash) { Copy(hash); }
  ~Hash_Table() { Destroy(); }
  int Insert(_Key key, _Data data);
  int Delete(_Key key);
  void clear();
  Hash_Table& operator= (const Hash_Table &rhs);
  _Data* Fetch(_Key key);
  _Data& operator[] (_Key key);
  //int Size() const { return _size; }
  //int NumEntries() const { return _numEntries; } //real size()
  size_t size() const { return _numEntries; }
  bool empty() const { return size() == 0; }
        void erase(_Key key);
        int count(_Key key) const;
        typedef _Hashtable_iterator<_Key, _Data>
          iterator;
        typedef _Hashtable_const_iterator<_Key, _Data>
          const_iterator;
        friend struct
                _Hashtable_iterator<_Key, _Data>;
        friend struct
                _Hashtable_const_iterator<_Key, _Data>;
        

  //IF_DEBUG(
    void Print();
  //)
 
        const_iterator begin() const{ 
      if (size()>0)
        return const_iterator(_hashTbl[0], this);
          else
                return end();
        }

        const_iterator end() const{ return const_iterator(0, this); }
        const_iterator find(const _Key& key) const{
                //cout << "hashtable-find e: " << key << endl;
                return const_iterator(*Find_Hash_Entry(key), this);
        }
        template<class InputIterator>
                void insert(InputIterator l, InputIterator r);
};


/****************************************************************************/
/*  class Hash_Ptr                                                          */
/****************************************************************************/
template <class _Key, class _Data>
class Hash_Ptr {
        //friend class ExprMap;
private:
  Hash_Table<_Key, _Data> *_hash;
  int _index;
  Hash_Entry<_Key, _Data> *_hashEntry;
  void Set_Next_Hash_Entry();
  
public:
  Hash_Ptr() : _hash(0), _index(0), _hashEntry(0) {}
  Hash_Ptr(Hash_Table<_Key, _Data> *hash) : 
  _hash(hash), _index(0), _hashEntry(hash->_hashTbl[0]) 
    { if (_hashEntry == NULL) Set_Next_Hash_Entry(); }
  Hash_Ptr(const Hash_Table<_Key, _Data> *hash) :
    _hash((Hash_Table<_Key, _Data>*)hash), _index(0),
    _hashEntry(hash->_hashTbl[0])
    { if (_hashEntry == NULL) Set_Next_Hash_Entry(); }
  Hash_Entry<_Key, _Data>* operator-> () { return _hashEntry; }
  Hash_Entry<_Key, _Data>& operator* () 
    { //ASSERT(_hashEntry);  
        return *_hashEntry; }
  operator void_pointer() const { return void_pointer(_hashEntry); }
  int Null() const { return _hashEntry == NULL; }
  void operator++ () { Set_Next_Hash_Entry(); }
  void Reset(Hash_Table<_Key, _Data> *hash)
    { *this = Hash_Ptr(hash); }
};   


/****************************************************************************/
/*    Hash_Table::Hash_Table()                                              */
/****************************************************************************/
template <class _Key, class _Data>
Hash_Table<_Key, _Data>::Hash_Table
//(int (*hashFunc)(const _Key), int (*matchFunc)(const _Key, const _Key),
(size_t (*hashFunc)(const _Key), size_t (*matchFunc)(const _Key, const _Key),
 int size, int threshold, int factor)
: _hashFunc(hashFunc), _matchFunc(matchFunc), _size(size),
  _growThreshold(threshold), _growFactor(factor), _numEntries(0)
{
  //ASSERT(_growFactor >= HASH_TABLE_GROW_FACTOR);
  //ASSERT(_growThreshold >= HASH_TABLE_GROW_THRESHOLD);

        //cout << "hashtable-hashtable(hfun, mfun):" << endl;
  _hashTbl = new Hash_Entry<_Key, _Data> *[_size];
  for(int i=0; i<_size; i++)
    _hashTbl[i] = NULL;
}


/****************************************************************************/
/*    Hash_Table::Destroy()                                                 */
/****************************************************************************/
template <class _Key, class _Data>
void Hash_Table<_Key, _Data>::Destroy()
{
  for (int i=0; i<_size; i++) {
    Hash_Entry<_Key, _Data> *tmp = _hashTbl[i];

    while(tmp != NULL) {
      Hash_Entry<_Key, _Data> *next = tmp->_next;
      delete tmp;
      tmp = next;
    }
  }

  delete [] _hashTbl;
}


/****************************************************************************/
/*    Hash_Table::Copy()                                                    */
/****************************************************************************/
template <class _Key, class _Data>
void Hash_Table<_Key, _Data>::Copy(const Hash_Table<_Key, _Data> &rhs)
{
  _hashFunc = rhs._hashFunc;
  _matchFunc = rhs._matchFunc;
  _numEntries = rhs._numEntries;
  _size = rhs._size;
  _growThreshold = rhs._growThreshold;
  _growFactor = rhs._growFactor;
  _hashTbl = new Hash_Entry<_Key, _Data> *[rhs._size];

  for (int i=0; i<rhs._size; i++) {
    Hash_Entry<_Key, _Data> *tmp = rhs._hashTbl[i];
    Hash_Entry<_Key, _Data> **copy = &(_hashTbl[i] = NULL);

    while(tmp != NULL) {
      *copy = new Hash_Entry<_Key, _Data>(*tmp);
      copy = &(*copy)->_next;
      tmp = tmp->_next;
    }
  }
}


/****************************************************************************/
/*    Hash_Table::Resize()                                                  */
/****************************************************************************/
template <class _Key, class _Data>
void Hash_Table<_Key, _Data>::Resize(int size)
{
  Hash_Table<_Key, _Data> tmp(_hashFunc, _matchFunc, size);

  Hash_Ptr<_Key, _Data> ptr(this);
  for (;!ptr.Null(); ++ptr) {
    _Key key = ptr->Key();
    tmp.Insert(key, ptr->Data());
  }

  Destroy();
  Copy(tmp);
}


/****************************************************************************/
/*   Hash_Table::operator=                                                  */
/****************************************************************************/
template <class _Key, class _Data>
Hash_Table<_Key, _Data>& Hash_Table<_Key, _Data>::operator=
(const Hash_Table<_Key, _Data> &rhs)
{
  if (this != &rhs) {
    Destroy();
    Copy(rhs);
  }

  return *this;
}


/****************************************************************************/
/*    Hash_Table::Find_Hash_Entry()                                         */
/*                                                                          */
/*    Return a pointer to the element if found, or a pointer to where       */
/*    the element should be if not found.                                   */
/****************************************************************************/
template <class _Key, class _Data>
Hash_Entry<_Key, _Data>** 
Hash_Table<_Key, _Data>::Find_Hash_Entry(const _Key& key) const
{
  int index = (*_hashFunc)(key) % _size;
  //cout << "hashtable-findHashEntry, index: " << index << endl;

  //ASSERT(index >=0);
  Hash_Entry<_Key, _Data>** link = &_hashTbl[index];  
  while (*link != NULL && !_matchFunc((*link)->_key, key))
    link = &((*link)->_next);
  return link;
}


/****************************************************************************/
/*    Hash_Table::Insert()                                                  */
/*                                                                          */
/*    Return 0 if the element was successfully inserted                     */
/*    Return 1 if insertion fails becuase an entry with the same key        */
/*    is already present                                                    */
/****************************************************************************/
template <class _Key, class _Data>
int Hash_Table<_Key, _Data>::Insert(_Key key, _Data data)
{
  if (_numEntries>_size*_growThreshold)
    Resize(_size*_growFactor);

  Hash_Entry<_Key, _Data>* hash_entry = 
    new Hash_Entry<_Key, _Data>(key, data);
  Hash_Entry<_Key, _Data>** link = Find_Hash_Entry(key);
  
  if (*link != NULL) {
    delete hash_entry;
    return 1;
  }
  
  _numEntries++;
  *link = hash_entry;
  return 0;
}

template<class InputIterator>
void insert(InputIterator l, InputIterator r) {
        for(; l!=r; ++l) {
                Insert((*l).first, (*l).second);
        }       
}

/****************************************************************************/
/*    Hash_Table::Delete()                                                  */
/*                                                                          */
/*    Return 0 if the element was successfully deleted and 1                */
/*    if the deletion failed becuase the entry could not be found.          */
/****************************************************************************/
template <class _Key, class _Data>
int Hash_Table<_Key, _Data>::Delete(_Key key)
{
  Hash_Entry<_Key, _Data>** link = Find_Hash_Entry(key);
  Hash_Entry<_Key, _Data>* tmp;
  
  if (*link == NULL)
    return 1;
  
  _numEntries--;
  tmp = (*link);
  *link = (*link)->_next;
  delete tmp;
  return 0;
}

template <class _Key, class _Data>
void Hash_Table<_Key, _Data>::erase(_Key key){
  Hash_Entry<_Key, _Data>** link = Find_Hash_Entry(key);
  Hash_Entry<_Key, _Data>* tmp;
  
  if (*link == NULL)
    return;
  
  _numEntries--;
  tmp = (*link);
  *link = (*link)->_next;
  delete tmp;
  return;
}

/****************************************************************************/
/*    Hash_Table::clear()                                                   */
/*                                                                          */
/*    Delete all elements in the hash table.                                */
/****************************************************************************/
template <class _Key, class _Data>
void Hash_Table<_Key, _Data>::clear()
{
  for (int i=0; i<_size; i++) {
    Hash_Entry<_Key, _Data> *tmp = _hashTbl[i];
    _hashTbl[i] = NULL;

    while(tmp != NULL) {
      Hash_Entry<_Key, _Data> *next = tmp->_next;
      delete tmp;
      tmp = next;
    }
  }
  _numEntries = 0;
}


/****************************************************************************/
/*    Hash_Table::Fetch()                                                   */
/*                                                                          */
/*    Return a pointer to the element if it was found, otherwise return     */
/*    a NULL pointer.                                                       */
/****************************************************************************/
template <class _Key, class _Data>
_Data* Hash_Table<_Key, _Data>::Fetch(_Key key)
{
  Hash_Entry<_Key, _Data>** link = Find_Hash_Entry(key);
  return (*link) ? &(*link)->Data() : (_Data *)NULL;
}

template <class _Key, class _Data>
int Hash_Table<_Key, _Data>::count(_Key key) const{
  Hash_Entry<_Key, _Data>** link = Find_Hash_Entry(key);
  return (*link) ? 1 : 0;
}

/****************************************************************************/
/*    Hash_Table::operator[]                                                */
/****************************************************************************/
/*
template <class _Key, class _Data>
_Data& Hash_Table<_Key, _Data>::operator[] (_Key key)
{
  _Data* result = Fetch(key);
  //ASSERT(result != NULL);
  return *result;
}
*/

template <class _Key, class _Data>
_Data& Hash_Table<_Key, _Data>::operator[](_Key key)
{
 _Data* result = Fetch(key);
 if (result) return *result;
 else {
   _Data data;

   if (_numEntries>_size*_growThreshold)
     Resize(_size*_growFactor);

   Hash_Entry<_Key, _Data>* hash_entry = 
     new Hash_Entry<_Key, _Data>(key, data);

   Hash_Entry<_Key, _Data>** link = Find_Hash_Entry(key);
  
   //ASSERT(*link != NULL);

   _numEntries++;
   *link = hash_entry;
   //cout << "hashtable [] 3: link" << *link << endl;

   return (hash_entry->Data());
 }
}

/****************************************************************************/
/*    Hash_Ptr::Set_Next_Hash_Entry()                                       */
/****************************************************************************/
template <class _Key, class _Data>
void Hash_Ptr<_Key, _Data>::Set_Next_Hash_Entry()
{
  if (_hashEntry != NULL && _hashEntry->Next() != NULL) {
    _hashEntry = _hashEntry->Next();
    return;
  }
  
  while (++_index < _hash->_size)
    if (_hash->_hashTbl[_index] != NULL) {
      _hashEntry = _hash->_hashTbl[_index];
      return;
    }
  
  _hashEntry = NULL;
}


template <class _Key, class _Data>
void HashUpdateIntData(Hash_Table<_Key, _Data>& t, _Key key, _Data i)
{
  _Data *tmp = t.Fetch(key);
  if (tmp) *tmp = *tmp + i;
  else t.Insert(key, i);
}


#ifdef DEBUG
/****************************************************************************/
/*    Hash_Entry::operator<<                                                */
/****************************************************************************/
template <class _Key, class _Data>
void Hash_Entry<_Key, _Data>::Print()
{ 
  std::cout << "key: \"" << Key() << "\" data: " << Data() << '\n';
}


/****************************************************************************/
/*    Hash_Table::operator<<                                                */
/****************************************************************************/
template <class _Key, class _Data>
void Hash_Table<_Key, _Data>::Print()
{ 
  for (Hash_Ptr<_Key, _Data> ptr(this); !ptr.Null(); ++ptr) 
    ptr->Print();
}
#endif

} // end of namespace CVCL

#endif /* _hash_h_ */

---