githubmirror/ding-libs

dhash/dhash.c
991 строка30 KB
Stephen Gallagher
Properly license libdhash
18 фев 2010, 23:46
18 фев 2010, 23:46f003197
/*
    Authors:
        John Dennis <jdennis.redhat.com>
        Esmond Pitt <ejp@ausmelb.oz.AU>

    This implementation was based on a 3/7/1989 public domain submission
    to comp.sources.misc by Esmond Pitt <ejp@ausmelb.oz.AU>.

    Copyright (C) 2009 Red Hat

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published by
    the Free Software Foundation; either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

/*****************************************************************************/
/******************************** Documentation ******************************/
/*****************************************************************************/

/*
 * See documentation in corresponding header file dhash.h.
 *
 * Compilation controls:
 * DEBUG controls some informative traces, mainly for debugging.
 * HASH_STATISTICS causes hash_accesses and hash_collisions to be maintained;
 * when combined with DEBUG, these are displayed by hash_destroy().
 *
 */

/*****************************************************************************/
/******************************* Include Files *******************************/
/*****************************************************************************/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
#include "dhash.h"

/*****************************************************************************/
/****************************** Internal Defines *****************************/
/*****************************************************************************/

#define PRIME_1                 37
#define PRIME_2                 1048583

 /*
  * Fast arithmetic, relying on powers of 2, and on pre-processor
  * concatenation property
  */

#define halloc(table, size) table->halloc(size, table->halloc_pvt)
#define hfree(table, ptr) table->hfree(ptr, table->halloc_pvt)
#define hdelete_callback(table, type, entry) do { \
    if (table->delete_callback) { \
        table->delete_callback(entry, type, table->delete_pvt); \
    } \
} while(0)

/*****************************************************************************/
/************************** Internal Type Definitions ************************/
/*****************************************************************************/

typedef struct element_t {
    hash_entry_t entry;
    struct element_t *next;
} element_t, *segment_t;


struct hash_table_str {
    unsigned long   p;             /* Next bucket to be split */
    unsigned long   maxp;          /* upper bound on p during expansion */
    unsigned long   entry_count;   /* current # entries */
    unsigned long   bucket_count;  /* current # buckets */
    unsigned long   segment_count; /* current # segments */
    unsigned long   min_load_factor;
    unsigned long   max_load_factor;
    unsigned long   directory_size;
    unsigned int    directory_size_shift;
    unsigned long   segment_size;
    unsigned int    segment_size_shift;
    hash_delete_callback *delete_callback;
    void *delete_pvt;
    hash_alloc_func *halloc;
    hash_free_func *hfree;
    void *halloc_pvt;
    segment_t **directory;
#ifdef HASH_STATISTICS
    hash_statistics_t statistics;
#endif

};

typedef unsigned long address_t;

typedef struct hash_keys_callback_data_t {
    unsigned long index;
    hash_key_t *keys;
} hash_keys_callback_data_t;

typedef struct hash_values_callback_data_t {
    unsigned long index;
    hash_value_t *values;
} hash_values_callback_data_t;

struct _hash_iter_context_t {
    struct hash_iter_context_t iter;
    hash_table_t *table;
    unsigned long i, j;
    segment_t *s;
    element_t *p;
};

/*****************************************************************************/
/**********************  External Function Declarations  *********************/
/*****************************************************************************/

/*****************************************************************************/
/**********************  Internal Function Declarations  *********************/
/*****************************************************************************/

static address_t convert_key(hash_key_t *key);
static address_t hash(hash_table_t *table, hash_key_t *key);
static bool key_equal(hash_key_t *a, hash_key_t *b);
static int contract_table(hash_table_t *table);
static int expand_table(hash_table_t *table);
static hash_entry_t *hash_iter_next(struct hash_iter_context_t *iter);

/*****************************************************************************/
/*************************  External Global Variables  ***********************/
/*****************************************************************************/

/*****************************************************************************/
/*************************  Internal Global Variables  ***********************/
/*****************************************************************************/

#if DEBUG
int debug_level = 1;
#endif

/*****************************************************************************/
/***************************  Internal Functions  ****************************/
/*****************************************************************************/

static void *sys_malloc_wrapper(size_t size, void *pvt)
{
    return malloc(size);
}

static void sys_free_wrapper(void *ptr, void *pvt)
{
    return free(ptr);
}

