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