![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to linklist.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [WindowsNT SDKs] / mstools / samples / deb|
Return to linklist.c CVS log | Up to [WindowsNT SDKs] / mstools / samples / deb |
1.1.1.3 ! 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: 1.1 root 12: // ************************************************************************ 1.1.1.3 ! root 13: // MODULE : LinkList.C - Ordered Double Linked List Package ! 14: // PURPOSE : Provide a general, sorted, double linked list package 1.1.1.2 root 15: // FUNCTIONS : 1.1.1.3 ! root 16: // CreateList - allocate memory for a new list, registers the ! 17: // ordering function ! 18: // CreateNode - allocate memory fpr a new node that can be put ! 19: // into the linked list 1.1 root 20: // InsertNode - insert a new node into the list 1.1.1.3 ! root 21: // SetCurrentNode - finds the 1st occurence of a node that matches ! 22: // a key(s) according to the match function ! 23: // and sets it as the current node ! 24: // SetCurrentNodeEx - finds the Nth occurence of a node that matches ! 25: // a key(s) according to the match function ! 26: // and sets it as the current node ! 27: // GetCurrentNode - get the current node ! 28: // GetFirstNode - get the first (left-most) node in the list ! 29: // GetLastNode - get the last (right-most) node in the list ! 30: // GetNextNode - get the next (right) node from the current ! 31: // GetPrevNode - get the previous (left) node from the current ! 32: // DeleteCurrentNode - deletes the current node from the list and ! 33: // frees the memory associated with it ! 34: // DestroyNode - deallocates the memory associated with a node ! 35: // DestroyList - deallocates the memory associated with a list, ! 36: // does not delete any of the nodes ! 37: // GetListError - gets the current list error 1.1 root 38: // 1.1.1.3 ! root 39: // COMMENTS : The application must serialize access to the linked list 1.1 root 40: // 41: // Format of the Ordering and Matching functions is as follows: 1.1.1.3 ! root 42: // ----------------------------------------------------------- 1.1 root 43: // 44: // int OrderFunc( PNODE pNodeOne, PNODE pNodeTwo ) 45: // { 1.1.1.3 ! root 46: // if( (pNodeOne->pNodeData).SortKey < (pNodeTwo->pNodeData).SortKey ) ! 47: // return( LIST_LEFT_OF ); ! 48: // if( (pNodeOne->pNodeData).SortKey == (pNodeTwo->pNodeData).SortKey ) ! 49: // return( LIST_MATCH ); ! 50: // if( (pNodeOne->pNodeData).SortKey > (pNodeTwo->pNodeData).SortKey ) ! 51: // return( LIST_RIGHT_OF ); 1.1 root 52: // } 53: // 54: // ************************************************************************ 55: #include <StdLib.H> // malloc(), free() 56: #include "LinkList.H" 57: 58: //-- NULL pointer dereferencing checking macro 1.1.1.3 ! root 59: #define CHECK_POINTER( ppNode ) \ ! 60: if( ppNode == NULL ) { \ ! 61: return( pList->ListError = LIST_ERROR_DEREFERENCE_NULL ); \ 1.1 root 62: } 63: 64: // ************************************************************************ 1.1.1.3 ! root 65: // FUNCTION : CreateList( PLIST* ppList, int (*)(PNODE, PNODE) ) ) ! 66: // PURPOSE : allocate a new list, registers the ordering function ! 67: // COMMENTS : sets all pointers to NULL 1.1 root 68: // ************************************************************************ 1.1.1.3 ! root 69: BOOL ! 70: CreateList( PLIST* ppList, int (*OrderFunction)( PNODE pNodeOne, PNODE pNodeTwo ) ) 1.1 root 71: { 1.1.1.3 ! root 72: *ppList = (PLIST) malloc( sizeof(LIST) ); ! 73: if( ppList == NULL ) { ! 74: (*ppList)->ListError = LIST_NO_ERROR; ! 75: return( FALSE ); 1.1 root 76: } 77: 78: //-- register the link list data ordering function 1.1.1.3 ! root 79: (*ppList)->OrderFunction = OrderFunction; 1.1 root 80: 1.1.1.3 ! root 81: //-- initialize the general linked list node pointers to NULL ! 82: (*ppList)->pFirstNode = NULL; ! 83: (*ppList)->pCurrentNode = NULL; ! 84: (*ppList)->pLastNode = NULL; ! 85: ! 86: //-- indicate no error ! 87: (*ppList)->ListError = LIST_NO_ERROR; ! 88: ! 89: return( TRUE ); 1.1 root 90: } 91: 92: 93: // ************************************************************************ 1.1.1.3 ! root 94: // FUNCTION : CreateNode( PNODE* ) 1.1 root 95: // PURPOSE : create/allocate a new node that can be put into list 96: // COMMENTS : 97: // ************************************************************************ 1.1.1.3 ! root 98: BOOL ! 99: CreateNode( PNODE* ppNewNode ) 1.1 root 100: { 1.1.1.3 ! root 101: *ppNewNode = (PNODE) malloc( sizeof(NODE) ); ! 102: if( *ppNewNode == NULL ) { ! 103: return( FALSE ); 1.1 root 104: } 105: 1.1.1.3 ! root 106: //-- initialize the node pointers to NULL ! 107: (*ppNewNode)->pRightLink = NULL; ! 108: (*ppNewNode)->pLeftLink = NULL; ! 109: ! 110: return( TRUE ); 1.1 root 111: } 112: 113: 114: // ************************************************************************ 115: // FUNCTION : InsertNode( PLIST pList, PNODE ) 116: // PURPOSE : insert a new node into the list 1.1.1.3 ! root 117: // COMMENTS : ! 118: // All nodes must have a unique key entry (from order function), if a ! 119: // match is found during an insert then the old node gets replaced with ! 120: // the new node. ! 121: // ! 122: // NOTE: changes pList->pCurrentNode 1.1 root 123: // ************************************************************************ 1.1.1.3 ! root 124: BOOL 1.1 root 125: InsertNode( PLIST pList, PNODE pNewNode ) 126: { 127: int Position; 128: int LastPosition; 129: 1.1.1.3 ! root 130: //-- if this is the first node in a new list ! 131: if( pList->pFirstNode == NULL ) { ! 132: pList->pFirstNode = pNewNode; ! 133: pList->pLastNode = pNewNode; ! 134: pList->pCurrentNode = pNewNode; ! 135: pList->ListError = LIST_NO_ERROR; ! 136: return( TRUE ); 1.1 root 137: } 138: 139: Position = (*(pList->OrderFunction))( pNewNode, pList->pCurrentNode ); 140: 141: //-- search for insertion point 1.1.1.3 ! root 142: while( pList->pCurrentNode != NULL ) { 1.1 root 143: 144: LastPosition = Position; 145: Position = (*(pList->OrderFunction))(pNewNode, pList->pCurrentNode); 146: 1.1.1.3 ! root 147: if( pList->pFirstNode == pList->pLastNode ) 1.1 root 148: break; 149: 150: if( Position != LastPosition ) 151: break; 152: 1.1.1.3 ! root 153: if( pList->pCurrentNode == pList->pFirstNode ) { ! 154: if( Position == LIST_RIGHT_OF ) { ! 155: pList->pCurrentNode = pList->pCurrentNode->pRightLink; 1.1 root 156: continue; 157: } 158: break; 159: } 160: 1.1.1.3 ! root 161: if( pList->pCurrentNode == pList->pLastNode ) { ! 162: if( Position == LIST_LEFT_OF ) { ! 163: pList->pCurrentNode = pList->pCurrentNode->pLeftLink; 1.1 root 164: continue; 165: } 166: break; 167: } 168: 169: if( Position == LastPosition ) { 1.1.1.3 ! root 170: if( Position == LIST_LEFT_OF) { ! 171: pList->pCurrentNode = pList->pCurrentNode->pLeftLink; 1.1 root 172: continue; 173: } 1.1.1.3 ! root 174: if( Position == LIST_RIGHT_OF ) { ! 175: pList->pCurrentNode = pList->pCurrentNode->pRightLink; 1.1 root 176: continue; 177: } 178: break; 179: } 180: 181: } 182: 183: //-- now, insert the pNewNode 184: switch( Position ) { 185: 1.1.1.3 ! root 186: case LIST_LEFT_OF: ! 187: pNewNode->pRightLink = pList->pCurrentNode; ! 188: pNewNode->pLeftLink = pList->pCurrentNode->pLeftLink; ! 189: if( pList->pCurrentNode == pList->pFirstNode ) ! 190: pList->pFirstNode = pNewNode; 1.1 root 191: else 1.1.1.3 ! root 192: pList->pCurrentNode->pLeftLink->pRightLink = pNewNode; ! 193: pList->pCurrentNode->pLeftLink = pNewNode; 1.1 root 194: break; 195: 1.1.1.3 ! root 196: #if 1 // replace duplicates with new data ! 197: ! 198: case LIST_MATCH: ! 199: pNewNode->pLeftLink = pList->pCurrentNode->pLeftLink; ! 200: pNewNode->pRightLink = pList->pCurrentNode->pRightLink; ! 201: if( pList->pCurrentNode == pList->pLastNode ) ! 202: pList->pLastNode = pNewNode; 1.1 root 203: else 1.1.1.3 ! root 204: pList->pCurrentNode->pRightLink->pLeftLink = pNewNode; ! 205: if( pList->pCurrentNode == pList->pFirstNode ) ! 206: pList->pFirstNode = pNewNode; ! 207: else ! 208: pList->pCurrentNode->pLeftLink->pRightLink = pNewNode; ! 209: // note: doesn't destroy extra data associated with the node ! 210: DestroyNode( pList->pCurrentNode ); 1.1 root 211: break; 212: 1.1.1.3 ! root 213: #else // or allow duplicates ! 214: ! 215: case LIST_MATCH: ! 216: ! 217: #endif ! 218: ! 219: case LIST_RIGHT_OF: ! 220: pNewNode->pLeftLink = pList->pCurrentNode; ! 221: pNewNode->pRightLink = pList->pCurrentNode->pRightLink; ! 222: if( pList->pCurrentNode == pList->pLastNode ) ! 223: pList->pLastNode = pNewNode; ! 224: else ! 225: pList->pCurrentNode->pRightLink->pLeftLink = pNewNode; ! 226: pList->pCurrentNode->pRightLink = pNewNode; 1.1 root 227: break; 228: 229: } 1.1.1.3 ! root 230: pList->pCurrentNode = pNewNode; ! 231: pList->ListError = LIST_NO_ERROR; 1.1 root 232: 1.1.1.3 ! root 233: return( TRUE ); 1.1 root 234: } 235: 236: 237: // ************************************************************************ 1.1.1.3 ! root 238: // FUNCTION : SetCurrentNode( PLIST pList, PNODE, int (*)(PNODE, PNODE) ) ! 239: // PURPOSE : finds the first occurence of a node from the list that matches ! 240: // a key(s) according to the match function. 1.1 root 241: // COMMENTS : 1.1.1.3 ! root 242: // May use the ordering function or a new matching function if not ! 243: // searching for a match based on the primary ordering key. ! 244: // NOTE: the matching and ordering functions have the same definition. ! 245: // NOTE: changes pList->pCurrentNode. ! 246: // ************************************************************************ ! 247: BOOL ! 248: SetCurrentNode( PLIST pList, PNODE pKeyNode, ! 249: int (*MatchFunction)( PNODE pNodeOne, PNODE pNodeTwo ) ) 1.1 root 250: { 1.1.1.3 ! root 251: return( SetCurrentNodeEx( pList, pKeyNode, MatchFunction, 1 ) ); 1.1 root 252: } 253: 254: 255: // ************************************************************************ 1.1.1.3 ! root 256: // FUNCTION : SetCurrentNodeEx( PLIST pList, PNODE, int (*)(PNODE, PNODE), int ) ! 257: // PURPOSE : finds the Nth occurence of a node from the list that matches ! 258: // a key(s) according to the match function. ! 259: // COMMENTS : ! 260: // May use the ordering function or a new matching function if not ! 261: // searching for a match based on the primary ordering key. ! 262: // NOTE: the matching and ordering functions have the same definition. ! 263: // NOTE: changes pList->pCurrentNode. ! 264: // ************************************************************************ ! 265: BOOL ! 266: SetCurrentNodeEx( PLIST pList, PNODE pKeyNode, ! 267: int (*MatchFunction)( PNODE pNodeOne, PNODE pNodeTwo ), ! 268: int Occurence ) 1.1 root 269: { 1.1.1.3 ! root 270: int Position; 1.1 root 271: 1.1.1.3 ! root 272: //-- if list is empty, exit ! 273: if( pList->pCurrentNode == NULL ) { ! 274: pList->ListError = LIST_ERROR_NO_NODE; ! 275: return( FALSE ); ! 276: } 1.1 root 277: 1.1.1.3 ! root 278: //-- if match and order are same function ! 279: if( MatchFunction == (pList->OrderFunction) ) { ! 280: int LastPosition; ! 281: ! 282: LastPosition = Position = (*MatchFunction)(pKeyNode, pList->pCurrentNode); ! 283: ! 284: while( Occurence ) { ! 285: if( ( Position == LIST_LEFT_OF ) && ( LastPosition == LIST_LEFT_OF ) ! 286: && ( pList->pCurrentNode != pList->pFirstNode ) ) ! 287: pList->pCurrentNode = pList->pCurrentNode->pLeftLink; ! 288: else if( ( Position == LIST_RIGHT_OF ) && ( LastPosition == LIST_RIGHT_OF ) ! 289: && ( pList->pCurrentNode != pList->pLastNode ) ) ! 290: pList->pCurrentNode = pList->pCurrentNode->pRightLink; ! 291: else { ! 292: Occurence--; ! 293: continue; ! 294: } ! 295: LastPosition = Position; ! 296: Position = (*MatchFunction)(pKeyNode, pList->pCurrentNode); 1.1 root 297: } 1.1.1.3 ! root 298: ! 299: } ! 300: //-- match and order are not the same function, thus start ! 301: // the search at the front of the list ! 302: else { ! 303: pList->pCurrentNode = pList->pFirstNode; ! 304: while( (Occurence > 0) && ( (pList->pCurrentNode) != NULL ) ) { ! 305: Position = (*MatchFunction)(pKeyNode, pList->pCurrentNode); ! 306: if( Position == LIST_MATCH ) ! 307: Occurence--; ! 308: if( Occurence > 0 ) ! 309: pList->pCurrentNode = pList->pCurrentNode->pRightLink; 1.1 root 310: } 1.1.1.3 ! root 311: } 1.1 root 312: 1.1.1.3 ! root 313: if( ( Position == LIST_MATCH ) && ( Occurence == 0 ) ) { ! 314: pList->ListError = LIST_NO_ERROR; ! 315: return( TRUE ); ! 316: } ! 317: pList->ListError = LIST_ERROR_NO_MATCH; 1.1 root 318: 1.1.1.3 ! root 319: return( FALSE ); ! 320: } 1.1 root 321: 1.1.1.3 ! root 322: ! 323: // ************************************************************************ ! 324: // FUNCTION : GetCurrentNode( PLIST pList, PNODE* ) ! 325: // PURPOSE : gets the current node from the list ! 326: // COMMENTS : ! 327: // Does not change pList->pCurrentNode. ! 328: // Changes ppNode, thus do not pass in a ppNode which has additional ! 329: // memory associated with it. ! 330: // ************************************************************************ ! 331: BOOL ! 332: GetCurrentNode( PLIST pList, PNODE* ppNode ) ! 333: { ! 334: CHECK_POINTER( ppNode ); ! 335: if( pList->pCurrentNode == NULL ) { ! 336: pList->ListError = LIST_ERROR_NO_NODE; ! 337: return( FALSE ); 1.1 root 338: } 1.1.1.3 ! root 339: *ppNode = pList->pCurrentNode; ! 340: pList->ListError = LIST_NO_ERROR; 1.1 root 341: 1.1.1.3 ! root 342: return( TRUE ); ! 343: } ! 344: ! 345: ! 346: // ************************************************************************ ! 347: // FUNCTION : GetFirstNode( PLIST pList, PNODE* ) ! 348: // PURPOSE : gets the first (left-most) node from the list ! 349: // COMMENTS : ! 350: // Does not change pList->pCurrentNode. ! 351: // Changes ppNode, thus do not pass in a ppNode which has additional ! 352: // memory associated with it. ! 353: // ************************************************************************ ! 354: BOOL ! 355: GetFirstNode( PLIST pList, PNODE* ppNode ) ! 356: { ! 357: CHECK_POINTER( ppNode ); ! 358: if( pList->pFirstNode == NULL ) { ! 359: pList->ListError = LIST_ERROR_NO_NODE; ! 360: return( FALSE ); ! 361: } ! 362: *ppNode = pList->pFirstNode; ! 363: pList->ListError = LIST_NO_ERROR; ! 364: ! 365: return( TRUE ); ! 366: } ! 367: ! 368: ! 369: // ************************************************************************ ! 370: // FUNCTION : GetLastNode( PLIST pList, PNODE* ) ! 371: // PURPOSE : get the last (right-most) node from the List ! 372: // COMMENTS : ! 373: // Does not change pList->pCurrentNode. ! 374: // Changes ppNode, thus do not pass in a ppNode which has additional ! 375: // memory associated with it. ! 376: // ************************************************************************ ! 377: BOOL ! 378: GetLastNode( PLIST pList, PNODE* ppNode ) ! 379: { ! 380: CHECK_POINTER( ppNode ); ! 381: if( pList->pLastNode == NULL ) { ! 382: pList->ListError = LIST_ERROR_NO_NODE; ! 383: return( FALSE ); ! 384: } ! 385: *ppNode = pList->pLastNode; ! 386: pList->ListError = LIST_NO_ERROR; ! 387: ! 388: return( TRUE ); 1.1 root 389: } 390: 391: 392: // ************************************************************************ 393: // FUNCTION : GetNextNode( PLIST pList, PNODE* ) 394: // PURPOSE : get the next (right) node from the pList->pCurrentNode 1.1.1.3 ! root 395: // COMMENTS : ! 396: // Does not change pList->pCurrentNode. ! 397: // Changes ppNode, thus do not pass in a ppNode which has additional ! 398: // memory associated with it. 1.1 root 399: // ************************************************************************ 1.1.1.3 ! root 400: BOOL 1.1 root 401: GetNextNode( PLIST pList, PNODE* ppNode ) 402: { 1.1.1.2 root 403: CHECK_POINTER( ppNode ); 1.1.1.3 ! root 404: if( (*ppNode)->pRightLink == NULL ) { ! 405: pList->ListError = LIST_ERROR_NO_NODE; ! 406: return( FALSE ); ! 407: } ! 408: *ppNode = (*ppNode)->pRightLink; ! 409: pList->ListError = LIST_NO_ERROR; 1.1 root 410: 1.1.1.3 ! root 411: return( TRUE ); 1.1 root 412: } 413: 414: 415: // ************************************************************************ 1.1.1.3 ! root 416: // FUNCTION : GetPrevNode( PLIST pList, PNODE* ) 1.1 root 417: // PURPOSE : get the previous (left) node from the pList->pCurrentNode 1.1.1.3 ! root 418: // COMMENTS : ! 419: // Does not change pList->pCurrentNode. ! 420: // Changes ppNode, thus do not pass in a ppNode which has additional ! 421: // memory associated with it. 1.1 root 422: // ************************************************************************ 1.1.1.3 ! root 423: BOOL ! 424: GetPrevNode( PLIST pList, PNODE* ppNode ) 1.1 root 425: { 1.1.1.2 root 426: CHECK_POINTER( ppNode ); 1.1.1.3 ! root 427: if( (*ppNode)->pLeftLink == NULL ) { ! 428: pList->ListError = LIST_ERROR_NO_NODE; ! 429: return( FALSE ); ! 430: } ! 431: *ppNode = (*ppNode)->pLeftLink; ! 432: pList->ListError = LIST_NO_ERROR; 1.1 root 433: 1.1.1.3 ! root 434: return( TRUE ); 1.1 root 435: } 436: 437: 438: // ************************************************************************ 1.1.1.3 ! root 439: // FUNCTION : DeleteCurrentNode( PLIST pList ) ! 440: // PURPOSE : deletes the current node from the list and frees the memory ! 441: // associated with it ! 442: // COMMENTS : ! 443: // Changes pList->pCurrentNode. ! 444: // ! 445: // Typically, SetCurrentNode (or SetCurrentNodeEx) is called first to set ! 446: // pList->pCurrentNode. Also, any addtional memory associated with this ! 447: // node should be freed first before calling this function. 1.1 root 448: // ************************************************************************ 1.1.1.3 ! root 449: BOOL ! 450: DeleteCurrentNode( PLIST pList ) 1.1 root 451: { 1.1.1.3 ! root 452: PNODE pOldCurrentNode; 1.1 root 453: 1.1.1.3 ! root 454: if( pList->pCurrentNode != NULL ) { ! 455: pOldCurrentNode = pList->pCurrentNode; 1.1 root 456: 1.1.1.3 ! root 457: if( pOldCurrentNode == pList->pFirstNode ) { ! 458: pList->pFirstNode = pOldCurrentNode->pRightLink; ! 459: pList->pCurrentNode = pOldCurrentNode->pRightLink; 1.1 root 460: } 1.1.1.3 ! root 461: else { ! 462: pOldCurrentNode->pLeftLink->pRightLink = pOldCurrentNode->pRightLink; ! 463: pList->pCurrentNode = pOldCurrentNode->pLeftLink; 1.1 root 464: } 465: 1.1.1.3 ! root 466: if( pOldCurrentNode == pList->pLastNode ) ! 467: pList->pLastNode = pOldCurrentNode->pLeftLink; ! 468: else ! 469: pOldCurrentNode->pRightLink->pLeftLink = pOldCurrentNode->pLeftLink; ! 470: ! 471: DestroyNode( pOldCurrentNode ); ! 472: pList->ListError = LIST_NO_ERROR; ! 473: return( TRUE ); 1.1 root 474: } 1.1.1.3 ! root 475: pList->ListError = LIST_NO_ERROR; 1.1 root 476: 1.1.1.3 ! root 477: return( TRUE ); ! 478: } 1.1 root 479: 480: 1.1.1.3 ! root 481: // ************************************************************************ ! 482: // FUNCTION : DestroyNode( PNODE pNode ) ! 483: // PURPOSE : deallocates a node ! 484: // COMMENTS : ! 485: // ************************************************************************ ! 486: BOOL ! 487: DestroyNode( PNODE pNode ) ! 488: { ! 489: free( pNode ); ! 490: ! 491: return( TRUE ); ! 492: } ! 493: ! 494: ! 495: // ************************************************************************ ! 496: // FUNCTION : DestroyList( PLIST pList ) ! 497: // PURPOSE : deallocates a list, does not free any nodes, if present ! 498: // COMMENTS : ! 499: // ************************************************************************ ! 500: BOOL ! 501: DestroyList( PLIST pList ) ! 502: { ! 503: free( pList ); ! 504: pList->ListError = LIST_NO_ERROR; ! 505: ! 506: return( TRUE ); ! 507: } ! 508: ! 509: ! 510: // ************************************************************************ ! 511: // FUNCTION : GetListError( PLIST pList ) ! 512: // PURPOSE : get the last linked list error ! 513: // COMMENTS : ! 514: // ************************************************************************ ! 515: int ! 516: GetListError( PLIST pList ) ! 517: { 1.1 root 518: return( pList->ListError ); 519: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.