diff options
Diffstat (limited to 'dhash/dhash.c')
-rw-r--r-- | dhash/dhash.c | 133 |
1 files changed, 87 insertions, 46 deletions
diff --git a/dhash/dhash.c b/dhash/dhash.c index f92e463..79f9c38 100644 --- a/dhash/dhash.c +++ b/dhash/dhash.c @@ -53,10 +53,13 @@ #define PRIME_1 37 #define PRIME_2 1048583 - /* - * Fast arithmetic, relying on powers of 2, and on pre-processor - * concatenation property - */ +#ifndef MIN + #define MIN(a,b) (((a) < (b)) ? (a) : (b)) +#endif + +#ifndef MAX + #define MAX(a,b) (((a) > (b)) ? (a) : (b)) +#endif #define halloc(table, size) table->halloc(size, table->halloc_pvt) #define hfree(table, ptr) table->hfree(ptr, table->halloc_pvt) @@ -247,7 +250,7 @@ static int expand_table(hash_table_t *table) if (table->bucket_count < (table->directory_size << table->segment_size_shift)) { #ifdef DEBUG - if (debug_level >= 1) + if (debug_level >= 2) fprintf(stderr, "expand_table on entry: bucket_count=%lu, segment_count=%lu p=%lu maxp=%lu\n", table->bucket_count, table->segment_count, table->p, table->maxp); #endif @@ -314,7 +317,7 @@ static int expand_table(hash_table_t *table) } } #ifdef DEBUG - if (debug_level >= 1) + if (debug_level >= 2) fprintf(stderr, "expand_table on exit: bucket_count=%lu, segment_count=%lu p=%lu maxp=%lu\n", table->bucket_count, table->segment_count, table->p, table->maxp); #endif @@ -330,9 +333,9 @@ static int contract_table(hash_table_t *table) segment_t *old_segment, *new_segment; element_t *current; - if (table->bucket_count > table->segment_size) { + if ((table->bucket_count > table->segment_size) && (table->segment_count > 1)) { #ifdef DEBUG - if (debug_level >= 1) + if (debug_level >= 2) fprintf(stderr, "contract_table on entry: bucket_count=%lu, segment_count=%lu p=%lu maxp=%lu\n", table->bucket_count, table->segment_count, table->p, table->maxp); #endif @@ -395,7 +398,7 @@ static int contract_table(hash_table_t *table) } #ifdef DEBUG - if (debug_level >= 1) + if (debug_level >= 2) fprintf(stderr, "contract_table on exit: bucket_count=%lu, segment_count=%lu p=%lu maxp=%lu\n", table->bucket_count, table->segment_count, table->p, table->maxp); #endif @@ -428,7 +431,7 @@ static int lookup(hash_table_t *table, hash_key_t *key, element_t **element_arg, current_segment = table->directory[segment_dir]; #ifdef DEBUG - if (debug_level >= 2) + if (debug_level >= 3) fprintf(stderr, "lookup: h=%lu, segment_dir=%lu, segment_index=%lu current_segment=%p\n", h, segment_dir, segment_index, current_segment); #endif @@ -505,19 +508,47 @@ int hash_create_ex(unsigned long count, hash_table_t **tbl, hash_free_func *free_func, void *alloc_private_data, hash_delete_callback *delete_callback, - void *delete_private_data) -{ + void *delete_private_data) { unsigned long i; - unsigned int n_addr_bits; + unsigned int n_addr_bits, requested_bits; + unsigned int requested_directory_bits; + unsigned int requested_segment_bits; address_t addr; hash_table_t *table = NULL; + /* Initialize to NULL in case of an early return due to an error */ + *tbl = NULL; + if (alloc_func == NULL) alloc_func = sys_malloc_wrapper; if (free_func == NULL) free_func = sys_free_wrapper; /* Compute directory and segment parameters */ - if (directory_bits == 0) directory_bits = HASH_DEFAULT_DIRECTORY_BITS; - if (segment_bits == 0) segment_bits = HASH_DEFAULT_SEGMENT_BITS; + + /* compute power of 2 >= count; it's the number of requested buckets */ + if (count > 1) { + for (requested_bits = 0; (1 << requested_bits) < count; requested_bits++); + } else { + requested_bits = 1; + } + + /* + * If caller didn't specify directory & segment allocation then + * compute it from the requested count. + */ + if (directory_bits == 0 || segment_bits == 0) { + /* Equally divide buckets between the directory and segments */ + requested_directory_bits = MAX(requested_bits >> 1, 1); + requested_segment_bits = MAX(requested_bits - requested_directory_bits, 1); + + /* If the requested count wasn't specified pick a default */ + if (count == 0) { + directory_bits = MAX(requested_directory_bits, HASH_DEFAULT_DIRECTORY_BITS); + segment_bits = MAX(requested_segment_bits, HASH_DEFAULT_SEGMENT_BITS); + } else { + directory_bits = requested_directory_bits; + segment_bits = requested_segment_bits; + } + } for (addr = ~0, n_addr_bits = 0; addr; addr >>= 1, n_addr_bits++); @@ -534,45 +565,46 @@ int hash_create_ex(unsigned long count, hash_table_t **tbl, table->halloc_pvt = alloc_private_data; table->directory_size_shift = directory_bits; - for (i = 0, table->directory_size = 1; i < table->directory_size_shift; i++, table->directory_size <<= 1); + table->directory_size = directory_bits ? 1 << directory_bits : 0; table->segment_size_shift = segment_bits; - for (i = 0, table->segment_size = 1; i < table->segment_size_shift; i++, table->segment_size <<= 1); - + table->segment_size = segment_bits ? 1 << segment_bits : 0; /* Allocate directory */ table->directory = (segment_t **)halloc(table, table->directory_size * sizeof(segment_t *)); if (table->directory == NULL) { + hash_destroy(table); return HASH_ERROR_NO_MEMORY; } memset(table->directory, 0, table->directory_size * sizeof(segment_t *)); /* - * Adjust count to be nearest higher power of 2, minimum SEGMENT_SIZE, then - * convert into segments. + * If one wanted to pre-allocate all the buckets necessary to meet the needs + * of the requested count it would be done like this: + * + * table->segment_count = MIN((count + table->segment_size-1) / table->segment_size, + * table->directory_size); + * + * But with dynamic hash tables there is little point to this, the whole idea is to + * allow the table to grow/shrink dynamically, therefore we start with just one + * segment of buckets, the minimum necessary. */ - i = table->segment_size; - while (i < count) - i <<= 1; - count = i >> table->segment_size_shift; - - table->segment_count = 0; + table->segment_count = 1; table->p = 0; table->entry_count = 0; table->delete_callback = delete_callback; table->delete_pvt = delete_private_data; /* - * Allocate initial 'i' segments of buckets + * Allocate initial segments of buckets */ - for (i = 0; i < count; i++) { + for (i = 0; i < table->segment_count; i++) { table->directory[i] = (segment_t *)halloc(table, table->segment_size * sizeof(segment_t)); if (table->directory[i] == NULL) { hash_destroy(table); return HASH_ERROR_NO_MEMORY; } memset(table->directory[i], 0, table->segment_size * sizeof(segment_t)); - table->segment_count++; } table->bucket_count = table->segment_count << table->segment_size_shift; table->maxp = table->bucket_count; @@ -580,9 +612,16 @@ int hash_create_ex(unsigned long count, hash_table_t **tbl, table->max_load_factor = max_load_factor == 0 ? HASH_DEFAULT_MAX_LOAD_FACTOR : max_load_factor; #if DEBUG - if (debug_level >= 1) - fprintf(stderr, "hash_create_ex: table=%p count=%lu maxp=%lu segment_count=%lu\n", - table, count, table->maxp, table->segment_count); + if (debug_level >= 1) { + fprintf(stderr, "hash_create_ex: count=%lu available buckets=%lu bucket_count=%lu maxp=%lu\n", + count, table->directory_size*table->segment_size, table->bucket_count, table->maxp); + fprintf(stderr, " directory_bits=%u segment_bits=%u requested_bits=%u\n", + directory_bits, segment_bits, requested_bits); + fprintf(stderr, " directory_size=%lu segment_size=%lu segment_count=%lu\n", + table->directory_size, table->segment_size, table->segment_count); + fprintf(stderr, " min_load_factor=%lu max_load_factor=%lu\n", + table->min_load_factor, table->max_load_factor); + } #endif #ifdef HASH_STATISTICS memset(&table->statistics, 0, sizeof(table->statistics)); @@ -613,25 +652,27 @@ int hash_destroy(hash_table_t *table) if (!table) return HASH_ERROR_BAD_TABLE; if (table != NULL) { - for (i = 0; i < table->segment_count; i++) { - /* test probably unnecessary */ - if ((s = table->directory[i]) != NULL) { - for (j = 0; j < table->segment_size; j++) { - p = s[j]; - while (p != NULL) { - q = p->next; - hdelete_callback(table, HASH_TABLE_DESTROY, &p->entry); - if (p->entry.key.type == HASH_KEY_STRING) { - hfree(table, (char *)p->entry.key.str); + if (table->directory) { + for (i = 0; i < table->segment_count; i++) { + /* test probably unnecessary */ + if ((s = table->directory[i]) != NULL) { + for (j = 0; j < table->segment_size; j++) { + p = s[j]; + while (p != NULL) { + q = p->next; + hdelete_callback(table, HASH_TABLE_DESTROY, &p->entry); + if (p->entry.key.type == HASH_KEY_STRING) { + hfree(table, (char *)p->entry.key.str); + } + hfree(table, (char *)p); + p = q; } - hfree(table, (char *)p); - p = q; } + hfree(table, s); } - hfree(table, s); } + hfree(table, table->directory); } - hfree(table, table->directory); hfree(table, table); table = NULL; } |