home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: InfoMgt / InfoMgt.zip / shr93.zip / LIST.C < prev    next >
Text File  |  1993-04-12  |  13KB  |  591 lines
  1. /*
  2.  * OS/2 Work Place Shell Sample Program - Simple ordered list functions
  3.  *
  4.  * Copyright (C) 1993 IBM Corporation
  5.  *
  6.  *   DISCLAIMER OF WARRANTIES.  The following [enclosed] code is
  7.  *   sample code created by IBM Corporation.  This sample code is
  8.  *   not part of any standard or IBM product and is provided to you
  9.  *   solely for the purpose of assisting you in the development of
  10.  *   your applications.  The code is provided "AS IS".  ALL
  11.  *   WARRANTIES ARE EXPRESSLY DISCLAIMED, INCLUDING THE IMPLIED
  12.  *   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  13.  *   PURPOSE.  IBM shall not be liable for any damages arising out
  14.  *   of your use of the sample code, even if IBM has been advised of
  15.  *   the possibility of such damages.
  16.  *
  17.  * A simple unindex ordered collection implemented as a 
  18.  * double linked list.  Performs well for small lists, and
  19.  * very badly for large lists.
  20.  */
  21.  
  22. #include <os2.h>          
  23. #include <stdlib.h>
  24. #include <stdio.h>
  25. #include <string.h>
  26. #include <memory.h>
  27. #include "list.h"
  28.  
  29. /*
  30.  * Macros and constants.
  31.  */
  32.  
  33. #define BOOLFROMP(p)         ((p) ? TRUE : FALSE)
  34. #define LISTSIGNATURE        0x4E109D30
  35. #define LISTENUMSIGNATURE    0x74C01283
  36. #define ASSOCIATIONSIGNATURE 0xF7A52033
  37.  
  38. #define ShrValidateList(l,m) \
  39.     (PLIST) ((l && ((PLIST) l)->ulSignature==LISTSIGNATURE) ? \
  40.     l : DebugBox("Invalid List", m))
  41. #define ShrValidateListEnum(l,e,m) (PLISTENUM) \
  42.     ((l && e && ((PLISTENUM) e)->ulSignature==LISTENUMSIGNATURE && \
  43.     ((PLISTENUM) e)->pList==(PLIST)l) ? \
  44.     e : DebugBox("Invalid List Enum", m))
  45.  
  46. /*
  47.  * Typedef's
  48.  */
  49.  
  50. typedef struct _LISTNODE
  51. {
  52.   PVOID pValue;
  53.   struct _LISTNODE *pNext;
  54.   struct _LISTNODE *pPrev;
  55.   BOOL bRemoved;
  56. } LISTNODE, *PLISTNODE;
  57.  
  58. typedef struct _LIST
  59. {
  60.   ULONG ulSignature;
  61.   ULONG ulCount;
  62.   ULONG ulEnumCount;
  63.   ULONG ulRemovedCount;
  64.   PLISTNODE pHead;
  65.   PLISTNODE pTail;
  66.   PFNLISTCOMPARE pfnCompare;
  67. } LIST, *PLIST;
  68.  
  69. typedef struct
  70. {
  71.   ULONG ulSignature;
  72.   PLIST pList;
  73.   PLISTNODE pNext;
  74. } LISTENUM, *PLISTENUM;
  75.  
  76. /*
  77.  * Local function declarations.
  78.  */
  79.  
  80. static PVOID DebugBox(PSZ pszTitle, PSZ pszText);
  81.  
  82. static LONG ShrCompareExactString(PVOID psz1, PVOID psz2);
  83. static LONG ShrCompareString(PVOID psz1, PVOID psz2);
  84. static LONG ShrCompareValue(PVOID pv1, PVOID pv2);
  85.  
  86. static PLISTNODE ShrListInsertBefore
  87.     (PLIST pList, PVOID pValue, PLISTNODE pBeforeListNode);
  88. static PLISTNODE ShrListInsertAfter
  89.     (PLIST pList, PVOID pValue, PLISTNODE pBeforeListNode);
  90. static PLISTNODE ShrListFindNode(PLIST pList, PVOID pValue);
  91. static VOID ShrListRemoveNode(PLIST pList, PLISTNODE pListNode);
  92.  
  93. /*
  94.  * List creation for the standard list
  95.  * types (string, string exact, long). 
  96.  */
  97.  
  98. extern PVOID ShrExactStringListNew()
  99. {
  100.   return ShrGenericListNew(ShrCompareExactString);
  101. }
  102.  
  103. extern PVOID ShrStringListNew()
  104. {
  105.   return ShrGenericListNew(ShrCompareString);
  106. }
  107.  
  108. extern PVOID ShrValueListNew()
  109. {
  110.   return ShrGenericListNew(ShrCompareValue);
  111. }
  112.  
  113. /*
  114.  * List creation and destruction.
  115.  */
  116.  
  117. extern PVOID ShrGenericListNew(PFNLISTCOMPARE pfnCompare)
  118. {
  119.   PLIST pList;
  120.  
  121.   pList = (PLIST) malloc(sizeof(LIST));
  122.  
  123.   if (pList)
  124.   {
  125.     memset(pList, 0, sizeof(LIST));
  126.     pList->pfnCompare = pfnCompare;
  127.  
  128.     /*
  129.      * The "signature" below is used to test whether a valid 
  130.      * list pointer is being passed into the list functions.
  131.      * See the ShrValidateList macro for details.
  132.      */
  133.  
  134.     pList->ulSignature = LISTSIGNATURE;
  135.   }
  136.  
  137.   return (PVOID) pList;
  138. }
  139.  
  140. extern BOOL ShrListFree(PVOID pListParm)
  141. {
  142.   PLIST pList = ShrValidateList(pListParm, "ShrListFree");
  143.   PLISTNODE pListNode, pListNextNode;
  144.   CHAR szText[128];
  145.   BOOL bSuccess = FALSE;
  146.  
  147.   if (pList)
  148.   {
  149.     bSuccess = TRUE;
  150.  
  151.     pListNode = pList->pHead;
  152.     while (pListNode)
  153.     {
  154.       pListNextNode = pListNode->pNext;
  155.       free(pListNode);
  156.       pListNode = pListNextNode;
  157.     }
  158.  
  159.     if (pList->ulEnumCount)
  160.     {
  161.       sprintf(szText, 
  162.           "ShrListFree warning: ShrListBeginEnum called %u times"
  163.           " without calling ShrListEndEnum", pList->ulEnumCount);
  164.       DebugBox("ShrListFree", szText);
  165.  
  166.       bSuccess = FALSE;
  167.     }
  168.  
  169.     memset(pList, 0, sizeof(LIST));
  170.     free(pList);
  171.   }
  172.  
  173.   return bSuccess;
  174. }
  175.  
  176. /*
  177.  * List and list item statistics.
  178.  */
  179.  
  180. extern ULONG ShrListCount(PVOID pListParm)
  181. {
  182.   PLIST pList = ShrValidateList(pListParm, "ShrListCount");
  183.   ULONG ulCount = 0;
  184.  
  185.   if (pList)
  186.     ulCount = pList->ulCount - pList->ulRemovedCount;
  187.  
  188.   return ulCount;
  189. }
  190.  
  191. extern BOOL ShrListIncludes
  192.     (PVOID pListParm, PVOID pValue)
  193. {
  194.   PLIST pList = ShrValidateList(pListParm, "ShrListIncludes");
  195.   BOOL bFound = FALSE;
  196.  
  197.   if (pList)
  198.     bFound = BOOLFROMP(ShrListFindNode(pList, pValue));
  199.  
  200.   return bFound;
  201. }
  202.  
  203. /*
  204.  * Adding list items.
  205.  */
  206.  
  207. extern BOOL ShrListAddLast(PVOID pListParm, PVOID pValue)
  208. {
  209.   PLIST pList = ShrValidateList(pListParm, "ShrListAddLast");
  210.   PLISTNODE pListNode = NULL;
  211.  
  212.   if (pList)
  213.   {
  214.     if (pList->pTail)
  215.     {
  216.       pListNode = ShrListInsertAfter(pList, pValue, pList->pTail);
  217.     }
  218.     else
  219.     {
  220.       pListNode = (PLISTNODE) malloc(sizeof(LISTNODE));
  221.  
  222.       if (pListNode)
  223.       {
  224.         memset(pListNode, 0, sizeof(LISTNODE));
  225.         pListNode->pValue = pValue;
  226.  
  227.         pList->pHead = pList->pTail = pListNode;
  228.         pList->ulCount = 1;
  229.       }
  230.     }
  231.   }
  232.  
  233.   return BOOLFROMP(pListNode);
  234. }
  235.  
  236. extern BOOL ShrListAddFirst(PVOID pListParm, PVOID pValue)
  237. {
  238.   PLIST pList = ShrValidateList(pListParm, "ShrListAddFirst");
  239.   PLISTNODE pListNode = NULL;
  240.  
  241.   if (pList)
  242.   {
  243.     if (pList->pHead)
  244.     {
  245.       pListNode = ShrListInsertBefore(pList, pValue, pList->pHead);
  246.     }
  247.     else
  248.     {
  249.       pListNode = (PLISTNODE) malloc(sizeof(LISTNODE));
  250.  
  251.       if (pListNode)
  252.       {
  253.         memset(pListNode, 0, sizeof(LISTNODE));
  254.         pListNode->pValue = pValue;
  255.  
  256.         pList->pHead = pList->pTail = pListNode;
  257.         pList->ulCount = 1;
  258.       }
  259.     }
  260.   }
  261.  
  262.   return BOOLFROMP(pListNode);
  263. }
  264.  
  265. extern BOOL ShrListAddAfter
  266.     (PVOID pListParm, PVOID pValue, PVOID pAfterValue)
  267. {
  268.   PLIST pList = ShrValidateList(pListParm, "ShrListAddAfter");
  269.   PLISTNODE pAfterListNode, pListNode = NULL;
  270.  
  271.   if (pList)
  272.   {
  273.     pAfterListNode = ShrListFindNode(pList, pAfterValue);
  274.  
  275.     if (pAfterListNode)
  276.       pListNode = ShrListInsertAfter(pList, pValue, pAfterListNode);
  277.   }
  278.  
  279.   return BOOLFROMP(pListNode);
  280. }
  281.  
  282. extern BOOL ShrListAddBefore
  283.     (PVOID pListParm, PVOID pValue, PVOID pBeforeValue)
  284. {
  285.   PLIST pList = ShrValidateList(pListParm, "ShrListAddBefore");
  286.   PLISTNODE pBeforeListNode, pListNode = NULL;
  287.  
  288.   if (pList)
  289.   {
  290.     pBeforeListNode = ShrListFindNode(pList, pBeforeValue);
  291.  
  292.     if (pBeforeListNode)
  293.       pListNode = ShrListInsertBefore(pList, pValue, pBeforeListNode);
  294.   }
  295.  
  296.   return BOOLFROMP(pListNode);
  297. }
  298.  
  299. /*
  300.  * List item removal.
  301.  */
  302.  
  303. extern BOOL ShrListRemove(PVOID pListParm, PVOID pValue)
  304. {
  305.   PLIST pList = ShrValidateList(pListParm, "ShrListRemove");
  306.   PLISTNODE pListNode = NULL;
  307.  
  308.   if (pList)
  309.   {
  310.     pListNode = ShrListFindNode(pList, pValue);
  311.  
  312.     if (pListNode)
  313.       ShrListRemoveNode(pList, pListNode);
  314.   }
  315.  
  316.   return BOOLFROMP(pListNode);
  317. }
  318.  
  319. extern PVOID ShrListRemoveFirst(PVOID pListParm)
  320. {
  321.   PLIST pList = ShrValidateList(pListParm, "ShrListRemoveFirst");
  322.   PLISTNODE pListNode = NULL;
  323.   PVOID pValue = NULL;
  324.  
  325.   if (pList)
  326.   {
  327.     pListNode = pList->pHead;
  328.  
  329.     if (pListNode)
  330.     {
  331.       pValue = pListNode->pValue;
  332.       ShrListRemoveNode(pList, pListNode);
  333.     }
  334.   }
  335.  
  336.   return pValue;
  337. }
  338.  
  339. extern BOOL ShrListRemoveAll(PVOID pListParm)
  340. {
  341.   PLIST pList = ShrValidateList(pListParm, "ShrListRemoveAll");
  342.   PLISTNODE pListNextNode, pListNode;
  343.   BOOL bSuccess = FALSE;
  344.  
  345.   if (pList)
  346.   {
  347.     pListNode = pList->pHead;
  348.     bSuccess = TRUE;
  349.  
  350.     while (pListNode)
  351.     {
  352.       pListNextNode = pListNode->pNext;
  353.       ShrListRemoveNode(pList, pListNode);
  354.       pListNode = pListNextNode;
  355.     }
  356.   }
  357.  
  358.   return bSuccess;
  359. }
  360.  
  361. /*
  362.  * List traversal.
  363.  */
  364.  
  365. extern PVOID ShrListBeginEnum(PVOID pListParm)
  366. {
  367.   PLIST pList = ShrValidateList(pListParm, "ShrListBeginEnum");
  368.   PLISTENUM pListEnum = NULL;
  369.  
  370.   if (pList)
  371.   {
  372.     pListEnum = (PLISTENUM) malloc(sizeof(LISTENUM));
  373.  
  374.     if (pListEnum)
  375.     {
  376.       pListEnum->pList = pList;
  377.       pListEnum->pNext = pList->pHead;
  378.  
  379.       pList->ulEnumCount++;
  380.  
  381.       /*
  382.        * The "signature" below is used to test whether a valid
  383.        * enum pointer is being passed into the list functions.
  384.        * See the ShrValidateListEnum macro for details.
  385.        */
  386.  
  387.       pListEnum->ulSignature = LISTENUMSIGNATURE;
  388.     }
  389.   }
  390.  
  391.   return (PVOID) pListEnum;
  392. }
  393.  
  394. extern BOOL ShrListEndEnum(PVOID pListParm, PVOID pListEnumParm)
  395. {
  396.   PLIST pList = ShrValidateList(pListParm, "ShrListEndEnum");
  397.   PLISTENUM pListEnum = 
  398.       ShrValidateListEnum(pListParm, pListEnumParm, "ShrListEndEnum");
  399.   PLISTNODE pListNode, pListNextNode;
  400.  
  401.   if (pList && pListEnum)
  402.   {
  403.     memset(pListEnum, 0, sizeof(LISTENUM));
  404.     free(pListEnum);
  405.  
  406.     pList->ulEnumCount--;
  407.  
  408.     if (pList->ulEnumCount == 0 && pList->ulRemovedCount)
  409.     {
  410.       pListNode = pList->pHead;
  411.  
  412.       while (pListNode && pList->ulRemovedCount)
  413.       {
  414.         pListNextNode = pListNode->pNext;
  415.  
  416.         if (pListNode->bRemoved)
  417.           ShrListRemoveNode(pList, pListNode);
  418.  
  419.         pListNode = pListNextNode;
  420.       }
  421.     }
  422.   }
  423.  
  424.   return (pList && pListEnum);
  425. }
  426.  
  427. extern BOOL ShrListNext
  428.     (PVOID pListParm, PVOID pListEnumParm, PVOID *ppValue)
  429. {
  430.   PLIST pList = ShrValidateList(pListParm, "ShrListNext");
  431.   PLISTENUM pListEnum = 
  432.       ShrValidateListEnum(pListParm, pListEnumParm, "ShrListNext");
  433.  
  434.   if (pList && pListEnum)
  435.   {
  436.     while (pListEnum->pNext)
  437.     {
  438.       if (!pListEnum->pNext->bRemoved)
  439.       {
  440.         *ppValue = pListEnum->pNext->pValue;
  441.         pListEnum->pNext = pListEnum->pNext->pNext;
  442.  
  443.         return TRUE;
  444.       }
  445.  
  446.       pListEnum->pNext = pListEnum->pNext->pNext;
  447.     }
  448.   }
  449.  
  450.   return FALSE;
  451. }
  452.  
  453. /*
  454.  * Internal functions (note they assume the
  455.  * parameters have been validated).
  456.  */
  457.  
  458. static PLISTNODE ShrListFindNode(PLIST pList, PVOID pValue)
  459. {
  460.   PLISTNODE pListNode;
  461.  
  462.   pListNode = pList->pHead;
  463.  
  464.   while (pListNode)
  465.     if (!pListNode->bRemoved &&
  466.         (*pList->pfnCompare)(pListNode->pValue, pValue) == 0)
  467.       return pListNode;
  468.     else
  469.       pListNode = pListNode->pNext;
  470.  
  471.   return NULL;
  472. }
  473.  
  474. static PLISTNODE ShrListInsertAfter
  475.     (PLIST pList, PVOID pValue, PLISTNODE pAfterListNode)
  476. {
  477.   PLISTNODE pListNode = NULL;
  478.  
  479.   pListNode = (PLISTNODE) malloc(sizeof(LISTNODE));
  480.  
  481.   if (pListNode)
  482.   {
  483.     memset(pListNode, 0, sizeof(LISTNODE));
  484.     pListNode->pValue = pValue;
  485.  
  486.     pListNode->pPrev = pAfterListNode;
  487.     pListNode->pNext = pAfterListNode->pNext;
  488.  
  489.     if (pAfterListNode->pNext)
  490.       pAfterListNode->pNext->pPrev = pListNode;
  491.  
  492.     pAfterListNode->pNext = pListNode;
  493.  
  494.     if (pList->pTail == pAfterListNode)
  495.       pList->pTail = pListNode;
  496.  
  497.     pList->ulCount++;
  498.   }
  499.  
  500.   return pListNode;
  501. }
  502.  
  503. static PLISTNODE ShrListInsertBefore
  504.     (PLIST pList, PVOID pValue, PLISTNODE pBeforeListNode)
  505. {
  506.   PLISTNODE pListNode = NULL;
  507.  
  508.   pListNode = (PLISTNODE) malloc(sizeof(LISTNODE));
  509.  
  510.   if (pListNode)
  511.   {
  512.     memset(pListNode, 0, sizeof(LISTNODE));
  513.     pListNode->pValue = pValue;
  514.  
  515.     pListNode->pNext = pBeforeListNode;
  516.     pListNode->pPrev = pBeforeListNode->pPrev;
  517.  
  518.     if (pBeforeListNode->pPrev)
  519.       pBeforeListNode->pPrev->pNext = pListNode;
  520.  
  521.     pBeforeListNode->pPrev = pListNode;
  522.  
  523.     if (pList->pHead == pBeforeListNode)
  524.       pList->pHead = pListNode;
  525.  
  526.     pList->ulCount++;
  527.   }
  528.  
  529.   return pListNode;
  530. }
  531.  
  532. static VOID ShrListRemoveNode(PLIST pList, PLISTNODE pListRemoveNode)
  533. {
  534.   if (pList->ulEnumCount == 0)
  535.   {
  536.     pList->ulCount--;
  537.  
  538.     if (pList->pHead == pListRemoveNode)
  539.       pList->pHead = pListRemoveNode->pNext;
  540.     if (pList->pTail == pListRemoveNode)
  541.       pList->pTail = pListRemoveNode->pPrev;
  542.     
  543.     if (pListRemoveNode->pPrev)
  544.       pListRemoveNode->pPrev->pNext = pListRemoveNode->pNext;
  545.     
  546.     if (pListRemoveNode->pNext)
  547.       pListRemoveNode->pNext->pPrev = pListRemoveNode->pPrev;
  548.  
  549.     if (pListRemoveNode->bRemoved)
  550.       pList->ulRemovedCount--;
  551.  
  552.     free(pListRemoveNode);
  553.   }
  554.   else
  555.   {
  556.     pListRemoveNode->bRemoved = TRUE;
  557.     pList->ulRemovedCount++;
  558.   }
  559.   
  560.   return;
  561. }
  562.  
  563. static PVOID DebugBox(PSZ pszTitle, PSZ pszText)
  564. {
  565.   WinMessageBox( HWND_DESKTOP, HWND_DESKTOP, pszText, pszTitle,
  566.      20, MB_OK | MB_INFORMATION | MB_MOVEABLE);
  567.  
  568.   return NULL;
  569. }
  570.  
  571. /*
  572.  * List item comparision functions for the standard list
  573.  * types (string, string exact, long).  Use ShrGenericListNew
  574.  * to provide your own list item type.
  575.  */
  576.  
  577. static LONG ShrCompareExactString(PVOID psz1, PVOID psz2)
  578. {
  579.   return strcmp((PSZ) psz1, (PSZ) psz2);
  580. }
  581.  
  582. static LONG ShrCompareString(PVOID psz1, PVOID psz2)
  583. {
  584.   return stricmp((PSZ) psz1, (PSZ) psz2);
  585. }
  586.  
  587. static LONG ShrCompareValue(PVOID pv1, PVOID pv2)
  588. {
  589.   return (LONG) pv1 - (LONG) pv2;
  590. }
  591.