gdsl_hash.h

一个通用的C语言实现的数据结构

/*
 * This file is part of the Generic Data Structures Library (GDSL).
 * Copyright (C) 1998-2006 Nicolas Darnis <[e-mail]>.
 *
 * The GDSL library 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.
 *
 * The GDSL library 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 the GDSL library; see the file COPYING.
 * If not, write to the Free Software Foundation, Inc., 
 * 59 Temple Place, Suite 330, Boston, MA  02111-1307, USA.
 *
 * $RCSfile: gdsl_hash.h,v $
 * $Revision: 1.25 $
 * $Date: 2006/03/04 16:32:05 $
 */


#ifndef _GDSL_HASH_H_
#define _GDSL_HASH_H_


#include <stdio.h>


#include "gdsl_types.h"


#ifdef __cplusplus
extern "C" 
{
#endif /* __cplusplus */


/**
 * @defgroup gdsl_hash Hashtable manipulation module
 * @{
 */


/**
 * @brief GDSL hashtable type.
 *
 * This type is voluntary opaque. Variables of this kind could'nt be directly
 * used, but by the functions of this module.
 */
typedef struct hash_table* gdsl_hash_t;

/**
 * @brief GDSL hashtable key function type.
 * @post Returned value must be != "" && != NULL.
 * @param VALUE The value used to get the key from
 * @return The key associated to the VALUE.
 */
typedef const char* (*gdsl_key_func_t) (void* VALUE
					);

/**
 * @brief GDSL hashtable hash function type.
 * @param KEY the key used to compute the hash code.
 * @return The hashed value computed from KEY.
 */
typedef ulong (*gdsl_hash_func_t) (const char* KEY
				   );

/******************************************************************************/
/* Generic hash function                                                      */
/******************************************************************************/

/**
 * @brief Computes a hash value from a NULL terminated character string.
 *
 * This function computes a hash value from the NULL terminated KEY string.
 *
 * @note Complexity: O ( |key| )
 * @pre KEY must be NULL-terminated.
 * @param KEY The NULL terminated string to compute the key from
 * @return the hash code computed from KEY.
 */
extern ulong
gdsl_hash (const char* KEY
	   );

/******************************************************************************/
/* Management functions of hashtables                                         */
/******************************************************************************/

/**
 * @brief Create a new hashtable.
 *
 * Allocate a new hashtable data structure which name is set to a copy of NAME.
 * The new hashtable will contain initially INITIAL_ENTRIES_NB lists. This value
 * could be (only) increased with gdsl_hash_modify() function. Until this 
 * function is called, then all H's lists entries have no size limit.
 * The function pointers ALLOC_F and FREE_F could be used to respectively, alloc
 * and free elements in the hashtable. The KEY_F function must provide a unique 
 * key associated to its argument. The HASH_F function must compute a hash code
 * from its argument.
 * These pointers could be set to NULL to use the default ones:
 * - the default ALLOC_F simply returns its argument
 * - the default FREE_F does nothing
 * - the default KEY_F simply returns its argument
 * - the default HASH_F is gdsl_hash() above
 *
 * @note Complexity: O( 1 )
 * @pre nothing.
 * @param NAME The name of the new hashtable to create
 * @param ALLOC_F Function to alloc element when inserting it in the hashtable
 * @param FREE_F Function to free element when deleting it from the hashtable
 * @param KEY_F Function to get the key from an element
 * @param HASH_F Function used to compute the hash value.
 * @param INITIAL_ENTRIES_NB Initial number of entries of the hashtable
 * @return the newly allocated hashtable in case of success.
 * @return NULL in case of insufficient memory.
 * @see gdsl_hash_free()
 * @see gdsl_hash_flush()
 * @see gdsl_hash_insert()
 * @see gdsl_hash_modify()
 */
extern gdsl_hash_t
gdsl_hash_alloc (const char* NAME,
		 gdsl_alloc_func_t ALLOC_F,
		 gdsl_free_func_t FREE_F,
		 gdsl_key_func_t KEY_F,
		 gdsl_hash_func_t HASH_F,
		 ushort INITIAL_ENTRIES_NB
		 );

/**
 * @brief Destroy a hashtable.
 *
 * Deallocate all the elements of the hashtable H by calling H's FREE_F function
 * passed to gdsl_hash_alloc(). The name of H is deallocated and H is 
 * deallocated itself too.
 *
 * @note Complexity: O( |H| )
 * @pre H must be a valid gdsl_hash_t
 * @param H The hashtable to destroy
 * @see gdsl_hash_alloc()
 * @see gdsl_hash_flush()
 */
extern void
gdsl_hash_free (gdsl_hash_t H
		);

/**
 * @brief Flush a hashtable.
 *
 * Deallocate all the elements of the hashtable H by calling H's FREE_F function
 * passed to gdsl_hash_alloc(). H is not deallocated itself and H's name is not
 * modified.
 *
 * @note Complexity: O( |H| )
 * @pre H must be a valid gdsl_hash_t
 * @param H The hashtable to flush
 * @see gdsl_hash_alloc()
 * @see gdsl_hash_free()
 */
extern void
gdsl_hash_flush (gdsl_hash_t H
		 );

/******************************************************************************/
/* Consultation functions of hashtables                                       */
/******************************************************************************/

/**
 * @brief Get the name of a hashtable.
 * @note Complexity: O( 1 )
 * @pre H must be a valid gdsl_hash_t
 * @post The returned string MUST NOT be freed.
 * @param H The hashtable to get the name from
 * @return the name of the hashtable H.
 * @see gdsl_hash_set_name()
 */
extern const char*
gdsl_hash_get_name (const gdsl_hash_t H
		    );

/**
 * @brief Get the number of entries of a hashtable.
 * @note Complexity: O( 1 )
 * @pre H must be a valid gdsl_hash_t
 * @param H The hashtable to use.
 * @return the number of lists entries of the hashtable H.
 * @see gdsl_hash_get_size()
 * @see gdsl_hash_fill_factor()
 */
extern ushort
gdsl_hash_get_entries_number (const gdsl_hash_t H
			      );

/**
 * @brief Get the max number of elements allowed in each entry of a hashtable.
 * @note Complexity: O( 1 )
 * @pre H must be a valid gdsl_hash_t
 * @param H The hashtable to use.
 * @return 0 if no lists max size was set before (ie. no limit for H's entries).
 * @return the max number of elements for each entry of the hashtable H, if the
 * function gdsl_hash_modify() was used with a NEW_LISTS_MAX_SIZE greather than 
 * the actual one.
 * @see gdsl_hash_fill_factor()
 * @see gdsl_hash_get_entries_number()
 * @see gdsl_hash_get_longest_list_size()
 * @see gdsl_hash_modify()
 */
extern ushort
gdsl_hash_get_lists_max_size (const gdsl_hash_t H
			      );

/**
 * @brief Get the number of elements of the longest list entry of a hashtable.
 * @note Complexity: O( L ), where L = gdsl_hash_get_entries_number(H)
 * @pre H must be a valid gdsl_hash_t
 * @param H The hashtable to use.
 * @return the number of elements of the longest list entry of the hashtable H.
 * @see gdsl_hash_get_size()
 * @see gdsl_hash_fill_factor()
 * @see gdsl_hash_get_entries_number()
 * @see gdsl_hash_get_lists_max_size()
 */
extern ushort
gdsl_hash_get_longest_list_size (const gdsl_hash_t H
				 );

/**
 * @brief Get the size of a hashtable.
 * @note Complexity: O( L ), where L = gdsl_hash_get_entries_number(H)
 * @pre H must be a valid gdsl_hash_t
 * @param H The hashtable to get the size from
 * @return the number of elements of H (noted |H|).
 * @see gdsl_hash_get_entries_number()
 * @see gdsl_hash_fill_factor()
 * @see gdsl_hash_get_longest_list_size()
 */
extern ulong
gdsl_hash_get_size (const gdsl_hash_t H
		    );

/**
 * @brief Get the fill factor of a hashtable.
 * @note Complexity: O( L ), where L = gdsl_hash_get_entries_number(H)
 * @pre H must be a valid gdsl_hash_t
 * @param H The hashtable to use
 * @return The fill factor of H, computed as |H| / L
 * @see gdsl_hash_get_entries_number()
 * @see gdsl_hash_get_longest_list_size()
 * @see gdsl_hash_get_size()
 */
extern double
gdsl_hash_get_fill_factor (const gdsl_hash_t H
			   );

/******************************************************************************/
/* Modification functions of hashtables                                       */
/******************************************************************************/
  
/**
 * @brief Set the name of a hashtable.
 *