list.doc

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

/*
 * Revision Control Information
 *
 * /projects/hsis/CVS/utilities/list/list.doc,v
 * shiple
 * 1.4
 * 1995/08/30 17:37:12
 *
 */

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.

Programs using this package should include the file list.h found
in ~cad/include.  The linkage line for a user program called `myprog'
would look like:

      cc -g -o myprog myprog.o /cad/lib/liblist.a

Status Codes
------------

Most of the routines described below return lsStatus (an integer
return code).  The possible return codes are described below:

LS_OK		Routine completed successfully

LS_BADSTATE	Generator is in a bad state
LS_BADPARAM	Bad parameter value to function
LS_NOMORE	No more items to generate

Note that LS_OK is zero.  Thus,  routine return values should be
explicitly compared against LS_OK for success.

Item Handles
------------

Routines which return items of a list optionally return a `handle'.
This handle can be stored in user data structures and later used to
quickly access the item without generating through the list.  If you
do not wish to use handles,  you can pass the zero handle `(lsHandle *) 0'
to the routine.  For brevity,  the LS_NH macro may be used to specify
no handle to routines which return a handle.

List Creation, Deletion, and Copying
------------------------------------

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. 

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.  If no `delFunc' is provided
	(i.e. `delFunc' is zero),  the items in the list are not
	freed.  Accessing a list after its destruction is a no-no.

lsList lsCopy(list, copyFunc)
lsList list;			/* List to copy              */
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,  the routine will use
       an identity function.

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.

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.

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.

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.  Accessing the last item of a list is a constant
	time operation.


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.  If `data' is
	non-zero,  it will be filled with a pointer to the user data
	for the item (which may then be disposed).  The routine
	returns LS_NOMORE if there are no items in the list to delete.

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.  If `data' is
	non-zero,  it will be filled with a pointer to the user data
	for the item (which may then be disposed).  The routine
	returns LS_NOMORE if there are no items in the list to delete.
	Deleting the last item of a list is a constant time operation.

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.  Obtaining the length of the
       list is a constant time operation.


List Generation Routines
------------------------

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.  The generator is initialized to the
       beginning of the list.  It returns a generator handle which
       should be used when calling lsNext, lsPrev, lsInBefore,
       lsInAfter, lsDelBefore, lsDelAfter, or lsFinish.

lsGen lsEnd(list)
lsList list;			/* List to generate items from */

       This routine returns a generator which can be used to step
       through each item of `list'.  The generator is initialized to
       the end of the list.  This can be used to generate through
       items in reverse order.

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.

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 returns LS_OK).
	lsNext DOES NOT automatically clean up after all elements have
	been generated.  lsFinish must be called explicitly to do
	this.  (Note: an item is generated twice when an lsNext is
        followed by an lsPrev and vice versa.)

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.  (Note: an item is generated twice when an lsNext is
        followed by an lsPrev and vice versa.)

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.

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. 

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 unaffected.  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).

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 unaffected.  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). 

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.



Functional List Generation
--------------------------

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.

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.



Direct Handle Manipulation Routines
-----------------------------------

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.

lsGeneric lsFetchHandle(itemHandle)
lsHandle itemHandle;		/* Handle of an item  */

	Returns the data associated with `handle'.  Returns 0 if
	their were problems.

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'.


Sorting Operations
------------------

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 which runs in
	O(n log n) time.

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.

lsForEachItem(list, gen, data)
list,  /* lsList, list to iterate */      
gen,   /* lsGen, local variable for iterator */
data   /* lsGeneric, variable to return data */ 
        Macro to iterate the items of a list.