Subversion Repositories f9daq

Rev

Rev 17 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
16 f9daq 1
//-------------------------------------------------------------------------------------------
2
// klist.c - parts to maintain a doubly linked list (org microsoft)
3
//
4
// Please announce changes and hints to ARW Elektronik
5
// 
6
//
7
// $Log: Klist.c,v $
8
// Revision 1.2  2004/07/24 07:47:46  klaus
9
// revised, removed wrong license terms
10
//
11
// Revision 1.1.1.1  2003/11/14 23:17:18  klaus
12
// First put into repository
13
//
14
// Revision 1.2  2002/10/27 17:05:33  klaus
15
// CVS log added, file addressing bug > 2 Gbtye circumvent
16
//
17
// what                                                              who    when
18
// first steps                                                       AR     07.11.1999
19
//
20
 
21
//-------------------------------------------------------------------------------------------
22
// INCLUDES
23
//
24
#include <memory.h>
25
#include <windows.h>
26
#include <Klist.h>
27
 
28
//-------------------------------------------------------------------------------------------
29
// DEFINES
30
//
31
#define memcpy  memcpy
32
#define BLOCKSIZE 0x4000
33
 
34
//-------------------------------------------------------------------------------------------
35
// TYPEDEFS
36
//
37
typedef struct
38
{
39
        HANDLE hMem;   // memory handle for this block  
40
        int iInUse;    // number of allocations taken out of it.  0 => free it  
41
        int iNext;     // next byte to use  
42
        char chData[BLOCKSIZE];
43
} BLOCK, FAR *PBLOCK;
44
 
45
/* The following definition tells the truth about what an ITEM is.  The
46
|  header file says only that there's a structure with the tag item_tag and
47
|  that a LIST is a pointer to one.  Here we spell out what that structure
48
|  is (and a LIST is still a pointer to one).  A PLIST is defined as a
49
|  pointer to one of those, but is only really used because the C
50
|  parameter mechanism demands an extra level of indirection for a
51
|  parameter that can be updated.  (Modula-2 VAR parameter).
52
*/
53
typedef struct item_tag
54
{
55
        struct item_tag FAR *pitNext;    /* to next in circular list */
56
    struct item_tag FAR *pitPrev;    /* to prev in circular list */
57
    PBLOCK pBlock;               /* to memory block */
58
    BOOL bAnchor;                /* TRUE iff an anchor block */
59
    BOOL bOK;                    /* true unless a list op has failed */
60
    int iLen;                    /* length of data only */
61
    char Data[1];                /* the caller's data.  The '1' is a lie */
62
} ITEM;
63
 
64
/* For an anchor block, only the fields pitNext thru bAnchor are allocated.
65
|  For a normal list element, Data may well be longer than 1 byte.
66
|  The bOK flag is to support a style of programming where several
67
|  successive operations can be done without having to check the return
68
|  code at each stage.  At the end, the list can be examined to see if
69
|  the data in it is valid or if it has been made invalid by the failure
70
|  of any of the previous operations.  Certain operations may result in
71
|  having no list at all if they fail (e.g. create) and for these, you'd
72
|  better check the result at once!
73
|  ??? Some of this screed belongs in the header!!!
74
*/
75
 
76
//-------------------------------------------------------------------------------------------
77
// LOCALS
78
//
79
static CRITICAL_SECTION CritSec;  /* to protect pCurrent */
80
 
81
#define List_Enter_Crit(x)      EnterCriticalSection(x)
82
#define List_Leave_Crit(x)      LeaveCriticalSection(x)
83
 
84
static PBLOCK pCurrent = NULL;  // block currently in use  
85
                          // must always be either NULL or valid  
86
 
87
static int iAnchorSize;      /* Size of anchor block (no data, no dummy) */
88
static int iHeaderSize;      /* Size of data block not counting Data
89
                              and offset from cursor back to item.       */
90
static BOOL bInited = FALSE; /* TRUE <=> iAnchorSize and iHeaderSize are OK*/
91
 
92
#define MOVEBACK(Curs)                                               \
93
   { Curs = ((char FAR *)Curs-iHeaderSize); } /*move from Data to pitNext*/
94
 
95
//-------------------------------------------------------------------------------------------
96
// EXTERNALS
97
//
98
 
99
//-------------------------------------------------------------------------------------------
100
// GLOBALS
101
//
102
 
103
//-------------------------------------------------------------------------------------------
104
// FUNCTIONS
105
//
106
 
