list.c

主要进行大规模的电路综合

/*
 * Revision Control Information
 *
 * /projects/hsis/CVS/utilities/list/list.c,v
 * rajeev
 * 1.3
 * 1995/08/08 22:39:51
 *
 */
/*
 * List Management Package
 * 
 * David Harrison
 * University of California, Berkeley, 1985
 *
 * This package implements a simple generic linked list data type.  It
 * uses a doubly linked list structure and provides some standard operations
 * for storing and retrieving data from the list.
 */

#include "util.h"
#include "list.h"		/* Self declaration        */


/*
 * The list identifier is in reality a pointer to the following list
 * descriptor structure.  Lists are doubly linked with both top and
 * bottom pointers stored in the list descriptor.  The length
 * of the list is also stored in the descriptor.
 */

typedef struct list_elem {	/* One list element  */
    struct list_desc *mainList;	/* List descriptor   */
    struct list_elem *prevPtr;	/* Previous element  */
    struct list_elem *nextPtr;	/* Next list element */
    lsGeneric userData;		/* User pointer      */
} lsElem;

typedef struct list_desc {	/* List descriptor record            */
    lsElem *topPtr, *botPtr;	/* Pointer to top and bottom of list */
    int length;			/* Length of list                    */
} lsDesc;


/*
 * Generators are in reality pointers to the generation descriptor 
 * defined below.  A generator has a current spot which is *between*
 * two items.  Thus,  a generator consists of two pointers:  record
 * before spot and record after spot.  A pointer to the main list
 * is included so the top and bottom pointers of the list can be
 * modified if needed.
 */

typedef struct gen_desc {	/* Generator Descriptor 	*/
    lsDesc *mainList;		/* Pointer to list descriptor   */
    lsElem *beforeSpot;		/* Item before the current spot */
    lsElem *afterSpot;		/* Item after the current spot  */
} lsGenInternal;

/*
 * Handles are in reality pointers to lsElem records.  They are
 * cheap to generate and need not be disposed.
 */



/*
 * List Creation and Deletion
 */

lsList lsCreate()
/*
 * Creates a new linked list and returns its handle.  The handle is used
 * by all other list manipulation routines and should not be discarded.
 */
{
    lsDesc *newList;

    newList = ALLOC(lsDesc, 1);
    newList->topPtr = newList->botPtr = NIL(lsElem);
    newList->length = 0;
    return( (lsList) newList );
}

lsStatus lsDestroy(list, delFunc)
lsList list;			/* List to destroy              */
void (*delFunc)();		/* Routine to release user data */
/*
 * Frees all resources associated with the specified list.  It frees memory
 * associated with all elements of the list and then deletes the list.
 * User data is released by calling 'delFunc' with the pointer as the
 * argument.  Accessing a list after its destruction is a no-no.
 */
{
    lsDesc *realList;
    lsElem *index, *temp;

    realList = (lsDesc *) list;
    /* Get rid of elements */
    index = realList->topPtr;
    while (index != NIL(lsElem)) {
	temp = index;  index = index->nextPtr;
	if (delFunc)
	  (*delFunc)(temp->userData);
	FREE(temp);
    }
    /* Get rid of descriptor */
    FREE(realList);
    return(LS_OK);
}


/*
 * Copying lists
 */

static lsGeneric lsIdentity(data)
lsGeneric data;
/* Identity copy function */
{
    return data;
}

lsList lsCopy(list, copyFunc)
lsList list;			/* List to be copied         */
lsGeneric (*copyFunc)();	/* Routine to copy user data */
/*
 * Returns a copy of list `list'.  If `copyFunc' is non-zero,
 * it will be called for each item in `list' and the pointer it 
 * returns will be used in place of the original user data for the 
 * item in the newly created list.  The form of `copyFunc' should be:
 *   lsGeneric copyFunc(data)
 *   lsGeneric data;
 * This is normally used to make copies of the user data in the new list.
 * If no `copyFunc' is provided,  an identity function is used.
 */
{
    lsList newList;
    lsGen gen;
    lsGeneric data;

    if (!copyFunc) copyFunc = lsIdentity;
    newList = lsCreate();
    gen = lsStart(list);
    while (lsNext(gen, &data, LS_NH) == LS_OK) {
	(void) lsNewEnd(newList, (*copyFunc)(data), LS_NH);
    }
    lsFinish(gen);
    return newList;
}


/*
 * Adding New Elements to the Beginning and End of a List
 */

