//-------------------------------------------------------------------------------------------
// klist.c - parts to maintain a doubly linked list (org microsoft)
//
// Please announce changes and hints to ARW Elektronik
//
//
// $Log: Klist.c,v $
// Revision 1.2 2004/07/24 07:47:46 klaus
// revised, removed wrong license terms
//
// Revision 1.1.1.1 2003/11/14 23:17:18 klaus
// First put into repository
//
// Revision 1.2 2002/10/27 17:05:33 klaus
// CVS log added, file addressing bug > 2 Gbtye circumvent
//
// what who when
// first steps AR 07.11.1999
//
//-------------------------------------------------------------------------------------------
// INCLUDES
//
#include <memory.h>
#include <windows.h>
#include <Klist.h>
//-------------------------------------------------------------------------------------------
// DEFINES
//
#define memcpy memcpy
#define BLOCKSIZE 0x4000
//-------------------------------------------------------------------------------------------
// TYPEDEFS
//
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;
/* 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!!!
*/
//-------------------------------------------------------------------------------------------
// LOCALS
//
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
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*/
//-------------------------------------------------------------------------------------------
// EXTERNALS
//
//-------------------------------------------------------------------------------------------
// GLOBALS
//
//-------------------------------------------------------------------------------------------
// FUNCTIONS
//
/* 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;
// ensure that the data is aligned 4 byte
pCurrent->iNext += 3;
pCurrent->iNext -= pCurrent->iNext % 4;
return pRet;
}
static void Free(PBLOCK pBlock, LPVOID p)
{
HANDLE hMem;
List_Enter_Crit(&CritSec);
--pBlock->iInUse;
if (pBlock->iInUse<=0)
{
if (pBlock->iInUse<0)
{
// don't know what to do with it
}
hMem = pBlock->hMem;
GlobalUnlock(hMem);
GlobalFree(hMem);
if (pCurrent==pBlock) pCurrent = NULL; /* defend the invariant */
}
List_Leave_Crit(&CritSec);
}
/*==================================================================
|| 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.
È===================================================================*/
/*------------------------------------------------------------------
| Set iAnchorSize and iHeaderSize. Implementation independent!
-------------------------------------------------------------------*/
void APIENTRY List_Init(void)
{
LIST P;
P = (LIST)&P; /* really any old address will do */
iAnchorSize = (char FAR *)&(P->iLen) - (char FAR *)&(P->pitNext);
iHeaderSize = (char FAR *)&(P->Data) - (char FAR *)&(P->pitNext);
InitializeCriticalSection(&CritSec);
/* assumes layout in storage is linear */
}
/*------------------------------------------------------------------
| Create a list. It will be initially empty
-------------------------------------------------------------------*/
LIST APIENTRY List_Create(void)
{
LIST lst;
if (!bInited) {List_Init(); } /* prevent some silly errors */
lst = Alloc(iAnchorSize);
if (lst==NULL) { return NULL; }
lst->pBlock = pCurrent;
List_Leave_Crit(&CritSec);
lst->bOK = TRUE;
lst->pitNext = lst;
lst->pitPrev = lst;
lst->bAnchor = TRUE;
/* no length field set in an anchor block */
return lst;
}
/*------------------------------------------------------------------
| Destroy *plst. It does not need to be empty first
-------------------------------------------------------------------*/
void APIENTRY List_Destroy(PLIST plst)
{
LIST pitP; /* item cursor on * plst */
LIST pitQ; /* item cursor runs one step ahead of pitQ */
if (plst==NULL)
return;
/* There is at least an anchor block to destroy */
pitP = *plst;
do
{
pitQ = pitP->pitNext;
Free(pitP->pBlock, pitP);
pitP = pitQ;
}while(pitP != *plst);
*plst = NULL;
}
/*------------------------------------------------------------------
| Return the address of the place for Len bytes of data in a new
| item at the start of lst
-------------------------------------------------------------------*/
LPVOID APIENTRY List_NewFirst(LIST lst, UINT uLen)
{
LIST pit;
if (lst==NULL)
return NULL;
pit = Alloc(iHeaderSize+uLen);
if (pit==NULL) { lst->bOK = FALSE; return NULL; }
pit->pBlock = pCurrent;
List_Leave_Crit(&CritSec);
pit->iLen = uLen;
pit->pitPrev = lst;
pit->pitNext = lst->pitNext;
lst->pitNext->pitPrev = pit; /* for empty list that set lst->pitPrev */
lst->pitNext = pit;
pit->bAnchor = FALSE;
return (char FAR *)&(pit->Data);
}
/*------------------------------------------------------------------
| Delete the item that Curs identifies.
| This will be only a few (maybe as little as 3) machine instructions
| quicker than DeleteForwards or DeleteBackwards but leaves Curs dangling.
| It is therefore NOT usually to be preferred.
| It may be useful when you have a function which returns an LPVOID
| since the argument does not need to be a variable.
| Trivial example: List_Delete(List_First(L));
-------------------------------------------------------------------*/
void APIENTRY List_Delete(LPVOID Curs)
{
LIST pit;
if(Curs==NULL)
return;
MOVEBACK(Curs)
pit = (LIST)Curs;
pit->pitNext->pitPrev = pit->pitPrev;
pit->pitPrev->pitNext = pit->pitNext;
Free(pit->pBlock, pit);
}
/*---------------------------------------------------------------------
| Return TRUE if and only if lst is empty
----------------------------------------------------------------------*/
BOOL APIENTRY List_IsEmpty(LIST lst)
{
if (lst==NULL)
return TRUE; /* well it's sort of true isn't it? */
return lst->pitNext ==lst;
}