list.c

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

 * returns LS_OK).  lsNext DOES NOT automatically clean up after all 
 * elements have been generated.  lsFinish must be called explicitly to do this.
 */
{
    register lsGenInternal *realGen = (lsGenInternal *) generator;

    if (realGen->afterSpot == NIL(lsElem)) {
	/* No more stuff to generate */
	*data = (lsGeneric) 0;
	if (itemHandle) *itemHandle = (lsHandle) 0;
	return LS_NOMORE;
    } else {
	*data = realGen->afterSpot->userData;
	if (itemHandle) *itemHandle = (lsHandle) (realGen->afterSpot);
	/* Move the pointers down one */
	realGen->beforeSpot = realGen->afterSpot;
	realGen->afterSpot = realGen->afterSpot->nextPtr;
	return LS_OK;
    }
}


lsStatus lsPrev(generator, data, itemHandle)
lsGen generator;		/* Generator handle        */
lsGeneric *data;		/* User data (return)      */
lsHandle *itemHandle;		/* Handle to item (return) */
/*
 * Generates the item before 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 
 * returns LS_OK).  lsPrev DOES NOT automatically clean up after all 
 * elements have been generated.  lsFinish must be called explicitly to do this.
 */
{
    register lsGenInternal *realGen = (lsGenInternal *) generator;

    if (realGen->beforeSpot == NIL(lsElem)) {
	/* No more stuff to generate */
	*data = (lsGeneric) 0;
	if (itemHandle) *itemHandle = (lsHandle) 0;
	return LS_NOMORE;
    } else {
	*data = realGen->beforeSpot->userData;
	if (itemHandle) *itemHandle = (lsHandle) (realGen->beforeSpot);
	/* Move the pointers down one */
	realGen->afterSpot = realGen->beforeSpot;
	realGen->beforeSpot = realGen->beforeSpot->prevPtr;
	return LS_OK;
    }

}

lsStatus lsInBefore(generator, data, itemHandle)
lsGen generator;		/* Generator handle          */
lsGeneric data;			/* Arbitrary pointer to data */
lsHandle *itemHandle;		/* Handle to item (return) */
/*
 * Inserts an element BEFORE the current spot.  The item generated
 * by lsNext will be unchanged;  the inserted item will be generated
 * by lsPrev.  This modifies the list.  'itemHandle' may be used at 
 * a later time to produce a generation handle without generating 
 * through the list.
 */
{
    lsGenInternal *realGen = (lsGenInternal *) generator;
    lsElem *newElem;

    if (realGen->beforeSpot == NIL(lsElem)) {
	/* Item added to the beginning of the list */
	(void) lsNewBegin((lsList) realGen->mainList, data, itemHandle);
	realGen->beforeSpot = realGen->mainList->topPtr;
	return LS_OK;
    } else if (realGen->afterSpot == NIL(lsElem)) {
	/* Item added to the end of the list */
	(void) lsNewEnd((lsList) realGen->mainList, data, itemHandle);
	realGen->afterSpot = realGen->mainList->botPtr;
	return LS_OK;
    } else {
	/* Item added in the middle of the list */
	newElem = ALLOC(lsElem, 1);
	newElem->mainList = realGen->mainList;
	newElem->prevPtr = realGen->beforeSpot;
	newElem->nextPtr = realGen->afterSpot;
	newElem->userData = data;
	realGen->beforeSpot->nextPtr = newElem;
	realGen->afterSpot->prevPtr = newElem;
	realGen->beforeSpot = newElem;
	realGen->mainList->length += 1;
	if (itemHandle) *itemHandle = (lsHandle) newElem;
	return LS_OK;
    }
}