static address_t convert_key(hash_key_t *key)
{
    address_t h;
    unsigned char *k;

    switch(key->type) {
    case HASH_KEY_ULONG:
        h = key->ul;
        break;
    case HASH_KEY_STRING:
        /* Convert string to integer */
        for (h = 0, k = (unsigned char *) key->str; *k; k++)
            h = h * PRIME_1 ^ (*k - ' ');
        break;
    default:
        h = key->ul;
        break;
    }
    return h;
}

static address_t hash(hash_table_t *table, hash_key_t *key)
{
    address_t h, address;

    h = convert_key(key);
    h %= PRIME_2;
    address = h & (table->maxp-1);            /* h % maxp */
    if (address < table->p)
        address = h & ((table->maxp << 1)-1); /* h % (2*table->maxp) */

    return address;
}

static bool is_valid_key_type(hash_key_enum key_type)
{
    switch(key_type) {
    case HASH_KEY_ULONG:
    case HASH_KEY_STRING:
        return true;
    default:
        return false;
    }
}

static bool is_valid_value_type(hash_value_enum value_type)
{
    switch(value_type) {
    case HASH_VALUE_UNDEF:
    case HASH_VALUE_PTR:
    case HASH_VALUE_INT:
    case HASH_VALUE_UINT:
    case HASH_VALUE_LONG:
    case HASH_VALUE_ULONG:
    case HASH_VALUE_FLOAT:
    case HASH_VALUE_DOUBLE:
        return true;
    default:
        return false;
    }
}

static bool key_equal(hash_key_t *a, hash_key_t *b)
{
    if (a->type != b->type) return false;

    switch(a->type) {
    case HASH_KEY_ULONG:
        return (a->ul == b->ul);
    case HASH_KEY_STRING:
        return (strcmp(a->str, b->str) == 0);
    }
    return false;
}


static int expand_table(hash_table_t *table)
{
    address_t  new_address;
    unsigned long old_segment_index, new_segment_index;
    unsigned long old_segment_dir, new_segment_dir;
    segment_t *old_segment, *new_segment;
    element_t *current, **previous, **last_of_new;

    if (table->bucket_count < (table->directory_size << table->segment_size_shift)) {
#ifdef DEBUG
        if (debug_level >= 1)
            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
#ifdef HASH_STATISTICS
        table->statistics.table_expansions++;
#endif

        /*
         * Locate the bucket to be split
         */
        old_segment_dir = table->p >> table->segment_size_shift;
        old_segment = table->directory[old_segment_dir];
        old_segment_index = table->p & (table->segment_size-1); /* p % segment_size */
        /*
         * Expand address space; if necessary create a new segment
         */
        new_address = table->maxp + table->p;
        new_segment_dir = new_address >> table->segment_size_shift;
        new_segment_index = new_address & (table->segment_size-1); /* new_address % segment_size */
        if (new_segment_index == 0) {
            table->directory[new_segment_dir] = (segment_t *)halloc(table, table->segment_size * sizeof(segment_t));
            if (table->directory[new_segment_dir] == NULL) {
                return HASH_ERROR_NO_MEMORY;
            }
            memset(table->directory[new_segment_dir], 0, table->segment_size * sizeof(segment_t));
            table->segment_count++;
        }
        new_segment = table->directory[new_segment_dir];
        /*
         * Adjust state variables
         */
        table->p++;
        if (table->p == table->maxp) {
            table->maxp <<= 1;  /* table->maxp *= 2 */
            table->p = 0;
        }
        table->bucket_count++;
        /*
         * Relocate records to the new bucket
         */
        previous = &old_segment[old_segment_index];
        current = *previous;
        last_of_new = &new_segment[new_segment_index];
        *last_of_new = NULL;
        while (current != NULL) {
            if (hash(table, &current->entry.key) == new_address) {
                /*
                 * Attach it to the end of the new chain
                 */
                *last_of_new = current;
                /*
                 * Remove it from old chain
                 */
                *previous = current->next;
                last_of_new = &current->next;
                current = current->next;
                *last_of_new = NULL;
            } else {
                /*
                 * leave it on the old chain
                 */
                previous = &current->next;
                current = current->next;
            }
        }
#ifdef DEBUG
        if (debug_level >= 1)
            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
    }
    return HASH_SUCCESS;
}

