dlist.c

常用数据结构算法代码库

/****************************************************************************
*
*					Copyright (C) 1991 Kendall Bennett.
*							All rights reserved.
*
* Filename:		$RCSfile: dlist.c $
* Version:		$Revision: 1.5 $
*
* Language:		ANSI C
* Environment:	any
*
* Description:	Module to implement doubly linked lists. Includes a routine
*				to peform a mergesort on the doubly linked list.
*
* $Id: dlist.c 1.5 91/12/31 19:39:49 kjb Exp $
*
* Revision History:
* -----------------
*
* $Log:	dlist.c $
* Revision 1.5  91/12/31  19:39:49  kjb
* Modified include file directories.
* 
* Revision 1.4  91/10/28  03:16:39  kjb
* Ported to the Iris.
* 
* Revision 1.3  91/09/27  03:09:18  kjb
* Cosmetic change.
* 
* Revision 1.2  91/09/03  18:27:42  ROOT_DOS
* Ported to UNIX.
* 
* Revision 1.1  91/09/01  18:35:23  ROOT_DOS
* Initial revision
* 
****************************************************************************/

#include <stdio.h>
#include <malloc.h>
#include <signal.h>
#include "debug.h"
#include "dlist.h"

PUBLIC void *dlst_newnode(int size)
/****************************************************************************
*
* Function:		dlst_newnode
* Parameters:	size	- Amount of memory to allocate for node
* Returns:      Pointer to the allocated node's user space.
*
* Description:	Allocates the memory required for a node, adding a small
*				header at the start of the node. We return a reference to
*				the user space of the node, as if it had been allocated via
*				malloc().
*
****************************************************************************/
{
	DLST_BUCKET	*node;

	if ( !(node = (DLST_BUCKET*)malloc(size + sizeof(DLST_BUCKET))) ) {
		fprintf(stderr,"Not enough memory to allocate list node.\n");
		raise(SIGABRT);
		return NULL;
		}

	return DLST_USERSPACE(node);		/* Return pointer to user space */
}

PUBLIC void dlst_freenode(void *node)
/****************************************************************************
*
* Function:		dlst_freenode
* Parameters:	node	- Node to free.
*
* Description:  Frees a node previously allocated with lst_newnode().
*
****************************************************************************/
{
	free(DLST_HEADER(node));
}

PUBLIC DLIST *dlst_init(void)
/****************************************************************************
*
* Function:		dlst_init
* Returns:      Pointer to a newly created list.
*
* Description:	Initialises a list and returns a pointer to it.
*
****************************************************************************/
{
	DLIST	*l;

	if ((l = (DLIST*)malloc(sizeof(DLIST))) != NULL) {
		l->count = 0;
		l->head = &(l->hz[0]);
		l->z = &(l->hz[1]);
		l->head->next = l->z->next = l->z;
		l->z->prev = l->head->prev = l->head;
		}
	else {
		fprintf(stderr,"Insufficient memory to allocate list\n");
		raise(SIGABRT);
		return NULL;
		}

	return l;
}

PUBLIC void dlst_kill(DLIST *l, void (*freeNode)(void *node))
/****************************************************************************
*
* Function:		dlst_kill
* Parameters:	l			- List to kill
*				freeNode	- Pointer to user routine to free a node
*
* Description:	Kills the list l, by deleting all of the elements contained
*				within the list one by one and then deleting the list
*				itself. Note that we call the user supplied routine
*				(*freeNode)() to free each list node. This allows the user
*				program to perform any extra processing needed to kill each
*				node (if each node contains pointers to other items on the
*				heap for example). If no extra processing is required, just
*				pass the address of dlst_freenode(), ie:
*
*					dlst_kill(myList,dlst_freenode);
*
****************************************************************************/
{
	DLST_BUCKET	*n, *p;

	n = l->head->next;
	while (n != l->z) {			/* Free all nodes in list				*/
		p = n;
		n = n->next;
		(*freeNode)(DLST_USERSPACE(p));
		}
	free(l);					/* Free the list itself					*/
}

PUBLIC void dlst_insertafter(DLIST *l,void *node,void *after)
/****************************************************************************
*
* Function:		lst_insertafter
* Parameters:	l		- List to insert node into
*				node	- Pointer to user space of node to insert
*				after	- Pointer to user space of node to insert node after
*
* Description:	Inserts a new node into the list after the node 'after'. To
*				insert a new node at the beginning of the list, user the
*				macro DLST_HEAD in place of 'after'. ie:
*
*					dlst_insertafter(mylist,node,DLST_HEAD(mylist));
*
****************************************************************************/
{
	DLST_BUCKET	*n = DLST_HEADER(node),*a = DLST_HEADER(after);

	n->next = a->next;
	a->next = n;
	n->prev = a;
	n->next->prev = n;
	l->count++;
}

PUBLIC void *dlst_deletenext(DLIST *l,void *node)
/****************************************************************************
*
* Function:		lst_deletenext
* Parameters:	l		- List to delete node from.
*				node	- Node to delete the next node from
* Returns:		Pointer to the deleted node's userspace.
*
* Description:	Removes the node AFTER 'node' from the list l.
*
****************************************************************************/
{
	DLST_BUCKET	*n = DLST_HEADER(node);

	node = DLST_USERSPACE(n->next);
	n->next->next->prev = n;
	n->next = n->next->next;
	l->count--;
	return node;
}

PUBLIC void *dlst_first(DLIST *l)
/****************************************************************************
*
* Function:		dlst_first
* Parameters:	l		- List to obtain first node from
* Returns:		Pointer to first node in list, NULL if list is empty.
*
* Description:	Returns a pointer to the user space of the first node in
*				the list. If the list is empty, we return NULL.
*
****************************************************************************/
{
	DLST_BUCKET	*n;

	n = l->head->next;
	return (n == l->z ? NULL : DLST_USERSPACE(n));
}

