2 * Name : test_hash_table
3 * Author : Chris Koeritz
5 * Tests out the hash_table abstract data type.
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/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>
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;
39 //#define DEBUG_HASH_TABLE
40 // uncomment for noisier run.
42 const double TEST_DURATION = 0.014 * MINUTE_ms;
43 //const double TEST_DURATION = 20 * SECOND_ms;
45 const int MAX_ELEMENTS = 8;
46 // we start low since we will rehash occasionally.
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.
72 // a simple object that is used as the contents of the hash_table.
78 astring snacky_string;
84 : snacky_string(string_manipulation::make_random_name()),
85 chunk(chao.inclusive(100, 10000)), food_bar(0), hungry(false) {}
90 class test_hash_table : virtual public unit_base, virtual public application_shell
95 DEFINE_CLASS_NAME("test_hash_table");
97 int raw_random_id(); //!< returns an unvetted random number.
99 //! returns an unused (so far) random number.
100 int unused_random_id();
103 // the main startup for the test.
105 bool perform_a_test(test_actions test_type);
106 // carries out the specifics of the "test_type".
109 // randomly picks one of the test types and performs it.
111 static const char *test_name(test_actions test_type);
113 // these functions each perform one type of test, which their names indicate.
121 bool test_find_zap_add();
122 bool test_acquire_add_zap();
123 bool test_find_add_find();
124 bool test_reset(bool always_run = false);
125 bool test_check_sanity();
129 static bool equivalence_applier(const int &key, data_shuttle &item, void *dlink);
132 int_set _keys_in_use; // keys that we think are stored in the table.
133 hash_table<int, data_shuttle> _the_table; // our table under test.
134 int _hits[LAST_TEST - FIRST_TEST + 1]; // tracks our testing activities.
135 int _tested; // simple counter of number of test calls.
140 typedef hash_table<int, data_shuttle> our_hash; // cleans up somewhat.
144 test_hash_table::test_hash_table()
145 : application_shell(),
146 _the_table(rotating_byte_hasher(), MAX_ELEMENTS),
149 for (int i = FIRST_TEST; i <= LAST_TEST; i++)
150 _hits[i - FIRST_TEST] = 0;
153 int test_hash_table::raw_random_id()
155 return randomizer().inclusive(-MAXINT32 / 4, MAXINT32 / 4);
158 int test_hash_table::unused_random_id()
161 int checking = raw_random_id();
162 if (!_keys_in_use.member(checking)) return checking; // got one.
163 } // keep going until we find unused id.
164 return -1; // this is a failure, but we will never get here.
167 int test_hash_table::execute()
169 time_stamp exit_time((int)TEST_DURATION);
170 while (time_stamp() < exit_time) {
173 test_reset(true); // force it to run at least once.
175 #ifdef DEBUG_HASH_TABLE
176 log(a_sprintf("did %d tests.\n", _tested));
177 log(astring("Test Activity:"));
178 for (int i = 0; i < LAST_TEST - FIRST_TEST + 1; i++)
179 log(astring(astring::SPRINTF, "%d (%s): %d hits", i + FIRST_TEST,
180 test_name(test_actions(i + FIRST_TEST)), _hits[i]));
181 log(a_sprintf("note that test %d will seldom be executed.", RESET));
183 return final_report();
186 const char *test_hash_table::test_name(test_actions test_type)
189 case ADD: return "ADD";
190 case ADD_ADD: return "ADD_ADD";
191 case ZAP: return "ZAP";
192 case ADD_ZAP: return "ADD_ZAP";
193 case ZAP_ADD: return "ZAP_ADD";
194 case FIND: return "FIND";
195 case ACQUIRE: return "ACQUIRE";
196 case FIND_ZAP_ADD: return "FIND_ZAP_ADD";
197 case ACQUIRE_ADD_ZAP: return "ACQUIRE_ADD_ZAP";
198 case FIND_ADD_FIND: return "FIND_ADD_FIND";
199 case RESET: return "RESET";
200 case COPY: return "COPY";
201 case REHASH: return "REHASH";
202 case CHECK_SANITY: return "CHECK_SANITY";
203 default: return "UnknownTest";
207 bool test_hash_table::perform_a_test(test_actions test_type)
209 FUNCDEF("perform_a_test");
211 // log(astring(test_name(test_type)) + " ");
214 case ADD: return test_add();
215 case ADD_ADD: return test_add_add();
216 case ZAP: return test_zap();
217 case ADD_ZAP: return test_add_zap();
218 case ZAP_ADD: return test_zap_add();
219 case FIND: return test_find();
220 case ACQUIRE: return test_acquire();
221 case FIND_ZAP_ADD: return test_find_zap_add();
222 case ACQUIRE_ADD_ZAP: return test_acquire_add_zap();
223 case FIND_ADD_FIND: return test_find_add_find();
224 case RESET: return test_reset();
225 case COPY: return test_copy();
226 case REHASH: return test_rehash();
227 case CHECK_SANITY: return test_check_sanity();
229 ASSERT_TRUE(false, "should not see any missing cases");
230 return false; // never gets here.
234 bool test_hash_table::pick_a_test()
237 return perform_a_test(test_actions(randomizer().inclusive(FIRST_TEST,
241 bool test_hash_table::test_add()
244 _hits[ADD - FIRST_TEST]++;
245 int random_id = raw_random_id();
246 data_shuttle *to_add = new data_shuttle;
247 to_add->snacky_string = string_manipulation::make_random_name();
248 to_add->food_bar = random_id;
249 outcome expected = common::IS_NEW;
250 // make sure it doesn't exist already.
251 if (_keys_in_use.member(random_id)) return false;
252 ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), expected.value(),
253 "add should give proper outcome based on expectation");
254 if (_keys_in_use.member(random_id))
255 return true; // already was there so we replaced.
256 _keys_in_use.add(random_id);
262 hash_table<int, data_shuttle> *_hang_on = NIL;
263 // must be set before calling the apply method.
265 #undef UNIT_BASE_THIS_OBJECT
266 #define UNIT_BASE_THIS_OBJECT (*dynamic_cast<unit_base *>(application_shell::single_instance()))
268 bool test_hash_table::equivalence_applier(const int &key, data_shuttle &item, void *dlink)
270 FUNCDEF("equivalence_applier");
271 ASSERT_NON_NULL(dlink, "should have been given name");
272 if (!dlink) return false; // fail.
273 astring test_name = (char *)dlink;
275 //application_shell::single_instance()->log(astring("after name check"));
277 data_shuttle *found = _hang_on->find(key);
278 ASSERT_NON_NULL(found, test_name + ": should find equivalent entry in second list");
279 if (!found) return false; // bail or we'll crash.
281 //application_shell::single_instance()->log(astring("after finding"));
283 ASSERT_EQUAL(item.food_bar, found->food_bar, test_name + ": food_bar should not differ");
284 ASSERT_EQUAL(item.snacky_string, found->snacky_string, test_name + ": snacky_string should not differ");
285 ASSERT_EQUAL(item.hungry, found->hungry, test_name + ": hungry should not differ");
289 #undef UNIT_BASE_THIS_OBJECT
290 #define UNIT_BASE_THIS_OBJECT (*this)
294 bool test_hash_table::test_rehash()
296 FUNCDEF("test_rehash");
297 _hang_on = &_the_table; // must happen first.
299 // we don't want to rehash too often; it is expensive.
300 int maybe = randomizer().inclusive(1, 50);
301 if (maybe < 32) return true; // not this time.
303 _hits[REHASH - FIRST_TEST]++;
305 hash_table<int, data_shuttle> table_copy(rotating_byte_hasher(),
306 _the_table.estimated_elements());
308 //log("copying table...");
309 copy_hash_table(table_copy, _the_table);
310 // make a copy of the table.
312 //log("rehashing table...");
313 _the_table.rehash(randomizer().inclusive(1, 20));
314 //hmmm: need test of non-existent dehash function that reduces max_bits.
316 //log("comparing table...");
317 table_copy.apply(equivalence_applier, (void*)func);
318 //log("done copy and compare.");
323 bool test_hash_table::test_copy()
325 FUNCDEF("test_copy");
326 _hang_on = &_the_table; // must happen first.
328 // we don't want to copy too often. it's a heavy operation.
329 int maybe = randomizer().inclusive(1, 50);
330 if (maybe > 16) return true; // not this time.
332 _hits[COPY - FIRST_TEST]++;
334 hash_table<int, data_shuttle> table_copy(rotating_byte_hasher(), MAX_ELEMENTS);
336 //log("copying table...");
337 copy_hash_table(table_copy, _the_table);
338 // make a copy of the table.
340 //log("comparing table...");
341 table_copy.apply(equivalence_applier, (void*)func);
342 //log("done copy and compare.");
349 bool test_hash_table::test_add_add()
351 FUNCDEF("test_add_add");
352 _hits[ADD_ADD - FIRST_TEST]++;
353 int random_id = unused_random_id();
354 data_shuttle *to_add = new data_shuttle;
355 to_add->snacky_string = string_manipulation::make_random_name();
356 to_add->food_bar = random_id;
357 ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), common::IS_NEW,
358 "new addition should be seen as such");
359 // add the new key if it's really new.
360 _keys_in_use.add(random_id);
362 // second add on same id.
363 data_shuttle *next_add = new data_shuttle;
364 next_add->snacky_string = string_manipulation::make_random_name();
365 next_add->food_bar = random_id;
366 ASSERT_EQUAL(_the_table.add(random_id, next_add).value(), our_hash::EXISTING,
367 "second add should not say first failed");
372 bool test_hash_table::test_zap()
375 int maybe = randomizer().inclusive(1, 1000);
376 if (maybe > 50) return true;
377 if (!_keys_in_use.elements()) return false; // can't do it yet.
378 _hits[ZAP - FIRST_TEST]++;
379 int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
380 int dead_key = _keys_in_use[rand_indy];
381 _keys_in_use.remove(dead_key); // remove the record of that key.
382 ASSERT_TRUE(_the_table.zap(dead_key), "key should be present in table");
386 bool test_hash_table::test_add_zap()
388 FUNCDEF("test_add_zap");
390 _hits[ADD_ZAP - FIRST_TEST]++;
391 int random_id = unused_random_id();
392 data_shuttle *to_add = new data_shuttle;
393 to_add->snacky_string = string_manipulation::make_random_name();
394 to_add->food_bar = random_id;
395 ASSERT_EQUAL(_the_table.add(random_id, to_add).value(), common::IS_NEW,
396 "putting new item in should be seen as new");
398 ASSERT_TRUE(_the_table.zap(random_id), "key should be present after add");
402 bool test_hash_table::test_zap_add()
404 FUNCDEF("test_zap_add");
405 if (!_keys_in_use.elements()) return false; // can't do it yet.
406 _hits[ZAP_ADD - FIRST_TEST]++;
407 int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
408 // in the end, the key list state won't be changed unless the test fails.
409 int dead_key = _keys_in_use[rand_indy];
410 ASSERT_TRUE(_the_table.zap(dead_key), "key should be there when we look");
412 data_shuttle *to_add = new data_shuttle;
413 to_add->snacky_string = string_manipulation::make_random_name();
414 to_add->food_bar = dead_key;
415 outcome ret = _the_table.add(dead_key, to_add);
416 ASSERT_EQUAL(ret.value(), our_hash::IS_NEW, "key should not be present already");
420 bool test_hash_table::test_find()
422 FUNCDEF("test_find");
423 if (!_keys_in_use.elements()) return false; // can't do it yet.
424 _hits[FIND - FIRST_TEST]++;
425 int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
426 int find_key = _keys_in_use[rand_indy];
427 data_shuttle *found = NIL;
428 ASSERT_TRUE(_the_table.find(find_key, found), "key should be there as expected");
429 ASSERT_NON_NULL(found, "contents should not be NIL");
430 ASSERT_EQUAL(found->food_bar, find_key, "stored key should be same as real key");
431 ASSERT_TRUE(found->snacky_string.length(), "stored string should have length");
435 bool test_hash_table::test_acquire()
437 FUNCDEF("test_acquire");
438 int maybe = randomizer().inclusive(1, 1000);
439 if (maybe > 150) return true;
440 if (!_keys_in_use.elements()) return false; // can't do it yet.
441 _hits[ACQUIRE - FIRST_TEST]++;
442 int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
443 int find_key = _keys_in_use[rand_indy];
444 _keys_in_use.remove(find_key); // remove the record of that key.
445 data_shuttle *found = _the_table.acquire(find_key);
446 ASSERT_NON_NULL(found, "key should be present when expected");
447 ASSERT_EQUAL(found->food_bar, find_key, "stored key should be same as real key");
448 ASSERT_TRUE(found->snacky_string.length(), "stored string should not have zero length");
450 found = _the_table.acquire(find_key);
451 ASSERT_NULL(found, "key should not be there after zap");
455 bool test_hash_table::test_find_zap_add()
457 FUNCDEF("test_find_zap_add");
459 if (!_keys_in_use.elements()) return false; // can't do it yet.
460 _hits[FIND_ZAP_ADD - FIRST_TEST]++;
461 int rand_indy = randomizer().inclusive(0, _keys_in_use.elements() - 1);
462 // this is another key list invariant function, if it works.
463 int find_key = _keys_in_use[rand_indy];
464 data_shuttle *found = NIL;
465 ASSERT_TRUE(_the_table.find(find_key, found), "key should be locateable");
466 ASSERT_NON_NULL(found, "key should not have NIL contents");
467 ASSERT_EQUAL(found->food_bar, find_key, "stored key should be equal to real key");
468 ASSERT_TRUE(found->snacky_string.length(), "stored string should not have zero length");
470 ASSERT_TRUE(_the_table.zap(find_key), "should be able to zap the item we had found");
472 data_shuttle *to_add = new data_shuttle;
473 to_add->snacky_string = string_manipulation::make_random_name();
474 to_add->food_bar = find_key;
475 ASSERT_EQUAL(_the_table.add(find_key, to_add).value(), our_hash::IS_NEW,
476 "the item we zapped should be gone");
480 bool test_hash_table::test_reset(bool always_run)
482 FUNCDEF("test_reset");
484 int maybe = randomizer().inclusive(1, 1000);
485 // this is hardly ever hit, but it loses all contents too often otherwise.
486 if ( (maybe > 372) || (maybe < 368) ) return true;
489 // we hit the big time; we will reset now.
490 _hits[RESET - FIRST_TEST]++;
492 for (int i = _keys_in_use.elements() - 1; i >= 0; i--) {
493 int dead_key = _keys_in_use[i];
494 ASSERT_FALSE(_the_table.acquire(dead_key), "after reset, we should not find item");
495 _keys_in_use.remove(dead_key);
500 //hmmm: implement these tests!
502 bool test_hash_table::test_acquire_add_zap()
504 _hits[ACQUIRE_ADD_ZAP - FIRST_TEST]++;
508 bool test_hash_table::test_find_add_find()
510 _hits[FIND_ADD_FIND - FIRST_TEST]++;
514 bool test_hash_table::test_check_sanity()
516 _hits[CHECK_SANITY - FIRST_TEST]++;
522 HOOPLE_MAIN(test_hash_table, )