static int contract_table(hash_table_t *table)
{
    address_t  new_address, old_address;
    unsigned long old_segment_index, new_segment_index;
    unsigned long old_segment_dir, new_segment_dir;
    segment_t *old_segment, *new_segment;
    element_t *current;

    if (table->bucket_count > table->segment_size) {
#ifdef DEBUG
        if (debug_level >= 1)
            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

#ifdef HASH_STATISTICS
        table->statistics.table_contractions++;
#endif
        /*
         * Locate the bucket to be merged with the last bucket
         */
        old_address = table->bucket_count - 1;
        old_segment_dir = old_address >> table->segment_size_shift;
        old_segment = table->directory[old_segment_dir];
        old_segment_index = old_address & (table->segment_size-1); /* old_address % segment_size */

        /*
         * Adjust state variables
         */
        if (table->p > 0) {
            table->p--;
        } else {
            table->maxp >>= 1;
            table->p = table->maxp - 1;
        }
        table->bucket_count--;

        /*
         * Find the last bucket to merge back
         */
        if((current = old_segment[old_segment_index]) != NULL) {
            new_address = hash(table, &old_segment[old_segment_index]->entry.key);
            new_segment_dir = new_address >> table->segment_size_shift;
            new_segment_index = new_address & (table->segment_size-1); /* new_address % segment_size */
            new_segment = table->directory[new_segment_dir];

            /*
             * Relocate records to the new bucket by splicing the two chains
             * together by inserting the old chain at the head of the new chain.
             * First find the end of the old chain, then set its next pointer to
             * point to the head of the new chain, set the head of the new chain to
             * point to the old chain, then finally set the head of the old chain to
             * NULL.
             */

            while (current->next != NULL) {
                current = current->next;
            }

            current->next = new_segment[new_segment_index];
            new_segment[new_segment_index] = old_segment[old_segment_index];
            old_segment[old_segment_index] = NULL;
        }
        /*
         * If we have removed the last of the chains in this segment then free the
         * segment since its no longer in use.
         */
        if (old_segment_index == 0) {
            table->segment_count--;
            hfree(table, table->directory[old_segment_dir]);
        }

#ifdef DEBUG
        if (debug_level >= 1)
            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

    }
    return HASH_SUCCESS;
}

static int lookup(hash_table_t *table, hash_key_t *key, element_t **element_arg, segment_t **chain_arg)
{
    address_t h;
    segment_t *current_segment;
    unsigned long segment_index, segment_dir;
    segment_t *chain, element;

    *element_arg = NULL;
    *chain_arg = NULL;

    if (!table) return HASH_ERROR_BAD_TABLE;

#ifdef HASH_STATISTICS
    table->statistics.hash_accesses++;
#endif
    h = hash(table, key);
    segment_dir = h >> table->segment_size_shift;
    segment_index = h & (table->segment_size-1); /* h % segment_size */
    /*
     * valid segment ensured by hash()
     */
    current_segment = table->directory[segment_dir];

#ifdef DEBUG
    if (debug_level >= 2)
        fprintf(stderr, "lookup: h=%lu, segment_dir=%lu, segment_index=%lu current_segment=%p\n",
                h, segment_dir, segment_index, current_segment);
#endif

    if (current_segment == NULL) return EFAULT;
    chain = &current_segment[segment_index];
    element = *chain;
    /*
     * Follow collision chain
     */
    while (element != NULL && !key_equal(&element->entry.key, key)) {
        chain = &element->next;
        element = *chain;
#ifdef HASH_STATISTICS
        table->statistics.hash_collisions++;
#endif
    }
    *element_arg = element;
    *chain_arg = chain;

    return HASH_SUCCESS;
}

static bool hash_keys_callback(hash_entry_t *item, void *user_data)
{
    hash_keys_callback_data_t *data = (hash_keys_callback_data_t *)user_data;

    data->keys[data->index++] = item->key;
    return true;
}

static bool hash_values_callback(hash_entry_t *item, void *user_data)
{
    hash_values_callback_data_t *data = (hash_values_callback_data_t *)user_data;

    data->values[data->index++] = item->value;
    return true;
}

/*****************************************************************************/
/****************************  Exported Functions  ***************************/
/*****************************************************************************/

