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