home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: WPS_PM / WPS_PM.zip / xfld085s.zip / helpers / linklist.h < prev    next >
C/C++ Source or Header  |  1999-02-23  |  7KB  |  171 lines
  1.  
  2. /*
  3.  * linklist.h:
  4.  *      header file for linklist.c.
  5.  *
  6.  *      This file is new with V0.81 and contains all the
  7.  *      declarations with respect to linked lists that
  8.  *      used to be in helpers.h.
  9.  *
  10.  *      Copyright (C) 1997-99 Ulrich Möller.
  11.  *      This file is part of the XFolder source package.
  12.  *      XFolder is free software; you can redistribute it and/or modify
  13.  *      it under the terms of the GNU General Public License as published
  14.  *      by the Free Software Foundation, in version 2 as it comes in the
  15.  *      "COPYING" file of the XFolder main distribution.
  16.  *      This program is distributed in the hope that it will be useful,
  17.  *      but WITHOUT ANY WARRANTY; without even the implied warranty of
  18.  *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19.  *      GNU General Public License for more details.
  20.  */
  21.  
  22. #if __cplusplus
  23. extern "C" {
  24. #endif
  25.  
  26. #ifndef LINKLIST_HEADER_INCLUDED
  27.     #define LINKLIST_HEADER_INCLUDED
  28.  
  29.     #ifndef OS2_INCLUDED
  30.         typedef unsigned long BOOL;
  31.         #define TRUE (BOOL)1
  32.         #define FALSE (BOOL)0
  33.     #endif
  34.  
  35.     typedef struct LIST_STRUCT {
  36.         struct LIST_STRUCT   *pNext, *pPrevious;
  37.         unsigned long        ulSize;
  38.     } LISTITEM, *PLISTITEM;
  39.  
  40.     typedef signed short (FNSORTLIST)(void*, void*, void*);
  41.     typedef FNSORTLIST *PFNSORTLIST;
  42.  
  43.     /*
  44.      * lstAppendItem:
  45.      *      this will create an item for a linked list starting at
  46.      *      *ppFirst; this must be a pointer to a pointer to the
  47.      *      first list item; if *ppFirst is NULL (= list is empty),
  48.      *      *ppFirst will be adjusted so that it points to the new
  49.      *      item. If ppLast == NULL, the list is assumed to be
  50.      *      a "one-way" list, otherwise it must point to a pointer
  51.      *      for the last list item, which will be adjusted.
  52.      *      This function returns the address of the new list item.
  53.      */
  54.  
  55.     PLISTITEM lstAppendItem(PLISTITEM *ppFirst, // first list item
  56.                 PLISTITEM *ppLast,              // last list item (or NULL)
  57.                 PLISTITEM pNewItem);            // item to insert
  58.  
  59.     /*
  60.      * lstInsertItemAt:
  61.      *      does just the same, but does not append the new item
  62.      *      at the end of the list, but BEFORE the specified index
  63.      *      lIndex. If lIndex is larger than the number of items
  64.      *      on the list or == -1, the new item will be appended.
  65.      */
  66.  
  67.     PLISTITEM lstInsertItemAt(PLISTITEM *ppFirst, // first list item
  68.                 PLISTITEM *ppLast,              // last list item (or NULL)
  69.                 PLISTITEM pNewItem,             // item to insert
  70.                 long lIndex);                   // insert at (>= 0)
  71.  
  72.     /*
  73.      * lstRemoveItem:
  74.      *      reversely, this will remove a given pRemoveItem from
  75.      *      the linked list beginning at *ppFirst. Returns TRUE if
  76.      *      successful, FALSE if pRemoveItem was not found.
  77.      */
  78.  
  79.     BOOL lstRemoveItem(PLISTITEM *ppFirst,      // first list item
  80.                 PLISTITEM *ppLast,              // last list item (or NULL)
  81.                 PLISTITEM pRemoveItem);         // item to remove
  82.  
  83.     /*
  84.      * lstSwapItems:
  85.      *      this will swap the items ppItem1 and ppItem2 in the linked
  86.      *      list starting at *ppFirst; useful for sorting.
  87.      *      Note that this function will not only adjust the pNext
  88.      *      and pPrevious pointers of the LISTITEMs, but also
  89.      *      swap the *ppItem1 and *ppItem2 pointers.
  90.      */
  91.  
  92.     BOOL lstSwapItems(PLISTITEM *ppFirst,       // first list item
  93.                 PLISTITEM *ppLast,              // last list item (or NULL)
  94.                 PLISTITEM *ppItem1, PLISTITEM *ppItem2);// items to swap
  95.  
  96.     /*
  97.      * lstQuickSort:
  98.      *      this will sort the list starting at *ppFirst using the
  99.      *      sort function pfnSort, which works similar to those of the
  100.      *      container sorts, i.e. it must be declared as a
  101.      *          SHORT EXPENTRY fnSort(PVOID pItem1, PVOID pItem1, PVOID pStorage)
  102.      *      These sort functions need to return the following:
  103.      *          0   pItem1 == pItem2
  104.      *         -1   pItem1 <  pItem2
  105.      *         +1   pItem1 >  pItem2
  106.      *      This function uses the "quick sort" algorithm, which is one of
  107.      *      the fastest sort algorithms available. However, this is an
  108.      *      "instable" sort algorithm, meaning that list items considered
  109.      *      equal by pfnSort do _not_ retain their position, but might be
  110.      *      changed. If you need these to remain where they are, use
  111.      *      lstBubbleSort.
  112.      */
  113.  
  114.     BOOL lstQuickSort(PLISTITEM *ppFirst,       // first list item
  115.                 PLISTITEM *ppLast,              // last list item (or NULL)
  116.                 PFNSORTLIST pfnSort,            // comparison func
  117.                 void* pStorage);                // param for comp. func
  118.  
  119.     /*
  120.      * lstBubbleSort:
  121.      *      this will sort the list starting at *ppFirst using the
  122.      *      sort function pfnSort, which works similar to those of the
  123.      *      container sorts, i.e. it must be declared as a
  124.      *          SHORT EXPENTRY fnSort(PVOID pItem1, PVOID pItem1, PVOID pStorage)
  125.      *      These sort functions need to return the following:
  126.      *          0   pItem1 == pItem2
  127.      *         -1   pItem1 <  pItem2
  128.      *         +1   pItem1 >  pItem2
  129.      *      This function uses the "bubble sort" algorithm, which will cause a
  130.      *      lot of calls to pfnSort and which is really ineffective for lists
  131.      *      with more than 100 items.
  132.      */
  133.  
  134.     BOOL lstBubbleSort(PLISTITEM *ppFirst,      // first list item
  135.                 PLISTITEM *ppLast,              // last list item (or NULL)
  136.                 PFNSORTLIST pfnSort,            // comparison func
  137.                 void* pStorage);                // param for comp. func
  138.  
  139.     /*
  140.      * lstCountItems:
  141.      *      this will count the number of items from pFirst;
  142.      *      returns 0 if error occured.
  143.      */
  144.  
  145.     unsigned long lstCountItems(PLISTITEM pFirst);
  146.  
  147.     /*
  148.      * lstItemFromIndex:
  149.      *      returns the list item with a given ulIndex
  150.      *      (counting from 0), or NULL if ulIndex is too large
  151.      */
  152.  
  153.     PLISTITEM lstItemFromIndex(PLISTITEM pFirst,
  154.                 unsigned long ulIndex);                 // item to find (>= 0)
  155.  
  156.     /*
  157.      * lstClear:
  158.      *      this will free the whole list starting
  159.      *      at *ppFirst and set *ppFirst/*ppLast to NULL
  160.      */
  161.  
  162.     void lstClear(PLISTITEM *ppFirst,           // first list item
  163.                 PLISTITEM *ppLast);             // last list item (or NULL)
  164.  
  165. #endif
  166.  
  167. #if __cplusplus
  168. }
  169. #endif
  170.  
  171.