const char* hash_error_string(int error)
{
    switch(error) {
    case HASH_SUCCESS:              return "Success";
    case HASH_ERROR_BAD_KEY_TYPE:   return "Bad key type";
    case HASH_ERROR_BAD_VALUE_TYPE: return "Bad value type";
    case HASH_ERROR_NO_MEMORY:      return "No memory";
    case HASH_ERROR_KEY_NOT_FOUND:  return "Key not found";
    case HASH_ERROR_BAD_TABLE:      return "Bad table";
    }
    return NULL;
}


int hash_create(unsigned long count, hash_table_t **tbl,
                hash_delete_callback *delete_callback,
                void *delete_private_data)
{
    return hash_create_ex(count, tbl, 0, 0, 0, 0,
                          NULL, NULL, NULL,
                          delete_callback,
                          delete_private_data);
}

int hash_create_ex(unsigned long count, hash_table_t **tbl,
                   unsigned int directory_bits,
                   unsigned int segment_bits,
                   unsigned long min_load_factor,
                   unsigned long max_load_factor,
                   hash_alloc_func *alloc_func,
                   hash_free_func *free_func,
                   void *alloc_private_data,
                   hash_delete_callback *delete_callback,
                   void *delete_private_data)
{
    unsigned long i;
    unsigned int n_addr_bits;
    address_t addr;
    hash_table_t *table = 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;

    for (addr = ~0, n_addr_bits = 0; addr; addr >>= 1, n_addr_bits++);

    if (directory_bits + segment_bits > n_addr_bits) return EINVAL;

    table = (hash_table_t *)alloc_func(sizeof(hash_table_t),
                                       alloc_private_data);
    if (table == NULL) {
        return HASH_ERROR_NO_MEMORY;
    }
    memset(table, 0, sizeof(hash_table_t));
    table->halloc = alloc_func;
    table->hfree = free_func;
    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->segment_size_shift = segment_bits;
    for (i = 0, table->segment_size = 1; i < table->segment_size_shift; i++, table->segment_size <<= 1);


    /* Allocate directory */
    table->directory = (segment_t **)halloc(table, table->directory_size * sizeof(segment_t *));
    if (table->directory == NULL) {
        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.
     */
    i = table->segment_size;
    while (i < count)
        i <<= 1;
    count = i >> table->segment_size_shift;

    table->segment_count = 0;
    table->p = 0;
    table->entry_count = 0;
    table->delete_callback = delete_callback;
    table->delete_pvt = delete_private_data;

    /*
     * Allocate initial 'i' segments of buckets
     */
    for (i = 0; i < 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;
    table->min_load_factor = min_load_factor == 0 ? HASH_DEFAULT_MIN_LOAD_FACTOR : min_load_factor;
    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);
#endif
#ifdef HASH_STATISTICS
    memset(&table->statistics, 0, sizeof(table->statistics));
#endif

    *tbl = table;
    return HASH_SUCCESS;
}

#ifdef HASH_STATISTICS
int hash_get_statistics(hash_table_t *table, hash_statistics_t *statistics)
{
    if (!table) return HASH_ERROR_BAD_TABLE;
    if (!statistics) return EINVAL;

    *statistics = table->statistics;

    return HASH_SUCCESS;
}
#endif

int hash_destroy(hash_table_t *table)
{
    unsigned long i, j;
    segment_t *s;
    element_t *p, *q;

    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);
                        }
                        hfree(table, (char *)p);
                        p = q;
                    }
                }
                hfree(table, s);
            }
        }
        hfree(table, table->directory);
        hfree(table, table);
        table = NULL;
    }
    return HASH_SUCCESS;
}

int hash_iterate(hash_table_t *table, hash_iterate_callback callback, void *user_data)
{
    unsigned long i, j;
    segment_t *s;
    element_t *p;

    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) {
                        if(!(*callback)(&p->entry, user_data)) return HASH_SUCCESS;
                        p = p->next;
                    }
                }
            }
        }
    }
    return HASH_SUCCESS;
}

