gdsl_list.h

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

 * @return the modified list L in case of success.
 * @return NULL if L is empty.
 * @see gdsl_list_alloc()
 * @see gdsl_list_destroy_tail()
 * @see gdsl_list_destroy()
 */
extern gdsl_list_t
gdsl_list_delete_head (gdsl_list_t L
		       );

/** 
 * @brief Delete the tail of a list.
 *
 * Remove the footer element from the list L and deallocates it using the 
 * FREE_F function passed to gdsl_list_alloc().
 *
 * @note Complexity: O( 1 )
 * @pre L must be a valid gdsl_list_t
 * @param L The list to destroy the tail from
 * @return the modified list L in case of success.
 * @return NULL if L is empty.
 * @see gdsl_list_alloc()
 * @see gdsl_list_destroy_head()
 * @see gdsl_list_destroy()
 */
extern gdsl_list_t
gdsl_list_delete_tail (gdsl_list_t L
		       );

/**
 * @brief Delete a particular element from a list.
 *
 * Search into the list L for the first element E equal to VALUE by using 
 * COMP_F. If E is found, it is removed from L and deallocated using the 
 * FREE_F function passed to gdsl_list_alloc().
 *
 * @note Complexity: O( |L| / 2 )
 * @pre L must be a valid gdsl_list_t & COMP_F != NULL
 * @param L The list to destroy the element from
 * @param COMP_F The comparison function used to find the element to destroy
 * @param VALUE The value used to compare the element to destroy with
 * @return the modified list L if the element is found.
 * @return NULL if the element to destroy is not found.
 * @see gdsl_list_alloc()
 * @see gdsl_list_destroy_head()
 * @see gdsl_list_destroy_tail()
 */
extern gdsl_list_t
gdsl_list_delete (gdsl_list_t L,
		  gdsl_compare_func_t COMP_F,
		  const void* VALUE
		  );

/******************************************************************************/
/* Search functions of doubly-linked lists                                    */
/******************************************************************************/

/**
 * @brief Search for a particular element into a list.
 *
 * Search the first element E equal to VALUE in the list L, by using COMP_F to
 * compare all L's element with.
 *
 * @note Complexity: O( |L| / 2 )
 * @pre L must be a valid gdsl_list_t & COMP_F != NULL
 * @param L The list to search the element in
 * @param COMP_F The comparison function used to compare L's element with VALUE
 * @param VALUE The value to compare L's elemenst with
 * @return the first founded element E in case of success.
 * @return NULL in case the searched element E was not found.
 * @see gdsl_list_search_by_position()
 * @see gdsl_list_search_max()
 * @see gdsl_list_search_min()
 */ 
extern gdsl_element_t
gdsl_list_search (const gdsl_list_t L,
		  gdsl_compare_func_t COMP_F,
		  const void* VALUE
		  );

/**
 * @brief Search for an element by its position in a list.
 * @note Complexity: O( |L| / 2 )
 * @pre L must be a valid gdsl_list_t & POS > 0 & POS <= |L|
 * @param L The list to search the element in
 * @param POS The position where is the element to search
 * @return the element at the POS-th position in the list L.
 * @return NULL if POS > |L| or POS <= 0.
 * @see gdsl_list_search()
 * @see gdsl_list_search_max()
 * @see gdsl_list_search_min()
 */
extern gdsl_element_t
gdsl_list_search_by_position (const gdsl_list_t L,
			      ulong POS
			      );

/**
 * @brief Search for the greatest element of a list.
 *
 * Search the greatest element of the list L, by using COMP_F to compare L's
 * elements with.
 *
 * @note Complexity: O( |L| )
 * @pre L must be a valid gdsl_list_t & COMP_F != NULL
 * @param L The list to search the element in
 * @param COMP_F The comparison function to use to compare L's element with
 * @return the highest element of L, by using COMP_F function.
 * @return NULL if L is empty.
 * @see gdsl_list_search()
 * @see gdsl_list_search_by_position()
 * @see gdsl_list_search_min()
 */
extern gdsl_element_t
gdsl_list_search_max (const gdsl_list_t L,
		      gdsl_compare_func_t COMP_F
		      );

