gdsl_hash.h

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

 * Change the previous name of the hashtable H to a copy of NEW_NAME.
 * 
 * @note Complexity: O( 1 )
 * @pre H must be a valid gdsl_hash_t
 * @param H The hashtable to change the name
 * @param NEW_NAME The new name of H
 * @return the modified hashtable in case of success.
 * @return NULL in case of insufficient memory.
 * @see gdsl_hash_get_name()
 */
extern gdsl_hash_t
gdsl_hash_set_name (gdsl_hash_t H,
		    const char* NEW_NAME
		    );

/**
 * @brief Insert an element into a hashtable (PUSH).
 *
 * Allocate a new element E by calling H's ALLOC_F function on VALUE. The key K
 * of the new element E is computed using KEY_F called on E. If the value of
 * gdsl_hash_get_lists_max_size(H) is not reached, or if it is equal to zero,
 * then the insertion is simple. Otherwise, H is re-organized as follow:
 * - its actual gdsl_hash_get_entries_number(H) (say N) is modified as N * 2 + 1
 * - its actual gdsl_hash_get_lists_max_size(H) (say M) is modified as M * 2
 * The element E is then inserted into H at the entry computed by HASH_F( K ) 
 * modulo gdsl_hash_get_entries_number(H). ALLOC_F, KEY_F and HASH_F are the 
 * function pointers passed to gdsl_hash_alloc(). 
 *
 * @note Complexity: O( 1 ) if gdsl_hash_get_lists_max_size(H) is not reached or
 * if it is equal to zero
 * @note Complexity: O ( gdsl_hash_modify (H) ) if 
 * gdsl_hash_get_lists_max_size(H) is reached, so H needs to grow
 * @pre H must be a valid gdsl_hash_t
 * @param H The hashtable to modify
 * @param VALUE The value used to make the new element to insert into H
 * @return the inserted element E in case of success.
 * @return NULL in case of insufficient memory.
 * @see gdsl_hash_alloc()
 * @see gdsl_hash_remove()
 * @see gdsl_hash_delete()
 * @see gdsl_hash_get_size()
 * @see gdsl_hash_get_entries_number()
 * @see gdsl_hash_modify()
 */
extern gdsl_element_t
gdsl_hash_insert (gdsl_hash_t H,
		  void* VALUE
		  );
  
/**
 * @brief Remove an element from a hashtable (POP).
 *
 * Search into the hashtable H for the first element E equal to KEY.
 * If E is found, it is removed from H and then returned. 
 *
 * @note Complexity: O( M ), where M is the average size of H's lists
 * @pre H must be a valid gdsl_hash_t
 * @param H The hashtable to modify
 * @param KEY The key used to find the element to remove
 * @return the first founded element equal to KEY in H in case is found.
 * @return NULL in case no element equal to KEY is found in H.
 * @see gdsl_hash_insert()
 * @see gdsl_hash_search()
 * @see gdsl_hash_delete()
 */
extern gdsl_element_t
gdsl_hash_remove (gdsl_hash_t H,
		  const char* KEY
		  );
/**
 * @brief Delete an element from a hashtable.
 *
 * Remove from he hashtable H the first founded element E equal to KEY.
 * If E is found, it is removed from H and E is deallocated using H's FREE_F
 * function passed to gdsl_hash_alloc(), then H is returned.
 *
 * @note Complexity: O( M ), where M is the average size of H's lists
 * @pre H must be a valid gdsl_hash_t
 * @param H The hashtable to modify
 * @param KEY The key used to find the element to remove
 * @return the modified hashtable after removal of E if E was found.
 * @return NULL if no element equal to KEY was found.
 * @see gdsl_hash_insert()
 * @see gdsl_hash_search()
 * @see gdsl_hash_remove()
 */
extern gdsl_hash_t
gdsl_hash_delete (gdsl_hash_t H,
		  const char* KEY
		  );

/**
 * @brief Increase the dimensions of a hashtable.
 *
 * The hashtable H is re-organized to have NEW_ENTRIES_NB lists entries. Each
 * entry is limited to NEW_LISTS_MAX_SIZE elements. After a call to this 
 * function, all insertions into H will make H automatically growing if needed.
 * The grow is needed each time an insertion makes an entry list to reach 
 * NEW_LISTS_MAX_SIZE elements. In this case, H will be reorganized 
 * automatically by gdsl_hash_insert().
 *
 * @note Complexity: O( |H| )
 * @pre H must be a valid gdsl_hash_t
 *      & NEW_ENTRIES_NB > gdsl_hash_get_entries_number(H)
 *      & NEW_LISTS_MAX_SIZE > gdsl_hash_get_lists_max_size(H)
 * @param H The hashtable to modify
 * @param NEW_ENTRIES_NB
 * @param NEW_LISTS_MAX_SIZE
 * @return the modified hashtable H in case of success
 * @return NULL in case of failure, 
 *         or in case NEW_ENTRIES_NB <= gdsl_hash_get_entries_number(H)
 *         or in case NEW_LISTS_MAX_SIZE <= gdsl_hash_get_lists_max_size(H)
 *         in these cases, H is not modified
 * @see gdsl_hash_insert()
 * @see gdsl_hash_get_entries_number()
 * @see gdsl_hash_get_fill_factor()
 * @see gdsl_hash_get_longest_list_size()
 * @see gdsl_hash_get_lists_max_size()
 */
