--- /dev/null
+/*
+* Name : test_int_hash
+* Author : Chris Koeritz
+* Purpose:
+* Tests out hash_table specialization for integers.
+**
+* Copyright (c) 2001-$now By Author. This program is free software; you can *
+* redistribute it and/or modify it under the terms of the GNU General Public *
+* License as published by the Free Software Foundation; either version 2 of *
+* the License or (at your option) any later version. This is online at: *
+* http://www.fsf.org/copyleft/gpl.html *
+* Please send any updates to: fred@gruntose.com *
+*/
+
+#include <application/hoople_main.h>
+#include <basis/guards.h>
+#include <basis/astring.h>
+#include <loggers/console_logger.h>
+#include <loggers/file_logger.h>
+#include <mathematics/chaos.h>
+#include <structures/int_hash.h>
+#include <structures/static_memory_gremlin.h>
+#include <textual/string_manipulation.h>
+#include <timely/time_stamp.h>
+#include <unit_test/unit_base.h>
+
+using namespace application;
+using namespace basis;
+using namespace mathematics;
+using namespace filesystem;
+using namespace loggers;
+using namespace structures;
+using namespace textual;
+using namespace timely;
+using namespace unit_test;
+
+//#define DEBUG_INT_HASH
+ // uncomment for noisier run.
+
+#define EXTREME_CHECKING
+ // causes extra checks in the library code.
+
+const double TEST_DURATION = 0.5 * SECOND_ms;
+
+const int MAX_DEFAULT_BITS = 2;
+ // we start low since we will rehash occasionally.
+
+//////////////
+
+enum test_actions {
+ FIRST_TEST = 38, // place-holder.
+ ADD = FIRST_TEST,
+ // adds an item that is probably new.
+ ADD_ADD,
+ // adds an item that is probably new, followed by another item under the
+ // same key id. this ensures the overwriting gets tested.
+ ZAP,
+ // finds an item we know is in the list and whacks it.
+ ADD_ZAP,
+ // adds a new item and immediately finds and zaps it.
+ ZAP_ADD,
+ // zaps an item that we know about and then adds a new item with the same
+ // identifier.
+ FIND,
+ // locates an item in the list which we know should exist.
+ ACQUIRE,
+ // grabs an item out of the list (and tosses it).
+ 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.
+ ACQUIRE_ADD_ZAP,
+ // removes an item from the list that we know should be there, adds it back
+ // in, and then whacks it.
+ FIND_ADD_FIND,
+ // find an item with a particular id (one that we know should be in the
+ // list) and then adds a different item using the same id. the new item
+ // is then sought.
+ RESET,
+ // tosses all data out of the hash table. not done very often.
+ CHECK_SANITY,
+ // look for any problems or irregularities; print the contents of the list
+ // if any are found.
+ REHASH,
+ // resizes the hash table.
+ COPY,
+ // copies a hash table to another hash table.
+ LAST_TEST = COPY // place-holder; must equal test just prior.
+};
+
+//////////////
+
+// a simple object that is used as the contents of the hash_table.
+
+class data_shuttle
+{
+public:
+ int food_bar;
+ astring snacky_string;
+ bool hungry;
+ byte_array chunk;
+ chaos chao;
+
+ data_shuttle()
+ : snacky_string(string_manipulation::make_random_name()),
+ chunk(chao.inclusive(100, 10000)) {}
+};
+
+//////////////
+
+class test_int_hash : public virtual unit_base, virtual public application_shell
+{
+public:
+ test_int_hash();
+
+ int execute();
+ //!< the main startup for the test.
+
+ bool perform_a_test(test_actions test_type);
+ //!< carries out the specifics of the "test_type".
+
+ bool pick_a_test();
+ //!< randomly picks one of the test types and performs it.
+
+ DEFINE_CLASS_NAME("test_int_hash");
+
+ static bool equivalence_applier(const int &key, data_shuttle &item, void *dlink);
+
+ static const char *test_name(test_actions test_type);
+
+ int raw_random_id(); //!< returns an unvetted random number.
+ int unused_random_id(); //!< returns an unused (so far) random number.
+
+ // these functions each perform one type of test, which their names indicate.
+ bool test_add();
+ bool test_add_add();
+ bool test_zap();
+ bool test_add_zap();
+ bool test_zap_add();
+ bool test_find();
+ bool test_acquire();
+ bool test_find_zap_add();
+ bool test_acquire_add_zap();
+ bool test_find_add_find();
+ bool test_reset(bool always_do_it = false);
+ bool test_check_sanity();
+ bool test_copy();
+ bool test_rehash();
+
+private:
+ int_set _keys_in_use; // keys that we think are stored in the table.
+ int_hash<data_shuttle> _the_table; // our table under test.
+ int _hits[LAST_TEST - FIRST_TEST + 1]; // tracks our testing activities.
+ int _tested; // simple counter of number of test calls.
+};
+
+//////////////
+
+typedef int_hash<data_shuttle> our_hash; // cleans up somewhat.
+
+//////////////
+
+test_int_hash::test_int_hash()
+: application_shell(),
+ _the_table(MAX_DEFAULT_BITS),
+ _tested(0)
+{
+ for (int i = FIRST_TEST; i <= LAST_TEST; i++)
+ _hits[i - FIRST_TEST] = 0;
+}
+
+int test_int_hash::execute()
+{
+ time_stamp exit_time((int)TEST_DURATION);
+//log(astring("before starting tests"));
+ while (time_stamp() < exit_time) {
+ pick_a_test();
+ }
+ test_reset(true); // make sure we do this at least once.
+#ifdef DEBUG_INT_HASH
+ log(a_sprintf("did %d tests.\n", _tested));
+ log(astring("Test Activity:"));
+ for (int i = 0; i < LAST_TEST - FIRST_TEST + 1; i++)
+ log(astring(astring::SPRINTF, "%d (%s): %d hits", i + FIRST_TEST,
+ test_name(test_actions(i + FIRST_TEST)), _hits[i]));
+ log(a_sprintf("note that test %d will seldom be executed.", RESET));
+#endif
+ return final_report();
+}
+
+const char *test_int_hash::test_name(test_actions test_type)
+{
+ switch (test_type) {
+ case ADD: return "ADD";
+ case ADD_ADD: return "ADD_ADD";
+ case ZAP: return "ZAP";
+ case ADD_ZAP: return "ADD_ZAP";
+ case ZAP_ADD: return "ZAP_ADD";
+ case FIND: return "FIND";
+ case ACQUIRE: return "ACQUIRE";
+ case FIND_ZAP_ADD: return "FIND_ZAP_ADD";
+ case ACQUIRE_ADD_ZAP: return "ACQUIRE_ADD_ZAP";
+ case FIND_ADD_FIND: return "FIND_ADD_FIND";
+ case RESET: return "RESET";
+ case COPY: return "COPY";
+ case REHASH: return "REHASH";
+ case CHECK_SANITY: return "CHECK_SANITY";
+ default: return "UnknownTest";
+ }
+}
+
+bool test_int_hash::perform_a_test(test_actions test_type)
+{
+ FUNCDEF("perform_a_test");
+
+// log(astring(test_name(test_type)) + " ");
+
+ switch (test_type) {
+ case ADD: return test_add();
+ case ADD_ADD: return test_add_add();
+ case ZAP: return test_zap();
+ case ADD_ZAP: return test_add_zap();
+ case ZAP_ADD: return test_zap_add();
+ case FIND: return test_find();
+ case ACQUIRE: return test_acquire();
+ case FIND_ZAP_ADD: return test_find_zap_add();
+ case ACQUIRE_ADD_ZAP: return test_acquire_add_zap();
+ case FIND_ADD_FIND: return test_find_add_find();
+ case RESET: return test_reset();
+ case COPY: return test_copy();
+ case REHASH: return test_rehash();
+ case CHECK_SANITY: return test_check_sanity();
+ default:
+ ASSERT_TRUE(false, "there should be no missing case seen!");
+ return false; // never gets here.
+ }
+}
+
+bool test_int_hash::pick_a_test()
+{
+ _tested++;
+ return perform_a_test(test_actions(randomizer().inclusive(FIRST_TEST, LAST_TEST)));
+}
+
+int test_int_hash::raw_random_id()
+{
+ return randomizer().inclusive(-MAXINT32 / 4, MAXINT32 / 4);
+}
+
+int test_int_hash::unused_random_id()
+{
+ while (true) {
+ int checking = raw_random_id();
+ if (!_keys_in_use.member(checking)) return checking; // got one.
+ } // keep going until we find unused id.
+}
+
+bool test_int_hash::test_add()
+{
+ FUNCDEF("test_add");
+ _hits[ADD - FIRST_TEST]++;
+ int random_id = raw_random_id();
+ data_shuttle *to_add = new data_shuttle;
+ to_add->snacky_string = string_manipulation::make_random_name();
+ to_add->food_bar = random_id;
+ outcome wanting = common::IS_NEW;
+ if (_keys_in_use.member(random_id)) wanting = common::EXISTING;
+ ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), wanting.value(),
+ "adding key should work with right expectation");
+ if (_keys_in_use.member(random_id))
+ return true; // already was there so we replaced.
+ _keys_in_use.add(random_id);
+ return true;
+}
+
+//////////////
+
+#undef UNIT_BASE_THIS_OBJECT
+#define UNIT_BASE_THIS_OBJECT (*dynamic_cast<unit_base *>(application_shell::single_instance()))
+
+int_hash<data_shuttle> *_hang_on = NIL;
+ // must be set before calling the apply method.
+
+bool test_int_hash::equivalence_applier(const int &key, data_shuttle &item, void *dlink)
+{
+ FUNCDEF("equivalence_applier");
+ ASSERT_TRUE(dlink, "should have been given name");
+ if (!dlink) return false; // fail.
+ astring test_name = (char *)dlink;
+
+//application_shell::single_instance()->log(astring("after name check"));
+
+ data_shuttle *found = _hang_on->find(key);
+ ASSERT_TRUE(found, test_name + ": should find equivalent entry in second list");
+ if (!found) return false; // bail or we'll crash.
+
+//application_shell::single_instance()->log(astring("after finding"));
+
+ ASSERT_EQUAL(item.food_bar, found->food_bar, test_name + ": food_bar should not differ");
+ ASSERT_EQUAL(item.snacky_string, found->snacky_string, test_name + ": snacky_string should not differ");
+ ASSERT_EQUAL(item.hungry, found->hungry, test_name + ": hungry should not differ");
+ return true;
+}
+
+#undef UNIT_BASE_THIS_OBJECT
+#define UNIT_BASE_THIS_OBJECT (*this)
+
+//////////////
+
+bool test_int_hash::test_rehash()
+{
+ FUNCDEF("test_rehash");
+ // we don't want to rehash too often; it is expensive.
+// int maybe = randomizer().inclusive(1, 50);
+// if (maybe < 32) return true; // not this time.
+
+ _hang_on = &_the_table; // must do this first.
+
+ _hits[REHASH - FIRST_TEST]++;
+
+ int_hash<data_shuttle> table_copy(_the_table.estimated_elements());
+
+ _the_table.apply(equivalence_applier, (void *)func);
+ astring second_test_name(func);
+ second_test_name += " try 2";
+ table_copy.apply(equivalence_applier, (void *)second_test_name.s());
+
+ if (!_the_table.elements()) return true; // nothing to do right now for comparisons.
+
+//log("copying table...");
+ copy_hash_table(table_copy, _the_table);
+ // make a copy of the table.
+
+ ASSERT_INEQUAL(0, table_copy.elements(), "copy shouldn't have unexpected absence of contents");
+
+//log("rehashing table...");
+ _the_table.rehash(randomizer().inclusive(1, 20));
+
+//hmmm: need test of dehash function that reduces elements estimated.
+
+//log("comparing table...");
+ astring third_test_name(func);
+ third_test_name += " try 3";
+ table_copy.apply(equivalence_applier, (void *)third_test_name.s());
+//log("done copy and compare.");
+
+ return true;
+}
+
+bool test_int_hash::test_copy()
+{
+ FUNCDEF("test_copy");
+ // we don't want to copy too often. it's a heavy operation.
+// int maybe = randomizer().inclusive(1, 50);
+// if (maybe > 16) return true; // not this time.
+
+ _hang_on = &_the_table; // must do this first.
+
+ _hits[COPY - FIRST_TEST]++;
+
+ int_hash<data_shuttle> table_copy(MAX_DEFAULT_BITS);
+
+//log("copying table...");
+ copy_hash_table(table_copy, _the_table);
+ // make a copy of the table.
+
+//log("comparing table...");
+ table_copy.apply(equivalence_applier, (void *)func);
+//log("done copy and compare.");
+
+ return true;
+}
+
+//////////////
+
+bool test_int_hash::test_add_add()
+{
+ FUNCDEF("test_add_add");
+ _hits[ADD_ADD - FIRST_TEST]++;
+ int random_id = unused_random_id();
+ data_shuttle *to_add = new data_shuttle;
+ to_add->snacky_string = string_manipulation::make_random_name();
+ to_add->food_bar = random_id;
+ ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), common::IS_NEW, "key should be new");
+ _keys_in_use.add(random_id);
+
+ // second add on same id.
+ data_shuttle *next_add = new data_shuttle;
+ next_add->snacky_string = string_manipulation::make_random_name();
+ next_add->food_bar = random_id;
+ ASSERT_EQUAL(_the_table.add(random_id, next_add).value(), our_hash::EXISTING,
+ "second add should not say first failed");
+
+ return true;
+}
+
+bool test_int_hash::test_zap()
+{
+ FUNCDEF("test_zap");
+ int maybe = randomizer().inclusive(1, 1000);
+ if (maybe > 500) return true;
+ if (!_keys_in_use.elements()) return false; // can't do it yet.
+ _hits[ZAP - FIRST_TEST]++;
+ int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
+ int dead_key = _keys_in_use[rand_indy];
+ _keys_in_use.remove(dead_key); // remove the record of that key.
+ ASSERT_TRUE(_the_table.zap(dead_key), "zap should work on key");
+ return true;
+}
+
+bool test_int_hash::test_add_zap()
+{
+ FUNCDEF("test_add_zap");
+ // add.
+ _hits[ADD_ZAP - FIRST_TEST]++;
+ int random_id = unused_random_id();
+ data_shuttle *to_add = new data_shuttle;
+ to_add->snacky_string = string_manipulation::make_random_name();
+ to_add->food_bar = random_id;
+ ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), common::IS_NEW, "key is new before zap");
+ // zap.
+ ASSERT_TRUE(_the_table.zap(random_id), "add then zap should remove the key");
+ return true;
+}
+
+bool test_int_hash::test_zap_add()
+{
+ FUNCDEF("test_zap_add");
+ if (!_keys_in_use.elements()) return false; // can't do it yet.
+ _hits[ZAP_ADD - FIRST_TEST]++;
+ int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
+ // in the end, the key list state won't be changed unless the test fails.
+ int dead_key = _keys_in_use[rand_indy];
+ ASSERT_TRUE(_the_table.zap(dead_key), "key should be there for zapping");
+
+ data_shuttle *to_add = new data_shuttle;
+ to_add->snacky_string = string_manipulation::make_random_name();
+ to_add->food_bar = dead_key;
+ outcome ret = _the_table.add(dead_key, to_add);
+ ASSERT_EQUAL(ret.value(), our_hash::IS_NEW, "key should not already be present somehow");
+ return true;
+}
+
+int functional_return(int to_pass) {
+ return to_pass;
+}
+
+bool test_int_hash::test_find()
+{
+ FUNCDEF("test_find");
+ if (!_keys_in_use.elements()) return false; // can't do it yet.
+ _hits[FIND - FIRST_TEST]++;
+ int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
+ int find_key = _keys_in_use[rand_indy];
+ data_shuttle *found = NIL;
+ ASSERT_TRUE(_the_table.find(functional_return(find_key), found),
+ "key should be there when we look");
+ ASSERT_TRUE(_the_table.find(functional_return(find_key)), "find2: key be there when checked");
+ ASSERT_TRUE(found, "when key is found contents should not be NIL");
+ ASSERT_EQUAL(found->food_bar, find_key, "stored key should be same as real key");
+ ASSERT_TRUE(found->snacky_string.length(), "stored string should have some length");
+ return true;
+}
+
+bool test_int_hash::test_acquire()
+{
+ FUNCDEF("test_acquire");
+ int maybe = randomizer().inclusive(1, 1000);
+ if (maybe > 750) return true;
+ if (!_keys_in_use.elements()) return false; // can't do it yet.
+ _hits[ACQUIRE - FIRST_TEST]++;
+ int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
+ int find_key = _keys_in_use[rand_indy];
+ _keys_in_use.remove(find_key); // remove the record of that key.
+ data_shuttle *found = _the_table.acquire(find_key);
+ ASSERT_TRUE(found, "key should be there like clockwork");
+ ASSERT_EQUAL(found->food_bar, find_key, "stored key should be same as real key");
+ ASSERT_TRUE(found->snacky_string.length(), "stored string should have some length");
+ WHACK(found);
+ found = _the_table.acquire(find_key);
+ ASSERT_FALSE(found, "key should be missing after zap");
+ return true;
+}
+
+bool test_int_hash::test_find_zap_add()
+{
+ FUNCDEF("test_find_zap_add");
+ // find.
+ if (!_keys_in_use.elements()) return false; // can't do it yet.
+ _hits[FIND_ZAP_ADD - FIRST_TEST]++;
+ int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
+ // this is another key list invariant function, if it works.
+ int find_key = _keys_in_use[rand_indy];
+ data_shuttle *found = NIL;
+ ASSERT_TRUE(_the_table.find(find_key, found), "key should be there when sought");
+ ASSERT_TRUE(_the_table.find(find_key), "find2: key should be there for us to find");
+ ASSERT_TRUE(found, "found key should have non-NIL contents");
+ ASSERT_EQUAL(found->food_bar, find_key, "stored key should have no differences from real key");
+ ASSERT_TRUE(found->snacky_string.length(), "stored string should have non-zero length");
+ // zap.
+ ASSERT_TRUE(_the_table.zap(find_key), "should be able to zap the item we had found");
+ // add.
+ data_shuttle *to_add = new data_shuttle;
+ to_add->snacky_string = string_manipulation::make_random_name();
+ to_add->food_bar = find_key;
+ ASSERT_EQUAL(_the_table.add(find_key, to_add).value(), our_hash::IS_NEW,
+ "the item we zapped should not still be there");
+ return true;
+}
+
+bool test_int_hash::test_reset(bool always_do_it)
+{
+ FUNCDEF("test_reset");
+ if (!always_do_it) {
+ int maybe = randomizer().inclusive(1, 1000);
+ // this is hardly ever hit, but it loses all contents too often otherwise.
+ if ( (maybe > 372) || (maybe < 368) ) return true;
+ }
+
+ // we hit the big time; we will reset now.
+ _hits[RESET - FIRST_TEST]++;
+ _the_table.reset();
+ for (int i = _keys_in_use.elements() - 1; i >= 0; i--) {
+ int dead_key = _keys_in_use[i];
+ ASSERT_FALSE(_the_table.acquire(dead_key), "after reset, we should not find an item");
+ _keys_in_use.remove(dead_key);
+ }
+ return true;
+}
+
+//hmmm: implement these tests!
+
+bool test_int_hash::test_acquire_add_zap()
+{
+ _hits[ACQUIRE_ADD_ZAP - FIRST_TEST]++;
+return false;
+}
+
+bool test_int_hash::test_find_add_find()
+{
+ _hits[FIND_ADD_FIND - FIRST_TEST]++;
+return false;
+}
+
+bool test_int_hash::test_check_sanity()
+{
+ _hits[CHECK_SANITY - FIRST_TEST]++;
+return false;
+}
+
+//////////////
+
+HOOPLE_MAIN(test_int_hash, )
+
projects / feisty_meow.git / blobdiff