1 #include <kvm/rbtree-interval.h>
2 #include <stddef.h>
3 #include <errno.h>
4
rb_int_search_single(struct rb_root * root,u64 point)5 struct rb_int_node *rb_int_search_single(struct rb_root *root, u64 point)
6 {
7 struct rb_node *node = root->rb_node;
8
9 while (node) {
10 struct rb_int_node *cur = rb_int(node);
11
12 if (point < cur->low)
13 node = node->rb_left;
14 else if (cur->high <= point)
15 node = node->rb_right;
16 else
17 return cur;
18 }
19
20 return NULL;
21 }
22
rb_int_search_range(struct rb_root * root,u64 low,u64 high)23 struct rb_int_node *rb_int_search_range(struct rb_root *root, u64 low, u64 high)
24 {
25 struct rb_int_node *range;
26
27 range = rb_int_search_single(root, low);
28 if (range == NULL)
29 return NULL;
30
31 /* We simply verify that 'high' is smaller than the end of the range where 'low' is located */
32 if (range->high < high)
33 return NULL;
34
35 return range;
36 }
37
rb_int_insert(struct rb_root * root,struct rb_int_node * i_node)38 int rb_int_insert(struct rb_root *root, struct rb_int_node *i_node)
39 {
40 struct rb_node **node = &root->rb_node, *parent = NULL;
41
42 while (*node) {
43 struct rb_int_node *cur = rb_int(*node);
44
45 parent = *node;
46 if (i_node->high <= cur->low)
47 node = &cur->node.rb_left;
48 else if (cur->high <= i_node->low)
49 node = &cur->node.rb_right;
50 else
51 return -EEXIST;
52 }
53
54 rb_link_node(&i_node->node, parent, node);
55 rb_insert_color(&i_node->node, root);
56
57 return 0;
58 }
59