00001 /* rbTree - rbTreeRed-rbTreeBlack Tree - a type of binary tree which 00002 * automatically keeps relatively balanced during 00003 * inserts and deletions. 00004 * original author: Shane Saunders 00005 * adapted into local conventions: Jim Kent 00006 */ 00007 #ifndef RBTREE_H 00008 #define RBTREE_H 00009 00010 typedef enum {rbTreeRed,rbTreeBlack} rbTreeColor; 00011 00012 00013 /* Structure type for nodes in the red-black tree. */ 00014 struct rbTreeNode 00015 { 00016 struct rbTreeNode *left, *right; /* Children. */ 00017 rbTreeColor color; /* Heart of algorithm. */ 00018 void *item; /* Item stored in tree */ 00019 }; 00020 00021 /* Structure type for the red-black tree. */ 00022 struct rbTree 00023 { 00024 struct rbTree *next; /* Next tree in list. */ 00025 struct rbTreeNode *root; /* Root of tree */ 00026 int n; /* Number of items in tree. */ 00027 int (* compare)(void *, void *);/* Comparison function */ 00028 struct rbTreeNode **stack; /* Ancestor stack. */ 00029 struct lm *lm; /* Local memory pool. */ 00030 struct rbTreeNode *freeList; /* List of nodes to reuse. */ 00031 }; 00032 00033 struct rbTree *rbTreeNew(int (*compare)(void *, void *)); 00034 /* Allocates space for a red-black tree and returns a pointer 00035 * to it. The function compare compares they keys of two items, and returns a 00036 * negative, zero, or positive integer depending on whether the first item is 00037 * less than, equal to, or greater than the second. */ 00038 00039 void rbTreeFree(struct rbTree **pTree); 00040 /* Frees space used by the red-black tree pointed to by t. */ 00041 00042 struct rbTree *rbTreeNewDetailed(int (*compare)(void *, void *), struct lm *lm, 00043 struct rbTreeNode *stack[128]); 00044 /* Allocate rbTree on an existing local memory & stack. This is for cases 00045 * where you want a lot of trees, and don't want the overhead for each one. 00046 * Note, to clean these up, just do freez(&rbTree) rather than rbFreeTree(&rbTree). */ 00047 00048 void *rbTreeAdd(struct rbTree *t, void *item); 00049 /* Inserts an item into the red-black tree pointed to by t, 00050 * according the the value its key. The key of an item in the red-black 00051 * tree must be unique among items in the tree. If an item with the same key 00052 * already exists in the tree, a pointer to that item is returned. Otherwise, 00053 * NULL is returned, indicating insertion was successful. 00054 */ 00055 00056 void *rbTreeFind(struct rbTree *t, void *item); 00057 /* Find an item in the red-black tree with the same key as the 00058 * item pointed to by `item'. Returns a pointer to the item found, or NULL 00059 * if no item was found. 00060 */ 00061 00062 void *rbTreeRemove(struct rbTree *t, void *item); 00063 /* rbTreeRemove() - Delete an item in the red-black tree with the same key as 00064 * the item pointed to by `item'. Returns a pointer to the deleted item, 00065 * and NULL if no item was found. 00066 */ 00067 00068 void rbTreeTraverseRange(struct rbTree *tree, void *minItem, void *maxItem, 00069 void (*doItem)(void *item)); 00070 /* Apply doItem function to all items in tree such that 00071 * minItem <= item <= maxItem */ 00072 00073 struct slRef *rbTreeItemsInRange(struct rbTree *tree, void *minItem, void *maxItem); 00074 /* Return a sorted list of references to items in tree between range. 00075 * slFreeList this list when done. */ 00076 00077 void rbTreeTraverse(struct rbTree *tree, void (*doItem)(void *item)); 00078 /* Apply doItem function to all items in tree */ 00079 00080 struct slRef *rbTreeItems(struct rbTree *tree); 00081 /* Return sorted list of items. slFreeList this when done.*/ 00082 00083 void rbTreeDump(struct rbTree *tree, FILE *f, 00084 void (*dumpItem)(void *item, FILE *f)); 00085 /* Dump out rb tree to file, mostly for debugging. */ 00086 00087 int rbTreeCmpString(void *a, void *b); 00088 /* Set up rbTree so as to work on strings. */ 00089 00090 int rbTreeCmpWord(void *a, void *b); 00091 /* Set up rbTree so as to work on case-insensitive strings. */ 00092 00093 #endif /* RBTREE_H */ 00094
1.5.2