lsStatus lsNewBegin(list, data, itemHandle)
lsList list;			/* List to add element to    */
lsGeneric data;			/* Arbitrary pointer to data */
lsHandle *itemHandle;		/* Handle to data (returned) */
/*
 * Adds a new item to the start of a previously created linked list.
 * If 'itemHandle' is non-zero,  it will be filled with a handle
 * which can be used to generate a generator positioned at the
 * item without generating through the list.
 */
{
    lsDesc *realList = (lsDesc *) list;
    lsElem *newElem;

    newElem = ALLOC(lsElem, 1);
    newElem->userData = data;
    newElem->nextPtr = realList->topPtr;
    newElem->prevPtr = NIL(lsElem);
    newElem->mainList = realList;
    if (realList->topPtr == NIL(lsElem)) {
	/* The new item is both the top and bottom element */
	realList->botPtr = newElem;
    } else {
	/* There was a top element - make its prev correct */
	realList->topPtr->prevPtr = newElem;
    }
    realList->topPtr = newElem;
    realList->length += 1;
    if (itemHandle) *itemHandle = (lsHandle) newElem;
    return(LS_OK);
}

lsStatus lsNewEnd(list, data, itemHandle)
lsList list;			/* List to append element to */
lsGeneric data;			/* Arbitrary pointer to data */
lsHandle *itemHandle;		/* Handle to data (returned) */
/*
 * Adds a new item to the end of a previously created linked list.
 * This routine appends the item in constant time and
 * can be used freely without guilt.
 */
{
    lsDesc *realList = (lsDesc *) list;
    lsElem *newElem;

    newElem = ALLOC(lsElem, 1);
    newElem->userData = data;
    newElem->prevPtr = realList->botPtr;
    newElem->nextPtr = NIL(lsElem);
    newElem->mainList = realList;
    if (realList->topPtr == NIL(lsElem))
      realList->topPtr = newElem;
    if (realList->botPtr != NIL(lsElem))
      realList->botPtr->nextPtr = newElem;
    realList->botPtr = newElem;
    realList->length += 1;
    if (itemHandle) *itemHandle = (lsHandle) newElem;
    return(LS_OK);
}

/*
 * Retrieving the first and last items of a list
 */

lsStatus lsFirstItem(list, data, itemHandle)
lsList list;			/* List to get item from */
lsGeneric *data;			/* User data (returned)  */
lsHandle *itemHandle;	/* Handle to data (returned) */
/*
 * Returns the first item in the list.  If the list is empty,
 * it returns LS_NOMORE.  Otherwise,  it returns LS_OK.
 * If 'itemHandle' is non-zero,  it will be filled with a
 * handle which may be used to generate a generator.
 */
{
    lsDesc *realList = (lsDesc *) list;

    if (realList->topPtr != NIL(lsElem)) {
	*data = realList->topPtr->userData;
	if (itemHandle) *itemHandle = (lsHandle) (realList->topPtr);
	return(LS_OK);
    } else {
	*data = (lsGeneric) 0;
	if (itemHandle) *itemHandle = (lsHandle) 0;
	return(LS_NOMORE);
    }
}

lsStatus lsLastItem(list, data, itemHandle)
lsList list;			/* List to get item from */
lsGeneric *data;			/* User data (returned)  */
lsHandle *itemHandle;	/* Handle to data (returned) */
/*
 * Returns the last item of a list.  If the list is empty,
 * the routine returns LS_NOMORE.  Otherwise,  'data' will
 * be set to the last item and the routine will return LS_OK.
 * If 'itemHandle' is non-zero,  it will be filled with a
 * handle which can be used to generate a generator postioned
 * at this item.
 */
{
    lsDesc *realList = (lsDesc *) list;

    if (realList->botPtr != NIL(lsElem)) {
	*data = realList->botPtr->userData;
	if (itemHandle) *itemHandle = (lsHandle) (realList->botPtr);
	return(LS_OK);
    } else {
	*data = (lsGeneric) 0;
	if (itemHandle) *itemHandle = (lsHandle) 0;
	return(LS_NOMORE);
    }
}



/* Length of a list */

int lsLength(list)
lsList list;			/* List to get the length of */
/*
 * Returns the length of the list.  The list must have been
 * already created using lsCreate.
 */
{
    lsDesc *realList = (lsDesc *) list;

    return(realList->length);
}



/*
 * Deleting first and last items of a list
 */

