path: root/common/dhash/dhash.h

/*
    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/>.
*/

#ifndef DHASH_H
#define DHASH_H

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

#if 0

Dynamic hash table implementation based on article in CACM April 1988 pp.
446-457, by Per-Ake Larson.

This implementation was based on a 3/7/1989 submission to comp.sources.misc by
Esmond Pitt (ejp@ausmelb.oz.AU) that emulated the hsearch(3) interface. The interface
was reworked to be much more flexible and significant new functionality was
added by John Dennis (jdennis@sharpeye.com).

A hash table maintains a set of <key,value> pairs. Lookups are performed by
locating the key in the table and returning its value.

A dynamic hash table keeps the number of hash collisions constant
independent of the number of entries in the hash table.

Both keys and values may be of different types. Two different key types are
supported, strings and unsigned longs. If the key type is a string the hash
library will automatically allocate memory to hold the hash key string and
will automatically free the memory for the key string when the hash entry
is destroyed. Items in the hash table only match when their key types match
AND the keys themselves match. For example if there were two hash entries,
one whose key type was an unsigned long equal to 1 and one whose key type was
a string equal to "1" they would not match, these are considered two
distinct entries.

The value of the key may be a undefined, pointer, an int, an unsigned int, a
long, an unsigned long, a float, or a double. The hash library does nothing
with user pointers (value.type == HASH_VALUE_PTR). Its the user responsibility
to free items pointed to by these pointers when a hash entry is deleted or the
hash table is destroyed (see hash_delete_callback and/or hash_destroy).

See dhash_example.c for an illustration of how one might use the API. It does not
represent complete API coverage nor the optimal way to do things in all cases,
it is just a general example.

Copyright 2009-1010 John Dennis
This program is distributed under the terms of the GNU Lesser General Public
License (LGPL). See the included COPYING and COPYING.lesser files for the
terms of this license.

#endif

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

#include <stdbool.h>

/*****************************************************************************/
/*********************************** Defines *********************************/
/*****************************************************************************/

#if 1
#define HASH_STATISTICS
#endif

#define HASH_DEFAULT_DIRECTORY_BITS 5
#define HASH_DEFAULT_SEGMENT_BITS 5
#define HASH_DEFAULT_MIN_LOAD_FACTOR 1
#define HASH_DEFAULT_MAX_LOAD_FACTOR 5

#define HASH_ERROR_BASE -2000
#define HASH_ERROR_LIMIT (HASH_ERROR_BASE+20)
#define IS_HASH_ERROR(error)  (((error) >= HASH_ERROR_BASE) && ((error) < HASH_ERROR_LIMIT))

#define HASH_SUCCESS              0
#define HASH_ERROR_BAD_KEY_TYPE   (HASH_ERROR_BASE + 1)
#define HASH_ERROR_BAD_VALUE_TYPE (HASH_ERROR_BASE + 2)
#define HASH_ERROR_NO_MEMORY      (HASH_ERROR_BASE + 3)
#define HASH_ERROR_KEY_NOT_FOUND  (HASH_ERROR_BASE + 4)
#define HASH_ERROR_BAD_TABLE      (HASH_ERROR_BASE + 5)

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

struct hash_table_str;
typedef struct hash_table_str hash_table_t;

typedef enum {
    HASH_KEY_STRING,
    HASH_KEY_ULONG
} hash_key_enum;

typedef enum
{
    HASH_VALUE_UNDEF,
    HASH_VALUE_PTR,
    HASH_VALUE_INT,
    HASH_VALUE_UINT,
    HASH_VALUE_LONG,
    HASH_VALUE_ULONG,
    HASH_VALUE_FLOAT,
    HASH_VALUE_DOUBLE
} hash_value_enum;

typedef enum
{
    HASH_TABLE_DESTROY,
    HASH_ENTRY_DESTROY
} hash_destroy_enum;

typedef struct hash_key_t {
    hash_key_enum type;
    union {
        char *str;
        unsigned long ul;
    };
} hash_key_t;

typedef struct hash_value_t {
    hash_value_enum type;
    union {
        void *ptr;
        int i;
        unsigned int ui;
        long l;
        unsigned long ul;
        float f;
        double d;
    };
} hash_value_t;

typedef struct hash_entry_t {
    hash_key_t key;
    hash_value_t value;
} hash_entry_t;

