gdsl_list.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_list.h,v $
 * $Revision: 1.25 $
 * $Date: 2006/03/04 16:32:05 $
 */


#ifndef _GDSL_LIST_H_
#define _GDSL_LIST_H_

#include <stdio.h>

#include "gdsl_types.h"

#ifdef __cplusplus
extern "C" 
{
#endif


/**
 * @defgroup gdsl_list Doubly-linked list manipulation module
 * @{
 */


/**
 * @brief GDSL doubly-linked list type.
 *
 * This type is voluntary opaque. Variables of this kind could'nt be directly
 * used, but by the functions of this module.
 */
typedef struct _gdsl_list* gdsl_list_t;

/**
 * @brief GDSL doubly-linked list cursor type.
 *
 * This type is voluntary opaque. Variables of this kind could'nt be directly
 * used, but by the functions of this module.
 */
typedef struct _gdsl_list_cursor* gdsl_list_cursor_t;

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

/**
 * @brief Create a new list.
 *
 * Allocate a new list data structure which name is set to a copy of NAME.
 * The function pointers ALLOC_F and FREE_F could be used to respectively, alloc
 * and free elements in the list. 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
 *
 * @note Complexity: O( 1 )
 * @pre nothing
 * @param NAME The name of the new list to create
 * @param ALLOC_F Function to alloc element when inserting it in the list
 * @param FREE_F Function to free element when removing it from the list
 * @return the newly allocated list in case of success.
 * @return NULL in case of insufficient memory.
 * @see gdsl_list_free()
 * @see gdsl_list_flush()
 */
extern gdsl_list_t
gdsl_list_alloc (const char* NAME,
		 gdsl_alloc_func_t ALLOC_F,
		 gdsl_free_func_t FREE_F
		 );

/**
 * @brief Destroy a list.
 *
 * Flush and destroy the list L. All the elements of L are freed using L's 
 * FREE_F function passed to gdsl_list_alloc(). 
 *
 * @note Complexity: O( |L| )
 * @pre L must be a valid gdsl_list_t
 * @param L The list to destroy
 * @see gdsl_list_alloc()
 * @see gdsl_list_flush()
 */
extern void 
gdsl_list_free (gdsl_list_t L
		);

/**
 * @brief Flush a list.
 *
 * Destroy all the elements of the list L by calling L's FREE_F function passed
 * to gdsl_list_alloc(). L is not deallocated itself and L's name is not 
 * modified.
 *
 * @note Complexity: O( |L| )
 * @pre L must be a valid gdsl_list_t
 * @param L The list to flush
 * @see gdsl_list_alloc()
 * @see gdsl_list_free()
 */
extern void
gdsl_list_flush (gdsl_list_t L
		 );

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

/** 
 * @brief Get the name of a list.
 * @note Complexity: O( 1 )
 * @pre L must be a valid gdsl_list_t
 * @post The returned string MUST NOT be freed.
 * @param L The list to get the name from
 * @return the name of the list L.
 * @see gdsl_list_set_name()
 */
extern const char*
gdsl_list_get_name (const gdsl_list_t L
		    );

/** 
 * @brief Get the size of a list.
 * @note Complexity: O( 1 )
 * @pre L must be a valid gdsl_list_t
 * @param L The list to get the size from
 * @return the number of elements of the list L (noted |L|).
 */
extern ulong
gdsl_list_get_size (const gdsl_list_t L
		    );

/** 
 * @brief Check if a list is empty.
 * @note Complexity: O( 1 )
 * @pre L must be a valid gdsl_list_t
 * @param L The list to check
 * @return TRUE if the list L is empty.
 * @return FALSE if the list L is not empty.
 */
extern bool
gdsl_list_is_empty (const gdsl_list_t L
		    );

/**
 * @brief Get the head of a list.
 * @note Complexity: O( 1 )
 * @pre L must be a valid gdsl_list_t
 * @param L The list to get the head from
 * @return the element at L's head position if L is not empty. The returned 
 * element is not removed from L.
 * @return NULL if the list L is empty.
 * @see gdsl_list_get_tail()
 */
extern gdsl_element_t
gdsl_list_get_head (const gdsl_list_t L
		    );

/** 
 * @brief Get the tail of a list.
 * @note Complexity: O( 1 )
 * @pre L must be a valid gdsl_list_t
 * @param L The list to get the tail from
 * @return the element at L's tail position if L is not empty. The returned 
 * element is not removed from L.
 * @return NULL if L is empty.
 * @see gdsl_list_get_head()
 */
extern gdsl_element_t
gdsl_list_get_tail (const gdsl_list_t L
		    );

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

/** 
 * @brief Set the name of a list.
 *
 * Changes the previous name of the list L to a copy of NEW_NAME.
 *
 * @note Complexity: O( 1 )
 * @pre L must be a valid gdsl_list_t
 * @param L The list to change the name
 * @param NEW_NAME The new name of L
 * @return the modified list in case of success.
 * @return NULL in case of failure.
 * @see gdsl_list_get_name()
 */
extern gdsl_list_t
gdsl_list_set_name (gdsl_list_t L,
		    const char* NEW_NAME
		    );

/**
 * @brief Insert an element at the head of a list.
 *
 * Allocate a new element E by calling L's ALLOC_F function on VALUE. ALLOC_F
 * is the function pointer passed to gdsl_list_alloc(). The new element E is
 * then inserted at the header position of the list L.
 *
 * @note Complexity: O( 1 )
 * @pre L must be a valid gdsl_list_t
 * @param L The list to insert into
 * @param VALUE The value used to make the new element to insert into L
 * @return the inserted element E in case of success.
 * @return NULL in case of failure.
 * @see gdsl_list_insert_tail()
 * @see gdsl_list_remove_head()
 * @see gdsl_list_remove_tail()
 * @see gdsl_list_remove()
 */
extern gdsl_element_t
gdsl_list_insert_head (gdsl_list_t L,
		       void* VALUE
		       );

/** 
 * @brief Insert an element at the tail of a list.
 *
 * Allocate a new element E by calling L's ALLOC_F function on VALUE. ALLOC_F
 * is the function pointer passed to gdsl_list_alloc(). The new element E is
 * then inserted at the footer position of the list L.
 *
 * @note Complexity: O( 1 )
 * @pre L must be a valid gdsl_list_t
 * @param L The list to insert into
 * @param VALUE The value used to make the new element to insert into L
 * @return the inserted element E in case of success.
 * @return NULL in case of failure.
 * @see gdsl_list_insert_head()
 * @see gdsl_list_remove_head()
 * @see gdsl_list_remove_tail()
 * @see gdsl_list_remove()
 */
extern gdsl_element_t
gdsl_list_insert_tail (gdsl_list_t L,
		       void* VALUE
		       );

/**
 * @brief Remove the head of a list.
 *
 * Remove the element at the head of the list L.
 *
 * @note Complexity: O( 1 )
 * @pre L must be a valid gdsl_list_t
 * @param L The list to remove the head from
 * @return the removed element in case of success.
 * @return NULL in case of L is empty.
 * @see gdsl_list_insert_head()
 * @see gdsl_list_insert_tail()
 * @see gdsl_list_remove_tail()
 * @see gdsl_list_remove()
 */
extern gdsl_element_t
gdsl_list_remove_head (gdsl_list_t L
		       );

/**
 * @brief Remove the tail of a list.
 *
 * Remove the element at the tail of the list L.
 *
 * @note Complexity: O( 1 )
 * @pre L must be a valid gdsl_list_t
 * @param L The list to remove the tail from
 * @return the removed element in case of success.
 * @return NULL in case of L is empty.
 * @see gdsl_list_insert_head()
 * @see gdsl_list_insert_tail()
 * @see gdsl_list_remove_head()
 * @see gdsl_list_remove()
 */
extern gdsl_element_t
gdsl_list_remove_tail (gdsl_list_t L
		       );

/**
 * @brief Remove 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 then returned.
 *
 * @note Complexity: O( |L| / 2 )
 * @pre L must be a valid gdsl_list_t & COMP_F != NULL
 * @param L The list to remove the element from
 * @param COMP_F The comparison function used to find the element to remove
 * @param VALUE The value used to compare the element to remove with
 * @return the founded element E if it was found.
 * @return NULL in case the searched element E was not found.
 * @see gdsl_list_insert_head()
 * @see gdsl_list_insert_tail()
 * @see gdsl_list_remove_head()
 * @see gdsl_list_remove_tail()
 */
extern gdsl_element_t
gdsl_list_remove (gdsl_list_t L,
		  gdsl_compare_func_t COMP_F,
		  const void* VALUE
		  );

/** 
 * @brief Delete the head of a list.
 *
 * Remove the header 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 head from