static hash_entry_t *hash_iter_next(struct hash_iter_context_t *iter_arg)
{
    struct _hash_iter_context_t *iter = (struct _hash_iter_context_t *) iter_arg;
    hash_entry_t *entry;

    if (iter->table == NULL) return NULL;
    goto state_3a;

 state_1:
    iter->i++;
    if(iter->i >= iter->table->segment_count) return NULL;
    /* test probably unnecessary */
    iter->s = iter->table->directory[iter->i];
    if (iter->s == NULL) goto state_1;
    iter->j = 0;
 state_2:
    if (iter->j >= iter->table->segment_size) goto state_1;
    iter->p = iter->s[iter->j];
 state_3a:
    if (iter->p == NULL) goto state_3b;
    entry = &iter->p->entry;
    iter->p = iter->p->next;
    return entry;
 state_3b:
    iter->j++;
    goto state_2;

    /* Should never reach here */
    fprintf(stderr, "ERROR hash_iter_next reached invalid state\n");
    return NULL;
}

struct hash_iter_context_t *new_hash_iter_context(hash_table_t *table)
{
    struct _hash_iter_context_t *iter;

    if (!table) return NULL;;

    iter = halloc(table, sizeof(struct _hash_iter_context_t));
    if (iter == NULL) {
        return NULL;
    }


    iter->iter.next = (hash_iter_next_t) hash_iter_next;

    iter->table = table;
    iter->i = 0;
    iter->j = 0;
    iter->s = table->directory[iter->i];
    iter->p = iter->s[iter->j];

    return (struct hash_iter_context_t *)iter;
}

unsigned long hash_count(hash_table_t *table)
{
    return table->entry_count;
}


int hash_keys(hash_table_t *table, unsigned long *count_arg, hash_key_t **keys_arg)
{
    unsigned long count = table->entry_count;
    hash_key_t *keys;
    hash_keys_callback_data_t data;

    if (!table) return HASH_ERROR_BAD_TABLE;

    if (count == 0) {
        *count_arg = 0;
        *keys_arg = NULL;
        return HASH_SUCCESS;
    }

    keys = halloc(table, sizeof(hash_key_t) * count);
    if (keys == NULL) {
        *count_arg = -1;
        *keys_arg = NULL;
        return HASH_ERROR_NO_MEMORY;
    }

    data.index = 0;
    data.keys = keys;

    hash_iterate(table, hash_keys_callback, &data);

    *count_arg = count;
    *keys_arg = keys;
    return HASH_SUCCESS;
}

int hash_values(hash_table_t *table, unsigned long *count_arg, hash_value_t **values_arg)
{
    unsigned long count = table->entry_count;
    hash_value_t *values;
    hash_values_callback_data_t data;

    if (!table) return HASH_ERROR_BAD_TABLE;

    if (count == 0) {
        *count_arg = 0;
        *values_arg = NULL;
        return HASH_SUCCESS;
    }

    values = halloc(table, sizeof(hash_value_t) * count);
    if (values == NULL) {
        *count_arg = -1;
        *values_arg = NULL;
        return HASH_ERROR_NO_MEMORY;
    }

    data.index = 0;
    data.values = values;

    hash_iterate(table, hash_values_callback, &data);

    *count_arg = count;
    *values_arg = values;
    return HASH_SUCCESS;
}

typedef struct hash_entries_callback_data_t {
    unsigned long index;
    hash_entry_t *entries;
} hash_entries_callback_data_t;

static bool hash_entries_callback(hash_entry_t *item, void *user_data)
{
    hash_entries_callback_data_t *data = (hash_entries_callback_data_t *)user_data;

    data->entries[data->index++] = *item;
    return true;
}

int hash_entries(hash_table_t *table, unsigned long *count_arg, hash_entry_t **entries_arg)
{
    unsigned long count = table->entry_count;
    hash_entry_t *entries;
    hash_entries_callback_data_t data;

    if (!table) return HASH_ERROR_BAD_TABLE;

    if (count == 0) {
        *count_arg = 0;
        *entries_arg = NULL;
        return HASH_SUCCESS;
    }

    entries = halloc(table, sizeof(hash_entry_t) * count);
    if (entries == NULL) {
        *count_arg = -1;
        *entries_arg = NULL;
        return HASH_ERROR_NO_MEMORY;
    }

    data.index = 0;
    data.entries = entries;

    hash_iterate(table, hash_entries_callback, &data);

    *count_arg = count;
    *entries_arg = entries;
    return HASH_SUCCESS;
}

bool hash_has_key(hash_table_t *table, hash_key_t *key)
{
    hash_value_t value;

    if (hash_lookup(table, key, &value) == HASH_SUCCESS)
        return true;
    else
        return false;
}


