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