mirror of https://github.com/lianthony/NT4.0
You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
136 lines
3.7 KiB
136 lines
3.7 KiB
/* --------------------------------------------------------------------
|
|
|
|
Microsoft OS/2 LAN Manager
|
|
Copyright(c) Microsoft Corp., 1990
|
|
|
|
RPC - Written by Dov Harel
|
|
|
|
This file contains the definition for splay tree self
|
|
adjusting binary trees
|
|
-------------------------------------------------------------------- */
|
|
|
|
#ifndef __DICT_HXX__
|
|
#define __DICT_HXX__
|
|
|
|
#ifndef Nil
|
|
#define Nil 0
|
|
#endif
|
|
|
|
#ifndef DICT_MYSPLAY
|
|
#define VIRT_SPLAY
|
|
#else
|
|
#define VIRT_SPLAY virtual
|
|
#endif
|
|
|
|
typedef void * pUserType;
|
|
|
|
class TreeNode {
|
|
|
|
public:
|
|
TreeNode *left; /* left child pointer */
|
|
TreeNode *right; /* right child pointer */
|
|
pUserType item; /* pointer to some structure */
|
|
|
|
TreeNode(pUserType itemI) {
|
|
left = right = Nil;
|
|
item = itemI;
|
|
}
|
|
};
|
|
|
|
typedef int (* CompareFN)(pUserType, pUserType);
|
|
typedef void (* PrintFN)(pUserType);
|
|
|
|
typedef enum {
|
|
SUCCESS,
|
|
ITEM_ALREADY_PRESENT,
|
|
ITEM_NOT_FOUND,
|
|
FIRST_ITEM,
|
|
LAST_ITEM,
|
|
EMPTY_DICTIONARY,
|
|
OUT_OF_MEMORY,
|
|
NULL_ITEM
|
|
} Dict_Status;
|
|
|
|
class Dictionary {
|
|
TreeNode *root; // pointer to the root of a SAT
|
|
int fCompare; // value of last compare
|
|
pUserType itemCur; // the current item
|
|
int size; // number of records in dictionary/
|
|
// functions provided by user
|
|
CompareFN CompareItem; // compare 2 user types
|
|
PrintFN PrintItem; // print a usertype
|
|
public:
|
|
|
|
Dictionary(CompareFN compareI,
|
|
PrintFN printI = Nil) {
|
|
|
|
root = Nil;
|
|
size = 0;
|
|
CompareItem = compareI;
|
|
PrintItem = printI;
|
|
}
|
|
|
|
VIRT_SPLAY int SplayUserType(pUserType);
|
|
|
|
pUserType Dict_Curr_Item () { // return the top of the tree
|
|
return ((root)? root->item: Nil);
|
|
}
|
|
|
|
pUserType Dict_Item () { // return item from Find/Next/Prev methods
|
|
return (itemCur);
|
|
}
|
|
|
|
int Dict_Empty () { // Is the tree empty
|
|
return (root == Nil);
|
|
}
|
|
|
|
void Dict_Print(int indent = 1); // printout the tree, requires print function
|
|
|
|
Dict_Status Dict_Find(pUserType); // Item searched for
|
|
|
|
Dict_Status Dict_Next(pUserType = Nil); // Next item of a Type
|
|
Dict_Status Dict_Prev(pUserType = Nil); // Previous item of a Type
|
|
|
|
Dict_Status Dict_Insert(pUserType, pUserType); // Add a new item to the tree
|
|
Dict_Status Dict_Delete(pUserType *); // Delete an item form the tree
|
|
// returns the item just deleted
|
|
};
|
|
|
|
// The following macros derive a new class based on Dictionary. They
|
|
// all return a pointer to an item instead of a status_dict.
|
|
// The NewDictArg is used when pUserType-TYPEARG (the key) is embedded
|
|
// in another type-TYPE, which is the first field in the structure.
|
|
|
|
#define DICT_CLASS_ Dictionary
|
|
|
|
#define NewDict(TYPE) NewDictArg(TYPE, TYPE)
|
|
|
|
#define NewDictArg(TYPE, TYPEARG) \
|
|
\
|
|
int TYPE##compare(TYPE *, TYPE *); \
|
|
\
|
|
class TYPE##Dict:public Dictionary { \
|
|
public: \
|
|
\
|
|
TYPE##Dict (PrintFN printI = Nil): DICT_CLASS_ ((CompareFN) TYPE##Compare, printI) {} \
|
|
\
|
|
TYPE * Item () {return( (TYPE *) Dict_Item()); } \
|
|
\
|
|
TYPE * Find(TYPEARG *item ) {Dictionary::Dict_Find((pUserType) item); \
|
|
return((TYPE *) Dict_Item()); } \
|
|
\
|
|
TYPE * Next(TYPEARG * item = Nil){Dictionary::Dict_Next((pUserType) item); \
|
|
return((TYPE *) Dict_Item()); } \
|
|
TYPE * Prev(TYPEARG * item = Nil){Dictionary::Dict_Prev((pUserType) item); \
|
|
return((TYPE *) Dict_Item()); } \
|
|
Dict_Status Insert( TYPE * item1, TYPEARG * item2 ){ \
|
|
return( Dictionary::Dict_Insert((pUserType) item1,(pUserType) item2) );} \
|
|
TYPE * Remove(TYPEARG *item ){ \
|
|
\
|
|
pUserType pT = (pUserType) item; \
|
|
Dictionary::Dict_Delete(&pT); \
|
|
return((TYPE *) pT); } \
|
|
\
|
|
};
|
|
|
|
#endif // __DICT_HXX__
|