nucleus/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)), food_bar(0), hungry(false) {}
 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   return -1;
 256 }
 257
 258 bool test_int_hash::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 wanting = common::IS_NEW;
 267   if (_keys_in_use.member(random_id)) wanting = common::EXISTING;
 268   ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), wanting.value(),
 269       "adding key should work with right 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 #undef UNIT_BASE_THIS_OBJECT
 279 #define UNIT_BASE_THIS_OBJECT (*dynamic_cast<unit_base *>(application_shell::single_instance()))
 280
 281 int_hash<data_shuttle> *_hang_on = NIL;
 282   // must be set before calling the apply method.
 283
 284 bool test_int_hash::equivalence_applier(const int &key, data_shuttle &item, void *dlink)
 285 {
 286   FUNCDEF("equivalence_applier");
 287   ASSERT_TRUE(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_TRUE(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_int_hash::test_rehash()
 311 {
 312   FUNCDEF("test_rehash");
 313   // we don't want to rehash too often; it is expensive.
 314 //  int maybe = randomizer().inclusive(1, 50);
 315 //  if (maybe < 32) return true;  // not this time.
 316
 317   _hang_on = &_the_table;  // must do this first.
 318
 319   _hits[REHASH - FIRST_TEST]++;
 320
 321   int_hash<data_shuttle> table_copy(_the_table.estimated_elements());
 322
 323   _the_table.apply(equivalence_applier, (void *)func);
 324   astring second_test_name(func);
 325   second_test_name += " try 2";
 326   table_copy.apply(equivalence_applier, (void *)second_test_name.s());
 327
 328   if (!_the_table.elements()) return true;  // nothing to do right now for comparisons.
 329
 330 //log("copying table...");
 331   copy_hash_table(table_copy, _the_table);
 332     // make a copy of the table.
 333
 334   ASSERT_INEQUAL(0, table_copy.elements(), "copy shouldn't have unexpected absence of contents");
 335
 336 //log("rehashing table...");
 337   _the_table.rehash(randomizer().inclusive(1, 20));
 338
 339 //hmmm: need test of dehash function that reduces elements estimated.
 340
 341 //log("comparing table...");
 342   astring third_test_name(func);
 343   third_test_name += " try 3";
 344   table_copy.apply(equivalence_applier, (void *)third_test_name.s());
 345 //log("done copy and compare.");
 346
 347   return true;
 348 }
 349
 350 bool test_int_hash::test_copy()
 351 {
 352   FUNCDEF("test_copy");
 353   // we don't want to copy too often.  it's a heavy operation.
 354 //  int maybe = randomizer().inclusive(1, 50);
 355 //  if (maybe > 16) return true;  // not this time.
 356
 357   _hang_on = &_the_table;  // must do this first.
 358
 359   _hits[COPY - FIRST_TEST]++;
 360
 361   int_hash<data_shuttle> table_copy(MAX_DEFAULT_BITS);
 362
 363 //log("copying table...");
 364   copy_hash_table(table_copy, _the_table);
 365     // make a copy of the table.
 366
 367 //log("comparing table...");
 368   table_copy.apply(equivalence_applier, (void *)func);
 369 //log("done copy and compare.");
 370
 371   return true;
 372 }
 373
 374 //////////////
 375
 376 bool test_int_hash::test_add_add()
 377 {
 378   FUNCDEF("test_add_add");
 379   _hits[ADD_ADD - FIRST_TEST]++;
 380   int random_id = unused_random_id();
 381   data_shuttle *to_add = new data_shuttle;
 382   to_add->snacky_string = string_manipulation::make_random_name();
 383   to_add->food_bar = random_id;
 384   ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), common::IS_NEW, "key should be new");
 385   _keys_in_use.add(random_id);
 386
 387   // second add on same id.
 388   data_shuttle *next_add = new data_shuttle;
 389   next_add->snacky_string = string_manipulation::make_random_name();
 390   next_add->food_bar = random_id;
 391   ASSERT_EQUAL(_the_table.add(random_id, next_add).value(), our_hash::EXISTING,
 392       "second add should not say first failed");
 393
 394   return true;
 395 }
 396
 397 bool test_int_hash::test_zap()
 398 {
 399   FUNCDEF("test_zap");
 400   int maybe = randomizer().inclusive(1, 1000);
 401   if (maybe > 500) return true;
 402   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 403   _hits[ZAP - FIRST_TEST]++;
 404   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 405   int dead_key = _keys_in_use[rand_indy];
 406   _keys_in_use.remove(dead_key);  // remove the record of that key.
 407   ASSERT_TRUE(_the_table.zap(dead_key), "zap should work on key");
 408   return true;
 409 }
 410
 411 bool test_int_hash::test_add_zap()
 412 {
 413   FUNCDEF("test_add_zap");
 414   // add.
 415   _hits[ADD_ZAP - FIRST_TEST]++;
 416   int random_id = unused_random_id();
 417   data_shuttle *to_add = new data_shuttle;
 418   to_add->snacky_string = string_manipulation::make_random_name();
 419   to_add->food_bar = random_id;
 420   ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), common::IS_NEW, "key is new before zap");
 421   // zap.
 422   ASSERT_TRUE(_the_table.zap(random_id), "add then zap should remove the key");
 423   return true;
 424 }
 425
 426 bool test_int_hash::test_zap_add()
 427 {
 428   FUNCDEF("test_zap_add");
 429   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 430   _hits[ZAP_ADD - FIRST_TEST]++;
 431   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 432   // in the end, the key list state won't be changed unless the test fails.
 433   int dead_key = _keys_in_use[rand_indy];
 434   ASSERT_TRUE(_the_table.zap(dead_key), "key should be there for zapping");
 435
 436   data_shuttle *to_add = new data_shuttle;
 437   to_add->snacky_string = string_manipulation::make_random_name();
 438   to_add->food_bar = dead_key;
 439   outcome ret = _the_table.add(dead_key, to_add);
 440   ASSERT_EQUAL(ret.value(), our_hash::IS_NEW, "key should not already be present somehow");
 441   return true;
 442 }
 443
 444 int functional_return(int to_pass) {
 445   return to_pass;
 446 }
 447
 448 bool test_int_hash::test_find()
 449 {
 450   FUNCDEF("test_find");
 451   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 452   _hits[FIND - FIRST_TEST]++;
 453   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 454   int find_key = _keys_in_use[rand_indy];
 455   data_shuttle *found = NIL;
 456   ASSERT_TRUE(_the_table.find(functional_return(find_key), found),
 457       "key should be there when we look");
 458   ASSERT_TRUE(_the_table.find(functional_return(find_key)), "find2: key be there when checked");
 459   ASSERT_TRUE(found, "when key is found contents should not be NIL");
 460   ASSERT_EQUAL(found->food_bar, find_key, "stored key should be same as real key");
 461   ASSERT_TRUE(found->snacky_string.length(), "stored string should have some length");
 462   return true;
 463 }
 464
 465 bool test_int_hash::test_acquire()
 466 {
 467   FUNCDEF("test_acquire");
 468   int maybe = randomizer().inclusive(1, 1000);
 469   if (maybe > 750) return true;
 470   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 471   _hits[ACQUIRE - FIRST_TEST]++;
 472   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 473   int find_key = _keys_in_use[rand_indy];
 474   _keys_in_use.remove(find_key);  // remove the record of that key.
 475   data_shuttle *found = _the_table.acquire(find_key);
 476   ASSERT_TRUE(found, "key should be there like clockwork");
 477   ASSERT_EQUAL(found->food_bar, find_key, "stored key should be same as real key");
 478   ASSERT_TRUE(found->snacky_string.length(), "stored string should have some length");
 479   WHACK(found);
 480   found = _the_table.acquire(find_key);
 481   ASSERT_FALSE(found, "key should be missing after zap");
 482   return true;
 483 }
 484
 485 bool test_int_hash::test_find_zap_add()
 486 {
 487   FUNCDEF("test_find_zap_add");
 488   // find.
 489   if (!_keys_in_use.elements()) return false;  // can't do it yet.
 490   _hits[FIND_ZAP_ADD - FIRST_TEST]++;
 491   int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
 492   // this is another key list invariant function, if it works.
 493   int find_key = _keys_in_use[rand_indy];
 494   data_shuttle *found = NIL;
 495   ASSERT_TRUE(_the_table.find(find_key, found), "key should be there when sought");
 496   ASSERT_TRUE(_the_table.find(find_key), "find2: key should be there for us to find");
 497   ASSERT_TRUE(found, "found key should have non-NIL contents");
 498   ASSERT_EQUAL(found->food_bar, find_key, "stored key should have no differences from real key");
 499   ASSERT_TRUE(found->snacky_string.length(), "stored string should have non-zero length");
 500   // zap.
 501   ASSERT_TRUE(_the_table.zap(find_key), "should be able to zap the item we had found");
 502   // add.
 503   data_shuttle *to_add = new data_shuttle;
 504   to_add->snacky_string = string_manipulation::make_random_name();
 505   to_add->food_bar = find_key;
 506   ASSERT_EQUAL(_the_table.add(find_key, to_add).value(), our_hash::IS_NEW,
 507       "the item we zapped should not still be there");
 508   return true;
 509 }
 510
 511 bool test_int_hash::test_reset(bool always_do_it)
 512 {
 513   FUNCDEF("test_reset");
 514   if (!always_do_it) {
 515     int maybe = randomizer().inclusive(1, 1000);
 516     // this is hardly ever hit, but it loses all contents too often otherwise.
 517     if ( (maybe > 372) || (maybe < 368) ) return true;
 518   }
 519
 520   // we hit the big time; we will reset now.
 521   _hits[RESET - FIRST_TEST]++;
 522   _the_table.reset();
 523   for (int i = _keys_in_use.elements() - 1; i >= 0; i--) {
 524     int dead_key = _keys_in_use[i];
 525     ASSERT_FALSE(_the_table.acquire(dead_key), "after reset, we should not find an item");
 526     _keys_in_use.remove(dead_key);
 527   }
 528   return true;
 529 }
 530
 531 //hmmm: implement these tests!
 532
 533 bool test_int_hash::test_acquire_add_zap()
 534 {
 535   _hits[ACQUIRE_ADD_ZAP - FIRST_TEST]++;
 536 return false;
 537 }
 538
 539 bool test_int_hash::test_find_add_find()
 540 {
 541   _hits[FIND_ADD_FIND - FIRST_TEST]++;
 542 return false;
 543 }
 544
 545 bool test_int_hash::test_check_sanity()
 546 {
 547   _hits[CHECK_SANITY - FIRST_TEST]++;
 548 return false;
 549 }
 550
 551 //////////////
 552
 553 HOOPLE_MAIN(test_int_hash, )
 554