From patchwork Tue May 17 06:58:34 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sasha Levin X-Patchwork-Id: 790632 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by demeter2.kernel.org (8.14.4/8.14.3) with ESMTP id p4H71615020125 for ; Tue, 17 May 2011 07:01:07 GMT Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752333Ab1EQHAz (ORCPT ); Tue, 17 May 2011 03:00:55 -0400 Received: from mail-fx0-f46.google.com ([209.85.161.46]:59875 "EHLO mail-fx0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752115Ab1EQHAy (ORCPT ); Tue, 17 May 2011 03:00:54 -0400 Received: by fxm17 with SMTP id 17so211588fxm.19 for ; Tue, 17 May 2011 00:00:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:from:to:cc:subject:date:message-id:x-mailer; bh=Q6Rz3JciPFii+m7B5PrC21eB8ejsxr13nR3Lb5A9XsI=; b=XuaMXfnBBQzV9AxActitQMjEXgS4SM6ryAN6NHvSQHtYpp/0s0cznkJf8J1P40vr02 btcEWvcN7W5r7e1u6w7sr6ruzq0vvVZydOfNI7B+V2xgFs/LHHSrziknX6DUfavbz7vq 0PPT4qwt8kUEXirgP4m2z77o/LRafH5EvYGt8= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=from:to:cc:subject:date:message-id:x-mailer; b=kwbVWk3ugYKoE6PBgLwiR/Kqb+l568h0hJo2bHspCfLj5OfgrZwobrAoeA/JPn584L 4VjGM0Zn/+KXJYUO6l7/2gdEReRRg/fIwRSYes35+XVaYMLhfuIiqAt/i8S7Kd8Yt5x2 4n+ydbQuHyBP/hv/6fsFdkrGsEO21viXS+W+0= Received: by 10.223.48.139 with SMTP id r11mr359385faf.63.1305615653280; Tue, 17 May 2011 00:00:53 -0700 (PDT) Received: from localhost.localdomain ([188.120.132.169]) by mx.google.com with ESMTPS id r13sm74029fax.32.2011.05.17.00.00.51 (version=TLSv1/SSLv3 cipher=OTHER); Tue, 17 May 2011 00:00:52 -0700 (PDT) From: Sasha Levin To: penberg@kernel.org Cc: mingo@elte.hu, asias.hejun@gmail.com, prasadjoshi124@gmail.com, gorcunov@gmail.com, kvm@vger.kernel.org, john@jfloren.net, Sasha Levin Subject: [PATCH 1/2] kvm tools: Add interval red-black tree helper Date: Tue, 17 May 2011 09:58:34 +0300 Message-Id: <1305615515-13913-1-git-send-email-levinsasha928@gmail.com> X-Mailer: git-send-email 1.7.5.rc3 Sender: kvm-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: kvm@vger.kernel.org X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-4.2.6 (demeter2.kernel.org [140.211.167.43]); Tue, 17 May 2011 07:01:07 +0000 (UTC) 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 ) which alows for the augmention of the classical rb-tree to be used as an interval tree. Signed-off-by: Sasha Levin --- 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 +#include + +#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 +#include +#include + +#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); + +}