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