home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / xwphescr.zip / XWPH0208.ZIP / src / helpers / linklist.c < prev    next >
C/C++ Source or Header  |  2002-07-26  |  32KB  |  1,121 lines
  1.  
  2. /*
  3.  *@@sourcefile linklist.c:
  4.  *      contains helper functions for maintaining doubly-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.  *      Usage: All C programs; not OS/2-specific.
  11.  *
  12.  *      Function prefixes (new with V0.81):
  13.  *      --  lst*    linked list helper functions
  14.  *
  15.  *      <B>Usage:</B>
  16.  *
  17.  *      Linked lists are implemented through the LINKLIST structure.
  18.  *      This can either be created on the stack or as a global variable
  19.  *      (and must then be initialized using lstInit) or from the heap
  20.  *      with lstCreate.
  21.  *
  22.  *      Each list item is stored in a LISTNODE structure, which in
  23.  *      turn has a pItemData field, which you can use to get your
  24.  *      data. So a typical list would be coded like this (this is
  25.  *      a heap list):
  26.  *
  27.  +
  28.  +          typedef struct _YOURDATA
  29.  +          {
  30.  +              ULONG ulWhatever;
  31.  +          } YOURDATA, *PYOURDATA
  32.  +
  33.  +          // fill the list
  34.  +          PLINKLIST pll = lstCreate(TRUE or FALSE);
  35.  +          while ...
  36.  +          {
  37.  +              PYOURDATA pYourData = (PYOURDATA)malloc(sizeof(YOURDATA));
  38.  +              lstAppendItem(pll, pYourData);  // store the data in a new node
  39.  +          }
  40.  +
  41.  +          ...
  42.  +
  43.  +          // now iterate over the list
  44.  +          PLISTNODE pNode = lstQueryFirstNode(pll);
  45.  +          while (pNode)
  46.  +          {
  47.  +              PYOURDATA pYourData = (PYOURDATA)pNode->pItemData;
  48.  +              ...
  49.  +              pNode = pNode->pNext;
  50.  +          }
  51.  +
  52.  +          lstFree(pll);   // this is free the list items too, if TRUE had
  53.  +                          // been specified with lstCreate
  54.  *
  55.  *      If __XWPMEMDEBUG__ is defined, the lstCreate and lstAppendItem funcs will
  56.  *      automatically be replaced with lstCreateDebug and lstAppendItemDebug,
  57.  *      and mapper macros are defined in linklist.h.
  58.  *
  59.  *      Note: If you frequently need to search your data structures,
  60.  *      you might prefer the new balanced binary trees in tree.c which
  61.  *      have been added with V0.9.5.
  62.  *
  63.  *      Note: Version numbering in this file relates to XWorkplace version
  64.  *            numbering.
  65.  *
  66.  *@@header "helpers\linklist.h"
  67.  */
  68.  
  69. /*
  70.  *      Copyright (C) 1997-2001 Ulrich Möller.
  71.  *      This file is part of the "XWorkplace helpers" source package.
  72.  *      This is free software; you can redistribute it and/or modify
  73.  *      it under the terms of the GNU General Public License as published
  74.  *      by the Free Software Foundation, in version 2 as it comes in the
  75.  *      "COPYING" file of the XWorkplace main distribution.
  76.  *      This program is distributed in the hope that it will be useful,
  77.  *      but WITHOUT ANY WARRANTY; without even the implied warranty of
  78.  *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  79.  *      GNU General Public License for more details.
  80.  */
  81.  
  82. #include <stdlib.h>
  83. #include <string.h>
  84.  
  85. #include "setup.h"                      // code generation and debugging options
  86.  
  87. #define DONT_REPLACE_LIST_MALLOC
  88. #include "helpers\linklist.h"
  89.  
  90. #pragma hdrstop
  91.  
  92. /*
  93.  *@@category: Helpers\C helpers\Linked lists
  94.  *      See linklist.c.
  95.  */
  96.  
  97. /* ******************************************************************
  98.  *
  99.  *   List base functions
  100.  *
  101.  ********************************************************************/
  102.  
  103. /*
  104.  *@@ lstMalloc:
  105.  *      wrapper around malloc() to make sure memory is
  106.  *      allocated from the C runtime the helpers were
  107.  *      compiled with. This is useful for auto-free
  108.  *      lists.
  109.  *
  110.  *@@added V0.9.7 (2000-12-07) [umoeller]
  111.  */
  112.  
  113. void* lstMalloc(size_t size)
  114. {
  115.     return (malloc(size));
  116. }
  117.  
  118. /*
  119.  *@@ lstStrDup:
  120.  *      wrapper around strdup() to make sure memory is
  121.  *      allocated from the C runtime the helpers were
  122.  *      compiled with. This is useful for auto-free
  123.  *      lists.
  124.  *
  125.  *@@added V0.9.7 (2000-12-07) [umoeller]
  126.  */
  127.  
  128. void* lstStrDup(const char *pcsz)
  129. {
  130.     return (strdup(pcsz));
  131. }
  132.  
  133. /*
  134.  *@@ lstInit:
  135.  *      this initializes a given LINKLIST structure.
  136.  *
  137.  *      This is useful only if you have a static
  138.  *      LINKLIST structure in your sources (either as
  139.  *      a global variable or as a stack variable) and
  140.  *      don't use lstCreate/lstFree to have lists created
  141.  *      from the heap.
  142.  *
  143.  *      In that case, use this function as follows:
  144.  +
  145.  +          LINKLIST llWhatever;
  146.  +          lstInit(&llWhatever);
  147.  +          ...
  148.  +          lstClear(&llWhatever);
  149.  *
  150.  *      The list which is initialized here must be
  151.  *      cleaned up using lstClear.
  152.  *
  153.  *      If (fItemsFreeable == TRUE), free() will be
  154.  *      invoked on list items automatically in lstClear,
  155.  *      lstRemoveNode, and lstRemoveItem.
  156.  *
  157.  *      --  Set this to TRUE if you have created the
  158.  *          list items yourself using malloc().
  159.  *
  160.  *          This of course will be a "flat" free(). If
  161.  *          you store structures in the list using other
  162.  *          heap pointers, auto-free would cause memory leaks.
  163.  *
  164.  *          Also, auto-free only works if the malloc() that
  165.  *          has been used on the list item is in the same C
  166.  *          runtime as with the linklist functions. If the
  167.  *          caller uses a different runtime (e.g. from a DLL),
  168.  *          it  can use lstMalloc() for allocating the list
  169.  *          item and still use auto-free.
  170.  *
  171.  *      --  Set this to FALSE if you're storing other
  172.  *          objects, such as numbers or other static items.
  173.  *
  174.  *      Note: You better call lstInit only once per list,
  175.  *      because we don't check here if the list
  176.  *      contains any data. This will lead to memory
  177.  *      leaks if called upon existing lists, because
  178.  *      we'll lose track of the allocated items.
  179.  */
  180.  
  181. void lstInit(PLINKLIST pList,
  182.              BOOL fItemsFreeable)   // in: invoke free() on the data
  183.                                     // item pointers upon destruction?
  184. {
  185.     if (pList)
  186.     {
  187.         memset(pList, 0, sizeof(LINKLIST));
  188.         pList->ulMagic = LINKLISTMAGIC;      // set integrity check word
  189.         pList->fItemsFreeable = fItemsFreeable;
  190.     }
  191. }
  192.  
  193. /*
  194.  *@@ lstClear:
  195.  *      this will delete all list items. As opposed to
  196.  *      lstFree, the "root" of the list will not be
  197.  *      freed so that items can be added later again.
  198.  *
  199.  *      This can be used on static lists initialized with
  200.  *      lstInit also.
  201.  *
  202.  *      If fItemsFreeable had been specified as TRUE
  203.  *      when the list was initialized (lstInit), free()
  204.  *      will be invoked on all data item pointers also.
  205.  *      See the remarks for lstInit.
  206.  *
  207.  *      Returns FALSE only upon errors, e.g. because
  208.  *      integrity checks failed.
  209.  */
  210.  
  211. BOOL lstClear(PLINKLIST pList)
  212. {
  213.     BOOL brc = FALSE;
  214.  
  215.     if (pList)
  216.         if (pList->ulMagic == LINKLISTMAGIC)
  217.         {
  218.             PLISTNODE  pNode = pList->pFirst,
  219.                        pNode2;
  220.  
  221.             while (pNode)
  222.             {
  223.                 if (pList->fItemsFreeable)
  224.                     if (pNode->pItemData)
  225.                         free(pNode->pItemData);
  226.                 pNode2 = pNode->pNext;
  227.                 free(pNode);
  228.                 pNode = pNode2;
  229.             } // while (pNode);
  230.  
  231.             lstInit(pList, pList->fItemsFreeable);
  232.             brc = TRUE;
  233.         }
  234.  
  235.     return brc;
  236. }
  237.  
  238. #ifdef __DEBUG_MALLOC_ENABLED__
  239.  
  240. /*
  241.  *@@ lstCreateDebug:
  242.  *      debug version of lstCreate, using _debug_malloc.
  243.  *
  244.  *      Calls to lstCreate are automatically mapped to
  245.  *      this function if __XWPMEMDEBUG__ is defined.
  246.  *      This makes sure that the source file and line stored
  247.  *      with the debug memory functions will be that of the
  248.  *      caller, not the ones in this file.
  249.  *
  250.  *@@added V0.9.1 (99-12-18) [umoeller]
  251.  */
  252.  
  253. PLINKLIST lstCreateDebug(BOOL fItemsFreeable,
  254.                          const char *file,
  255.                          unsigned long line,
  256.                          const char *function)
  257. {
  258.     PLINKLIST pNewList = (PLINKLIST)memdMalloc(sizeof(LINKLIST),
  259.                                                file,
  260.                                                line,
  261.                                                function);
  262.  
  263.     lstInit(pNewList, fItemsFreeable);
  264.     return (pNewList);
  265. }
  266.  
  267. #endif
  268.  
  269. // #else       // __DEBUG_MALLOC_ENABLED__
  270.  
  271. /*
  272.  *@@ lstCreate:
  273.  *      this creates a new linked list and initializes it
  274.  *      (using lstInit).
  275.  *      The LINKLIST structure which defines the "root" of
  276.  *      the list is returned. This must be passed to all
  277.  *      other list functions.
  278.  *
  279.  *      The list which is created here must be destroyed
  280.  *      using lstFree.
  281.  *
  282.  *      See lstInit for the description of fItemsFreeable.
  283.  *
  284.  *      Returns NULL upon errors.
  285.  *
  286.  *      <B>Usage:</B>
  287.  +          PLINKLIST pllWhatever = lstCreate();
  288.  +          ...
  289.  +          lstFree(pllWhatever);
  290.  */
  291.  
  292. PLINKLIST lstCreate(BOOL fItemsFreeable)    // in: invoke free() on the data
  293.                                             // item pointers upon destruction?
  294. {
  295.     PLINKLIST pNewList;
  296.     if (pNewList = (PLINKLIST)malloc(sizeof(LINKLIST)))
  297.         lstInit(pNewList, fItemsFreeable);
  298.     return (pNewList);
  299. }
  300.  
  301. // #endif      // __DEBUG_MALLOC_ENABLED__
  302.  
  303. /*
  304.  *@@ lstFree:
  305.  *      this will delete all list items (by calling
  306.  *      lstClear) and the list "root" itself.
  307.  *      Returns TRUE if anything was deleted at all
  308.  *      (even if the list was empty)
  309.  *      or FALSE upon errors, e.g. because integrity
  310.  *      checks failed.
  311.  *
  312.  *      If fItemsFreeable had been specified as TRUE
  313.  *      when the list was created (lstCreate), free()
  314.  *      will be invoked on all data item pointers also.
  315.  *      See the remarks for lstInit.
  316.  *
  317.  *      This must only be used with heap lists created
  318.  *      with lstCreate.
  319.  *
  320.  *      This uses a pointer to a PLINKLIST so that
  321.  *      the pointer is automatically reset to NULL
  322.  *      by this function AND to avoid confusion
  323.  *      with lstClear.
  324.  *
  325.  *@@changed V0.9.12 (2001-05-24) [umoeller]: changed prototype to use pointer to pointer
  326.  */
  327.  
  328. BOOL lstFree(PLINKLIST *ppList)
  329. {
  330.     BOOL brc = FALSE;
  331.     PLINKLIST p;
  332.  
  333.     if (    (ppList)
  334.          && (p = *ppList)
  335.        )
  336.         if (lstClear(p))        // this checks for list integrity
  337.         {
  338.             // unset magic word; the pList pointer
  339.             // will point to invalid memory after
  340.             // freeing the list, and subsequent
  341.             // integrity checks must fail
  342.             p->ulMagic = 0;
  343.             free(p);
  344.  
  345.             *ppList = NULL;
  346.  
  347.             brc = TRUE;
  348.         }
  349.  
  350.     return brc;
  351. }
  352.  
  353. /*
  354.  *@@ lstCountItems:
  355.  *      this will return the number of items
  356.  *      in the given linked list.
  357.  *      This returns 0 if the list is empty
  358.  *      or -1 if the list is invalid or corrupt.
  359.  */
  360.  
  361. long lstCountItems(const LINKLIST *pList)
  362. {
  363.     long lCount = -1;
  364.  
  365.     if (pList)
  366.         if (pList->ulMagic == LINKLISTMAGIC)
  367.         {
  368.             lCount = pList->ulCount;
  369.         }
  370.  
  371.     return (lCount);
  372. }
  373.  
  374. /*
  375.  *@@ lstQueryFirstNode:
  376.  *      this returns the first node of the list,
  377.  *      or NULL if the list is empty. This is
  378.  *      preferred over getting the first directly
  379.  *      from the LINKLIST structure, because this
  380.  *      one checks for data integrity.
  381.  *
  382.  *      The item data can be queried from the node
  383.  *      as follows:
  384.  *
  385.  +          PLINKLIST pll = lstCreate();
  386.  +          ...  // add items here
  387.  +          PLISTNODE pNode = lstQueryFirstNode(pll);
  388.  +          PYOURDATA pData = pNode->pItemData;
  389.  *
  390.  *      You can iterate over the whole list like this:
  391.  *
  392.  +          PLISTNODE pNode = lstQueryFirstNode(pll);
  393.  +          while (pNode)
  394.  +          {
  395.  +              PYOURDATA pYourData = (PYOURDATA)pNode->pItemData;
  396.  +              ...
  397.  +              pNode = pNode->pNext;
  398.  +          }
  399.  */
  400.  
  401. PLISTNODE lstQueryFirstNode(const LINKLIST *pList)
  402. {
  403.     if (    (pList)
  404.          && (pList->ulMagic == LINKLISTMAGIC)
  405.        )
  406.         return (pList->pFirst);
  407.  
  408.     return (0);
  409. }
  410.  
  411. /*
  412.  *@@ lstQueryLastNode:
  413.  *      similar to lstQueryFirstNode, but this returns
  414.  *      the last node.
  415.  *
  416.  *@@added V0.9.9 (2001-02-14) [umoeller]
  417.  */
  418.  
  419. PLISTNODE lstQueryLastNode(const LINKLIST *pList)
  420. {
  421.     if (    (pList)
  422.          && (pList->ulMagic == LINKLISTMAGIC)
  423.        )
  424.         return (pList->pLast);
  425.  
  426.     return (0);
  427. }
  428.  
  429. /*
  430.  *@@ lstNodeFromIndex:
  431.  *      returns the data of list item with a given ulIndex
  432.  *      (counting from 0), or NULL if ulIndex is too large.
  433.  *
  434.  *      This traverses the whole list, so it's not terribly
  435.  *      fast. See lstQueryFirstNode for how to traverse
  436.  *      the list yourself.
  437.  *
  438.  *      Note: As opposed to lstItemFromIndex, this one
  439.  *      returns the LISTNODE structure.
  440.  */
  441.  
  442. PLISTNODE lstNodeFromIndex(PLINKLIST pList,
  443.                            unsigned long ulIndex)
  444. {
  445.     PLISTNODE pNode = NULL;
  446.  
  447.     if (    (pList)
  448.          && (pList->ulMagic == LINKLISTMAGIC)
  449.          && (pList->pFirst)
  450.        )
  451.     {
  452.         unsigned long ulCount = 0;
  453.         pNode = pList->pFirst;
  454.         for (ulCount = 0;
  455.              ((pNode) && (ulCount < ulIndex));
  456.              ulCount++)
  457.         {
  458.             if (pNode->pNext)
  459.                 pNode = pNode->pNext;
  460.             else
  461.                 pNode = NULL; // exit
  462.         }
  463.     }
  464.  
  465.     return (pNode);
  466. }
  467.  
  468. /*
  469.  *@@ lstNodeFromItem:
  470.  *      this finds the list node which has the given
  471.  *      data pointer or NULL if not found.
  472.  *
  473.  *      This traverses the whole list, so it's not terribly
  474.  *      fast. See lstQueryFirstNode for how to traverse
  475.  *      the list yourself.
  476.  */
  477.  
  478. PLISTNODE lstNodeFromItem(PLINKLIST pList,
  479.                           void* pItemData)
  480. {
  481.     PLISTNODE pNode = 0,
  482.               pNodeFound = 0;
  483.  
  484.     if (    (pList)
  485.          && (pList->ulMagic == LINKLISTMAGIC)
  486.          && (pItemData)
  487.        )
  488.     {
  489.         pNode = pList->pFirst;
  490.         while (pNode)
  491.         {
  492.             if (pNode->pItemData == pItemData)
  493.             {
  494.                 pNodeFound = pNode;
  495.                 break;
  496.             }
  497.  
  498.             pNode = pNode->pNext;
  499.         }
  500.     }
  501.  
  502.     return (pNodeFound);
  503. }
  504.  
  505. /*
  506.  *@@ lstItemFromIndex:
  507.  *      returns the data of the list item with a given ulIndex
  508.  *      (counting from 0), or NULL if ulIndex is too large.
  509.  *
  510.  *      This traverses the whole list, so it's not terribly
  511.  *      fast. See lstQueryFirstNode for how to traverse
  512.  *      the list yourself.
  513.  *
  514.  *      Note: As opposed to lstNodeFromIndex, this one
  515.  *      returns the item data directly, not the LISTNODE
  516.  *      structure.
  517.  */
  518.  
  519. void* lstItemFromIndex(PLINKLIST pList,
  520.                        unsigned long ulIndex)
  521. {
  522.     PLISTNODE pNode;
  523.     if (pNode = lstNodeFromIndex(pList, ulIndex))
  524.         return (pNode->pItemData);
  525.     else
  526.         return (0);
  527. }
  528.  
  529. /*
  530.  *@@ lstIndexFromItem:
  531.  *      returns the index of the list node with
  532.  *      the specified item pointer. The first
  533.  *      node returns 0, the second 1, and so on.
  534.  *
  535.  *      Returns -1 if not found.
  536.  *
  537.  *      In the worst case, this function traverses
  538.  *      the whole list.
  539.  *
  540.  *@@added V0.9.7 (2000-12-13) [umoeller]
  541.  */
  542.  
  543. unsigned long lstIndexFromItem(PLINKLIST pList, void *pItemData)
  544. {
  545.     ULONG ulrc = -1,
  546.           ulIndex = 0;
  547.     PLISTNODE pNode = lstQueryFirstNode(pList);
  548.     while (pNode)
  549.     {
  550.         if (pNode->pItemData == pItemData)
  551.         {
  552.             ulrc = ulIndex;
  553.             break;
  554.         }
  555.  
  556.         pNode = pNode->pNext;
  557.         ulIndex++;
  558.     }
  559.  
  560.     return (ulrc);
  561. }
  562.  
  563. #ifdef __DEBUG_MALLOC_ENABLED__
  564.  
  565. /*
  566.  *@@ lstAppendItemDebug:
  567.  *      debug version of lstAppendItem, using _debug_malloc.
  568.  *
  569.  *      Calls to lstAppendItem are automatically mapped to
  570.  *      this function if __XWPMEMDEBUG__ is defined.
  571.  *      This makes sure that the source file and line stored
  572.  *      with the debug memory functions will be that of the
  573.  *      caller, not the ones in this file.
  574.  *
  575.  *@@added V0.9.1 (99-12-18) [umoeller]
  576.  */
  577.  
  578. PLISTNODE lstAppendItemDebug(PLINKLIST pList,
  579.                              void* pNewItemData,     // in: data to store in list node
  580.                              const char *file,
  581.                              unsigned long line,
  582.                              const char *function)
  583. {
  584.     PLISTNODE pNewNode = NULL;
  585.  
  586.     if (    (pList)
  587.          && (pList->ulMagic == LINKLISTMAGIC)
  588.          && (pNewNode = (PLISTNODE)memdMalloc(sizeof(LISTNODE), file, line, function))
  589.        )
  590.     {
  591.         memset(pNewNode, 0, sizeof(LISTNODE));
  592.         pNewNode->pItemData = pNewItemData;
  593.  
  594.         if (pList->pLast)
  595.         {
  596.             // list is not empty: append to tail
  597.  
  598.             // 1) make last item point to new node
  599.             pList->pLast->pNext = pNewNode;
  600.             // 2) make new node point to last item
  601.             pNewNode->pPrevious = pList->pLast;
  602.             // 3) store new node as new last item
  603.             pList->pLast = pNewNode;
  604.  
  605.             pList->ulCount++;
  606.         }
  607.         else
  608.         {
  609.             // list is empty: insert as first
  610.             pList->pFirst
  611.                 = pList->pLast
  612.                 = pNewNode;
  613.  
  614.             pList->ulCount = 1;
  615.         }
  616.     }
  617.  
  618.     return (pNewNode);
  619. }
  620.  
  621. #endif
  622.  
  623. // #else  // __DEBUG_MALLOC_ENABLED__
  624.  
  625. /*
  626.  *@@ lstAppendItem:
  627.  *      this adds a new node to the tail of the list.
  628.  *      As opposed to lstInsertItemBefore, this is very
  629.  *      fast, since the list always keeps track of its last item.
  630.  *
  631.  *      This returns the LISTNODE of the new list item,
  632.  *      or NULL upon errors.
  633.  */
  634.  
  635. PLISTNODE lstAppendItem(PLINKLIST pList,
  636.                         void* pNewItemData)     // in: data to store in list node
  637. {
  638.     PLISTNODE pNewNode = NULL;
  639.  
  640.     if (    (pList)
  641.          && (pList->ulMagic == LINKLISTMAGIC)
  642.          && (pNewNode = (PLISTNODE)malloc(sizeof(LISTNODE)))
  643.        )
  644.     {
  645.         memset(pNewNode, 0, sizeof(LISTNODE));
  646.         pNewNode->pItemData = pNewItemData;
  647.  
  648.         if (pList->pLast)
  649.         {
  650.             // list is not empty: append to tail
  651.  
  652.             // 1) make last item point to new node
  653.             pList->pLast->pNext = pNewNode;
  654.             // 2) make new node point to last item
  655.             pNewNode->pPrevious = pList->pLast;
  656.             // 3) store new node as new last item
  657.             pList->pLast = pNewNode;
  658.  
  659.             pList->ulCount++;
  660.         }
  661.         else
  662.         {
  663.             // list is empty: insert as first
  664.             pList->pFirst
  665.                 = pList->pLast
  666.                 = pNewNode;
  667.  
  668.             pList->ulCount = 1;
  669.         }
  670.     }
  671.  
  672.     return (pNewNode);
  673. }
  674.  
  675. // #endif // __DEBUG_MALLOC_ENABLED__
  676.  
  677. /*
  678.  *@@ lstInsertItemBefore:
  679.  *      this inserts a new node to the list. As opposed to
  680.  *      lstAppendItem, the new node can be appended anywhere
  681.  *      in the list, that is, it will be appended BEFORE
  682.  *      the specified index lIndex.
  683.  *
  684.  *      So if ulIndex == 0, the new item will be made the first
  685.  *      item.
  686.  *
  687.  *      If ulIndex is larger than the item count on the list,
  688.  *      the new node will be appended at the tail of the list
  689.  *      (as with lstAppendItem).
  690.  *
  691.  *      This needs to traverse the list to find the indexed
  692.  *      item, so for larger ulIndex's this function is not
  693.  *      terribly fast.
  694.  *
  695.  *      This returns the LISTNODE of the new list item,
  696.  *      or NULL upon errors.
  697.  *
  698.  *@@changed V0.9.14 (2001-07-14) [umoeller]: this never worked on empty lists, fixed
  699.  */
  700.  
  701. PLISTNODE lstInsertItemBefore(PLINKLIST pList,
  702.                               void* pNewItemData,     // data to store in list node
  703.                               unsigned long ulIndex)
  704. {
  705.     PLISTNODE pNewNode = NULL;
  706.  
  707.     if (    (pList)
  708.          && (pList->ulMagic == LINKLISTMAGIC)
  709.          && (pNewNode = (PLISTNODE)malloc(sizeof(LISTNODE)))
  710.        )
  711.     {
  712.         memset(pNewNode, 0, sizeof(LISTNODE));
  713.         pNewNode->pItemData = pNewItemData;
  714.  
  715.         if (ulIndex == 0)
  716.         {
  717.             // insert at beginning:
  718.             if (pList->pFirst)
  719.                 pList->pFirst->pPrevious = pNewNode;
  720.  
  721.             pNewNode->pNext = pList->pFirst;
  722.             pNewNode->pPrevious = NULL;
  723.  
  724.             pList->pFirst = pNewNode;
  725.  
  726.             if (!pList->pLast)
  727.                 // the list was empty:
  728.                 pList->pLast = pNewNode;        // V0.9.14 (2001-07-14) [umoeller]
  729.  
  730.             (pList->ulCount)++;
  731.         }
  732.         else
  733.         {
  734.             // insert at a later position:
  735.             PLISTNODE pNodeInsertAfter = lstNodeFromIndex(
  736.                                     pList,
  737.                                     (ulIndex-1));
  738.  
  739.             if (pNodeInsertAfter)
  740.             {
  741.                 // 1) set pointers for new node
  742.                 pNewNode->pPrevious = pNodeInsertAfter;
  743.                 pNewNode->pNext = pNodeInsertAfter->pNext;
  744.  
  745.                 // 2) adjust next item
  746.                 // so that it points to the new node
  747.                 if (pNodeInsertAfter->pNext)
  748.                     pNodeInsertAfter->pNext->pPrevious = pNewNode;
  749.  
  750.                 // 3) adjust previous item
  751.                 // so that it points to the new node
  752.                 pNodeInsertAfter->pNext = pNewNode;
  753.  
  754.                 // 4) adjust last item, if necessary
  755.                 if (pList->pLast == pNodeInsertAfter)
  756.                     pList->pLast = pNewNode;
  757.  
  758.                 (pList->ulCount)++;
  759.             }
  760.             else
  761.             {
  762.                 // item index too large: append instead
  763.                 free(pNewNode);
  764.                 pNewNode = lstAppendItem(pList, pNewItemData);
  765.             }
  766.         }
  767.     }
  768.  
  769.     return (pNewNode);
  770. }
  771.  
  772. /*
  773.  *@@ lstRemoveNode:
  774.  *      this will remove a given pRemoveNode from
  775.  *      the given linked list.
  776.  *
  777.  *      To remove a node according to the item pointer,
  778.  *      use lstRemoveItem.
  779.  *      To get the node from a node index, use
  780.  *      lstNodeFromIndex.
  781.  *
  782.  *      Since the LISTNODE is known, this function
  783.  *      operates very fast.
  784.  *
  785.  *      If fItemsFreeable had been specified as TRUE
  786.  *      when the list was created (lstInit or lstCreate),
  787.  *      free() will be invoked on the data item pointer also.
  788.  *      See the remarks there.
  789.  *
  790.  *      Returns TRUE if successful, FALSE upon errors.
  791.  */
  792.  
  793. BOOL lstRemoveNode(PLINKLIST pList,
  794.                    PLISTNODE pRemoveNode)
  795. {
  796.     BOOL fFound = FALSE;
  797.  
  798.     if (    (pList)
  799.          && (pList->ulMagic == LINKLISTMAGIC)
  800.          && (pRemoveNode)
  801.        )
  802.     {
  803.         if (pList->pFirst == pRemoveNode)
  804.             // item to be removed is first: adjust first
  805.             pList->pFirst = pRemoveNode->pNext;     // can be NULL
  806.  
  807.         if (pList->pLast == pRemoveNode)
  808.             // item to be removed is last: adjust last
  809.             pList->pLast = pRemoveNode->pPrevious;  // can be NULL
  810.  
  811.         if (pRemoveNode->pPrevious)
  812.             // adjust previous item
  813.             pRemoveNode->pPrevious->pNext = pRemoveNode->pNext;
  814.  
  815.         if (pRemoveNode->pNext)
  816.             // adjust next item
  817.             pRemoveNode->pNext->pPrevious = pRemoveNode->pPrevious;
  818.  
  819.         // decrease list count
  820.         pList->ulCount--;
  821.  
  822.         // free node data
  823.         if (pList->fItemsFreeable)
  824.             if (pRemoveNode->pItemData)
  825.                 free(pRemoveNode->pItemData);
  826.         // free node
  827.         free(pRemoveNode);
  828.  
  829.         fFound = TRUE;
  830.     }
  831.  
  832.     return (fFound);
  833. }
  834.  
  835. /*
  836.  *@@ lstRemoveItem:
  837.  *      as opposed to lstRemoveNode, this removes a
  838.  *      node according to an item data pointer.
  839.  *
  840.  *      This needs to call lstNodeFromItem first and
  841.  *      then invokes lstRemoveNode, so this is a lot
  842.  *      slower.
  843.  *
  844.  *      If fItemsFreeable had been specified as TRUE
  845.  *      when the list was created (lstInit or lstCreate),
  846.  *      free() will be invoked on the data item pointer also.
  847.  *      See the remarks there.
  848.  *
  849.  *      Returns TRUE if successful, FALSE upon errors.
  850.  */
  851.  
  852. BOOL lstRemoveItem(PLINKLIST pList, void* pRemoveItem)
  853. {
  854.     PLISTNODE pNode;
  855.  
  856.     if (pNode = lstNodeFromItem(pList, pRemoveItem))
  857.         return (lstRemoveNode(pList, pNode));
  858.  
  859.     return (FALSE);
  860. }
  861.  
  862. /*
  863.  *@@ lstSwapItems:
  864.  *      this will swap the items pNode1 and pNode2.
  865.  *      This is used in the sort routines.
  866.  *
  867.  *      Note that it is not really the nodes that are swapped,
  868.  *      but only the data item pointers. This is a lot quicker
  869.  *      than what we did in versions < 0.9.0.
  870.  */
  871.  
  872. BOOL lstSwapNodes(PLISTNODE pNode1,
  873.                   PLISTNODE pNode2)
  874. {
  875.     if ( (pNode1) && (pNode2) )
  876.     {
  877.         void* pTemp = pNode1->pItemData;
  878.         pNode1->pItemData = pNode2->pItemData;
  879.         pNode2->pItemData = pTemp;
  880.  
  881.         return (TRUE);
  882.     }
  883.  
  884.     return (FALSE);
  885. }
  886.  
  887. /* ******************************************************************
  888.  *
  889.  *   List sorting
  890.  *
  891.  ********************************************************************/
  892.  
  893. /*
  894.  * lstQuickSort2:
  895.  *      helper routine for recursing during quicksort (lstQuickSort).
  896.  */
  897.  
  898. void lstQuickSort2(PLINKLIST pList,
  899.                    PFNSORTLIST pfnSort,
  900.                    void* pStorage,
  901.                    long lLeft,
  902.                    long lRight)
  903. {
  904.     long ll = lLeft,
  905.          lr = lRight - 1,
  906.          lPivot = lRight;
  907.  
  908.     if (lRight > lLeft)
  909.     {
  910.         PLISTNODE   pNodeLeft = lstNodeFromIndex(pList, ll),
  911.                     pNodeRight = lstNodeFromIndex(pList, lr),
  912.                     pNodePivot = lstNodeFromIndex(pList, lPivot);
  913.  
  914.         while (TRUE)
  915.         {
  916.             // compare left item data to pivot item data
  917.             while ( pfnSort(pNodeLeft->pItemData,
  918.                             pNodePivot->pItemData,
  919.                             pStorage)
  920.                     < 0 )
  921.             {
  922.                 ll++;
  923.                 // advance to next
  924.                 pNodeLeft = pNodeLeft->pNext;
  925.             }
  926.  
  927.             // compare right item to pivot
  928.             while (     ( pfnSort(pNodeRight->pItemData,
  929.                                   pNodePivot->pItemData,
  930.                                   pStorage)
  931.                            >= 0 )
  932.                     && (lr > ll)
  933.                   )
  934.             {
  935.                 lr--;
  936.                 // step to previous
  937.                 pNodeRight = pNodeRight->pPrevious;
  938.             }
  939.  
  940.             if (lr <= ll)
  941.                 break;
  942.  
  943.             // swap pNodeLeft and pNodeRight
  944.             lstSwapNodes(pNodeLeft, pNodeRight);
  945.         }
  946.  
  947.         // swap pNodeLeft and pNodePivot
  948.         lstSwapNodes(pNodeLeft, pNodePivot);
  949.  
  950.         // recurse!
  951.         lstQuickSort2(pList, pfnSort, pStorage,
  952.                       lLeft,
  953.                       ll - 1);
  954.         lstQuickSort2(pList, pfnSort, pStorage,
  955.                       ll + 1,
  956.                       lRight);
  957.     }
  958. }
  959.  
  960. /*
  961.  *@@ lstQuickSort:
  962.  *      this will sort the given linked list using the
  963.  *      sort function pfnSort, which works similar to those of the
  964.  *      container sorts, i.e. it must be declared as a
  965.  +          signed short XWPENTRY fnSort(void* pItem1, void* pItem2, void* pStorage)
  966.  *
  967.  *      These sort functions need to return the following:
  968.  *      --      0:   pItem1 == pItem2
  969.  *      --     -1:   pItem1 <  pItem2
  970.  *      --     +1:   pItem1 >  pItem2
  971.  *
  972.  *      Note that the comparison function does not get the PLISTNODEs,
  973.  *      but the item data pointers instead.
  974.  *
  975.  *      The pStorage parameter will simply be passed to the comparison
  976.  *      function. This might be useful for additional data you might need.
  977.  *
  978.  *      This returns FALSE upon errors.
  979.  *
  980.  *      This function implements the "quick sort" algorithm, which is one
  981.  *      of the fastest sort algorithms known to mankind. However, this is
  982.  *      an "instable" sort algorithm, meaning that list items considered
  983.  *      equal by pfnSort do _not_ retain their position, but might be
  984.  *      changed. If you need these to remain where they are, use
  985.  *      lstBubbleSort, which is a lot slower though.
  986.  *
  987.  *      This calls lstSwapNodes to swap the list items.
  988.  */
  989.  
  990. BOOL lstQuickSort(PLINKLIST pList,
  991.                   PFNSORTLIST pfnSort,
  992.                   void* pStorage)
  993. {
  994.     BOOL brc = FALSE;
  995.  
  996.     if (    (pList)
  997.          && (pList->ulMagic == LINKLISTMAGIC)
  998.          && (pfnSort)
  999.        )
  1000.     {
  1001.         long lRight = lstCountItems(pList) - 1;
  1002.  
  1003.         lstQuickSort2(pList, pfnSort, pStorage,
  1004.                       0,          // lLeft
  1005.                       lRight);
  1006.         brc = TRUE;
  1007.     }
  1008.  
  1009.     return brc;
  1010. }
  1011.  
  1012. /*
  1013.  *@@ lstBubbleSort:
  1014.  *      just like lstQuickSort, this will sort a given linked list.
  1015.  *      See lstQuickSort for the parameters.
  1016.  *
  1017.  *      However, this function uses the "bubble sort" algorithm, which
  1018.  *      will cause a lot of calls to pfnSort and which is really
  1019.  *      ineffective for lists with more than 100 items.
  1020.  *      Use only if you absolutely need a stable sort.
  1021.  *
  1022.  *      This calls lstSwapNodes to swap the list items.
  1023.  */
  1024.  
  1025. BOOL lstBubbleSort(PLINKLIST pList,
  1026.                    PFNSORTLIST pfnSort,
  1027.                    void* pStorage)
  1028. {
  1029.     BOOL brc = FALSE;
  1030.  
  1031.     if (pList)
  1032.         if (    (pList->ulMagic == LINKLISTMAGIC)
  1033.              && (pfnSort)
  1034.            )
  1035.         {
  1036.             long lRight = lstCountItems(pList),
  1037.                  lSorted,
  1038.                  x;
  1039.  
  1040.             do {
  1041.                 lRight--;
  1042.                 lSorted = 0;
  1043.                 for (x = 0; x < lRight; x++)
  1044.                 {
  1045.                     // ulComp++;
  1046.                     PLISTNODE pNode1 = lstNodeFromIndex(pList, x),
  1047.                               pNode2 = pNode1->pNext;
  1048.                     if ((pNode1) && (pNode2))
  1049.                         if ( (*pfnSort)(pNode1->pItemData,
  1050.                                         pNode2->pItemData,
  1051.                                         pStorage) > 0
  1052.                            )
  1053.                         {
  1054.                             lstSwapNodes(pNode1, pNode2);
  1055.                             lSorted++;
  1056.                         }
  1057.                 }
  1058.             } while ( lSorted && (lRight > 1) );
  1059.  
  1060.             brc = TRUE;
  1061.         }
  1062.  
  1063.     return brc;
  1064. }
  1065.  
  1066. /* ******************************************************************
  1067.  *
  1068.  *   List pseudo-stacks
  1069.  *
  1070.  ********************************************************************/
  1071.  
  1072. /*
  1073.  *@@ lstPush:
  1074.  *      pushes any data onto a "stack", which is a plain
  1075.  *      LINKLIST being abused as a stack.
  1076.  *      The "stack" is last-in, first-out (LIFO), meaning
  1077.  *      that the last item pushed onto the list will be
  1078.  *      the first returned by lstPop. See lstPop for example
  1079.  *      usage.
  1080.  *
  1081.  *@@added V0.9.3 (2000-05-18) [umoeller]
  1082.  */
  1083.  
  1084. PLISTNODE lstPush(PLINKLIST pList,
  1085.                   void* pNewItemData)     // in: data to store in list node
  1086. {
  1087.     return (lstAppendItem(pList, pNewItemData));
  1088. }
  1089.  
  1090. /*
  1091.  *@@ lstPop:
  1092.  *      returns the last item which has been pushed onto
  1093.  *      a pseudo-stack LIFO LINKLIST using lstPush.
  1094.  *
  1095.  *      If (fRemove == TRUE), the item is also removed
  1096.  *      from the stack. Otherwise it remains there so the
  1097.  *      next lstPop would return the next item.
  1098.  *
  1099.  *      Example:
  1100.  *
  1101.  +          LINKLIST ll;
  1102.  +          PLISTNODE pNode;
  1103.  +          lstInit(&ll, FALSE);
  1104.  +
  1105.  +          lstPush(&ll, (PVOID)1);
  1106.  +          lstPush(&ll, (PVOID)2);
  1107.  +
  1108.  +          pNode = lstPop(&ll);  // returns the node containing "2"
  1109.  +          lstRemoveNode(pNode);
  1110.  +          pNode = lstPop(&ll);  // returns the node containing "1"
  1111.  *
  1112.  *@@added V0.9.3 (2000-05-18) [umoeller]
  1113.  */
  1114.  
  1115. PLISTNODE lstPop(PLINKLIST pList)
  1116. {
  1117.     return (pList->pLast);
  1118. }
  1119.  
  1120.  
  1121.