src/list/list.c

Go to the documentation of this file.

/*
 * $Id: list.c,v 1.11 2009/04/11 02:02:54 fabio Exp $
 *
 */
/*
 * 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(void)
/*
 * 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(
  lsList list                   /* List to destroy              */,
  void (*delFunc)(lsGeneric)    /* 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(lsGeneric data)
/* Identity copy function */
{
    return data;
}

lsList lsCopy(
  lsList list                           /* List to be copied         */,
  lsGeneric (*copyFunc)(lsGeneric)      /* 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(
  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(
  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(
  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)) {
        *(void **)data = realList->topPtr->userData;
        if (itemHandle) *itemHandle = (lsHandle) (realList->topPtr);
        return(LS_OK);
    } else {
        *(void **)data = (lsGeneric) 0;
        if (itemHandle) *itemHandle = (lsHandle) 0;
        return(LS_NOMORE);
    }
}

lsStatus lsLastItem(
  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)) {
        *(void **)data = realList->botPtr->userData;
        if (itemHandle) *itemHandle = (lsHandle) (realList->botPtr);
        return(LS_OK);
    } else {
        *(void **)data = (lsGeneric) 0;
        if (itemHandle) *itemHandle = (lsHandle) 0;
        return(LS_NOMORE);
    }
}


/* Length of a list */

int lsLength(
  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(
  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 */
        *(void **)data = (lsGeneric) 0;
        return LS_NOMORE;
    } else {
        *(void **)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(
  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 */
        *(void **)data = (lsGeneric) 0;
        return LS_NOMORE;
    } else {
        *(void **)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(
  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(
  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(
  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;
    *(void **)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(
  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.
 */
{
    register lsGenInternal *realGen = (lsGenInternal *) generator;

    if (realGen->afterSpot == NIL(lsElem)) {
        /* No more stuff to generate */
        *(void **) data = (lsGeneric) 0;
        if (itemHandle) *itemHandle = (lsHandle) 0;
        return LS_NOMORE;
    } else {
        *(void **) 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(
  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 */
        *(void **) data = (lsGeneric) 0;
        if (itemHandle) *itemHandle = (lsHandle) 0;
        return LS_NOMORE;
    } else {
        *(void **) 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(
  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(
  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(
  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 */
        *(void **)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;
        *(void **)data = doomedItem->userData;
        FREE(doomedItem);
        return LS_OK;
    }
}


lsStatus lsDelAfter(
  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 */
        *(void **)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;
        *(void **)data = doomedItem->userData;
        FREE(doomedItem);
        return LS_OK;
    }
}


lsStatus lsFinish(
  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 (*userFunc)(lsGeneric, lsGeneric),
                          lsGeneric arg, lsGen gen,
                          lsStatus (*gen_func)(lsGen, lsGeneric, lsHandle *),
                          lsStatus (*del_func)(lsGen, lsGeneric));

lsStatus lsForeach(
  lsList list                   /* List to generate through */,
  lsStatus (*userFunc)(lsGeneric, lsGeneric) /* 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(
  lsList list                   /* List to generate through */,
  lsStatus (*userFunc)(lsGeneric, lsGeneric) /* 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(
  lsStatus (*userFunc)(lsGeneric, lsGeneric) /* User provided function */,
  lsGeneric arg                 /* Data to pass to function       */,
  lsGen gen                     /* Generator to use               */,
  lsStatus (*gen_func)(lsGen, lsGeneric, lsHandle *)
                                /* Generator function to use      */,
  lsStatus (*del_func)(lsGen, lsGeneric) /* 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(
  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(lsHandle itemHandle)
/*
 * This routine returns the user data of the item associated with
 * `itemHandle'.
 */
{
    return ((lsElem *) itemHandle)->userData;
}

lsStatus lsRemoveItem(
  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(
  lsList list                           /* List to sort        */,
  int (*compare)(lsGeneric, lsGeneric)  /* 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(
  lsList list                           /* List to remove duplicates from */,
  int (*compare)(lsGeneric, lsGeneric)  /* Item comparison function       */,
  void (*delFunc)(lsGeneric)            /* 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;
}

---