107
/* Allocate storage for List elements.  n.b. after a call to this
108
   you MUST record the value of pCurrent as you need to hand that in
109
   to Free.  You don't hand in the value of the actual storage.
110
   See screed above.
111
   This function Enters the critical section.  The caller must Leave it.
112
*/
113
static LPVOID Alloc(int size)
114
{
115
        HANDLE hMem;
116
        LPVOID pRet;
117
        List_Enter_Crit(&CritSec);
118
        if ((pCurrent==NULL)||(pCurrent->iNext+size>BLOCKSIZE+1))
119
        {
120
                hMem = GlobalAlloc(GMEM_MOVEABLE|GMEM_SHARE,(DWORD)(sizeof(BLOCK)));
121
                if (hMem==NULL)
122
                {
123
                        pCurrent = NULL;
124
                        OutputDebugString("GlobalAlloc failed!!\n");
125
                        return NULL;
126
                }
127
                pCurrent = (PBLOCK)GlobalLock(hMem);
128
                if (pCurrent==NULL)
129
                {
130
                        OutputDebugString("GlobalLock failed!!\n");
131
                        return NULL;
132
                }
133
                pCurrent->hMem = hMem;
134
                pCurrent->iInUse = 0;
135
                pCurrent->iNext = 0;
136
        }
137
        pRet = &(pCurrent->chData[pCurrent->iNext]);
138
        ++(pCurrent->iInUse);
139
        pCurrent->iNext += size;
140
 
141
        // ensure that the data is aligned 4 byte 
142
        pCurrent->iNext += 3;
143
        pCurrent->iNext -= pCurrent->iNext % 4;
144
 
145
        return pRet;
146
}
147
 
148
static void Free(PBLOCK pBlock, LPVOID p)
149
{
150
        HANDLE hMem;
151
        List_Enter_Crit(&CritSec);
152
    --pBlock->iInUse;
153
        if (pBlock->iInUse<=0)
154
        {
155
                if (pBlock->iInUse<0)
156
                {
157
                        // don't know what to do with it 
158
                }
159
 
160
                hMem = pBlock->hMem;
161
                GlobalUnlock(hMem);
162
                GlobalFree(hMem);
163
                if (pCurrent==pBlock) pCurrent = NULL; /* defend the invariant */
164
        }
165
        List_Leave_Crit(&CritSec);
166
}
167
 
168
  /*==================================================================
169
  || Lists are circular, doubly linked with an anchor block which holds
170
  || pointers to both ends.  Every block has a flag which shows whether
171
  || it's an anchor or not.
172
  ||
173
  || Empty list:
174
  ||
175
  ||      -------------
176
  ||     |             |
177
  ||     |   Anchor    |
178
  ||     v   -------   |
179
  ||  Ul--->| Next--+--|
180
  ||        |-------|  |
181
  ||        | Prev--+--
182
  ||         -------
183
  ||
184
  || One entry list:
185
  ||
186
  ||      ------------------------------------
187
  ||     |                                    |
188
  ||     |   Anchor                           |
189
  ||     v   -------                ------    |
190
  ||  Ul--->| Next--+------------->| Next-+---|
191
  ||        |-------|    |         |------|   |
192
  ||        | Prev--+----          | Prev-+---
193
  ||         -------               |------|
194
  ||                               | Len  |
195
  ||                               |------|
196
  ||                               | Data |
197
  ||                                ------
198
  || Two entry list:
199
  ||
200
  ||      -------------------------------------------------
201
  ||     | ---------------    ---------------              |
202
  ||     ||               |  |               |             |
203
  ||     ||  Anchor       |  |               |             |
204
  ||     vv  --------     |  v    ------     |    ------   |
205
  ||  Ul--->| Next--+-----+----->| Next-+----+-->| Next-+--
206
  ||        |-------|     |      |------|  | |   |------|
207
  ||        | Prev--+--    ------+-Prev |  |  ---+-Prev |
208
  ||         -------   |         |------|  |     |------|
209
  ||                   |         | Len  |  |     | Len  |
210
  ||                   |         |------|  |     |------|<----Cursor
211
  ||                   |         | Data |  |     | Data |
212
  ||                   |          ------   |      ------
213
  ||                   |                   |
214
  ||                    -------------------
215
  ||
216
  || etc.
217
  ||
218
  || Note that an external cursor (i.e one which is seen by the caller)
219
  || points to the Data field, not to the start of the structure.
220
  || This allows easy access to the data by the user at the cost of a
221
  || slightly slower traverse.
222
  || Within this module, we may sometimes traverse a list with  a cursor
223
  || that points to the start of an item.  This is called an item cursor.
224
  È===================================================================*/
