268 lines
11 KiB
C
268 lines
11 KiB
C
/*
|
|
* cfuhash.h - This file is part of the libcfu library
|
|
*
|
|
* Copyright (c) 2005 Don Owens. All rights reserved.
|
|
*
|
|
* This code is released under the BSD license:
|
|
*
|
|
* Redistribution and use in source and binary forms, with or without
|
|
* modification, are permitted provided that the following conditions
|
|
* are met:
|
|
*
|
|
* * Redistributions of source code must retain the above copyright
|
|
* notice, this list of conditions and the following disclaimer.
|
|
*
|
|
* * Redistributions in binary form must reproduce the above
|
|
* copyright notice, this list of conditions and the following
|
|
* disclaimer in the documentation and/or other materials provided
|
|
* with the distribution.
|
|
*
|
|
* * Neither the name of the author nor the names of its
|
|
* contributors may be used to endorse or promote products derived
|
|
* from this software without specific prior written permission.
|
|
*
|
|
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
|
|
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
|
|
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
|
|
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
|
|
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
|
|
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
|
|
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
|
|
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
|
|
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
|
|
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
|
|
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
|
|
* OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
*/
|
|
|
|
#ifndef CFU_HASH_H_
|
|
#define CFU_HASH_H_
|
|
|
|
#include <cfu.h>
|
|
#include <stdio.h>
|
|
|
|
CFU_BEGIN_DECLS
|
|
|
|
/* The hash table itself. */
|
|
typedef struct cfuhash_table cfuhash_table_t;
|
|
|
|
/* Prototype for a pointer to a hashing function. */
|
|
typedef unsigned int (*cfuhash_function_t)(const void *key, size_t length);
|
|
|
|
/* Prototype for a pointer to a free function. */
|
|
typedef void (*cfuhash_free_fn_t)(void *data);
|
|
|
|
/* Prototype for a pointer to a function that determines whether
|
|
* or not to remove an entry from the hash.
|
|
*/
|
|
typedef int (*cfuhash_remove_fn_t)(void *key, size_t key_size, void *data, size_t data_size,
|
|
void *arg);
|
|
|
|
/* Prototype for a pointer to a function to be called foreach
|
|
* key/value pair in the hash by cfuhash_foreach(). Iteration
|
|
* stops if a non-zero value is returned.
|
|
*/
|
|
typedef int (*cfuhash_foreach_fn_t)(void *key, size_t key_size, void *data, size_t data_size,
|
|
void *arg);
|
|
|
|
/* Creates a new hash table. */
|
|
cfuhash_table_t * cfuhash_new(void);
|
|
|
|
/* Creates a new hash table with the specified size (number of
|
|
* buckets).
|
|
*/
|
|
cfuhash_table_t * cfuhash_new_with_initial_size(size_t size);
|
|
|
|
/* Creates a new hash table with the specified flags. Pass zero
|
|
* for flags if you want the defaults.
|
|
*/
|
|
cfuhash_table_t * cfuhash_new_with_flags(unsigned int flags);
|
|
|
|
/* Same as cfuhash_new() except automatically calls cfuhash_set_free_fn(). */
|
|
cfuhash_table_t * cfuhash_new_with_free_fn(cfuhash_free_fn_t ff);
|
|
|
|
/* Copies entries in src to dst */
|
|
int cfuhash_copy(cfuhash_table_t *src, cfuhash_table_t *dst);
|
|
|
|
/* Returns a new hash containing entries from both hash tables.
|
|
* For any entries with the same key, the one from ht2 wins.
|
|
*/
|
|
cfuhash_table_t * cfuhash_merge(cfuhash_table_t *ht1, cfuhash_table_t *ht2,
|
|
unsigned int flags);
|
|
|
|
/* Sets the hashing function to use when computing which bucket to add
|
|
* entries to. It should return a 32-bit unsigned integer. By
|
|
* default, Perl's hashing algorithm is used.
|
|
*/
|
|
int cfuhash_set_hash_function(cfuhash_table_t *ht, cfuhash_function_t hf);
|
|
|
|
/* Sets the thresholds for when to rehash. The ratio
|
|
* num_entries/buckets is compared against low and high. If it is
|
|
* below 'low' or above 'high', the hash will shrink or grow,
|
|
* respectively, unless the flags say to do otherwise.
|
|
*/
|
|
int cfuhash_set_thresholds(cfuhash_table_t *ht, float low, float high);
|
|
|
|
/* Sets the function to use when removing an entry from the hash,
|
|
* i.e., when replacing an existing entry, deleting an entry, or
|
|
* clearing the hash. It is passed the value of the entry as a
|
|
* void *.
|
|
*/
|
|
int cfuhash_set_free_function(cfuhash_table_t * ht, cfuhash_free_fn_t ff);
|
|
|
|
/* Returns the hash's flags. See below for flag definitions. */
|
|
unsigned int cfuhash_get_flags(cfuhash_table_t *ht);
|
|
|
|
/* Sets a flag. */
|
|
unsigned int cfuhash_set_flag(cfuhash_table_t *ht, unsigned int flag);
|
|
|
|
/* Clears a flag. */
|
|
unsigned int cfuhash_clear_flag(cfuhash_table_t *ht, unsigned int new_flag);
|
|
|
|
/* Returns the value for the entry with given key. If key_size is -1,
|
|
* key is assumed to be a null-terminated string. If data_size is not
|
|
* NULL, the size of the value is placed into data_size.
|
|
*/
|
|
int cfuhash_get_data(cfuhash_table_t *ht, const void *key, size_t key_size,
|
|
void **data, size_t *data_size);
|
|
|
|
/* Returns 1 if an entry with the given key exists in the hash, 0 otherwise. */
|
|
int cfuhash_exists_data(cfuhash_table_t *ht, const void *key, size_t key_size);
|
|
|
|
/* Inserts the given data value into the hash and associates it with
|
|
* key. If key_size is -1, key is assumed to be a null-terminated
|
|
* string. If data_size is -1, it is assumed to be a null-terminated
|
|
* string (it's length will be calculated using strlen). If
|
|
* data_size is zero, it will be returned as zero when the value is
|
|
* requested.
|
|
*/
|
|
int cfuhash_put_data(cfuhash_table_t *ht, const void *key, size_t key_size, void *data,
|
|
size_t data_size, void **r);
|
|
|
|
/* Clears the hash table (deletes all entries). */
|
|
void cfuhash_clear(cfuhash_table_t *ht);
|
|
|
|
/* Deletes the entry in the hash associated with key. If the entry
|
|
* existed, it's value will be returned.
|
|
*/
|
|
void * cfuhash_delete_data(cfuhash_table_t *ht, const void *key, size_t key_size);
|
|
|
|
/* Returns all the keys from the hash. The number of keys is placed
|
|
* into the value pointed to by num_keys. If key_sizes is not NULL,
|
|
* it will be set to an array of key sizes. If fast is zero, copies
|
|
* of the keys are returned. Otherwise, pointers to the real keys
|
|
* will be returned.
|
|
*/
|
|
void **cfuhash_keys_data(cfuhash_table_t *ht, size_t *num_keys, size_t **key_sizes,
|
|
int fast);
|
|
|
|
/* Initializes a loop over all the key/value pairs in the hash. It
|
|
* returns the first key/value pair (see cfuhash_next_data()). 1 is
|
|
* returned if there are any entries in the hash. 0 is returned
|
|
* otherwise.
|
|
*/
|
|
int cfuhash_each_data(cfuhash_table_t *ht, void **key, size_t *key_size, void **data,
|
|
size_t *data_size);
|
|
|
|
/* Gets the next key/value pair from the hash. You must initialize
|
|
* the loop using cfuhash_each_data() before calling this function.
|
|
* If a entry is left to return, 1 is returned from the function. 0
|
|
* is returned if there are no more entries in the hash.
|
|
*/
|
|
int cfuhash_next_data(cfuhash_table_t *ht, void **key, size_t *key_size, void **data,
|
|
size_t *data_size);
|
|
|
|
/* Iterates over the key/value pairs in the hash, passing each one
|
|
* to r_fn, and removes all entries for which r_fn returns true.
|
|
* If ff is not NULL, it is the passed the data to be freed. arg
|
|
* is passed to r_fn.
|
|
*/
|
|
size_t cfuhash_foreach_remove(cfuhash_table_t *ht, cfuhash_remove_fn_t r_fn,
|
|
cfuhash_free_fn_t ff, void *arg);
|
|
|
|
/* Iterates over the key/value pairs in the hash, passing each one
|
|
* to fe_fn, along with arg. This locks the hash, so do not call
|
|
* any operations on the hash from within fe_fn unless you really
|
|
* know what you're doing. A non-zero return value from fe_fn()
|
|
* stops the iteration.
|
|
*/
|
|
size_t cfuhash_foreach(cfuhash_table_t *ht, cfuhash_foreach_fn_t fe_fn, void *arg);
|
|
|
|
/* Frees all resources allocated by the hash. If ff is not NULL, it
|
|
* is called for each hash entry with the value of the entry passed as
|
|
* its only argument. If ff is not NULL, it overrides any function
|
|
* set previously with cfuhash_set_free_function().
|
|
*/
|
|
int cfuhash_destroy(cfuhash_table_t *ht);
|
|
|
|
int cfuhash_destroy_with_free_fn(cfuhash_table_t *ht, cfuhash_free_fn_t ff);
|
|
|
|
/* Rebuild the hash to better accomodate the number of entries. See
|
|
* cfuhash_set_thresholds().
|
|
*/
|
|
int cfuhash_rehash(cfuhash_table_t *ht);
|
|
|
|
/* Returns the number entries in the hash. */
|
|
size_t cfuhash_num_entries(cfuhash_table_t *ht);
|
|
|
|
/* Returns the number of buckets allocated for the hash. */
|
|
size_t cfuhash_num_buckets(cfuhash_table_t *ht);
|
|
|
|
/* Returns the number of buckets actually used out of the total number
|
|
* allocated for the hash.
|
|
*/
|
|
size_t cfuhash_num_buckets_used(cfuhash_table_t *ht);
|
|
|
|
/* Assumes all the keys and values are null-terminated strings and
|
|
* returns a bencoded string representing the hash (see
|
|
* http://www.bittorrent.com/protocol.html)
|
|
*/
|
|
char * cfuhash_bencode_strings(cfuhash_table_t *ht);
|
|
|
|
/* Locks the hash. Use this with the each and next functions for
|
|
* concurrency control. Note that the hash is locked automatically
|
|
* when doing inserts and deletes, so if you lock the hash and then
|
|
* try to insert something into it, you may get into a deadlock,
|
|
* depending on your system defaults for how mutexes work.
|
|
*/
|
|
int cfuhash_lock(cfuhash_table_t *ht);
|
|
|
|
/* Unlocks the hash. Use this with the each an next functions for
|
|
* concurrency control. The caveat for cfuhash_lcok() also applies to
|
|
* this function.
|
|
*/
|
|
int cfuhash_unlock(cfuhash_table_t *ht);
|
|
|
|
/* Pretty print the hash's key/value pairs to the stream fp. It is
|
|
* assumed that all the keys and values are null-terminated strings.
|
|
*/
|
|
int cfuhash_pretty_print(cfuhash_table_t *ht, FILE *fp);
|
|
|
|
/* These are like the _data versions of these functions, with the
|
|
* following exceptions:
|
|
* 1) They assume that the key provided is a null-terminated string.
|
|
* 2) They don't worry about the size of the data.
|
|
* 3) Returned keys or values are the return value of the function.
|
|
*/
|
|
void * cfuhash_get(cfuhash_table_t *ht, const char *key);
|
|
int cfuhash_exists(cfuhash_table_t *ht, const char *key);
|
|
void * cfuhash_put(cfuhash_table_t *ht, const char *key, void *data);
|
|
void * cfuhash_delete(cfuhash_table_t *ht, const char *key);
|
|
int cfuhash_each(cfuhash_table_t *ht, char **key, void **data);
|
|
int cfuhash_next(cfuhash_table_t *ht, char **key, void **data);
|
|
void **cfuhash_keys(cfuhash_table_t *ht, size_t *num_keys, int fast);
|
|
|
|
|
|
/* hash table flags */
|
|
#define CFUHASH_NOCOPY_KEYS 1 /* do not copy the key when inserting a hash entry */
|
|
#define CFUHASH_NO_LOCKING (1 << 1) /* do not make the hash thread-safe */
|
|
#define CFUHASH_FROZEN (1 << 2) /* do not rehash when the size thresholds are reached */
|
|
#define CFUHASH_FROZEN_UNTIL_GROWS (1 << 3) /* do not shrink the hash until it has grown */
|
|
#define CFUHASH_FREE_DATA (1 << 4) /* call free() on each value when the hash is destroyed */
|
|
#define CFUHASH_IGNORE_CASE (1 << 5) /* treat keys case-insensitively */
|
|
|
|
|
|
CFU_END_DECLS
|
|
|
|
#endif
|