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