lsStatus lsInAfter(generator, data, itemHandle)
lsGen generator;		/* Generator handle          */
lsGeneric data;			/* Arbitrary pointer to data */
lsHandle *itemHandle;		/* Handle to item (return)   */
/*
 * Inserts an element AFTER the current spot.  The next item generated
 * by lsNext will be the new element.  The next  item generated by
 * lsPrev is unchanged.  This modifies the list.  'itemHandle' may
 * be used at a later time to generate a generation handle without
 * searching through the list to find the item.
 */
{
    lsGenInternal *realGen = (lsGenInternal *) generator;
    lsElem *newElem;

    if (realGen->beforeSpot == NIL(lsElem)) {
	/* Item added to the beginning of the list */
	(void) lsNewBegin((lsList) realGen->mainList, data, itemHandle);
	realGen->beforeSpot = realGen->mainList->topPtr;
	return LS_OK;
    } else if (realGen->afterSpot == NIL(lsElem)) {
	/* Item added to the end of the list */
	(void) lsNewEnd((lsList) realGen->mainList, data, itemHandle);
	realGen->afterSpot = realGen->mainList->botPtr;
	return LS_OK;
    } else {
	/* Item added in the middle of the list */
	newElem = ALLOC(lsElem, 1);
	newElem->mainList = realGen->mainList;
	newElem->prevPtr = realGen->beforeSpot;
	newElem->nextPtr = realGen->afterSpot;
	newElem->userData = data;
	realGen->beforeSpot->nextPtr = newElem;
	realGen->afterSpot->prevPtr = newElem;
	realGen->afterSpot = newElem;
	realGen->mainList->length += 1;
	if (itemHandle) *itemHandle = (lsHandle) newElem;
	return LS_OK;
    }
}
	

lsStatus lsDelBefore(generator, data)
lsGen generator;		/* Generator handle        */
lsGeneric *data;			/* Deleted item (returned) */
/*
 * Removes the item before the current spot.  The next call to lsPrev
 * will return the item before the deleted item.  The next call to lsNext
 * will be uneffected.  This modifies the list.  The routine returns 
 * LS_BADSTATE if the user tries to call the routine and there is
 * no item before the current spot.  This routine returns the userData
 * of the deleted item so it may be freed (if necessary).
 */
{
    lsGenInternal *realGen = (lsGenInternal *) generator;
    lsElem *doomedItem;

    if (realGen->beforeSpot == NIL(lsElem)) {
	/* No item to delete */
	*data = (lsGeneric) 0;
	return LS_BADSTATE;
    } else if (realGen->beforeSpot == realGen->mainList->topPtr) {
	/* Delete the first item of the list */
	realGen->beforeSpot = realGen->beforeSpot->prevPtr;
	return lsDelBegin((lsList) realGen->mainList, data);
    } else if (realGen->beforeSpot == realGen->mainList->botPtr) {
	/* Delete the last item of the list */
	realGen->beforeSpot = realGen->beforeSpot->prevPtr;
	return lsDelEnd((lsList) realGen->mainList, data);
    } else {
	/* Normal mid list deletion */
	doomedItem = realGen->beforeSpot;
	doomedItem->prevPtr->nextPtr = doomedItem->nextPtr;
	doomedItem->nextPtr->prevPtr = doomedItem->prevPtr;
	realGen->beforeSpot = doomedItem->prevPtr;
	realGen->mainList->length -= 1;
	*data = doomedItem->userData;
	FREE(doomedItem);
	return LS_OK;
    }
}


lsStatus lsDelAfter(generator, data)
lsGen generator;		/* Generator handle        */
lsGeneric *data;			/* Deleted item (returned) */
/*
 * Removes the item after the current spot.  The next call to lsNext
 * will return the item after the deleted item.  The next call to lsPrev
 * will be uneffected.  This modifies the list.  The routine returns 
 * LS_BADSTATE if the user tries to call the routine and there is
 * no item after the current spot.  This routine returns the userData
 * of the deleted item so it may be freed (if necessary).
 */
{
    lsGenInternal *realGen = (lsGenInternal *) generator;
    lsElem *doomedItem;

    if (realGen->afterSpot == NIL(lsElem)) {
	/* No item to delete */
	*data = (lsGeneric) 0;
	return LS_BADSTATE;
    } else if (realGen->afterSpot == realGen->mainList->topPtr) {
	/* Delete the first item of the list */
	realGen->afterSpot = realGen->afterSpot->nextPtr;
	return lsDelBegin((lsList) realGen->mainList, data);
    } else if (realGen->afterSpot == realGen->mainList->botPtr) {
	/* Delete the last item of the list */
	realGen->afterSpot = realGen->afterSpot->nextPtr;
	return lsDelEnd((lsList) realGen->mainList, data);
    } else {
	/* Normal mid list deletion */
	doomedItem = realGen->afterSpot;
	doomedItem->prevPtr->nextPtr = doomedItem->nextPtr;
	doomedItem->nextPtr->prevPtr = doomedItem->prevPtr;
	realGen->afterSpot = doomedItem->nextPtr;
	realGen->mainList->length -= 1;
	*data = doomedItem->userData;
	FREE(doomedItem);
	return LS_OK;
    }
}



