gdsl_list.c

一个通用的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.c,v $
 * $Revision: 1.26 $
 * $Date: 2006/03/04 16:32:05 $
 */


#include <config.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>


#include "_gdsl_node.h"
#include "_gdsl_list.h"
#include "gdsl_types.h"
#include "gdsl_list.h"


struct _gdsl_list
{
  _gdsl_node_t      d;          /* begin of the list (sentinel)     */
  _gdsl_node_t      z;          /* end of the list (sentinel)       */
  char*             name;       /* name of the list                 */
  ulong             card;       /* cardinality of the list          */

  gdsl_alloc_func_t alloc_func; /* alloc element function pointer   */
  gdsl_free_func_t  free_func;  /* dealloc element function pointer */
};

struct _gdsl_list_cursor
{
    _gdsl_node_t c;
    gdsl_list_t  l;
};

static gdsl_element_t 
default_alloc (void* e);

static void 
default_free (gdsl_element_t e);

static _gdsl_node_t 
search_by_function (gdsl_list_t l, gdsl_compare_func_t comp_f, const void* v);

static _gdsl_node_t 
search_by_position (gdsl_list_t l, ulong pos);

static gdsl_element_t 
update_cursor (gdsl_list_cursor_t c, _gdsl_node_t n);

static _gdsl_node_t 
sort (_gdsl_node_t u, gdsl_compare_func_t comp_f, _gdsl_node_t z);

static _gdsl_node_t 
merge (_gdsl_node_t s, _gdsl_node_t t, gdsl_compare_func_t comp_f, 
       _gdsl_node_t z);

static gdsl_location_t
get_location (gdsl_list_t list, _gdsl_node_t node);

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

extern gdsl_list_t
gdsl_list_alloc (const char* name, gdsl_alloc_func_t alloc_func, 
		 gdsl_free_func_t free_func)
{
    gdsl_list_t list;
    
    list = (gdsl_list_t) malloc (sizeof (struct _gdsl_list));
    
    if (list == NULL)
	{
	    return NULL;
	}
    
    list->d = _gdsl_node_alloc ();
    
    if (list->d == NULL)
	{
	    free (list);
	    return NULL;
	}
    
    list->z = _gdsl_node_alloc ();
    
    if (list->z == NULL)
	{
	    _gdsl_node_free (list->d);
	    free (list);
	    return NULL;
	}
    
    list->name = NULL;
    
    if (gdsl_list_set_name (list, name) == NULL)
	{
	    _gdsl_node_free (list->z);
	    _gdsl_node_free (list->d);
	    free (list);
	    return NULL;
	}
    
    _gdsl_node_link (list->d, list->z);
    _gdsl_node_set_succ (list->z, list->z);
    _gdsl_node_set_pred (list->d, list->d);
    
    list->card = 0UL;
    list->alloc_func = alloc_func ? alloc_func : default_alloc;
    list->free_func  = free_func  ? free_func  : default_free;
    
    return list;
}

extern void 
gdsl_list_free (gdsl_list_t list)
{
    assert (list != NULL);

    if (!gdsl_list_is_empty (list))
	{
	    gdsl_list_flush (list);
	}

    _gdsl_node_free (list->d);
    _gdsl_node_free (list->z);

    if (list->name != NULL)
	{
	    free (list->name);
	}

    free (list);
}

extern void
gdsl_list_flush (gdsl_list_t list)
{
    _gdsl_node_t save;
    _gdsl_node_t tmp;

    assert (list != NULL);

    tmp = _gdsl_node_get_succ (list->d);

    while (tmp != list->z)
	{
	    save = _gdsl_node_get_succ (tmp);
	    list->free_func (_gdsl_node_get_content (tmp));
	    _gdsl_node_free (tmp);
	    tmp = save;
	}

    _gdsl_node_link (list->d, list->z);
    _gdsl_node_set_succ (list->z, list->z);
    _gdsl_node_set_pred (list->d, list->d);

    list->card = 0UL;
}

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

extern const char*
gdsl_list_get_name (const gdsl_list_t list)
{
    assert (list != NULL);

    return list->name;
}

extern ulong
gdsl_list_get_size (const gdsl_list_t list)
{
    assert (list != NULL);

    return list->card;
}

extern bool
gdsl_list_is_empty (const gdsl_list_t list)
{
    assert (list != NULL);

    return (bool) (_gdsl_node_get_succ (list->d) == list->z);
}

extern gdsl_element_t
gdsl_list_get_head (const gdsl_list_t list)
{
    assert (list != NULL);

    return _gdsl_node_get_content (_gdsl_node_get_succ (list->d));
}

extern gdsl_element_t
gdsl_list_get_tail (const gdsl_list_t list)
{
    assert (list != NULL);

    return _gdsl_node_get_content (_gdsl_node_get_pred (list->z));
}

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

extern gdsl_list_t
gdsl_list_set_name (gdsl_list_t list, const char* name)
{
    assert (list != NULL);

    if (list->name != NULL)
	{
	    free (list->name);
	    list->name = NULL;
	}

    if (name != NULL)
	{
	    list->name = (char*) malloc ((1 + strlen (name)) * sizeof (char));

	    if (list->name == NULL)
		{
		    return NULL;
		}

	    strcpy (list->name, name);
	}

    return list;
}

