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 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 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 38 /* 39 * Update a node after it has been linked into the tree: 40 */ 41 static void propagate_callback(struct rb_node *node, struct rb_node *stop) 42 { 43 struct rb_int_node *i_node; 44 45 if (node == stop) 46 return; 47 48 i_node = rb_int(node); 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 /* 58 * Copy the extra data to a new node: 59 */ 60 static void copy_callback(struct rb_node *node_old, struct rb_node *node_new) 61 { 62 struct rb_int_node *i_node_old = rb_int(node_old); 63 struct rb_int_node *i_node_new = rb_int(node_new); 64 65 i_node_new->low = i_node_old->low; 66 i_node_new->high = i_node_old->high; 67 68 i_node_new->max_high = i_node_old->max_high; 69 } 70 71 /* 72 * Update after tree rotation: 73 */ 74 static void rotate_callback(struct rb_node *node_old, struct rb_node *node_new) 75 { 76 propagate_callback(node_old, NULL); 77 propagate_callback(node_new, NULL); 78 } 79 80 /* 81 * All augmented rbtree callbacks: 82 */ 83 struct rb_augment_callbacks callbacks = { 84 .propagate = propagate_callback, 85 .copy = copy_callback, 86 .rotate = rotate_callback, 87 }; 88 89 int rb_int_insert(struct rb_root *root, struct rb_int_node *i_node) 90 { 91 struct rb_node **node = &root->rb_node, *parent = NULL; 92 93 while (*node) { 94 struct rb_int_node *cur = rb_int(*node); 95 96 parent = *node; 97 if (i_node->high <= cur->low) 98 node = &cur->node.rb_left; 99 else if (cur->high <= i_node->low) 100 node = &cur->node.rb_right; 101 else 102 return -EEXIST; 103 } 104 105 rb_link_node(&i_node->node, parent, node); 106 rb_insert_augmented(&i_node->node, root, &callbacks); 107 108 return 0; 109 } 110 111 void rb_int_erase(struct rb_root *root, struct rb_int_node *node) 112 { 113 rb_erase_augmented(&node->node, root, &callbacks); 114 } 115