From patchwork Tue May 17 10:28:42 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sasha Levin X-Patchwork-Id: 791162 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 p4HATLiM007625 for ; Tue, 17 May 2011 10:29:21 GMT Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753432Ab1EQK3S (ORCPT ); Tue, 17 May 2011 06:29:18 -0400 Received: from mail-fx0-f46.google.com ([209.85.161.46]:43483 "EHLO mail-fx0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752535Ab1EQK3R (ORCPT ); Tue, 17 May 2011 06:29:17 -0400 Received: by fxm17 with SMTP id 17so315122fxm.19 for ; Tue, 17 May 2011 03:29:16 -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=2GjHFH5EjIzBNbIwa52X6pET79FPgkOoY/TwxlaZWmo=; b=nDyD8zQ/KbAH5A36bXYTIVt0oTg3A9Uswea1QVDMzxe4bfTRlO8BjnOvoQoIo/XPwU OgJwWN43HJyO9zfImGhsB7CD2e2jmethJOVyipq8QzSuLaAYLCNzEg0a2Vn2O2eDz1Iq I6BlLvh6rPqsiRbP6x3dKSCxmUsouk073vCZM= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=from:to:cc:subject:date:message-id:x-mailer; b=B7KIxZkI/8RfRoiPb2XUVQvB3xrbqCzO7RfFokENHcb7E6dwsssRoC9mh3Pk65wzZ5 Cd48TWWlmV6/Ox4hur5gnnXepP20C851du2JFXCWyJO38qvEMRb+BKprFrMg2OpXk5VI k0fZXimlBm5I8IroyIS/C8h8LW7jhnI6WXRfk= Received: by 10.223.98.5 with SMTP id o5mr610192fan.33.1305628156208; Tue, 17 May 2011 03:29:16 -0700 (PDT) Received: from localhost.localdomain ([188.120.132.169]) by mx.google.com with ESMTPS id c24sm154436fak.31.2011.05.17.03.29.14 (version=TLSv1/SSLv3 cipher=OTHER); Tue, 17 May 2011 03:29:15 -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 V2] kvm tools: Add interval red-black tree helper Date: Tue, 17 May 2011 13:28:42 +0300 Message-Id: <1305628123-18440-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 10:29:21 +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 Acked-by: Ingo Molnar --- 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 +#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 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 +#include + +#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); + +}