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