include/AD/hash/lhash2.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef linear_probing_hash_table2_h
  26 #define linear_probing_hash_table2_h
  27
  28 ////////////////////////////////////////////////////////////////////////////
  29 //  Class LHashTable2 implements a hash table using a simple
  30 //  linear hashing scheme\cite{Algorithms}.
  31 ////////////////////////////////////////////////////////////////////////////
  32
  33 #include <string.h>
  34 #include <AD/generic/ordering.h>
  35
  36 ////////////////////////////////////////////////////////////////////////////
  37 //  Class |LHashTable2| is parameterized with the class of the
  38 //  key and the class of the value.  Furthermore, the functions
  39 //      unsigned int hash(const K&);          and
  40 //      Bool     equal(const K&, const K&);
  41 //  must be defined by the client that uses this template.
  42 ////////////////////////////////////////////////////////////////////////////
  43 template <class K, class V, class C>
  44    class LHashTable2 {
  45
  46       K *     keys;           // the array of keys
  47       V *     values;         // the array of values
  48       char *  status;         // status of cell
  49       int     table_size;     // size of the array
  50       int     elem_count;     // number of elements
  51       double  max_load_ratio; // maximum load ratio (> 0 && < 1)
  52       double  growth_ratio;   // amount to grow when expanding
  53       int     max_load;       // maximum elements before resizing
  54
  55    public:
  56       ////////////////////////////////////////////////////////////////////
  57       //  Constructor and destructor
  58       ////////////////////////////////////////////////////////////////////
  59       LHashTable2(int initial_size      = 32,
  60                   double max_load_ratio = 0.0,
  61                   double growth_ratio   = 2.0);
  62      ~LHashTable2();
  63
  64       ////////////////////////////////////////////////////////////////////
  65       //  Assignment
  66       ////////////////////////////////////////////////////////////////////
  67       void operator = (const LHashTable2&);
  68
  69       ////////////////////////////////////////////////////////////////////
  70       //  Selectors
  71       ////////////////////////////////////////////////////////////////////
  72       inline int  capacity() const { return table_size; }   // current capacity
  73       inline int  size()     const { return elem_count; }   // number of elements
  74       inline Bool is_empty() const { return elem_count == 0; }
  75       inline Bool is_full()  const { return elem_count == table_size; }
  76       inline Bool contains(const K& k) const { return lookup(k) != 0; }
  77       inline const V& operator [] (const K& k) const { return value(lookup(k)); }
  78       inline       V& operator [] (const K& k)       { return value(lookup(k)); }
  79
  80       ////////////////////////////////////////////////////////////////////
  81       // Insertion and deletion.
  82       ////////////////////////////////////////////////////////////////////
  83       void clear();                      // clears out the hash table
  84       Ix   lookup(const K&) const;       // lookup entry by key
  85       Ix   insert(const K&, const V&);   // insert a new entry
  86       Bool remove(const K&);             // remove an old entry
  87
  88       ////////////////////////////////////////////////////////////////////
  89       // Iteration:
  90       //    first()  start the iteration
  91       //    next()   get index to the next element; or 0 if none
  92       //    key()    get the key on index
  93       //    value()  get the value on index
  94       // Implementation note: Ix's are represented internally as 1-based
  95       // array index.
  96       ////////////////////////////////////////////////////////////////////
  97       inline Ix first()           const { return find_next(0); }
  98       inline Ix next(Ix i)        const { return find_next((int)i); }
  99       inline const K& key(Ix i)   const { return keys[(int)i-1]; }
 100       inline const V& value(Ix i) const { return values[(int)i-1]; }
 101       inline       V& value(Ix i)       { return values[(int)i-1]; }
 102
 103       ////////////////////////////////////////////////////////////////////
 104       // Resize the table
 105       ////////////////////////////////////////////////////////////////////
 106       void resize(int new_size = 0);
 107
 108    private:
 109       ////////////////////////////////////////////////////////////////////
 110       //  Addition implementation methods
 111       ////////////////////////////////////////////////////////////////////
 112       inline Ix find_next(int i) const  // locate the next used entry
 113       {  while (i < table_size) if (status[i++] == Cell_used) return (Ix)i;
 114          return (Ix)0;
 115       }
 116    };
 117
 118 //////////////////////////////////////////////////////////////////////////
 119 //  Implementation of the template methods
 120 //////////////////////////////////////////////////////////////////////////
 121
 122 //////////////////////////////////////////////////////////////////////////
 123 //  Create a new table.
 124 //  Implementation note: each end of each chain of the buckets are
 125 //  linked to the next.  This makes it possible to find the next entry
 126 //  during iteration quickly.
 127 //////////////////////////////////////////////////////////////////////////
 128 template <class K, class V, class C>
 129    LHashTable2<K,V,C>::LHashTable2
 130        (int size, double maximum_load_ratio, double growth)
 131       : keys(new K [size]), values(new V [size]),
 132         status(new char [size]),
 133         table_size(size)
 134    {  clear();
 135       if (maximum_load_ratio >= 0.9 || maximum_load_ratio <= 0.1)
 136          max_load_ratio = .7;
 137       else
 138          max_load_ratio = maximum_load_ratio;
 139       if (growth <= 1.2 || growth >= 5.0) growth_ratio = 2.0;
 140       else growth_ratio = growth;
 141       max_load = (int)(max_load_ratio * size);
 142       if (max_load >= size) max_load = size - 1;
 143    }
 144
 145 //////////////////////////////////////////////////////////////////////////
 146 //  Destroy a table
 147 //////////////////////////////////////////////////////////////////////////
 148 template <class K, class V, class C>
 149    LHashTable2<K,V,C>::~LHashTable2()
 150    {  delete [] keys; delete [] values; delete [] status; }
 151
 152 //////////////////////////////////////////////////////////////////////////
 153 //  Assignment
 154 //////////////////////////////////////////////////////////////////////////
 155 template <class K, class V, class C>
 156    void LHashTable2<K,V,C>::operator = (const LHashTable2<K,V,C>& t)
 157    {  if (this != &t) {
 158          delete [] keys; delete [] values; delete [] status;
 159          elem_count = t.elem_count;
 160          table_size = t.table_size;
 161          keys   = new K    [table_size];
 162          values = new V    [table_size];
 163          status = new char [table_size];
 164          for (int i = 0; i < table_size; i++) {
 165             if ((status[i] = t.status[i]) == Cell_used) {
 166                keys[i] = t.keys[i]; values[i] = t.values[i];
 167             }
 168          }
 169       }
 170    }
 171
 172 //////////////////////////////////////////////////////////////////////////
 173 //  Clear a table.
 174 //  We'll traverse thru all the buckets and delete each one iteratively.
 175 //////////////////////////////////////////////////////////////////////////
 176 template <class K, class V, class C>
 177    void LHashTable2<K,V,C>::clear()
 178    {  memset(status,0,table_size); elem_count = 0; }
 179
 180 //////////////////////////////////////////////////////////////////////////
 181 //  Lookup an entry by key; if the entry is not found, return (Ix)0.
 182 //  A simple linear search is used.
 183 //////////////////////////////////////////////////////////////////////////
 184 template <class K, class V, class C>
 185    Ix LHashTable2<K,V,C>::lookup(const K& key) const
 186    {  int i = C::hash(key) % table_size;
 187       for (;;) {
 188          switch (status[i]) {
 189             case Cell_unused: return (Ix)0;
 190             case Cell_used:   if (C::equal(key,keys[i])) return (Ix)(i+1);
 191          }
 192          if (++i == table_size) i = 0;
 193       }
 194    }
 195
 196 //////////////////////////////////////////////////////////////////////////
 197 //  Insert a new entry; there are two different cases of behavior:
 198 //  (1) If the key doesn't already exists, new key/value pair will be
 199 //      inserted into the table.
 200 //  (2) If the key already exists, then the old value will be overwritten
 201 //      by the new value.
 202 //  Also, if the number of elements have exceeded the maximum load,
 203 //  the table will be automatically resized.
 204 //////////////////////////////////////////////////////////////////////////
 205 template <class K, class V, class C>
 206    Ix LHashTable2<K,V,C>::insert(const K& key, const V& value)
 207    {
 208       /////////////////////////////////////////////////////////////////////
 209       // Make sure we have at least one unused cell.
 210       /////////////////////////////////////////////////////////////////////
 211       if (elem_count >= max_load) resize();
 212       register int i = C::hash(key) % table_size;
 213       register int deleted;
 214
 215       /////////////////////////////////////////////////////////////////////
 216       //  Loop until one of the following:
 217       //    (1) The key is found; in which case the value is updated.
 218       //    (2) An unused cell is found; then we'll use the first
 219       //        deleted cell found along the way.  If there is none,
 220       //        we'll use the unused cell.   This is done to minimize
 221       //        the effect of contamination.
 222       /////////////////////////////////////////////////////////////////////
 223       for (deleted = -1;;) {
 224          switch (status[i]) {
 225             case Cell_deleted: if (deleted < 0) deleted = i; break;
 226             case Cell_unused:  goto found;
 227             case Cell_used:    if (C::equal(key,keys[i]))
 228                                   { values[i] = value; return (Ix)(i+1); }
 229          }
 230          if (++i == table_size) i = 0;
 231       }
 232    found:
 233       if (deleted >= 0) i = deleted; elem_count++;
 234       keys[i] = key; values[i] = value; status[i] = Cell_used;
 235       return (Ix)(i+1);
 236    }
 237
 238 //////////////////////////////////////////////////////////////////////////
 239 //  Resizing the hash table.  All entries are completed rehashed.
 240 //////////////////////////////////////////////////////////////////////////
 241 template <class K, class V, class C>
 242    void LHashTable2<K,V,C>::resize(int new_size)
 243    {  if (new_size <= elem_count) new_size = (int)(table_size * growth_ratio);
 244
 245       char * new_status = new char [ new_size ];
 246       K    * new_keys   = new K    [ new_size ];
 247       V    * new_values = new V    [ new_size ];
 248       memset(new_status,0,new_size);
 249
 250       //////////////////////////////////////////////////////////////////
 251       //  Rehash all used cells one by one.  Notice that since all keys
 252       //  are unique, we don't have to do any comparison.
 253       //////////////////////////////////////////////////////////////////
 254       for (int i = 0; i < table_size; i++) {
 255          if (status[i] == Cell_used) {
 256             register int j = C::hash(keys[i]) % new_size;
 257             for (;;) {
 258                if (new_status[j] != Cell_used) {
 259                   new_keys[j] = keys[i]; new_values[j] = values[i];
 260                   new_status[j] = Cell_used; break;
 261                }
 262                if (++j == new_size) j = 0;
 263             }
 264          }
 265       }
 266       delete [] keys; delete [] values; delete [] status;
 267       keys = new_keys; values = new_values; status = new_status;
 268       table_size = new_size;
 269       max_load = (int)(max_load_ratio * table_size);
 270    }
 271
 272 //////////////////////////////////////////////////////////////////////////
 273 //  Remove an entry from the table; there are two different cases:
 274 //  (1) If the key exists within the table, the key/value pair will be
 275 //      removed; otherwise
 276 //  (2) The table will be unaltered.
 277 //      If the removal operation successfully deletes the entry,
 278 //      we'll also return true to the client.
 279 //////////////////////////////////////////////////////////////////////////
 280 template <class K, class V, class C>
 281    Bool LHashTable2<K,V,C>::remove(const K& key)
 282    {  Ix i;
 283       ///////////////////////////////////////////////////////////////////
 284       // We'll just call lookup() to do the dirty work of locating the
 285       // appropriate entry.
 286       ///////////////////////////////////////////////////////////////////
 287       if ((i = lookup(key))) {
 288          elem_count--; status[(int)i-1] = Cell_deleted; return true;
 289       } else return false;
 290    }
 291
 292 #endif