hash.h

Simple Operating Systems （简称SOS）是一个可以运行在X86平台上（包括QEMU

/* 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);

/** 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)
 * @param hfunc The element comparaison function (@see
 *              sos_hash_key_eq_func_t)
 * @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,hcmp,nbuckets,\
                        name_key_field,name_h_linkage)    \
  _sos_hash_create_FULL(name, hfunc, hcmp, 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);


/** 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);


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