home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: WPS_PM / WPS_PM.zip / xfld085s.zip / helpers / linklist.c < prev    next >
C/C++ Source or Header  |  1999-02-23  |  17KB  |  495 lines
  1.  
  2. /*
  3.  *@@sourcefile linklist.c:
  4.  *      contains helper functions for maintaining linked lists.
  5.  *      See explanations below.
  6.  *
  7.  *      This file is new with V0.81 and contains all the functions
  8.  *      that were in helpers.c previously.
  9.  *
  10.  *      Function prefixes (new with V0.81):
  11.  *      --  lst*    linked list helper functions
  12.  *
  13.  *      Changes for V0.84: All references to mutex semaphores have been
  14.  *      removed. It is now the exclusive job of the caller to serialize
  15.  *      access to these linked lists. It is not possible to implement
  16.  *      proper exception handling otherwise.
  17.  *
  18.  *@@include #include "linklist.h"
  19.  */
  20.  
  21. /*
  22.  *      Copyright (C) 1997-99 Ulrich Möller.
  23.  *      This file is part of the XFolder source package.
  24.  *      XFolder is free software; you can redistribute it and/or modify
  25.  *      it under the terms of the GNU General Public License as published
  26.  *      by the Free Software Foundation, in version 2 as it comes in the
  27.  *      "COPYING" file of the XFolder main distribution.
  28.  *      This program is distributed in the hope that it will be useful,
  29.  *      but WITHOUT ANY WARRANTY; without even the implied warranty of
  30.  *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  31.  *      GNU General Public License for more details.
  32.  */
  33.  
  34. #include <stdlib.h>
  35. // #include <string.h>
  36. // #include <stdio.h>
  37.  
  38. #include "linklist.h"
  39.  
  40. /********************************************************************
  41.  *                                                                  *
  42.  *   Functions for maintaining linked pointer lists                 *
  43.  *                                                                  *
  44.  ********************************************************************/
  45.  
  46. /* The following functions are used commonly to maintain linked
  47.    pointer lists: we have functions for appending, counting and
  48.    removing list items, plus one for deleting a whole list.
  49.    All these function names are introduced by "lst".
  50.  
  51.    Note that all these functions assume the passed pointers to
  52.    be pointers to LISTITEM structures (linklist.h). You may, of course,
  53.    use different structures, but the first items in your structure
  54.    must be *pNext, *pPrevious, ulSize like in LISTITEM to make these
  55.    functions work. You will then have to cast your structure pointers
  56.    manually to PLISTITEM or PLISTITEM* before using these functions.
  57.  
  58.    All of the following functions work in two modes:
  59.    -- "one-way" lists, i.e. list which can only be accessed through
  60.       the first item on the list: this mode applies when *ppList
  61.       is specified to be NULL;
  62.    -- "two-way" lists, i.e. list which can be accessed both through
  63.       the first item and the last item on the list; in this case,
  64.       you must also specify *ppLast, the pointer of the last item,
  65.       which will also be maintained by these functions. "Two-way"
  66.       lists are much faster when appending many items, because we
  67.       don't have to go through the whole list to find the last item.
  68. */
  69.  
  70. /*
  71.  *@@ lstAppendItem:
  72.  *      this will create an item for a linked list starting at
  73.  *      *ppFirst; this must be a pointer to a pointer to the
  74.  *      first list item; if *ppFirst is NULL (= list is empty),
  75.  *      *ppFirst will be adjusted so that it points to the new
  76.  *      item. If ppLast == NULL, the list is assumed to be
  77.  *      a "one-way" list, otherwise it must point to a pointer
  78.  *      for the last list item, which will be adjusted.
  79.  *      This function returns the address of the new list item.
  80.  */
  81.  
  82. PLISTITEM lstAppendItem(PLISTITEM *ppFirst, // first list item
  83.             PLISTITEM *ppLast,              // last list item (or NULL)
  84.             PLISTITEM pNewItem)             // item to insert
  85. {
  86.     if (pNewItem)
  87.     {
  88.         pNewItem->pNext = NULL;
  89.  
  90.         if (*ppFirst == NULL) {
  91.             // list is empty: set first pointer to new list item
  92.             *ppFirst = (void*)pNewItem;
  93.             pNewItem->pPrevious = NULL;
  94.         } else {
  95.             BOOL    Search = TRUE;
  96.             // list is not empty: find end of list and append the
  97.             // new item
  98.  
  99.             if (ppLast)
  100.                 if (*ppLast) {
  101.                     // last item given: use this
  102.                     (*ppLast)->pNext = pNewItem;
  103.                     pNewItem->pPrevious = *ppLast;
  104.                     Search = FALSE;
  105.                 }
  106.  
  107.             if (Search)
  108.             {
  109.                 // last item was not given: find last item
  110.                 PLISTITEM pItem = (PLISTITEM)*ppFirst;
  111.                 while (pItem->pNext)
  112.                     pItem = pItem->pNext;
  113.                 pItem->pNext = pNewItem;
  114.                 pNewItem->pPrevious = pItem;
  115.             }
  116.         }
  117.         if (ppLast)
  118.             *ppLast = pNewItem;
  119.     }
  120.  
  121.     return (pNewItem);
  122. }
  123.  
  124. /*
  125.  *@@ lstInsertItemAt:
  126.  *      does just the same, but does not append the new item
  127.  *      at the end of the list, but BEFORE the specified index
  128.  *      lIndex. If lIndex is larger than the number of items
  129.  *      on the list or == -1, the new item will be appended.
  130.  */
  131.  
  132. PLISTITEM lstInsertItemAt(PLISTITEM *ppFirst, PLISTITEM *ppLast,
  133.             PLISTITEM pNewItem, long lIndex)
  134. {
  135.     if (pNewItem)
  136.     {
  137.         if (lIndex == -1)
  138.             lstAppendItem(ppFirst, ppLast, pNewItem);
  139.         else
  140.         {
  141.             if (lIndex == 0) {
  142.                 // insert at beginning:
  143.                 pNewItem->pNext = (*ppFirst);
  144.                 pNewItem->pPrevious = NULL;
  145.                 (*ppFirst)->pPrevious = pNewItem;
  146.                 *ppFirst = pNewItem;
  147.             } else {
  148.                 // insert at a later position:
  149.                 PLISTITEM pItemInsertAfter = lstItemFromIndex(
  150.                                 *ppFirst, (lIndex-1));
  151.  
  152.                 if (pItemInsertAfter) {
  153.                     pNewItem->pNext = pItemInsertAfter->pNext;
  154.                     pItemInsertAfter->pNext = pNewItem;
  155.                     pNewItem->pPrevious = pItemInsertAfter;
  156.                     if (pNewItem->pNext)
  157.                         pNewItem->pNext->pPrevious = pNewItem;
  158.                 } else {
  159.                     // item index too large: append instead
  160.                     lstAppendItem(ppFirst, ppLast, pNewItem);
  161.                 }
  162.             }
  163.         }
  164.         return (pNewItem);
  165.     } else
  166.         return (NULL);
  167. }
  168.  
  169. /*
  170.  *@@ lstRemoveItem:
  171.  *      reversely, this will remove a given pRemoveItem from
  172.  *      the linked list beginning at *ppFirst. Returns TRUE if
  173.  *      successful, FALSE if pRemoveItem was not found.
  174.  */
  175.  
  176. BOOL lstRemoveItem(PLISTITEM *ppFirst, PLISTITEM *ppLast, PLISTITEM pRemoveItem)
  177. {
  178.     BOOL        Found = FALSE;
  179.  
  180.     if (ppFirst) {
  181.         if ((*ppFirst) && (pRemoveItem))
  182.         {
  183.             if (*ppFirst == pRemoveItem) {
  184.                 // pRemoveItem is the first item on the list:
  185.                 // set *ppFirst to the second item on the list.
  186.                 // This also works if pRemoveItem is the only item */
  187.                 *ppFirst = pRemoveItem->pNext;
  188.                 if (*ppFirst)
  189.                     (*ppFirst)->pPrevious = NULL;
  190.                 Found = TRUE;
  191.             }
  192.             else {
  193.                 // otherwise begin searching list:
  194.                 PLISTITEM pLastItem = *ppFirst;
  195.                 PLISTITEM pItem = pLastItem->pNext;
  196.  
  197.                 while (pItem)
  198.                 {
  199.                     if (pItem == pRemoveItem) {
  200.                         // item found: set pNext of previous item to next item
  201.                         // (i.e. leave out pRemoveItem) */
  202.                         pLastItem->pNext = pRemoveItem->pNext;
  203.                         if (pRemoveItem->pNext)
  204.                             pRemoveItem->pNext->pPrevious = pLastItem;
  205.                         Found = TRUE;
  206.                         break;
  207.                     }
  208.                     else {
  209.                         pLastItem = pItem;
  210.                         pItem = pItem->pNext;
  211.                     }
  212.                 }
  213.             }
  214.         }
  215.         if (Found) {
  216.             if (ppLast)
  217.                 /* if (*ppLast == pRemoveItem)
  218.                     *ppLast = pRemoveItem->pPrevious;*/
  219.                 *ppLast = NULL;
  220.  
  221.             free(pRemoveItem);
  222.         }
  223.     }
  224.  
  225.     return (Found);
  226. }
  227.  
  228. /*
  229.  *@@ lstSwapItems:
  230.  *      this will swap the items ppItem1 and ppItem2 in the linked
  231.  *      list starting at *ppFirst; useful for sorting.
  232.  *      Note that this function will not only adjust the pNext
  233.  *      and pPrevious pointers of the LISTITEMs, but also
  234.  *      swap the *ppItem1 and *ppItem2 pointers.
  235.  */
  236.  
  237. BOOL lstSwapItems(PLISTITEM *ppFirst, PLISTITEM *ppLast,
  238.             PLISTITEM *ppItem1, PLISTITEM *ppItem2)
  239. {
  240.     BOOL brc = FALSE;
  241.     // PLISTITEM   pPrevious = NULL;
  242.  
  243.     if ( (ppFirst) && (ppItem1) && (ppItem2) )
  244.         if ((*ppFirst) && ((*ppItem1)) && ((*ppItem2)))
  245.             if (*ppItem1 != *ppItem2)
  246.             {
  247.                 PLISTITEM pBefore1 = (*ppItem1)->pPrevious,
  248.                           pAfter1 = (*ppItem1)->pNext,
  249.                           pBefore2 = (*ppItem2)->pPrevious,
  250.                           pAfter2 = (*ppItem2)->pNext,
  251.                           pItemTemp;
  252.  
  253.                 if ((*ppItem1)->pNext == (*ppItem2)) {
  254.                     (*ppItem1)->pNext = pAfter2;
  255.                     if (pAfter2)
  256.                         pAfter2->pPrevious = (*ppItem1);
  257.  
  258.                     (*ppItem2)->pNext = (*ppItem1);
  259.                     (*ppItem1)->pPrevious = (*ppItem2);
  260.  
  261.                     if (pBefore1) {
  262.                         pBefore1->pNext = (*ppItem2);
  263.                         (*ppItem2)->pPrevious = pBefore1;
  264.                     } else {
  265.                         *ppFirst = (*ppItem2);
  266.                         (*ppItem2)->pPrevious = NULL;
  267.                     }
  268.                 } else {
  269.                     if (pBefore1) {
  270.                         pBefore1->pNext = (*ppItem2);
  271.                         (*ppItem2)->pPrevious = pBefore1;
  272.                     } else {
  273.                         *ppFirst = (*ppItem2);
  274.                         (*ppItem2)->pPrevious = NULL;
  275.                     }
  276.                     (*ppItem2)->pNext = pAfter1;
  277.                     if (pAfter1)
  278.                         pAfter1->pPrevious = (*ppItem2);
  279.  
  280.                     if (pBefore2) {
  281.                         pBefore2->pNext = (*ppItem1);
  282.                         (*ppItem1)->pPrevious = pBefore2;
  283.                     } else {
  284.                         *ppFirst = (*ppItem1);
  285.                         (*ppItem1)->pPrevious = NULL;
  286.                     }
  287.                     (*ppItem1)->pNext = pAfter2;
  288.                     if (pAfter2)
  289.                         pAfter2->pPrevious = (*ppItem1);
  290.                 }
  291.  
  292.                 // now swap the pointers also
  293.                 pItemTemp = *ppItem1;
  294.                 *ppItem1 = *ppItem2;
  295.                 *ppItem2 = pItemTemp;
  296.  
  297.                 if (ppLast)
  298.                     *ppLast = NULL;
  299.             }
  300.  
  301.     return (brc);
  302. }
  303.  
  304. /*
  305.  *@@ lstQuickSort2:
  306.  *      helper routine for recursive quicksort (below)
  307.  */
  308.  
  309. void lstQuickSort2(PLISTITEM *ppFirst, PLISTITEM *ppLast, PFNSORTLIST pfnSort, void* pStorage,
  310.             long lLeft, long lRight)
  311. {
  312.     long ll = lLeft, lr = lRight-1,
  313.          lPivot = lRight;
  314.  
  315.     if (lRight > lLeft) {
  316.         PLISTITEM   pItemLeft = lstItemFromIndex(*ppFirst, ll),
  317.                     pItemRight = lstItemFromIndex(*ppFirst, lr),
  318.                     pItemPivot = lstItemFromIndex(*ppFirst, lPivot);
  319.  
  320.         while (TRUE) {
  321.             // compare left item to pivot
  322.             while ( (*pfnSort)(pItemLeft, pItemPivot, pStorage) < 0 )
  323.             {
  324.                 ll++;
  325.                 pItemLeft = pItemLeft->pNext;
  326.             }
  327.  
  328.             // compare right item to pivot
  329.             while (     ( (*pfnSort)(pItemRight, pItemPivot, pStorage) >= 0 )
  330.                     && (lr > ll)
  331.                   )
  332.             {
  333.                 lr--;
  334.                 pItemRight = pItemRight->pPrevious;
  335.             }
  336.  
  337.             if (lr <= ll)
  338.                 break;
  339.  
  340.             // swap pItemLeft and pItemRight
  341.             lstSwapItems(ppFirst, ppLast, &pItemLeft, &pItemRight);
  342.         }
  343.  
  344.         // swap pItemLeft and pItemPivot
  345.         lstSwapItems(ppFirst, ppLast, &pItemLeft, &pItemPivot);
  346.  
  347.         lstQuickSort2(ppFirst, ppLast, pfnSort, pStorage, lLeft, ll-1);
  348.         lstQuickSort2(ppFirst, ppLast, pfnSort, pStorage, ll+1, lRight);
  349.     }
  350. }
  351.  
  352. /*
  353.  *@@ lstQuickSort:
  354.  *      this will sort the list starting at *ppFirst using the
  355.  *      sort function pfnSort, which works similar to those of the
  356.  *      container sorts, i.e. it must be declared as a
  357.  *          SHORT fnSort(void* pItem1, void* pItem1, void* pStorage)
  358.  *      These sort functions need to return the following:
  359.  *          0   pItem1 == pItem2
  360.  *         -1   pItem1 <  pItem2
  361.  *         +1   pItem1 >  pItem2
  362.  *      This function uses the "quick sort" algorithm, which is one of
  363.  *      the fastest sort algorithms available. However, this is an
  364.  *      "instable" sort algorithm, meaning that list items considered
  365.  *      equal by pfnSort do _not_ retain their position, but might be
  366.  *      changed. If you need these to remain where they are, use
  367.  *      lstBubbleSort.
  368.  */
  369.  
  370. BOOL lstQuickSort(PLISTITEM *ppFirst, PLISTITEM *ppLast,
  371.             PFNSORTLIST pfnSort, void* pStorage)
  372. {
  373.     if ((pfnSort) && (ppFirst))
  374.     {
  375.         long lRight = lstCountItems(*ppFirst)-1;
  376.  
  377.         lstQuickSort2(ppFirst, ppLast, pfnSort, pStorage,
  378.                     0,          // lLeft
  379.                     lRight);
  380.     }
  381.  
  382.     return (TRUE);
  383. }
  384.  
  385. /*
  386.  *@@ lstBubbleSort:
  387.  *      this will sort the list starting at *ppFirst using the
  388.  *      sort function pfnSort, which works similar to those of the
  389.  *      container sorts, i.e. it must be declared as a
  390.  *          SHORT EXPENTRY fnSort(void* pItem1, void* pItem1, void* pStorage)
  391.  *      These sort functions need to return the following:
  392.  *          0   pItem1 == pItem2
  393.  *         -1   pItem1 <  pItem2
  394.  *         +1   pItem1 >  pItem2
  395.  *      This function uses the "bubble sort" algorithm, which will cause a
  396.  *      lot of calls to pfnSort and which is really ineffective for lists
  397.  *      with more than 100 items.
  398.  */
  399.  
  400. BOOL lstBubbleSort(PLISTITEM *ppFirst, PLISTITEM *ppLast,
  401.             PFNSORTLIST pfnSort, void* pStorage)
  402. {
  403.     if ((pfnSort) && (ppFirst))
  404.     {
  405.         long lRight = lstCountItems(*ppFirst),
  406.              lSorted, x;
  407.  
  408.         do {
  409.             lRight--;
  410.             lSorted = 0;
  411.             for (x = 0; x < lRight; x++) {
  412.                 // ulComp++;
  413.                 PLISTITEM pItem1 = lstItemFromIndex(*ppFirst, x),
  414.                           pItem2 = pItem1->pNext;
  415.                 if ((pItem1) && (pItem2))
  416.                     if ( (*pfnSort)(pItem1, pItem2, pStorage) > 0 )
  417.                     {
  418.                         lstSwapItems(ppFirst, ppLast, &pItem1, &pItem2);
  419.                         lSorted++;
  420.                     }
  421.             }
  422.         } while ( lSorted && (lRight > 1) );
  423.     }
  424.  
  425.     return (TRUE);
  426. }
  427.  
  428. /*
  429.  *@@ lstCountItems:
  430.  *      this will count the number of items from pFirst;
  431.  *      returns 0 if error occured.
  432.  */
  433.  
  434. unsigned long lstCountItems(PLISTITEM pFirst)
  435. {
  436.     unsigned long ulCount = 0;
  437.     PLISTITEM pItem = pFirst;
  438.  
  439.     while (pItem)
  440.     {
  441.         ulCount++;
  442.         pItem = pItem->pNext;
  443.     }
  444.  
  445.     return (ulCount);
  446. }
  447.  
  448. /*
  449.  *@@ lstItemFromIndex:
  450.  *      returns the list item with a given ulIndex
  451.  *      (counting from 0), or NULL if ulIndex is too large
  452.  */
  453.  
  454. PLISTITEM lstItemFromIndex(PLISTITEM pFirst, unsigned long ulIndex)
  455. {
  456.     unsigned long           ulCount = 0;
  457.     PLISTITEM pItem = NULL;
  458.  
  459.     if (pFirst) {
  460.         pItem = pFirst;
  461.         for (ulCount = 0; ((pItem) && (ulCount < ulIndex)); ulCount++)
  462.             if (pItem->pNext)
  463.                 pItem = pItem->pNext;
  464.             else
  465.                 pItem = NULL;
  466.     }
  467.  
  468.     return (pItem);
  469. }
  470.  
  471. /*
  472.  *@@ lstClear:
  473.  *      this will free the whole list starting
  474.  *      at *ppFirst and set *ppFirst/*ppLast to NULL
  475.  */
  476.  
  477. void lstClear(PLISTITEM *ppFirst, PLISTITEM *ppLast)
  478. {
  479.     PLISTITEM  pItem, pItem2;
  480.  
  481.     pItem = (PLISTITEM)*ppFirst;
  482.     while (pItem) {
  483.         pItem2 = pItem->pNext;
  484.         free(pItem);
  485.         pItem = pItem2;
  486.     }; // while (pItem);
  487.  
  488.     *ppFirst = NULL;
  489.     if (ppLast)
  490.         *ppLast = NULL;
  491.  
  492. }
  493.  
  494.  
  495.