![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to dict0.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [WindowsNT SDKs] / mstools / samples / rpc / dict|
Return to dict0.c CVS log | Up to [WindowsNT SDKs] / mstools / samples / rpc / dict |
1.1 root 1: /*************************************************************/
2: /** **/
3: /** Microsoft RPC Examples **/
4: /** Dictionary Application **/
5: /** Copyright(c) Microsoft Corp. 1991 **/
6: /** **/
7: /*************************************************************/
8:
9: #include <stdio.h>
10: #include <malloc.h>
11: #include <stdlib.h>
12: #include <string.h>
13: #include <ctype.h>
14: #include <windows.h>
15:
16: #include <rpc.h>
17: #include "dict0.h"
18:
19: /************************************************************************/
20: TreeNode Dumbo;
21: // volatile
22: TreeNode *Dummy = &Dumbo; // a global dummy node
23:
24: #define ROTATELEFT tmp=t->right; t->right=tmp->left; tmp->left=t; t=tmp
25: #define ROTATERIGHT tmp=t->left; t->left=tmp->right; tmp->right=t; t=tmp
26: #define LINKLEFT tmp=t; t=t->right; l=l->right=tmp
27: #define LINKRIGHT tmp=t; t=t->left; r=r->left=tmp
28: #define ASSEMBLE r->left=t->right; l->right=t->left; \
29: t->left=Dummy->right; t->right=Dummy->left
30: /************************************************************************/
31:
32: /************************************************************************
33: Basic structure declarations from dict0.h:
34:
35: typedef struct tnode {
36: struct tnode *left; // left child pointer
37: struct tnode *right; // right child pointer
38: void *item; // pointer to some structure
39: } TreeNode;
40:
41: typedef struct dictnode {
42: TreeNode *root; // pointer to the root of a SAT
43: long size; // number of records in dictionary
44: void * state; // reserved for state info
45: // int (*cmp_rec)(void *, void *); comparison function pointer
46: cmp_rec_func cmp_rec;
47: TreeNode* (*splay)(TreeNode *, void *, cmp_rec_func);
48: // pointer to a splay function
49: void (*print_rec)(void *); // one line print function
50: } Dictionary;
51:
52: #define DICT_CURR_ITEM(pDict) pDict->root->item
53:
54: typedef enum {
55: SUCCESS,
56: ITEM_ALREADY_PRESENT,
57: ITEM_NOT_FOUND,
58: FIRST_ITEM,
59: LAST_ITEM,
60: EMPTY_DICTIONARY,
61: NULL_ITEM
62: }
63: Dict_Status;
64: **************************************************************************/
65:
66:
67: /*************************************************************************/
68: /*** MIDL_user_allocate / MIDL_user_free ***/
69: /*************************************************************************/
70:
71: void *
72: MIDL_user_allocate(unsigned long count);
73:
74: void
75: MIDL_user_free(void * p);
76:
77: /*************************************************************************/
78: /*** Minimal Dictionary Operations: ***/
79: /*** ***/
80: /*** Dictionary *Dict_New(Cmp_rec*, Splay*, print_rec*) ***/
81: /*** ***/
82: /*** Dict_Status Dict_Find(Dictionary*, Item*) ***/
83: /*** Dict_Status Dict_Next(Dictionary*, Item*) ***/
84: /*** Dict_Status Dict_Prev(Dictionary*, Item*) ***/
85: /*** Dict_Status Dict_Insert(Dictionary*, Item*) ***/
86: /*** Dict_Status Dict_Delete(Dictionary*, Item**) ***/
87: /*** ***/
88: /*** Item* DICT_CURR_ITEM(Dict*) ***/
89: /*************************************************************************/
90:
91: #define TreeNode_New(pnode, pitem) pnode = \
92: (TreeNode*) MIDL_user_allocate (sizeof(TreeNode)); \
93: pnode->left = pnode->right = NULL; pnode->item = pitem;
94:
95: Dictionary*
96: Dict_New( // returns a new dictionary node
97: int (*cmp_rec) // pointer to item comparison function
98: (void *, void *),
99: TreeNode* (*splay) // pointer to a splay function
100: (TreeNode *, void *, cmp_rec_func),
101: void (*print_rec) // pointer to one line item print routine
102: (void *) )
103: {
104: Dictionary* dp;
105: dp = (Dictionary*)MIDL_user_allocate(sizeof(Dictionary));
106: dp->root = NULL;
107: dp->size = 0;
108: dp->state = NULL;
109: dp->print_rec = print_rec;
110: dp->splay = splay;
111: dp->cmp_rec = cmp_rec;
112: return(dp);
113: }
114:
115:
116: Dict_Status
117: Dict_Find(
118: Dictionary* dp, // Dictionary to be searched.
119: void* item) // Item searched for.
120: {
121: int keycmp;
122: TreeNode* t;
123:
124: if (dp->root == NULL) return (EMPTY_DICTIONARY);
125: if (item == NULL) return(NULL_ITEM);
126: t = dp->root = dp->splay(dp->root, item, dp->cmp_rec);
127: keycmp = (dp->cmp_rec)( t->item, item );
128: if (keycmp != 0)
129: return(ITEM_NOT_FOUND);
130: else return(SUCCESS);
131: }
132:
133: Dict_Status
134: Dict_Next(
135: Dictionary* dp, // Dictionary to be searched.
136: void* item) // A Key item. Advance to successor of item in dp.
137: {
138: TreeNode* t;
139: int keycmp;
140:
141: if (dp->root == NULL) return (EMPTY_DICTIONARY);
142: if (item == NULL) { dp->root = tdSplayLeft(dp->root);
143: return(SUCCESS);
144: }
145: if (item == DICT_CURR_ITEM(dp)) {
146: t = dp->root;
147: keycmp = 0; }
148: else {
149: dp->root = t = dp->splay(dp->root, item, dp->cmp_rec);
150: keycmp = (dp->cmp_rec)( item, t->item );
151: }
152: if (keycmp < 0)
153: return(SUCCESS);
154: else if (t->right == NULL) {
155: return(LAST_ITEM); }
156: else {
157: t = dp->root;
158: dp->root = tdSplayLeft(t->right);
159: dp->root->left = t;
160: t->right = NULL;
161: return(SUCCESS);
162: }
163: }
164:
165: Dict_Status
166: Dict_Prev(
167: Dictionary* dp, // Dictionary to be searched.
168: void* item) // A Key item. Retreat to predecessor of item in dp.
169: {
170: TreeNode* t;
171: int keycmp;
172:
173: if (dp->root == NULL) return (EMPTY_DICTIONARY);
174: if (item == NULL) { dp->root = tdSplayRight(dp->root);
175: return(SUCCESS);
176: }
177: if (item == DICT_CURR_ITEM(dp)) {
178: t = dp->root;
179: keycmp = 0; }
180: else {
181: dp->root = t = dp->splay(dp->root, item, dp->cmp_rec);
182: keycmp = (dp->cmp_rec)( item, t->item );
183: }
184: if (keycmp > 0)
185: return(SUCCESS);
186: else if (t->left == NULL) {
187: return(FIRST_ITEM); }
188: else {
189: t = dp->root;
190: dp->root = tdSplayRight(t->left);
191: dp->root->right = t;
192: t->left = NULL;
193: return(SUCCESS);
194: }
195: }
196:
197: Dict_Status
198: Dict_Insert( // insert the given item into the tree
199: Dictionary* dp, // the modified dictionary
200: void* item) // the item to be inserted
201: {
202: int keycmp;
203: TreeNode *t, *newNode;
204:
205: if (item == NULL) return(NULL_ITEM);
206: if (dp->root == NULL) {
207: TreeNode_New(newNode, item);
208: dp->root = newNode;
209: dp->size++;
210: return(SUCCESS);
211: }
212: t = dp->root = dp->splay(dp->root, item, dp->cmp_rec);
213: keycmp = (dp->cmp_rec)( t->item, item );
214: if (keycmp == 0)
215: return(ITEM_ALREADY_PRESENT);
216:
217: TreeNode_New(newNode, item);
218: if (keycmp < 0) { // t->item < item
219: newNode->right = t->right;
220: t->right = NULL;
221: newNode->left = t; }
222: else {
223: newNode->left = t->left;
224: t->left = NULL;
225: newNode->right = t;
226: }
227: dp->root = newNode;
228: dp->size++;
229: return(SUCCESS);
230: }
231:
232:
233: Dict_Status
234: Dict_Delete( // delete the given item into from the tree
235: Dictionary* dp, // the modified dictionary
236: void** pItem) // IN: points to the (key) item to be deleted
237: // OUT: points to the item just deleted
238: {
239: TreeNode *t, *r;
240: int keycmp;
241: void* item = *pItem;
242: t = dp->root;
243:
244: if (item == NULL) return(NULL_ITEM);
245: if (dp->root == NULL) return (EMPTY_DICTIONARY);
246: if (item == DICT_CURR_ITEM(dp))
247: keycmp = 0;
248: else {
249: dp->root = t = dp->splay(dp->root, item, dp->cmp_rec);
250: keycmp = (dp->cmp_rec)( item, t->item );
251: }
252: if (keycmp != 0)
253: return(ITEM_NOT_FOUND);
254: *pItem = DICT_CURR_ITEM(dp);
255:
256: if (t->left == NULL) {
257: dp->root = t->right; }
258: else if ( (r = t->right) == NULL) {
259: dp->root = t->left; }
260: else {
261: r = tdSplayLeft(r);
262: // at this point r->left == NULL
263: r->left = t->left;
264: dp->root = r;
265: }
266: t->left = t->right = t->item = NULL;
267: MIDL_user_free(t);
268: dp->size--;
269: return(SUCCESS);
270: }
271:
272:
273: /*************************************************************************/
274: /***** Core functions (internal) *****/
275: /*************************************************************************/
276:
277: TreeNode * // returns the new root
278: tdSplay( // general top down splay
279: TreeNode *root, // the current root of the tree
280: void *keyItem, // pointer to a "key item" searched for
281: int (*cmp)(void *, void *) )
282: // pointer to a comparison function
283: {
284: TreeNode* t=root; // current search point
285: TreeNode* l; // root of "left subtree" < keyItem
286: TreeNode* r; // root of "right subtree" > keyItem
287: int kcmpt, kcmpleft, kcmpright;
288: // cash comparison results
289: TreeNode* tmp;
290:
291: /***/
292: Dummy = &Dumbo;
293: l = Dummy;
294: r = Dummy;
295: /***/
296:
297: if ( (root == NULL) || ((*cmp)(keyItem, root->item) == 0) ) return (root);
298: Dummy->left=Dummy->right=NULL;
299: while ( (kcmpt = (*cmp)(keyItem, t->item)) != 0 ) {
300: if ( kcmpt < 0 ) {
301: if ( t->left == NULL ) break;
302: if ( (kcmpleft = (*cmp)(keyItem, t->left->item)) == 0 ) {
303: LINKRIGHT; }
304: else if ( kcmpleft < 0 ) {
305: ROTATERIGHT;
306: if ( t->left != NULL ) {
307: LINKRIGHT; } }
308: else { // keyItem > t->left->item
309: LINKRIGHT;
310: if ( t->right != NULL ) {
311: LINKLEFT; } } }
312: else { // keyItem > t->item
313: if ( t->right == NULL ) break;
314: if ( (kcmpright = (*cmp)(keyItem, t->right->item)) == 0 ) {
315: LINKLEFT; }
316: else if ( kcmpright > 0 ) {
317: ROTATELEFT;
318: if ( t->right != NULL ) {
319: LINKLEFT; } }
320: else { // keyItem < t->right->item
321: LINKLEFT;
322: if ( t->left != NULL ) {
323: LINKRIGHT; } }
324: }
325: }
326: // assemble:
327: r->left=t->right; l->right=t->left;
328: t->left=Dummy->right; t->right=Dummy->left;
329: return(t);
330: }
331:
332: TreeNode*
333: tdSplayLeft(TreeNode* root)
334: {
335: TreeNode* t=root; // current "search" point
336: TreeNode* l=Dummy; // root of "left subtree" < keyItem
337: TreeNode* r=Dummy; // root of "right subtree" > keyItem
338: TreeNode* tmp;
339:
340: if ((t == NULL) || (t->left == NULL)) return(t);
341: if (t->left->left == NULL) {
342: ROTATERIGHT; return(t); }
343: Dummy->left=Dummy->right=NULL;
344: while ( t->left != NULL ) {
345: ROTATERIGHT;
346: if ( t->left != NULL ) {
347: LINKRIGHT; }
348: }
349: r->left=t->right; l->right=t->left;
350: t->left=Dummy->right; t->right=Dummy->left;
351: return(t);
352: }
353:
354: TreeNode*
355: tdSplayRight(TreeNode* root)
356: {
357: TreeNode* t=root; // current "search" point
358: TreeNode* l=Dummy; // root of "left subtree" < keyItem
359: TreeNode* r=Dummy; // root of "right subtree" > keyItem
360: TreeNode* tmp;
361:
362: if ((t == NULL) || (t->right == NULL)) return(t);
363: Dummy->left=Dummy->right=NULL;
364: while ( t->right != NULL ) {
365: ROTATELEFT;
366: if ( t->right != NULL ) {
367: LINKLEFT; }
368: }
369: r->left=t->right; l->right=t->left;
370: t->left=Dummy->right; t->right=Dummy->left;
371: return(t);
372: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.