/**
 * @brief Search for the lowest element of a list.
 *
 * Search the lowest element of the list L, by using COMP_F to compare L's
 * elements with.
 *
 * @note Complexity: O( |L| )
 * @pre L must be a valid gdsl_list_t & COMP_F != NULL
 * @param L The list to search the element in
 * @param COMP_F The comparison function to use to compare L's element with
 * @return the lowest element of L, by using COMP_F function.
 * @return NULL if L is empty.
 * @see gdsl_list_search()
 * @see gdsl_list_search_by_position()
 * @see gdsl_list_search_max()
 */
extern gdsl_element_t
gdsl_list_search_min (const gdsl_list_t L,
		      gdsl_compare_func_t COMP_F
		      );

/******************************************************************************/
/* Sort functions of doubly-linked lists                                      */
/******************************************************************************/

/**
 * @brief Sort a list.
 *
 * Sort the list L using COMP_F to order L's elements. 
 *
 * @note Complexity: O( |L| * log( |L| ) )
 * @pre L must be a valid gdsl_list_t & COMP_F != NULL 
 *      & L must not contains elements that are equals
 * @param L The list to sort
 * @param COMP_F The comparison function used to order L's elements
 * @return the sorted list L.
 */
extern gdsl_list_t
gdsl_list_sort (gdsl_list_t L,
		gdsl_compare_func_t COMP_F
		);

/******************************************************************************/
/* Parse functions of doubly-linked lists                                     */
/******************************************************************************/

/**
 * @brief Parse a list from head to tail.
 *
 * Parse all elements of the list L from head to tail. The MAP_F function is
 * called on each L's element with USER_DATA argument. If MAP_F returns 
 * GDSL_MAP_STOP, then gdsl_list_map_forward() stops and returns its last 
 * examinated element.
 *
 * @note Complexity: O( |L| )
 * @pre L must be a valid gdsl_list_t & MAP_F != NULL
 * @param L The list to parse
 * @param MAP_F The map function to apply on each L's element
 * @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.
 * @see gdsl_list_map_backward()
 */
extern gdsl_element_t
gdsl_list_map_forward (const gdsl_list_t L,
		       gdsl_map_func_t MAP_F,
		       void* USER_DATA
		       );

/**
 * @brief Parse a list from tail to head.
 *
 * Parse all elements of the list L from tail to head. The MAP_F function is
 * called on each L's element with USER_DATA argument. If MAP_F returns 
 * GDSL_MAP_STOP then gdsl_list_map_backward() stops and returns its last
 * examinated element.
 *
 * @note Complexity: O( |L| )
 * @pre L must be a valid gdsl_list_t & MAP_F != NULL
 * @param L The list to parse
 * @param MAP_F The map function to apply on each L's element
 * @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.
 * @see gdsl_list_map_forward()
 */
extern gdsl_element_t
gdsl_list_map_backward (const gdsl_list_t L,
			gdsl_map_func_t MAP_F,
			void* USER_DATA
			);

/******************************************************************************/
/* Input/output functions of doubly-linked lists                              */
/******************************************************************************/

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

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

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

/******************************************************************************/
/* Cursor specific functions of doubly-linked lists                           */
/******************************************************************************/

/**
 * @brief Create a new list cursor.
 * @note Complexity: O( 1 )
 * @pre L must be a valid gdsl_list_t
 * @param L The list on wich the cursor is positionned.
 * @return the newly allocated list cursor in case of success.
 * @return NULL in case of insufficient memory.
 * @see gdsl_list_cursor_free()
 */
gdsl_list_cursor_t
gdsl_list_cursor_alloc (const gdsl_list_t L
			);
/**
 * @brief Destroy a list cursor.
 * @note Complexity: O( 1 )
 * @pre C must be a valid gdsl_list_cursor_t.
 * @param C The list cursor to destroy.
 * @see gdsl_list_cursor_alloc()
 */
void
gdsl_list_cursor_free (gdsl_list_cursor_t C
		       );

/**
 * @brief Put a cursor on the head of its list.
 *
 * Put the cursor C on the head of C's list. Does nothing if C's list is empty.
 *
 * @note Complexity: O( 1 )
 * @pre C must be a valid gdsl_list_cursor_t
 * @param C The cursor to use
 * @see gdsl_list_cursor_move_to_tail()
 */
extern void
gdsl_list_cursor_move_to_head (gdsl_list_cursor_t C
			       );

/**
 * @brief Put a cursor on the tail of its list.
 *
 * Put the cursor C on the tail of C's list. Does nothing if C's list is empty.
 *
 * @note Complexity: O( 1 )
 * @pre C must be a valid gdsl_list_cursor_t