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