list.c

Hausdorff Distance for Image Recognition

/*
 *
 *	$Header: /usr/u/wjr/src/ADT/RCS/list.c,v 1.19 1993/09/02 21:48:33 wjr Exp $
 *
 * Copyright (c) 1990, 1991, 1992, 1993 Cornell University.  All Rights
 * Reserved.
 *
 * Copyright (c) 1991, 1992 Xerox Corporation.  All Rights Reserved.
 *
 * Use, reproduction and preparation of derivative works of this software is
 * permitted.  Any copy of this software or of any derivative work must
 * include both the above copyright notices of Cornell University and Xerox
 * Corporation and this paragraph.  This software is made available AS IS, and
 * XEROX CORPORATION DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
 * WITHOUT LIMITATION THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE, AND NOTWITHSTANDING ANY OTHER PROVISION CONTAINED
 * HEREIN, ANY LIABILITY FOR DAMAGES RESULTING FROM THE SOFTWARE OR ITS USE IS
 * EXPRESSLY DISCLAIMED, WHETHER ARISING IN CONTRACT, TORT (INCLUDING
 * NEGLIGENCE) OR STRICT LIABILITY, EVEN IF XEROX CORPORATION IS ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGES.
 */
/*
 * Xerox may use this code without restriction.
 */

static char *rcsid = "@(#)$Header: /usr/u/wjr/src/ADT/RCS/list.c,v 1.19 1993/09/02 21:48:33 wjr Exp $";

/*
 *	list.c - Yet Another List Module
 *
 * How many times have you seen this implemented? I know I've implemented it
 * a few too many times...
 *
 * This module handles generic lists.
 *
 * Exports:
 *	type List
 *	type ListNode
 *
 *	constant List NULLLIST
 *	constant ListNode NULLLISTNODE
 *
 *	List liNew(void) - create a new, empty list
 *
 *	void liFree(List l) - free list l
 *
 *	ListNode liFirst(List l) - return the first entry in list l
 *
 *	ListNode liNext(ListNode ln) - return the next entry after
 *		ln in whatever list ln is in
 *
 *	ListNode liAdd(List l, void *userdata) - append a node containing
 *		userdata to list l
 *
 *	void liRem(ListNode ln) - remove node ln from whatever list it
 *		is in
 *
 *	ListNode liRemAndNext(ListNode ln) - remove node ln from whatever list
 *		it is in, and return the ListNode which followed it.
 *
 *	void *liGet(ListNode ln) - return the userdata of node ln
 *
 *	ListNode liIsIn(List l, void *userdata) - search l for a node
 *		containing that userdata value
 *
 *	unsigned int liLen(List l) - return the length of l
 *
 *	void liApp(List l1, List l2) - append l2 to l1
 *
 *	macro foreach(ln, l) - iterate over each node in a list
 *
 *	macro forafter(ln1, ln2) - iterate over each node in a list after
 *		a given node
 *
 * An object of type List is used as a handle on a list, which consists of
 *	multiple ListNodes. Each ListNode contains a void *
 *	field, which is used for whatever data the user wishes to attach
 *	to that node. It is standard C idiom that (void *) pointers can
 *	be cast to and from any other type of pointer without error or loss.
 *
 * liNew creates an empty list. If this is not possible, it returns NULLLIST.
 *
 * liFree frees the storage associated with a List and the ListNodes it
 *	contains. Note that it does not free the userdata; the user
 *	must do this before freeing the list structure
 *
 * liFirst returns the first entry of the given list. If the list is
 *	empty, it returns NULLLISTNODE.
 *
 * liNext returns the ListNode after the given one. A call to liFirst
 *	followed by multiple calls to liNext will return all entries
 *	in that list, in the order in which they were added. When liNext
 *	is called on the last entry of a list, it returns NULLLISTNODE.
 *
 * liAdd appends a node to the given list. The userdata pointer is
 *	stored in that node. If it is not possible to append to that
 *	list, it returns NULLLISTNODE.
 *
 * liRem removes a node from the list it is in.
 *
 * liRemAndNext removes a node from the list it is in, and returns the
 *	ListNode that followed it. If the ListNode was the last in its list,
 *	liRemAndNext returns NULLLISTNODE.

 * liGet gets the userdata associated with the given node.
 *
 * liIsIn searches the userdata fields of a list and returns where
 *	that field appeared in the list. This is the only routine which
 *	does anything to the userdata fields other than copy them. liIsIn
 *	compares them for equality. If the field does not appear in the list,
 *	it returns NULLLISTNODE.
 *
 * liLen counts the number of nodes which are on the given list.
 *
 * liApp appends the list l2 to the list l1. They must not be the same list.
 *	l2 becomes invalid after the call.
 *
 * foreach is a replacement for the C "for" construct which successively
 *	assigns ln to each node in l.
 *
 * forafter is a replacement for the C "for" construct which successively
 *	assigns ln1 to each node in the list containing ln2, starting with
 *	the successor of ln2 (liNext(ln2)). ln1 and ln2 may be the same
 *	variable.
 *
 * Note that all ListNodes must be part of some list. When a ListNode is
 * removed from a list, or when its list is freed, it becomes invalid.
 * When a List is freed, it becomes invalid.
 * Interleaving liAdd, liRem and liNext will produce undefined results.
 * If a List is modified, you must start at the beginning with liFirst
 * and scan through it; all ListNodes become invalid when the list is
 * modified.
 * However, since scanning through a list removing some of the entries is
 * a common operation, liRemAndNext has been provided. Scanning through
 * a list using liNext in the case than a node is not to be deleted, and
 * liRemAndNext in the case that it is is guaranteed to work.
 *
 */

