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)->high); 55 if (node->rb_right) 56 i_node->max_high = max(i_node->max_high, rb_int(node->rb_right)->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(*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 } 91