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