Line data Source code
1 : /*
2 : Authors:
3 : John Dennis <jdennis.redhat.com>
4 :
5 : Copyright (C) 2009 Red Hat
6 :
7 : This program is free software; you can redistribute it and/or modify
8 : it under the terms of the GNU Lesser General Public License as published by
9 : the Free Software Foundation; either version 3 of the License, or
10 : (at your option) any later version.
11 :
12 : This program is distributed in the hope that it will be useful,
13 : but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : GNU Lesser General Public License for more details.
16 :
17 : You should have received a copy of the GNU Lesser General Public License
18 : along with this program. If not, see <http://www.gnu.org/licenses/>.
19 : */
20 :
21 : #include <stdio.h>
22 : #include <assert.h>
23 : #include <string.h>
24 : #include <stdlib.h>
25 : #include <time.h>
26 : #include <getopt.h>
27 : #include "dhash.h"
28 :
29 : #define BUF_SIZE 1024
30 : #define DEFAULT_MAX_TEST (500)
31 : hash_entry_t *iter_result_1 = NULL;
32 : hash_entry_t *iter_result_2 = NULL;
33 :
34 : unsigned long max_test = DEFAULT_MAX_TEST;
35 : int verbose = 0;
36 :
37 0 : static const char *error_string(int error)
38 : {
39 : const char *str;
40 :
41 0 : if (IS_HASH_ERROR(error))
42 0 : return hash_error_string(error);
43 :
44 0 : if (error < 0) {
45 0 : return "Negative error codes are not supported.";
46 : }
47 :
48 0 : str = strerror(error);
49 0 : if (str == NULL) {
50 0 : return "strerror() returned NULL.";
51 : }
52 :
53 0 : return str;
54 : }
55 :
56 0 : static char *key_string(hash_key_t *key)
57 : {
58 : static char buf[BUF_SIZE];
59 :
60 0 : switch(key->type) {
61 : case HASH_KEY_ULONG:
62 0 : snprintf(buf, sizeof(buf), "key ulong = %lu", key->ul);
63 0 : break;
64 : case HASH_KEY_STRING:
65 0 : snprintf(buf, sizeof(buf), "key string = \"%s\"", key->str);
66 0 : break;
67 : default:
68 0 : snprintf(buf, sizeof(buf), "unknown key type = %d", key->type);
69 0 : break;
70 : }
71 0 : return buf;
72 : }
73 :
74 0 : static char *value_string(hash_value_t *value)
75 : {
76 : static char buf[BUF_SIZE];
77 :
78 0 : switch(value->type) {
79 : case HASH_VALUE_UNDEF:
80 0 : snprintf(buf, sizeof(buf), "value undefined");
81 0 : break;
82 : case HASH_VALUE_PTR:
83 0 : snprintf(buf, sizeof(buf), "value str = \"%s\"", (char *)value->ptr);
84 0 : break;
85 : case HASH_VALUE_INT:
86 0 : snprintf(buf, sizeof(buf), "value int = %d", value->i);
87 0 : break;
88 : case HASH_VALUE_UINT:
89 0 : snprintf(buf, sizeof(buf), "value unsigned int = %u", value->ui);
90 0 : break;
91 : case HASH_VALUE_LONG:
92 0 : snprintf(buf, sizeof(buf), "value long = %ld", value->l);
93 0 : break;
94 : case HASH_VALUE_ULONG:
95 0 : snprintf(buf, sizeof(buf), "value unsigned long = %lu", value->ul);
96 0 : break;
97 : case HASH_VALUE_FLOAT:
98 0 : snprintf(buf, sizeof(buf), "value float = %f", value->f);
99 0 : break;
100 : case HASH_VALUE_DOUBLE:
101 0 : snprintf(buf, sizeof(buf), "value double = %f", value->f);
102 0 : break;
103 : default:
104 0 : snprintf(buf, sizeof(buf), "unknown value type = %d", value->type);
105 0 : break;
106 : }
107 :
108 0 : return buf;
109 : }
110 :
111 0 : static char *entry_string(hash_entry_t *entry)
112 : {
113 : static char buf[BUF_SIZE];
114 :
115 0 : snprintf(buf, sizeof(buf), "[%s] = [%s]", key_string(&entry->key), value_string(&entry->value));
116 :
117 0 : return buf;
118 :
119 : }
120 :
121 500 : static bool callback(hash_entry_t *item, void *user_data)
122 : {
123 500 : unsigned long *callback_count = (unsigned long *)user_data;
124 :
125 500 : iter_result_1[*callback_count] = *item;
126 :
127 500 : (*callback_count)++;
128 :
129 500 : if (verbose) printf("%s\n", entry_string(item));
130 500 : return true;
131 : }
132 :
133 502 : static void delete_callback(hash_entry_t *item, hash_destroy_enum type,
134 : void *pvt)
135 : {
136 502 : if (item->value.type == HASH_VALUE_PTR) free(item->value.ptr);
137 502 : }
138 :
139 : typedef struct test_val_t {
140 : long val;
141 : char *str;
142 : } test_val_t;
143 :
144 :
145 1 : int main(int argc, char **argv)
146 : {
147 1 : test_val_t *test = NULL;
148 : long i, j, k;
149 : bool duplicate;
150 : long val;
151 : int status;
152 : hash_value_t value;
153 : hash_value_t old_value;
154 : hash_value_t new_value;
155 : hash_key_t key;
156 : char buf[BUF_SIZE];
157 1 : hash_table_t *table = NULL;
158 1 : unsigned long callback_count = 0;
159 1 : unsigned long table_size = 0;
160 1 : unsigned int seed = time(0);
161 1 : unsigned int directory_bits = 0;
162 1 : unsigned int segment_bits = 0;
163 1 : unsigned long min_load_factor = HASH_DEFAULT_MIN_LOAD_FACTOR;
164 1 : unsigned long max_load_factor = HASH_DEFAULT_MAX_LOAD_FACTOR;
165 :
166 : while (1) {
167 : int arg;
168 1 : int option_index = 0;
169 : static struct option long_options[] = {
170 : {"count", 1, 0, 'c'},
171 : {"verbose", 1, 0, 'v'},
172 : {"quiet", 1, 0, 'q'},
173 : {"table-size", 1, 0, 't'},
174 : {"directory-bits", 1, 0, 'd'},
175 : {"segment-bits", 1, 0, 's'},
176 : {"min-load-factor", 1, 0, 'l'},
177 : {"max-load-factor", 1, 0, 'h'},
178 : {"seed", 1, 0, 'r'},
179 : {0, 0, 0, 0}
180 : };
181 :
182 1 : arg = getopt_long(argc, argv, "c:vqt:d:s:l:h:r:",
183 : long_options, &option_index);
184 1 : if (arg == -1) break;
185 :
186 0 : switch (arg) {
187 : case 'c':
188 0 : max_test = strtoul(optarg, NULL, 0);
189 0 : break;
190 : case 'v':
191 0 : verbose = 1;
192 0 : break;
193 : case 'q':
194 0 : verbose = 0;
195 0 : break;
196 : case 't':
197 0 : table_size = strtoul(optarg, NULL, 0);
198 0 : break;
199 : case 'd':
200 0 : directory_bits = atoi(optarg);
201 0 : break;
202 : case 's':
203 0 : segment_bits = atoi(optarg);
204 0 : break;
205 : case 'l':
206 0 : min_load_factor = strtoul(optarg, NULL, 0);
207 0 : break;
208 : case 'h':
209 0 : max_load_factor = strtoul(optarg, NULL, 0);
210 0 : break;
211 : case 'r':
212 0 : seed = strtoul(optarg, NULL, 0);
213 0 : break;
214 : }
215 0 : }
216 :
217 1 : if ((test = (test_val_t *) calloc(max_test, sizeof(test_val_t))) == NULL) {
218 0 : fprintf(stderr, "Failed to allocate test array\n");
219 0 : exit(1);
220 : }
221 1 : if ((iter_result_1 = (hash_entry_t *) calloc(max_test, sizeof(hash_entry_t))) == NULL) {
222 0 : fprintf(stderr, "Failed to allocate iter_result_1 array\n");
223 0 : exit(1);
224 : }
225 1 : if ((iter_result_2 = (hash_entry_t *) calloc(max_test, sizeof(hash_entry_t))) == NULL) {
226 0 : fprintf(stderr, "Failed to allocate iter_result_2 array\n");
227 0 : exit(1);
228 : }
229 :
230 :
231 : /* Initialize the random number generator */
232 1 : srandom(seed);
233 1 : printf("random seed: %#x\n", seed);
234 :
235 : /* Create the hash table as small as possible to exercise growth */
236 1 : if ((status = hash_create_ex(table_size, &table,
237 : directory_bits, segment_bits,
238 : min_load_factor, max_load_factor,
239 : NULL, NULL, NULL,
240 : delete_callback, NULL)) != HASH_SUCCESS) {
241 0 : fprintf(stderr, "table creation failed at line %d (%s)\n", __LINE__, error_string(status));
242 0 : exit(1);
243 : }
244 :
245 : /* Initialize the array of test values */
246 501 : for (i = 0; i < max_test; i++) {
247 : /* Get random value, make sure it's unique */
248 500 : duplicate = true;
249 1500 : while (duplicate) {
250 500 : duplicate = false;
251 500 : val = random();
252 125250 : for (j = 0; j < i; j++) {
253 124750 : if (test[j].val == val) {
254 0 : duplicate = true;
255 0 : break;
256 : }
257 : }
258 : }
259 500 : test[i].val = val;
260 : /* If the value is odd we'll use a string as the key,
261 : * otherwise we'll use an unsigned long as the key */
262 500 : if (test[i].val & 1) {
263 251 : key.type = HASH_KEY_STRING;
264 251 : snprintf(buf, BUF_SIZE, "%ld", test[i].val);
265 251 : test[i].str = strdup(buf);
266 : }
267 : }
268 :
269 1 : printf("Completed building test values, beginning test ...\n");
270 :
271 : /* Enter all the test values into the hash table */
272 501 : for (i = 0; i < max_test; i++) {
273 500 : if (test[i].val & 1) {
274 251 : key.type = HASH_KEY_STRING;
275 251 : key.str = test[i].str;
276 251 : value.type = HASH_VALUE_PTR;
277 251 : value.ptr = (void *) strdup(test[i].str);
278 : }
279 : else {
280 249 : key.type = HASH_KEY_ULONG;
281 249 : key.ul = test[i].val;
282 249 : value.type = HASH_VALUE_LONG;
283 249 : value.l = test[i].val;
284 : }
285 :
286 500 : if (hash_has_key(table, &key)) {
287 0 : fprintf(stderr, "Error: %ld already in table when inserting, i = %lu, at line %d\n",
288 0 : test[i].val, i, __LINE__);
289 0 : exit(1);
290 : }
291 500 : if ((status = hash_enter(table, &key, &value)) != HASH_SUCCESS) {
292 0 : fprintf(stderr, "Error: %ld failed insertion at line %d (%s) \n",
293 0 : test[i].val, __LINE__, error_string(status));
294 0 : exit(1);
295 : }
296 : }
297 :
298 : /* Now visit each entry in the table using a callback iterator,
299 : * store what we found in iter_result_1 for testing the iterator object later on */
300 1 : if (verbose) printf("callback iterate:\n");
301 1 : callback_count = 0;
302 1 : if ((status = hash_iterate(table, callback, &callback_count)) != HASH_SUCCESS) {
303 0 : fprintf(stderr, "hash_iterate failed at line %d (%s)\n", __LINE__, error_string(status));
304 0 : exit(1);
305 : }
306 1 : if (verbose) printf("hash_count=%ld, callback_count=%ld\n", hash_count(table), callback_count);
307 :
308 1 : if (hash_count(table) != callback_count) {
309 0 : fprintf(stderr, "Error: hash_count(%ld) != callback_count(%ld) at line %d\n",
310 : hash_count(table), callback_count, __LINE__);
311 0 : exit(1);
312 : }
313 :
314 : /* Now vist each entry in the table using an iterator object */
315 : {
316 : struct hash_iter_context_t *iter;
317 : unsigned long n_items;
318 : hash_entry_t *entry;
319 :
320 1 : if (verbose) printf("iter iterate:\n");
321 :
322 1 : n_items = 0;
323 1 : iter = new_hash_iter_context(table);
324 :
325 502 : while ((entry = iter->next(iter)) != NULL) {
326 500 : if (verbose) printf("%s\n", entry_string(entry));
327 500 : iter_result_2[n_items] = *entry;
328 500 : n_items++;
329 : }
330 1 : if (verbose) printf("hash_count=%ld, n_items=%ld\n", hash_count(table), n_items);
331 :
332 1 : if (hash_count(table) != n_items) {
333 0 : fprintf(stderr, "Error: hash_count(%ld) != n_items(%ld) at line %d\n",
334 : hash_count(table), n_items, __LINE__);
335 0 : exit(1);
336 : }
337 1 : free(iter);
338 : }
339 :
340 : /* Both iterators should have visited each item in the same order, verify ... */
341 501 : for (i = 0; i < max_test; i++) {
342 500 : if (memcmp(&iter_result_1[i], &iter_result_2[i], sizeof(iter_result_1[0])) != 0) {
343 0 : fprintf(stderr, "Error: iter_result_1[%lu] != iter_result_2[%lu] at line %d\n",
344 : i, i, __LINE__);
345 0 : exit(1);
346 : }
347 : }
348 :
349 : /* Get an array of keys in the table, print them out */
350 : {
351 : unsigned long count;
352 : hash_key_t *keys;
353 :
354 1 : if (verbose) printf("\nhash_keys:\n");
355 1 : if ((status = hash_keys(table, &count, &keys)) != HASH_SUCCESS) {
356 0 : fprintf(stderr, "hash_keys failed at line %d (%s)\n",
357 : __LINE__, error_string(status));
358 0 : exit(1);
359 : }
360 :
361 1 : if (hash_count(table) != count) {
362 0 : fprintf(stderr, "Error: hash_count(%ld) != hash_keys() count(%ld) at line %d\n",
363 : hash_count(table), count, __LINE__);
364 0 : exit(1);
365 : }
366 :
367 501 : for (i = 0; i < count; i++) {
368 500 : if (verbose) printf("%s\n", key_string(&keys[i]));
369 : }
370 1 : free(keys);
371 : }
372 :
373 : /* Get an array of values in the table, print them out */
374 : {
375 : unsigned long count;
376 : hash_value_t *values;
377 :
378 1 : if (verbose) printf("\nhash_values:\n");
379 1 : hash_values(table, &count, &values);
380 :
381 1 : if (hash_count(table) != count) {
382 0 : fprintf(stderr, "Error: hash_count(%ld) != hash_values() count(%ld) at line %d\n",
383 : hash_count(table), count, __LINE__);
384 0 : exit(1);
385 : }
386 :
387 501 : for (i = 0; i < count; i++) {
388 500 : if (verbose) printf("%s\n", value_string(&values[i]));
389 : }
390 1 : free(values);
391 : }
392 :
393 : /* Get an array of items in the table, print them out */
394 : {
395 : unsigned long count;
396 : hash_entry_t *entries;
397 :
398 1 : if (verbose) printf("\nhash_entries:\n");
399 1 : hash_entries(table, &count, &entries);
400 :
401 1 : if (hash_count(table) != count) {
402 0 : fprintf(stderr, "Error: hash_count(%ld) != hash_entries() count(%ld) at line %d\n",
403 : hash_count(table), count, __LINE__);
404 0 : exit(1);
405 : }
406 :
407 501 : for (i = 0; i < count; i++) {
408 500 : if (verbose) printf("%s\n", entry_string(&entries[i]));
409 : }
410 1 : free(entries);
411 : }
412 :
413 : /* See if we can find every key */
414 501 : for (i = max_test - 1; i >= 0; i--) {
415 500 : if (test[i].val & 1) {
416 251 : key.type = HASH_KEY_STRING;
417 251 : key.str = test[i].str;
418 : }
419 : else {
420 249 : key.type = HASH_KEY_ULONG;
421 249 : key.ul = test[i].val;
422 : }
423 500 : if ((status = hash_lookup(table, &key, &value)) != HASH_SUCCESS) {
424 0 : fprintf(stderr, "Error: failed first lookup for value %ld at index %ld at line %d (%s)\n",
425 0 : test[i].val, i, __LINE__, error_string(status));
426 0 : exit(1);
427 : }
428 : else {
429 500 : switch(value.type) {
430 : case HASH_VALUE_PTR:
431 251 : if (strcmp((char *)value.ptr, test[i].str) != 0) {
432 0 : fprintf(stderr, "Error: corrupt ptr data for %lu at line %d\n", i, __LINE__);
433 0 : exit(1);
434 : }
435 251 : break;
436 : case HASH_VALUE_LONG:
437 249 : if (value.l != test[i].val) {
438 0 : fprintf(stderr, "Error: corrupt long data for %lu at line %d\n", i, __LINE__);
439 0 : exit(1);
440 : }
441 249 : break;
442 : default:
443 0 : fprintf(stderr, "Error: unknown value type for %lu\n", i);
444 0 : break;
445 : }
446 : }
447 : }
448 :
449 : /* Update an entry */
450 1 : if (test[0].val & 1) {
451 1 : key.type = HASH_KEY_STRING;
452 1 : key.str = test[0].str;
453 : } else {
454 0 : key.type = HASH_KEY_ULONG;
455 0 : key.ul = test[0].val;
456 : }
457 :
458 1 : if ((status = hash_lookup(table, &key, &value)) != HASH_SUCCESS) {
459 0 : fprintf(stderr, "Error: failed lookup for value %ld, at line %d (%s)\n",
460 : test[0].val, __LINE__, error_string(status));
461 0 : exit(1);
462 : }
463 :
464 1 : old_value.type = value.type;
465 1 : switch (value.type) {
466 : case HASH_VALUE_LONG:
467 0 : old_value.ul = value.ul;
468 0 : break;
469 : case HASH_VALUE_PTR:
470 1 : old_value.ptr = strdup(value.ptr);
471 1 : break;
472 : default:
473 0 : fprintf(stderr, "Error: unsupported value type for update.\n");
474 0 : exit(1);
475 : }
476 :
477 1 : value.type = HASH_VALUE_PTR;
478 1 : value.ptr = (void *) strdup("Updated");
479 :
480 1 : if ((status = hash_enter(table, &key, &value)) != HASH_SUCCESS) {
481 0 : fprintf(stderr, "Error: %ld failed insertion at line %d (%s) \n",
482 : test[0].val, __LINE__, error_string(status));
483 0 : exit(1);
484 : }
485 :
486 1 : if ((status = hash_lookup(table, &key, &new_value)) != HASH_SUCCESS) {
487 0 : fprintf(stderr, "Error: failed lookup for value %ld, at line %d (%s)\n",
488 : test[0].val, __LINE__, error_string(status));
489 0 : exit(1);
490 : }
491 :
492 1 : if (value.type == new_value.type) {
493 1 : if (strcmp(value.ptr, new_value.ptr) != 0) {
494 0 : fprintf(stderr, "Error: Updated value is not correct, "
495 : "expected (%s) got (%s), at line %d\n",
496 0 : (char *) value.ptr, (char *) new_value.ptr, __LINE__);
497 0 : exit(1);
498 : }
499 : } else {
500 0 : fprintf(stderr, "Error: Updated value is not correct, "
501 : "expected type (%d) got (%d), at line %d\n",
502 0 : value.type, new_value.type, __LINE__);
503 0 : exit(1);
504 : }
505 :
506 1 : if ((status = hash_enter(table, &key, &old_value)) != HASH_SUCCESS) {
507 0 : fprintf(stderr, "Error: %ld failed insertion at line %d (%s) \n",
508 : test[0].val, __LINE__, error_string(status));
509 0 : exit(1);
510 : }
511 :
512 :
513 : /*
514 : * Delete a key, make sure we can't find it, assure we can find all other
515 : * keys.
516 : */
517 501 : for (i = 0; i < max_test; i++) {
518 500 : if (test[i].val & 1) {
519 251 : key.type = HASH_KEY_STRING;
520 251 : key.str = test[i].str;
521 : }
522 : else {
523 249 : key.type = HASH_KEY_ULONG;
524 249 : key.ul = test[i].val;
525 : }
526 :
527 500 : if ((status = hash_lookup(table, &key, &value)) != HASH_SUCCESS) {
528 0 : fprintf(stderr, "Error: failed delete lookup for value %ld at index %ld at line %d (%s)\n",
529 0 : test[i].val, i, __LINE__, error_string(status));
530 0 : exit(1);
531 : }
532 :
533 500 : if ((status = hash_delete(table, &key)) != HASH_SUCCESS) {
534 0 : fprintf(stderr, "Error: %ld not in table when deleting, i = %lu at line %d (%s)\n",
535 0 : test[i].val, i, __LINE__, error_string(status));
536 0 : exit(1);
537 : }
538 :
539 500 : if (hash_lookup(table, &key, &value) != HASH_ERROR_KEY_NOT_FOUND) {
540 0 : fprintf(stderr, "Error: found in table after deletion, value = %ld at index %ld at line %d\n",
541 0 : test[i].val, i, __LINE__);
542 0 : exit(1);
543 : }
544 : /* See if we can find all remaining keys */
545 125250 : for (k = i + 1; k < max_test; k++) {
546 124750 : if (test[k].val & 1) {
547 65268 : key.type = HASH_KEY_STRING;
548 65268 : key.str = test[k].str;
549 : } else {
550 59482 : key.type = HASH_KEY_ULONG;
551 59482 : key.ul = test[k].val;
552 : }
553 124750 : if ((status = hash_lookup(table, &key, &value)) != HASH_SUCCESS) {
554 0 : fprintf(stderr, "Error: failed second lookup for value %ld, i = %lu k = %lu at line %d (%s)\n",
555 0 : test[k].val, i, k, __LINE__, error_string(status));
556 0 : exit(1);
557 : } else {
558 124750 : switch(value.type) {
559 : case HASH_VALUE_PTR:
560 65268 : if (strcmp((char *)value.ptr, test[k].str) != 0) {
561 0 : fprintf(stderr, "Error: corrupt ptr data for %lu at line %d\n", k, __LINE__);
562 0 : exit(1);
563 : }
564 65268 : break;
565 : case HASH_VALUE_LONG:
566 59482 : if (value.l != test[k].val) {
567 0 : fprintf(stderr, "Error: corrupt long data for %lu at line %d\n", k, __LINE__);
568 0 : exit(1);
569 : }
570 59482 : break;
571 : default:
572 0 : fprintf(stderr, "Error: unknown value type (%d) for %lu\n", value.type, k);
573 0 : break;
574 : }
575 : }
576 : }
577 : }
578 :
579 1 : if (verbose) printf("\n");
580 :
581 : #ifdef HASH_STATISTICS
582 : {
583 : hash_statistics_t stats;
584 :
585 1 : if ((status = hash_get_statistics(table, &stats)) != HASH_SUCCESS) {
586 0 : fprintf(stderr, "Error: could not get statistics at line %d (%s)\n",
587 : __LINE__, error_string(status));
588 0 : exit(1);
589 : }
590 :
591 2 : printf("Statistics: Accesses = %ld, Collisions = %ld, Collision Rate = %.2f, Expansions = %ld, Contractions = %ld\n",
592 : stats.hash_accesses, stats.hash_collisions,
593 1 : ((float)stats.hash_collisions / (float)stats.hash_accesses),
594 : stats.table_expansions, stats.table_contractions);
595 : }
596 : #endif
597 :
598 1 : if ((status = hash_destroy(table)) != HASH_SUCCESS) {
599 0 : fprintf(stderr, "table destruction failed at line %d (%s)\n",
600 : __LINE__, error_string(status));
601 0 : exit(1);
602 : }
603 :
604 501 : for (i = 0; i < max_test; i++) {
605 500 : if (test[i].val & 1) {
606 251 : free(test[i].str);
607 : }
608 : }
609 1 : free(test);
610 1 : free(iter_result_1);
611 1 : free(iter_result_2);
612 :
613 1 : printf("Successfully tested %lu values\n", max_test);
614 1 : return 0;
615 : }
|
