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