DICT0.H

/*************************************************************/ 
/**                                                         **/ 
/**                 Microsoft RPC Examples                  **/ 
/**                 Dictionary Application                  **/ 
/**           Copyright 1992 - 1998 Microsoft Corporation   **/ 
/**                                                         **/ 
/*************************************************************/ 
 
/**************************************************************/ 
/*  user interface header file for top down splay package     */ 
/*  based on Sleator & Tarjan's Self Adjusting Trees          */ 
/**************************************************************/ 
 
typedef int (*cmp_rec_func)(void *, void *); 
                            /* type of a comparison function */ 
 
typedef struct tnode { 
    struct tnode *left;     /* left child pointer */ 
    struct tnode *right;    /* right child pointer */ 
    void *item;             /* pointer to some structure */ 
} TreeNode; 
 
typedef struct dictnode { 
    TreeNode *root;                 /* pointer to the root of a SAT     */ 
    long size;                      /* number of records in dictionary  */ 
    void * state;                   /* reserved for state info          */ 
    cmp_rec_func cmp_rec;           /* pointer to a comparison function */ 
    TreeNode* (*splay)(TreeNode *, void *, cmp_rec_func); 
                                    /* pointer to a splay function      */ 
    void (*print_rec)(void *);      /* one line print function          */ 
} Dictionary; 
 
/*************************************************************************/ 
/*****              Core functions (internal)                        *****/ 
/*************************************************************************/ 
 
TreeNode *              /* returns the new root                 */ 
tdSplay(                /* general top down splay               */ 
    TreeNode *root,     /* the current root of the tree         */ 
    void *keyItem,      /* pointer to a "key item" searched for */ 
    int (*cmp)(void *, void *) ); 
                        /* pointer to a comparison function     */ 
 
TreeNode* 
tdSplayLeft(TreeNode* root); 
 
TreeNode* 
tdSplayRight(TreeNode* root); 
 
void 
print_tree_sat(         /* prints the binary tree (indented right subtree, 
                           followed by the root, followed by the indented 
                           right dubtree) */ 
    Dictionary * dp, 
    int indent);        /* number of blanks to indent subtrees */ 
 
/*************************************************************************/ 
/***    Minimal Dictionary Operations:                                 ***/ 
/***                                                                   ***/ 
/***    Dictionary *Dict_New(Cmp_rec*, Splay*, print_rec*)             ***/ 
/***                                                                   ***/ 
/***    Dict_Status Dict_Find(Dictionary*, Item*)                      ***/ 
/***    Dict_Status Dict_Next(Dictionary*, Item*)                      ***/ 
/***    Dict_Status Dict_Prev(Dictionary*, Item*)                      ***/ 
/***    Dict_Status Dict_Insert(Dictionary*, Item*)                    ***/ 
/***    Dict_Status Dict_Delete(Dictionary*, Item**)                   ***/ 
/***                                                                   ***/ 
/***    Item* DICT_CURR_ITEM(Dict*)                                    ***/ 
/*************************************************************************/ 
 
typedef enum { 
    SUCCESS, 
    ITEM_ALREADY_PRESENT, 
    ITEM_NOT_FOUND, 
    FIRST_ITEM, 
    LAST_ITEM, 
    EMPTY_DICTIONARY, 
    NULL_ITEM 
} Dict_Status; 
 
#define DICT_CURR_ITEM(pDict)  ( (pDict)->root->item ) 
 
#define DICT_EMPTY(pDict)      ( (pDict)->root == NULL ) 
 
Dictionary* 
Dict_New(                    /* returns a new dictionary node          */ 
    int (*cmp_rec)           /* pointer to item comparison function    */ 
        (void *, void *), 
    TreeNode* (*splay)       /* pointer to a splay function            */ 
        (TreeNode *, void *, cmp_rec_func), 
 
    void (*print_rec)        /* pointer to one line item print routine */ 
        (void *) ); 
 
Dict_Status 
Dict_Find( 
    Dictionary* dp,     /* Dictionary to be searched. */ 
    void* item);        /* Item searched for. */ 
 
Dict_Status 
Dict_Next( 
    Dictionary* dp,     /* Dictionary to be searched. */ 
    void* item);        /* A Key item.  Advance to successor of item in dp. */ 
 
Dict_Status 
Dict_Prev( 
    Dictionary* dp,     /* Dictionary to be searched. */ 
    void* item);        /* A Key item.  Retreat to predecessor of item in dp. */ 
 
Dict_Status 
Dict_Insert(            /* insert the given item into the tree */ 
    Dictionary* dp,     /* the modified dictionary */ 
    void* item);        /* the item to be inserted */ 
 
Dict_Status 
Dict_Delete(            /* delete the given item into from the tree */ 
    Dictionary* dp,     /* the modified dictionary */ 
    void** pItem);      /* IN: points to the (key) item to be deleted */ 
                        /* OUT: points to the item just deleted */