extern gdsl_element_t 
gdsl_list_insert_head (gdsl_list_t list, void* v)
{
    gdsl_element_t e;
    _gdsl_node_t   head;

    assert (list != NULL);

    head = _gdsl_node_alloc ();

    if (head == NULL)
	{
	    return NULL;
	}

    e = list->alloc_func (v);

    if (e == NULL)
	{
	    _gdsl_node_free (head);
	    return NULL;
	}

    list->card++;

    _gdsl_node_set_content (head, e);  
    _gdsl_node_link (head, _gdsl_node_get_succ (list->d));
    _gdsl_node_link (list->d, head);

    return e;
}

extern gdsl_element_t
gdsl_list_insert_tail (gdsl_list_t list, void* v)
{
    gdsl_element_t e;
    _gdsl_node_t   tail;

    assert (list != NULL);

    tail = _gdsl_node_alloc ();

    if (tail == NULL)
	{
	    return NULL;
	}

    e = list->alloc_func (v);

    if (e == NULL)
	{
	    _gdsl_node_free (tail);
	    return NULL;
	}

    list->card++;

    _gdsl_node_set_content (tail, e);
    _gdsl_node_link (_gdsl_node_get_pred (list->z), tail);
    _gdsl_node_link (tail, list->z);

    return e;
}

extern gdsl_element_t
gdsl_list_remove_head (gdsl_list_t list)
{
    assert (list != NULL);

    if (!gdsl_list_is_empty (list))
	{
	    _gdsl_node_t   head = _gdsl_node_get_succ (list->d);
	    gdsl_element_t e    = _gdsl_node_get_content (head);
      
	    _gdsl_list_remove (head);
	    _gdsl_node_free (head);
      
	    list->card--;
	    return e;
	}
  
    return NULL;
}

extern gdsl_element_t
gdsl_list_remove_tail (gdsl_list_t list)
{
    assert (list != NULL);

    if (!gdsl_list_is_empty (list))
	{
	    _gdsl_node_t tail = _gdsl_node_get_pred (list->z);
	    gdsl_element_t e = _gdsl_node_get_content (tail);

	    _gdsl_list_remove (tail);
	    _gdsl_node_free (tail);

	    list->card--;
	    return e;
	}

    return NULL;
}

extern gdsl_element_t
gdsl_list_remove (gdsl_list_t list, gdsl_compare_func_t comp_f, const void* v)
{
    _gdsl_node_t   n;
    gdsl_element_t e;

    assert (list != NULL);
    assert (comp_f != NULL);

    n = search_by_function (list, comp_f, v);

    if (n == NULL)
	{
	    return NULL;
	}

    e = _gdsl_node_get_content (n);

    _gdsl_list_remove (n);
    _gdsl_node_free (n);

    list->card--;

    return e;
}

extern gdsl_list_t
gdsl_list_delete_head (gdsl_list_t list)
{
    gdsl_element_t e;

    assert (list != NULL);

    e = gdsl_list_remove_head (list);

    if (e == NULL)
	{
	    return NULL;
	}

    list->free_func (e);

    return list;
}

extern gdsl_list_t
gdsl_list_delete_tail (gdsl_list_t list)
{
    gdsl_element_t e;

    assert (list != NULL);

    e = gdsl_list_remove_tail (list);
  
    if (e == NULL)
	{
	    return NULL;
	}

    list->free_func (e);

    return list;
}

extern gdsl_list_t
gdsl_list_delete (gdsl_list_t list, gdsl_compare_func_t comp_f, const void* v)
{
    gdsl_element_t e;

    assert (list != NULL);
    assert (comp_f != NULL);

    e = gdsl_list_remove (list, comp_f, v);

    if (e == NULL)
	{
	    return NULL;
	}

    list->free_func (e);

    return list;
}

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

extern gdsl_element_t
gdsl_list_search (const gdsl_list_t list, gdsl_compare_func_t comp_f, 
		  const void* value)
{
    _gdsl_node_t n;

    assert (list != NULL);
    assert (comp_f != NULL);

    n = search_by_function (list, comp_f, value);

    return (n == NULL) ? NULL : _gdsl_node_get_content (n);
}

extern gdsl_element_t
gdsl_list_search_by_position (const gdsl_list_t list, ulong pos)
{
    _gdsl_node_t n;

    assert (list != NULL);
    assert (pos > 0 && pos <= list->card);

    n = search_by_position (list, pos);

    return n ? _gdsl_node_get_content (n) : NULL;
}

extern gdsl_element_t
gdsl_list_search_max (const gdsl_list_t list, gdsl_compare_func_t comp_f)
{
    _gdsl_node_t   tmp;
    gdsl_element_t max;

    assert (list != NULL);
    assert (comp_f != NULL);

    tmp = _gdsl_node_get_succ (list->d);
    max = _gdsl_node_get_content (tmp);

    while (tmp != list->z)
	{
	    gdsl_element_t e = _gdsl_node_get_content (tmp);

	    if (comp_f (e, max) > 0)
		{
		    max = e;
		}

	    tmp = _gdsl_node_get_succ (tmp);
	}

    return max;
}

