feisty meow concerns codebase  2.140
test_int_hash.cpp
Go to the documentation of this file.
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 
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>
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 
49 
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.
57  ZAP,
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
63  // identifier.
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
77  // is then sought.
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
82  // if any are found.
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.
88 };
89 
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 
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();
117 
118  bool perform_a_test(test_actions test_type);
120 
121  bool pick_a_test();
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();
131  int unused_random_id();
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 
157 
158 typedef int_hash<data_shuttle> our_hash; // cleans up somewhat.
159 
161 
162 test_int_hash::test_int_hash()
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 
277 
278 #undef UNIT_BASE_THIS_OBJECT
279 #define UNIT_BASE_THIS_OBJECT (*dynamic_cast<unit_base *>(application_shell::single_instance()))
280 
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 
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 
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 
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 = NULL_POINTER;
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 null");
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 = NULL_POINTER;
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-null 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 
552 
553 HOOPLE_MAIN(test_int_hash, )
554 
The application_shell is a base object for console programs.
a_sprintf is a specialization of astring that provides printf style support.
Definition: astring.h:440
Provides a dynamically resizable ASCII character string.
Definition: astring.h:35
const char * s() const
synonym for observe. the 's' stands for "string", if that helps.
Definition: astring.h:113
A very common template for a dynamic array of bytes.
Definition: byte_array.h:36
Outcomes describe the state of completion for an operation.
Definition: outcome.h:31
int value() const
Definition: outcome.h:51
a platform-independent way to acquire random numbers in a specific range.
Definition: chaos.h:51
int inclusive(int low, int high) const
< Returns a pseudo-random number r, such that "low" <= r <= "high".
Definition: chaos.h:88
int elements() const
the number of valid items we found by traversing the hash table.
Definition: hash_table.h:576
bool find(const key_type &key, contents *&item_found) const
locates the item specified by the "key", if possible.
Definition: hash_table.h:460
void apply(apply_function *to_apply, void *data_link)
operates on every item in the int_hash table.
Definition: int_hash.h:116
A simple object that wraps a templated set of ints.
Definition: set.h:156
Represents a point in time relative to the operating system startup time.
Definition: time_stamp.h:38
#define NULL_POINTER
The value representing a pointer to nothing.
Definition: definitions.h:32
#define MAXINT32
Maximum 32-bit integer value.
Definition: definitions.h:75
#define DEFINE_CLASS_NAME(objname)
Defines the name of a class by providing a couple standard methods.
Definition: enhance_cpp.h:45
#define FUNCDEF(func_in)
FUNCDEF sets the name of a function (and plugs it into the callstack).
Definition: enhance_cpp.h:57
Provides macros that implement the 'main' program of an application.
#define HOOPLE_MAIN(obj_name, obj_args)
options that should work for most unix and linux apps.
Definition: hoople_main.h:61
Implements an application lock to ensure only one is running at once.
The guards collection helps in testing preconditions and reporting errors.
Definition: array.h:30
void WHACK(contents *&ptr)
deletion with clearing of the pointer.
Definition: functions.h:121
const int SECOND_ms
Number of milliseconds in a second.
Definition: definitions.h:120
A platform independent way to obtain the timestamp of a file.
Definition: byte_filer.cpp:37
A logger that sends to the console screen using the standard output device.
An extension to floating point primitives providing approximate equality.
Definition: averager.h:21
A dynamic container class that holds any kind of object via pointers.
Definition: amorph.h:55
void copy_hash_table(hash_table< key_type, contents > &target, const hash_table< key_type, contents > &source)
Copies the entire hash table, given a contents type that supports copying.
Definition: hash_table.h:292
#include <time.h>
Definition: earth_time.cpp:37
Useful support functions for unit testing, especially within hoople.
Definition: unit_base.cpp:35
#define randomizer()
test_actions
test_actions
@ FIRST_TEST
@ CHECK_SANITY
@ REHASH
@ ADD_ZAP
@ FIND_ADD_FIND
@ RESET
@ FIND_ZAP_ADD
@ FIND
@ ADD_ADD
@ ACQUIRE_ADD_ZAP
@ ZAP
@ LAST_TEST
@ COPY
@ ADD
@ ACQUIRE
@ ZAP_ADD
int_hash< data_shuttle > our_hash
const double TEST_DURATION
int functional_return(int to_pass)
const int MAX_DEFAULT_BITS
int_hash< data_shuttle > * _hang_on
#define test_name()
#define ASSERT_EQUAL(a, b, test_name)
Definition: unit_base.h:38
#define ASSERT_TRUE(a, test_name)
Definition: unit_base.h:46
#define ASSERT_FALSE(a, test_name)
Definition: unit_base.h:50
#define ASSERT_INEQUAL(a, b, test_name)
Definition: unit_base.h:42