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 <levinsasha...@gmail.com>
---
tools/kvm/Makefile | 1 +
tools/kvm/include/kvm/interval-rbtree.h | 27 +++++++++
tools/kvm/util/interval-rbtree.c | 97 +++++++++++++++++++++++++++++++
3 files changed, 125 insertions(+), 0 deletions(-)
create mode 100644 tools/kvm/include/kvm/interval-rbtree.h
create mode 100644 tools/kvm/util/interval-rbtree.c
diff --git a/tools/kvm/Makefile b/tools/kvm/Makefile
index 64fdcbe..b175e18 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/interval-rbtree.o
DEPS := $(patsubst %.o,%.d,$(OBJS))
diff --git a/tools/kvm/include/kvm/interval-rbtree.h
b/tools/kvm/include/kvm/interval-rbtree.h
new file mode 100644
index 0000000..13862b3
--- /dev/null
+++ b/tools/kvm/include/kvm/interval-rbtree.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 in which p is located. */
+struct rb_int_node *rb_int_search_single(struct rb_root *root, u64 p);
+
+/* 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/interval-rbtree.c b/tools/kvm/util/interval-rbtree.c
new file mode 100644
index 0000000..8957c62
--- /dev/null
+++ b/tools/kvm/util/interval-rbtree.c
@@ -0,0 +1,97 @@
+#include <kvm/interval-rbtree.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#define RB_INT(n) container_of(n, struct rb_int_node, node)
+
+struct rb_int_node *rb_int_search_single(struct rb_root *root, u64 p)
+{
+ struct rb_node *node = root->rb_node;
+ struct rb_node *lowest = NULL;
+
+ while (node) {
+ struct rb_int_node *cur = RB_INT(node);
+ struct rb_int_node *left;
+ if (node->rb_left)
+ left = RB_INT(node->rb_left);
+ if (node->rb_left && (RB_INT(node->rb_left)->max_high > p)) {
+ node = node->rb_left;
+ } else if (cur->low <= p && cur->high > p) {
+ lowest = node;
+ break;
+ } else if (p > cur->low) {
+ node = node->rb_right;
+ } else {
+ break;
+ }
+ }
+
+ if (lowest == NULL)
+ return NULL;
+
+ return container_of(lowest, struct rb_int_node, node);
+}
+
+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)
+{
+ u64 high_left = 0, high_right = 0;
+ struct rb_int_node *data = RB_INT(node);
+
+ if (node->rb_left)
+ high_left = RB_INT(node->rb_left)->high;
+ if (node->rb_right)
+ high_right = RB_INT(node->rb_right)->high;
+
+ data->max_high = (high_left > high_right) ? high_left : high_right;
+ if (data->max_high < RB_INT(node)->high)
+ data->max_high = RB_INT(node)->high;
+}
+
+int rb_int_insert(struct rb_root *root, struct rb_int_node *data)
+{
+ struct rb_node **new = &(root->rb_node), *parent = NULL;
+
+ while (*new) {
+ struct rb_int_node *this = RB_INT(*new);
+ int result = data->low - this->low;
+
+ parent = *new;
+ if (result < 0)
+ new = &((*new)->rb_left);
+ else if (result > 0)
+ new = &((*new)->rb_right);
+ else
+ return 0;
+ }
+
+ rb_link_node(&data->node, parent, new);
+ rb_insert_color(&data->node, root);
+
+ rb_augment_insert(*new, 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 majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