PUBLIC void *dlst_last(DLIST *l)
/****************************************************************************
*
* Function:		dlst_last
* Parameters:	l	- List to obtain last node from
* Returns:		Pointer to last node in list, NULL if list is empty.
*
* Description:	Returns a pointer to the user space of the last node in
*				the list. If the list is empty, we return NULL.
*
****************************************************************************/
{
	DLST_BUCKET	*n;

	n = l->z->prev;
	return (n == l->head ? NULL : DLST_USERSPACE(n));
}

PUBLIC void *dlst_next(void *prev)
/****************************************************************************
*
* Function:		dlst_next
* Parameters:	prev	- Previous node in list to obtain next node from
* Returns:		Pointer to the next node in the list, NULL at end of list.
*
* Description:	Returns a pointer to the user space of the next node in the
*				list given a pointer to the user space of the previous node.
*				If we have reached the end of the list, we return NULL. The
*				end of the list is detected when the next pointer of a node
*				points back to itself, as does the dummy last node's next
*				pointer. This enables us to detect the end of the list
*				without needed access to the list data structure itself.
*
*				NOTE:	We do no checking to ensure that 'prev' is NOT a
*						NULL pointer.
*
****************************************************************************/
{
	DLST_BUCKET	*n = DLST_HEADER(prev);

	n = n->next;
	return (n == n->next ? NULL : DLST_USERSPACE(n));
}

PUBLIC void *dlst_prev(void *next)
/****************************************************************************
*
* Function:		dlst_prev
* Parameters:	next	- Next node in list to obtain previous node from
* Returns:		Pointer to the previous node in the list, NULL at start list.
*
* Description:	Returns a pointer to the user space of the prev node in the
*				list given a pointer to the user space of the next node.
*				If we have reached the start of the list, we return NULL. The
*				start of the list is detected when the prev pointer of a node
*				points back to itself, as does the dummy head node's prev
*				pointer. This enables us to detect the start of the list
*				without needed access to the list data structure itself.
*
*				NOTE:	We do no checking to ensure that 'next' is NOT a
*						NULL pointer.
*
****************************************************************************/
{
	DLST_BUCKET	*n = DLST_HEADER(next);

	n = n->prev;
	return (n == n->prev ? NULL : DLST_USERSPACE(n));
}

/* Static globals required by merge()	*/

static DLST_BUCKET	*z;
static int 			(*cmp)(void*,void*);

PRIVATE DLST_BUCKET *merge(DLST_BUCKET *a,DLST_BUCKET *b,DLST_BUCKET **end)
/****************************************************************************
*
* Function:		merge
* Parameters:	a,b		- Sublist's to merge
* Returns:		Pointer to the merged sublists.
*
* Description:	Merges two sorted lists of nodes together into a single
*				sorted list.
*
****************************************************************************/
{
	DLST_BUCKET	*c;

	/* Go through the lists, merging them together in sorted order	*/

	c = z;
	while (a != z && b != z) {
		if ((*cmp)(DLST_USERSPACE(a),DLST_USERSPACE(b)) <= 0) {
			c->next = a; c = a; a = a->next;
			}
		else {
			c->next = b; c = b; b = b->next;
			}
		};

	/* If one of the lists is not exhausted, then re-attach it to the end
	 * of the newly merged list
	 */

	if (a != z) c->next = a;
	if (b != z) c->next = b;

	/* Set *end to point to the end of the newly merged list	*/

	while (c->next != z) c = c->next;
	*end = c;

	/* Determine the start of the merged lists, and reset z to point to
	 * itself
	 */

	c = z->next; z->next = z;
	return c;
}

PUBLIC void dlst_mergesort(DLIST *l,int (*cmp_func)(void*,void*))
/****************************************************************************
*
* Function:		dlst_mergesort
* Parameters:	l			- List to merge sort
*				cmp_func	- Function to compare two user spaces
*
* Description:	Mergesort's all the nodes in the list. 'cmp' must point to
*				a comparison function that can compare the user spaces of
*				two different nodes. 'cmp' should work the same as
*				strcmp(), in terms of the values it returns. Rather than
*				waste processing time keeping the previous pointers up to
*				date while performing the mergesort, we simply run through
*				the list at the end of the sort to fix the previous pointers.
*
****************************************************************************/
{
	int			i,N;
	DLST_BUCKET	*a,*b;		/* Pointers to sublists to merge			*/
	DLST_BUCKET	*c;			/* Pointer to end of sorted sublists		*/
	DLST_BUCKET	*head;		/* Pointer to dummy head node for list		*/
	DLST_BUCKET	*todo;		/* Pointer to sublists yet to be sorted		*/
	DLST_BUCKET	*t;			/* Temporary								*/

	/* Set up globals required by merge() and pointer to head	*/

	z = l->z; cmp = cmp_func; head = l->head;

	for (N = 1,a = z; a != head->next; N = N + N) {
		todo = head->next; c = head;
		while (todo != z) {

			/* Build first sublist to be merged, and splice from main list
			 */

			a = t = todo;
			for (i = 1; i < N; i++) t = t->next;
			b = t->next; t->next = z; t = b;

			/* Build second sublist to be merged and splice from main list
			 */

			for (i = 1; i < N; i++) t = t->next;
			todo = t->next; t->next = z;

			/* Merge the two sublists created, and set 'c' to point to the
			 * end of the newly merged sublists.
			 */

			c->next = merge(a,b,&t); c = t;
			}
		}

	/* Fix the previous pointers for the list	*/

	a = b = l->head;
	b = b->next;
	while (1) {
		b->prev = a;
		if (b == z)
			break;
		a = a->next;
		b = b->next;
		}
}