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   if (_keys_in_use.member(random_id)) return common::EXISTING;
 251   ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), expected.value(),
 252       "add should give proper outcome based on expectation");
 253   if (_keys_in_use.member(random_id))
 254     return true;  // already was there so we replaced.
 255   _keys_in_use.add(random_id);
 256   return true;
 257 }
 258
 259 //////////////
 260
 261 hash_table<int, data_shuttle> *_hang_on = NIL;
 262   // must be set before calling the apply method.
 263
 264 #undef UNIT_BASE_THIS_OBJECT
 265 #define UNIT_BASE_THIS_OBJECT (*dynamic_cast<unit_base *>(application_shell::single_instance()))
 266
 267 bool test_hash_table::equivalence_applier(const int &key, data_shuttle &item, void *dlink)
 268 {
 269   FUNCDEF("equivalence_applier");
 270   ASSERT_NON_NULL(dlink, "should have been given name");
 271   if (!dlink) return false;  // fail.
 272   astring test_name = (char *)dlink;
 273
 274 //application_shell::single_instance()->log(astring("after name check"));
 275
 276   data_shuttle *found = _hang_on->find(key);
 277   ASSERT_NON_NULL(found, test_name + ": should find equivalent entry in second list");
 278   if (!found) return false;  // bail or we'll crash.
 279
 280 //application_shell::single_instance()->log(astring("after finding"));
 281
 282   ASSERT_EQUAL(item.food_bar, found->food_bar, test_name + ": food_bar should not differ");
 283   ASSERT_EQUAL(item.snacky_string, found->snacky_string, test_name + ": snacky_string should not differ");
 284   ASSERT_EQUAL(item.hungry, found->hungry, test_name + ": hungry should not differ");
 285   return true;
 286 }
 287
 288 #undef UNIT_BASE_THIS_OBJECT
 289 #define UNIT_BASE_THIS_OBJECT (*this)
 290
 291 //////////////
 292
 293 bool test_hash_table::test_rehash()
 294 {
 295   FUNCDEF("test_rehash");
 296   _hang_on = &_the_table;  // must happen first.
 297
 298   // we don't want to rehash too often; it is expensive.
 299   int maybe = randomizer().inclusive(1, 50);
 300   if (maybe < 32) return true;  // not this time.
 301
 302   _hits[REHASH - FIRST_TEST]++;
 303
 304   hash_table<int, data_shuttle> table_copy(rotating_byte_hasher(),
 305       _the_table.estimated_elements());
 306
 307 //log("copying table...");
 308   copy_hash_table(table_copy, _the_table);
 309     // make a copy of the table.
 310
 311 //log("rehashing table...");
 312   _the_table.rehash(randomizer().inclusive(1, 20));
 313 //hmmm: need test of non-existent dehash function that reduces max_bits.
 314
 315 //log("comparing table...");
 316   table_copy.apply(equivalence_applier, (void*)func);
 317 //log("done copy and compare.");
 318
 319   return true;
 320 }
 321
 322 bool test_hash_table::test_copy()
 323 {
 324   FUNCDEF("test_copy");
 325   _hang_on = &_the_table;  // must happen first.
 326
 327   // we don't want to copy too often.  it's a heavy operation.
 328   int maybe = randomizer().inclusive(1, 50);
 329   if (maybe > 16) return true;  // not this time.
 330
 331   _hits[COPY - FIRST_TEST]++;
 332
 333   hash_table<int, data_shuttle> table_copy(rotating_byte_hasher(), MAX_ELEMENTS);
 334
 335 //log("copying table...");
 336   copy_hash_table(table_copy, _the_table);
 337     // make a copy of the table.
 338
 339 //log("comparing table...");
 340   table_copy.apply(equivalence_applier, (void*)func);
 341 //log("done copy and compare.");
 342
 343   return true;
 344 }
 345
 346 //////////////
 347
 348 bool test_hash_table::test_add_add()
 349 {
 350   FUNCDEF("test_add_add");
 351   _hits[ADD_ADD - FIRST_TEST]++;
 352   int random_id = unused_random_id();
 353   data_shuttle *to_add = new data_shuttle;
 354   to_add->snacky_string = string_manipulation::make_random_name();
 355   to_add->food_bar = random_id;
 356   ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), common::IS_NEW,
 357       "new addition should be seen as such");
 358   // add the new key if it's really new.
 359   _keys_in_use.add(random_id);
 360
 361   // second add on same id.
 362   data_shuttle *next_add = new data_shuttle;
 363   next_add->snacky_string = string_manipulation::make_random_name();
 364   next_add->food_bar = random_id;
 365   ASSERT_EQUAL(_the_table.add(random_id, next_add).value(), our_hash::EXISTING,
 366       "second add should not say first failed");
 367
 368   return true;
 369 }
 370
 371 bool test_hash_table::test_zap()
 372 {
 373   FUNCDEF("test_zap");
 374   int maybe = randomizer().inclusive(1, 1000);
 375   if (maybe > 50) return true;
 376   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 377   _hits[ZAP - FIRST_TEST]++;
 378   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 379   int dead_key = _keys_in_use[rand_indy];
 380   _keys_in_use.remove(dead_key);  // remove the record of that key.
 381   ASSERT_TRUE(_the_table.zap(dead_key), "key should be present in table");
 382   return true;
 383 }
 384
 385 bool test_hash_table::test_add_zap()
 386 {
 387   FUNCDEF("test_add_zap");
 388   // add.
 389   _hits[ADD_ZAP - FIRST_TEST]++;
 390   int random_id = unused_random_id();
 391   data_shuttle *to_add = new data_shuttle;
 392   to_add->snacky_string = string_manipulation::make_random_name();
 393   to_add->food_bar = random_id;
 394   ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), common::IS_NEW,
 395       "putting new item in should be seen as new");
 396   // zap.
 397   ASSERT_TRUE(_the_table.zap(random_id), "key should be present after add");
 398   return true;
 399 }
 400
 401 bool test_hash_table::test_zap_add()
 402 {
 403   FUNCDEF("test_zap_add");
 404   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 405   _hits[ZAP_ADD - FIRST_TEST]++;
 406   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 407   // in the end, the key list state won't be changed unless the test fails.
 408   int dead_key = _keys_in_use[rand_indy];
 409   ASSERT_TRUE(_the_table.zap(dead_key), "key should be there when we look");
 410
 411   data_shuttle *to_add = new data_shuttle;
 412   to_add->snacky_string = string_manipulation::make_random_name();
 413   to_add->food_bar = dead_key;
 414   outcome ret = _the_table.add(dead_key, to_add);
 415   ASSERT_EQUAL(ret.value(), our_hash::IS_NEW, "key should not be present already");
 416   return true;
 417 }
 418
 419 bool test_hash_table::test_find()
 420 {
 421   FUNCDEF("test_find");
 422   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 423   _hits[FIND - FIRST_TEST]++;
 424   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 425   int find_key = _keys_in_use[rand_indy];
 426   data_shuttle *found = NIL;
 427   ASSERT_TRUE(_the_table.find(find_key, found), "key should be there as expected");
 428   ASSERT_NON_NULL(found, "contents should not be NIL");
 429   ASSERT_EQUAL(found->food_bar, find_key, "stored key should be same as real key");
 430   ASSERT_TRUE(found->snacky_string.length(), "stored string should have length");
 431   return true;
 432 }
 433
 434 bool test_hash_table::test_acquire()
 435 {
 436   FUNCDEF("test_acquire");
 437   int maybe = randomizer().inclusive(1, 1000);
 438   if (maybe > 150) return true;
 439   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 440   _hits[ACQUIRE - FIRST_TEST]++;
 441   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 442   int find_key = _keys_in_use[rand_indy];
 443   _keys_in_use.remove(find_key);  // remove the record of that key.
 444   data_shuttle *found = _the_table.acquire(find_key);
 445   ASSERT_NON_NULL(found, "key should be present when expected");
 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 not have zero length");
 448   WHACK(found);
 449   found = _the_table.acquire(find_key);
 450   ASSERT_NULL(found, "key should not be there after zap");
 451   return true;
 452 }
 453
 454 bool test_hash_table::test_find_zap_add()
 455 {
 456   FUNCDEF("test_find_zap_add");
 457   // find.
 458   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 459   _hits[FIND_ZAP_ADD - FIRST_TEST]++;
 460   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 461   // this is another key list invariant function, if it works.
 462   int find_key = _keys_in_use[rand_indy];
 463   data_shuttle *found = NIL;
 464   ASSERT_TRUE(_the_table.find(find_key, found), "key should be locateable");
 465   ASSERT_NON_NULL(found, "key should not have NIL contents");
 466   ASSERT_EQUAL(found->food_bar, find_key, "stored key should be equal to real key");
 467   ASSERT_TRUE(found->snacky_string.length(), "stored string should not have zero length");
 468   // zap.
 469   ASSERT_TRUE(_the_table.zap(find_key), "should be able to zap the item we had found");
 470   // add.
 471   data_shuttle *to_add = new data_shuttle;
 472   to_add->snacky_string = string_manipulation::make_random_name();
 473   to_add->food_bar = find_key;
 474   ASSERT_EQUAL(_the_table.add(find_key, to_add).value(), our_hash::IS_NEW,
 475       "the item we zapped should be gone");
 476   return true;
 477 }
 478
 479 bool test_hash_table::test_reset(bool always_run)
 480 {
 481   FUNCDEF("test_reset");
 482   if (!always_run) {
 483     int maybe = randomizer().inclusive(1, 1000);
 484     // this is hardly ever hit, but it loses all contents too often otherwise.
 485     if ( (maybe > 372) || (maybe < 368) ) return true;
 486   }
 487
 488   // we hit the big time; we will reset now.
 489   _hits[RESET - FIRST_TEST]++;
 490   _the_table.reset();
 491   for (int i = _keys_in_use.elements() - 1; i >= 0; i--) {
 492     int dead_key = _keys_in_use[i];
 493     ASSERT_FALSE(_the_table.acquire(dead_key), "after reset, we should not find item");
 494     _keys_in_use.remove(dead_key);
 495   }
 496   return true;
 497 }
 498
 499 //hmmm: implement these tests!
 500
 501 bool test_hash_table::test_acquire_add_zap()
 502 {
 503   _hits[ACQUIRE_ADD_ZAP - FIRST_TEST]++;
 504 return false;
 505 }
 506
 507 bool test_hash_table::test_find_add_find()
 508 {
 509   _hits[FIND_ADD_FIND - FIRST_TEST]++;
 510 return false;
 511 }
 512
 513 bool test_hash_table::test_check_sanity()
 514 {
 515   _hits[CHECK_SANITY - FIRST_TEST]++;
 516 return false;
 517 }
 518
 519 //////////////
 520
 521 HOOPLE_MAIN(test_hash_table, )
 522