3 * Author : Chris Koeritz
5 * Tests out hash_table specialization for integers.
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 *
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>
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;
37 //#define DEBUG_INT_HASH
38 // uncomment for noisier run.
40 #define EXTREME_CHECKING
41 // causes extra checks in the library code.
43 const double TEST_DURATION = 0.5 * SECOND_ms;
45 const int MAX_DEFAULT_BITS = 2;
46 // we start low since we will rehash occasionally.
51 FIRST_TEST = 38, // place-holder.
53 // adds an item that is probably new.
55 // adds an item that is probably new, followed by another item under the
56 // same key id. this ensures the overwriting gets tested.
58 // finds an item we know is in the list and whacks it.
60 // adds a new item and immediately finds and zaps it.
62 // zaps an item that we know about and then adds a new item with the same
65 // locates an item in the list which we know should exist.
67 // grabs an item out of the list (and tosses it).
69 // finds an item we know should exist, zaps it out of the list, then adds
70 // a new item with the same id.
72 // removes an item from the list that we know should be there, adds it back
73 // in, and then whacks it.
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
79 // tosses all data out of the hash table. not done very often.
81 // look for any problems or irregularities; print the contents of the list
84 // resizes the hash table.
86 // copies a hash table to another hash table.
87 LAST_TEST = COPY // place-holder; must equal test just prior.
92 // a simple object that is used as the contents of the hash_table.
98 astring snacky_string;
104 : snacky_string(string_manipulation::make_random_name()),
105 chunk(chao.inclusive(100, 10000)), food_bar(0), hungry(false) {}
110 class test_int_hash : public virtual unit_base, virtual public application_shell
116 //!< the main startup for the test.
118 bool perform_a_test(test_actions test_type);
119 //!< carries out the specifics of the "test_type".
122 //!< randomly picks one of the test types and performs it.
124 DEFINE_CLASS_NAME("test_int_hash");
126 static bool equivalence_applier(const int &key, data_shuttle &item, void *dlink);
128 static const char *test_name(test_actions test_type);
130 int raw_random_id(); //!< returns an unvetted random number.
131 int unused_random_id(); //!< returns an unused (so far) random number.
133 // these functions each perform one type of test, which their names indicate.
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();
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.
158 typedef int_hash<data_shuttle> our_hash; // cleans up somewhat.
162 test_int_hash::test_int_hash()
163 : application_shell(),
164 _the_table(MAX_DEFAULT_BITS),
167 for (int i = FIRST_TEST; i <= LAST_TEST; i++)
168 _hits[i - FIRST_TEST] = 0;
171 int test_int_hash::execute()
173 time_stamp exit_time((int)TEST_DURATION);
174 //log(astring("before starting tests"));
175 while (time_stamp() < exit_time) {
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));
187 return final_report();
190 const char *test_int_hash::test_name(test_actions 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";
211 bool test_int_hash::perform_a_test(test_actions test_type)
213 FUNCDEF("perform_a_test");
215 // log(astring(test_name(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();
233 ASSERT_TRUE(false, "there should be no missing case seen!");
234 return false; // never gets here.
238 bool test_int_hash::pick_a_test()
241 return perform_a_test(test_actions(randomizer().inclusive(FIRST_TEST, LAST_TEST)));
244 int test_int_hash::raw_random_id()
246 return randomizer().inclusive(-MAXINT32 / 4, MAXINT32 / 4);
249 int test_int_hash::unused_random_id()
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.
258 bool test_int_hash::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);
278 #undef UNIT_BASE_THIS_OBJECT
279 #define UNIT_BASE_THIS_OBJECT (*dynamic_cast<unit_base *>(application_shell::single_instance()))
281 int_hash<data_shuttle> *_hang_on = NIL;
282 // must be set before calling the apply method.
284 bool test_int_hash::equivalence_applier(const int &key, data_shuttle &item, void *dlink)
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;
291 //application_shell::single_instance()->log(astring("after name check"));
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.
297 //application_shell::single_instance()->log(astring("after finding"));
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");
305 #undef UNIT_BASE_THIS_OBJECT
306 #define UNIT_BASE_THIS_OBJECT (*this)
310 bool test_int_hash::test_rehash()
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.
317 _hang_on = &_the_table; // must do this first.
319 _hits[REHASH - FIRST_TEST]++;
321 int_hash<data_shuttle> table_copy(_the_table.estimated_elements());
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());
328 if (!_the_table.elements()) return true; // nothing to do right now for comparisons.
330 //log("copying table...");
331 copy_hash_table(table_copy, _the_table);
332 // make a copy of the table.
334 ASSERT_INEQUAL(0, table_copy.elements(), "copy shouldn't have unexpected absence of contents");
336 //log("rehashing table...");
337 _the_table.rehash(randomizer().inclusive(1, 20));
339 //hmmm: need test of dehash function that reduces elements estimated.
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.");
350 bool test_int_hash::test_copy()
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.
357 _hang_on = &_the_table; // must do this first.
359 _hits[COPY - FIRST_TEST]++;
361 int_hash<data_shuttle> table_copy(MAX_DEFAULT_BITS);
363 //log("copying table...");
364 copy_hash_table(table_copy, _the_table);
365 // make a copy of the table.
367 //log("comparing table...");
368 table_copy.apply(equivalence_applier, (void *)func);
369 //log("done copy and compare.");
376 bool test_int_hash::test_add_add()
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);
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");
397 bool test_int_hash::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");
411 bool test_int_hash::test_add_zap()
413 FUNCDEF("test_add_zap");
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");
422 ASSERT_TRUE(_the_table.zap(random_id), "add then zap should remove the key");
426 bool test_int_hash::test_zap_add()
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");
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");
444 int functional_return(int to_pass) {
448 bool test_int_hash::test_find()
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");
465 bool test_int_hash::test_acquire()
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");
480 found = _the_table.acquire(find_key);
481 ASSERT_FALSE(found, "key should be missing after zap");
485 bool test_int_hash::test_find_zap_add()
487 FUNCDEF("test_find_zap_add");
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");
501 ASSERT_TRUE(_the_table.zap(find_key), "should be able to zap the item we had found");
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");
511 bool test_int_hash::test_reset(bool always_do_it)
513 FUNCDEF("test_reset");
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;
520 // we hit the big time; we will reset now.
521 _hits[RESET - FIRST_TEST]++;
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);
531 //hmmm: implement these tests!
533 bool test_int_hash::test_acquire_add_zap()
535 _hits[ACQUIRE_ADD_ZAP - FIRST_TEST]++;
539 bool test_int_hash::test_find_add_find()
541 _hits[FIND_ADD_FIND - FIRST_TEST]++;
545 bool test_int_hash::test_check_sanity()
547 _hits[CHECK_SANITY - FIRST_TEST]++;
553 HOOPLE_MAIN(test_int_hash, )