![[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.