lsStatus lsDelBegin(list, data)
lsList list;			/* List to delete item from     */
lsGeneric *data;		/* First item (returned)        */
/*
 * This routine deletes the first item of a list.  The user
 * data associated with the item is returned so the caller
 * may dispose of it.  Returns LS_NOMORE if there is no
 * item to delete.
 */
{
    lsDesc *realList = (lsDesc *) list;
    lsElem *temp;

    if (realList->topPtr == NIL(lsElem)) {
	/* Nothing to delete */
	*data = (lsGeneric) 0;
	return LS_NOMORE;
    } else {
	*data = realList->topPtr->userData;
	temp = realList->topPtr;
	realList->topPtr = realList->topPtr->nextPtr;
	if (temp->nextPtr != NIL(lsElem)) {
	    /* There is something after the first item */
	    temp->nextPtr->prevPtr = NIL(lsElem);
	} else {
	    /* Nothing after it - bottom becomes null as well */
	    realList->botPtr = NIL(lsElem);
	}
	FREE(temp);
	realList->length -= 1;
    }
    return LS_OK;
}


lsStatus lsDelEnd(list, data)
lsList list;			/* List to delete item from */
lsGeneric *data;			/* Last item (returned)     */
/*
 * This routine deletes the last item of a list.  The user
 * data associated with the item is returned so the caller
 * may dispose of it.  Returns LS_NOMORE if there is nothing
 * to delete.
 */
{
    lsDesc *realList = (lsDesc *) list;
    lsElem *temp;

    if (realList->botPtr == NIL(lsElem)) {
	/* Nothing to delete */
	*data = (lsGeneric) 0;
	return LS_NOMORE;
    } else {
	*data = realList->botPtr->userData;
	temp = realList->botPtr;
	realList->botPtr = realList->botPtr->prevPtr;
	if (temp->prevPtr != NIL(lsElem)) {
	    /* There is something before the last item */
	    temp->prevPtr->nextPtr = NIL(lsElem);
	} else {
	    /* Nothing before it - top becomes null as well */
	    realList->topPtr = NIL(lsElem);
	}
	FREE(temp);
	realList->length -= 1;
    }
    return LS_OK;
}


/*
 * List Generation Routines
 *
 * nowPtr is the element just before the next one to be generated
 */

lsGen lsStart(list)
lsList list;			/* List to generate items from */
/*
 * This routine defines a generator which is used to step through
 * each item of the list.  It returns a generator handle which should
 * be used when calling lsNext, lsPrev, lsInBefore, lsInAfter, lsDelete,
 * or lsFinish.
 */
{
    lsDesc *realList = (lsDesc *) list;
    lsGenInternal *newGen;

    newGen = ALLOC(lsGenInternal, 1);
    newGen->mainList = realList;
    newGen->beforeSpot = NIL(lsElem);
    newGen->afterSpot = realList->topPtr;
    return ( (lsGen) newGen );
}

lsGen lsEnd(list)
lsList list;			/* List to generate items from */
/*
 * This routine defines a generator which is used to step through
 * each item of a list.  The generator is initialized to the end 
 * of the list.
 */
{
    lsDesc *realList = (lsDesc *) list;
    lsGenInternal *newGen;

    newGen = ALLOC(lsGenInternal, 1);
    newGen->mainList = realList;
    newGen->beforeSpot = realList->botPtr;
    newGen->afterSpot = NIL(lsElem);
    return (lsGen) newGen;
}

lsGen lsGenHandle(itemHandle, data, option)
lsHandle itemHandle;		/* Handle of an item         */
lsGeneric *data;			/* Data associated with item */
int option;			/* LS_BEFORE or LS_AFTER     */
/*
 * This routine produces a generator given a handle.  Handles
 * are produced whenever an item is added to a list.  The generator
 * produced by this routine may be used when calling any of 
 * the standard generation routines.  NOTE:  the generator
 * should be freed using lsFinish.  The 'option' parameter
 * determines whether the generator spot is before or after
 * the handle item.
 */
{
    lsElem *realItem = (lsElem *) itemHandle;
    lsGenInternal *newGen;

    newGen = ALLOC(lsGenInternal, 1);
    newGen->mainList = realItem->mainList;
    *data = realItem->userData;
    if (option & LS_BEFORE) {
	newGen->beforeSpot = realItem->prevPtr;
	newGen->afterSpot = realItem;
    } else if (option & LS_AFTER) {
	newGen->beforeSpot = realItem;
	newGen->afterSpot = realItem->nextPtr;
    } else {
	FREE(newGen);
	newGen = (lsGenInternal *) 0;
    }
    return ( (lsGen) newGen );
}


lsStatus lsNext(generator, data, itemHandle)
lsGen generator;		/* Generator handle        */
lsGeneric *data;			/* User data (return)      */
lsHandle *itemHandle;		/* Handle to item (return) */
/*
 * Generates the item after the item previously generated by lsNext
 * or lsPrev.   It returns a pointer to the user data structure in 'data'.  
 * 'itemHandle' may be used to get a generation handle without
 * generating through the list to find the item.  If there are no more 
 * elements to generate, the routine returns  LS_NOMORE (normally it