From 746391a1719659161f026684193b3fb04593f563 Mon Sep 17 00:00:00 2001 From: Stephen Gallagher Date: Thu, 7 Jan 2010 15:11:07 -0500 Subject: Split off libdhash into a shared library Right now, the pkg-config checks for the system version of libdhash are forcibly disabled, requiring the SSSD to build it from its own tree. In the future, when we split the libraries off from the SSSD, it will be easy to switch this check to the external library. --- common/dhash/Makefile.am | 22 +- common/dhash/README | 1 + common/dhash/configure.ac | 2 +- common/dhash/dhash_example.c | 118 -------- common/dhash/dhash_test.c | 490 ---------------------------------- common/dhash/examples/dhash_example.c | 118 ++++++++ common/dhash/examples/dhash_test.c | 490 ++++++++++++++++++++++++++++++++++ 7 files changed, 624 insertions(+), 617 deletions(-) create mode 100644 common/dhash/README delete mode 100644 common/dhash/dhash_example.c delete mode 100644 common/dhash/dhash_test.c create mode 100644 common/dhash/examples/dhash_example.c create mode 100644 common/dhash/examples/dhash_test.c (limited to 'common/dhash') diff --git a/common/dhash/Makefile.am b/common/dhash/Makefile.am index de3c34d20..d5a561871 100644 --- a/common/dhash/Makefile.am +++ b/common/dhash/Makefile.am @@ -8,22 +8,28 @@ endif ACLOCAL_AMFLAGS = -I m4 pkgconfigdir = $(libdir)/pkgconfig -dist_noinst_DATA = \ - dhash.pc \ - m4 +dist_pkgconfig_DATA = dhash.pc -noinst_LTLIBRARIES = libdhash.la -libdhash_la_SOURCES = \ - dhash.c \ - dhash.h +dist_noinst_DATA = m4 + +dist_include_HEADERS = dhash.h + +lib_LTLIBRARIES = libdhash.la +libdhash_la_SOURCES = dhash.c +libdhash_la_LDFLAGS = \ + -version-info 1:0:0 check_PROGRAMS = dhash_test dhash_example TESTS = $(check_PROGRAMS) +dhash_test_SOURCES = examples/dhash_test.c dhash_test_LDADD = dhash.o + +dhash_example_SOURCES = examples/dhash_example.c dhash_example_LDADD = dhash.o examplesdir = $(docdir)/examples -dist_noinst_DATA += dhash_test.c dhash_example.c +dist_examples_DATA = examples/dhash_test.c examples/dhash_example.c +dist_doc_DATA = README tests: all $(check_PROGRAMS) diff --git a/common/dhash/README b/common/dhash/README new file mode 100644 index 000000000..bee5024ee --- /dev/null +++ b/common/dhash/README @@ -0,0 +1 @@ +Documentation for libdhash can be found in dhash.h diff --git a/common/dhash/configure.ac b/common/dhash/configure.ac index bd2102877..1012afbbd 100644 --- a/common/dhash/configure.ac +++ b/common/dhash/configure.ac @@ -1,4 +1,4 @@ -AC_INIT([dhash], [0.3.3], [jdennis@redhat.com]) +AC_INIT([dhash], [0.4.0], [jdennis@redhat.com]) AC_CONFIG_SRCDIR([dhash.c]) AC_CONFIG_AUX_DIR([build]) AM_INIT_AUTOMAKE([-Wall -Werror foreign]) diff --git a/common/dhash/dhash_example.c b/common/dhash/dhash_example.c deleted file mode 100644 index 7ed01d71a..000000000 --- a/common/dhash/dhash_example.c +++ /dev/null @@ -1,118 +0,0 @@ -#include -#include -#include -#include -#include "dhash.h" - -struct my_data_t { - int foo; - char bar[128]; -}; - -void delete_callback(hash_entry_t *entry, hash_destroy_enum type, void *pvt) -{ - if (entry->value.type == HASH_VALUE_PTR) free(entry->value.ptr); -} - -bool visit_callback(hash_entry_t *entry, void *user_data) -{ - unsigned long *count = (unsigned long *)user_data; - struct my_data_t *my_data = (struct my_data_t *) entry->value.ptr; - - (*count)++; - - printf("%s = [foo=%d bar=%s]\n", entry->key.str, my_data->foo, my_data->bar); - return true; -} - -struct my_data_t *new_data(int foo, const char *bar) -{ - struct my_data_t *my_data = malloc(sizeof(struct my_data_t)); - my_data->foo = foo; - strncpy(my_data->bar, bar, sizeof(my_data->bar)); - return my_data; -} -int main(int argc, char **argv) -{ - static hash_table_t *table = NULL; - hash_key_t key, *keys; - hash_value_t value; - struct hash_iter_context_t *iter; - hash_entry_t *entry; - unsigned long i, n_entries; - int error; - struct my_data_t *my_data = new_data(1024, "Hello World!"); - unsigned long count; - - /* Create a hash table */ - error = hash_create(10, &table, delete_callback, NULL); - if (error != HASH_SUCCESS) { - fprintf(stderr, "cannot create hash table (%s)\n", hash_error_string(error)); - return error; - } - - /* Enter a key named "My Data" and specify it's value as a pointer to my_data */ - key.type = HASH_KEY_STRING; - key.str = strdup("My Data"); - value.type = HASH_VALUE_PTR; - value.ptr = my_data; - - if ((error = hash_enter(table, &key, &value)) != HASH_SUCCESS) { - fprintf(stderr, "cannot add to table \"%s\" (%s)\n", key.str, hash_error_string(error)); - return error; - } - - /* Get a list of keys and print them out, free the list when we're done */ - if ((error = hash_keys(table, &count, &keys)) != HASH_SUCCESS) { - fprintf(stderr, "cannot get key list (%s)\n", hash_error_string(error)); - return error; - } - - for (i = 0; i < count; i++) - printf("key: %s\n", keys[i].str); - free(keys); - - /* Lookup the key named "My Data" */ - key.type = HASH_KEY_STRING; - key.str = strdup("My Data"); - if ((error = hash_lookup(table, &key, &value)) != HASH_SUCCESS) { - fprintf(stderr, "cannot find key \"%s\" (%s)\n", key.str, hash_error_string(error)); - } - - /* Visit each entry in the table, callback will increment count on each visit */ - printf("Iterate using callback\n"); - count = 0; - hash_iterate(table, visit_callback, &count); - - /* Assure number of visits equal the table size */ - assert(count == hash_count(table)); - - /* Visit each entry using iterator object */ - printf("Iterate using iterator\n"); - n_entries = 0; - iter = new_hash_iter_context(table); - while ((entry = iter->next(iter)) != NULL) { - struct my_data_t *data = (struct my_data_t *) entry->value.ptr; - - printf("%s = [foo=%d bar=%s]\n", entry->key.str, data->foo, data->bar); - n_entries++; - } - free(iter); - /* Assure number of visits equal the table size */ - assert(n_entries == hash_count(table)); - - /* Remove the entry, deletion callback will be invoked */ - key.type = HASH_KEY_STRING; - key.str = strdup("My Data"); - if ((error = hash_delete(table, &key)) != HASH_SUCCESS) { - fprintf(stderr, "cannot delete from table (%s)\n", hash_error_string(error)); - } - - /* Assure key is no longer in table */ - assert (!hash_has_key(table, &key)); - - /* Free the table */ - hash_destroy(table); - - return 0; -} diff --git a/common/dhash/dhash_test.c b/common/dhash/dhash_test.c deleted file mode 100644 index 27eb88d52..000000000 --- a/common/dhash/dhash_test.c +++ /dev/null @@ -1,490 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include "dhash.h" - -#define DEFAULT_MAX_TEST (500) -hash_entry_t *iter_result_1 = NULL; -hash_entry_t *iter_result_2 = NULL; - -unsigned long max_test = DEFAULT_MAX_TEST; -int verbose = 0; - -const char *error_string(int error) -{ - if (IS_HASH_ERROR(error)) - return hash_error_string(error); - - return strerror(error); -} - -char *key_string(hash_key_t *key) -{ - static char buf[1024]; - - switch(key->type) { - case HASH_KEY_ULONG: - snprintf(buf, sizeof(buf), "key ulong = %lu", key->ul); - break; - case HASH_KEY_STRING: - snprintf(buf, sizeof(buf), "key string = \"%s\"", key->str); - break; - default: - snprintf(buf, sizeof(buf), "unknown key type = %d", key->type); - break; - } - return buf; -} - -char *value_string(hash_value_t *value) -{ - static char buf[1024]; - - switch(value->type) { - case HASH_VALUE_UNDEF: - snprintf(buf, sizeof(buf), "value undefined"); - break; - case HASH_VALUE_PTR: - snprintf(buf, sizeof(buf), "value str = \"%s\"", (char *)value->ptr); - break; - case HASH_VALUE_INT: - snprintf(buf, sizeof(buf), "value int = %d", value->i); - break; - case HASH_VALUE_UINT: - snprintf(buf, sizeof(buf), "value unsigned int = %u", value->ui); - break; - case HASH_VALUE_LONG: - snprintf(buf, sizeof(buf), "value long = %ld", value->l); - break; - case HASH_VALUE_ULONG: - snprintf(buf, sizeof(buf), "value unsigned long = %lu", value->ul); - break; - case HASH_VALUE_FLOAT: - snprintf(buf, sizeof(buf), "value float = %f", value->f); - break; - case HASH_VALUE_DOUBLE: - snprintf(buf, sizeof(buf), "value double = %f", value->f); - break; - default: - snprintf(buf, sizeof(buf), "unknown value type = %d", value->type); - break; - } - - return buf; -} - -char *entry_string(hash_entry_t *entry) -{ - static char buf[1024]; - - snprintf(buf, sizeof(buf), "[%s] = [%s]", key_string(&entry->key), value_string(&entry->value)); - - return buf; - -} - -bool callback(hash_entry_t *item, void *user_data) -{ - unsigned long *callback_count = (unsigned long *)user_data; - - iter_result_1[*callback_count] = *item; - - (*callback_count)++; - - if (verbose) printf("%s\n", entry_string(item)); - return true; -} - -void delete_callback(hash_entry_t *item, hash_destroy_enum type, void *pvt) -{ - if (item->value.type == HASH_VALUE_PTR) free(item->value.ptr); -} - -typedef struct test_val_t { - long val; - char *str; -} test_val_t; - - -int main(int argc, char **argv) -{ - test_val_t *test = NULL; - long i, k; - int status; - hash_value_t value; - hash_key_t key; - char buf[1024]; - hash_table_t *table = NULL; - unsigned long callback_count = 0; - unsigned int directory_bits = HASH_DEFAULT_DIRECTORY_BITS; - unsigned int segment_bits = HASH_DEFAULT_SEGMENT_BITS; - unsigned long min_load_factor = HASH_DEFAULT_MIN_LOAD_FACTOR; - unsigned long max_load_factor = HASH_DEFAULT_MAX_LOAD_FACTOR; - - while (1) { - int arg; - int option_index = 0; - static struct option long_options[] = { - {"count", 1, 0, 'c'}, - {"verbose", 1, 0, 'v'}, - {"quiet", 1, 0, 'q'}, - {"directory-bits", 1, 0, 'd'}, - {"segment-bits", 1, 0, 's'}, - {"min-load-factor", 1, 0, 'l'}, - {"max-load-factor", 1, 0, 'h'}, - {0, 0, 0, 0} - }; - - arg = getopt_long(argc, argv, "c:vqd:s:l:h:", - long_options, &option_index); - if (arg == -1) break; - - switch (arg) { - case 'c': - max_test = atol(optarg); - break; - case 'v': - verbose = 1; - break; - case 'q': - verbose = 0; - break; - case 'd': - directory_bits = atoi(optarg); - break; - case 's': - segment_bits = atoi(optarg); - break; - case 'l': - min_load_factor = atol(optarg); - break; - case 'h': - max_load_factor = atol(optarg); - break; - } - } - - if ((test = (test_val_t *) calloc(max_test, sizeof(test_val_t))) == NULL) { - fprintf(stderr, "Failed to allocate test array\n"); - exit(1); - } - if ((iter_result_1 = (hash_entry_t *) calloc(max_test, sizeof(hash_entry_t))) == NULL) { - fprintf(stderr, "Failed to allocate iter_result_1 array\n"); - exit(1); - } - if ((iter_result_2 = (hash_entry_t *) calloc(max_test, sizeof(hash_entry_t))) == NULL) { - fprintf(stderr, "Failed to allocate iter_result_2 array\n"); - exit(1); - } - - - /* Initialize the random number generator */ - srandom(time(0)); - - /* Create the hash table as small as possible to exercise growth */ - if ((status = hash_create_ex(1, &table, - directory_bits, segment_bits, - min_load_factor, max_load_factor, - NULL, NULL, NULL, - delete_callback, NULL)) != HASH_SUCCESS) { - fprintf(stderr, "table creation failed at line %d (%s)\n", __LINE__, error_string(status)); - exit(1); - } - - /* Initialize the array of test values */ - for (i = 0; i < max_test; i++) { - test[i].val = random(); - /* If the value is odd we'll use a string as the key, - * otherwise we'll use an unsigned long as the key */ - if (test[i].val & 1) { - key.type = HASH_KEY_STRING; - sprintf(buf, "%ld", test[i].val); - test[i].str = strdup(buf); - } - } - - /* Enter all the test values into the hash table */ - for (i = 0; i < max_test; i++) { - if (test[i].val & 1) { - key.type = HASH_KEY_STRING; - key.str = test[i].str; - value.type = HASH_VALUE_PTR; - value.ptr = (void *) strdup(test[i].str); - } - else { - key.type = HASH_KEY_ULONG; - key.ul = test[i].val; - value.type = HASH_VALUE_LONG; - value.l = test[i].val; - } - - if (hash_has_key(table, &key)) { - fprintf(stderr, "Error: %ld already in table when inserting, i = %lu, at line %d\n", - test[i].val, i, __LINE__); - exit(1); - } - if ((status = hash_enter(table, &key, &value)) != HASH_SUCCESS) { - fprintf(stderr, "Error: %ld failed insertion at line %d (%s) \n", - test[i].val, __LINE__, error_string(status)); - exit(1); - } - } - - /* Now visit each entry in the table using a callback iterator, - * store what we found in iter_result_1 for testing the iterator object later on */ - if (verbose) printf("callback iterate:\n"); - callback_count = 0; - if ((status = hash_iterate(table, callback, &callback_count)) != HASH_SUCCESS) { - fprintf(stderr, "hash_iterate failed at line %d (%s)\n", __LINE__, error_string(status)); - exit(1); - } - if (verbose) printf("hash_count=%ld, callback_count=%ld\n", hash_count(table), callback_count); - - if (hash_count(table) != callback_count) { - fprintf(stderr, "Error: hash_count(%ld) != callback_count(%ld) at line %d\n", - hash_count(table), callback_count, __LINE__); - exit(1); - } - - /* Now vist each entry in the table using an iterator object */ - { - struct hash_iter_context_t *iter; - unsigned long n_items; - hash_entry_t *entry; - - if (verbose) printf("iter iterate:\n"); - - n_items = 0; - iter = new_hash_iter_context(table); - - while ((entry = iter->next(iter)) != NULL) { - if (verbose) printf("%s\n", entry_string(entry)); - iter_result_2[n_items] = *entry; - n_items++; - } - if (verbose) printf("hash_count=%ld, n_items=%ld\n", hash_count(table), n_items); - - if (hash_count(table) != n_items) { - fprintf(stderr, "Error: hash_count(%ld) != n_items(%ld) at line %d\n", - hash_count(table), n_items, __LINE__); - exit(1); - } - free(iter); - } - - /* Both iterators should have visited each item in the same order, verify ... */ - for (i = 0; i < max_test; i++) { - if (memcmp(&iter_result_1[i], &iter_result_2[i], sizeof(iter_result_1[0])) != 0) { - fprintf(stderr, "Error: iter_result_1[%lu] != iter_result_2[%lu] at line %d\n", - i, i, __LINE__); - exit(1); - } - } - - /* Get an array of keys in the table, print them out */ - { - unsigned long count; - hash_key_t *keys; - - if (verbose) printf("\nhash_keys:\n"); - if ((status = hash_keys(table, &count, &keys)) != HASH_SUCCESS) { - fprintf(stderr, "hash_keys failed at line %d (%s)\n", - __LINE__, error_string(status)); - exit(1); - } - - if (hash_count(table) != count) { - fprintf(stderr, "Error: hash_count(%ld) != hash_keys() count(%ld) at line %d\n", - hash_count(table), count, __LINE__); - exit(1); - } - - for (i = 0; i < count; i++) { - if (verbose) printf("%s\n", key_string(&keys[i])); - } - free(keys); - } - - /* Get an array of values in the table, print them out */ - { - unsigned long count; - hash_value_t *values; - - if (verbose) printf("\nhash_values:\n"); - hash_values(table, &count, &values); - - if (hash_count(table) != count) { - fprintf(stderr, "Error: hash_count(%ld) != hash_values() count(%ld) at line %d\n", - hash_count(table), count, __LINE__); - exit(1); - } - - for (i = 0; i < count; i++) { - if (verbose) printf("%s\n", value_string(&values[i])); - } - free(values); - } - - /* Get an array of items in the table, print them out */ - { - unsigned long count; - hash_entry_t *entries; - - if (verbose) printf("\nhash_entries:\n"); - hash_entries(table, &count, &entries); - - if (hash_count(table) != count) { - fprintf(stderr, "Error: hash_count(%ld) != hash_entries() count(%ld) at line %d\n", - hash_count(table), count, __LINE__); - exit(1); - } - - for (i = 0; i < count; i++) { - if (verbose) printf("%s\n", entry_string(&entries[i])); - } - free(entries); - } - - /* See if we can find every key */ - for (i = max_test - 1; i >= 0; i--) { - if (test[i].val & 1) { - key.type = HASH_KEY_STRING; - key.str = test[i].str; - } - else { - key.type = HASH_KEY_ULONG; - key.ul = test[i].val; - } - if ((status = hash_lookup(table, &key, &value)) != HASH_SUCCESS) { - fprintf(stderr, "Error: failed first lookup for value %ld at index %ld at line %d (%s)\n", - test[i].val, i, __LINE__, error_string(status)); - exit(1); - } - else { - switch(value.type) { - case HASH_VALUE_PTR: - if (strcmp((char *)value.ptr, test[i].str) != 0) { - fprintf(stderr, "Error: corrupt ptr data for %lu at line %d\n", i, __LINE__); - exit(1); - } - break; - case HASH_VALUE_LONG: - if (value.l != test[i].val) { - fprintf(stderr, "Error: corrupt long data for %lu at line %d\n", i, __LINE__); - exit(1); - } - break; - default: - fprintf(stderr, "Error: unknown value type for %lu\n", i); - break; - } - } - } - - - /* - * Delete a key, make sure we can't find it, assure we can find all other - * keys. - */ - for (i = 0; i < max_test; i++) { - if (test[i].val & 1) { - key.type = HASH_KEY_STRING; - key.str = test[i].str; - } - else { - key.type = HASH_KEY_ULONG; - key.ul = test[i].val; - } - - if ((status = hash_lookup(table, &key, &value)) != HASH_SUCCESS) { - fprintf(stderr, "Error: failed delete lookup for value %ld at index %ld at line %d (%s)\n", - test[i].val, i, __LINE__, error_string(status)); - exit(1); - } - - if ((status = hash_delete(table, &key)) != HASH_SUCCESS) { - fprintf(stderr, "Error: %ld not in table when deleting, i = %lu at line %d (%s)\n", - test[i].val, i, __LINE__, error_string(status)); - exit(1); - } - - if (hash_lookup(table, &key, &value) != HASH_ERROR_KEY_NOT_FOUND) { - fprintf(stderr, "Error: found in table after deletion, value = %ld at index %ld at line %d\n", - test[i].val, i, __LINE__); - exit(1); - } - /* See if we can find all remaining keys */ - for (k = i + 1; k < max_test; k++) { - if (test[k].val & 1) { - key.type = HASH_KEY_STRING; - key.str = test[k].str; - } else { - key.type = HASH_KEY_ULONG; - key.ul = test[k].val; - } - if ((status = hash_lookup(table, &key, &value)) != HASH_SUCCESS) { - fprintf(stderr, "Error: failed second lookup for value %ld, i = %lu k = %lu at line %d (%s)\n", - test[k].val, i, k, __LINE__, error_string(status)); - exit(1); - } else { - switch(value.type) { - case HASH_VALUE_PTR: - if (strcmp((char *)value.ptr, test[k].str) != 0) { - fprintf(stderr, "Error: corrupt ptr data for %lu at line %d\n", k, __LINE__); - exit(1); - } - break; - case HASH_VALUE_LONG: - if (value.l != test[k].val) { - fprintf(stderr, "Error: corrupt long data for %lu at line %d\n", k, __LINE__); - exit(1); - } - break; - default: - fprintf(stderr, "Error: unknown value type (%d) for %lu\n", value.type, k); - break; - } - } - } - } - - if (verbose) printf("\n"); - -#ifdef HASH_STATISTICS - { - hash_statistics_t stats; - - if ((status = hash_get_statistics(table, &stats)) != HASH_SUCCESS) { - fprintf(stderr, "Error: could not get statistics at line %d (%s)\n", - __LINE__, error_string(status)); - exit(1); - } - - printf("Statistics: Accesses = %ld, Collisions = %ld, Collision Rate = %.2f, Expansions = %ld, Contractions = %ld\n", - stats.hash_accesses, stats.hash_collisions, - ((float)stats.hash_collisions / (float)stats.hash_accesses), - stats.table_expansions, stats.table_contractions); - } -#endif - - if ((status = hash_destroy(table)) != HASH_SUCCESS) { - fprintf(stderr, "table destruction failed at line %d (%s)\n", - __LINE__, error_string(status)); - exit(1); - } - - for (i = 0; i < max_test; i++) { - if (test[i].val & 1) { - free(test[i].str); - } - } - free(test); - free(iter_result_1); - free(iter_result_2); - - printf("Successfully tested %lu values\n", max_test); - return 0; -} diff --git a/common/dhash/examples/dhash_example.c b/common/dhash/examples/dhash_example.c new file mode 100644 index 000000000..7ed01d71a --- /dev/null +++ b/common/dhash/examples/dhash_example.c @@ -0,0 +1,118 @@ +#include +#include +#include +#include +#include "dhash.h" + +struct my_data_t { + int foo; + char bar[128]; +}; + +void delete_callback(hash_entry_t *entry, hash_destroy_enum type, void *pvt) +{ + if (entry->value.type == HASH_VALUE_PTR) free(entry->value.ptr); +} + +bool visit_callback(hash_entry_t *entry, void *user_data) +{ + unsigned long *count = (unsigned long *)user_data; + struct my_data_t *my_data = (struct my_data_t *) entry->value.ptr; + + (*count)++; + + printf("%s = [foo=%d bar=%s]\n", entry->key.str, my_data->foo, my_data->bar); + return true; +} + +struct my_data_t *new_data(int foo, const char *bar) +{ + struct my_data_t *my_data = malloc(sizeof(struct my_data_t)); + my_data->foo = foo; + strncpy(my_data->bar, bar, sizeof(my_data->bar)); + return my_data; +} +int main(int argc, char **argv) +{ + static hash_table_t *table = NULL; + hash_key_t key, *keys; + hash_value_t value; + struct hash_iter_context_t *iter; + hash_entry_t *entry; + unsigned long i, n_entries; + int error; + struct my_data_t *my_data = new_data(1024, "Hello World!"); + unsigned long count; + + /* Create a hash table */ + error = hash_create(10, &table, delete_callback, NULL); + if (error != HASH_SUCCESS) { + fprintf(stderr, "cannot create hash table (%s)\n", hash_error_string(error)); + return error; + } + + /* Enter a key named "My Data" and specify it's value as a pointer to my_data */ + key.type = HASH_KEY_STRING; + key.str = strdup("My Data"); + value.type = HASH_VALUE_PTR; + value.ptr = my_data; + + if ((error = hash_enter(table, &key, &value)) != HASH_SUCCESS) { + fprintf(stderr, "cannot add to table \"%s\" (%s)\n", key.str, hash_error_string(error)); + return error; + } + + /* Get a list of keys and print them out, free the list when we're done */ + if ((error = hash_keys(table, &count, &keys)) != HASH_SUCCESS) { + fprintf(stderr, "cannot get key list (%s)\n", hash_error_string(error)); + return error; + } + + for (i = 0; i < count; i++) + printf("key: %s\n", keys[i].str); + free(keys); + + /* Lookup the key named "My Data" */ + key.type = HASH_KEY_STRING; + key.str = strdup("My Data"); + if ((error = hash_lookup(table, &key, &value)) != HASH_SUCCESS) { + fprintf(stderr, "cannot find key \"%s\" (%s)\n", key.str, hash_error_string(error)); + } + + /* Visit each entry in the table, callback will increment count on each visit */ + printf("Iterate using callback\n"); + count = 0; + hash_iterate(table, visit_callback, &count); + + /* Assure number of visits equal the table size */ + assert(count == hash_count(table)); + + /* Visit each entry using iterator object */ + printf("Iterate using iterator\n"); + n_entries = 0; + iter = new_hash_iter_context(table); + while ((entry = iter->next(iter)) != NULL) { + struct my_data_t *data = (struct my_data_t *) entry->value.ptr; + + printf("%s = [foo=%d bar=%s]\n", entry->key.str, data->foo, data->bar); + n_entries++; + } + free(iter); + /* Assure number of visits equal the table size */ + assert(n_entries == hash_count(table)); + + /* Remove the entry, deletion callback will be invoked */ + key.type = HASH_KEY_STRING; + key.str = strdup("My Data"); + if ((error = hash_delete(table, &key)) != HASH_SUCCESS) { + fprintf(stderr, "cannot delete from table (%s)\n", hash_error_string(error)); + } + + /* Assure key is no longer in table */ + assert (!hash_has_key(table, &key)); + + /* Free the table */ + hash_destroy(table); + + return 0; +} diff --git a/common/dhash/examples/dhash_test.c b/common/dhash/examples/dhash_test.c new file mode 100644 index 000000000..27eb88d52 --- /dev/null +++ b/common/dhash/examples/dhash_test.c @@ -0,0 +1,490 @@ +#include +#include +#include +#include +#include +#include +#include "dhash.h" + +#define DEFAULT_MAX_TEST (500) +hash_entry_t *iter_result_1 = NULL; +hash_entry_t *iter_result_2 = NULL; + +unsigned long max_test = DEFAULT_MAX_TEST; +int verbose = 0; + +const char *error_string(int error) +{ + if (IS_HASH_ERROR(error)) + return hash_error_string(error); + + return strerror(error); +} + +char *key_string(hash_key_t *key) +{ + static char buf[1024]; + + switch(key->type) { + case HASH_KEY_ULONG: + snprintf(buf, sizeof(buf), "key ulong = %lu", key->ul); + break; + case HASH_KEY_STRING: + snprintf(buf, sizeof(buf), "key string = \"%s\"", key->str); + break; + default: + snprintf(buf, sizeof(buf), "unknown key type = %d", key->type); + break; + } + return buf; +} + +char *value_string(hash_value_t *value) +{ + static char buf[1024]; + + switch(value->type) { + case HASH_VALUE_UNDEF: + snprintf(buf, sizeof(buf), "value undefined"); + break; + case HASH_VALUE_PTR: + snprintf(buf, sizeof(buf), "value str = \"%s\"", (char *)value->ptr); + break; + case HASH_VALUE_INT: + snprintf(buf, sizeof(buf), "value int = %d", value->i); + break; + case HASH_VALUE_UINT: + snprintf(buf, sizeof(buf), "value unsigned int = %u", value->ui); + break; + case HASH_VALUE_LONG: + snprintf(buf, sizeof(buf), "value long = %ld", value->l); + break; + case HASH_VALUE_ULONG: + snprintf(buf, sizeof(buf), "value unsigned long = %lu", value->ul); + break; + case HASH_VALUE_FLOAT: + snprintf(buf, sizeof(buf), "value float = %f", value->f); + break; + case HASH_VALUE_DOUBLE: + snprintf(buf, sizeof(buf), "value double = %f", value->f); + break; + default: + snprintf(buf, sizeof(buf), "unknown value type = %d", value->type); + break; + } + + return buf; +} + +char *entry_string(hash_entry_t *entry) +{ + static char buf[1024]; + + snprintf(buf, sizeof(buf), "[%s] = [%s]", key_string(&entry->key), value_string(&entry->value)); + + return buf; + +} + +bool callback(hash_entry_t *item, void *user_data) +{ + unsigned long *callback_count = (unsigned long *)user_data; + + iter_result_1[*callback_count] = *item; + + (*callback_count)++; + + if (verbose) printf("%s\n", entry_string(item)); + return true; +} + +void delete_callback(hash_entry_t *item, hash_destroy_enum type, void *pvt) +{ + if (item->value.type == HASH_VALUE_PTR) free(item->value.ptr); +} + +typedef struct test_val_t { + long val; + char *str; +} test_val_t; + + +int main(int argc, char **argv) +{ + test_val_t *test = NULL; + long i, k; + int status; + hash_value_t value; + hash_key_t key; + char buf[1024]; + hash_table_t *table = NULL; + unsigned long callback_count = 0; + unsigned int directory_bits = HASH_DEFAULT_DIRECTORY_BITS; + unsigned int segment_bits = HASH_DEFAULT_SEGMENT_BITS; + unsigned long min_load_factor = HASH_DEFAULT_MIN_LOAD_FACTOR; + unsigned long max_load_factor = HASH_DEFAULT_MAX_LOAD_FACTOR; + + while (1) { + int arg; + int option_index = 0; + static struct option long_options[] = { + {"count", 1, 0, 'c'}, + {"verbose", 1, 0, 'v'}, + {"quiet", 1, 0, 'q'}, + {"directory-bits", 1, 0, 'd'}, + {"segment-bits", 1, 0, 's'}, + {"min-load-factor", 1, 0, 'l'}, + {"max-load-factor", 1, 0, 'h'}, + {0, 0, 0, 0} + }; + + arg = getopt_long(argc, argv, "c:vqd:s:l:h:", + long_options, &option_index); + if (arg == -1) break; + + switch (arg) { + case 'c': + max_test = atol(optarg); + break; + case 'v': + verbose = 1; + break; + case 'q': + verbose = 0; + break; + case 'd': + directory_bits = atoi(optarg); + break; + case 's': + segment_bits = atoi(optarg); + break; + case 'l': + min_load_factor = atol(optarg); + break; + case 'h': + max_load_factor = atol(optarg); + break; + } + } + + if ((test = (test_val_t *) calloc(max_test, sizeof(test_val_t))) == NULL) { + fprintf(stderr, "Failed to allocate test array\n"); + exit(1); + } + if ((iter_result_1 = (hash_entry_t *) calloc(max_test, sizeof(hash_entry_t))) == NULL) { + fprintf(stderr, "Failed to allocate iter_result_1 array\n"); + exit(1); + } + if ((iter_result_2 = (hash_entry_t *) calloc(max_test, sizeof(hash_entry_t))) == NULL) { + fprintf(stderr, "Failed to allocate iter_result_2 array\n"); + exit(1); + } + + + /* Initialize the random number generator */ + srandom(time(0)); + + /* Create the hash table as small as possible to exercise growth */ + if ((status = hash_create_ex(1, &table, + directory_bits, segment_bits, + min_load_factor, max_load_factor, + NULL, NULL, NULL, + delete_callback, NULL)) != HASH_SUCCESS) { + fprintf(stderr, "table creation failed at line %d (%s)\n", __LINE__, error_string(status)); + exit(1); + } + + /* Initialize the array of test values */ + for (i = 0; i < max_test; i++) { + test[i].val = random(); + /* If the value is odd we'll use a string as the key, + * otherwise we'll use an unsigned long as the key */ + if (test[i].val & 1) { + key.type = HASH_KEY_STRING; + sprintf(buf, "%ld", test[i].val); + test[i].str = strdup(buf); + } + } + + /* Enter all the test values into the hash table */ + for (i = 0; i < max_test; i++) { + if (test[i].val & 1) { + key.type = HASH_KEY_STRING; + key.str = test[i].str; + value.type = HASH_VALUE_PTR; + value.ptr = (void *) strdup(test[i].str); + } + else { + key.type = HASH_KEY_ULONG; + key.ul = test[i].val; + value.type = HASH_VALUE_LONG; + value.l = test[i].val; + } + + if (hash_has_key(table, &key)) { + fprintf(stderr, "Error: %ld already in table when inserting, i = %lu, at line %d\n", + test[i].val, i, __LINE__); + exit(1); + } + if ((status = hash_enter(table, &key, &value)) != HASH_SUCCESS) { + fprintf(stderr, "Error: %ld failed insertion at line %d (%s) \n", + test[i].val, __LINE__, error_string(status)); + exit(1); + } + } + + /* Now visit each entry in the table using a callback iterator, + * store what we found in iter_result_1 for testing the iterator object later on */ + if (verbose) printf("callback iterate:\n"); + callback_count = 0; + if ((status = hash_iterate(table, callback, &callback_count)) != HASH_SUCCESS) { + fprintf(stderr, "hash_iterate failed at line %d (%s)\n", __LINE__, error_string(status)); + exit(1); + } + if (verbose) printf("hash_count=%ld, callback_count=%ld\n", hash_count(table), callback_count); + + if (hash_count(table) != callback_count) { + fprintf(stderr, "Error: hash_count(%ld) != callback_count(%ld) at line %d\n", + hash_count(table), callback_count, __LINE__); + exit(1); + } + + /* Now vist each entry in the table using an iterator object */ + { + struct hash_iter_context_t *iter; + unsigned long n_items; + hash_entry_t *entry; + + if (verbose) printf("iter iterate:\n"); + + n_items = 0; + iter = new_hash_iter_context(table); + + while ((entry = iter->next(iter)) != NULL) { + if (verbose) printf("%s\n", entry_string(entry)); + iter_result_2[n_items] = *entry; + n_items++; + } + if (verbose) printf("hash_count=%ld, n_items=%ld\n", hash_count(table), n_items); + + if (hash_count(table) != n_items) { + fprintf(stderr, "Error: hash_count(%ld) != n_items(%ld) at line %d\n", + hash_count(table), n_items, __LINE__); + exit(1); + } + free(iter); + } + + /* Both iterators should have visited each item in the same order, verify ... */ + for (i = 0; i < max_test; i++) { + if (memcmp(&iter_result_1[i], &iter_result_2[i], sizeof(iter_result_1[0])) != 0) { + fprintf(stderr, "Error: iter_result_1[%lu] != iter_result_2[%lu] at line %d\n", + i, i, __LINE__); + exit(1); + } + } + + /* Get an array of keys in the table, print them out */ + { + unsigned long count; + hash_key_t *keys; + + if (verbose) printf("\nhash_keys:\n"); + if ((status = hash_keys(table, &count, &keys)) != HASH_SUCCESS) { + fprintf(stderr, "hash_keys failed at line %d (%s)\n", + __LINE__, error_string(status)); + exit(1); + } + + if (hash_count(table) != count) { + fprintf(stderr, "Error: hash_count(%ld) != hash_keys() count(%ld) at line %d\n", + hash_count(table), count, __LINE__); + exit(1); + } + + for (i = 0; i < count; i++) { + if (verbose) printf("%s\n", key_string(&keys[i])); + } + free(keys); + } + + /* Get an array of values in the table, print them out */ + { + unsigned long count; + hash_value_t *values; + + if (verbose) printf("\nhash_values:\n"); + hash_values(table, &count, &values); + + if (hash_count(table) != count) { + fprintf(stderr, "Error: hash_count(%ld) != hash_values() count(%ld) at line %d\n", + hash_count(table), count, __LINE__); + exit(1); + } + + for (i = 0; i < count; i++) { + if (verbose) printf("%s\n", value_string(&values[i])); + } + free(values); + } + + /* Get an array of items in the table, print them out */ + { + unsigned long count; + hash_entry_t *entries; + + if (verbose) printf("\nhash_entries:\n"); + hash_entries(table, &count, &entries); + + if (hash_count(table) != count) { + fprintf(stderr, "Error: hash_count(%ld) != hash_entries() count(%ld) at line %d\n", + hash_count(table), count, __LINE__); + exit(1); + } + + for (i = 0; i < count; i++) { + if (verbose) printf("%s\n", entry_string(&entries[i])); + } + free(entries); + } + + /* See if we can find every key */ + for (i = max_test - 1; i >= 0; i--) { + if (test[i].val & 1) { + key.type = HASH_KEY_STRING; + key.str = test[i].str; + } + else { + key.type = HASH_KEY_ULONG; + key.ul = test[i].val; + } + if ((status = hash_lookup(table, &key, &value)) != HASH_SUCCESS) { + fprintf(stderr, "Error: failed first lookup for value %ld at index %ld at line %d (%s)\n", + test[i].val, i, __LINE__, error_string(status)); + exit(1); + } + else { + switch(value.type) { + case HASH_VALUE_PTR: + if (strcmp((char *)value.ptr, test[i].str) != 0) { + fprintf(stderr, "Error: corrupt ptr data for %lu at line %d\n", i, __LINE__); + exit(1); + } + break; + case HASH_VALUE_LONG: + if (value.l != test[i].val) { + fprintf(stderr, "Error: corrupt long data for %lu at line %d\n", i, __LINE__); + exit(1); + } + break; + default: + fprintf(stderr, "Error: unknown value type for %lu\n", i); + break; + } + } + } + + + /* + * Delete a key, make sure we can't find it, assure we can find all other + * keys. + */ + for (i = 0; i < max_test; i++) { + if (test[i].val & 1) { + key.type = HASH_KEY_STRING; + key.str = test[i].str; + } + else { + key.type = HASH_KEY_ULONG; + key.ul = test[i].val; + } + + if ((status = hash_lookup(table, &key, &value)) != HASH_SUCCESS) { + fprintf(stderr, "Error: failed delete lookup for value %ld at index %ld at line %d (%s)\n", + test[i].val, i, __LINE__, error_string(status)); + exit(1); + } + + if ((status = hash_delete(table, &key)) != HASH_SUCCESS) { + fprintf(stderr, "Error: %ld not in table when deleting, i = %lu at line %d (%s)\n", + test[i].val, i, __LINE__, error_string(status)); + exit(1); + } + + if (hash_lookup(table, &key, &value) != HASH_ERROR_KEY_NOT_FOUND) { + fprintf(stderr, "Error: found in table after deletion, value = %ld at index %ld at line %d\n", + test[i].val, i, __LINE__); + exit(1); + } + /* See if we can find all remaining keys */ + for (k = i + 1; k < max_test; k++) { + if (test[k].val & 1) { + key.type = HASH_KEY_STRING; + key.str = test[k].str; + } else { + key.type = HASH_KEY_ULONG; + key.ul = test[k].val; + } + if ((status = hash_lookup(table, &key, &value)) != HASH_SUCCESS) { + fprintf(stderr, "Error: failed second lookup for value %ld, i = %lu k = %lu at line %d (%s)\n", + test[k].val, i, k, __LINE__, error_string(status)); + exit(1); + } else { + switch(value.type) { + case HASH_VALUE_PTR: + if (strcmp((char *)value.ptr, test[k].str) != 0) { + fprintf(stderr, "Error: corrupt ptr data for %lu at line %d\n", k, __LINE__); + exit(1); + } + break; + case HASH_VALUE_LONG: + if (value.l != test[k].val) { + fprintf(stderr, "Error: corrupt long data for %lu at line %d\n", k, __LINE__); + exit(1); + } + break; + default: + fprintf(stderr, "Error: unknown value type (%d) for %lu\n", value.type, k); + break; + } + } + } + } + + if (verbose) printf("\n"); + +#ifdef HASH_STATISTICS + { + hash_statistics_t stats; + + if ((status = hash_get_statistics(table, &stats)) != HASH_SUCCESS) { + fprintf(stderr, "Error: could not get statistics at line %d (%s)\n", + __LINE__, error_string(status)); + exit(1); + } + + printf("Statistics: Accesses = %ld, Collisions = %ld, Collision Rate = %.2f, Expansions = %ld, Contractions = %ld\n", + stats.hash_accesses, stats.hash_collisions, + ((float)stats.hash_collisions / (float)stats.hash_accesses), + stats.table_expansions, stats.table_contractions); + } +#endif + + if ((status = hash_destroy(table)) != HASH_SUCCESS) { + fprintf(stderr, "table destruction failed at line %d (%s)\n", + __LINE__, error_string(status)); + exit(1); + } + + for (i = 0; i < max_test; i++) { + if (test[i].val & 1) { + free(test[i].str); + } + } + free(test); + free(iter_result_1); + free(iter_result_2); + + printf("Successfully tested %lu values\n", max_test); + return 0; +} -- cgit