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