gdsl.zip_gdsl

/* * This file is part of the Generic Data Structures Library (GDSL). * Copyright (C) 1998-2006 Nicolas Darnis <ndarnis@free.fr>. * * 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); /* 注意 : 将 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 ();