list.c

<Win2k系统编程>源码.次数为国人自编,内容丰富,还是不错的.

/****************************** Module Header *******************************
* Module Name: LIST.C
*
*
* Functions:
*
* Alloc()
* Free()
* List_Init()
* List_Dump()
* List_Show()
* List_Create()
* List_Destroy()
* List_AddFirst()
* List_NewFirst()
* List_DeleteFirst()
* List_AddLast()
* List_NewLast()
* LIst_DeleteLast()
* List_AddAfter()
* List_NewAfter()
* List_AddBefore()
* List_NewBefore()
* List_Delete()
* List_DeleteForwards()
* List_DeleteBackwards()
* List_ItemLength()
* List_First()
* List_Last()
* List_Next()
* List_Prev()
* List_Clear()
* List_IsEmpty()
* SwitchLists()
* List_Join()
* List_InsertListAfter()
* List_InsertListBefore()
* List_SplitAfter()
* List_SplitBefore()
* List_Card()
* List_IsOK()
* LIst_MakeOK()
* List_Check()
* List_Recover()
*
* Comments:
*
*
****************************************************************************/

#include <memory.h>
#include <windows.h>

#include "gutils.h"
#include "list.h"
#include "gutilsrc.h"

#define memcpy  memcpy

char msg[80];  /* a temp for building up wsprintf messages in */

#define BLOCKSIZE 25000
 typedef struct
 { HANDLE hMem;     /* memory handle for this block */
   int iInUse;    /* number of allocations taken out of it.  0 => free it */
   int iNext;     /* next byte to use */
   char chData[BLOCKSIZE];
 } BLOCK, FAR *PBLOCK;

static CRITICAL_SECTION CritSec;  /* to protect pCurrent */
#define List_Enter_Crit(x)      EnterCriticalSection(x)
#define List_Leave_Crit(x)      LeaveCriticalSection(x)

static PBLOCK pCurrent = NULL;  /* block currently in use */
                          /* must always be either NULL or valid */

 /* Allocate storage for List elements.  n.b. after a call to this
    you MUST record the value of pCurrent as you need to hand that in
    to Free.  You don't hand in the value of the actual storage.
    See screed above.
    This function Enters the critical section.  The caller must Leave it.
 */
static LPVOID Alloc(int size)
 { HANDLE hMem;
   LPVOID pRet;
   List_Enter_Crit(&CritSec);
   if ((pCurrent==NULL)||(pCurrent->iNext+size>BLOCKSIZE+1))
   { hMem = GlobalAlloc(GMEM_MOVEABLE|GMEM_SHARE,(DWORD)(sizeof(BLOCK)));
     if (hMem==NULL)
       { pCurrent = NULL;
         OutputDebugString("GlobalAlloc failed!!\n");
         return NULL;
       }
     pCurrent = (PBLOCK)GlobalLock(hMem);
     if (pCurrent==NULL)
       { OutputDebugString("GlobalLock failed!!\n");
         return NULL;
       }
     pCurrent->hMem = hMem;
     pCurrent->iInUse = 0;
     pCurrent->iNext = 0;
   }
   pRet = &(pCurrent->chData[pCurrent->iNext]);
   ++(pCurrent->iInUse);
   pCurrent->iNext += size;

   /* for MIPS we must also ensure that the data is aligned 4 byte*/
   pCurrent->iNext += 3;
   pCurrent->iNext -= pCurrent->iNext % 4;

   return pRet;
 } /* Alloc */

