prop-src/hashtab.h

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //  A very simple hash table class.
   3 ///////////////////////////////////////////////////////////////////////////////
   4 #ifndef hash_table_h
   5 #define hash_table_h
   6
   7 #include <AD/generic/generic.h>
   8
   9 class HashTable {
  10    HashTable(const HashTable&); // no copy constructor
  11    void operator = (const HashTable&); // no assignment
  12 public:
  13
  14    ////////////////////////////////////////////////////////////////////////////
  15    //  Type definitions.
  16    ////////////////////////////////////////////////////////////////////////////
  17    typedef const void * Key;
  18    typedef const void * Value;
  19    typedef unsigned int (*HashFunction)(Key);
  20    typedef Bool         (*Equality)(Key, Key);
  21    struct Entry { Key k; Value v; long hash_val; };
  22
  23 protected:
  24
  25    ////////////////////////////////////////////////////////////////////////////
  26    //  Internals.
  27    ////////////////////////////////////////////////////////////////////////////
  28    HashFunction hash;         // hash function
  29    Equality     eq;           // equality function
  30    int          count;        // number of elements
  31    int          growth_limit; // expand when this limit is reached
  32    int          capacity;     // capacity of the table
  33    Entry *      table;        // the hash table itself.
  34
  35 public:
  36
  37    ////////////////////////////////////////////////////////////////////////////
  38    //  Constructor and destructor
  39    ////////////////////////////////////////////////////////////////////////////
  40    HashTable(HashFunction, Equality, int = 32);
  41   ~HashTable();
  42
  43    ////////////////////////////////////////////////////////////////////////////
  44    //  Operations.
  45    ////////////////////////////////////////////////////////////////////////////
  46    inline int    size()                 const { return count; }
  47    inline Bool   is_empty()             const { return count == 0; }
  48    inline Key    key  (const Entry * e) const { return e->k; }
  49    inline Value  value(const Entry * e) const { return e->v; }
  50    inline Value  operator [] (Key k)    const { return lookup(k)->v; }
  51           Bool          contains (Key key) const;
  52           Entry *       lookup   (Key key) const;
  53           void          clear    ();
  54           void          insert   (Key key, Value value);
  55           Entry * first ()        const;
  56           Entry * next  (Entry *) const;
  57           void          grow     (int);
  58 private:
  59           const Entry * private_lookup (unsigned int h, Key key) const;
  60 };
  61
  62 ///////////////////////////////////////////////////////////////////////////////
  63 //  Useful macros
  64 ///////////////////////////////////////////////////////////////////////////////
  65 #define foreach_entry(i,h) \
  66    for (HashTable::Entry * i = (h).first(); i; i = (h).next(i))
  67 #define key_of(T,h,i)   (T)(long)((h).key(i))
  68 #define value_of(T,h,i) (T)(long)((h).value(i))
  69
  70 ///////////////////////////////////////////////////////////////////////////////
  71 //  Some common hashing and equality functions.
  72 ///////////////////////////////////////////////////////////////////////////////
  73 unsigned int string_hash   (HashTable::Key);
  74 Bool         string_equal  (HashTable::Key, HashTable::Key);
  75 unsigned int integer_hash  (HashTable::Key);
  76 Bool         integer_equal (HashTable::Key, HashTable::Key);
  77
  78 #endif