---

HashTable.h

Go to the documentation of this file.

// $Header: /nfs/slac/g/glast/ground/cvs/GaudiKernel/GaudiKernel/HashTable.h,v 1.1.1.1 2001/04/18 18:14:18 tlindner Exp $
#ifndef GAUDIKERNEL_HASHTABLE_H
#define GAUDIKERNEL_HASHTABLE_H

#include <list>
#include <vector>
#include <functional>

template <class T> class HashTableHasher : public std::unary_function<const T&,size_t>  {
public:
  size_t operator()(const T& key)    {
    size_t f = size_t(key)>>4;
    const unsigned char* s = (const unsigned char*)&f;
    return (((((((0^*s++)<<1)^*s++)<<1)^*s++)<<1)^*s++);
  }
};

template < class K, class E, class H=HashTableHasher< K > > 
class HashTable {
public:

  template<class KK, class EE> class TableEntry {
    friend class HashTable<KK,EE,H>;
  private:
    TableEntry* chain;
  public:
    KK       first;
    EE       second;
    TableEntry() : chain(0)  {
    }
    TableEntry(const TableEntry& copy) 
    : chain(copy.chain), first(copy.first), second(copy.second) {
    }
    TableEntry(const KK& k, const EE& e,TableEntry* c)
    : chain(c), first(k), second(e) {
    }
    bool operator==(const TableEntry& copy)     const   {
      return copy.first == first;
    }
    TableEntry& operator=(const TableEntry& copy)   {
      first  = copy.first;
      second = copy.second;
      chain  = copy.chain;
      return *this;
    }
  };
  typedef HashTable<K,E,H>               table_type;
  typedef H                              hash_type;
  typedef TableEntry<K, E>               value_type;
  typedef std::list< value_type >        container_type;
  typedef container_type::iterator       iterator;
  typedef container_type::const_iterator const_iterator;
protected:
  int     m_size;
  int     m_incr;
  std::vector<value_type*> m_vec;
  container_type           m_con;
  hash_type                m_hash;
protected:
  void rehash(int new_size)   {
    m_vec.clear();
    m_vec.insert(m_vec.begin(), new_size, (value_type*)0);
    for ( container_type::iterator i = m_con.begin(); i != m_con.end(); i++ )    {
      size_t h   = m_hash((*i).first)%m_vec.size();
      (*i).chain = m_vec[h];
      m_vec[h]   = &(*i);
    }
  }
  value_type* find(size_t idx, const K& key )    {
    for (value_type* e = m_vec[idx]; e != 0; e = e->chain)    {
      if ( e->first == key )  {
        return e;
      }
    }
    return 0;
  }
  void remove(value_type* e)  {
    m_con.remove(*e);
    m_size--;
  }
public:
  HashTable(int length = 16, int incr = 2) : m_size(0), m_incr(incr)  {
    reserve(length);
  }
  virtual ~HashTable()    {
    clear();
  }
  iterator begin()    {
    return m_con.begin();
  }
  const_iterator begin()   const  {
    return m_con.begin();
  }
  iterator end()    {
    return m_con.end();
  }
  const_iterator end()   const  {
    return m_con.end();
  }
  void clear()      {
    m_con.erase(m_con.begin(), m_con.end());
    m_vec.erase(m_vec.begin(), m_vec.end());
  }
  long size()   const   {
    return m_size;
  }
  void reserve(int len)   {
    if ( int(m_vec.size()) < len ) rehash(len);
  }
  bool insert(const K& first, const E& second)     {
    size_t h = m_hash(first)%m_vec.size();
    value_type* val = find(h, first);
    if ( !val )    {
      if ( ++m_size == int(m_vec.size()) )   {
        rehash(m_vec.size()*m_incr);
        h = m_hash(first)%m_vec.size();
      }
      m_con.insert(m_con.end(), value_type(first, second, m_vec[h]));
      m_vec[h] = &m_con.back();
      return true;
    }
    return false;
  }
  value_type* find(const K& first)    {
    return find(m_hash(first)%m_vec.size(), first);
  }
  const value_type* find(const K& first) const    {
    table_type* thisPtr = const_cast<table_type*>(this);
    return thisPtr->find(m_hash(first)%m_vec.size(), first);
  }
  void remove(const K& first)    {
    size_t h = m_hash(first)%m_vec.size();
    if (0 != m_vec[h])     {
      value_type *prev, *e = m_vec[h];
      if ( e->first == first )   {
        m_vec[h] = e->chain;
        remove(e);
        return;
      } 
      do    {
        prev = e;
        e = e->chain;
      } while ( 0 != e && e->first != first);
      if ( 0 != e )  {
        prev->chain = e->chain;
        remove(e);
      }
    }
  }
};

#endif    // GAUDI_KERNEL_HASHTABLE_H

---