tools/kvm/util/rbtree-interval.c

   1 #include <kvm/rbtree-interval.h>
   2 #include <stddef.h>
   3
   4 #define rb_int(n) rb_entry(n, struct rb_int_node, node)
   5
   6 struct rb_int_node *rb_int_search_single(struct rb_root *root, u64 point)
   7 {
   8         struct rb_node *node = root->rb_node;
   9         struct rb_node *lowest = NULL;
  10
  11         while (node) {
  12                 struct rb_int_node *cur = rb_int(node);
  13
  14                 if (node->rb_left && (rb_int(node->rb_left)->max_high > point)) {
  15                         node = node->rb_left;
  16                 } else if (cur->low <= point && cur->high > point) {
  17                         lowest = node;
  18                         break;
  19                 } else if (point > cur->low) {
  20                         node = node->rb_right;
  21                 } else {
  22                         break;
  23                 }
  24         }
  25
  26         if (lowest == NULL)
  27                 return NULL;
  28
  29         return rb_int(lowest);
  30 }
  31
  32 struct rb_int_node *rb_int_search_range(struct rb_root *root, u64 low, u64 high)
  33 {
  34         struct rb_int_node *range;
  35
  36         range = rb_int_search_single(root, low);
  37         if (range == NULL)
  38                 return NULL;
  39
  40         /* We simply verify that 'high' is smaller than the end of the range where 'low' is located */
  41         if (range->high < high)
  42                 return NULL;
  43
  44         return range;
  45 }
  46
  47 static void update_node_max_high(struct rb_node *node, void *arg)
  48 {
  49         struct rb_int_node *i_node = rb_int(node);
  50
  51         i_node->max_high = i_node->high;
  52
  53         if (node->rb_left)
  54                 i_node->max_high = max(i_node->max_high, rb_int(node->rb_left)->max_high);
  55         if (node->rb_right)
  56                 i_node->max_high = max(i_node->max_high, rb_int(node->rb_right)->max_high);
  57 }
  58
  59 int rb_int_insert(struct rb_root *root, struct rb_int_node *i_node)
  60 {
  61         struct rb_node **node   = &(root->rb_node), *parent = NULL;
  62
  63         while (*node) {
  64                 int result      = i_node->low - rb_int(*node)->low;
  65
  66                 parent = *node;
  67                 if (result < 0)
  68                         node    = &((*node)->rb_left);
  69                 else if (result > 0)
  70                         node    = &((*node)->rb_right);
  71                 else
  72                         return 0;
  73         }
  74
  75         rb_link_node(&i_node->node, parent, node);
  76         rb_insert_color(&i_node->node, root);
  77
  78         rb_augment_insert(&i_node->node, update_node_max_high, NULL);
  79         return 1;
  80 }
  81
  82 void rb_int_erase(struct rb_root *root, struct rb_int_node *node)
  83 {
  84         struct rb_node *deepest;
  85
  86         deepest = rb_augment_erase_begin(&node->node);
  87         rb_erase(&node->node, root);
  88         rb_augment_erase_end(deepest, update_node_max_high, NULL);
  89
  90 }