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