include/AD/hash/ohash2.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 hash_table_with_ordered_hashing2_h
  26 #define hash_table_with_ordered_hashing2_h
  27
  28 ////////////////////////////////////////////////////////////////////////////
  29 // Class OHashTable2 implements a hash table using an ordered hashing
  30 // scheme\cite{Algorithms}.  Ordered hashing simulates the effect
  31 // of insertion in increasing order by reordering keys in a probe sequence
  32 // if it is found that they are out of order.   It helps unsuccessful
  33 // searches to terminate faster by eliminating unnecessary probes
  34 // once the next key proves to be smaller that the current one.
  35 ////////////////////////////////////////////////////////////////////////////
  36
  37 #include <string.h>
  38 #include <AD/generic/ordering.h>
  39
  40 ////////////////////////////////////////////////////////////////////////////
  41 //  Class |OHashTable2| is parameterized with the class of the
  42 //  key and the class of the value.  Furthermore, the functions
  43 //      unsigned int hash(const K&);          and
  44 //      int      compare(const K&, const K&)
  45 //  must be defined by the client that uses this template.
  46 ////////////////////////////////////////////////////////////////////////////
  47 template <class K, class V, class C>
  48    class OHashTable2 {
  49
  50       K *     keys;           // the array of keys
  51       V *     values;         // the array of values
  52       char *  status;         // status of cell
  53       int     table_size;     // size of the array
  54       int     elem_count;     // number of elements
  55       double  max_load_ratio; // maximum load ratio (> 0 && < 1)
  56       double  growth_ratio;   // amount to expand when resizing
  57       int     max_load;       // maximum elements before resizing
  58
  59    public:
  60       ////////////////////////////////////////////////////////////////////
  61       //  Constructor and destructor
  62       ////////////////////////////////////////////////////////////////////
  63       OHashTable2(int    initial_size   = 32,
  64                   double max_load_ratio = 0.0,
  65                   double growth_ratio   = 2.0);
  66      ~OHashTable2();
  67
  68       ////////////////////////////////////////////////////////////////////
  69       //  Assignment
  70       ////////////////////////////////////////////////////////////////////
  71       void operator = (const OHashTable2&);
  72
  73       ////////////////////////////////////////////////////////////////////
  74       //  Selectors
  75       ////////////////////////////////////////////////////////////////////
  76       inline int  capacity() const { return table_size; }   // current capacity
  77       inline int  size()     const { return elem_count; }   // number of elements
  78       inline Bool is_empty() const { return elem_count == 0; }
  79       inline Bool is_full()  const { return elem_count == table_size; }
  80       inline Bool contains(const K& k) const { return lookup(k) != 0; }
  81       inline const V& operator [] (const K& k) const { return value(lookup(k)); }
  82       inline       V& operator [] (const K& k)       { return value(lookup(k)); }
  83
  84       ////////////////////////////////////////////////////////////////////
  85       // Insertion and deletion.
  86       ////////////////////////////////////////////////////////////////////
  87       void clear();                      // clears out the hash table
  88       Ix   lookup(const K&) const;       // lookup entry by key
  89       Ix   insert(const K, const V);     // insert a new entry
  90       Bool remove(const K&);             // remove an old entry
  91
  92       ////////////////////////////////////////////////////////////////////
  93       // Iteration:
  94       //    first()  start the iteration
  95       //    next()   get index to the next element; or 0 if none
  96       //    key()    get the key on index
  97       //    value()  get the value on index
  98       // Implementation note: Ix's are represented internally as 1-based
  99       // array index.
 100       ////////////////////////////////////////////////////////////////////
 101       inline Ix first()           const { return find_next(0); }
 102       inline Ix next(Ix i)        const { return find_next((int)i); }
 103       inline const K& key(Ix i)   const { return keys[(int)i-1]; }
 104       inline const V& value(Ix i) const { return values[(int)i-1]; }
 105       inline       V& value(Ix i)       { return values[(int)i-1]; }
 106
 107       ////////////////////////////////////////////////////////////////////
 108       // Resizing the table
 109       ////////////////////////////////////////////////////////////////////
 110       void resize(int new_size = 0);
 111
 112    private:
 113       ////////////////////////////////////////////////////////////////////
 114       //  Addition implementation methods
 115       ////////////////////////////////////////////////////////////////////
 116       inline Ix find_next(int i) const;  // locate the next used entry
 117    };
 118
 119 //////////////////////////////////////////////////////////////////////////
 120 //  Implementation of the template methods
 121 //////////////////////////////////////////////////////////////////////////
 122
 123 //////////////////////////////////////////////////////////////////////////
 124 //  Locate the next used cell; called by the iterator functions
 125 //////////////////////////////////////////////////////////////////////////
 126 template <class K, class V, class C>
 127    inline Ix OHashTable2<K,V,C>::find_next(register int i) const
 128    {  while (i < table_size) if (status[i++] == Cell_used) return (Ix)i;
 129       return (Ix)0;
 130    }
 131
 132 //////////////////////////////////////////////////////////////////////////
 133 //  Create a new table.
 134 //  Implementation note: each end of each chain of the buckets are
 135 //  linked to the next.  This makes it possible to find the next entry
 136 //  during iteration quickly.
 137 //////////////////////////////////////////////////////////////////////////
 138 template <class K, class V, class C>
 139    OHashTable2<K,V,C>::OHashTable2
 140        (int size, double maximum_load_ratio, double growth)
 141       : keys(new K [size]), values(new V [size]),
 142         status(new char [size]),
 143         table_size(size)
 144    {  clear();
 145       if (maximum_load_ratio >= 0.9 || maximum_load_ratio <= 0.1)
 146          max_load_ratio = .7;
 147       else
 148          max_load_ratio = maximum_load_ratio;
 149       max_load = (int)(max_load_ratio * size);
 150       if (max_load >= size) max_load = size - 1;
 151       if (growth <= 1.2 || growth >= 5.0) growth_ratio = 2.0;
 152       else growth_ratio = growth;
 153    }
 154
 155 //////////////////////////////////////////////////////////////////////////
 156 //  Destroy a table
 157 //////////////////////////////////////////////////////////////////////////
 158 template <class K, class V, class C>
 159    OHashTable2<K,V,C>::~OHashTable2()
 160    {  delete [] keys; delete [] values; delete [] status; }
 161
 162 //////////////////////////////////////////////////////////////////////////
 163 //  Assignment
 164 //////////////////////////////////////////////////////////////////////////
 165 template <class K, class V, class C>
 166    void OHashTable2<K,V,C>::operator = (const OHashTable2<K,V,C>& t)
 167    {  if (this != &t) {
 168          delete [] keys; delete [] values; delete [] status;
 169          elem_count = t.elem_count;
 170          table_size = t.table_size;
 171          keys   = new K    [table_size];
 172          values = new V    [table_size];
 173          status = new char [table_size];
 174          for (int i = 0; i < table_size; i++) {
 175             if ((status[i] = t.status[i]) == Cell_used) {
 176                keys[i] = t.keys[i]; values[i] = t.values[i];
 177             }
 178          }
 179       }
 180    }
 181
 182 //////////////////////////////////////////////////////////////////////////
 183 //  Clear a table.
 184 //  We'll traverse thru all the buckets and delete each one iteratively.
 185 //////////////////////////////////////////////////////////////////////////
 186 template <class K, class V, class C>
 187    void OHashTable2<K,V,C>::clear()
 188    {  memset(status,0,table_size); elem_count = 0; }
 189
 190 //////////////////////////////////////////////////////////////////////////
 191 //  Lookup an entry by key; if the entry is not found, return (Ix)0.
 192 //////////////////////////////////////////////////////////////////////////
 193 template <class K, class V, class C>
 194    Ix OHashTable2<K,V,C>::lookup(const K& key) const
 195    {  unsigned int h    = C::hash(key);
 196       unsigned int i    = h % table_size;
 197       unsigned int inc  = 0;  // increment
 198       unsigned int last;
 199
 200       ////////////////////////////////////////////////////////////////////
 201       // Since the size of the hash table is not necessary a prime,
 202       // care must be taken so that each probing sequence covers the
 203       // entire table.  The simple strategy of computing new location as
 204       //        i = (i + inc) % table_size
 205       // cannot be used.
 206       ////////////////////////////////////////////////////////////////////
 207       for (;;) {
 208          switch (status[i]) {
 209             case Cell_unused: return (Ix)0;
 210             case Cell_used:
 211                int r = C::compare(keys[i],key);
 212                if (r == 0) return (Ix)(i+1);
 213                if (r >  0) return (Ix)0;
 214          }
 215          ////////////////////////////////////////////////////////////////////
 216          // Compute increment only if the initial probe fails.
 217          ////////////////////////////////////////////////////////////////////
 218          if (inc == 0) {
 219             // recycle those higher order bits of hash value
 220             inc = ( h / table_size ) % table_size;
 221             if (inc == 0) inc = 1; // use linear probing if all else fails
 222             last = i;
 223          }
 224          i += inc;
 225          if (i >= table_size) i -= table_size;
 226          if (i == last) { last = ++i; }
 227       }
 228    }
 229
 230 //////////////////////////////////////////////////////////////////////////
 231 //  Insert a new entry; there are two different cases of behavior:
 232 //  (1) If the key doesn't already exists, new key/value pair will be
 233 //      inserted into the table.
 234 //  (2) If the key already exists, then the old value will be overwritten
 235 //      by the new value.
 236 //  Also, if the number of elements have exceeded the maximum load,
 237 //  the table will be automatically resized.
 238 //////////////////////////////////////////////////////////////////////////
 239 template <class K, class V, class C>
 240    Ix OHashTable2<K,V,C>::insert(const K key, const V value)
 241    {  /////////////////////////////////////////////////////////////////////
 242       // Make sure we have at least one unused cell.
 243       /////////////////////////////////////////////////////////////////////
 244       if (elem_count >= max_load) resize();
 245       unsigned int h   = C::hash(key);
 246       unsigned int i   = h % table_size;
 247       unsigned int inc = 0;
 248       unsigned int last; int count;
 249
 250       /////////////////////////////////////////////////////////////////////
 251       //  Loop until one of the following:
 252       //    (1) The key is found; in which case the value is updated.
 253       //    (2) An unused cell is found, or a deleted cell is found
 254       //        and we have looped over all the entries once around.
 255       /////////////////////////////////////////////////////////////////////
 256       for (count = table_size ;; count--) {
 257          switch (status[i]) {
 258             case Cell_deleted: if (count > 0) break;
 259             case Cell_unused:
 260                elem_count++;
 261                keys[i] = key; values[i] = value; status[i] = Cell_used;
 262                return (Ix)(i+1);
 263             case Cell_used:
 264                int r = C::compare(keys[i],key);
 265                if (r == 0) { values[i] = value; return (Ix)(i+1); }
 266                if (r > 0) { // exchange entries and continue
 267                   K k = key; key = keys[i]; keys[i] = k;
 268                   V v = value; value = values[i]; values[i] = v;
 269                   h = C::hash(key); inc = 0;
 270                }
 271          }
 272          if (inc == 0) {
 273             // recycle those higher order bits of hash value
 274             inc = ( h / table_size ) % table_size;
 275             if (inc == 0) inc = 1; // use linear probing if all else fails
 276             last = i;
 277          }
 278          i += inc;
 279          if (i >= table_size) i -= table_size;
 280          if (i == last) { last = ++i; }
 281       }
 282    }
 283
 284 //////////////////////////////////////////////////////////////////////////
 285 //  Resizing the hash table.  All entries are completed rehashed.
 286 //////////////////////////////////////////////////////////////////////////
 287 template <class K, class V, class C>
 288    void OHashTable2<K,V,C>::resize(int new_size)
 289    {  if (new_size <= elem_count)
 290          new_size = (int)(table_size * growth_ratio);
 291
 292       //////////////////////////////////////////////////////////////////
 293       // Just making sure the new size makes sense.
 294       //////////////////////////////////////////////////////////////////
 295       if (new_size <= table_size) new_size = table_size + 32;
 296       char * new_status = new char [ new_size ];
 297       K    * new_keys   = new K    [ new_size ];
 298       V    * new_values = new V    [ new_size ];
 299       memset(new_status,0,new_size);
 300
 301       //////////////////////////////////////////////////////////////////
 302       //  Rehash all used cells one by one.  Notice that since all keys
 303       //  are unique, we don't have to do any comparison.
 304       //////////////////////////////////////////////////////////////////
 305       for (int i = 0; i < table_size; i++) {
 306          if (status[i] == Cell_used) {
 307             unsigned int h = C::hash(keys[i]);
 308             unsigned int j = h % new_size;
 309             unsigned int inc = 0, last;
 310             for (;;) {
 311                if (new_status[j] != Cell_used) {
 312                   new_keys[j] = keys[i]; new_values[j] = values[i];
 313                   new_status[j] = Cell_used; break;
 314                }
 315                int r = C::compare(new_keys[j],keys[i]);
 316                if (r > 0) { // exchange entries and continue
 317                   K k = new_keys[j]; new_keys[j] = keys[i]; keys[i] = k;
 318                   V v = new_values[j]; new_values[j] = values[i]; values[i] = v;
 319                   h = C::hash(k); inc = 0;
 320                }
 321                if (inc == 0) {
 322                   inc = ( h / new_size ) % new_size;
 323                   if (inc == 0) inc = 1; last = j;
 324                }
 325                j += inc;
 326                if (j >= new_size) j -= new_size;
 327                if (j == last) { last = ++j; }
 328             }
 329          }
 330       }
 331       delete [] keys; delete [] values; delete [] status;
 332       keys = new_keys; values = new_values; status = new_status;
 333       table_size = new_size;
 334       max_load = (int)(max_load_ratio * table_size);
 335    }
 336
 337 //////////////////////////////////////////////////////////////////////////
 338 //  Remove an entry from the table; there are two different cases:
 339 //  (1) If the key exists within the table, the key/value pair will be
 340 //      removed; otherwise
 341 //  (2) The table will be unaltered.
 342 //      If the removal operation successfully deletes the entry,
 343 //      we'll also return true to the client.
 344 //////////////////////////////////////////////////////////////////////////
 345 template <class K, class V, class C>
 346    Bool OHashTable2<K,V,C>::remove(const K& key)
 347    {  Ix i;
 348       ///////////////////////////////////////////////////////////////////
 349       // We'll just call lookup() to do the dirty work of locating the
 350       // appropriate entry.
 351       ///////////////////////////////////////////////////////////////////
 352       if ((i = lookup(key))) {
 353          elem_count--; status[(int)i-1] = Cell_deleted; return true;
 354       } else return false;
 355    }
 356
 357 #endif