extern gdsl_hash_t
gdsl_hash_modify (gdsl_hash_t H, 
		  ushort NEW_ENTRIES_NB, 
		  ushort NEW_LISTS_MAX_SIZE
		  );

/******************************************************************************/
/* Search functions of hashtables                                             */
/******************************************************************************/

/**
 * @brief Search for a particular element into a hashtable (GET).
 *
 * Search the first element E equal to KEY in the hashtable H.
 *
 * @note Complexity: O( M ), where M is the average size of H's lists
 * @pre H must be a valid gdsl_hash_t
 * @param H The hashtable to search the element in
 * @param KEY The key to compare H's elements with
 * @return the founded element E if it was found.
 * @return NULL in case the searched element E was not found.
 * @see gdsl_hash_insert()
 * @see gdsl_hash_remove()
 * @see gdsl_hash_delete()
 */
extern gdsl_element_t
gdsl_hash_search (const gdsl_hash_t H,
		  const char* KEY
		  );

/******************************************************************************/
/* Parse functions of hashtables                                              */
/******************************************************************************/

/**
 * @brief Parse a hashtable.
 *
 * Parse all elements of the hashtable H. The MAP_F function is called on each 
 * H's element with USER_DATA argument. If MAP_F returns GDSL_MAP_STOP then
 * gdsl_hash_map() stops and returns its last examinated element.
 *
 * @note Complexity: O( |H| )
 * @pre H must be a valid gdsl_hash_t & MAP_F != NULL
 * @param H The hashtable to map
 * @param MAP_F The map function.
 * @param USER_DATA User's datas passed to MAP_F
 * @return the first element for which MAP_F returns GDSL_MAP_STOP.
 * @return NULL when the parsing is done.
 */
extern gdsl_element_t
gdsl_hash_map (const gdsl_hash_t H,
	       gdsl_map_func_t MAP_F,
	       void* USER_DATA
	       );

/******************************************************************************/
/* Input/output functions of hashtables                                       */
/******************************************************************************/

/**
 * @brief Write all the elements of a hashtable to a file.
 *
 * Write the elements of the hashtable H to OUTPUT_FILE, using WRITE_F function.
 * Additionnal USER_DATA argument could be passed to WRITE_F.
 *
 * @note Complexity: O( |H| )
 * @pre H must be a valid gdsl_hash_t & OUTPUT_FILE != NULL & WRITE_F != NULL
 * @param H The hashtable to write.
 * @param WRITE_F The write function.
 * @param OUTPUT_FILE The file where to write H's elements.
 * @param USER_DATA User's datas passed to WRITE_F.
 * @see gdsl_hash_write_xml()
 * @see gdsl_hash_dump()
 */
extern void
gdsl_hash_write (const gdsl_hash_t H,
		 gdsl_write_func_t WRITE_F,
		 FILE* OUTPUT_FILE,
		 void* USER_DATA
		 );

/**
 * @brief Write the content of a hashtable to a file into XML.
 *
 * Write the elements of the hashtable H to OUTPUT_FILE, into XML language.
 * If WRITE_F != NULL, then uses WRITE_F to write H's elements to OUTPUT_FILE.
 * Additionnal USER_DATA argument could be passed to WRITE_F.
 *
 * @note Complexity: O( |H| )
 * @pre H must be a valid gdsl_hash_t & OUTPUT_FILE != NULL
 * @param H The hashtable to write.
 * @param WRITE_F The write function.
 * @param OUTPUT_FILE The file where to write H's elements.
 * @param USER_DATA User's datas passed to WRITE_F.
 * @see gdsl_hash_write()
 * @see gdsl_hash_dump()
 */
extern void
gdsl_hash_write_xml (const gdsl_hash_t H,
		     gdsl_write_func_t WRITE_F,
		     FILE* OUTPUT_FILE,
		     void* USER_DATA
		     );

/**
 * @brief Dump the internal structure of a hashtable to a file.
 *
 * Dump the structure of the hashtable H to OUTPUT_FILE. If WRITE_F != NULL,
 * then uses WRITE_F to write H's elements to OUTPUT_FILE.
 * Additionnal USER_DATA argument could be passed to WRITE_F.
 *
 * @note Complexity: O( |H| )
 * @pre H must be a valid gdsl_hash_t & OUTPUT_FILE != NULL
 * @param H The hashtable to write
 * @param WRITE_F The write function
 * @param OUTPUT_FILE The file where to write H's elements
 * @param USER_DATA User's datas passed to WRITE_F
 * @see gdsl_hash_write()
 * @see gdsl_hash_write_xml()
 */
extern void
gdsl_hash_dump (const gdsl_hash_t H,
		gdsl_write_func_t WRITE_F,
		FILE* OUTPUT_FILE,
		void* USER_DATA
		);

/*
 * @}
 */


#ifdef __cplusplus
}
#endif /* __cplusplus */


#endif /* _GDSL_HASH_H_ */


/** EMACS **
 * Local variables:
 * mode: c
 * c-basic-offset: 4
 * End:
 */