Azinix

list.c

Go to the documentation of this file.
00001 /**
00002  * \file list.c
00003  * 
00004  * \brief Double linked list code
00005  
00006  It uses a doubly linked list structure and provides some standard operations
00007  for storing and retrieving data from the list.
00008  */
00009 
00010 #include "util.h"
00011 #include "list.h"       /* Self declaration        */
00012 
00013 /**AutomaticStart*************************************************************/
00014 
00015 /*---------------------------------------------------------------------------*/
00016 /* Static function prototypes                                                */
00017 /*---------------------------------------------------------------------------*/
00018 
00019 
00020 /**AutomaticEnd***************************************************************/
00021 
00022 
00023 
00024 /*
00025  * The list identifier is in reality a pointer to the following list
00026  * descriptor structure.  Lists are doubly linked with both top and
00027  * bottom pointers stored in the list descriptor.  The length
00028  * of the list is also stored in the descriptor.
00029  */
00030 
00031 typedef struct list_elem
00032 {               /* One list element  */
00033   struct list_desc *mainList;   /* List descriptor   */
00034   struct list_elem *prevPtr;    /* Previous element  */
00035   struct list_elem *nextPtr;    /* Next list element */
00036   lsGeneric userData;       /* User pointer      */
00037 } lsElem;
00038 
00039 typedef struct list_desc
00040 {               /* List descriptor record            */
00041   lsElem *topPtr, *botPtr;  /* Pointer to top and bottom of list */
00042   int length;           /* Length of list                    */
00043 } lsDesc;
00044 
00045 
00046 /*
00047  * Generators are in reality pointers to the generation descriptor 
00048  * defined below.  A generator has a current spot which is *between*
00049  * two items.  Thus,  a generator consists of two pointers:  record
00050  * before spot and record after spot.  A pointer to the main list
00051  * is included so the top and bottom pointers of the list can be
00052  * modified if needed.
00053  */
00054 
00055 typedef struct gen_desc
00056 {               /* Generator Descriptor         */
00057   lsDesc *mainList;     /* Pointer to list descriptor   */
00058   lsElem *beforeSpot;       /* Item before the current spot */
00059   lsElem *afterSpot;        /* Item after the current spot  */
00060 } lsGenInternal;
00061 
00062 /*
00063  * Handles are in reality pointers to lsElem records.  They are
00064  * cheap to generate and need not be disposed.
00065  */
00066 
00067 
00068 
00069 /*
00070  * List Creation and Deletion
00071  */
00072 
00073 lsList
00074 lsCreate ()
00075 /*
00076  * Creates a new linked list and returns its handle.  The handle is used
00077  * by all other list manipulation routines and should not be discarded.
00078  */
00079 {
00080   lsDesc *newList;
00081 
00082   newList = ALLOC (lsDesc, 1);
00083   newList->topPtr = newList->botPtr = NIL (lsElem);
00084   newList->length = 0;
00085   return ((lsList) newList);
00086 }
00087 
00088 lsStatus
00089 lsDestroy (
00090      lsList list,       // List to destroy              
00091      void (*delFunc) () )   // Routine to release user data 
00092 /*
00093  * Frees all resources associated with the specified list.  It frees memory
00094  * associated with all elements of the list and then deletes the list.
00095  * User data is released by calling 'delFunc' with the pointer as the
00096  * argument.  Accessing a list after its destruction is a no-no.
00097  */
00098 {
00099   lsDesc *realList;
00100   lsElem *index, *temp;
00101 
00102   realList = (lsDesc *) list;
00103   /* Get rid of elements */
00104   index = realList->topPtr;
00105   while (index != NIL (lsElem))
00106     {
00107       temp = index;
00108       index = index->nextPtr;
00109       if (delFunc)
00110     (* ( void(*)( lsGeneric ) ) delFunc) (temp->userData);
00111       free ((lsGeneric) temp);
00112     }
00113   /* Get rid of descriptor */
00114   free ((lsGeneric) realList);
00115   return (LS_OK);
00116 }
00117 
00118 
00119 /*
00120  * Copying lists
00121  */
00122 
00123 static lsGeneric
00124 lsIdentity ( lsGeneric data )
00125 /* Identity copy function */
00126 {
00127   return data;
00128 }
00129 
00130 lsList
00131 lsCopy (
00132         lsList list,            // List to be copied       
00133     lsGeneric (*copyFunc) ()    // Routine to copy user data 
00134 )
00135 /*
00136  * Returns a copy of list `list'.  If `copyFunc' is non-zero,
00137  * it will be called for each item in `list' and the pointer it 
00138  * returns will be used in place of the original user data for the 
00139  * item in the newly created list.  The form of `copyFunc' should be:
00140  *   lsGeneric copyFunc(data)
00141  *   lsGeneric data;
00142  * This is normally used to make copies of the user data in the new list.
00143  * If no `copyFunc' is provided,  an identity function is used.
00144  */
00145 {
00146   lsList newList;
00147   lsGen gen;
00148   lsGeneric data;
00149 
00150   if (!copyFunc)
00151     copyFunc = ( lsGeneric(*)( ) ) lsIdentity;
00152   newList = lsCreate ();
00153   gen = lsStart (list);
00154   while (lsNext (gen, &data, LS_NH) == LS_OK)
00155     {
00156       (void) lsNewEnd (newList, (*(lsGeneric(*)(lsGeneric) ) copyFunc) (data), LS_NH);
00157     }
00158   lsFinish (gen);
00159   return newList;
00160 }
00161 
00162 
00163 /*
00164  * Adding New Elements to the Beginning and End of a List
00165  */
00166 
00167 lsStatus
00168 lsNewBegin (
00169      lsList list,       // List to add element to    
00170      lsGeneric data,        // Arbitrary pointer to data 
00171      lsHandle *itemHandle   // Handle to data (returned)
00172 )
00173 /*
00174  * Adds a new item to the start of a previously created linked list.
00175  * If 'itemHandle' is non-zero,  it will be filled with a handle
00176  * which can be used to generate a generator positioned at the
00177  * item without generating through the list.
00178  */
00179 {
00180   lsDesc *realList = (lsDesc *) list;
00181   lsElem *newElem;
00182 
00183   newElem = ALLOC (lsElem, 1);
00184   newElem->userData = data;
00185   newElem->nextPtr = realList->topPtr;
00186   newElem->prevPtr = NIL (lsElem);
00187   newElem->mainList = realList;
00188   if (realList->topPtr == NIL (lsElem))
00189     {
00190       /* The new item is both the top and bottom element */
00191       realList->botPtr = newElem;
00192     }
00193   else
00194     {
00195       /* There was a top element - make its prev correct */
00196       realList->topPtr->prevPtr = newElem;
00197     }
00198   realList->topPtr = newElem;
00199   realList->length += 1;
00200   if (itemHandle)
00201     *itemHandle = (lsHandle) newElem;
00202   return (LS_OK);
00203 }
00204 
00205 lsStatus
00206 lsNewEnd (
00207      lsList list,       // List to append element to
00208      lsGeneric data,        // Arbitrary pointer to data
00209      lsHandle *itemHandle   // Handle to data (returned) 
00210 )
00211 /*
00212  * Adds a new item to the end of a previously created linked list.
00213  * This routine appends the item in constant time and
00214  * can be used freely without guilt.
00215  */
00216 {
00217   lsDesc *realList = (lsDesc *) list;
00218   lsElem *newElem;
00219 
00220   newElem = ALLOC (lsElem, 1);
00221   newElem->userData = data;
00222   newElem->prevPtr = realList->botPtr;
00223   newElem->nextPtr = NIL (lsElem);
00224   newElem->mainList = realList;
00225   if (realList->topPtr == NIL (lsElem))
00226     realList->topPtr = newElem;
00227   if (realList->botPtr != NIL (lsElem))
00228     realList->botPtr->nextPtr = newElem;
00229   realList->botPtr = newElem;
00230   realList->length += 1;
00231   if (itemHandle)
00232     *itemHandle = (lsHandle) newElem;
00233   return (LS_OK);
00234 }
00235 
00236 /*
00237  * Retrieving the first and last items of a list
00238  */
00239 
00240 lsStatus
00241 lsFirstItem (
00242      lsList list,       // List to get item from 
00243      lsGeneric *data,       // User data (returned)  
00244      lsHandle *itemHandle   // Handle to data (returned) 
00245 )
00246 /*
00247  * Returns the first item in the list.  If the list is empty,
00248  * it returns LS_NOMORE.  Otherwise,  it returns LS_OK.
00249  * If 'itemHandle' is non-zero,  it will be filled with a
00250  * handle which may be used to generate a generator.
00251  */
00252 {
00253   lsDesc *realList = (lsDesc *) list;
00254 
00255   if (realList->topPtr != NIL (lsElem))
00256     {
00257       *data = realList->topPtr->userData;
00258       if (itemHandle)
00259     *itemHandle = (lsHandle) (realList->topPtr);
00260       return (LS_OK);
00261     }
00262   else
00263     {
00264       *data = (lsGeneric) 0;
00265       if (itemHandle)
00266     *itemHandle = (lsHandle) 0;
00267       return (LS_NOMORE);
00268     }
00269 }
00270 
00271 lsStatus
00272 lsLastItem (
00273      lsList list,       // List to get item from
00274      lsGeneric *data,       // User data (returned) 
00275      lsHandle *itemHandle   // Handle to data (returned) 
00276 )
00277 /*
00278  * Returns the last item of a list.  If the list is empty,
00279  * the routine returns LS_NOMORE.  Otherwise,  'data' will
00280  * be set to the last item and the routine will return LS_OK.
00281  * If 'itemHandle' is non-zero,  it will be filled with a
00282  * handle which can be used to generate a generator postioned
00283  * at this item.
00284  */
00285 {
00286   lsDesc *realList = (lsDesc *) list;
00287 
00288   if (realList->botPtr != NIL (lsElem))
00289     {
00290       *data = realList->botPtr->userData;
00291       if (itemHandle)
00292     *itemHandle = (lsHandle) (realList->botPtr);
00293       return (LS_OK);
00294     }
00295   else
00296     {
00297       *data = (lsGeneric) 0;
00298       if (itemHandle)
00299     *itemHandle = (lsHandle) 0;
00300       return (LS_NOMORE);
00301     }
00302 }
00303 
00304 
00305 
00306 /* Length of a list */
00307 
00308 int
00309 lsLength (lsList list)
00310 /*
00311  * Returns the length of the list.  The list must have been
00312  * already created using lsCreate.
00313  */
00314 {
00315   lsDesc *realList = (lsDesc *) list;
00316 
00317   return (realList->length);
00318 }
00319 
00320 
00321 
00322 /*
00323  * Deleting first and last items of a list
00324  */
00325 
00326 lsStatus
00327 lsDelBegin (
00328      lsList list,       // List to delete item from 
00329      lsGeneric *data        // First item (returned)   
00330 )
00331 /*
00332  * This routine deletes the first item of a list.  The user
00333  * data associated with the item is returned so the caller
00334  * may dispose of it.  Returns LS_NOMORE if there is no
00335  * item to delete.
00336  */
00337 {
00338   lsDesc *realList = (lsDesc *) list;
00339   lsElem *temp;
00340 
00341   if (realList->topPtr == NIL (lsElem))
00342     {
00343       /* Nothing to delete */
00344       *data = (lsGeneric) 0;
00345       return LS_NOMORE;
00346     }
00347   else
00348     {
00349       *data = realList->topPtr->userData;
00350       temp = realList->topPtr;
00351       realList->topPtr = realList->topPtr->nextPtr;
00352       if (temp->nextPtr != NIL (lsElem))
00353     {
00354       /* There is something after the first item */
00355       temp->nextPtr->prevPtr = NIL (lsElem);
00356     }
00357       else
00358     {
00359       /* Nothing after it - bottom becomes null as well */
00360       realList->botPtr = NIL (lsElem);
00361     }
00362       free ((lsGeneric) temp);
00363       realList->length -= 1;
00364     }
00365   return LS_OK;
00366 }
00367 
00368 
00369 lsStatus
00370 lsDelEnd (
00371      lsList list,       /* List to delete item from */
00372      lsGeneric *data        /* Last item (returned)     */
00373 )
00374 /*
00375  * This routine deletes the last item of a list.  The user
00376  * data associated with the item is returned so the caller
00377  * may dispose of it.  Returns LS_NOMORE if there is nothing
00378  * to delete.
00379  */
00380 {
00381   lsDesc *realList = (lsDesc *) list;
00382   lsElem *temp;
00383 
00384   if (realList->botPtr == NIL (lsElem))
00385     {
00386       /* Nothing to delete */
00387       *data = (lsGeneric) 0;
00388       return LS_NOMORE;
00389     }
00390   else
00391     {
00392       *data = realList->botPtr->userData;
00393       temp = realList->botPtr;
00394       realList->botPtr = realList->botPtr->prevPtr;
00395       if (temp->prevPtr != NIL (lsElem))
00396     {
00397       /* There is something before the last item */
00398       temp->prevPtr->nextPtr = NIL (lsElem);
00399     }
00400       else
00401     {
00402       /* Nothing before it - top becomes null as well */
00403       realList->topPtr = NIL (lsElem);
00404     }
00405       free ((lsGeneric) temp);
00406       realList->length -= 1;
00407     }
00408   return LS_OK;
00409 }
00410 
00411 
00412 /*
00413  * List Generation Routines
00414  *
00415  * nowPtr is the element just before the next one to be generated
00416  */
00417 
00418 lsGen
00419 lsStart (
00420      lsList list        /* List to generate items from */
00421 )
00422 /*
00423  * This routine defines a generator which is used to step through
00424  * each item of the list.  It returns a generator handle which should
00425  * be used when calling lsNext, lsPrev, lsInBefore, lsInAfter, lsDelete,
00426  * or lsFinish.
00427  */
00428 {
00429   lsDesc *realList = (lsDesc *) list;
00430   lsGenInternal *newGen;
00431 
00432   newGen = ALLOC (lsGenInternal, 1);
00433   newGen->mainList = realList;
00434   newGen->beforeSpot = NIL (lsElem);
00435   newGen->afterSpot = realList->topPtr;
00436   return ((lsGen) newGen);
00437 }
00438 
00439 lsGen
00440 lsEnd (
00441      lsList list        // List to generate items from
00442 )
00443 /*
00444  * This routine defines a generator which is used to step through
00445  * each item of a list.  The generator is initialized to the end 
00446  * of the list.
00447  */
00448 {
00449   lsDesc *realList = (lsDesc *) list;
00450   lsGenInternal *newGen;
00451 
00452   newGen = ALLOC (lsGenInternal, 1);
00453   newGen->mainList = realList;
00454   newGen->beforeSpot = realList->botPtr;
00455   newGen->afterSpot = NIL (lsElem);
00456   return (lsGen) newGen;
00457 }
00458 
00459 lsGen
00460 lsGenHandle (
00461      lsHandle itemHandle,   /* Handle of an item         */
00462      lsGeneric *data,       /* Data associated with item */
00463      int option     /* LS_BEFORE or LS_AFTER     */
00464 )
00465 /*
00466  * This routine produces a generator given a handle.  Handles
00467  * are produced whenever an item is added to a list.  The generator
00468  * produced by this routine may be used when calling any of 
00469  * the standard generation routines.  NOTE:  the generator
00470  * should be freed using lsFinish.  The 'option' parameter
00471  * determines whether the generator spot is before or after
00472  * the handle item.
00473  */
00474 {
00475   lsElem *realItem = (lsElem *) itemHandle;
00476   lsGenInternal *newGen;
00477 
00478   newGen = ALLOC (lsGenInternal, 1);
00479   newGen->mainList = realItem->mainList;
00480   *data = realItem->userData;
00481   if (option & LS_BEFORE)
00482     {
00483       newGen->beforeSpot = realItem->prevPtr;
00484       newGen->afterSpot = realItem;
00485     }
00486   else if (option & LS_AFTER)
00487     {
00488       newGen->beforeSpot = realItem;
00489       newGen->afterSpot = realItem->nextPtr;
00490     }
00491   else
00492     {
00493       free ((lsGeneric) newGen);
00494       newGen = (lsGenInternal *) 0;
00495     }
00496   return ((lsGen) newGen);
00497 }
00498 
00499 
00500 lsStatus
00501 lsNext (
00502      lsGen generator,       /* Generator handle        */
00503      lsGeneric *data,       /* User data (return)      */
00504      lsHandle *itemHandle   /* Handle to item (return) */
00505 )
00506 /*
00507  * Generates the item after the item previously generated by lsNext
00508  * or lsPrev.   It returns a pointer to the user data structure in 'data'.  
00509  * 'itemHandle' may be used to get a generation handle without
00510  * generating through the list to find the item.  If there are no more 
00511  * elements to generate, the routine returns  LS_NOMORE (normally it 
00512  * returns LS_OK).  lsNext DOES NOT automatically clean up after all 
00513  * elements have been generated.  lsFinish must be called explicitly to do this.
00514  */
00515 {
00516   register lsGenInternal *realGen = (lsGenInternal *) generator;
00517 
00518   if (realGen->afterSpot == NIL (lsElem))
00519     {
00520       /* No more stuff to generate */
00521       *data = (lsGeneric) 0;
00522       if (itemHandle)
00523     *itemHandle = (lsHandle) 0;
00524       return LS_NOMORE;
00525     }
00526   else
00527     {
00528       *data = realGen->afterSpot->userData;
00529       if (itemHandle)
00530     *itemHandle = (lsHandle) (realGen->afterSpot);
00531       /* Move the pointers down one */
00532       realGen->beforeSpot = realGen->afterSpot;
00533       realGen->afterSpot = realGen->afterSpot->nextPtr;
00534       return LS_OK;
00535     }
00536 }
00537 
00538 
00539 lsStatus
00540 lsPrev (
00541      lsGen generator,       /* Generator handle        */
00542      lsGeneric *data,       /* User data (return)      */
00543      lsHandle *itemHandle   /* Handle to item (return) */
00544 )
00545 /*
00546  * Generates the item before the item previously generated by lsNext
00547  * or lsPrev.   It returns a pointer to the user data structure in 'data'.  
00548  * 'itemHandle' may be used to get a generation handle without
00549  * generating through the list to find the item.  If there are no more 
00550  * elements to generate, the routine returns  LS_NOMORE (normally it 
00551  * returns LS_OK).  lsPrev DOES NOT automatically clean up after all 
00552  * elements have been generated.  lsFinish must be called explicitly to do this.
00553  */
00554 {
00555   register lsGenInternal *realGen = (lsGenInternal *) generator;
00556 
00557   if (realGen->beforeSpot == NIL (lsElem))
00558     {
00559       /* No more stuff to generate */
00560       *data = (lsGeneric) 0;
00561       if (itemHandle)
00562     *itemHandle = (lsHandle) 0;
00563       return LS_NOMORE;
00564     }
00565   else
00566     {
00567       *data = realGen->beforeSpot->userData;
00568       if (itemHandle)
00569     *itemHandle = (lsHandle) (realGen->beforeSpot);
00570       /* Move the pointers down one */
00571       realGen->afterSpot = realGen->beforeSpot;
00572       realGen->beforeSpot = realGen->beforeSpot->prevPtr;
00573       return LS_OK;
00574     }
00575 
00576 }
00577 
00578 lsStatus
00579 lsInBefore (
00580      lsGen generator,       /* Generator handle          */
00581      lsGeneric data,        /* Arbitrary pointer to data */
00582      lsHandle *itemHandle   /* Handle to item (return) */
00583 )
00584 /*
00585  * Inserts an element BEFORE the current spot.  The item generated
00586  * by lsNext will be unchanged;  the inserted item will be generated
00587  * by lsPrev.  This modifies the list.  'itemHandle' may be used at 
00588  * a later time to produce a generation handle without generating 
00589  * through the list.
00590  */
00591 {
00592   lsGenInternal *realGen = (lsGenInternal *) generator;
00593   lsElem *newElem;
00594 
00595   if (realGen->beforeSpot == NIL (lsElem))
00596     {
00597       /* Item added to the beginning of the list */
00598       (void) lsNewBegin ((lsList) realGen->mainList, data, itemHandle);
00599       realGen->beforeSpot = realGen->mainList->topPtr;
00600       return LS_OK;
00601     }
00602   else if (realGen->afterSpot == NIL (lsElem))
00603     {
00604       /* Item added to the end of the list */
00605       (void) lsNewEnd ((lsList) realGen->mainList, data, itemHandle);
00606       realGen->afterSpot = realGen->mainList->botPtr;
00607       return LS_OK;
00608     }
00609   else
00610     {
00611       /* Item added in the middle of the list */
00612       newElem = ALLOC (lsElem, 1);
00613       newElem->mainList = realGen->mainList;
00614       newElem->prevPtr = realGen->beforeSpot;
00615       newElem->nextPtr = realGen->afterSpot;
00616       newElem->userData = data;
00617       realGen->beforeSpot->nextPtr = newElem;
00618       realGen->afterSpot->prevPtr = newElem;
00619       realGen->beforeSpot = newElem;
00620       realGen->mainList->length += 1;
00621       if (itemHandle)
00622     *itemHandle = (lsHandle) newElem;
00623       return LS_OK;
00624     }
00625 }
00626 
00627 lsStatus
00628 lsInAfter (
00629      lsGen generator,       /* Generator handle          */
00630      lsGeneric data,        /* Arbitrary pointer to data */
00631      lsHandle *itemHandle   /* Handle to item (return)   */
00632 )
00633 /*
00634  * Inserts an element AFTER the current spot.  The next item generated
00635  * by lsNext will be the new element.  The next  item generated by
00636  * lsPrev is unchanged.  This modifies the list.  'itemHandle' may
00637  * be used at a later time to generate a generation handle without
00638  * searching through the list to find the item.
00639  */
00640 {
00641   lsGenInternal *realGen = (lsGenInternal *) generator;
00642   lsElem *newElem;
00643 
00644   if (realGen->beforeSpot == NIL (lsElem))
00645     {
00646       /* Item added to the beginning of the list */
00647       (void) lsNewBegin ((lsList) realGen->mainList, data, itemHandle);
00648       realGen->beforeSpot = realGen->mainList->topPtr;
00649       return LS_OK;
00650     }
00651   else if (realGen->afterSpot == NIL (lsElem))
00652     {
00653       /* Item added to the end of the list */
00654       (void) lsNewEnd ((lsList) realGen->mainList, data, itemHandle);
00655       realGen->afterSpot = realGen->mainList->botPtr;
00656       return LS_OK;
00657     }
00658   else
00659     {
00660       /* Item added in the middle of the list */
00661       newElem = ALLOC (lsElem, 1);
00662       newElem->mainList = realGen->mainList;
00663       newElem->prevPtr = realGen->beforeSpot;
00664       newElem->nextPtr = realGen->afterSpot;
00665       newElem->userData = data;
00666       realGen->beforeSpot->nextPtr = newElem;
00667       realGen->afterSpot->prevPtr = newElem;
00668       realGen->afterSpot = newElem;
00669       realGen->mainList->length += 1;
00670       if (itemHandle)
00671     *itemHandle = (lsHandle) newElem;
00672       return LS_OK;
00673     }
00674 }
00675 
00676 
00677 lsStatus
00678 lsDelBefore (
00679      lsGen generator,       /* Generator handle        */
00680      lsGeneric *data        /* Deleted item (returned) */
00681 )
00682 /*
00683  * Removes the item before the current spot.  The next call to lsPrev
00684  * will return the item before the deleted item.  The next call to lsNext
00685  * will be uneffected.  This modifies the list.  The routine returns 
00686  * LS_BADSTATE if the user tries to call the routine and there is
00687  * no item before the current spot.  This routine returns the userData
00688  * of the deleted item so it may be freed (if necessary).
00689  */
00690 {
00691   lsGenInternal *realGen = (lsGenInternal *) generator;
00692   lsElem *doomedItem;
00693 
00694   if (realGen->beforeSpot == NIL (lsElem))
00695     {
00696       /* No item to delete */
00697       *data = (lsGeneric) 0;
00698       return LS_BADSTATE;
00699     }
00700   else if (realGen->beforeSpot == realGen->mainList->topPtr)
00701     {
00702       /* Delete the first item of the list */
00703       realGen->beforeSpot = realGen->beforeSpot->prevPtr;
00704       return lsDelBegin ((lsList) realGen->mainList, data);
00705     }
00706   else if (realGen->beforeSpot == realGen->mainList->botPtr)
00707     {
00708       /* Delete the last item of the list */
00709       realGen->beforeSpot = realGen->beforeSpot->prevPtr;
00710       return lsDelEnd ((lsList) realGen->mainList, data);
00711     }
00712   else
00713     {
00714       /* Normal mid list deletion */
00715       doomedItem = realGen->beforeSpot;
00716       doomedItem->prevPtr->nextPtr = doomedItem->nextPtr;
00717       doomedItem->nextPtr->prevPtr = doomedItem->prevPtr;
00718       realGen->beforeSpot = doomedItem->prevPtr;
00719       realGen->mainList->length -= 1;
00720       *data = doomedItem->userData;
00721       free ((lsGeneric) doomedItem);
00722       return LS_OK;
00723     }
00724 }
00725 
00726 
00727 lsStatus
00728 lsDelAfter (
00729      lsGen generator,       /* Generator handle        */
00730      lsGeneric *data        /* Deleted item (returned) */
00731 )
00732 /*
00733  * Removes the item after the current spot.  The next call to lsNext
00734  * will return the item after the deleted item.  The next call to lsPrev
00735  * will be uneffected.  This modifies the list.  The routine returns 
00736  * LS_BADSTATE if the user tries to call the routine and there is
00737  * no item after the current spot.  This routine returns the userData
00738  * of the deleted item so it may be freed (if necessary).
00739  */
00740 {
00741   lsGenInternal *realGen = (lsGenInternal *) generator;
00742   lsElem *doomedItem;
00743 
00744   if (realGen->afterSpot == NIL (lsElem))
00745     {
00746       /* No item to delete */
00747       *data = (lsGeneric) 0;
00748       return LS_BADSTATE;
00749     }
00750   else if (realGen->afterSpot == realGen->mainList->topPtr)
00751     {
00752       /* Delete the first item of the list */
00753       realGen->afterSpot = realGen->afterSpot->nextPtr;
00754       return lsDelBegin ((lsList) realGen->mainList, data);
00755     }
00756   else if (realGen->afterSpot == realGen->mainList->botPtr)
00757     {
00758       /* Delete the last item of the list */
00759       realGen->afterSpot = realGen->afterSpot->nextPtr;
00760       return lsDelEnd ((lsList) realGen->mainList, data);
00761     }
00762   else
00763     {
00764       /* Normal mid list deletion */
00765       doomedItem = realGen->afterSpot;
00766       doomedItem->prevPtr->nextPtr = doomedItem->nextPtr;
00767       doomedItem->nextPtr->prevPtr = doomedItem->prevPtr;
00768       realGen->afterSpot = doomedItem->nextPtr;
00769       realGen->mainList->length -= 1;
00770       *data = doomedItem->userData;
00771       free ((lsGeneric) doomedItem);
00772       return LS_OK;
00773     }
00774 }
00775 
00776 
00777 
00778 lsStatus
00779 lsFinish (
00780      lsGen generator        /* Generator handle */
00781 )
00782 /*
00783  * Marks the completion of a generation of list items.  This routine should
00784  * be called after calls to lsNext to free resources used by the
00785  * generator.  This rule applies even if all items of a list are
00786  * generated by lsNext.
00787  */
00788 {
00789   lsGenInternal *realGen = (lsGenInternal *) generator;
00790 
00791   free ((lsGeneric) realGen);
00792   return (LS_OK);
00793 }
00794 
00795 
00796 
00797 /*
00798  * Functional list generation
00799  *
00800  * An alternate form of generating through items of a list is provided.
00801  * The routines below generatae through all items of a list in a given
00802  * direction and call a user provided function for each one.
00803  */
00804 
00805 static lsStatus lsGenForm (
00806     lsStatus (*) (),    
00807         lsGeneric,
00808         lsGen,      
00809     lsStatus (*) (),    
00810     lsStatus (*) () );
00811 
00812 
00813 lsStatus
00814 lsForeach (
00815         lsList list,        /* List to generate through */
00816     lsStatus (*userFunc) (),    /* User provided function   */
00817         lsGeneric arg       /* User provided data       */
00818 )
00819 /*
00820  * This routine generates all items in `list' from the first item
00821  * to the last calling `userFunc' for each item.  The function
00822  * should have the following form:
00823  *   lsStatus userFunc(data, arg)
00824  *   lsGeneric data;
00825  *   lsGeneric arg;
00826  * `data' will be the user data associated with the item generated.
00827  * `arg' will be the same pointer provided to lsForeach.  The
00828  * routine should return LS_OK to continue the generation,  LS_STOP
00829  * to stop generating items,  and LS_DELETE to delete the item
00830  * from the list.  If the generation was stopped prematurely,
00831  * the routine will return LS_STOP.  If the user provided function
00832  * does not return an appropriate value,  the routine will return
00833  * LS_BADPARAM.
00834  */
00835 {
00836   return lsGenForm (userFunc, arg, lsStart (list), (lsStatus (*) ()) lsNext, (lsStatus (*) ()) lsDelBefore);
00837 }
00838 
00839 lsStatus
00840 lsBackeach (
00841         lsList list,        /* List to generate through */
00842     lsStatus (*userFunc) (),    /* User provided function   */
00843         lsGeneric arg       /* User provided data       */
00844 )
00845 /*
00846  * This routine is just like lsForeach except it generates
00847  * all items in `list' from the last item to the first.
00848  */
00849 {
00850   return lsGenForm (userFunc, arg, lsEnd (list), (lsStatus (*) ()) lsPrev, (lsStatus (*) ()) lsDelAfter);
00851 }
00852 
00853 
00854 
00855 static lsStatus
00856 lsGenForm (
00857     lsStatus (*userFunc) (),    /* User provided function         */
00858         lsGeneric arg,      /* Data to pass to function       */
00859         lsGen gen,          /* Generator to use               */
00860     lsStatus (*gen_func) (),    /* Generator function to use      */
00861     lsStatus (*del_func) () /* Deletion function to use       */
00862 )
00863 /*
00864  * This is the function used to implement the two functional
00865  * generation interfaces to lists.
00866  */
00867 {
00868   lsGeneric data;
00869 
00870   while ( (* ( lsStatus(*)( lsGen, lsGeneric *, lsHandle *  ) ) gen_func) (gen, & data, LS_NH) == LS_OK)
00871     {
00872       switch ( ( * ( lsStatus(*)( lsGeneric, lsGeneric ) ) userFunc ) (data, arg))
00873     {
00874     case LS_OK:
00875       /* Nothing */
00876       break;
00877     case LS_STOP:
00878       (void) lsFinish (gen);
00879       return LS_STOP;
00880     case LS_DELETE:
00881       (* ( lsStatus(*)(  lsGen, lsGeneric * ) ) del_func ) (gen, &data);
00882       break;
00883     default:
00884       return LS_BADPARAM;
00885     }
00886     }
00887   (void) lsFinish (gen);
00888   return LS_OK;
00889 }
00890 
00891 
00892 lsList
00893 lsQueryHandle (
00894      lsHandle itemHandle    /* Handle of an item  */
00895 )
00896 /*
00897  * This routine returns the associated list of the specified
00898  * handle.  Returns 0 if there were problems.
00899  */
00900 {
00901   lsElem *realHandle = (lsElem *) itemHandle;
00902 
00903   if (realHandle)
00904     {
00905       return (lsList) realHandle->mainList;
00906     }
00907   else
00908     {
00909       return (lsList) 0;
00910     }
00911 }
00912 
00913 lsGeneric
00914 lsFetchHandle (
00915      lsHandle itemHandle
00916 )
00917 /*
00918  * This routine returns the user data of the item associated with
00919  * `itemHandle'.
00920  */
00921 {
00922   return ((lsElem *) itemHandle)->userData;
00923 }
00924 
00925 lsStatus
00926 lsRemoveItem (
00927      lsHandle itemHandle,   /* Handle of an item */
00928      lsGeneric *userData    /* Returned data     */
00929 )
00930 /*
00931  * This routine removes the item associated with `handle' from
00932  * its list and returns the user data associated with the item
00933  * for reclaimation purposes.  Note this modifies the list
00934  * that originally contained `item'.
00935  */
00936 {
00937   lsElem *realItem = (lsElem *) itemHandle;
00938   lsGenInternal gen;
00939 
00940   gen.mainList = realItem->mainList;
00941   gen.beforeSpot = realItem->prevPtr;
00942   gen.afterSpot = realItem;
00943   return lsDelAfter ((lsGen) & gen, userData);
00944 }
00945 
00946 
00947 /* List sorting support */
00948 #define TYPE        lsElem
00949 #define SORT        lsSortItems
00950 #define NEXT        nextPtr
00951 #define FIELD       userData
00952 
00953 lsStatus
00954 lsUniq (
00955      lsList list,       /* List to remove duplicates from */
00956      int (*compare) (),     /* Item comparison function       */
00957      void (*delFunc) ()     /* Function to release user data  */
00958 )
00959 /*
00960  * This routine takes a sorted list and removes all duplicates
00961  * from it.  `compare' has the following form:
00962  *   int compare(item1, item2)
00963  *   lsGeneric item1, item2;
00964  * The routine should return -1 if item1 is less than item2, 0 if
00965  * they are equal,  and 1 if item1 is greater than item2. `delFunc'
00966  * will be called with a pointer to a user data item for each
00967  * duplicate destroyed.  `delFunc' can be zero if no clean up
00968  * is required.
00969  */
00970 {
00971   lsGeneric this_item, last_item;
00972   lsGenInternal realGen;
00973   lsDesc *realList = (lsDesc *) list;
00974 
00975   if (realList->length > 1)
00976     {
00977       last_item = realList->topPtr->userData;
00978 
00979       /* Inline creation of generator */
00980       realGen.mainList = realList;
00981       realGen.beforeSpot = realList->topPtr;
00982       realGen.afterSpot = realList->topPtr->nextPtr;
00983 
00984       while (realGen.afterSpot)
00985     {
00986       this_item = realGen.afterSpot->userData;
00987       if ((* ( int(*)( lsGeneric, lsGeneric )  ) compare) (this_item, last_item) == 0)
00988         {
00989           /* Duplicate -- eliminate */
00990           (void) lsDelAfter ((lsGen) & realGen, &this_item);
00991           if (delFunc)
00992         (* ( int(*)( lsGeneric ) ) delFunc) (this_item);
00993         }
00994       else
00995         {
00996           /* Move generator forward */
00997           realGen.beforeSpot = realGen.afterSpot;
00998           realGen.afterSpot = realGen.afterSpot->nextPtr;
00999           last_item = this_item;
01000         }
01001     }
01002     }
01003   return LS_OK;
01004 }