145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifndef YASM_INTTREE_H 245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define YASM_INTTREE_H 345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifndef YASM_LIB_DECL 545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define YASM_LIB_DECL 645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* The interval_tree.h and interval_tree.cc files contain code for 945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * interval trees implemented using red-black-trees as described in 1045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * the book _Introduction_To_Algorithms_ by Cormen, Leisserson, 1145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * and Rivest. 1245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 1345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 1445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgtypedef struct IntervalTreeNode { 1545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct IntervalTreeNode *left, *right, *parent; 1645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org void *data; 1745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org long low; 1845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org long high; 1945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org long maxHigh; 2045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org int red; /* if red=0 then the node is black */ 2145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} IntervalTreeNode; 2245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 2345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgtypedef struct it_recursion_node { 2445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* This structure stores the information needed when we take the 2545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * right branch in searching for intervals but possibly come back 2645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * and check the left branch as well. 2745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 2845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode *start_node; 2945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org unsigned int parentIndex; 3045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org int tryRightBranch; 3145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} it_recursion_node; 3245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 3345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgtypedef struct IntervalTree { 3445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* A sentinel is used for root and for nil. These sentinels are 3545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * created when ITTreeCreate is called. root->left should always 3645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * point to the node which is the root of the tree. nil points to a 3745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * node which should always be black but has aribtrary children and 3845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * parent and no key or info. The point of using these sentinels is so 3945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * that the root and nil nodes do not require special cases in the code 4045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 4145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode *root; 4245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode *nil; 4345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 4445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/*private:*/ 4545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org unsigned int recursionNodeStackSize; 4645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it_recursion_node * recursionNodeStack; 4745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org unsigned int currentParent; 4845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org unsigned int recursionNodeStackTop; 4945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} IntervalTree; 5045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 5145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 5245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIntervalTree *IT_create(void); 5345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 5445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgvoid IT_destroy(IntervalTree *); 5545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 5645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgvoid IT_print(const IntervalTree *); 5745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 5845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgvoid *IT_delete_node(IntervalTree *, IntervalTreeNode *, long *low, 5945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org long *high); 6045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 6145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIntervalTreeNode *IT_insert(IntervalTree *, long low, long high, void *data); 6245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 6345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIntervalTreeNode *IT_get_predecessor(const IntervalTree *, IntervalTreeNode *); 6445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 6545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIntervalTreeNode *IT_get_successor(const IntervalTree *, IntervalTreeNode *); 6645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 6745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgvoid IT_enumerate(IntervalTree *, long low, long high, void *cbd, 6845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org void (*callback) (IntervalTreeNode *node, void *cbd)); 6945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 7045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 71