libyasm/inttree.h

   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