#include "misc.h"
#include "list.h"
#include "chunk.h"

/*
 * This module uses the Chunk service to allocate and free ListNodes
 * efficiently.
 */
static ListNode malloc_ln(void);
static void free_ln(ListNode ln);

static Chunk lnChunk = NULLCHUNK;

List
liNew(void)
{
    List newList;

    if ((newList = (List)malloc(sizeof(* newList))) == NULL) {
	return(NULLLIST);
	}
    newList->first = newList->last = NULLLISTNODE;
    return(newList);
    }

void
liFree(List l)
{
    ListNode ln, nextln;

    assert(l != NULLLIST);

    /* Free all the ListNodes this list owns */
    for (ln = l->first; ln != NULLLISTNODE; ln = nextln) {
	assert(ln->owner == l);

	nextln = ln->next;
	free_ln(ln);
	}

    /* and the List structure itself */
    free((void *)l);
    }

ListNode
liFirst(List l)
{
    assert(l != NULLLIST);

    return(l->first);
    }

ListNode
liNext(ListNode ln)
{
    assert(ln != NULLLISTNODE);

    return(ln->next);
    }

ListNode
liAdd(List l, void *userdata)
{
    ListNode newln;

    assert(l != NULLLIST);

    /* Get a new ListNode */
    if ((newln = malloc_ln()) == NULL) {
	return(NULLLISTNODE);
	}

    /* and fill it out */
    newln->next = NULLLISTNODE;
    newln->prev = l->last;
    newln->owner = l;
    newln->userdata = userdata;

    /* Hook it in */
    if (l->last != NULLLISTNODE) {
	l->last->next = newln;
	l->last = newln;
	}
    else {
	assert(l->first == NULLLISTNODE);
	l->first = l->last = newln;
	}

    return(newln);
    }

void
liRem(ListNode ln)
{
    assert(ln != NULLLISTNODE);
    assert(ln->owner != NULLLIST);

    /* Unhook the ListNode */
    if (ln->owner->first == ln) {
	ln->owner->first = ln->next;
	assert(ln->prev == NULLLISTNODE);
	}
    else {
	ln->prev->next = ln->next;
	}
    if (ln->owner->last == ln) {
	ln->owner->last = ln->prev;
	assert(ln->next == NULLLISTNODE);
	}
    else {
	ln->next->prev = ln->prev;
	}
    /* and get rid of it */
    free_ln(ln);

    return;
    }

ListNode
liRemAndNext(ListNode ln)
{
    ListNode nextln;

    assert(ln != NULLLISTNODE);
    assert(ln->owner != NULLLIST);

    nextln = ln->next;
    liRem(ln);
    return(nextln);
    }

void *
liGet(ListNode ln)
{
    assert(ln != NULLLISTNODE);

    return(ln->userdata);
    }

ListNode
liIsIn(List l, void *userdata)
{
    ListNode ln;

    assert(l != NULLLIST);

    for (ln = l->first; ln != NULLLISTNODE; ln = ln->next) {
	if (ln->userdata == userdata) {
	    return(ln);
	    }
	}
    return(NULLLISTNODE);
    }

unsigned int
liLen(List l)
{
    unsigned int count = 0;
    ListNode ln;

    assert(l != NULLLIST);

    for (ln = l->first; ln != NULLLISTNODE; ln = ln->next) {
	count++;
	}

    return(count);
    }

void
liApp(List l1, List l2)
{
    ListNode ln;

    assert(l1 != NULLLIST);
    assert(l2 != NULLLIST);
    assert(l1 != l2);

    /* Patch up the owners from l2 */
    for (ln = l2->first; ln != NULLLISTNODE; ln = ln->next) {
	assert(ln->owner == l2);
	ln->owner = l1;
	}

    /* and hook l2 onto the end of l1 */
    if (l1->last != NULLLISTNODE) {
	assert(l1->last->next == NULLLISTNODE);

	l1->last->next = l2->first;
	if (l2->first != NULLLISTNODE) {
	    assert(l2->first->prev == NULLLISTNODE);
	    l2->first->prev = l1->last;

	    assert(l2->last != NULLLISTNODE);
	    l1->last = l2->last;
	    }
	}
    else {
	assert(l1->first == NULLLISTNODE);
	l1->last = l2->last;
	l1->first = l2->first;
	}

    /* The List l2 is now no longer valid. */
    free((void *)l2);

    return;
    }

/*
 * This routine gets a chunk of memory suitable for use as a ListNode.
 */
static ListNode
malloc_ln(void)
{
    ListNode ln;

    /* Allocate the Chunk if it hasn't been already */
    if (lnChunk == NULLCHUNK) {
	lnChunk = chNew(sizeof(*ln));
	if (lnChunk == NULLCHUNK) {
	    return(NULLLISTNODE);
	    }
	}

    ln = (ListNode)chAlloc(lnChunk);

    return(ln);
    }

/*
 * This routine gets rid of a ListNode, previously allocated through
 * malloc_ln.
 */
static void
free_ln(ListNode ln)
{
    assert(ln != NULLLISTNODE);
    assert(lnChunk != NULLCHUNK);

    chFree(lnChunk, (void *)ln);

    return;
    }