1 #ifndef YASM_INTTREE_H 2 #define YASM_INTTREE_H 3 4 #ifndef YASM_LIB_DECL 5 #define YASM_LIB_DECL 6 #endif 7 8 /* The interval_tree.h and interval_tree.cc files contain code for 9 * interval trees implemented using red-black-trees as described in 10 * the book _Introduction_To_Algorithms_ by Cormen, Leisserson, 11 * and Rivest. 12 */ 13 14 typedef struct IntervalTreeNode { 15 struct IntervalTreeNode *left, *right, *parent; 16 void *data; 17 long low; 18 long high; 19 long maxHigh; 20 int red; /* if red=0 then the node is black */ 21 } IntervalTreeNode; 22 23 typedef struct it_recursion_node { 24 /* This structure stores the information needed when we take the 25 * right branch in searching for intervals but possibly come back 26 * and check the left branch as well. 27 */ 28 IntervalTreeNode *start_node; 29 unsigned int parentIndex; 30 int tryRightBranch; 31 } it_recursion_node; 32 33 typedef struct IntervalTree { 34 /* A sentinel is used for root and for nil. These sentinels are 35 * created when ITTreeCreate is called. root->left should always 36 * point to the node which is the root of the tree. nil points to a 37 * node which should always be black but has aribtrary children and 38 * parent and no key or info. The point of using these sentinels is so 39 * that the root and nil nodes do not require special cases in the code 40 */ 41 IntervalTreeNode *root; 42 IntervalTreeNode *nil; 43 44 /*private:*/ 45 unsigned int recursionNodeStackSize; 46 it_recursion_node * recursionNodeStack; 47 unsigned int currentParent; 48 unsigned int recursionNodeStackTop; 49 } IntervalTree; 50 51 YASM_LIB_DECL 52 IntervalTree *IT_create(void); 53 YASM_LIB_DECL 54 void IT_destroy(IntervalTree *); 55 YASM_LIB_DECL 56 void IT_print(const IntervalTree *); 57 YASM_LIB_DECL 58 void *IT_delete_node(IntervalTree *, IntervalTreeNode *, long *low, 59 long *high); 60 YASM_LIB_DECL 61 IntervalTreeNode *IT_insert(IntervalTree *, long low, long high, void *data); 62 YASM_LIB_DECL 63 IntervalTreeNode *IT_get_predecessor(const IntervalTree *, IntervalTreeNode *); 64 YASM_LIB_DECL 65 IntervalTreeNode *IT_get_successor(const IntervalTree *, IntervalTreeNode *); 66 YASM_LIB_DECL 67 void IT_enumerate(IntervalTree *, long low, long high, void *cbd, 68 void (*callback) (IntervalTreeNode *node, void *cbd)); 69 70 #endif 71
