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