list.c

Go to the documentation of this file.

/**
 * \file list.c
 * 
 * \brief Double linked list code
 
 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        */

/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/


/**AutomaticEnd***************************************************************/



/*
 * 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 (
     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)
    (* ( void(*)( lsGeneric ) ) delFunc) (temp->userData);
      free ((lsGeneric) temp);
    }
  /* Get rid of descriptor */
  free ((lsGeneric) 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) ()    // 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 = ( lsGeneric(*)( ) ) lsIdentity;
  newList = lsCreate ();
  gen = lsStart (list);
  while (lsNext (gen, &data, LS_NH) == LS_OK)
    {
      (void) lsNewEnd (newList, (*(lsGeneric(*)(lsGeneric) ) 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))
    {
      *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 (
     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 (lsList list)
/*
 * 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 */
      *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 ((lsGeneric) 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 */
      *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 ((lsGeneric) 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;
  *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 ((lsGeneric) 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 */
      *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 (
     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 (
     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 */
      *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 ((lsGeneric) 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 */
      *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 ((lsGeneric) 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 ((lsGeneric) 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 (*) (),    
        lsGeneric,
        lsGen,      
    lsStatus (*) (),    
    lsStatus (*) () );


lsStatus
lsForeach (
        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), (lsStatus (*) ()) lsNext, (lsStatus (*) ()) lsDelBefore);
}

lsStatus
lsBackeach (
        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), (lsStatus (*) ()) lsPrev, (lsStatus (*) ()) lsDelAfter);
}



static lsStatus
lsGenForm (
    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 ( (* ( lsStatus(*)( lsGen, lsGeneric *, lsHandle *  ) ) gen_func) (gen, & data, LS_NH) == LS_OK)
    {
      switch ( ( * ( lsStatus(*)( lsGeneric, lsGeneric ) ) userFunc ) (data, arg))
    {
    case LS_OK:
      /* Nothing */
      break;
    case LS_STOP:
      (void) lsFinish (gen);
      return LS_STOP;
    case LS_DELETE:
      (* ( lsStatus(*)(  lsGen, lsGeneric * ) ) 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

lsStatus
lsUniq (
     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 ((* ( int(*)( lsGeneric, lsGeneric )  ) compare) (this_item, last_item) == 0)
        {
          /* Duplicate -- eliminate */
          (void) lsDelAfter ((lsGen) & realGen, &this_item);
          if (delFunc)
        (* ( int(*)( lsGeneric ) ) delFunc) (this_item);
        }
      else
        {
          /* Move generator forward */
          realGen.beforeSpot = realGen.afterSpot;
          realGen.afterSpot = realGen.afterSpot->nextPtr;
          last_item = this_item;
        }
    }
    }
  return LS_OK;
}