nucleus/library/tests_structures/test_hash_table.cpp

   1 /*
   2 *  Name   : test_hash_table
   3 *  Author : Chris Koeritz
   4 *  Purpose:
   5 *    Tests out the hash_table abstract data type.
   6 **
   7 * Copyright (c) 2001-$now By Author.  This program is free software; you can  *
   8 * redistribute it and/or modify it under the terms of the GNU General Public  *
   9 * License as published by the Free Software Foundation; either version 2 of   *
  10 * the License or (at your option) any later version.  This is online at:      *
  11 *     http://www.fsf.org/copyleft/gpl.html                                    *
  12 * Please send any updates to: fred@gruntose.com                               *
  13 */
  14
  15 #include <application/hoople_main.h>
  16 #include <basis/guards.h>
  17 #include <basis/astring.h>
  18 #include <loggers/console_logger.h>
  19 #include <loggers/file_logger.h>
  20 #include <mathematics/chaos.h>
  21 #include <structures/byte_hasher.h>
  22 #include <structures/hash_table.h>
  23 #include <structures/set.h>
  24 #include <structures/static_memory_gremlin.h>
  25 #include <textual/string_manipulation.h>
  26 #include <timely/time_stamp.h>
  27 #include <unit_test/unit_base.h>
  28
  29 using namespace application;
  30 using namespace basis;
  31 using namespace mathematics;
  32 using namespace filesystem;
  33 using namespace loggers;
  34 using namespace structures;
  35 using namespace textual;
  36 using namespace timely;
  37 using namespace unit_test;
  38
  39 //#define DEBUG_HASH_TABLE
  40   // uncomment for noisier run.
  41
  42 const double TEST_DURATION = 0.014 * MINUTE_ms;
  43 //const double TEST_DURATION = 20 * SECOND_ms;
  44
  45 const int MAX_ELEMENTS = 8;
  46   // we start low since we will rehash occasionally.
  47
  48 //////////////
  49
  50 enum test_actions
  51 {
  52         FIRST_TEST = 38,  // place-holder.
  53         ADD = FIRST_TEST,  // adds an item that is probably new.
  54         ADD_ADD,  // adds a probably new item, then adds different item under same key id to test overwriting.
  55         ZAP,  // finds an item we know is in the list and whacks it.
  56         ADD_ZAP,  // adds a new item and immediately finds and zaps it.
  57         ZAP_ADD,  // zaps an item that we know about and then adds a new item with the same identifier.
  58         FIND,  // locates an item in the list which we know should exist.
  59         ACQUIRE,  // grabs an item out of the list (and tosses it).
  60         FIND_ZAP_ADD,  // finds an item we know should exist, zaps it out of the list, then adds a new item with the same id.
  61         ACQUIRE_ADD_ZAP,  // removes an item from the list that we know should be there, adds it back in, and then whacks it.
  62         FIND_ADD_FIND,  // finds item with particular id, adds different item using same id, refinds new item.
  63         RESET,  // tosses all data out of the hash table.  not done very often.
  64         CHECK_SANITY,  // look for any problems or irregularities; print the contents of the list if any are found.
  65         REHASH,  // resizes the hash table.
  66         COPY,  // copies a hash table to another hash table.
  67         LAST_TEST = COPY  // place-holder; must equal test just prior.
  68 };
  69
  70 //////////////
  71
  72 // a simple object that is used as the contents of the hash_table.
  73
  74 class data_shuttle
  75 {
  76 public:
  77   int food_bar;
  78   astring snacky_string;
  79   bool hungry;
  80   byte_array chunk;
  81   chaos chao;
  82
  83   data_shuttle()
  84   : snacky_string(string_manipulation::make_random_name()),
  85     chunk(chao.inclusive(100, 10000)), food_bar(0), hungry(false) {}
  86 };
  87
  88 //////////////
  89
  90 class test_hash_table : virtual public unit_base, virtual public application_shell
  91 {
  92 public:
  93   test_hash_table();
  94
  95   DEFINE_CLASS_NAME("test_hash_table");
  96
  97   int raw_random_id();  //!< returns an unvetted random number.
  98
  99   //! returns an unused (so far) random number.
 100   int unused_random_id();
 101
 102   int execute();
 103     // the main startup for the test.
 104
 105   bool perform_a_test(test_actions test_type);
 106     // carries out the specifics of the "test_type".
 107
 108   bool pick_a_test();
 109     // randomly picks one of the test types and performs it.
 110
 111   static const char *test_name(test_actions test_type);
 112
 113   // these functions each perform one type of test, which their names indicate.
 114   bool test_add();
 115   bool test_add_add();
 116   bool test_zap();
 117   bool test_add_zap();
 118   bool test_zap_add();
 119   bool test_find();
 120   bool test_acquire();
 121   bool test_find_zap_add();
 122   bool test_acquire_add_zap();
 123   bool test_find_add_find();
 124   bool test_reset(bool always_run = false);
 125   bool test_check_sanity();
 126   bool test_copy();
 127   bool test_rehash();
 128
 129   static bool equivalence_applier(const int &key, data_shuttle &item, void *dlink);
 130
 131 private:
 132   int_set _keys_in_use;  // keys that we think are stored in the table.
 133   hash_table<int, data_shuttle> _the_table;  // our table under test.
 134   int _hits[LAST_TEST - FIRST_TEST + 1];  // tracks our testing activities.
 135   int _tested;  // simple counter of number of test calls.
 136 };
 137
 138 //////////////
 139
 140 typedef hash_table<int, data_shuttle> our_hash;  // cleans up somewhat.
 141
 142 //////////////
 143
 144 test_hash_table::test_hash_table()
 145 : application_shell(),
 146   _the_table(rotating_byte_hasher(), MAX_ELEMENTS),
 147   _tested(0)
 148 {
 149   for (int i = FIRST_TEST; i <= LAST_TEST; i++)
 150     _hits[i - FIRST_TEST] = 0;
 151 }
 152
 153 int test_hash_table::raw_random_id()
 154 {
 155   return randomizer().inclusive(-MAXINT32 / 4, MAXINT32 / 4);
 156 }
 157
 158 int test_hash_table::unused_random_id()
 159 {
 160   while (true) {
 161     int checking = raw_random_id();
 162     if (!_keys_in_use.member(checking)) return checking;  // got one.
 163   } // keep going until we find unused id.
 164   return -1;  // this is a failure, but we will never get here.
 165 }
 166
 167 int test_hash_table::execute()
 168 {
 169   time_stamp exit_time((int)TEST_DURATION);
 170   while (time_stamp() < exit_time) {
 171     pick_a_test();
 172   }
 173   test_reset(true);  // force it to run at least once.
 174
 175 #ifdef DEBUG_HASH_TABLE
 176   log(a_sprintf("did %d tests.\n", _tested));
 177   log(astring("Test Activity:"));
 178   for (int i = 0; i < LAST_TEST - FIRST_TEST + 1; i++)
 179     log(astring(astring::SPRINTF, "%d (%s): %d hits", i + FIRST_TEST,
 180         test_name(test_actions(i + FIRST_TEST)), _hits[i]));
 181   log(a_sprintf("note that test %d will seldom be executed.", RESET));
 182 #endif
 183   return final_report();
 184 }
 185
 186 const char *test_hash_table::test_name(test_actions test_type)
 187 {
 188   switch (test_type) {
 189     case ADD: return "ADD";
 190     case ADD_ADD: return "ADD_ADD";
 191     case ZAP: return "ZAP";
 192     case ADD_ZAP: return "ADD_ZAP";
 193     case ZAP_ADD: return "ZAP_ADD";
 194     case FIND: return "FIND";
 195     case ACQUIRE: return "ACQUIRE";
 196     case FIND_ZAP_ADD: return "FIND_ZAP_ADD";
 197     case ACQUIRE_ADD_ZAP: return "ACQUIRE_ADD_ZAP";
 198     case FIND_ADD_FIND: return "FIND_ADD_FIND";
 199     case RESET: return "RESET";
 200     case COPY: return "COPY";
 201     case REHASH: return "REHASH";
 202     case CHECK_SANITY: return "CHECK_SANITY";
 203     default: return "UnknownTest";
 204   }
 205 }
 206
 207 bool test_hash_table::perform_a_test(test_actions test_type)
 208 {
 209   FUNCDEF("perform_a_test");
 210
 211 //  log(astring(test_name(test_type)) + " ");
 212
 213   switch (test_type) {
 214     case ADD: return test_add();
 215     case ADD_ADD: return test_add_add();
 216     case ZAP: return test_zap();
 217     case ADD_ZAP: return test_add_zap();
 218     case ZAP_ADD: return test_zap_add();
 219     case FIND: return test_find();
 220     case ACQUIRE: return test_acquire();
 221     case FIND_ZAP_ADD: return test_find_zap_add();
 222     case ACQUIRE_ADD_ZAP: return test_acquire_add_zap();
 223     case FIND_ADD_FIND: return test_find_add_find();
 224     case RESET: return test_reset();
 225     case COPY: return test_copy();
 226     case REHASH: return test_rehash();
 227     case CHECK_SANITY: return test_check_sanity();
 228     default:
 229       ASSERT_TRUE(false, "should not see any missing cases");
 230       return false;  // never gets here.
 231   }
 232 }
 233
 234 bool test_hash_table::pick_a_test()
 235 {
 236   _tested++;
 237   return perform_a_test(test_actions(randomizer().inclusive(FIRST_TEST,
 238       LAST_TEST)));
 239 }
 240
 241 bool test_hash_table::test_add()
 242 {
 243   FUNCDEF("test_add");
 244   _hits[ADD - FIRST_TEST]++;
 245   int random_id = raw_random_id();
 246   data_shuttle *to_add = new data_shuttle;
 247   to_add->snacky_string = string_manipulation::make_random_name();
 248   to_add->food_bar = random_id;
 249   outcome expected = common::IS_NEW;
 250   // make sure it doesn't exist already.
 251   if (_keys_in_use.member(random_id)) return false;
 252   ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), expected.value(),
 253       "add should give proper outcome based on expectation");
 254   if (_keys_in_use.member(random_id))
 255     return true;  // already was there so we replaced.
 256   _keys_in_use.add(random_id);
 257   return true;
 258 }
 259
 260 //////////////
 261
 262 hash_table<int, data_shuttle> *_hang_on = NIL;
 263   // must be set before calling the apply method.
 264
 265 #undef UNIT_BASE_THIS_OBJECT
 266 #define UNIT_BASE_THIS_OBJECT (*dynamic_cast<unit_base *>(application_shell::single_instance()))
 267
 268 bool test_hash_table::equivalence_applier(const int &key, data_shuttle &item, void *dlink)
 269 {
 270   FUNCDEF("equivalence_applier");
 271   ASSERT_NON_NULL(dlink, "should have been given name");
 272   if (!dlink) return false;  // fail.
 273   astring test_name = (char *)dlink;
 274
 275 //application_shell::single_instance()->log(astring("after name check"));
 276
 277   data_shuttle *found = _hang_on->find(key);
 278   ASSERT_NON_NULL(found, test_name + ": should find equivalent entry in second list");
 279   if (!found) return false;  // bail or we'll crash.
 280
 281 //application_shell::single_instance()->log(astring("after finding"));
 282
 283   ASSERT_EQUAL(item.food_bar, found->food_bar, test_name + ": food_bar should not differ");
 284   ASSERT_EQUAL(item.snacky_string, found->snacky_string, test_name + ": snacky_string should not differ");
 285   ASSERT_EQUAL(item.hungry, found->hungry, test_name + ": hungry should not differ");
 286   return true;
 287 }
 288
 289 #undef UNIT_BASE_THIS_OBJECT
 290 #define UNIT_BASE_THIS_OBJECT (*this)
 291
 292 //////////////
 293
 294 bool test_hash_table::test_rehash()
 295 {
 296   FUNCDEF("test_rehash");
 297   _hang_on = &_the_table;  // must happen first.
 298
 299   // we don't want to rehash too often; it is expensive.
 300   int maybe = randomizer().inclusive(1, 50);
 301   if (maybe < 32) return true;  // not this time.
 302
 303   _hits[REHASH - FIRST_TEST]++;
 304
 305   hash_table<int, data_shuttle> table_copy(rotating_byte_hasher(),
 306       _the_table.estimated_elements());
 307
 308 //log("copying table...");
 309   copy_hash_table(table_copy, _the_table);
 310     // make a copy of the table.
 311
 312 //log("rehashing table...");
 313   _the_table.rehash(randomizer().inclusive(1, 20));
 314 //hmmm: need test of non-existent dehash function that reduces max_bits.
 315
 316 //log("comparing table...");
 317   table_copy.apply(equivalence_applier, (void*)func);
 318 //log("done copy and compare.");
 319
 320   return true;
 321 }
 322
 323 bool test_hash_table::test_copy()
 324 {
 325   FUNCDEF("test_copy");
 326   _hang_on = &_the_table;  // must happen first.
 327
 328   // we don't want to copy too often.  it's a heavy operation.
 329   int maybe = randomizer().inclusive(1, 50);
 330   if (maybe > 16) return true;  // not this time.
 331
 332   _hits[COPY - FIRST_TEST]++;
 333
 334   hash_table<int, data_shuttle> table_copy(rotating_byte_hasher(), MAX_ELEMENTS);
 335
 336 //log("copying table...");
 337   copy_hash_table(table_copy, _the_table);
 338     // make a copy of the table.
 339
 340 //log("comparing table...");
 341   table_copy.apply(equivalence_applier, (void*)func);
 342 //log("done copy and compare.");
 343
 344   return true;
 345 }
 346
 347 //////////////
 348
 349 bool test_hash_table::test_add_add()
 350 {
 351   FUNCDEF("test_add_add");
 352   _hits[ADD_ADD - FIRST_TEST]++;
 353   int random_id = unused_random_id();
 354   data_shuttle *to_add = new data_shuttle;
 355   to_add->snacky_string = string_manipulation::make_random_name();
 356   to_add->food_bar = random_id;
 357   ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), common::IS_NEW,
 358       "new addition should be seen as such");
 359   // add the new key if it's really new.
 360   _keys_in_use.add(random_id);
 361
 362   // second add on same id.
 363   data_shuttle *next_add = new data_shuttle;
 364   next_add->snacky_string = string_manipulation::make_random_name();
 365   next_add->food_bar = random_id;
 366   ASSERT_EQUAL(_the_table.add(random_id, next_add).value(), our_hash::EXISTING,
 367       "second add should not say first failed");
 368
 369   return true;
 370 }
 371
 372 bool test_hash_table::test_zap()
 373 {
 374   FUNCDEF("test_zap");
 375   int maybe = randomizer().inclusive(1, 1000);
 376   if (maybe > 50) return true;
 377   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 378   _hits[ZAP - FIRST_TEST]++;
 379   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 380   int dead_key = _keys_in_use[rand_indy];
 381   _keys_in_use.remove(dead_key);  // remove the record of that key.
 382   ASSERT_TRUE(_the_table.zap(dead_key), "key should be present in table");
 383   return true;
 384 }
 385
 386 bool test_hash_table::test_add_zap()
 387 {
 388   FUNCDEF("test_add_zap");
 389   // add.
 390   _hits[ADD_ZAP - FIRST_TEST]++;
 391   int random_id = unused_random_id();
 392   data_shuttle *to_add = new data_shuttle;
 393   to_add->snacky_string = string_manipulation::make_random_name();
 394   to_add->food_bar = random_id;
 395   ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), common::IS_NEW,
 396       "putting new item in should be seen as new");
 397   // zap.
 398   ASSERT_TRUE(_the_table.zap(random_id), "key should be present after add");
 399   return true;
 400 }
 401
 402 bool test_hash_table::test_zap_add()
 403 {
 404   FUNCDEF("test_zap_add");
 405   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 406   _hits[ZAP_ADD - FIRST_TEST]++;
 407   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 408   // in the end, the key list state won't be changed unless the test fails.
 409   int dead_key = _keys_in_use[rand_indy];
 410   ASSERT_TRUE(_the_table.zap(dead_key), "key should be there when we look");
 411
 412   data_shuttle *to_add = new data_shuttle;
 413   to_add->snacky_string = string_manipulation::make_random_name();
 414   to_add->food_bar = dead_key;
 415   outcome ret = _the_table.add(dead_key, to_add);
 416   ASSERT_EQUAL(ret.value(), our_hash::IS_NEW, "key should not be present already");
 417   return true;
 418 }
 419
 420 bool test_hash_table::test_find()
 421 {
 422   FUNCDEF("test_find");
 423   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 424   _hits[FIND - FIRST_TEST]++;
 425   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 426   int find_key = _keys_in_use[rand_indy];
 427   data_shuttle *found = NIL;
 428   ASSERT_TRUE(_the_table.find(find_key, found), "key should be there as expected");
 429   ASSERT_NON_NULL(found, "contents should not be NIL");
 430   ASSERT_EQUAL(found->food_bar, find_key, "stored key should be same as real key");
 431   ASSERT_TRUE(found->snacky_string.length(), "stored string should have length");
 432   return true;
 433 }
 434
 435 bool test_hash_table::test_acquire()
 436 {
 437   FUNCDEF("test_acquire");
 438   int maybe = randomizer().inclusive(1, 1000);
 439   if (maybe > 150) return true;
 440   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 441   _hits[ACQUIRE - FIRST_TEST]++;
 442   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 443   int find_key = _keys_in_use[rand_indy];
 444   _keys_in_use.remove(find_key);  // remove the record of that key.
 445   data_shuttle *found = _the_table.acquire(find_key);
 446   ASSERT_NON_NULL(found, "key should be present when expected");
 447   ASSERT_EQUAL(found->food_bar, find_key, "stored key should be same as real key");
 448   ASSERT_TRUE(found->snacky_string.length(), "stored string should not have zero length");
 449   WHACK(found);
 450   found = _the_table.acquire(find_key);
 451   ASSERT_NULL(found, "key should not be there after zap");
 452   return true;
 453 }
 454
 455 bool test_hash_table::test_find_zap_add()
 456 {
 457   FUNCDEF("test_find_zap_add");
 458   // find.
 459   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 460   _hits[FIND_ZAP_ADD - FIRST_TEST]++;
 461   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 462   // this is another key list invariant function, if it works.
 463   int find_key = _keys_in_use[rand_indy];
 464   data_shuttle *found = NIL;
 465   ASSERT_TRUE(_the_table.find(find_key, found), "key should be locateable");
 466   ASSERT_NON_NULL(found, "key should not have NIL contents");
 467   ASSERT_EQUAL(found->food_bar, find_key, "stored key should be equal to real key");
 468   ASSERT_TRUE(found->snacky_string.length(), "stored string should not have zero length");
 469   // zap.
 470   ASSERT_TRUE(_the_table.zap(find_key), "should be able to zap the item we had found");
 471   // add.
 472   data_shuttle *to_add = new data_shuttle;
 473   to_add->snacky_string = string_manipulation::make_random_name();
 474   to_add->food_bar = find_key;
 475   ASSERT_EQUAL(_the_table.add(find_key, to_add).value(), our_hash::IS_NEW,
 476       "the item we zapped should be gone");
 477   return true;
 478 }
 479
 480 bool test_hash_table::test_reset(bool always_run)
 481 {
 482   FUNCDEF("test_reset");
 483   if (!always_run) {
 484     int maybe = randomizer().inclusive(1, 1000);
 485     // this is hardly ever hit, but it loses all contents too often otherwise.
 486     if ( (maybe > 372) || (maybe < 368) ) return true;
 487   }
 488
 489   // we hit the big time; we will reset now.
 490   _hits[RESET - FIRST_TEST]++;
 491   _the_table.reset();
 492   for (int i = _keys_in_use.elements() - 1; i >= 0; i--) {
 493     int dead_key = _keys_in_use[i];
 494     ASSERT_FALSE(_the_table.acquire(dead_key), "after reset, we should not find item");
 495     _keys_in_use.remove(dead_key);
 496   }
 497   return true;
 498 }
 499
 500 //hmmm: implement these tests!
 501
 502 bool test_hash_table::test_acquire_add_zap()
 503 {
 504   _hits[ACQUIRE_ADD_ZAP - FIRST_TEST]++;
 505 return false;
 506 }
 507
 508 bool test_hash_table::test_find_add_find()
 509 {
 510   _hits[FIND_ADD_FIND - FIRST_TEST]++;
 511 return false;
 512 }
 513
 514 bool test_hash_table::test_check_sanity()
 515 {
 516   _hits[CHECK_SANITY - FIRST_TEST]++;
 517 return false;
 518 }
 519
 520 //////////////
 521
 522 HOOPLE_MAIN(test_hash_table, )
 523
 524