static void Free(PBLOCK pBlock, LPVOID p)
 { HANDLE hMem;
   List_Enter_Crit(&CritSec);
    --pBlock->iInUse;
   if (pBlock->iInUse<=0)
   { if (pBlock->iInUse<0)
     { 
        extern HANDLE hLibInst;
        TCHAR szBuf[512];
        LoadString(hLibInst, IDS_LIST_ALLOC_NEGATIVE, szBuf, sizeof(szBuf));
 
        wsprintf(msg, szBuf, pBlock->iInUse);
        MessageBox(NULL, msg, NULL, MB_OK | MB_ICONSTOP);
      }
 
     hMem = pBlock->hMem;
     GlobalUnlock(hMem);
     GlobalFree(hMem);
     if (pCurrent==pBlock) pCurrent = NULL; /* defend the invariant */
   }
   List_Leave_Crit(&CritSec);
 } /* Free */

  /* The following definition tells the truth about what an ITEM is.  The
  |  header file says only that there's a structure with the tag item_tag and
  |  that a LIST is a pointer to one.  Here we spell out what that structure
  |  is (and a LIST is still a pointer to one).  A PLIST is defined as a
  |  pointer to one of those, but is only really used because the C
  |  parameter mechanism demands an extra level of indirection for a
  |  parameter that can be updated.  (Modula-2 VAR parameter).
  */
  typedef struct item_tag
  { struct item_tag FAR *pitNext;    /* to next in circular list */
    struct item_tag FAR *pitPrev;    /* to prev in circular list */
    PBLOCK pBlock;               /* to memory block */
    BOOL bAnchor;                /* TRUE iff an anchor block */
    BOOL bOK;                    /* true unless a list op has failed */
    int iLen;                    /* length of data only */
    char Data[1];                /* the caller's data.  The '1' is a lie */
  } ITEM;

  /* For an anchor block, only the fields pitNext thru bAnchor are allocated.
  |  For a normal list element, Data may well be longer than 1 byte.
  |  The bOK flag is to support a style of programming where several
  |  successive operations can be done without having to check the return
  |  code at each stage.  At the end, the list can be examined to see if
  |  the data in it is valid or if it has been made invalid by the failure
  |  of any of the previous operations.  Certain operations may result in
  |  having no list at all if they fail (e.g. create) and for these, you'd
  |  better check the result at once!
  |  ??? Some of this screed belongs in the header!!!
  */

  static int iAnchorSize;      /* Size of anchor block (no data, no dummy) */
  static int iHeaderSize;      /* Size of data block not counting Data
                                  and offset from cursor back to item.
                               */
  static BOOL bInited = FALSE; /* TRUE <=> iAnchorSize and iHeaderSize are OK*/

#define MOVEBACK(Curs)                                               \
   { Curs = ((char FAR *)Curs-iHeaderSize); } /*move from Data to pitNext*/

  /*==================================================================
  || Lists are circular, doubly linked with an anchor block which holds
  || pointers to both ends.  Every block has a flag which shows whether
  || it's an anchor or not.
  ||
  || Empty list:
  ||
  ||      -------------
  ||     |             |
  ||     |   Anchor    |
  ||     v   -------   |
  ||  Ul--->| Next--+--|
  ||        |-------|  |
  ||        | Prev--+--
  ||         -------
  ||
  || One entry list:
  ||
  ||      ------------------------------------
  ||     |                                    |
  ||     |   Anchor                           |
  ||     v   -------                ------    |
  ||  Ul--->| Next--+------------->| Next-+---|
  ||        |-------|    |         |------|   |
  ||        | Prev--+----          | Prev-+---
  ||         -------               |------|
  ||                               | Len  |
  ||                               |------|
  ||                               | Data |
  ||                                ------
  || Two entry list:
  ||
  ||      -------------------------------------------------
  ||     | ---------------    ---------------              |
  ||     ||               |  |               |             |
  ||     ||  Anchor       |  |               |             |
  ||     vv  --------     |  v    ------     |    ------   |
  ||  Ul--->| Next--+-----+----->| Next-+----+-->| Next-+--
  ||        |-------|     |      |------|  | |   |------|
  ||        | Prev--+--    ------+-Prev |  |  ---+-Prev |
  ||         -------   |         |------|  |     |------|
  ||                   |         | Len  |  |     | Len  |
  ||                   |         |------|  |     |------|<----Cursor
  ||                   |         | Data |  |     | Data |
  ||                   |          ------   |      ------
  ||                   |                   |
  ||                    -------------------
  ||
  || etc.
  ||
  || Note that an external cursor (i.e one which is seen by the caller)
  || points to the Data field, not to the start of the structure.
  || This allows easy access to the data by the user at the cost of a
  || slightly slower traverse.
  || Within this module, we may sometimes traverse a list with  a cursor
  || that points to the start of an item.  This is called an item cursor.