Interval rb-tree allows to directly store interval ranges and quickly lookup an overlap with a single point or a range.
The helper is based on the kernel rb-tree implementation (located in <linux/rbtree.h>) which alows for the augmention of the classical rb-tree to be used as an interval tree. Signed-off-by: Sasha Levin <[email protected]> --- tools/kvm/Makefile | 1 + tools/kvm/include/kvm/rbtree-interval.h | 27 +++++++++ tools/kvm/util/rbtree-interval.c | 91 +++++++++++++++++++++++++++++++ 3 files changed, 119 insertions(+), 0 deletions(-) create mode 100644 tools/kvm/include/kvm/rbtree-interval.h create mode 100644 tools/kvm/util/rbtree-interval.c diff --git a/tools/kvm/Makefile b/tools/kvm/Makefile index 64fdcbe..45897d5 100644 --- a/tools/kvm/Makefile +++ b/tools/kvm/Makefile @@ -42,6 +42,7 @@ OBJS += mptable.o OBJS += threadpool.o OBJS += irq.o OBJS += ../../lib/rbtree.o +OBJS += util/rbtree-interval.o DEPS := $(patsubst %.o,%.d,$(OBJS)) diff --git a/tools/kvm/include/kvm/rbtree-interval.h b/tools/kvm/include/kvm/rbtree-interval.h new file mode 100644 index 0000000..a6688c4 --- /dev/null +++ b/tools/kvm/include/kvm/rbtree-interval.h @@ -0,0 +1,27 @@ +#ifndef KVM__INTERVAL_RBTREE_H +#define KVM__INTERVAL_RBTREE_H + +#include <linux/rbtree.h> +#include <linux/types.h> + +#define RB_INT_INIT(l, h) (struct rb_int_node){.low = l, .high = h} + +struct rb_int_node { + struct rb_node node; + u64 low; + u64 high; + + /* max_high will store the highest high of it's 2 children. */ + u64 max_high; +}; + +/* Return the rb_int_node interval in which 'point' is located. */ +struct rb_int_node *rb_int_search_single(struct rb_root *root, u64 point); + +/* Return the rb_int_node in which start:len is located. */ +struct rb_int_node *rb_int_search_range(struct rb_root *root, u64 low, u64 high); + +int rb_int_insert(struct rb_root *root, struct rb_int_node *data); +void rb_int_erase(struct rb_root *root, struct rb_int_node *node); + +#endif diff --git a/tools/kvm/util/rbtree-interval.c b/tools/kvm/util/rbtree-interval.c new file mode 100644 index 0000000..b0d36b0 --- /dev/null +++ b/tools/kvm/util/rbtree-interval.c @@ -0,0 +1,91 @@ +#include <kvm/rbtree-interval.h> +#include <stddef.h> + +#define rb_int(n) rb_entry(n, struct rb_int_node, node) +#define max(x, y) ((x) > (y)) ? (x) : (y) + +struct rb_int_node *rb_int_search_single(struct rb_root *root, u64 point) +{ + struct rb_node *node = root->rb_node; + struct rb_node *lowest = NULL; + + while (node) { + struct rb_int_node *cur = rb_int(node); + + if (node->rb_left && (rb_int(node->rb_left)->max_high > point)) { + node = node->rb_left; + } else if (cur->low <= point && cur->high > point) { + lowest = node; + break; + } else if (point > cur->low) { + node = node->rb_right; + } else { + break; + } + } + + if (lowest == NULL) + return NULL; + + return rb_int(lowest); +} + +struct rb_int_node *rb_int_search_range(struct rb_root *root, u64 low, u64 high) +{ + struct rb_int_node *range; + + range = rb_int_search_single(root, low); + if (range == NULL) + return NULL; + + /* We simply verify that 'high' is smaller than the end of the range where 'low' is located */ + if (range->high < high) + return NULL; + + return range; +} + +static void update_node_max_high(struct rb_node *node, void *arg) +{ + struct rb_int_node *i_node = rb_int(node); + + i_node->max_high = i_node->high; + + if (node->rb_left) + i_node->max_high = max(i_node->max_high, rb_int(node->rb_left)->high); + if (node->rb_right) + i_node->max_high = max(i_node->max_high, rb_int(node->rb_right)->high); +} + +int rb_int_insert(struct rb_root *root, struct rb_int_node *i_node) +{ + struct rb_node **node = &(root->rb_node), *parent = NULL; + + while (*node) { + int result = i_node->low - rb_int(*node)->low; + + parent = *node; + if (result < 0) + node = &((*node)->rb_left); + else if (result > 0) + node = &((*node)->rb_right); + else + return 0; + } + + rb_link_node(&i_node->node, parent, node); + rb_insert_color(&i_node->node, root); + + rb_augment_insert(*node, update_node_max_high, NULL); + return 1; +} + +void rb_int_erase(struct rb_root *root, struct rb_int_node *node) +{ + struct rb_node *deepest; + + deepest = rb_augment_erase_begin(&node->node); + rb_erase(&node->node, root); + rb_augment_erase_end(deepest, update_node_max_high, NULL); + +} -- 1.7.5.rc3 -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
