diff options
Diffstat (limited to 'common/dhash/examples')
-rw-r--r-- | common/dhash/examples/dhash_example.c | 118 | ||||
-rw-r--r-- | common/dhash/examples/dhash_test.c | 490 |
2 files changed, 608 insertions, 0 deletions
diff --git a/common/dhash/examples/dhash_example.c b/common/dhash/examples/dhash_example.c new file mode 100644 index 00000000..7ed01d71 --- /dev/null +++ b/common/dhash/examples/dhash_example.c @@ -0,0 +1,118 @@ +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include <assert.h> +#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 00000000..27eb88d5 --- /dev/null +++ b/common/dhash/examples/dhash_test.c @@ -0,0 +1,490 @@ +#include <stdio.h> +#include <assert.h> +#include <string.h> +#include <stdlib.h> +#include <time.h> +#include <getopt.h> +#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; +} |