extern gdsl_element_t
gdsl_list_search_min (const gdsl_list_t list, gdsl_compare_func_t comp_f)
{
    _gdsl_node_t tmp;
    gdsl_element_t min;

    assert (list != NULL);
    assert (comp_f != NULL);

    tmp = _gdsl_node_get_succ (list->d);
    min = _gdsl_node_get_content (tmp);

    while (tmp != list->z)
	{
	    gdsl_element_t e = _gdsl_node_get_content (tmp);

	    if (comp_f (e, min) < 0)
		{
		    min = e;
		}

	    tmp = _gdsl_node_get_succ (tmp);
	}

    return min;
}

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

extern gdsl_list_t
gdsl_list_sort (gdsl_list_t list, gdsl_compare_func_t comp_f
#ifdef USES_MAX
		, gdsl_element_t max
#endif
		)
{
    assert (list != NULL);
    assert (comp_f != NULL);

    /*
     * Sort the list l with merge-sort algorithm 
     *
     * VERY IMPORTANT: max must be an element NOT ALREADY PRESENT in l
     *                 AND GREATEST than ALL other l's elements!
     *
     * If max is used, the merge algorithm does not need first two tests.
     */
  
#ifdef USES_MAX
    _gdsl_node_set_content (list->z, max); /* [1] */
#endif

    _gdsl_node_link (list->d, 
		     sort (_gdsl_node_get_succ (list->d), comp_f, list->z));

#ifdef USES_MAX
    _gdsl_node_set_content (list->z, NULL);
#endif

    return list;
}

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

extern gdsl_element_t 
gdsl_list_map_forward (const gdsl_list_t list, gdsl_map_func_t map_f, 
		       void* user_data)
{
    _gdsl_node_t tmp;

    assert (list != NULL);
    assert (map_f != NULL);

    tmp = _gdsl_node_get_succ (list->d);

    while (tmp != list->z)
	{
	    gdsl_element_t e = _gdsl_node_get_content (tmp);

	    if (map_f (e, get_location (list, tmp), user_data) == GDSL_MAP_STOP)
		{
		    return e;
		}

	    tmp = _gdsl_node_get_succ (tmp);
	}

    return NULL;
}

extern gdsl_element_t 
gdsl_list_map_backward (const gdsl_list_t list, gdsl_map_func_t map_f, 
			void* user_data)
{
    _gdsl_node_t tmp;

    assert (list != NULL);
    assert (map_f != NULL);

    tmp = _gdsl_node_get_pred (list->z);

    while (tmp != list->d)
	{
	    gdsl_element_t e = _gdsl_node_get_content (tmp);

	    if (map_f (e, get_location (list, tmp), user_data) == GDSL_MAP_STOP)
		{
		    return e;
		}

	    tmp = _gdsl_node_get_pred (tmp);
	}

    return NULL;
}

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

extern void
gdsl_list_write (const gdsl_list_t list, gdsl_write_func_t write_f, 
		 FILE* file, void* user_data)
{
    _gdsl_node_t tmp;

    assert (list != NULL);
    assert (write_f != NULL);
    assert (file != NULL);

    tmp = _gdsl_node_get_succ (list->d);

    while (tmp != list->z)
	{
	    write_f (_gdsl_node_get_content (tmp), file, 
		     get_location (list, tmp), user_data);
	    tmp = _gdsl_node_get_succ (tmp);
	}
}

extern void
gdsl_list_write_xml (const gdsl_list_t list, gdsl_write_func_t write_f, 
		     FILE* file, void* user_data)
{
    _gdsl_node_t tmp;

    assert (list != NULL);
    assert (file != NULL);

    tmp = _gdsl_node_get_succ (list->d);

    fprintf (file, "<GDSL_LIST REF=\"%p\" NAME=\"%s\" CARD=\"%ld\" HEAD=\"%p\" TAIL=\"%p\">\n", 
	     (void*) list, list->name ? list->name : "", list->card, (void*) tmp, 
	     (void*) _gdsl_node_get_pred (list->z));

    while (tmp != list->z)
	{
	    if (tmp == _gdsl_node_get_succ (list->d))
		{
		    fprintf (file, "<GDSL_LIST_NODE REF=\"%p\" CONTENT=\"%p\" SUCC=\"%p\" PRED=\"\">", 
			     (void*) tmp, (void*) _gdsl_node_get_content (tmp), 
			     (void*) _gdsl_node_get_succ (tmp));
		}
	    else if (tmp == _gdsl_node_get_pred (list->z))
		{
		    fprintf (file, "<GDSL_LIST_NODE REF=\"%p\" CONTENT=\"%p\" SUCC=\"\" PRED=\"%p\">", 
			     (void*) tmp, (void*) _gdsl_node_get_content (tmp), 
			     (void*) _gdsl_node_get_pred (tmp));
		}
	    else