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
14typedef 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
23typedef 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
33typedef 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
51YASM_LIB_DECL
52IntervalTree *IT_create(void);
53YASM_LIB_DECL
54void IT_destroy(IntervalTree *);
55YASM_LIB_DECL
56void IT_print(const IntervalTree *);
57YASM_LIB_DECL
58void *IT_delete_node(IntervalTree *, IntervalTreeNode *, long *low,
59                     long *high);
60YASM_LIB_DECL
61IntervalTreeNode *IT_insert(IntervalTree *, long low, long high, void *data);
62YASM_LIB_DECL
63IntervalTreeNode *IT_get_predecessor(const IntervalTree *, IntervalTreeNode *);
64YASM_LIB_DECL
65IntervalTreeNode *IT_get_successor(const IntervalTree *, IntervalTreeNode *);
66YASM_LIB_DECL
67void IT_enumerate(IntervalTree *, long low, long high, void *cbd,
68                  void (*callback) (IntervalTreeNode *node, void *cbd));
69
70#endif
71