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