225
 
226
  /*------------------------------------------------------------------
227
  | Set iAnchorSize and iHeaderSize.  Implementation independent!
228
   -------------------------------------------------------------------*/
229
void APIENTRY List_Init(void)
230
{  
231
        LIST P;
232
 
233
    P = (LIST)&P;                  /* really any old address will do */
234
    iAnchorSize = (char FAR *)&(P->iLen) - (char FAR *)&(P->pitNext);
235
    iHeaderSize = (char FAR *)&(P->Data) - (char FAR *)&(P->pitNext);
236
    InitializeCriticalSection(&CritSec);
237
    /* assumes layout in storage is linear */
238
}
239
 
240
  /*------------------------------------------------------------------
241
  | Create a list.  It will be initially empty
242
   -------------------------------------------------------------------*/
243
LIST APIENTRY List_Create(void)
244
{  
245
        LIST lst;
246
 
247
    if (!bInited) {List_Init(); }          /* prevent some silly errors */
248
    lst = Alloc(iAnchorSize);
249
    if (lst==NULL) { return NULL; }
250
    lst->pBlock = pCurrent;
251
    List_Leave_Crit(&CritSec);
252
    lst->bOK = TRUE;
253
    lst->pitNext = lst;
254
    lst->pitPrev = lst;
255
    lst->bAnchor = TRUE;
256
    /* no length field set in an anchor block */
257
    return lst;
258
}
259
 
260
  /*------------------------------------------------------------------
261
  | Destroy *plst.  It does not need to be empty first
262
   -------------------------------------------------------------------*/
263
void APIENTRY List_Destroy(PLIST plst)
264
{  
265
        LIST pitP;    /* item cursor on * plst */
266
    LIST pitQ;    /* item cursor runs one step ahead of pitQ */
267
 
268
    if (plst==NULL)
269
       return;
270
    /* There is at least an anchor block to destroy */
271
    pitP = *plst;
272
    do
273
    {  
274
                pitQ = pitP->pitNext;
275
        Free(pitP->pBlock, pitP);
276
        pitP = pitQ;
277
    }while(pitP != *plst);
278
    *plst = NULL;
279
}
280
 
281
   /*------------------------------------------------------------------
282
  | Return the address of the place for Len bytes of data in a new
283
  | item at the start of lst
284
   -------------------------------------------------------------------*/
285
LPVOID APIENTRY List_NewFirst(LIST lst, UINT uLen)
286
{  
287
        LIST pit;
288
 
289
    if (lst==NULL)
290
       return NULL;
291
    pit = Alloc(iHeaderSize+uLen);
292
    if (pit==NULL) { lst->bOK = FALSE; return NULL; }
293
    pit->pBlock = pCurrent;
294
    List_Leave_Crit(&CritSec);
295
    pit->iLen = uLen;
296
    pit->pitPrev = lst;
297
    pit->pitNext = lst->pitNext;
298
    lst->pitNext->pitPrev = pit; /* for empty list that set lst->pitPrev */
299
    lst->pitNext = pit;
300
    pit->bAnchor = FALSE;
301
    return (char FAR *)&(pit->Data);
302
}
303
 
304
 
305
  /*------------------------------------------------------------------
306
  | Delete the item that Curs identifies.
307
  | This will be only a few (maybe as little as 3) machine instructions
308
  | quicker than DeleteForwards or DeleteBackwards but leaves Curs dangling.
309
  | It is therefore NOT usually to be preferred.
310
  | It may be useful when you have a function which returns an LPVOID
311
  | since the argument does not need to be a variable.
312
  |     Trivial example: List_Delete(List_First(L));
313
   -------------------------------------------------------------------*/
314
void APIENTRY List_Delete(LPVOID Curs)
315
{  
316
        LIST pit;
317
 
318
    if(Curs==NULL)
319
       return;
320
    MOVEBACK(Curs)
321
    pit = (LIST)Curs;
322
    pit->pitNext->pitPrev = pit->pitPrev;
323
    pit->pitPrev->pitNext = pit->pitNext;
324
    Free(pit->pBlock, pit);
325
}
326
 
327
 
328
  /*---------------------------------------------------------------------
329
  | Return TRUE if and only if lst is empty
330
   ----------------------------------------------------------------------*/
331
BOOL APIENTRY List_IsEmpty(LIST lst)
332
{  
333
        if (lst==NULL)
334
       return TRUE;   /* well it's sort of true isn't it? */
335
    return lst->pitNext ==lst;
336
}
337