lsStatus lsFinish(generator)
lsGen generator;		/* Generator handle */
/*
 * Marks the completion of a generation of list items.  This routine should
 * be called after calls to lsNext to free resources used by the
 * generator.  This rule applies even if all items of a list are
 * generated by lsNext.
 */
{
    lsGenInternal *realGen = (lsGenInternal *) generator;

    FREE(realGen);
    return(LS_OK);
}



/*
 * Functional list generation
 *
 * An alternate form of generating through items of a list is provided.
 * The routines below generatae through all items of a list in a given
 * direction and call a user provided function for each one.
 */

static lsStatus lsGenForm();

lsStatus lsForeach(list, userFunc, arg)
lsList list;			/* List to generate through */
lsStatus (*userFunc)();		/* User provided function   */
lsGeneric arg;			/* User provided data       */
/*
 * This routine generates all items in `list' from the first item
 * to the last calling `userFunc' for each item.  The function
 * should have the following form:
 *   lsStatus userFunc(data, arg)
 *   lsGeneric data;
 *   lsGeneric arg;
 * `data' will be the user data associated with the item generated.
 * `arg' will be the same pointer provided to lsForeach.  The
 * routine should return LS_OK to continue the generation,  LS_STOP
 * to stop generating items,  and LS_DELETE to delete the item
 * from the list.  If the generation was stopped prematurely,
 * the routine will return LS_STOP.  If the user provided function
 * does not return an appropriate value,  the routine will return
 * LS_BADPARAM.
 */
{
    return lsGenForm(userFunc, arg, lsStart(list), lsNext, lsDelBefore);
}


lsStatus lsBackeach(list, userFunc, arg)
lsList list;			/* List to generate through */
lsStatus (*userFunc)();		/* User provided function   */
lsGeneric arg;			/* User provided data       */
/*
 * This routine is just like lsForeach except it generates
 * all items in `list' from the last item to the first.
 */
{
    return lsGenForm(userFunc, arg, lsEnd(list), lsPrev, lsDelAfter);
}



static lsStatus lsGenForm(userFunc, arg, gen, gen_func, del_func)
lsStatus (*userFunc)();		/* User provided function         */
lsGeneric arg;			/* Data to pass to function       */
lsGen gen;			/* Generator to use               */
lsStatus (*gen_func)();		/* Generator function to use      */
lsStatus (*del_func)();		/* Deletion function to use       */
/*
 * This is the function used to implement the two functional
 * generation interfaces to lists.
 */
{
    lsGeneric data;

    while ((*gen_func)(gen, &data, LS_NH) == LS_OK) {
	switch ((*userFunc)(data, arg)) {
	case LS_OK:
	    /* Nothing */
	    break;
	case LS_STOP:
	    (void) lsFinish(gen);
	    return LS_STOP;
	case LS_DELETE:
	    (*del_func)(gen, &data);
	    break;
	default:
	    return LS_BADPARAM;
	}
    }
    (void) lsFinish(gen);
    return LS_OK;
}