int hash_get_default(hash_table_t *table, hash_key_t *key, hash_value_t *value, hash_value_t *default_value)
{
    int error;

    if (!table) return HASH_ERROR_BAD_TABLE;

    if ((error = hash_lookup(table, key, value)) != HASH_SUCCESS) {
        if ((error = hash_enter(table, key, default_value)) != HASH_SUCCESS) {
            return error;
        }
        *value = *default_value;
        return HASH_SUCCESS;
    }

    return HASH_SUCCESS;
}

int hash_enter(hash_table_t *table, hash_key_t *key, hash_value_t *value)
{
    int error;
    segment_t element, *chain;
    size_t len;

    if (!table) return HASH_ERROR_BAD_TABLE;

    if (!is_valid_key_type(key->type))
        return HASH_ERROR_BAD_KEY_TYPE;

    if (!is_valid_value_type(value->type))
        return HASH_ERROR_BAD_VALUE_TYPE;

    lookup(table, key, &element, &chain);

    if (element == NULL) {                    /* not found */
        element = (element_t *)halloc(table, sizeof(element_t));
        if (element == NULL) {
            /* Allocation failed, return NULL */
            return HASH_ERROR_NO_MEMORY;
        }
        memset(element, 0, sizeof(element_t));
        /*
         * Initialize new element
         */
        switch(element->entry.key.type = key->type) {
        case HASH_KEY_ULONG:
            element->entry.key.ul = key->ul;
            break;
        case HASH_KEY_STRING:
            len = strlen(key->str)+1;
            element->entry.key.str = halloc(table, len);
            if (element->entry.key.str == NULL) {
                hfree(table, element);
                return HASH_ERROR_NO_MEMORY;
            }
            memcpy((void *)element->entry.key.str, key->str, len);
            break;
        }
        switch(element->entry.value.type = value->type) {
        case HASH_VALUE_UNDEF:
            element->entry.value.ul = 0;
            break;
        case HASH_VALUE_PTR:
            element->entry.value.ptr = value->ptr;
            break;
        case HASH_VALUE_INT:
            element->entry.value.i = value->i;
            break;
        case HASH_VALUE_UINT:
            element->entry.value.ui = value->ui;
            break;
        case HASH_VALUE_LONG:
            element->entry.value.l = value->l;
            break;
        case HASH_VALUE_ULONG:
            element->entry.value.ul = value->ul;
            break;
        case HASH_VALUE_FLOAT:
            element->entry.value.f = value->f;
            break;
        case HASH_VALUE_DOUBLE:
            element->entry.value.d = value->d;
            break;
        }
        *chain = element;             /* link into chain */
        element->next = NULL;
        /*
         * Table over-full?
         */
        if (++table->entry_count / table->bucket_count > table->max_load_factor) {
            if ((error = expand_table(table)) != HASH_SUCCESS) { /* doesn't affect element */
                return error;
            }
        }
    }                                       /* end not found */
    return HASH_SUCCESS;
}

int hash_lookup(hash_table_t *table, hash_key_t *key, hash_value_t *value)
{
    segment_t element, *chain;

    if (!table) return HASH_ERROR_BAD_TABLE;

    if (!is_valid_key_type(key->type))
        return HASH_ERROR_BAD_KEY_TYPE;

    lookup(table, key, &element, &chain);

    if (element) {
        *value = element->entry.value;
        return HASH_SUCCESS;
    } else {
        return HASH_ERROR_KEY_NOT_FOUND;
    }
}

int hash_delete(hash_table_t *table, hash_key_t *key)
{
    int error;
    segment_t element, *chain;

    if (!table) return HASH_ERROR_BAD_TABLE;

    if (!is_valid_key_type(key->type))
        return HASH_ERROR_BAD_KEY_TYPE;

    lookup(table, key, &element, &chain);

    if (element) {
        hdelete_callback(table, HASH_ENTRY_DESTROY, &element->entry);
        *chain = element->next; /* remove from chain */
        /*
         * Table too sparse?
         */
        if (--table->entry_count / table->bucket_count < table->min_load_factor) {
            if ((error = contract_table(table)) != HASH_SUCCESS) { /* doesn't affect element */
                return error;
            }
        }
        if (element->entry.key.type == HASH_KEY_STRING) {
            hfree(table, (char *)element->entry.key.str);
        }
        hfree(table, element);
        return HASH_SUCCESS;
    } else {
        return HASH_ERROR_KEY_NOT_FOUND;
    }
}