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