lsList lsQueryHandle(itemHandle)
lsHandle itemHandle;		/* Handle of an item  */
/*
 * This routine returns the associated list of the specified
 * handle.  Returns 0 if there were problems.
 */
{
    lsElem *realHandle = (lsElem *) itemHandle;

    if (realHandle) {
	return (lsList) realHandle->mainList;
    } else {
	return (lsList) 0;
    }
}

lsGeneric lsFetchHandle(itemHandle)
lsHandle itemHandle;
/*
 * This routine returns the user data of the item associated with
 * `itemHandle'.
 */
{
    return ((lsElem *) itemHandle)->userData;
}

lsStatus lsRemoveItem(itemHandle, userData)
lsHandle itemHandle;		/* Handle of an item */
lsGeneric *userData;		/* Returned data     */
/*
 * This routine removes the item associated with `handle' from
 * its list and returns the user data associated with the item
 * for reclaimation purposes.  Note this modifies the list
 * that originally contained `item'.
 */
{
    lsElem *realItem = (lsElem *) itemHandle;
    lsGenInternal gen;

    gen.mainList = realItem->mainList;
    gen.beforeSpot = realItem->prevPtr;
    gen.afterSpot = realItem;
    return lsDelAfter((lsGen) &gen, userData);
}


/* List sorting support */
#define TYPE		lsElem
#define SORT		lsSortItems
#define NEXT		nextPtr
#define FIELD		userData
#include "lsort.h"		/* Merge sort by R. Rudell */

lsStatus lsSort(list, compare)
lsList list;			/* List to sort        */
int (*compare)();		/* Comparison function */
/*
 * This routine sorts `list' using `compare' as the comparison
 * function between items in the list.  `compare' has the following form:
 *   int compare(item1, item2)
 *   lsGeneric item1, item2;
 * The routine should return -1 if item1 is less than item2, 0 if
 * they are equal,  and 1 if item1 is greater than item2.
 * The routine uses a generic merge sort written by Rick Rudell.
 */
{
    lsDesc *realList = (lsDesc *) list;
    lsElem *idx, *lastElem;

    realList->topPtr = lsSortItems(realList->topPtr, compare,
				  realList->length);

    /* Forward pointers are correct - fix backward pointers */
    lastElem = (lsElem *) 0;
    for (idx = realList->topPtr;  idx != (lsElem *) 0;  idx = idx->nextPtr) {
	idx->prevPtr = lastElem;
	lastElem = idx;
    }
    /* lastElem is last item in list */
    realList->botPtr = lastElem;
    return LS_OK;
}



lsStatus lsUniq(list, compare, delFunc)
lsList list;			/* List to remove duplicates from */
int (*compare)();		/* Item comparison function       */
void (*delFunc)();		/* Function to release user data  */
/*
 * This routine takes a sorted list and removes all duplicates
 * from it.  `compare' has the following form:
 *   int compare(item1, item2)
 *   lsGeneric item1, item2;
 * The routine should return -1 if item1 is less than item2, 0 if
 * they are equal,  and 1 if item1 is greater than item2. `delFunc'
 * will be called with a pointer to a user data item for each
 * duplicate destroyed.  `delFunc' can be zero if no clean up
 * is required.
 */
{
    lsGeneric this_item, last_item;
    lsGenInternal realGen;
    lsDesc *realList = (lsDesc *) list;

    if (realList->length > 1) {
	last_item = realList->topPtr->userData;

	/* Inline creation of generator */
	realGen.mainList = realList;
	realGen.beforeSpot = realList->topPtr;
	realGen.afterSpot = realList->topPtr->nextPtr;

	while (realGen.afterSpot) {
	    this_item = realGen.afterSpot->userData;
	    if ((*compare)(this_item, last_item) == 0) {
		/* Duplicate -- eliminate */
		(void) lsDelAfter((lsGen) &realGen, &this_item);
		if (delFunc) (*delFunc)(this_item);
	    } else {
		/* Move generator forward */
		realGen.beforeSpot = realGen.afterSpot;
		realGen.afterSpot = realGen.afterSpot->nextPtr;
		last_item = this_item;
	    }
	}
    }
    return LS_OK;
}