core/library/structures/hash_table.h

   1 #ifndef HASH_TABLE_CLASS
   2 #define HASH_TABLE_CLASS
   3
   4 /*****************************************************************************\
   5 *                                                                             *
   6 *  Name   : hash_table                                                        *
   7 *  Author : Chris Koeritz                                                     *
   8 *                                                                             *
   9 *******************************************************************************
  10 * Copyright (c) 2001-$now By Author.  This program is free software; you can  *
  11 * redistribute it and/or modify it under the terms of the GNU General Public  *
  12 * License as published by the Free Software Foundation; either version 2 of   *
  13 * the License or (at your option) any later version.  This is online at:      *
  14 *     http://www.fsf.org/copyleft/gpl.html                                    *
  15 * Please send any updates to: fred@gruntose.com                               *
  16 \*****************************************************************************/
  17
  18 #include "amorph.h"
  19
  20 #include <basis/array.h>
  21 #include <basis/byte_array.h>
  22 #include <basis/contracts.h>
  23 #include <basis/enhance_cpp.h>
  24 #include <basis/functions.h>
  25
  26 #include <math.h>
  27
  28 namespace structures {
  29
  30 // forward.
  31 template <class key, class contents> class internal_hash_array;
  32
  33 //! A hashing algorithm takes a key and derives a related integer from it.
  34 /*!
  35   The hashing_algorithm is used in hash_tables for placing objects into slots
  36   that can be easily found again.  The numerical hash should be faster than
  37   actually doing a search on what might be unsorted data otherwise.
  38 */
  39
  40 class hashing_algorithm : public virtual basis::clonable
  41 {
  42 public:
  43   virtual basis::un_int hash(const void *key_data, int key_length) const = 0;
  44     //!< returns a hash value based on the "key_data" and "key_length".
  45     /*!< the "key_length" is provided from the sizeof() of the key type used
  46     in the hash_table (below).  it is up to the implementor to create a hash
  47     value that spreads the keys to be hashed appropriately.  if similar keys
  48     create same or similar hash values, then the efficiency of the hash_table
  49     is compromised. */
  50
  51   virtual hashing_algorithm *clone() const = 0;
  52     //!< supports virtual construction of new algorithm objects.
  53 };
  54
  55 //////////////
  56
  57 //! Implements hashing into buckets for quick object access.
  58 /*!
  59   The buckets are currently simple lists, but if the hashing algorithm is well
  60   chosen, then that's not a major problem.  This makes lookups a lot faster
  61   than a linear search, but no particular performance guarantees are made at
  62   this time (hmmm).
  63 */
  64
  65 template <class key_type, class contents>
  66   // the key_type must support valid copy constructor, assignment operator and
  67   // equality operators.  the contents need not support any special operations;
  68   // it is always considered as just a pointer.
  69 class hash_table : public virtual basis::nameable
  70 {
  71 public:
  72   hash_table(const hashing_algorithm &hasher, int estimated_elements);
  73     //!< Creates a table using the "hasher" that is ready to store "estimated_elements".
  74     /*!< the "hasher" must provide the hashing algorithm for the two types
  75     specified.  if the implementation is thread safe, then one object can
  76     be constructed to use with all the same types of hash tables.
  77     note that "hasher" must exist longer than any classes based on it; do
  78     not let "hasher" go out of scope or the hash table will explode. */
  79
  80   virtual ~hash_table();
  81     //!< destroys any objects left in the hash_table.
  82
  83   DEFINE_CLASS_NAME("hash_table");
  84
  85   void rehash(int estimated_elements);
  86     //!< resizes the hashing structures to optimise for a new size of "estimated_elements".
  87     /*!< this is a potentially expensive operation. */
  88
  89   enum outcomes {
  90     IS_NEW = basis::common::IS_NEW,
  91     EXISTING = basis::common::EXISTING
  92   };
  93
  94   static int calculate_num_slots(int estimated_elements);
  95     //!< a helper method that lets us know what n is for how many 2^n slots we should have.
  96
  97   int elements() const;
  98     //!< the number of valid items we found by traversing the hash table.
  99     /*!< this is a very costly method. */
 100
 101   int estimated_elements() const { return c_estim_elements; }
 102     //!< returns the size of table we're optimized for.
 103
 104   basis::outcome add(const key_type &key, contents *to_store);
 105     //!< Stores "to_store" into the table given its "key" for hashing.
 106     /*!< This places an entry in the hash table with the contents "to_store",
 107     using the "key" structure to identify it.  the return value reports whether
 108     the "key" was already in the list or not.  if the "key" was already in use,
 109     then the contents for it get replaced with "to_store".  note that the hash
 110     table assumes ownership of the "to_store" object but just makes a copy of
 111     the key.  thus, if an item is replaced, the previous contents are
 112     destroyed. */
 113
 114   basis::outcome fast_dangerous_add(const key_type &key, contents *to_store);
 115     //!< Like the add method above, but doesn't check for duplicates.
 116     /*!< This should only ever be used when one has already guaranteed that
 117     the table doesn't have a duplicate item for the "key" specified. */
 118
 119   bool find(const key_type &key, contents * &item_found) const;
 120     //!< locates the item specified by the "key", if possible.
 121     /*!< true is returned on success and the "item_found" is filled in.  the
 122     "item_found" is a pointer to the actual data held in the table, so do not
 123     destroy or otherwise damage the "item_found". */
 124
 125   contents *find(const key_type &key) const
 126           { contents *c = NIL; return find(key, c)? c : NIL; }
 127     //!< simplified form of above find() method.
 128
 129   contents *acquire(const key_type &key);
 130     //!< retrieves the contents held for "key" out of the table.
 131     /*!< afterwards, the contents pointer is the caller's responsibility; it
 132     is no longer in the table and must be destroyed externally.  if no item
 133     was found for the "key", then NIL is returned. */
 134
 135   bool zap(const key_type &key);
 136     //!< removes the entry with the "key" specified.
 137     /*!<  true is returned if the item was found and destroyed. */
 138
 139   void reset();
 140     //!< removes all entries in the table and returns it to a pristine state.
 141
 142   typedef bool apply_function(const key_type &key, contents &current,
 143           void *data_link);
 144     //!< the "apply_function" is what a user of the "apply" method must supply.
 145     /*!< the function will be called on every item in the table unless one of
 146     the invocations returns false; this causes the apply process to stop.
 147     the "data_link" provides a way for the function to refer back to an
 148     parent class of some sort. */
 149
 150   void apply(apply_function *to_apply, void *data_link);
 151     //!< Invokes the function "to_apply" on every entry in the table.
 152     /*!< This calls the "to_apply" function on every item in the catalog
 153     until the function returns false.  The "data_link" pointer is available to
 154     the applied method and can be used to communicate an object for use during
 155     the iteration.  NOTE: it is NOT safe to rearrange or manipulate the table
 156     in any way from your "to_apply" function. */
 157
 158   basis::outcome add(key_type *key, contents *to_store, bool check_dupes = true);
 159     //!< specialized add for a pre-existing pointer "key".
 160     /*!< responsibility for the "key" is taken over by the hash table, as of
 161     course it is for the "to_store" pointer.  this just allows others to
 162     generate new keys and hand them over to us when it might otherwise be
 163     very costly to copy the key structure.  if "check_dupes" is not true,
 164     then that asserts that you have independently verified that there's no
 165     need to check whether the key is already present. */
 166
 167   bool verify() const;
 168     //!< returns true if the hash table is internally consistent.
 169     /*!< this is mainly for debugging. */
 170
 171 private:
 172   int c_estim_elements;  //!< expected running size for the hash table.
 173   hashing_algorithm *_hasher;  //!< algorithm for getting hash value.
 174   internal_hash_array<key_type, contents> *_table;  //!< storage area.
 175   int _last_iter;
 176     //!< tracks where we left off iterating.  we restart just after that spot.
 177
 178   hash_table(const hash_table &to_copy);
 179     //!< not allowed; use the copy_hash_table function below.
 180   hash_table &operator =(const hash_table &to_copy);
 181     //!< not allowed; use the copy_hash_table function below.
 182
 183 public:
 184   internal_hash_array<key_type, contents> &table_access() const;
 185     //!< special accessor for the copy_hash_table method only.
 186 };
 187
 188 //////////////
 189
 190 //! Copies the entire hash table, given a contents type that supports copying.
 191 /*!
 192   Provides a copy operation on hash tables where the contents object supports
 193   a copy constructor, which is not appropriate to require in general.  The
 194   hash_table held in "target" will be wiped out and replaced with items
 195   equivalent to those in "source". */
 196
 197 template <class key_type, class contents>
 198 void copy_hash_table(hash_table<key_type, contents> &target,
 199     const hash_table<key_type, contents> &source);
 200
 201 //////////////
 202
 203 // implementations for longer methods below....
 204
 205 // this is a very special micro-managed class.  it holds two pointers which
 206 // it neither creates nor destroys.  thus all interaction with it must be
 207 // careful about removing these objects at the appropriate time.  we don't
 208 // want automatic memory management since we want a cheap copy on the items
 209 // in the buckets.
 210
 211 template <class key_type, class contents>
 212 class hash_wrapper : public virtual basis::root_object
 213 {
 214 public:
 215   key_type *_id;
 216   contents *_data;
 217
 218   hash_wrapper(key_type *id = NIL, contents *data = NIL)
 219       : _id(id), _data(data) {}
 220 };
 221
 222 //////////////
 223
 224 template <class key_type, class contents>
 225 class bucket
 226     : public basis::array<hash_wrapper<key_type, contents> >,
 227       public virtual basis::root_object
 228 {
 229 public:
 230   bucket() : basis::array<hash_wrapper<key_type, contents> >(0, NIL,
 231       basis::byte_array::SIMPLE_COPY | basis::byte_array::EXPONE
 232       | basis::byte_array::FLUSH_INVISIBLE) {}
 233
 234   int find(const key_type &to_find) {
 235     for (int i = 0; i < this->length(); i++) {
 236       key_type *curr_key = this->get(i)._id;
 237 //hmmm: if curr key is not set, is that a logic error?  it seems like we
 238 //      are seeing the potential for this.
 239       if (curr_key && (to_find == *curr_key))
 240         return i;
 241     }
 242     return basis::common::NOT_FOUND;
 243   }
 244 };
 245
 246 //////////////
 247
 248 template <class key_type, class contents>
 249 class internal_hash_array : public amorph<bucket<key_type, contents> >
 250 {
 251 public:
 252   internal_hash_array(int estimated_elements)
 253       : amorph<bucket<key_type, contents> >
 254            (hash_table<key_type, contents>::calculate_num_slots(estimated_elements)) {}
 255 };
 256
 257 //////////////
 258
 259 template <class key_type, class contents>
 260 hash_table<key_type, contents>::hash_table(const hashing_algorithm &hasher, int estimated_elements)
 261 : c_estim_elements(estimated_elements),
 262   _hasher(hasher.clone()),
 263   _table(new internal_hash_array<key_type, contents>(estimated_elements)),
 264   _last_iter(0)
 265 {}
 266
 267 template <class key_type, class contents>
 268 hash_table<key_type, contents>::~hash_table()
 269 {
 270 #ifdef EXTREME_CHECKING
 271   FUNCDEF("destructor");
 272   if (!verify()) deadly_error(class_name(), func, "state did not verify.");
 273 #endif
 274   reset();
 275   basis::WHACK(_table);
 276   basis::WHACK(_hasher);
 277 }
 278
 279 template <class key_type, class contents>
 280 int hash_table<key_type, contents>::calculate_num_slots(int estimated_elements)
 281 {
 282 //printf("elems wanted = %d\n", estimated_elements);
 283   int log_2_truncated = int(log(float(estimated_elements)) / log(2.0));
 284 //printf("log 2 of elems, truncated = %d\n", log_2_truncated);
 285   int slots_needed_for_elems = (int)pow(2.0, double(log_2_truncated + 1));
 286 //printf("slots needed = %d\n", slots_needed_for_elems );
 287   return slots_needed_for_elems;
 288 }
 289
 290 // the specialized copy operation.
 291 template <class key_type, class contents>
 292 void copy_hash_table(hash_table<key_type, contents> &target,
 293     const hash_table<key_type, contents> &source)
 294 {
 295 #ifdef EXTREME_CHECKING
 296   FUNCDEF("copy_hash_table");
 297   if (!source.verify())
 298     deadly_error(class_name(), func, "source state did not verify.");
 299 #endif
 300   target.reset();
 301   for (int i = 0; i < source.table_access().elements(); i++) {
 302     bucket<key_type, contents> *buck = source.table_access().borrow(i);
 303     if (!buck) continue;
 304     for (int j = 0; j < buck->length(); j++) {
 305       target.add(*((*buck)[j]._id), new contents(*((*buck)[j]._data)));
 306     }
 307   }
 308 #ifdef EXTREME_CHECKING
 309   if (!target.verify())
 310     deadly_error(class_name(), func, "target state did not verify.");
 311 #endif
 312   #undef class_name
 313 }
 314
 315 template <class key_type, class contents>
 316 void hash_table<key_type, contents>::reset()
 317 {
 318 #ifdef EXTREME_CHECKING
 319   FUNCDEF("reset");
 320   if (!verify()) deadly_error(class_name(), func, "state did not verify.");
 321 #endif
 322   // iterate over the list whacking the content items in the buckets.
 323   for (int i = 0; i < _table->elements(); i++) {
 324     bucket<key_type, contents> *buck = _table->acquire(i);
 325     if (!buck) continue;
 326     for (int j = 0; j < buck->length(); j++) {
 327       basis::WHACK((*buck)[j]._data);  // eliminate the stored data.
 328       basis::WHACK((*buck)[j]._id);  // eliminate the stored key.
 329       buck->zap(j, j);  // remove the element.
 330       j--;  // skip back before whack happened.
 331     }
 332     basis::WHACK(buck);
 333   }
 334 #ifdef EXTREME_CHECKING
 335   if (!verify())
 336     deadly_error(class_name(), func, "state did not verify afterwards.");
 337 #endif
 338 }
 339
 340 template <class key_type, class contents>
 341 bool hash_table<key_type, contents>::verify() const
 342 {
 343   for (int i = 0; i < _table->elements(); i++) {
 344     const bucket<key_type, contents> *buck = _table->borrow(i);
 345     if (!buck) continue;  // that's acceptable.
 346     for (int j = 0; j < buck->length(); j++) {
 347       const hash_wrapper<key_type, contents> &wrap = (*buck)[j];
 348       if (!wrap._data) {
 349 //        program_wide_logger::get().log(a_sprintf("hash table: no data segment at position %d.", j));
 350         return false;
 351       }
 352       if (!wrap._id) {
 353 //        program_wide_logger::get().log(a_sprintf("hash table: no identifier at position %d.", j));
 354         return false;
 355       }
 356     }
 357   }
 358   return true;
 359 }
 360
 361 template <class key_type, class contents>
 362 internal_hash_array<key_type, contents> &hash_table<key_type, contents>
 363     ::table_access() const
 364 { return *_table; }
 365
 366 template <class key_type, class contents>
 367 void hash_table<key_type, contents>::rehash(int estimated_elements)
 368 {
 369 #ifdef EXTREME_CHECKING
 370   FUNCDEF("rehash");
 371   if (!verify()) deadly_error(class_name(), func, "state did not verify.");
 372 #endif
 373   typedef bucket<key_type, contents> buckie;
 374   hash_table<key_type, contents> new_hash(*_hasher, estimated_elements);
 375     // this is the new table that will be used.
 376
 377   // scoot through the existing table so we can move items into the new one.
 378   for (int i = 0; i < _table->elements(); i++) {
 379     buckie *b = _table->borrow(i);  // look at the current element.
 380     if (!b) continue;  // nothing here, keep going.
 381     for (int j = b->length() - 1; j >= 0; j--) {
 382       key_type *k = b->use(j)._id;
 383       contents *c = b->use(j)._data;
 384       new_hash.add(k, c);
 385     }
 386     b->reset();
 387       // clean out any items in the buckets here now that they've moved.
 388   }
 389
 390   // now flip the contents of the new guy into "this".
 391   _table->reset();  // toss previous stuff.
 392   _table->adjust(new_hash._table->elements());
 393   for (int q = 0; q < new_hash._table->elements(); q++)
 394     _table->put(q, new_hash._table->acquire(q));
 395   // reset other data members.
 396   c_estim_elements = new_hash.c_estim_elements;
 397   _last_iter = 0;
 398 #ifdef EXTREME_CHECKING
 399   if (!verify())
 400     deadly_error(class_name(), func, "state did not verify afterwards.");
 401 #endif
 402 }
 403
 404 template <class key_type, class contents>
 405 basis::outcome hash_table<key_type, contents>::add(const key_type &key,
 406     contents *to_store)
 407 { return add(new key_type(key), to_store); }
 408
 409 template <class key_type, class contents>
 410 basis::outcome hash_table<key_type, contents>::add(key_type *key,
 411     contents *to_store, bool check_dupes)
 412 {
 413 #ifdef EXTREME_CHECKING
 414   FUNCDEF("add");
 415   if (!verify()) deadly_error(class_name(), func, "state did not verify.");
 416 #endif
 417   // get a hash value.
 418   basis::un_int hashed = _hasher->hash((const void *)key, sizeof(key_type));
 419   // make the value appropriate for our table.
 420   hashed = hashed % _table->elements();
 421   // see if the key already exists there.
 422   bucket<key_type, contents> *buck = _table->borrow(hashed);
 423   if (!buck) {
 424     // this slot doesn't exist yet.
 425     buck = new bucket<key_type, contents>;
 426     _table->put(hashed, buck);
 427   }
 428   if (!check_dupes) {
 429     // we aren't even going to check for its existence.
 430     *buck += hash_wrapper<key_type, contents>(key, to_store);
 431     return IS_NEW;
 432   }
 433   int indy = buck->find(*key);
 434   if (basis::negative(indy)) {
 435     // that value was not seen yet, so we're adding a new entry.
 436     *buck += hash_wrapper<key_type, contents>(key, to_store);
 437 #ifdef EXTREME_CHECKING
 438     if (!verify())
 439       deadly_error(class_name(), func, "state did not verify afterwards.");
 440 #endif
 441     return IS_NEW;
 442   }
 443   // that key already existed, so we'll re-use its slot with the new data.
 444   basis::WHACK((*buck)[indy]._data);
 445   basis::WHACK(key);  // toss since we're not using.
 446   (*buck)[indy]._data = to_store;
 447 #ifdef EXTREME_CHECKING
 448   if (!verify())
 449     deadly_error(class_name(), func, "state did not verify afterwards.");
 450 #endif
 451   return EXISTING;
 452 }
 453
 454 template <class key_type, class contents>
 455 basis::outcome hash_table<key_type, contents>::fast_dangerous_add
 456     (const key_type &key, contents *to_store)
 457 { return add(new key_type(key), to_store, false); }
 458
 459 template <class key_type, class contents>
 460 bool hash_table<key_type, contents>::find(const key_type &key,
 461     contents * &item_found) const
 462 {
 463 #ifdef EXTREME_CHECKING
 464   FUNCDEF("find");
 465   if (!verify()) deadly_error(class_name(), func, "state did not verify.");
 466 #endif
 467   item_found = NIL;
 468   // get a hash value.
 469   basis::un_int hashed = _hasher->hash((const void *)&key, sizeof(key));
 470   // make the value appropriate for our table.
 471   hashed = hashed % _table->elements();
 472   // see if the key exists in the bucket.
 473   bucket<key_type, contents> *buck = _table->borrow(hashed);
 474   if (!buck) return false;
 475   int indy = buck->find(key);
 476   if (basis::negative(indy)) return false;  // not there.
 477   // was there, so retrieve the data.
 478   item_found = (*buck)[indy]._data;
 479   return true;
 480 }
 481
 482 template <class key_type, class contents>
 483 contents *hash_table<key_type, contents>::acquire(const key_type &key)
 484 {
 485 #ifdef EXTREME_CHECKING
 486   FUNCDEF("acquire");
 487   if (!verify()) deadly_error(class_name(), func, "state did not verify.");
 488 #endif
 489   // get a hash value.
 490   basis::un_int hashed = _hasher->hash((const void *)&key, sizeof(key));
 491   // make the value appropriate for our table.
 492   hashed = hashed % _table->elements();
 493   // see if the key exists in the bucket.
 494   bucket<key_type, contents> *buck = _table->borrow(hashed);
 495   if (!buck) return NIL;
 496   int indy = buck->find(key);
 497   if (basis::negative(indy)) return NIL;  // nope, not there.
 498   contents *to_return = (*buck)[indy]._data;
 499   basis::WHACK((*buck)[indy]._id);  // clean the id.
 500   buck->zap(indy, indy);  // toss the storage blob for the item.
 501 #ifdef EXTREME_CHECKING
 502   if (!verify())
 503     deadly_error(class_name(), func, "state did not verify afterwards.");
 504 #endif
 505   return to_return;
 506 }
 507
 508 template <class key_type, class contents>
 509 bool hash_table<key_type, contents>::zap(const key_type &key)
 510 {
 511 #ifdef EXTREME_CHECKING
 512   FUNCDEF("zap");
 513   if (!verify()) deadly_error(class_name(), func, "state did not verify.");
 514 #endif
 515   // get a hash value.
 516   basis::un_int hashed = _hasher->hash((const void *)&key, sizeof(key));
 517   // make the value appropriate for our table.
 518   hashed = hashed % _table->elements();
 519   // see if the key exists in the bucket.
 520   bucket<key_type, contents> *buck = _table->borrow(hashed);
 521   if (!buck) return false;
 522   int indy = buck->find(key);
 523   if (basis::negative(indy)) {
 524     // nope, not there.
 525     return false;
 526   }
 527   basis::WHACK((*buck)[indy]._data);  // delete the data held.
 528   basis::WHACK((*buck)[indy]._id);  // delete the data held.
 529   buck->zap(indy, indy);  // toss the storage blob for the item.
 530   if (!buck->length()) {
 531     // clean up this bucket now.
 532     buck = _table->acquire(hashed);
 533     basis::WHACK(buck);
 534   }
 535 #ifdef EXTREME_CHECKING
 536   if (!verify())
 537     deadly_error(class_name(), func, "state did not verify afterwards.");
 538 #endif
 539   return true;
 540 }
 541
 542 template <class key_type, class contents>
 543 void hash_table<key_type, contents>::apply(apply_function *to_apply,
 544     void *data_link)
 545 {
 546 #ifdef EXTREME_CHECKING
 547   FUNCDEF("apply");
 548   if (!verify()) deadly_error(class_name(), func, "state did not verify.");
 549 #endif
 550   typedef bucket<key_type, contents> buckie;
 551   int bucks_seen = 0;
 552   int posn = _last_iter;  // start at the same place we left.
 553   while (bucks_seen++ < _table->elements()) {
 554     if ( (posn < 0) || (posn >= _table->elements()) )
 555       posn = 0;
 556     buckie *b = _table->borrow(posn);
 557     _last_iter = posn++;
 558       // record where the iteration last touched and increment next position.
 559       // we must do this before we check if the bucket exists or we'll rotate
 560       // on this same place forever.
 561     if (!b) continue;  // nothing here, keep going.
 562     for (int j = 0; j < b->length(); j++) {
 563       contents *c = b->use(j)._data;
 564       if (!c) {
 565 #ifdef EXTREME_CHECKING
 566         deadly_error("hash_table", "apply", "logic error--missing pointer");
 567 #endif
 568         continue;
 569       }
 570       if (!to_apply(*b->use(j)._id, *c, data_link)) return;
 571     }
 572   }
 573 }
 574
 575 template <class key_type, class contents>
 576 int hash_table<key_type, contents>::elements() const
 577 {
 578 #ifdef EXTREME_CHECKING
 579   FUNCDEF("elements");
 580   if (!verify()) deadly_error(class_name(), func, "state did not verify.");
 581 #endif
 582   typedef bucket<key_type, contents> buckie;
 583   int to_return = 0;
 584   for (int i = 0; i < _table->elements(); i++) {
 585     bucket<key_type, contents> *buck = _table->borrow(i);
 586     if (!buck) continue;  // nothing to count.
 587     to_return += buck->length();
 588   }
 589   return to_return;
 590 }
 591
 592 #undef static_class_name
 593
 594 } //namespace.
 595
 596 #endif // outer guard.
 597