home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / msdn_vcb / samples / vc98 / sdk / sdktools / windiff / list.c < prev    next >
C/C++ Source or Header  |  1997-10-05  |  39KB  |  1,054 lines
  1.  
  2. /******************************************************************************\
  3. *       This is a part of the Microsoft Source Code Samples. 
  4. *       Copyright (C) 1993-1997 Microsoft Corporation.
  5. *       All rights reserved. 
  6. *       This source code is only intended as a supplement to 
  7. *       Microsoft Development Tools and/or WinHelp documentation.
  8. *       See these sources for detailed information regarding the 
  9. *       Microsoft samples programs.
  10. \******************************************************************************/
  11.  
  12. /****************************** Module Header *******************************
  13. * Module Name: LIST.C
  14. *
  15. *
  16. * Functions:
  17. *
  18. * Alloc()
  19. * Free()
  20. * List_Init()
  21. * List_Dump()
  22. * List_Show()
  23. * List_Create()
  24. * List_Destroy()
  25. * List_AddFirst()
  26. * List_NewFirst()
  27. * List_DeleteFirst()
  28. * List_AddLast()
  29. * List_NewLast()
  30. * LIst_DeleteLast()
  31. * List_AddAfter()
  32. * List_NewAfter()
  33. * List_AddBefore()
  34. * List_NewBefore()
  35. * List_Delete()
  36. * List_DeleteForwards()
  37. * List_DeleteBackwards()
  38. * List_ItemLength()
  39. * List_First()
  40. * List_Last()
  41. * List_Next()
  42. * List_Prev()
  43. * List_Clear()
  44. * List_IsEmpty()
  45. * SwitchLists()
  46. * List_Join()
  47. * List_InsertListAfter()
  48. * List_InsertListBefore()
  49. * List_SplitAfter()
  50. * List_SplitBefore()
  51. * List_Card()
  52. * List_IsOK()
  53. * LIst_MakeOK()
  54. * List_Check()
  55. * List_Recover()
  56. *
  57. * Comments:
  58. *
  59. *
  60. ****************************************************************************/
  61.  
  62. #include <memory.h>
  63. #include <windows.h>
  64.  
  65. #include "gutils.h"
  66. #include "list.h"
  67. #include "gutilsrc.h"
  68.  
  69. #define memcpy  memcpy
  70.  
  71. char msg[80];  /* a temp for building up wsprintf messages in */
  72.  
  73. #define BLOCKSIZE 25000
  74.  typedef struct
  75.  { HANDLE hMem;     /* memory handle for this block */
  76.    int iInUse;    /* number of allocations taken out of it.  0 => free it */
  77.    int iNext;     /* next byte to use */
  78.    char chData[BLOCKSIZE];
  79.  } BLOCK, FAR *PBLOCK;
  80.  
  81. static CRITICAL_SECTION CritSec;  /* to protect pCurrent */
  82. #define List_Enter_Crit(x)      EnterCriticalSection(x)
  83. #define List_Leave_Crit(x)      LeaveCriticalSection(x)
  84.  
  85. static PBLOCK pCurrent = NULL;  /* block currently in use */
  86.                           /* must always be either NULL or valid */
  87.  
  88.  /* Allocate storage for List elements.  n.b. after a call to this
  89.     you MUST record the value of pCurrent as you need to hand that in
  90.     to Free.  You don't hand in the value of the actual storage.
  91.     See screed above.
  92.     This function Enters the critical section.  The caller must Leave it.
  93.  */
  94. static LPVOID Alloc(int size)
  95.  { HANDLE hMem;
  96.    LPVOID pRet;
  97.    List_Enter_Crit(&CritSec);
  98.    if ((pCurrent==NULL)||(pCurrent->iNext+size>BLOCKSIZE+1))
  99.    { hMem = GlobalAlloc(GMEM_MOVEABLE|GMEM_SHARE,(DWORD)(sizeof(BLOCK)));
  100.      if (hMem==NULL)
  101.        { pCurrent = NULL;
  102.          OutputDebugString("GlobalAlloc failed!!\n");
  103.          return NULL;
  104.        }
  105.      pCurrent = (PBLOCK)GlobalLock(hMem);
  106.      if (pCurrent==NULL)
  107.        { OutputDebugString("GlobalLock failed!!\n");
  108.          return NULL;
  109.        }
  110.      pCurrent->hMem = hMem;
  111.      pCurrent->iInUse = 0;
  112.      pCurrent->iNext = 0;
  113.    }
  114.    pRet = &(pCurrent->chData[pCurrent->iNext]);
  115.    ++(pCurrent->iInUse);
  116.    pCurrent->iNext += size;
  117.  
  118.    /* for MIPS we must also ensure that the data is aligned 4 byte*/
  119.    pCurrent->iNext += 3;
  120.    pCurrent->iNext -= pCurrent->iNext % 4;
  121.  
  122.    return pRet;
  123.  } /* Alloc */
  124.  
  125. static void Free(PBLOCK pBlock, LPVOID p)
  126.  { HANDLE hMem;
  127.    List_Enter_Crit(&CritSec);
  128.     --pBlock->iInUse;
  129.    if (pBlock->iInUse<=0)
  130.    { if (pBlock->iInUse<0)
  131.      { 
  132.         extern HANDLE hLibInst;
  133.         TCHAR szBuf[512];
  134.         LoadString(hLibInst, IDS_LIST_ALLOC_NEGATIVE, szBuf, sizeof(szBuf));
  135.  
  136.         wsprintf(msg, szBuf, pBlock->iInUse);
  137.         MessageBox(NULL, msg, NULL, MB_OK | MB_ICONSTOP);
  138.       }
  139.  
  140.      hMem = pBlock->hMem;
  141.      GlobalUnlock(hMem);
  142.      GlobalFree(hMem);
  143.      if (pCurrent==pBlock) pCurrent = NULL; /* defend the invariant */
  144.    }
  145.    List_Leave_Crit(&CritSec);
  146.  } /* Free */
  147.  
  148.   /* The following definition tells the truth about what an ITEM is.  The
  149.   |  header file says only that there's a structure with the tag item_tag and
  150.   |  that a LIST is a pointer to one.  Here we spell out what that structure
  151.   |  is (and a LIST is still a pointer to one).  A PLIST is defined as a
  152.   |  pointer to one of those, but is only really used because the C
  153.   |  parameter mechanism demands an extra level of indirection for a
  154.   |  parameter that can be updated.  (Modula-2 VAR parameter).
  155.   */
  156.   typedef struct item_tag
  157.   { struct item_tag FAR *pitNext;    /* to next in circular list */
  158.     struct item_tag FAR *pitPrev;    /* to prev in circular list */
  159.     PBLOCK pBlock;               /* to memory block */
  160.     BOOL bAnchor;                /* TRUE iff an anchor block */
  161.     BOOL bOK;                    /* true unless a list op has failed */
  162.     int iLen;                    /* length of data only */
  163.     char Data[1];                /* the caller's data.  The '1' is a lie */
  164.   } ITEM;
  165.  
  166.   /* For an anchor block, only the fields pitNext thru bAnchor are allocated.
  167.   |  For a normal list element, Data may well be longer than 1 byte.
  168.   |  The bOK flag is to support a style of programming where several
  169.   |  successive operations can be done without having to check the return
  170.   |  code at each stage.  At the end, the list can be examined to see if
  171.   |  the data in it is valid or if it has been made invalid by the failure
  172.   |  of any of the previous operations.  Certain operations may result in
  173.   |  having no list at all if they fail (e.g. create) and for these, you'd
  174.   |  better check the result at once!
  175.   |  ??? Some of this screed belongs in the header!!!
  176.   */
  177.  
  178.   static int iAnchorSize;      /* Size of anchor block (no data, no dummy) */
  179.   static int iHeaderSize;      /* Size of data block not counting Data
  180.                                   and offset from cursor back to item.
  181.                                */
  182.   static BOOL bInited = FALSE; /* TRUE <=> iAnchorSize and iHeaderSize are OK*/
  183.  
  184. #define MOVEBACK(Curs)                                               \
  185.    { Curs = ((char FAR *)Curs-iHeaderSize); } /*move from Data to pitNext*/
  186.  
  187.   /*==================================================================
  188.   || Lists are circular, doubly linked with an anchor block which holds
  189.   || pointers to both ends.  Every block has a flag which shows whether
  190.   || it's an anchor or not.
  191.   ||
  192.   || Empty list:
  193.   ||
  194.   ||      -------------
  195.   ||     |             |
  196.   ||     |   Anchor    |
  197.   ||     v   -------   |
  198.   ||  Ul--->| Next--+--|
  199.   ||        |-------|  |
  200.   ||        | Prev--+--
  201.   ||         -------
  202.   ||
  203.   || One entry list:
  204.   ||
  205.   ||      ------------------------------------
  206.   ||     |                                    |
  207.   ||     |   Anchor                           |
  208.   ||     v   -------                ------    |
  209.   ||  Ul--->| Next--+------------->| Next-+---|
  210.   ||        |-------|    |         |------|   |
  211.   ||        | Prev--+----          | Prev-+---
  212.   ||         -------               |------|
  213.   ||                               | Len  |
  214.   ||                               |------|
  215.   ||                               | Data |
  216.   ||                                ------
  217.   || Two entry list:
  218.   ||
  219.   ||      -------------------------------------------------
  220.   ||     | ---------------    ---------------              |
  221.   ||     ||               |  |               |             |
  222.   ||     ||  Anchor       |  |               |             |
  223.   ||     vv  --------     |  v    ------     |    ------   |
  224.   ||  Ul--->| Next--+-----+----->| Next-+----+-->| Next-+--
  225.   ||        |-------|     |      |------|  | |   |------|
  226.   ||        | Prev--+--    ------+-Prev |  |  ---+-Prev |
  227.   ||         -------   |         |------|  |     |------|
  228.   ||                   |         | Len  |  |     | Len  |
  229.   ||                   |         |------|  |     |------|<----Cursor
  230.   ||                   |         | Data |  |     | Data |
  231.   ||                   |          ------   |      ------
  232.   ||                   |                   |
  233.   ||                    -------------------
  234.   ||
  235.   || etc.
  236.   ||
  237.   || Note that an external cursor (i.e one which is seen by the caller)
  238.   || points to the Data field, not to the start of the structure.
  239.   || This allows easy access to the data by the user at the cost of a
  240.   || slightly slower traverse.
  241.   || Within this module, we may sometimes traverse a list with  a cursor
  242.   || that points to the start of an item.  This is called an item cursor.
  243.   ╚===================================================================*/
  244.  
  245.   /*------------------------------------------------------------------
  246.   | Set iAnchorSize and iHeaderSize.  Implementation independent!
  247.    -------------------------------------------------------------------*/
  248. void APIENTRY List_Init(void)
  249.   {  LIST P;
  250.      P = (LIST)&P;                  /* really any old address will do */
  251.      iAnchorSize = (char FAR *)&(P->iLen) - (char FAR *)&(P->pitNext);
  252.      iHeaderSize = (char FAR *)&(P->Data) - (char FAR *)&(P->pitNext);
  253.      InitializeCriticalSection(&CritSec);
  254.      /* assumes layout in storage is linear */
  255.   }
  256.  
  257.   /* Dump the internals to the debugger. */
  258. void APIENTRY List_Dump(LPSTR Header, LIST lst)
  259.   {  LIST pit;
  260.      char msg[250];
  261.  
  262.      OutputDebugString(Header);  OutputDebugString("\n");
  263.      pit = lst;
  264.      do
  265.      { wsprintf(msg,"%8x %8x %8x %ld %s "
  266.                , pit, pit->pitNext, pit->pitPrev, pit->iLen
  267.                , (pit->bAnchor ? "Anchor" : "Data")
  268.                );
  269.        OutputDebugString(msg);
  270.        if (pit->pitNext->pitPrev != pit)
  271.          OutputDebugString(" Next Prev error!!");
  272.        if (pit->pitPrev->pitNext != pit)
  273.          OutputDebugString(" Prev Next error!!");
  274.        OutputDebugString("\n");
  275.        pit = pit->pitNext;
  276.      } while (pit!=lst);
  277.      OutputDebugString("End of list dump\n");
  278.   } /* List_Dump */
  279.  
  280.   /* Dump hex representation of handle to debugger */
  281. void APIENTRY List_Show(LIST lst)
  282.   { char msg[50];               
  283.     wsprintf(msg, "%8x", lst);
  284.     OutputDebugString(msg);
  285.   } /* List_Show */
  286.  
  287.   /*------------------------------------------------------------------
  288.   | Create a list.  It will be initially empty
  289.    -------------------------------------------------------------------*/
  290. LIST APIENTRY List_Create(void)
  291.   {  LIST lst;
  292.      if (!bInited) {List_Init(); }          /* prevent some silly errors */
  293.      lst = Alloc(iAnchorSize);
  294.      if (lst==NULL) { return NULL; }
  295.      lst->pBlock = pCurrent;
  296.      List_Leave_Crit(&CritSec);
  297.      lst->bOK = TRUE;
  298.      lst->pitNext = lst;
  299.      lst->pitPrev = lst;
  300.      lst->bAnchor = TRUE;
  301.      /* no length field set in an anchor block */
  302.      return lst;
  303.   } /* List_Create */
  304.  
  305.   /*------------------------------------------------------------------
  306.   | Destroy *plst.  It does not need to be empty first
  307.    -------------------------------------------------------------------*/
  308.   void APIENTRY List_Destroy(PLIST plst)
  309.   {  LIST pitP;    /* item cursor on * plst */
  310.      LIST pitQ;    /* item cursor runs one step ahead of pitQ */
  311.  
  312.      if (plst==NULL)
  313.        return;
  314.      /* There is at least an anchor block to destroy */
  315.      pitP = *plst;
  316.      do
  317.      {  pitQ = pitP->pitNext;
  318.         Free(pitP->pBlock, pitP);
  319.         pitP = pitQ;
  320.      }while(pitP != *plst);
  321.      *plst = NULL;
  322.   } /* List_Destroy */
  323.  
  324.   /*------------------------------------------------------------------
  325.   | Add an item holding Object to the beginning of * plst
  326.    -------------------------------------------------------------------*/
  327.   void APIENTRY List_AddFirst(LIST lst, LPVOID pObject, UINT uLen)
  328.   {  LIST pit;      /* newly allocated item */
  329.  
  330.      if (lst==NULL)
  331.        return;
  332.      pit = Alloc(iHeaderSize+uLen);
  333.      if (pit==NULL) { lst->bOK = FALSE; return; }
  334.      pit->pBlock = pCurrent;
  335.      List_Leave_Crit(&CritSec);
  336.      pit->iLen = uLen;
  337.      pit->pitPrev = lst;
  338.      pit->pitNext = lst->pitNext;
  339.      lst->pitNext->pitPrev = pit; /* for empty list that set lst->pitPrev */
  340.      lst->pitNext = pit;
  341.      pit->bAnchor = FALSE;
  342.      memcpy( &(pit->Data), pObject, uLen );
  343.   } /* List_AddFirst */
  344.  
  345.   /*------------------------------------------------------------------
  346.   | Return the address of the place for Len bytes of data in a new
  347.   | item at the start of lst
  348.    -------------------------------------------------------------------*/
  349.   LPVOID APIENTRY List_NewFirst(LIST lst, UINT uLen)
  350.   {  LIST pit;
  351.  
  352.      if (lst==NULL)
  353.        return NULL;
  354.      pit = Alloc(iHeaderSize+uLen);
  355.      if (pit==NULL) { lst->bOK = FALSE; return NULL; }
  356.      pit->pBlock = pCurrent;
  357.      List_Leave_Crit(&CritSec);
  358.      pit->iLen = uLen;
  359.      pit->pitPrev = lst;
  360.      pit->pitNext = lst->pitNext;
  361.      lst->pitNext->pitPrev = pit; /* for empty list that set lst->pitPrev */
  362.      lst->pitNext = pit;
  363.      pit->bAnchor = FALSE;
  364.      return (char FAR *)&(pit->Data);
  365.   } /* List_NewFirst */
  366.  
  367.   /*------------------------------------------------------------------
  368.   | Delete the first item in lst.  Error if lst is empty
  369.    -------------------------------------------------------------------*/
  370.   void APIENTRY List_DeleteFirst(LIST lst)
  371.   {  LIST pit;
  372.  
  373.      if (lst==NULL)
  374.        return;
  375.                                /* attempting to delete the anchor block! */
  376.      if (lst->pitNext==lst) {lst->bOK = FALSE; }
  377.      else
  378.         {  pit = lst->pitNext;
  379.            pit->pitNext->pitPrev = pit->pitPrev;
  380.            pit->pitPrev->pitNext = pit->pitNext;
  381.            Free(pit->pBlock, pit);
  382.         }
  383.   } /* List_DeleteFirst */
  384.  
  385.   /*------------------------------------------------------------------
  386.   | Add an item holding Object to the end of lst
  387.    -------------------------------------------------------------------*/
  388.   void APIENTRY List_AddLast(LIST lst, LPVOID pObject, UINT uLen)
  389.   {  LIST pit;
  390.  
  391.      if (lst==NULL)
  392.        return;
  393.      pit = Alloc(iHeaderSize+uLen);
  394.      if (pit==NULL) { lst->bOK = FALSE; return; }
  395.      pit->pBlock = pCurrent;
  396.      List_Leave_Crit(&CritSec);
  397.      pit->iLen = uLen;
  398.      pit->pitNext = lst;
  399.      pit->pitPrev = lst->pitPrev;
  400.      lst->pitPrev->pitNext = pit; /* for empty list that set lst->pitNext */
  401.      lst->pitPrev = pit;
  402.      pit->bAnchor = FALSE;
  403.      memcpy( &(pit->Data), pObject, uLen );
  404.   } /* ListAddLast */
  405.  
  406.   /*------------------------------------------------------------------
  407.   | Return the address of the place for uLen bytes of data in a new
  408.   |  item at the end of lst
  409.    -------------------------------------------------------------------*/
  410.   LPVOID APIENTRY List_NewLast(LIST lst, UINT uLen)
  411.   {  LIST pit;
  412.  
  413.      if (lst==NULL)
  414.        return NULL;
  415.      pit = Alloc(iHeaderSize+uLen);
  416.      if (pit==NULL) { lst->bOK = FALSE; return NULL; }
  417.      pit->pBlock = pCurrent;
  418.      List_Leave_Crit(&CritSec);
  419.      pit->iLen = uLen;
  420.      pit->pitNext = lst;
  421.      pit->pitPrev = lst->pitPrev;
  422.      lst->pitPrev->pitNext = pit; /* for empty list that set lst->pitNext */
  423.      lst->pitPrev = pit;
  424.      pit->bAnchor = FALSE;
  425.      return (char FAR *)&(pit->Data);
  426.   } /* ListNewLast */
  427.  
  428.   /*------------------------------------------------------------------
  429.   | Delete the last item in lst.  Error if lst is empty
  430.    -------------------------------------------------------------------*/
  431.   void APIENTRY List_DeleteLast(LIST lst)
  432.   {  LIST pit;
  433.  
  434.      if (lst==NULL)
  435.        return;
  436.                                /* attempting to delete the anchor block! */
  437.      if (lst->pitNext==lst) {lst->bOK = FALSE; }
  438.      else
  439.         {  pit = lst->pitPrev;
  440.            pit->pitNext->pitPrev = pit->pitPrev;
  441.            pit->pitPrev->pitNext = pit->pitNext;
  442.            Free(pit->pBlock, pit);
  443.         }
  444.   } /* List_DeleteLast */
  445.  
  446.   /*--------------------------------------------------------------------
  447.   | Add an item holding * pObject to lst immediately after Curs.
  448.   | List_AddAfter(lst,NULL,pObject,Len) adds it to the start of the lst
  449.    ---------------------------------------------------------------------*/
  450.   void APIENTRY List_AddAfter( LIST lst
  451.                     , LPVOID Curs
  452.                     , LPVOID pObject
  453.                     , UINT uLen
  454.                     )
  455.   {  LIST pitNew;
  456.      LIST pitAfter;
  457.  
  458.      if (lst==NULL)
  459.        return;
  460.      if (Curs==NULL){ List_AddFirst(lst, pObject, uLen);}
  461.      else
  462.         {  MOVEBACK(Curs);
  463.            pitAfter = (LIST)Curs;
  464.            pitNew = Alloc(iHeaderSize+uLen);
  465.            if (pitNew==NULL) { lst->bOK = FALSE; return; }
  466.            pitNew->pBlock = pCurrent;
  467.            List_Leave_Crit(&CritSec);
  468.            pitNew->iLen = uLen;
  469.            pitNew->pitPrev = pitAfter;
  470.            pitNew->pitNext = pitAfter->pitNext;
  471.            pitAfter->pitNext->pitPrev = pitNew;
  472.            pitAfter->pitNext = pitNew;
  473.            pitNew->bAnchor = FALSE;
  474.            memcpy( &(pitNew->Data), pObject, uLen );
  475.         }
  476.   } /* List_AddAfter */
  477.  
  478.   /*--------------------------------------------------------------------
  479.   | Return the address of the place for uLen bytes of data in a new
  480.   | item immediately after Curs.
  481.   | List_NewAfter(Lst,NULL,uLen) returns a pointer
  482.   | to space for uLen bytes in a new first element.
  483.    ---------------------------------------------------------------------*/
  484.   LPVOID APIENTRY List_NewAfter(LIST lst, LPVOID Curs, UINT uLen)
  485.   {  LIST pitNew;
  486.      LIST pitAfter;
  487.  
  488.      if (lst==NULL)
  489.        return NULL;
  490.      if (Curs==NULL){ return List_NewFirst(lst, uLen);}
  491.      else
  492.         {  MOVEBACK(Curs);
  493.            pitAfter = (LIST)Curs;
  494.            pitNew = Alloc(iHeaderSize+uLen);
  495.            if (pitNew==NULL) { lst->bOK = FALSE; return NULL; }
  496.            pitNew->pBlock = pCurrent;
  497.            List_Leave_Crit(&CritSec);
  498.            pitNew->iLen = uLen;
  499.            pitNew->pitPrev = pitAfter;
  500.            pitNew->pitNext = pitAfter->pitNext;
  501.            pitAfter->pitNext->pitPrev = pitNew;
  502.            pitAfter->pitNext = pitNew;
  503.            pitNew->bAnchor = FALSE;
  504.            return (char FAR *)&(pitNew->Data);
  505.         }
  506.   } /* List_NewAfter */
  507.  
  508.   /*--------------------------------------------------------------------
  509.   | Add an item holding Object to lst immediately before Curs.
  510.   | List_AddBefore(Lst,NULL,Object,uLen) adds it to the end of the list
  511.    ---------------------------------------------------------------------*/
  512.   void APIENTRY List_AddBefore( LIST lst
  513.                      , LPVOID Curs
  514.                      , LPVOID pObject
  515.                      , UINT uLen
  516.                      )
  517.   {  LIST pitNew;
  518.      LIST pitBefore;
  519.  
  520.      if (lst==NULL)
  521.        return;
  522.      if (Curs==NULL){ List_AddLast(lst, pObject, uLen);}
  523.      else
  524.         {  MOVEBACK(Curs);
  525.            pitBefore = (LIST)Curs;
  526.            pitNew = Alloc(iHeaderSize+uLen);
  527.            if (pitNew==NULL) { lst->bOK = FALSE; return; }
  528.            pitNew->pBlock = pCurrent;
  529.            List_Leave_Crit(&CritSec);
  530.            pitNew->iLen = uLen;
  531.            pitNew->pitNext = pitBefore;
  532.            pitNew->pitPrev = pitBefore->pitPrev;
  533.            pitBefore->pitPrev->pitNext = pitNew;
  534.            pitBefore->pitPrev = pitNew;
  535.            pitNew->bAnchor = FALSE;
  536.            memcpy( &(pitNew->Data), pObject, uLen );
  537.         }
  538.   } /* List_AddBefore */
  539.  
  540.   /*--------------------------------------------------------------------
  541.   | Return the address of the place for uLen bytes of data in a new
  542.   | item immediately before Curs.
  543.   | List_NewBefore(Lst,NULL,uLen) returns a pointer
  544.   | to space for uLen bytes in a new last element.
  545.    ---------------------------------------------------------------------*/
  546.   LPVOID APIENTRY List_NewBefore(LIST lst, LPVOID Curs, UINT uLen )
  547.   {  LIST pitNew;
  548.      LIST pitBefore;
  549.  
  550.      if (lst==NULL)
  551.        return NULL;
  552.      if (Curs==NULL){ return List_NewLast(lst, uLen);}
  553.      else
  554.         {  MOVEBACK(Curs);
  555.            pitBefore = (LIST)Curs;
  556.            pitNew = Alloc(iHeaderSize+uLen);
  557.            if (pitNew==NULL) { lst->bOK = FALSE; return NULL; }
  558.            pitNew->pBlock = pCurrent;
  559.            List_Leave_Crit(&CritSec);
  560.            pitNew->iLen = uLen;
  561.            pitNew->pitNext = pitBefore;
  562.            pitNew->pitPrev = pitBefore->pitPrev;
  563.            pitBefore->pitPrev->pitNext = pitNew;
  564.            pitBefore->pitPrev = pitNew;
  565.            pitNew->bAnchor = FALSE;
  566.            return (char FAR *) &(pitNew->Data);
  567.         }
  568.   } /* List_NewBefore */
  569.  
  570.   /*------------------------------------------------------------------
  571.   | Delete the item that Curs identifies.
  572.   | This will be only a few (maybe as little as 3) machine instructions
  573.   | quicker than DeleteForwards or DeleteBackwards but leaves Curs dangling.
  574.   | It is therefore NOT usually to be preferred.
  575.   | It may be useful when you have a function which returns an LPVOID
  576.   | since the argument does not need to be a variable.
  577.   |     Trivial example: List_Delete(List_First(L));
  578.    -------------------------------------------------------------------*/
  579.   void APIENTRY List_Delete(LPVOID Curs)
  580.   {  LIST pit;
  581.  
  582.      if(Curs==NULL)
  583.        return;
  584.      MOVEBACK(Curs)
  585.      pit = (LIST)Curs;
  586.      pit->pitNext->pitPrev = pit->pitPrev;
  587.      pit->pitPrev->pitNext = pit->pitNext;
  588.      Free(pit->pBlock, pit);
  589.   } /* List_Delete */
  590.  
  591.   /*-----------------------------------------------------------------------
  592.   | Delete the item that Curs identifies and return a cursor that
  593.   | identifies the next item (NULL if already on last)
  594.    ------------------------------------------------------------------------*/
  595.   LPVOID APIENTRY List_DeleteForwards(LPVOID Curs)
  596.   {  LIST pitDel;  /* the item to delete */
  597.      LIST pitN;    /* the item after (could be anchor) */
  598.  
  599.      if(Curs==NULL)
  600.        return NULL;
  601.      MOVEBACK(Curs)
  602.      pitDel = (LIST)Curs;
  603.      pitN = pitDel->pitNext;
  604.  
  605.      pitN->pitPrev = pitDel->pitPrev;
  606.      pitDel->pitPrev->pitNext = pitN;
  607.      Free(pitDel->pBlock, pitDel);
  608.      if (pitN->bAnchor) return NULL;
  609.      else return (char FAR *)&(pitN->Data);
  610.   } /* List_DeleteForwards */
  611.  
  612.   /*-----------------------------------------------------------------------
  613.   | Delete the item that Curs identifies and return a cursor that
  614.   | identifies the previous item (NULL if already on first)
  615.    ------------------------------------------------------------------------*/
  616.   LPVOID APIENTRY List_DeleteBackwards(LPVOID Curs)
  617.   {  LIST pitDel;  /* the one to delete */
  618.      LIST pitB;    /* the one before */
  619.  
  620.      if(Curs==NULL)
  621.        return NULL;
  622.      MOVEBACK(Curs)
  623.      pitDel = (LIST)Curs;
  624.      pitB = pitDel->pitPrev;
  625.      pitDel->pitNext->pitPrev = pitB;
  626.      pitB->pitNext = pitDel->pitNext;
  627.      Free(pitDel->pBlock, pitDel);
  628.      if (pitB->bAnchor) return NULL;
  629.      else return (char FAR *)&(pitB->Data);
  630.   } /* List_DeleteBackwards */
  631.  
  632.   /*-------------------------------------------------------------------
  633.   | Return the length of the object identified by the cursor Curs
  634.    -------------------------------------------------------------------*/
  635.   int APIENTRY List_ItemLength(LPVOID Curs)
  636.   {  LIST pit;
  637.  
  638.      if(Curs==NULL)
  639.        return 0;
  640.      MOVEBACK(Curs)
  641.      pit = (LIST)Curs;
  642.      return pit->iLen;
  643.   } /* List_ItemLength */
  644.  
  645.   /*------------------------------------------------------------------
  646.   | Return the address of the first object in lst
  647.   |  If lst is empty then Return NULL.
  648.    -------------------------------------------------------------------*/
  649.   LPVOID APIENTRY List_First(LIST lst)
  650.   {  
  651.      if (lst==NULL)
  652.        return NULL;
  653.      if (lst->pitNext==lst) { return NULL; }
  654.      return &(lst->pitNext->Data);
  655.   } /* List_First */
  656.  
  657.   /*------------------------------------------------------------------
  658.   | Return the address of the last object in lst
  659.   | If lst is empty then return NULL.
  660.    -------------------------------------------------------------------*/
  661.   LPVOID APIENTRY List_Last(LIST lst)
  662.   {  
  663.      if (lst==NULL)
  664.        return NULL;
  665.      if (lst->pitNext==lst) { return NULL; }
  666.      return &(lst->pitPrev->Data);
  667.   } /* List_Last */
  668.  
  669.   /*------------------------------------------------------------------
  670.   | Return the address of the object after Curs^.
  671.   | List_Next(List_Last(lst)) == NULL;  List_Next(NULL) is an error.
  672.    -------------------------------------------------------------------*/
  673.   LPVOID APIENTRY List_Next(LPVOID Curs)
  674.   {  LIST pit;
  675.  
  676.      if(Curs==NULL)
  677.        return NULL;
  678.      MOVEBACK(Curs)
  679.      pit = (LIST)Curs;
  680.      pit = pit->pitNext;
  681.      if (pit->bAnchor) {return NULL;} else {return &(pit->Data);}
  682.   } /* List_Next */
  683.  
  684.   /*------------------------------------------------------------------
  685.   | Return the address of the object after Curs^.
  686.   | List_Prev(List_First(L)) == NULL;  List_Prev(NULL) is an error.
  687.    -------------------------------------------------------------------*/
  688.   LPVOID APIENTRY List_Prev(LPVOID Curs)
  689.   {  LIST pit;
  690.  
  691.      if(Curs==NULL)
  692.        return NULL;
  693.      MOVEBACK(Curs)
  694.      pit = (LIST)Curs;
  695.      pit = pit->pitPrev;
  696.      if (pit->bAnchor) {return NULL;} else {return &(pit->Data);}
  697.   } /* List_Prev */
  698.  
  699.   /*-------------------------------------------------------------------
  700.   | Arrange that lst is empty after this call
  701.    --------------------------------------------------------------------*/
  702.   void APIENTRY List_Clear(LIST lst)
  703.   {  LIST pitP;   /* item cursor on List, points to element starts */
  704.      LIST pitQ;   /* runs one step ahead of pitP                   */
  705.  
  706.      if (lst==NULL)
  707.        return;
  708.      pitP = lst->pitNext;   /* first element of list proper */
  709.      while (pitP!=lst)      /* while not wrapped onto anchor */
  710.         {  pitQ = pitP->pitNext;
  711.            Free(pitP->pBlock, pitP);
  712.            pitP = pitQ;
  713.         }
  714.      lst->bOK = TRUE;
  715.      lst->pitNext = lst;
  716.      lst->pitPrev = lst;
  717.   } /* List Clear */
  718.  
  719.   /*---------------------------------------------------------------------
  720.   | Return TRUE if and only if lst is empty
  721.    ----------------------------------------------------------------------*/
  722.   BOOL APIENTRY List_IsEmpty(LIST lst)
  723.   {  if (lst==NULL)
  724.        return TRUE;   /* well it's sort of true isn't it? */
  725.      return lst->pitNext ==lst;
  726.   } /* List_IsEmpty */
  727.  
  728.   /*------------------------------------------------------------------
  729.   | l1 had better be empty.  l1 then acquires all the elements from l2
  730.    -------------------------------------------------------------------*/
  731.   void APIENTRY SwitchLists(LIST l1, LIST l2)
  732.   {  /* connect l1 to l2's elements, l1 had better be initially empty */
  733.      l1->pitPrev = l2->pitPrev;
  734.      l1->pitNext = l2->pitNext;
  735.      /* connect the elements to l1 anchor block. */
  736.      l1->pitPrev->pitNext = l1;
  737.      l1->pitNext->pitPrev = l1;
  738.      /* make l2 empty */
  739.      l2->pitPrev = l2;
  740.      l2->pitNext = l2;
  741.   } /* SwitchLists */
  742.  
  743.   /*-----------------------------------------------------------------------
  744.   | l1 := l1||l2; l2 := empty
  745.   | The elements themselves are not moved, so pointers to them remain valid.
  746.   |
  747.   | l1 gets all the elements of l1 in their original order followed by
  748.   | all the elements of l2 in the order they were in in l2.
  749.   | l2 becomes empty.
  750.    ------------------------------------------------------------------------*/
  751.   void APIENTRY List_Join(LIST l1, LIST l2)
  752.   {  if((l1==NULL)||(l2==NULL))
  753.        return;
  754.      l1->bOK = l1->bOK &&l2->bOK;  /* result OK if both inputs OK */
  755.      l2->bOK = TRUE;               /* as l2 always becomes empty */
  756.      if (l2->pitNext==l2) { /* no elements need moving */ }
  757.      else if (l2->pitNext==l2) { SwitchLists(l1,l2); return; }
  758.      else
  759.         {  l2->pitNext->pitPrev = l1->pitPrev;
  760.            l1->pitPrev->pitNext = l2->pitNext;
  761.            l1->pitPrev = l2->pitPrev;
  762.            l1->pitPrev->pitNext = l1;
  763.            l2->pitNext = l2;
  764.            l2->pitPrev = l2;
  765.         }
  766.   } /* List_Join */
  767.  
  768.   /*-----------------------------------------------------------------------
  769.   | Let L1 be *pl1 and L2 be *pl2
  770.   | L1 := L1[...Curs] || L2 || L1[Curs+1...]; L2 := empty
  771.   | Curs=NULL means insert L2 at the start of L1
  772.   | The elements themselves are not moved, so pointers to them remain valid.
  773.   |
  774.   | L1 gets the elements of L1 from the start up to and including the element
  775.   | that Curs points at, in their original order,
  776.   | followed by all the elements that were in L2, in their original order,
  777.   | followed by the rest of L1
  778.    ------------------------------------------------------------------------*/
  779.   void APIENTRY List_InsertListAfter(LIST l1, LIST l2, LPVOID Curs)
  780.   {  LIST pitA;     /* The element after Curs, could be anchor */
  781.      LIST pit;      /* The start of the element that Curs points at
  782.                     |  or the anchor block if Curs==NULL
  783.                     */
  784.  
  785.      if ( (l1==NULL) || (l2==NULL))
  786.        return;
  787.      l1->bOK = l1->bOK && l2->bOK;
  788.      l2->bOK = TRUE;
  789.      if (l2->pitNext==l2) { /* no elements need moving */ }
  790.      else if ( l1->pitNext==l1)
  791.      {  /* the easy way to code this would be simply to switch the two
  792.         |  pointers l1 and l2, but they are value parameters and we don't
  793.         |  want to change that.
  794.         */
  795.         SwitchLists(l1,l2);
  796.         return;
  797.      }
  798.      else
  799.      {  if(Curs==NULL){ pit = l1;}
  800.         else
  801.         {  MOVEBACK(Curs)
  802.            pit = (LIST)Curs;
  803.         }
  804.         /* pit points to a block to insert after, could be anchor */
  805.         pitA = pit->pitNext;      /* Cannot be same as P, already checked */
  806.         l2->pitNext->pitPrev = pit;    /*  P<-- elems-of-l2    A */
  807.         l2->pitPrev->pitNext = pitA;   /*  P<-- elems-of-l2 -->A */
  808.         pit->pitNext = l2->pitNext;    /*  P<-->elems-of-l2 -->A */
  809.         pitA->pitPrev = l2->pitPrev;   /*  P<-->elems-of-l2<-->A */
  810.  
  811.         l2->pitNext = l2;
  812.         l2->pitPrev = l2;
  813.      }
  814.   }  /* List_InsertListAfter */
  815.  
  816.  
  817.   /*-----------------------------------------------------------------------
  818.   | l1 := l1[...Curs-1] || l2 || l1[Curs...]; l2 := empty
  819.   | Curs=NULL means insert l2 at the end of l1
  820.   | The elements themselves are not moved, so pointers to them remain valid.
  821.   |
  822.   | l1 gets the elements of l1 from the start up to but not including the
  823.   | element that Curs points at, in their original order,
  824.   | followed by all the elements that were in l2, in their original order,
  825.   | followed by the rest of l1.
  826.    ------------------------------------------------------------------------*/
  827.   void APIENTRY List_InsertListBefore(LIST l1, LIST l2, LPVOID Curs)
  828.   {  LIST pitB;     /* The element before Curs, could be anchor */
  829.      LIST pit;      /* The start of the element that Curs points at
  830.                     |  or the anchor block if Curs==NULL
  831.                     */
  832.  
  833.      if ((l1==NULL) || (l2==NULL))
  834.        return;
  835.      l1->bOK = l1->bOK && l2->bOK;
  836.      l2 ->bOK = TRUE;
  837.      if (l2->pitNext==l2) { /* no action needed */ }
  838.      else if (l1->pitNext==l1)
  839.      {  /* the easy way to code this would be simply to switch the two
  840.         |  pointers l1 and l2, but they are value parameters and we don't
  841.         |  want to change that.
  842.         */
  843.         SwitchLists(l1,l2);
  844.         return;
  845.      }
  846.      else
  847.      {  if(Curs==NULL) { pit = l1; }
  848.         else
  849.         {  MOVEBACK(Curs)
  850.            pit = (LIST)Curs;
  851.         }
  852.  
  853.         /* P points to a block to insert before, could be anchor */
  854.         pitB = pit->pitPrev;       /* Cannot be same as P, already checked */
  855.         l2->pitNext->pitPrev = pitB; /*  B<-- elems-of-L2    P */
  856.         l2->pitPrev->pitNext = pit;  /*  B<-- elems-of-L2 -->P */
  857.         pitB->pitNext = l2->pitNext; /*  B<-->elems-of-L2 -->P */
  858.         pit->pitPrev = l2->pitPrev;  /*  B<-->elems-of-L2<-->P */
  859.         l2->pitNext = l2;
  860.         l2->pitPrev = l2;
  861.      }
  862.   } /* List_InsertListBefore */
  863.  
  864.  
  865.   /*-----------------------------------------------------------------------
  866.   | Let l1 be l1 and l2 be l2
  867.   | Split l2 off from the front of l1:    final l2,l1 = original l1
  868.   |
  869.   | Split l1 into l2: objects of l1 up to and including Curs object
  870.   |               l1: objects of l1 after Curs
  871.   | Any original contents of l2 are freed.
  872.   | List_Spilt(l1, l2, NULL) splits l1 before the first object so l1 gets all.
  873.   | The elements themselves are not moved.
  874.    ------------------------------------------------------------------------*/
  875.   void APIENTRY List_SplitAfter(LIST l1, LIST l2, LPVOID Curs)
  876.   {  LIST pit;
  877.  
  878.      if ((l1==NULL) || (l2==NULL))
  879.        return;
  880.      if (l2->pitNext!=l2){ List_Clear(l2); };
  881.      if (Curs!=NULL)
  882.      {  MOVEBACK(Curs)
  883.         pit = (LIST)Curs;
  884.         /* Curs had better be an item in l1! l2 had better be created! */
  885.         if (pit==l1) { l1->bOK = FALSE; l2->bOK = FALSE; return; }
  886.         if (pit->pitNext==l1)
  887.         {  /* transfer whole of l2 to l1 */
  888.            SwitchLists(l2,l1);
  889.            return;
  890.         }
  891.         l2->pitPrev = pit;
  892.         l2->pitNext = l1->pitNext;
  893.         l1->pitNext = pit->pitNext;
  894.         pit->pitNext = l2;
  895.         l2->pitNext->pitPrev = l2;
  896.         l1->pitNext->pitPrev = l1;
  897.      }
  898.   } /* List_SplitAfter */
  899.  
  900.   /*----------------------------------------------------------------------
  901.   | Split l2 off from the back of l1:  final l1,l2 = original l1
  902.   |
  903.   | Split l1 into l1: objects of l1 up to but not including Curs object
  904.   |               l2: objects of l1 from Curs onwards
  905.   | Any original contants of l2 are freed.
  906.   | List_Spilt(l1, l2, NULL) splits l1 after the last object so l1 gets all.
  907.   | The elements themselves are not moved.
  908.    -----------------------------------------------------------------------*/
  909.   void APIENTRY List_SplitBefore(LIST l1, LIST l2, LPVOID Curs)
  910.   {  LIST pit;
  911.  
  912.      if ((l1==NULL) || (l2==NULL))
  913.        return;
  914.      if (l2->pitNext!=l2){ List_Clear(l2); }
  915.      if (Curs!=NULL)
  916.      {  MOVEBACK(Curs)
  917.         pit = (LIST)Curs;
  918.         /* Curs had better be an item in L1! L2 had better be created! */
  919.         if (pit==l1){ l1->bOK = FALSE; l2->bOK = FALSE; return; }
  920.         if (pit->pitPrev==l1) { SwitchLists(l2,l1); return; }
  921.         l2->pitNext = pit;
  922.         l2->pitPrev = l1->pitPrev;
  923.         l1->pitPrev = pit->pitPrev;
  924.         pit->pitPrev = l2;
  925.         l2->pitPrev->pitNext = l2;
  926.         l1->pitPrev->pitNext = l1;
  927.      }
  928.   } /* List_SplitBefore */
  929.  
  930.   /*------------------------------------------------------------------
  931.   | Return the number of items in L
  932.    -------------------------------------------------------------------*/
  933.   int APIENTRY List_Card(LIST lst)
  934.   {  LIST pit;     /* item cursor on lst */
  935.      int cit;
  936.  
  937.      if (lst==NULL)
  938.        return 0;    /* well it is sort of 0 */
  939.      pit = lst->pitNext;
  940.      cit = 0;
  941.      while(pit!=lst)
  942.         {  cit++;
  943.            pit = pit->pitNext;
  944.         }
  945.      return cit;
  946.   } /* List_Card */
  947.  
  948.   /*------------------------------------------------------------------
  949.   | Check return code
  950.    -------------------------------------------------------------------*/
  951.   BOOL APIENTRY List_IsOK(LIST lst)
  952.   {  if(lst==NULL)
  953.        return FALSE;       /* well it is sick ain't it! */
  954.      return lst->bOK;
  955.   } /* List_IsOK */
  956.  
  957.   /*------------------------------------------------------------------
  958.   | Set return code to good
  959.    -------------------------------------------------------------------*/
  960.   void APIENTRY List_MakeOK(LIST lst)
  961.   {  if(lst==NULL)
  962.        return;
  963.      lst->bOK = TRUE;
  964.   } /* List_MakeOK */
  965.  
  966.   BOOL APIENTRY List_Check(LIST lst)
  967.   { LIST pel;
  968.     BOOL bOK;
  969.     /*-----------------------------------------------------------------
  970.     | Check the anchor block has the Anchor flag set.
  971.     | Run through the LIST using the Anchor flag (which should be FALSE)
  972.     | to mark where we have been (to test for loops in the chain)
  973.     | and carry on until we see the Anchor flag again.  Check that this
  974.     | is the anchor block that we started from.  Now do another pass
  975.     | turning the Anchor flags off again and checking the Prev pointers.
  976.      -------------------------------------------------------------------*/
  977.     if(lst==NULL) return FALSE;  /* Should we trap?  Arguable */
  978.     bOK = lst->bAnchor;
  979.     pel = lst->pitNext;
  980.     while(! pel->bAnchor)
  981.     { pel->bAnchor = TRUE;
  982.       pel = pel->pitNext;
  983.     }
  984.     bOK = bOK && (pel==lst);
  985.     if(bOK)
  986.     { /* Turn all the bAnchor flags off */
  987.       pel = lst;
  988.       do
  989.       { pel->bAnchor = FALSE;
  990.         bOK = bOK & (pel->pitNext->pitPrev==pel);
  991.         pel = pel->pitNext;
  992.       } while (pel!=lst);
  993.       lst->bAnchor = TRUE;  /* except the real one */
  994.     }
  995.     else
  996.     { /* just turn off those that we set on */
  997.       pel = lst->pitNext;
  998.       while (pel->bAnchor)
  999.       { pel->bAnchor = FALSE;
  1000.         pel = pel->pitNext;
  1001.       }
  1002.       lst->bAnchor = TRUE;
  1003.     }
  1004.     return bOK;
  1005.   } /* List_Check */
  1006.  
  1007.  
  1008.   void APIENTRY List_Recover(PLIST plst)
  1009.   {  LIST Last, P,Q;
  1010.      BOOL OK;
  1011.     /* For no particular reason we presume that the forward chain
  1012.        is good and reconstruct the back chain from it.  A better
  1013.        algorithm would do the kind of things that List_Check does
  1014.        to figure out where the problems lie.  This just steps along
  1015.        until it sees either an address that it has already seen or
  1016.        else the anchor block.  (It's an n-squared algorithm).
  1017.        It links the last good block found back to the anchor and
  1018.        fixes all the Anchor flags.
  1019.     */
  1020.     if (plst==NULL) return;
  1021.     if (*plst==NULL)
  1022.     {  *plst = List_Create();
  1023.        return;
  1024.     }
  1025.     (*plst)->bAnchor = TRUE;
  1026.     P = (*plst)->pitNext;
  1027.     Last = *plst;
  1028.     for (; ; )
  1029.     {  if (P==*plst) break;
  1030.        Last = P;
  1031.        if (P->pitNext!=*plst)
  1032.        {   OK = TRUE;
  1033.            Q = *plst;
  1034.            for (; ; )
  1035.            {   OK &= (P->pitNext!=Q);
  1036.                if (Q==P) break;
  1037.                Q = Q->pitNext;
  1038.            }
  1039.            if (!OK) break;
  1040.        }
  1041.        P = P->pitNext;
  1042.     }
  1043.     P = *plst;
  1044.     while (P!=Last)
  1045.     {  P->pitNext->pitPrev = P;
  1046.        P->bAnchor = FALSE;
  1047.        P = P->pitNext;
  1048.     }
  1049.     Last->pitNext = *plst;
  1050.     (*plst)->pitPrev = Last;
  1051.     (*plst)->bAnchor = TRUE;
  1052.     (*plst)->bOK = TRUE;   /* Here's hoping! */
  1053.   } /* List_Recover */
  1054.