154 lines
4.6 KiB
C
154 lines
4.6 KiB
C
/* Copyright (C) 2005 David Decotigny
|
|
|
|
This program is free software; you can redistribute it and/or
|
|
modify it under the terms of the GNU General Public License
|
|
as published by the Free Software Foundation; either version 2
|
|
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 General Public License for more details.
|
|
|
|
You should have received a copy of the GNU General Public License
|
|
along with this program; if not, write to the Free Software
|
|
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
|
|
USA.
|
|
*/
|
|
#ifndef _SOS_HASH_H_
|
|
#define _SOS_HASH_H_
|
|
|
|
#include <sos/types.h>
|
|
#include <sos/errno.h>
|
|
#include <sos/macros.h>
|
|
|
|
/**
|
|
* hash.h
|
|
*
|
|
* Hash table implementation. The key and the element structure is
|
|
* user-definable. Each element must embed:
|
|
* - the key
|
|
* - a sos_hash_linkage structure
|
|
*
|
|
* The DANGER is that the key value must NOT be changed while the
|
|
* element is inserted in the hash
|
|
*/
|
|
|
|
/** Prototype of a hash function */
|
|
typedef unsigned long (sos_hash_func_t)(const void * ptr_key);
|
|
|
|
/** Prototype of a key comparison function */
|
|
typedef sos_bool_t (sos_hash_key_eq_func_t)(const void * ptr_key1,
|
|
const void * ptr_key2);
|
|
|
|
/** Prototype of a key/value iteration function: when FALSE = stop now ! */
|
|
typedef sos_bool_t (sos_hash_map_func_t)(void * custom_data,
|
|
void * elt_with_key);
|
|
|
|
|
|
/** Opaque structure */
|
|
struct sos_hash_table;
|
|
|
|
/** This structure must be embedded in the elements to be insterted in
|
|
the hah */
|
|
struct sos_hash_linkage
|
|
{
|
|
struct sos_hash_linkage * h_prev, * h_next;
|
|
};
|
|
|
|
|
|
/**
|
|
* Creation of a hash table
|
|
*
|
|
* @param name The name of the hash table (debug)
|
|
* @param elt_type The type of the elements
|
|
* @param hfunc The hash function (@see sos_hash_func_t). When NULL:
|
|
* identity (native unsigned long keys assumed)
|
|
* @param eqfunc The element comparaison function (@see
|
|
* sos_hash_key_eq_func_t). When NULL: native
|
|
* unsigned long comparison
|
|
* @param nbuckets The number of bucks in the hash
|
|
* @param name_key_field The name of the field in the element type
|
|
* that holds the key
|
|
* @param name_key_field The name of the field in the element type
|
|
* that hold the prev/next hash linkage data
|
|
*/
|
|
#define sos_hash_create(name,elt_type,hfunc,eqfunc,nbuckets, \
|
|
name_key_field,name_h_linkage) \
|
|
_sos_hash_create_FULL(name, hfunc, eqfunc, nbuckets, \
|
|
offsetof(elt_type, name_key_field), \
|
|
offsetof(elt_type, name_h_linkage))
|
|
|
|
|
|
/**
|
|
* @note Real hash creation function called by the sos_hash_create
|
|
* macro
|
|
*
|
|
* @param key_hasher When NULL: the value of the hash is directly the
|
|
* pointer address
|
|
* @param key_compare When NULL: compare directly the pointer addresses
|
|
*/
|
|
struct sos_hash_table *
|
|
_sos_hash_create_FULL(const char *name,
|
|
sos_hash_func_t *key_hasher,
|
|
sos_hash_key_eq_func_t *key_iseq,
|
|
sos_count_t nbuckets,
|
|
sos_uoffset_t offset_h_key,
|
|
sos_uoffset_t offset_h_linkage);
|
|
|
|
|
|
/** Return the number of elements in the hash table */
|
|
sos_count_t sos_hash_get_nb_elts(const struct sos_hash_table * h);
|
|
|
|
|
|
/** Does not free the elements themselves ! */
|
|
sos_ret_t sos_hash_dispose(struct sos_hash_table *h);
|
|
|
|
|
|
/**
|
|
* Insert the element in the hash, associating it with the key that it
|
|
* embeds
|
|
*
|
|
* Makes sure the element is not already in the hash
|
|
*/
|
|
sos_ret_t sos_hash_insert(struct sos_hash_table *h,
|
|
void *elt_with_key);
|
|
|
|
|
|
/** Look for the element stored in the hash that has the key given by
|
|
ptr_key */
|
|
void * sos_hash_lookup(struct sos_hash_table *h,
|
|
const void * ptr_key);
|
|
|
|
|
|
/** Remove an element from the hash, previously returned by
|
|
sos_hash_lookup */
|
|
sos_ret_t sos_hash_remove(struct sos_hash_table *h,
|
|
void *elt);
|
|
|
|
|
|
/**
|
|
* Call iter_func on each of the elements in the hash table
|
|
* Stop when iter_func returns 0 (and returns FALSE). Otherwise return
|
|
* TRUE.
|
|
*
|
|
* @note iter_func must NOT block !
|
|
* @note No particular locking
|
|
*/
|
|
sos_bool_t sos_hash_walk(const struct sos_hash_table *h,
|
|
sos_hash_map_func_t * iter_func,
|
|
void * custom_data);
|
|
|
|
|
|
/*
|
|
* Common hash functions
|
|
*/
|
|
|
|
/* key = 64bits integer */
|
|
unsigned long sos_hash_ui64(const void * ptr_key);
|
|
sos_bool_t sos_hash_key_eq_ui64(const void * ptr_key1,
|
|
const void * ptr_key2);
|
|
|
|
|
|
#endif /* _SOS_HASH_H_ */
|