/* * List Abstract Data Type * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net> * * Free Software License: * * All rights are reserved by the author, with the following exceptions: * Permission is granted to freely reproduce and distribute this software, * possibly in exchange for a fee, provided that this copyright notice appears * intact. Permission is also granted to adapt this software to produce * derivative works, as long as the modified versions carry this copyright * notice and additional notices stating that the work has been modified. * This source code may be translated into executable form and incorporated * into proprietary software; there is no requirement for such software to * contain a copyright notice related to this source. * * $Id: list.c,v 1.19.2.1 2000/04/17 01:07:21 kaz Exp $ * $Name: kazlib_1_20 $ */#include <stdlib.h>#include <stddef.h>#include <assert.h>#define LIST_IMPLEMENTATION#include "list.h"#define next list_next#define prev list_prev#define data list_data#define pool list_pool#define fre list_free#define size list_size#define nilnode list_nilnode#define nodecount list_nodecount#define maxcount list_maxcount#define list_nil(L)		(&(L)->nilnode)#define list_first_priv(L)	((L)->nilnode.next)#define list_last_priv(L)	((L)->nilnode.prev)#define lnode_next(N)		((N)->next)#define lnode_prev(N)		((N)->prev)#ifdef KAZLIB_RCSIDstatic const char rcsid[] = "$Id: list.c,v 1.19.2.1 2000/04/17 01:07:21 kaz Exp $";#endif/* * Initialize a list object supplied by the client such that it becomes a valid * empty list. If the list is to be ``unbounded'', the maxcount should be * specified as LISTCOUNT_T_MAX, or, alternately, as -1. The value zero * is not permitted. */list_t *list_init(list_t *list, listcount_t maxcount){    assert (maxcount != 0);    list->nilnode.next = &list->nilnode;    list->nilnode.prev = &list->nilnode;    list->nodecount = 0;    list->maxcount = maxcount;    return list;}/* * Dynamically allocate a list object using malloc(), and initialize it so that * it is a valid empty list. If the list is to be ``unbounded'', the maxcount * should be specified as LISTCOUNT_T_MAX, or, alternately, as -1. */list_t *list_create(listcount_t maxcount){    list_t *new = malloc(sizeof *new);    if (new) {	assert (maxcount != 0);	new->nilnode.next = &new->nilnode;	new->nilnode.prev = &new->nilnode;	new->nodecount = 0;	new->maxcount = maxcount;    }    return new;}/* * Destroy a dynamically allocated list object. * The client must remove the nodes first. */void list_destroy(list_t *list){    assert (list_isempty(list));    free(list);}/* * Free all of the nodes of a list. The list must contain only  * dynamically allocated nodes. After this call, the list * is empty. */void list_destroy_nodes(list_t *list){    lnode_t *lnode = list_first_priv(list), *nil = list_nil(list), *tmp;    while (lnode != nil) {	tmp = lnode->next;	lnode->next = NULL;	lnode->prev = NULL;	lnode_destroy(lnode);	lnode = tmp;    }    list_init(list, list->maxcount);}/* * Return all of the nodes of a list to a node pool. The nodes in * the list must all have come from the same pool. */void list_return_nodes(list_t *list, lnodepool_t *pool){    lnode_t *lnode = list_first_priv(list), *tmp, *nil = list_nil(list);    while (lnode != nil) {	tmp = lnode->next;	lnode->next = NULL;	lnode->prev = NULL;	lnode_return(pool, lnode);	lnode = tmp;    }    list_init(list, list->maxcount);}/* * Insert the node ``new'' into the list immediately after ``this'' node. */void list_ins_after(list_t *list, lnode_t *new, lnode_t *this){    lnode_t *that = this->next;    assert (new != NULL);    assert (!list_contains(list, new));    assert (!lnode_is_in_a_list(new));    assert (this == list_nil(list) || list_contains(list, this));    assert (list->nodecount + 1 > list->nodecount);    new->prev = this;    new->next = that;    that->prev = new;    this->next = new;    list->nodecount++;    assert (list->nodecount <= list->maxcount);}/* * Insert the node ``new'' into the list immediately before ``this'' node. */void list_ins_before(list_t *list, lnode_t *new, lnode_t *this){    lnode_t *that = this->prev;    assert (new != NULL);    assert (!list_contains(list, new));    assert (!lnode_is_in_a_list(new));    assert (this == list_nil(list) || list_contains(list, this));    assert (list->nodecount + 1 > list->nodecount);    new->next = this;    new->prev = that;    that->next = new;    this->prev = new;    list->nodecount++;    assert (list->nodecount <= list->maxcount);}/* * Delete the given node from the list. */lnode_t *list_delete(list_t *list, lnode_t *del){    lnode_t *next = del->next;    lnode_t *prev = del->prev;    assert (list_contains(list, del));    prev->next = next;    next->prev = prev;    list->nodecount--;    del->next = del->prev = NULL;    return del;}/* * For each node in the list, execute the given function. The list, * current node and the given context pointer are passed on each * call to the function. */void list_process(list_t *list, void *context,	void (* function)(list_t *list, lnode_t *lnode, void *context)){    lnode_t *node = list_first_priv(list), *next, *nil = list_nil(list);    while (node != nil) {	/* check for callback function deleting	*/	/* the next node from under us		*/	assert (list_contains(list, node));	next = node->next;	function(list, node, context);	node = next;    }}/* * Dynamically allocate a list node and assign it the given piece of data. */lnode_t *lnode_create(void *data){    lnode_t *new = malloc(sizeof *new);    if (new) {	new->data = data;	new->next = NULL;	new->prev = NULL;    }    return new;}/* * Initialize a user-supplied lnode. */lnode_t *lnode_init(lnode_t *lnode, void *data){    lnode->data = data;    lnode->next = NULL;    lnode->prev = NULL;    return lnode;}/* * Destroy a dynamically allocated node. */void lnode_destroy(lnode_t *lnode){    assert (!lnode_is_in_a_list(lnode));    free(lnode);}/* * Initialize a node pool object to use a user-supplied set of nodes. * The ``nodes'' pointer refers to an array of lnode_t objects, containing * ``n'' elements. */lnodepool_t *lnode_pool_init(lnodepool_t *pool, lnode_t *nodes, listcount_t n){    listcount_t i;    assert (n != 0);    pool->pool = nodes;    pool->fre = nodes;    pool->size = n;    for (i = 0; i < n - 1; i++) {	nodes[i].next = nodes + i + 1;    }    nodes[i].next = NULL;    nodes[i].prev = nodes;	/* to make sure node is marked ``on list'' */    return pool;}/* * Create a dynamically allocated pool of n nodes. */lnodepool_t *lnode_pool_create(listcount_t n){    lnodepool_t *pool;    lnode_t *nodes;    assert (n != 0);    pool = malloc(sizeof *pool);    if (!pool)	return NULL;    nodes = malloc(n * sizeof *nodes);    if (!nodes) {	free(pool);	return NULL;    }    lnode_pool_init(pool, nodes, n);    return pool;}/* * Determine whether the given pool is from this pool. */int lnode_pool_isfrom(lnodepool_t *pool, lnode_t *node){    listcount_t i;    /* this is carefully coded this way because ANSI C forbids pointers       to different objects from being subtracted or compared other       than for exact equality */    for (i = 0; i < pool->size; i++) {	if (pool->pool + i == node)	    return 1;    }    return 0;}/* * Destroy a dynamically allocated pool of nodes. */void lnode_pool_destroy(lnodepool_t *p){    free(p->pool);    free(p);}/* * Borrow a node from a node pool. Returns a null pointer if the pool * is exhausted.  */lnode_t *lnode_borrow(lnodepool_t *pool, void *data){    lnode_t *new = pool->fre;    if (new) {	pool->fre = new->next;	new->data = data;	new->next = NULL;	new->prev = NULL;    }    return new;}/* * Return a node to a node pool. A node must be returned to the pool * from which it came. */void lnode_return(lnodepool_t *pool, lnode_t *node){    assert (lnode_pool_isfrom(pool, node));    assert (!lnode_is_in_a_list(node));    node->next = pool->fre;    node->prev = node;    pool->fre = node;}/* * Determine whether the given list contains the given node. * According to this function, a list does not contain its nilnode. */int list_contains(list_t *list, lnode_t *node){    lnode_t *n, *nil = list_nil(list);    for (n = list_first_priv(list); n != nil; n = lnode_next(n)) {	if (node == n)	    return 1;    }    return 0;}/* * A more generalized variant of list_transfer. This one removes a * ``slice'' from the source list and appends it to the destination * list. */void list_extract(list_t *dest, list_t *source, lnode_t *first, lnode_t *last){    listcount_t moved = 1;    assert (first == NULL || list_contains(source, first));    assert (last == NULL || list_contains(source, last));    if (first == NULL || last == NULL)	return;    /* adjust the destination list so that the slice is spliced out */    first->prev->next = last->next;    last->next->prev = first->prev;    /* graft the splice at the end of the dest list */    last->next = &dest->nilnode;    first->prev = dest->nilnode.prev;    dest->nilnode.prev->next = first;    dest->nilnode.prev = last;    while (first != last) {	first = first->next;	assert (first != list_nil(source));	/* oops, last before first! */	moved++;    }        /* assert no overflows */    assert (source->nodecount - moved <= source->nodecount);    assert (dest->nodecount + moved >= dest->nodecount);    /* assert no weirdness */    assert (moved <= source->nodecount);    source->nodecount -= moved;    dest->nodecount += moved;    /* assert list sanity */    assert (list_verify(source));    assert (list_verify(dest));}/* * Split off a trailing sequence of nodes from the source list and relocate * them to the tail of the destination list. The trailing sequence begins * with node ``first'' and terminates with the last node of the source * list. The nodes are added to the end of the new list in their original * order. */void list_transfer(list_t *dest, list_t *source, lnode_t *first){    listcount_t moved = 1;    lnode_t *last;    assert (first == NULL || list_contains(source, first));    if (first == NULL)	return;    last = source->nilnode.prev;    source->nilnode.prev = first->prev;    first->prev->next = &source->nilnode;    last->next = &dest->nilnode;    first->prev = dest->nilnode.prev;    dest->nilnode.prev->next = first;    dest->nilnode.prev = last;    while (first != last) {	first = first->next;