#ifdef HASH_STATISTICS
typedef struct hash_statistics_t {
    unsigned long hash_accesses;
    unsigned long hash_collisions;
    unsigned long table_expansions;
    unsigned long table_contractions;
} hash_statistics_t;
#endif


/* typedef's for callback based iteration */
typedef bool(*hash_iterate_callback)(hash_entry_t *item, void *user_data);
typedef void (hash_delete_callback)(hash_entry_t *item,
                                    hash_destroy_enum type, void *pvt);

/* typedef's for iteration object based iteration */
struct hash_iter_context_t;
typedef hash_entry_t *(*hash_iter_next_t)(struct hash_iter_context_t *iter);
struct hash_iter_context_t {
    hash_iter_next_t next;
};

/* typedef for hash_create_ex() */
typedef void *(hash_alloc_func)(size_t size, void *pvt);
typedef void (hash_free_func)(void *ptr, void *pvt);

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

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

/*
 * Given an error code returned by a hash function, map it to a error string.
 * Returns NULL if the error code is unrecognized.
 */
const char* hash_error_string(int error);

/*
 * Create a new hash table with room for n initial entries.  hash_create returns
 * an opaque pointer to the new hash table in the table parameter. Functions
 * operating on the hash table pass in this hash table pointer. This means you
 * may have as many concurrent hash tables as you want. The delete_callback
 * parameter is a pointer to a function which will be called just prior to a
 * hash entry being deleted. This is useful when the hash value has items which
 * may need to be disposed of. The delete_callback may be NULL.
 * The delete_private_data is data passed to the delete_callback, this way
 * custom callbacks can have a private context to reach data they need to use
 * before performning their operations. delete_private_data may be NULL.
 */
int hash_create(unsigned long count, hash_table_t **tbl,
                hash_delete_callback *delete_callback,
                void *delete_private_data);

/*
 * Create a new hash table and fine tune it's configurable parameters.
 * Refer to CACM article for explanation of parameters.
 *
 * directory_bits: number of address bits allocated to top level directory array.
 * segment_bits: number of address bits allocated to segment array.
 * min_load_factor: table contracted when the ratio of entry count to bucket count
 *                  is less than the min_load_factor the table is contracted.
 * max_load_factor: table expanded when the ratio of entry count to bucket count
 *                  is greater than the max_load_factor the table is expanded.
 * alloc_func: function pointer for allocation
 * free_func: funciton pointer for freeing memory allocated with alloc_func
 * alloc_private data: data passed to the alloc and free functions so that
 *                     custom functions can refernce other private data they may
 *                     need during their execution without having to use global
 *                     variables.
 *
 * Note directory_bits + segment_bits must be <= number of bits in unsigned long
 */
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);

#ifdef HASH_STATISTICS
/*
 * Return statistics for the table.
 */
int hash_get_statistics(hash_table_t *table, hash_statistics_t *statistics);
#endif

/*
 * hash_destroy deletes all entries in the hash table, freeing all memory used
 * in implementing the hash table. Some hash entries may have values which are
 * pointers to user data structures. User pointers are not free by hash_destroy,
 * they must be free by the caller. This may be done by iterating over all the
 * entries in the table using hash_iterate() and freeing the values or by
 * registering a delete callback when the table is created with
 * hash_create(). Note, hash keys which are strings will be automatically freed
 * by hash_destroy, the caller does not need to free the key strings.
 */
int hash_destroy(hash_table_t *table);

/*
 * Enter or update an item in the table referenced by key. If the key does not
 * exist yet the item will be created and inserted into the table with the
 * value, otherwise the value for the existing key is updated. The return value
 * may be HASH_ERROR_BAD_KEY_TYPE or HASH_ERROR_BAD_VALUE_TYPE if the key or
 * value type respectively is invalid. This function might also return
 * HASH_ERROR_NO_MEMORY.
 */
int hash_enter(hash_table_t *table, hash_key_t *key, hash_value_t *value);

/*
 * Using the key lookup the value associated with it in the table. If the key is
 * not in the table HASH_ERROR_KEY_NOT_FOUND is returned. If the type of key is
 * invalid HASH_ERROR_BAD_KEY_TYPE is returned. Otherwise HASH_SUCCESS is
 * returned. If the result is anything other than HASH_SUCCESS the value pointer
 * is not updated.
 */
int hash_lookup(hash_table_t *table, hash_key_t *key, hash_value_t *value);

