Return to dict0.c CVS log

Up to [WindowsNT SDKs] / mstools / samples / rpc / dict

Annotation of mstools/samples/rpc/dict/dict0.c, revision 1.1

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.