![[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 ! root 1: // ************************************************************************ ! 2: // LinkList.C - Ordered Double Linked List Package ! 3: // ************************************************************************ ! 4: // PURPOSE: Provide a generalized sorted double linked list package ! 5: // ! 6: // FUNCTIONS: ! 7: // InitList - initialize/clear list ! 8: // CreateNode - allocate a new node that can be put into list ! 9: // InsertNode - insert a new node into the list ! 10: // DeleteCurrentNode - remove a node from the list ! 11: // GetNextNode - get the next (right) node from the CurrentNode ! 12: // GetPreviousNode - get the previous (left) node from the ! 13: // CurrentNode ! 14: // GetNode - get nth Occurence of a node that matches a ! 15: // key(s) ! 16: // GetListError - get the error value ! 17: // ! 18: // COMMENTS: The application must serialize access to the linked list ! 19: // ! 20: // Format of the Ordering and Matching functions is as follows: ! 21: // ! 22: // int OrderFunc( PNODE pNodeOne, PNODE pNodeTwo ) ! 23: // { ! 24: // if( (pNodeOne->NodeData).Key < (pNodeTwo->NodeData).Key ) ! 25: // return( LEFT_OF ); ! 26: // if( (pNodeOne->NodeData).Key == (pNodeTwo->NodeData).Key ) ! 27: // return( MATCH ); ! 28: // if( (pNodeOne->NodeData).Key > (pNodeTwo->NodeData).Key ) ! 29: // return( RIGHT_OF ); ! 30: // } ! 31: // ! 32: // ************************************************************************ ! 33: #include <StdLib.H> // malloc(), free() ! 34: #include <StdIO.H> // printf() ! 35: #include "LinkList.H" ! 36: ! 37: //-- NULL pointer dereferencing checking macro ! 38: #define CHECH_POINTER( Node ) \ ! 39: if( Node == NULL ) { \ ! 40: printf("Attempt to dereference NULL.\n"); \ ! 41: return(pList->ListError = DEREFERENCE_NULL_ERROR); \ ! 42: } ! 43: ! 44: //-- "member" functions that return the private data ! 45: int GetListError( PLIST pList ) { return( pList->ListError ); } ! 46: PNODE GetFirstNode( PLIST pList ) { return( pList->pFirstNode ); } ! 47: PNODE GetCurrentNode( PLIST pList ) { return( pList->pCurrentNode ); } ! 48: PNODE GetLastNode( PLIST pList ) { return( pList->pLastNode ); } ! 49: ! 50: ! 51: // ************************************************************************ ! 52: // FUNCTION : InitList( PLIST pList, int (*)(PNODE, PNODE) ) ! 53: // PURPOSE : initialize/clear list, registers the ordering function ! 54: // COMMENTS : ! 55: // ************************************************************************ ! 56: int ! 57: InitList( PLIST pList, int (*OrderFunc)( PNODE pNodeOne, PNODE pNodeTwo ) ) ! 58: { ! 59: PNODE pTempNode; ! 60: ! 61: //-- remove all nodes if the list is not empty ! 62: while( ( (pList->pFirstNode) != NULL) && ( (pList->ListError) == NO_ERROR_FOUND) ) { ! 63: pTempNode = (pList->pFirstNode); ! 64: if( DeleteCurrentNode( pList ) < NO_ERROR_FOUND ) { ! 65: (pList->ListError) = NO_NODE_ERROR; ! 66: return( pList->ListError ); ! 67: } ! 68: } ! 69: ! 70: //-- initialize the "private" pointers to NULL ! 71: (pList->pFirstNode) = NULL; ! 72: (pList->pCurrentNode) = NULL; ! 73: (pList->pLastNode) = NULL; ! 74: ! 75: //-- register the link list data ordering function ! 76: (pList->OrderFunction) = OrderFunc; ! 77: ! 78: (pList->ListError) = NO_ERROR_FOUND; ! 79: return( pList->ListError ); ! 80: } ! 81: ! 82: ! 83: // ************************************************************************ ! 84: // FUNCTION : CreateNode( PLIST pList, PNODE* ) ! 85: // PURPOSE : create/allocate a new node that can be put into list ! 86: // COMMENTS : ! 87: // ************************************************************************ ! 88: int ! 89: CreateNode( PLIST pList, PNODE* ppNewNode ) ! 90: { ! 91: (*ppNewNode) = (PNODE) malloc(sizeof(NODE)); ! 92: if(*ppNewNode == NULL) { ! 93: printf("malloc failed.\n"); ! 94: (pList->ListError) = NO_NODE_ERROR; ! 95: return( pList->ListError ); ! 96: } ! 97: ((*ppNewNode)->pRightLink) = NULL; ! 98: ((*ppNewNode)->pLeftLink) = NULL; ! 99: ! 100: (pList->ListError) = NO_ERROR_FOUND; ! 101: return( pList->ListError ); ! 102: } ! 103: ! 104: ! 105: // ************************************************************************ ! 106: // FUNCTION : InsertNode( PLIST pList, PNODE ) ! 107: // PURPOSE : insert a new node into the list ! 108: // COMMENTS : all nodes must have a unique key entry (from order ! 109: // function), if a match is found during an insert then the ! 110: // old node gets replaced with the new node ! 111: // NOTE: changes pList->pCurrentNode ! 112: // ************************************************************************ ! 113: int ! 114: InsertNode( PLIST pList, PNODE pNewNode ) ! 115: { ! 116: int Position; ! 117: int LastPosition; ! 118: ! 119: if( (pList->pFirstNode) == NULL ) { ! 120: ! 121: (pList->pFirstNode) = pNewNode; ! 122: (pList->pLastNode) = pNewNode; ! 123: (pList->pCurrentNode) = pNewNode; ! 124: (pList->ListError) = NO_ERROR_FOUND; ! 125: ! 126: return( pList->ListError ); ! 127: } ! 128: ! 129: Position = (*(pList->OrderFunction))( pNewNode, pList->pCurrentNode ); ! 130: ! 131: //-- search for insertion point ! 132: while( (pList->pCurrentNode) != NULL ) { ! 133: ! 134: LastPosition = Position; ! 135: Position = (*(pList->OrderFunction))(pNewNode, pList->pCurrentNode); ! 136: ! 137: if( (pList->pFirstNode) == (pList->pLastNode) ) ! 138: break; ! 139: ! 140: if( Position != LastPosition ) ! 141: break; ! 142: ! 143: if( (pList->pCurrentNode) == (pList->pFirstNode) ) { ! 144: if( Position == RIGHT_OF ) { ! 145: (pList->pCurrentNode) = ((pList->pCurrentNode)->pRightLink); ! 146: continue; ! 147: } ! 148: break; ! 149: } ! 150: ! 151: if( (pList->pCurrentNode) == (pList->pLastNode) ) { ! 152: if( Position == LEFT_OF ) { ! 153: (pList->pCurrentNode) = ((pList->pCurrentNode)->pLeftLink); ! 154: continue; ! 155: } ! 156: break; ! 157: } ! 158: ! 159: if( Position == LastPosition ) { ! 160: if( Position == LEFT_OF) { ! 161: (pList->pCurrentNode) = ((pList->pCurrentNode)->pLeftLink); ! 162: continue; ! 163: } ! 164: if( Position == RIGHT_OF ) { ! 165: (pList->pCurrentNode) = ((pList->pCurrentNode)->pRightLink); ! 166: continue; ! 167: } ! 168: break; ! 169: } ! 170: ! 171: } ! 172: ! 173: //-- now, insert the pNewNode ! 174: switch( Position ) { ! 175: ! 176: case LEFT_OF: ! 177: (pNewNode->pRightLink) = (pList->pCurrentNode); ! 178: (pNewNode->pLeftLink) = ((pList->pCurrentNode)->pLeftLink); ! 179: if( (pList->pCurrentNode) == (pList->pFirstNode) ) ! 180: (pList->pFirstNode) = pNewNode; ! 181: else ! 182: (((pList->pCurrentNode)->pLeftLink)->pRightLink) = pNewNode; ! 183: ((pList->pCurrentNode)->pLeftLink) = pNewNode; ! 184: break; ! 185: ! 186: case RIGHT_OF: ! 187: (pNewNode->pLeftLink) = (pList->pCurrentNode); ! 188: (pNewNode->pRightLink) = ((pList->pCurrentNode)->pRightLink); ! 189: if( (pList->pCurrentNode) == (pList->pLastNode) ) ! 190: (pList->pLastNode) = pNewNode; ! 191: else ! 192: (((pList->pCurrentNode)->pRightLink)->pLeftLink) = pNewNode; ! 193: ((pList->pCurrentNode)->pRightLink) = pNewNode; ! 194: break; ! 195: ! 196: case MATCH: ! 197: (pNewNode->pLeftLink) = ((pList->pCurrentNode)->pLeftLink); ! 198: (pNewNode->pRightLink) = ((pList->pCurrentNode)->pRightLink); ! 199: DestroyNode( pList->pCurrentNode ); ! 200: break; ! 201: ! 202: } ! 203: (pList->pCurrentNode) = pNewNode; ! 204: ! 205: (pList->ListError) = NO_ERROR_FOUND; ! 206: return( pList->ListError ); ! 207: } ! 208: ! 209: ! 210: // ************************************************************************ ! 211: // FUNCTION : DestroyNode( PNODE ) ! 212: // PURPOSE : deallocates a node ! 213: // COMMENTS : ! 214: // ************************************************************************ ! 215: int ! 216: DestroyNode( PNODE pNode ) ! 217: { ! 218: free( pNode ); ! 219: return( 1 ); ! 220: } ! 221: ! 222: ! 223: // ************************************************************************ ! 224: // FUNCTION : DeleteCurrentNode( PLIST pList ) ! 225: // PURPOSE : delete pList->pCurrentNode from the list and deallocate it ! 226: // COMMENTS : changes pList->pCurrentNode. Typically, GetNode is called first so ! 227: // pList->pCurrentNode points to the correct node ! 228: // ************************************************************************ ! 229: int ! 230: DeleteCurrentNode( PLIST pList ) ! 231: { ! 232: PNODE pOldCurrentNode; ! 233: ! 234: if( (pList->pCurrentNode) != NULL ) { ! 235: pOldCurrentNode = (pList->pCurrentNode); ! 236: ! 237: if( pOldCurrentNode == (pList->pFirstNode) ) { ! 238: (pList->pFirstNode) = (pOldCurrentNode->pRightLink); ! 239: (pList->pCurrentNode) = (pOldCurrentNode->pRightLink); ! 240: } ! 241: else { ! 242: ((pOldCurrentNode->pLeftLink)->pRightLink) = (pOldCurrentNode->pRightLink); ! 243: (pList->pCurrentNode) = (pOldCurrentNode->pLeftLink); ! 244: } ! 245: ! 246: if( pOldCurrentNode == (pList->pLastNode) ) ! 247: (pList->pLastNode) = (pOldCurrentNode->pLeftLink); ! 248: else ! 249: ((pOldCurrentNode->pRightLink)->pLeftLink) = (pOldCurrentNode->pLeftLink); ! 250: ! 251: DestroyNode( pOldCurrentNode ); ! 252: ! 253: (pList->ListError) = NO_ERROR_FOUND; ! 254: return( pList->ListError ); ! 255: } ! 256: ! 257: (pList->ListError) = NO_ERROR_FOUND; ! 258: return( pList->ListError ); ! 259: } ! 260: ! 261: ! 262: // ************************************************************************ ! 263: // FUNCTION : GetNextNode( PLIST pList, PNODE* ) ! 264: // PURPOSE : get the next (right) node from the pList->pCurrentNode ! 265: // COMMENTS : Does not change pList->pCurrentNode ! 266: // ************************************************************************ ! 267: int ! 268: GetNextNode( PLIST pList, PNODE* ppNode ) ! 269: { ! 270: CHECH_POINTER( ppNode ); ! 271: if( ((*ppNode)->pRightLink) == NULL ) ! 272: return( (pList->ListError) = NO_NEXT_NODE_ERROR ); ! 273: (*ppNode) = ((*ppNode)->pRightLink); ! 274: ! 275: (pList->ListError) = NO_ERROR_FOUND; ! 276: return( pList->ListError ); ! 277: } ! 278: ! 279: ! 280: // ************************************************************************ ! 281: // FUNCTION : GetPreviousNode( PLIST pList, PNODE* ) ! 282: // PURPOSE : get the previous (left) node from the pList->pCurrentNode ! 283: // COMMENTS : Does not change pList->pCurrentNode ! 284: // ************************************************************************ ! 285: int ! 286: GetPreviousNode( PLIST pList, PNODE* ppNode ) ! 287: { ! 288: CHECH_POINTER( ppNode ); ! 289: if( ((*ppNode)->pLeftLink) == NULL ) ! 290: return( (pList->ListError) = NO_PREV_NODE_ERROR); ! 291: (*ppNode) = ((*ppNode)->pLeftLink); ! 292: ! 293: (pList->ListError) = NO_ERROR_FOUND; ! 294: return( pList->ListError ); ! 295: } ! 296: ! 297: ! 298: // ************************************************************************ ! 299: // FUNCTION : GetNode( PLIST pList, PNODE*, int (*)(PNODE, PNODE), int ) ! 300: // PURPOSE : get nth Occurence of a node from the list that matches a ! 301: // key(s). ! 302: // COMMENTS : may use the ordering function or a new matching function ! 303: // if not searching for a match based on the primary ! 304: // ordering key. Note: the matching and ordering functions ! 305: // have the same definition. ! 306: // NOTE: changes pList->pCurrentNode ! 307: // ************************************************************************ ! 308: int ! 309: GetNode( PLIST pList, PNODE* ppKeyNode, ! 310: int (*MatchFunction)( PNODE pNodeOne, PNODE pNodeTwo ), ! 311: int Occurence ) ! 312: { ! 313: int Position; ! 314: ! 315: //-- if match and order are same function ! 316: if( MatchFunction == (pList->OrderFunction) ) { ! 317: int LastPosition; ! 318: ! 319: Position = (*MatchFunction)(*ppKeyNode, pList->pCurrentNode); ! 320: LastPosition = Position; ! 321: ! 322: while( Occurence ) { ! 323: if( (Position == LEFT_OF) && (LastPosition == LEFT_OF) ! 324: && ( (pList->pCurrentNode) != (pList->pFirstNode) ) ) ! 325: (pList->pCurrentNode) = ((pList->pCurrentNode)->pLeftLink); ! 326: else if( (Position == RIGHT_OF) && (LastPosition == RIGHT_OF) ! 327: && ( (pList->pCurrentNode) != (pList->pLastNode) ) ) ! 328: (pList->pCurrentNode) = ((pList->pCurrentNode)->pRightLink); ! 329: else { ! 330: Occurence--; ! 331: continue; ! 332: } ! 333: LastPosition = Position; ! 334: Position = (*MatchFunction)(*ppKeyNode, pList->pCurrentNode); ! 335: } ! 336: ! 337: } ! 338: else { // match and order are not the same function, thus start ! 339: // the search at the front of the list ! 340: (pList->pCurrentNode) = (pList->pFirstNode); ! 341: ! 342: while( (Occurence > 0) && ( (pList->pCurrentNode) != NULL)) { ! 343: Position = (*MatchFunction)(*ppKeyNode, pList->pCurrentNode); ! 344: if(Position == MATCH) ! 345: Occurence--; ! 346: if(Occurence > 0 ) ! 347: (pList->pCurrentNode) = ((pList->pCurrentNode)->pRightLink); ! 348: } ! 349: ! 350: } ! 351: ! 352: if( (Position == MATCH) && (Occurence == 0) ) { ! 353: *ppKeyNode = (pList->pCurrentNode); ! 354: ! 355: (pList->ListError) = NO_ERROR_FOUND; ! 356: return( pList->ListError ); ! 357: } ! 358: ! 359: (pList->ListError) = NO_MATCH_ERROR; ! 360: return( pList->ListError ); ! 361: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.