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.
Acked-by: Ingo Molnar <mingo@xxxxxxx>
Signed-off-by: Sasha Levin <levinsasha928@xxxxxxxxx>
---
tools/kvm/Makefile | 1 +
tools/kvm/include/kvm/rbtree-interval.h | 27 +++++++++
tools/kvm/include/linux/kernel.h | 13 +++++
tools/kvm/util/rbtree-interval.c | 90 +++++++++++++++++++++++++++++++
4 files changed, 131 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/include/linux/kernel.h b/tools/kvm/include/linux/kernel.h
index 8d83037..d2ec4a3 100644
--- a/tools/kvm/include/linux/kernel.h
+++ b/tools/kvm/include/linux/kernel.h
@@ -1,3 +1,4 @@
+
#ifndef KVM__LINUX_KERNEL_H_
#define KVM__LINUX_KERNEL_H_
@@ -23,4 +24,16 @@
(type *)((char *)__mptr - offsetof(type, member)); })
#endif
+#define min(x, y) ({ \
+ typeof(x) _min1 = (x); \
+ typeof(y) _min2 = (y); \
+ (void) (&_min1 == &_min2); \
+ _min1 < _min2 ? _min1 : _min2; })
+
+#define max(x, y) ({ \
+ typeof(x) _max1 = (x); \
+ typeof(y) _max2 = (y); \
+ (void) (&_max1 == &_max2); \
+ _max1 > _max2 ? _max1 : _max2; })
+
#endif
diff --git a/tools/kvm/util/rbtree-interval.c b/tools/kvm/util/rbtree-interval.c
new file mode 100644
index 0000000..735e912
--- /dev/null
+++ b/tools/kvm/util/rbtree-interval.c
@@ -0,0 +1,90 @@
+#include <kvm/rbtree-interval.h>
+#include <stddef.h>
+
+#define rb_int(n) rb_entry(n, struct rb_int_node, node)
+
+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 majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
