1 /*
2 ** Copyright (C) 2001-2020 by Carnegie Mellon University.
3 **
4 ** @OPENSOURCE_LICENSE_START@
5 ** See license information in ../../LICENSE.txt
6 ** @OPENSOURCE_LICENSE_END@
7 */
8
9 /* File: hashlib_tests.c: regression testing application for the hash library
10 *
11 * There's room to improve this to make the testing more thorough.
12 */
13
14 #include <silk/silk.h>
15
16 RCSIDENT("$SiLK: hashlib_tests.c ef14e54179be 2020-04-14 21:57:45Z mthomas $");
17
18 #include <silk/hashlib.h>
19
20
21 static void
hashlib_test1(void)22 hashlib_test1(
23 void)
24 {
25 int passed = 1;
26 uint32_t iKey;
27 uint32_t iValue;
28 uint32_t *key_ref, *val_ref;
29 const uint32_t max_key = 400000;
30 const int initial_table_size = 600000;
31 HashTable *test_ptr = NULL;
32 uint32_t no_value = 0xFFFFFFFF;
33 uint8_t *no_value_ptr;
34 uint32_t num_found = 0;
35 HASH_ITER iter;
36
37 printf("\n--- Testing value-based hash table\n");
38
39 /* Allocate memory for and initialize special "empty" value */
40 no_value_ptr = (uint8_t*)malloc(sizeof(iValue));
41 if (!no_value_ptr) {
42 printf("Out of memory\n");
43 exit(EXIT_FAILURE);
44 }
45 memcpy(no_value_ptr, &no_value, sizeof(iValue));
46
47 /* Create a table to test with */
48 test_ptr = hashlib_create_table(sizeof(iKey),
49 sizeof(iValue),
50 HTT_INPLACE, /* values, not pointers */
51 no_value_ptr, /* all FF means empty */
52 NULL, 0, /* No user data */
53 initial_table_size, DEFAULT_LOAD_FACTOR);
54 assert(test_ptr);
55
56 /* done with the no_value_ptr */
57 free(no_value_ptr);
58
59 /* Populate the table with integers and their doubles */
60 for (iKey = 1; iKey <= max_key; iKey++) {
61 iValue = iKey*2;
62 hashlib_insert(test_ptr, (uint8_t*)&iKey, (uint8_t**)&val_ref);
63 memcpy(val_ref, &iValue, sizeof(iValue));
64 }
65
66 /* Validate num entries */
67 if (hashlib_count_entries(test_ptr) != max_key) {
68 printf(("Error in hashlib_test1."
69 " hashlib_count_entries returned incorrect value\n"));
70 exit(EXIT_FAILURE);
71 }
72
73 printf("Table information:\n");
74 hashlib_dump_table_header(stderr, test_ptr);
75
76 printf("Testing iteration\n");
77 num_found = 0;
78 iter = hashlib_create_iterator(test_ptr);
79 while (hashlib_iterate(test_ptr, &iter, (uint8_t**)&key_ref,
80 (uint8_t**)&val_ref)
81 != ERR_NOMOREENTRIES)
82 {
83 uint32_t inv_val = (uint32_t) (*val_ref)/2;
84 num_found++;
85 if (inv_val != *key_ref) {
86 printf("%u --> %u (%u)", *key_ref, *val_ref, inv_val);
87 printf("****Incorrect value: %u != %u\n", inv_val, *key_ref);
88 exit(EXIT_FAILURE);
89 }
90 }
91
92 if (num_found != max_key) {
93 printf("Iteration failed. Expected %d entries, found %d\n", max_key,
94 num_found);
95 exit(EXIT_FAILURE);
96 }
97
98 if (passed) {
99 printf("Iteration test PASSED.\n");
100 } else {
101 printf("****Iteration test FAILED.\n");
102 }
103
104 printf("Testing lookup\n");
105 for (iKey = 1; iKey <= max_key; iKey++) {
106 uint32_t inv_val;
107 key_ref = &iKey;
108 hashlib_lookup(test_ptr, (uint8_t*) &iKey, (uint8_t**) &val_ref);
109 inv_val = (*val_ref)/2;
110 if (inv_val != *key_ref) {
111 printf("%u --> %u (%u)", *key_ref, *val_ref, inv_val);
112 printf("****Incorrect value: %u != %u\n", inv_val, *key_ref);
113 exit(EXIT_FAILURE);
114 }
115 }
116
117 if (passed) {
118 printf("Lookup test PASSED.\n");
119 } else {
120 printf("****Lookup test FAILED.\n");
121 }
122
123 hashlib_free_table(test_ptr);
124
125 }
126
127 /* NOTE: remove is not implemented. We may implement it
128 * eventually. Remove is intrinsically expensive since it requires a
129 * rehash. */
130 #if 0
131 static void
132 hashlib_test_remove(
133 void)
134 {
135 HashTable *table_ptr;
136 uint8_t *val_ptr;
137 int i, j;
138 int rv;
139 uint32_t key;
140 uint32_t removed_keys[] = {
141 152, /* -> 62 */
142 27, /* -> 62 */
143 7 /* -> 62 */
144 };
145
146 uint32_t num_present = 0;
147 uint32_t present_keys[300-sizeof(removed_keys)/4];
148 int num_removed_keys = sizeof(removed_keys)/4;
149
150 table_ptr =
151 hashlib_create_table(sizeof(uint32_t),
152 sizeof(uint32_t),
153 HTT_INPLACE, /* values, not pointers */
154 0, /* 0 value is empty */
155 NULL, 0, /* No user data */
156 300, DEFAULT_LOAD_FACTOR);
157
158 /* Add values except those in removed_keys to hash table and
159 * to present_keys array */
160 for (i = 0; i < 300; i++) {
161 uint8_t use_it_bool = 1;
162
163 /* Add it to present vals only if we're not going to remove it */
164 for (j = 0; j < num_removed_keys; j++) {
165 if (i == removed_keys[j]) {
166 use_it_bool = 0;
167 break;
168 }
169 }
170 if (use_it_bool) {
171 present_keys[num_present++] = i;
172 }
173
174 /* Add it to the table */
175 key = i;
176 rv = hashlib_insert(table_ptr, (uint8_t*) &key, (uint8_t**) &val_ptr);
177 *val_ptr = 1;
178 assert(rv==OK);
179 }
180
181 /* Remove values in removed_keys */
182 for (i = 0; i < num_removed_keys; i++) {
183 key = removed_keys[i];
184 fprintf(stderr, "Removing: %d\n", key);
185 rv = hashlib_remove(table_ptr, (uint8_t*) &key);
186 assert(rv==OK);
187 }
188
189 /* Make sure the values in present_keys are in the hash table */
190 for (i = 0; i < num_present; i++) {
191 key = present_keys[i];
192 fprintf(stderr, "Looking up %d\n", key);
193 rv = hashlib_lookup(table_ptr, (uint8_t*) &key, (uint8_t**) val_ptr);
194 if (rv != OK) {
195 fprintf(stderr, "Couldn't find key: %d\n", key);
196 hashlib_dump_table(stdout, table_ptr);
197 assert(rv==OK);
198 }
199 }
200
201 /* Make sure the removed_keys are not */
202 for (i = 0; i < num_removed_keys; i++) {
203 key = removed_keys[i];
204 fprintf(stderr, "Checking: %d. ", key);
205 rv = hashlib_lookup(table_ptr, (uint8_t*) &key, (uint8_t**) val_ptr);
206 if (rv == ERR_NOTFOUND) {
207 fprintf(stderr, "Removed.\n");
208 } else if (rv == OK) {
209 fprintf(stderr, "*** Found it. ERROR -- not removed\n");
210 assert(rv == ERR_NOTFOUND);
211 } else {
212 fprintf(stderr, "*** Found it. UNEXPECTED ERROR\n");
213 assert(rv == ERR_NOTFOUND);
214 }
215 }
216 }
217 #endif /* 0 */
218
219
main(int UNUSED (argc),char UNUSED (** argv))220 int main(
221 int UNUSED(argc),
222 char UNUSED(**argv))
223 {
224 fprintf(stdout, "Starting regression testing\n");
225
226 hashlib_test1();
227
228 /* If we reached this point, all tests were successful */
229 fprintf(stdout, "\nAll tests completed successfully.\n");
230
231 return 0;
232 }
233
234
235 /*
236 ** Local Variables:
237 ** mode:c
238 ** indent-tabs-mode:nil
239 ** c-basic-offset:4
240 ** End:
241 */
242