/*
 * Like hash_lookup() except if the key is not in the table then it is entered
 * into the table and assigned the default_value. Thus it is not possible for
 * hash_get_default() to return HASH_ERROR_KEY_NOT_FOUND.
 */
int hash_get_default(hash_table_t *table, hash_key_t *key, hash_value_t *value, hash_value_t *default_value);

/*
 * Delete the item from the table. The key and its type are specified in the key
 * parameter which are passed by reference. If the key was in the table
 * HASH_SUCCESS is returned otherwise HASH_ERROR_KEY_NOT_FOUND is
 * returned. Memory allocated to hold the key if it was a string is free by the
 * hash library, but values which are pointers to user data must be freed by the
 * caller (see delete_callback).
 */
int hash_delete(hash_table_t *table, hash_key_t *key);

/*
 * Often it is useful to operate on every key and/or value in the hash
 * table. The hash_iterate function will invoke the users callback on every item
 * in the table as long as the callback returns a non-zero value. Returning a
 * zero from the callback can be used to halt the iteration prematurely if some
 * condition is met. The user_data parameter is passed to the callback
 * function. It can be used for any purpose the caller wants. The callback
 * parameter list is:
 *
 * bool callback(hash_entry_t *item, hash_table_t *user_data);
 *
 * WARNING: Do not modify the contents of the table during an iteration it will
 * produce undefined results. If you need to visit each item in the table and
 * potentially delete or insert some entries the proper way to do this is to
 * obtain a list of keys or items using hash_keys() or hash_items() which
 * returns a copy of the keys or items. You may then loop on the list returned
 * and safely update the table (don't forget to free the list when done).
 */
int hash_iterate(hash_table_t *table, hash_iterate_callback callback, void *user_data);

/*
 * This is another method to iterate on every key/value in the hash table.
 * However, unlike hash_iterate which requires a callback this function returns
 * an iterator object which contains a next() function pointer.  Each time
 * next() is invoked it returns a pointer to the next hash entry in the table,
 * then NULL when all entries have been visited. In some circumstances it's more
 * convenient than having to define a callback. Like hash_iterate() one must
 * never modify the table contents during iteration. If you intend to modify the
 * table during iteration use the functions which return an indepent list of
 * keys, values, or items instead and iterate on the list.  The iterator object
 * must be free'ed when you're done iterating by calling free() on it.
 *
 * Example:
 *
 * struct hash_iter_context_t *iter;
 * hash_entry_t *entry;
 *
 * iter = new_hash_iter_context(table);
 * while ((entry = iter->next(iter)) != NULL) {
 *     do_something(entry);
 * }
 * free(iter);
 */
struct hash_iter_context_t *new_hash_iter_context(hash_table_t *table);

/*
 * Return a count of how many items are currently in the table.
 */
unsigned long hash_count(hash_table_t *table);

/*
 * Get an array of all the keys in the table returned through the keys
 * parameter. The number of elements in the array is returned in the count
 * parameter. Each key in the array is a copy of the key in the table. Any
 * pointers in the key will be shared with the table entry thus both the item in
 * the array and the item in the table point to the same object. The array
 * should be freed by calling free(). The function may return
 * HASH_ERROR_NO_MEMORY, otherwise HASH_SUCCESS.
 */
int hash_keys(hash_table_t *table, unsigned long *count, hash_key_t **keys);

/*
 * Get an array of all the values in the table returned through the values
 * parameter. The number of elements in the array is returned in the count
 * parameter. Each value in the array is a copy of the value in the table. Any
 * pointers in the value will be shared with the table entry thus both the item in
 * the array and the item in the table point to the same object. The array
 * should be freed by calling free(). The function may return
 * HASH_ERROR_NO_MEMORY, otherwise HASH_SUCCESS.
 */
int hash_values(hash_table_t *table, unsigned long *count, hash_value_t **values);


/*
 * Get an array of all the entries in the table returned through the entries
 * parameter. The number of elements in the array is returned in the count
 * parameter. Each entry in the array is a copy of the entry in the table. Any
 * pointers in the entry will be shared with the table entry thus both the item in
 * the array and the item in the table point to the same object. The array
 * should be freed by calling free(). The function may return
 * HASH_ERROR_NO_MEMORY, otherwise HASH_SUCCESS.
 */
int hash_entries(hash_table_t *table, unsigned long *count, hash_entry_t **entries);

/*
 * Return boolean if the key is in the table.
 */
bool hash_has_key(hash_table_t *table, hash_key_t *key);

#endif