core/library/tests_structures/test_int_hash.cpp

   1 /*
   2 *  Name   : test_int_hash
   3 *  Author : Chris Koeritz
   4 *  Purpose:
   5 *    Tests out hash_table specialization for integers.
   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/int_hash.h>
  22 #include <structures/static_memory_gremlin.h>
  23 #include <textual/string_manipulation.h>
  24 #include <timely/time_stamp.h>
  25 #include <unit_test/unit_base.h>
  26
  27 using namespace application;
  28 using namespace basis;
  29 using namespace mathematics;
  30 using namespace filesystem;
  31 using namespace loggers;
  32 using namespace structures;
  33 using namespace textual;
  34 using namespace timely;
  35 using namespace unit_test;
  36
  37 //#define DEBUG_INT_HASH
  38   // uncomment for noisier run.
  39
  40 #define EXTREME_CHECKING
  41   // causes extra checks in the library code.
  42
  43 const double TEST_DURATION = 0.5 * SECOND_ms;
  44
  45 const int MAX_DEFAULT_BITS = 2;
  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_int_hash : public virtual unit_base, virtual public application_shell
 111 {
 112 public:
 113   test_int_hash();
 114
 115   int execute();
 116     //!< the main startup for the test.
 117
 118   bool perform_a_test(test_actions test_type);
 119     //!< carries out the specifics of the "test_type".
 120
 121   bool pick_a_test();
 122     //!< randomly picks one of the test types and performs it.
 123
 124   DEFINE_CLASS_NAME("test_int_hash");
 125
 126   static bool equivalence_applier(const int &key, data_shuttle &item, void *dlink);
 127
 128   static const char *test_name(test_actions test_type);
 129
 130   int raw_random_id();  //!< returns an unvetted random number.
 131   int unused_random_id();  //!< returns an unused (so far) random number.
 132
 133   // these functions each perform one type of test, which their names indicate.
 134   bool test_add();
 135   bool test_add_add();
 136   bool test_zap();
 137   bool test_add_zap();
 138   bool test_zap_add();
 139   bool test_find();
 140   bool test_acquire();
 141   bool test_find_zap_add();
 142   bool test_acquire_add_zap();
 143   bool test_find_add_find();
 144   bool test_reset(bool always_do_it = false);
 145   bool test_check_sanity();
 146   bool test_copy();
 147   bool test_rehash();
 148
 149 private:
 150   int_set _keys_in_use;  // keys that we think are stored in the table.
 151   int_hash<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 int_hash<data_shuttle> our_hash;  // cleans up somewhat.
 159
 160 //////////////
 161
 162 test_int_hash::test_int_hash()
 163 : application_shell(),
 164   _the_table(MAX_DEFAULT_BITS),
 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_int_hash::execute()
 172 {
 173   time_stamp exit_time((int)TEST_DURATION);
 174 //log(astring("before starting tests"));
 175   while (time_stamp() < exit_time) {
 176     pick_a_test();
 177   }
 178   test_reset(true);  // make sure we do this at least once.
 179 #ifdef DEBUG_INT_HASH
 180   log(a_sprintf("did %d tests.\n", _tested));
 181   log(astring("Test Activity:"));
 182   for (int i = 0; i < LAST_TEST - FIRST_TEST + 1; i++)
 183     log(astring(astring::SPRINTF, "%d (%s): %d hits", i + FIRST_TEST,
 184         test_name(test_actions(i + FIRST_TEST)), _hits[i]));
 185   log(a_sprintf("note that test %d will seldom be executed.", RESET));
 186 #endif
 187   return final_report();
 188 }
 189
 190 const char *test_int_hash::test_name(test_actions test_type)
 191 {
 192   switch (test_type) {
 193     case ADD: return "ADD";
 194     case ADD_ADD: return "ADD_ADD";
 195     case ZAP: return "ZAP";
 196     case ADD_ZAP: return "ADD_ZAP";
 197     case ZAP_ADD: return "ZAP_ADD";
 198     case FIND: return "FIND";
 199     case ACQUIRE: return "ACQUIRE";
 200     case FIND_ZAP_ADD: return "FIND_ZAP_ADD";
 201     case ACQUIRE_ADD_ZAP: return "ACQUIRE_ADD_ZAP";
 202     case FIND_ADD_FIND: return "FIND_ADD_FIND";
 203     case RESET: return "RESET";
 204     case COPY: return "COPY";
 205     case REHASH: return "REHASH";
 206     case CHECK_SANITY: return "CHECK_SANITY";
 207     default: return "UnknownTest";
 208   }
 209 }
 210
 211 bool test_int_hash::perform_a_test(test_actions test_type)
 212 {
 213   FUNCDEF("perform_a_test");
 214
 215 //  log(astring(test_name(test_type)) + " ");
 216
 217   switch (test_type) {
 218     case ADD: return test_add();
 219     case ADD_ADD: return test_add_add();
 220     case ZAP: return test_zap();
 221     case ADD_ZAP: return test_add_zap();
 222     case ZAP_ADD: return test_zap_add();
 223     case FIND: return test_find();
 224     case ACQUIRE: return test_acquire();
 225     case FIND_ZAP_ADD: return test_find_zap_add();
 226     case ACQUIRE_ADD_ZAP: return test_acquire_add_zap();
 227     case FIND_ADD_FIND: return test_find_add_find();
 228     case RESET: return test_reset();
 229     case COPY: return test_copy();
 230     case REHASH: return test_rehash();
 231     case CHECK_SANITY: return test_check_sanity();
 232     default:
 233       ASSERT_TRUE(false, "there should be no missing case seen!");
 234       return false;  // never gets here.
 235   }
 236 }
 237
 238 bool test_int_hash::pick_a_test()
 239 {
 240   _tested++;
 241   return perform_a_test(test_actions(randomizer().inclusive(FIRST_TEST, LAST_TEST)));
 242 }
 243
 244 int test_int_hash::raw_random_id()
 245 {
 246   return randomizer().inclusive(-MAXINT32 / 4, MAXINT32 / 4);
 247 }
 248
 249 int test_int_hash::unused_random_id()
 250 {
 251   while (true) {
 252     int checking = raw_random_id();
 253     if (!_keys_in_use.member(checking)) return checking;  // got one.
 254   } // keep going until we find unused id.
 255 }
 256
 257 bool test_int_hash::test_add()
 258 {
 259   FUNCDEF("test_add");
 260   _hits[ADD - FIRST_TEST]++;
 261   int random_id = raw_random_id();
 262   data_shuttle *to_add = new data_shuttle;
 263   to_add->snacky_string = string_manipulation::make_random_name();
 264   to_add->food_bar = random_id;
 265   outcome wanting = common::IS_NEW;
 266   if (_keys_in_use.member(random_id)) wanting = common::EXISTING;
 267   ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), wanting.value(),
 268       "adding key should work with right expectation");
 269   if (_keys_in_use.member(random_id))
 270     return true;  // already was there so we replaced.
 271   _keys_in_use.add(random_id);
 272   return true;
 273 }
 274
 275 //////////////
 276
 277 #undef UNIT_BASE_THIS_OBJECT
 278 #define UNIT_BASE_THIS_OBJECT (*dynamic_cast<unit_base *>(application_shell::single_instance()))
 279
 280 int_hash<data_shuttle> *_hang_on = NIL;
 281   // must be set before calling the apply method.
 282
 283 bool test_int_hash::equivalence_applier(const int &key, data_shuttle &item, void *dlink)
 284 {
 285   FUNCDEF("equivalence_applier");
 286   ASSERT_TRUE(dlink, "should have been given name");
 287   if (!dlink) return false;  // fail.
 288   astring test_name = (char *)dlink;
 289
 290 //application_shell::single_instance()->log(astring("after name check"));
 291
 292   data_shuttle *found = _hang_on->find(key);
 293   ASSERT_TRUE(found, test_name + ": should find equivalent entry in second list");
 294   if (!found) return false;  // bail or we'll crash.
 295
 296 //application_shell::single_instance()->log(astring("after finding"));
 297
 298   ASSERT_EQUAL(item.food_bar, found->food_bar, test_name + ": food_bar should not differ");
 299   ASSERT_EQUAL(item.snacky_string, found->snacky_string, test_name + ": snacky_string should not differ");
 300   ASSERT_EQUAL(item.hungry, found->hungry, test_name + ": hungry should not differ");
 301   return true;
 302 }
 303
 304 #undef UNIT_BASE_THIS_OBJECT
 305 #define UNIT_BASE_THIS_OBJECT (*this)
 306
 307 //////////////
 308
 309 bool test_int_hash::test_rehash()
 310 {
 311   FUNCDEF("test_rehash");
 312   // we don't want to rehash too often; it is expensive.
 313 //  int maybe = randomizer().inclusive(1, 50);
 314 //  if (maybe < 32) return true;  // not this time.
 315
 316   _hang_on = &_the_table;  // must do this first.
 317
 318   _hits[REHASH - FIRST_TEST]++;
 319
 320   int_hash<data_shuttle> table_copy(_the_table.estimated_elements());
 321
 322   _the_table.apply(equivalence_applier, (void *)func);
 323   astring second_test_name(func);
 324   second_test_name += " try 2";
 325   table_copy.apply(equivalence_applier, (void *)second_test_name.s());
 326
 327   if (!_the_table.elements()) return true;  // nothing to do right now for comparisons.
 328
 329 //log("copying table...");
 330   copy_hash_table(table_copy, _the_table);
 331     // make a copy of the table.
 332
 333   ASSERT_INEQUAL(0, table_copy.elements(), "copy shouldn't have unexpected absence of contents");
 334
 335 //log("rehashing table...");
 336   _the_table.rehash(randomizer().inclusive(1, 20));
 337
 338 //hmmm: need test of dehash function that reduces elements estimated.
 339
 340 //log("comparing table...");
 341   astring third_test_name(func);
 342   third_test_name += " try 3";
 343   table_copy.apply(equivalence_applier, (void *)third_test_name.s());
 344 //log("done copy and compare.");
 345
 346   return true;
 347 }
 348
 349 bool test_int_hash::test_copy()
 350 {
 351   FUNCDEF("test_copy");
 352   // we don't want to copy too often.  it's a heavy operation.
 353 //  int maybe = randomizer().inclusive(1, 50);
 354 //  if (maybe > 16) return true;  // not this time.
 355
 356   _hang_on = &_the_table;  // must do this first.
 357
 358   _hits[COPY - FIRST_TEST]++;
 359
 360   int_hash<data_shuttle> table_copy(MAX_DEFAULT_BITS);
 361
 362 //log("copying table...");
 363   copy_hash_table(table_copy, _the_table);
 364     // make a copy of the table.
 365
 366 //log("comparing table...");
 367   table_copy.apply(equivalence_applier, (void *)func);
 368 //log("done copy and compare.");
 369
 370   return true;
 371 }
 372
 373 //////////////
 374
 375 bool test_int_hash::test_add_add()
 376 {
 377   FUNCDEF("test_add_add");
 378   _hits[ADD_ADD - FIRST_TEST]++;
 379   int random_id = unused_random_id();
 380   data_shuttle *to_add = new data_shuttle;
 381   to_add->snacky_string = string_manipulation::make_random_name();
 382   to_add->food_bar = random_id;
 383   ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), common::IS_NEW, "key should be new");
 384   _keys_in_use.add(random_id);
 385
 386   // second add on same id.
 387   data_shuttle *next_add = new data_shuttle;
 388   next_add->snacky_string = string_manipulation::make_random_name();
 389   next_add->food_bar = random_id;
 390   ASSERT_EQUAL(_the_table.add(random_id, next_add).value(), our_hash::EXISTING,
 391       "second add should not say first failed");
 392
 393   return true;
 394 }
 395
 396 bool test_int_hash::test_zap()
 397 {
 398   FUNCDEF("test_zap");
 399   int maybe = randomizer().inclusive(1, 1000);
 400   if (maybe > 500) return true;
 401   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 402   _hits[ZAP - FIRST_TEST]++;
 403   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 404   int dead_key = _keys_in_use[rand_indy];
 405   _keys_in_use.remove(dead_key);  // remove the record of that key.
 406   ASSERT_TRUE(_the_table.zap(dead_key), "zap should work on key");
 407   return true;
 408 }
 409
 410 bool test_int_hash::test_add_zap()
 411 {
 412   FUNCDEF("test_add_zap");
 413   // add.
 414   _hits[ADD_ZAP - FIRST_TEST]++;
 415   int random_id = unused_random_id();
 416   data_shuttle *to_add = new data_shuttle;
 417   to_add->snacky_string = string_manipulation::make_random_name();
 418   to_add->food_bar = random_id;
 419   ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), common::IS_NEW, "key is new before zap");
 420   // zap.
 421   ASSERT_TRUE(_the_table.zap(random_id), "add then zap should remove the key");
 422   return true;
 423 }
 424
 425 bool test_int_hash::test_zap_add()
 426 {
 427   FUNCDEF("test_zap_add");
 428   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 429   _hits[ZAP_ADD - FIRST_TEST]++;
 430   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 431   // in the end, the key list state won't be changed unless the test fails.
 432   int dead_key = _keys_in_use[rand_indy];
 433   ASSERT_TRUE(_the_table.zap(dead_key), "key should be there for zapping");
 434
 435   data_shuttle *to_add = new data_shuttle;
 436   to_add->snacky_string = string_manipulation::make_random_name();
 437   to_add->food_bar = dead_key;
 438   outcome ret = _the_table.add(dead_key, to_add);
 439   ASSERT_EQUAL(ret.value(), our_hash::IS_NEW, "key should not already be present somehow");
 440   return true;
 441 }
 442
 443 int functional_return(int to_pass) {
 444   return to_pass;
 445 }
 446
 447 bool test_int_hash::test_find()
 448 {
 449   FUNCDEF("test_find");
 450   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 451   _hits[FIND - FIRST_TEST]++;
 452   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 453   int find_key = _keys_in_use[rand_indy];
 454   data_shuttle *found = NIL;
 455   ASSERT_TRUE(_the_table.find(functional_return(find_key), found),
 456       "key should be there when we look");
 457   ASSERT_TRUE(_the_table.find(functional_return(find_key)), "find2: key be there when checked");
 458   ASSERT_TRUE(found, "when key is found contents should not be NIL");
 459   ASSERT_EQUAL(found->food_bar, find_key, "stored key should be same as real key");
 460   ASSERT_TRUE(found->snacky_string.length(), "stored string should have some length");
 461   return true;
 462 }
 463
 464 bool test_int_hash::test_acquire()
 465 {
 466   FUNCDEF("test_acquire");
 467   int maybe = randomizer().inclusive(1, 1000);
 468   if (maybe > 750) return true;
 469   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 470   _hits[ACQUIRE - FIRST_TEST]++;
 471   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 472   int find_key = _keys_in_use[rand_indy];
 473   _keys_in_use.remove(find_key);  // remove the record of that key.
 474   data_shuttle *found = _the_table.acquire(find_key);
 475   ASSERT_TRUE(found, "key should be there like clockwork");
 476   ASSERT_EQUAL(found->food_bar, find_key, "stored key should be same as real key");
 477   ASSERT_TRUE(found->snacky_string.length(), "stored string should have some length");
 478   WHACK(found);
 479   found = _the_table.acquire(find_key);
 480   ASSERT_FALSE(found, "key should be missing after zap");
 481   return true;
 482 }
 483
 484 bool test_int_hash::test_find_zap_add()
 485 {
 486   FUNCDEF("test_find_zap_add");
 487   // find.
 488   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 489   _hits[FIND_ZAP_ADD - FIRST_TEST]++;
 490   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 491   // this is another key list invariant function, if it works.
 492   int find_key = _keys_in_use[rand_indy];
 493   data_shuttle *found = NIL;
 494   ASSERT_TRUE(_the_table.find(find_key, found), "key should be there when sought");
 495   ASSERT_TRUE(_the_table.find(find_key), "find2: key should be there for us to find");
 496   ASSERT_TRUE(found, "found key should have non-NIL contents");
 497   ASSERT_EQUAL(found->food_bar, find_key, "stored key should have no differences from real key");
 498   ASSERT_TRUE(found->snacky_string.length(), "stored string should have non-zero length");
 499   // zap.
 500   ASSERT_TRUE(_the_table.zap(find_key), "should be able to zap the item we had found");
 501   // add.
 502   data_shuttle *to_add = new data_shuttle;
 503   to_add->snacky_string = string_manipulation::make_random_name();
 504   to_add->food_bar = find_key;
 505   ASSERT_EQUAL(_the_table.add(find_key, to_add).value(), our_hash::IS_NEW,
 506       "the item we zapped should not still be there");
 507   return true;
 508 }
 509
 510 bool test_int_hash::test_reset(bool always_do_it)
 511 {
 512   FUNCDEF("test_reset");
 513   if (!always_do_it) {
 514     int maybe = randomizer().inclusive(1, 1000);
 515     // this is hardly ever hit, but it loses all contents too often otherwise.
 516     if ( (maybe > 372) || (maybe < 368) ) return true;
 517   }
 518
 519   // we hit the big time; we will reset now.
 520   _hits[RESET - FIRST_TEST]++;
 521   _the_table.reset();
 522   for (int i = _keys_in_use.elements() - 1; i >= 0; i--) {
 523     int dead_key = _keys_in_use[i];
 524     ASSERT_FALSE(_the_table.acquire(dead_key), "after reset, we should not find an item");
 525     _keys_in_use.remove(dead_key);
 526   }
 527   return true;
 528 }
 529
 530 //hmmm: implement these tests!
 531
 532 bool test_int_hash::test_acquire_add_zap()
 533 {
 534   _hits[ACQUIRE_ADD_ZAP - FIRST_TEST]++;
 535 return false;
 536 }
 537
 538 bool test_int_hash::test_find_add_find()
 539 {
 540   _hits[FIND_ADD_FIND - FIRST_TEST]++;
 541 return false;
 542 }
 543
 544 bool test_int_hash::test_check_sanity()
 545 {
 546   _hits[CHECK_SANITY - FIRST_TEST]++;
 547 return false;
 548 }
 549
 550 //////////////
 551
 552 HOOPLE_MAIN(test_int_hash, )
 553