Lumiera  0.pre.03
»edit your freedom«
symbol-hashtable-test.cpp
Go to the documentation of this file.
1 /*
2  SymbolHashtable(Test) - building a hashtable with Symbol (id) keys
3 
4  Copyright (C)
5  2009, Hermann Vosseler <Ichthyostega@web.de>
6 
7   **Lumiera** is free software; you can redistribute it and/or modify it
8   under the terms of the GNU General Public License as published by the
9   Free Software Foundation; either version 2 of the License, or (at your
10   option) any later version. See the file COPYING for further details.
11 
12 * *****************************************************************/
13 
20 #include "lib/test/run.hpp"
21 #include "lib/test/test-helper.hpp"
22 #include "lib/util.hpp"
23 
24 #include "lib/symbol.hpp"
25 
26 #include <boost/functional/hash.hpp>
27 #include <unordered_map>
28 #include <cstring>
29 #include <string>
30 
31 using util::contains;
32 using util::isnil;
33 
34 
35 
36 namespace lib {
37 namespace test{
38 
39  using std::string;
40  using boost::hash;
41 
42 
43  namespace { // test data
44  Symbol KEY1 ("Key1");
45  Symbol KEY2 ("Key2");
46  Symbol KEY3 ("Key3");
47  Symbol KEY4 ("Key4");
48  Symbol KEY5 ("Key5");
49 
50  }
51 
52  typedef std::unordered_map< Symbol, string, hash<Symbol>> HTable;
53 
54 
55  /*********************************************************/
61  class SymbolHashtable_test : public Test
62  {
63 
64  virtual void
65  run (Arg)
66  {
67  seedRand();
68  checkHashFunction();
69 
70  HTable table;
71  CHECK (isnil(table));
72 
73  table[KEY1] = string (KEY1);
74  table[KEY2] = string (KEY2);
75  table[KEY3] = string (KEY3);
76  table[KEY4] = string (KEY4);
77 
78  CHECK (!isnil(table));
79  CHECK (4 == table.size());
80  CHECK (contains (table, KEY1));
81  CHECK (contains (table, KEY2));
82  CHECK (contains (table, KEY3));
83  CHECK (contains (table, KEY4));
84  CHECK (!contains (table, KEY5));
85 
86  CHECK (string (KEY1) == table[KEY1]);
87  CHECK (string (KEY2) == table[KEY2]);
88  CHECK (string (KEY3) == table[KEY3]);
89  CHECK (string (KEY4) == table[KEY4]);
90 
91  table[KEY3] += "...";
92  CHECK (string(KEY3) != table[KEY3]);
93  CHECK (string(KEY3)+"..." == table[KEY3]);
94 
95  CHECK (isnil (table[KEY5])); // adds a new empty value object as side effect
96  CHECK (5 == table.size());
97  }
98 
99 
100  void
101  checkHashFunction()
102  {
103  string random = randStr(STRING_MAX_RELEVANT+1);
104 
105  string copy1(random);
106  copy1[5] = '\0'; // truncate the c-String to 5 chars
107 
108  string copy2(random);
109  copy2[rani (STRING_MAX_RELEVANT)] = '*'; // modify a random position
110 
111  string copy3(copy2);
112  copy3[STRING_MAX_RELEVANT] = '*'; // modify behind observation limit
113 
114  Symbol l0;
115  Literal l51 (copy1.c_str());
116  Literal l52 (random.substr(0,5).c_str());
117 
118  Literal l_1 (random.c_str());
119  Literal l_2 (copy2.c_str());
120  Literal l_3 (copy3.c_str());
121 
122  CHECK (isnil (l0));
123  CHECK (l0 != l51);
124  CHECK (l51 == l52);
125 
126  CHECK (l51 != l_1);
127  CHECK (l_1 != l_2);
128  CHECK (l_2 == l_3); // difference not detected due to observation limit...
129  CHECK (!std::strncmp (l_2, l_3, STRING_MAX_RELEVANT ));
130  CHECK ( std::strncmp (l_2, l_3, STRING_MAX_RELEVANT+1));
131 
132  size_t h0 = hash_value (l0);
133  size_t h51 = hash_value (l51);
134  size_t h52 = hash_value (l52);
135  size_t h_1 = hash_value (l_1);
136  size_t h_2 = hash_value (l_2);
137  size_t h_3 = hash_value (l_3);
138 
139  CHECK (h0 == 0);
140  CHECK (h51 != 0);
141  CHECK (h52 != 0);
142  CHECK (h_1 != 0);
143  CHECK (h_2 != 0);
144  CHECK (h_3 != 0);
145 
146  CHECK (h51 == h52); // verify the hash function indeed stops at '\0'
147  CHECK (h51 != h_1); // share a common prefix, but the hash differs
148  CHECK (h_1 != h_2); // the single random modification is detected
149  CHECK (h_2 == h_3); // because l_2 and l_3 differ behind the fixed observation limit
150 
151  CHECK (h_1 == hash_value (l_1)); //reproducible
152  CHECK (h_2 == hash_value (l_2));
153  CHECK (h_3 == hash_value (l_3));
154  }
155  };
156 
157  LAUNCHER (SymbolHashtable_test, "function common");
158 
159 
160 }} // namespace lib::test
Definition: run.hpp:40
inline string literal This is a marker type to indicate that
Definition: symbol.hpp:76
int rani(uint bound=_iBOUND())
Definition: random.hpp:135
const size_t STRING_MAX_RELEVANT
safety guard: maximum number of chars to process.
Definition: symbol-impl.cpp:46
Implementation namespace for support and library code.
string randStr(size_t len)
create garbage string of given length
Definition: test-helper.cpp:61
Token or Atom with distinct identity.
Definition: symbol.hpp:117
Marker types to indicate a literal string and a Symbol.
Simplistic test class runner.
Tiny helper functions and shortcuts to be used everywhere Consider this header to be effectively incl...
A collection of frequently used helper functions to support unit testing.
HashVal hash_value(QueryText const &entry)
support using queries in hashtables.
Definition: query-text.cpp:52
bool contains(SEQ const &cont, typename SEQ::const_reference val)
shortcut for brute-force containment test in any sequential container
Definition: util.hpp:255