include/AD/hash/dchash2.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 direct_chaining_hash_table2_h
  26 #define direct_chaining_hash_table2_h
  27
  28 ////////////////////////////////////////////////////////////////////////////
  29 //  Class DCHashTable2 implements a hash table using direct
  30 //  chaining.
  31 ////////////////////////////////////////////////////////////////////////////
  32
  33 #include <AD/generic/ordering.h>
  34
  35 ////////////////////////////////////////////////////////////////////////////
  36 //  Class |DCHashTable| is parameterized with the class of the
  37 //  key and the class of the value.  Furthermore, the functions
  38 //      unsigned int hash(const K&);          and
  39 //      Bool     equal(const K&, const K&);
  40 //  must be defined by the client that uses this template.
  41 ////////////////////////////////////////////////////////////////////////////
  42 template <class K, class V, class C>
  43    class DCHashTable2 {
  44
  45       //////////////////////////////////////////////////////////////////////
  46       // A link in the hash chain
  47       //////////////////////////////////////////////////////////////////////
  48       struct Link {
  49          const K      key;          // key of entry
  50                V      value;        // value of entry
  51                Link * next;         // next entry or next bucket
  52          Link(const K& k, const V& v, Link * link)
  53             : key(k), value(v), next(link) {}
  54       };
  55
  56       //////////////////////////////////////////////////////////////////////
  57       // Is the link really a link?
  58       //////////////////////////////////////////////////////////////////////
  59       inline friend Bool   is_link(const Link * l)
  60          { return (((unsigned long)l) & 1) == 0; }
  61       inline friend Link * make_anchor(Link ** l)
  62          { return (DCHashTable2<K,V,C>::Link*)(((unsigned long)l)|1);}
  63       Ix   find_next(Ix i) const   // find next key given an index
  64       {  if (i) {
  65             Link ** bucket = (Link**)(((unsigned long)i) & ~1);
  66             Link ** limit  = table + table_size;
  67             for ( ; bucket < limit; bucket++)
  68                if (is_link(*bucket)) return *bucket;
  69          }
  70          return 0;
  71       }
  72
  73       Link ** table;          // the array of hash links
  74       int     table_size;     // size of the array
  75       int     elem_count;     // number of elements
  76       int     max_load;       // maximum number of entries before expansion
  77       double  max_load_ratio; // maximum ratio between entries versus buckets
  78       double  growth_ratio;   // amount to expand when resizing
  79
  80    public:
  81       ////////////////////////////////////////////////////////////////////
  82       //  Constructor and destructor
  83       ////////////////////////////////////////////////////////////////////
  84       DCHashTable2(int initial_size      = 32,
  85                    double max_load_ratio = 0.0,
  86                    double growth_ratio   = 2.0);
  87      ~DCHashTable2();
  88
  89       ////////////////////////////////////////////////////////////////////
  90       //  Assignment
  91       ////////////////////////////////////////////////////////////////////
  92       void operator = (const DCHashTable2&);
  93
  94       ////////////////////////////////////////////////////////////////////
  95       //  Selectors
  96       ////////////////////////////////////////////////////////////////////
  97       inline int  capacity() const { return table_size; }   // current capacity
  98       inline int  size()     const { return elem_count; }   // number of elements
  99       inline Bool is_empty() const { return elem_count == 0; }
 100       inline Bool is_full()  const { return elem_count == table_size; }
 101       inline Bool contains(const K& k) const { return lookup(k) != 0; }
 102       inline const V& operator [] (const K& k) const { return value(lookup(k)); }
 103       inline       V& operator [] (const K& k)       { return value(lookup(k)); }
 104
 105       ////////////////////////////////////////////////////////////////////
 106       // Insertion and deletion.
 107       ////////////////////////////////////////////////////////////////////
 108       void clear();                      // clears out the hash table
 109       Ix   lookup(const K&) const;       // lookup entry by key
 110       Ix   insert(const K&, const V&);   // insert a new entry
 111       Bool remove(const K&);             // remove an old entry
 112
 113       ////////////////////////////////////////////////////////////////////
 114       // Iteration:
 115       //    first()  start the iteration
 116       //    next()   get index to the next element; or 0 if none
 117       //    key()    get the key on index
 118       //    value()  get the value on index
 119       ////////////////////////////////////////////////////////////////////
 120       inline Ix first()     const { return find_next(table); }
 121       inline Ix next(Ix i)  const
 122          {  Link * pos = ((Link*)i)->next;
 123             return is_link(pos) ? pos : find_next(pos);
 124          }
 125       inline const K& key(Ix i)   const { return ((Link*)i)->key; }
 126       inline const V& value(Ix i) const { return ((Link*)i)->value; }
 127       inline       V& value(Ix i)       { return ((Link*)i)->value; }
 128
 129       ////////////////////////////////////////////////////////////////////
 130       //  Resize the table
 131       ////////////////////////////////////////////////////////////////////
 132       void resize(int new_size = 0);
 133    };
 134
 135 //////////////////////////////////////////////////////////////////////////
 136 //  Implementation of the template methods
 137 //////////////////////////////////////////////////////////////////////////
 138
 139 //////////////////////////////////////////////////////////////////////////
 140 //  Create a new table.
 141 //  Implementation note: each end of each chain of the buckets are
 142 //  linked to the next.  This makes it possible to find the next entry
 143 //  during iteration quickly.
 144 //////////////////////////////////////////////////////////////////////////
 145 template <class K, class V, class C>
 146    DCHashTable2<K,V,C>::DCHashTable2
 147       (int size, double maximum_load_ratio, double growth)
 148       : table_size(size), elem_count(0), table(new Link * [size])
 149    {  register int i;
 150       for (i = 1; i < size; i++) table[i-1] = make_anchor(table+i);
 151       if (size > 0) table[i-1] = 0;
 152       if (maximum_load_ratio <= 1.0) {
 153          max_load_ratio = 100000;
 154          max_load = 10000000;
 155       } else {
 156          max_load_ratio = maximum_load_ratio;
 157          max_load = (int)(size * maximum_load_ratio);
 158       }
 159       if (growth <= 1.2 || growth >= 5.0) growth_ratio = 2.0;
 160       else growth_ratio = growth;
 161    }
 162
 163 //////////////////////////////////////////////////////////////////////////
 164 //  Destroy a table
 165 //////////////////////////////////////////////////////////////////////////
 166 template <class K, class V, class C>
 167    DCHashTable2<K,V,C>::~DCHashTable2()
 168    {  clear(); delete [] table; }
 169
 170 //////////////////////////////////////////////////////////////////////////
 171 //  Assignment
 172 //////////////////////////////////////////////////////////////////////////
 173 template <class K, class V, class C>
 174    void DCHashTable2<K,V,C>::operator = (const DCHashTable2<K,V,C>& t)
 175    {  if (this != &t) {
 176          clear(); delete [] table;
 177          elem_count = 0;
 178          table      = new Link * [table_size = t.table_size];
 179          for (Ix i = t.first(); i; i = t.next(i))
 180             insert(t.key(i), t.value(i));
 181       }
 182    }
 183
 184 //////////////////////////////////////////////////////////////////////////
 185 //  Clear a table.
 186 //  We'll traverse thru all the buckets and delete each one iteratively.
 187 //////////////////////////////////////////////////////////////////////////
 188 template <class K, class V, class C>
 189    void DCHashTable2<K,V,C>::clear()
 190    {  int i;
 191       for (i = 0; i < table_size; i++) {
 192          Link * l, * next;
 193          for (l = table[i]; l && is_link(l); l = next) {
 194             next = l->next; delete l;
 195          }
 196       }
 197       for (i = 1; i < table_size; i++) table[i-1] = make_anchor(table+i);
 198       if (table_size > 0) table[i-1] = 0;
 199       elem_count = 0;
 200    }
 201
 202 //////////////////////////////////////////////////////////////////////////
 203 //  Lookup an entry by key; if the entry is not found, return (Ix)0.
 204 //  A simple linear search is used.
 205 //////////////////////////////////////////////////////////////////////////
 206 template <class K, class V, class C>
 207    Ix DCHashTable2<K,V,C>::lookup(const K& key) const
 208    {  unsigned int index = C::hash(key) % table_size;
 209       Link * link  = table[index];
 210       for ( ;link && is_link(link); link = link->next)
 211          if (C::equal(key, link->key)) return (Ix)link;
 212       return (Ix)0;
 213    }
 214
 215 //////////////////////////////////////////////////////////////////////////
 216 //  Insert a new entry; there are two different cases of behavior:
 217 //  (1) If the key doesn't already exists, new key/value pair will be
 218 //      inserted into the table.
 219 //  (2) If the key already exists, then the old value will be overwritten
 220 //      by the new value.
 221 //  Also, if the number of elements have exceeded the maximum load,
 222 //  the table will be automatically resized.
 223 //////////////////////////////////////////////////////////////////////////
 224 template <class K, class V, class C>
 225    Ix DCHashTable2<K,V,C>::insert(const K& key, const V& value)
 226    {  unsigned int index = C::hash(key) % table_size;
 227       Link * link  = table[index];
 228       for ( ;link && is_link(link); link = link->next)
 229          if (C::equal(key, link->key)) {
 230             link->value = value; return link;
 231          }
 232       table[index] = new Link (key,value,table[index]);
 233       if (++elem_count > max_load) resize();
 234       return table[index];
 235    }
 236
 237 //////////////////////////////////////////////////////////////////////////
 238 //  Resizing the hash table
 239 //////////////////////////////////////////////////////////////////////////
 240 template <class K, class V, class C>
 241    void DCHashTable2<K,V,C>::resize(int new_size)
 242    {  if (new_size <= max_load)
 243          new_size = (int)(max_load * growth_ratio);
 244
 245       Link ** new_table = new Link * [new_size];
 246       register int i;
 247
 248       ////////////////////////////////////////////////////////////////////
 249       // Set up the anchor links of new table first
 250       ////////////////////////////////////////////////////////////////////
 251       for (i = 1; i < new_size; i++) new_table[i-1] = make_anchor(new_table+i);
 252       if (new_size > 0) new_table[i-1] = 0;
 253
 254       ////////////////////////////////////////////////////////////////////
 255       // Then traverse the old table and move the links to the new one
 256       ////////////////////////////////////////////////////////////////////
 257       for (i = 0; i < table_size; i++) {
 258          Link * l, * next;
 259          for (l = table[i]; l && is_link(l); l = next) {
 260             unsigned int new_index = C::hash(l->key) % new_size;
 261             next = l->next;
 262             l->next = new_table[new_index];
 263             new_table[new_index] = l;
 264          }
 265       }
 266       delete [] table;
 267       table      = new_table;
 268       max_load   = (int)(new_size * max_load_ratio);
 269       table_size = new_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 DCHashTable2<K,V,C>::remove(const K& key)
 282    {  unsigned int index = C::hash(key) % table_size;
 283       Link * link  = table[index];
 284       Link * last  = 0;
 285       for ( ;link && is_link(link); last = link, link = link->next)
 286          if (C::equal(key, link->key)) {
 287             if (last)
 288                last->next = link->next; // redirect link
 289             else
 290                table[index] = link->next;
 291             delete link;              // frees the old entry
 292             elem_count--;
 293             return true;
 294          }
 295       return false;
 296    }
 297
 298 #endif