From patchwork Tue May 17 12:07:59 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sasha Levin X-Patchwork-Id: 791322 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by demeter1.kernel.org (8.14.4/8.14.3) with ESMTP id p4HC8Qnf026957 for ; Tue, 17 May 2011 12:08:26 GMT Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754228Ab1EQMIN (ORCPT ); Tue, 17 May 2011 08:08:13 -0400 Received: from mail-fx0-f46.google.com ([209.85.161.46]:53493 "EHLO mail-fx0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753710Ab1EQMIM (ORCPT ); Tue, 17 May 2011 08:08:12 -0400 Received: by fxm17 with SMTP id 17so369761fxm.19 for ; Tue, 17 May 2011 05:08:10 -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=40NVNg7MefheMUAW4NgE28ijucSAslK+qCW1x5SVBF8=; b=tlkrkvnOu0Gua2am/riPcpSbeXrwfRe20qDiLfoocAJwkijTkrAStSW29dxgQlPsHU 6BMjxSr6f9UP3AveHquP9M9ZXkeO+U35WBC6mvZonlsGF96DXkKXocU6f9pNtWdedGU3 qfdTNfXilMNeIp3dveh3H3MyYsoH+coxCOZAk= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=from:to:cc:subject:date:message-id:x-mailer; b=CoypZJC9V68qAjEPUw0w2/L3SKeFySNey5zK1yxmhR9SXdDBSKF7/5NkcvkSCwTyFR c7pvMS5b8tfv7qCoRYbvqPDd9E8N7qiUARVW0/s/Vx4UF7M8p8pMIDGi/katKXcwCdmv Il7wAkHujsI+Dex75fJkzApiv5E3GqzEQGu50= Received: by 10.223.72.13 with SMTP id k13mr710590faj.85.1305634090790; Tue, 17 May 2011 05:08:10 -0700 (PDT) Received: from localhost.localdomain ([188.120.132.169]) by mx.google.com with ESMTPS id 14sm192083fas.30.2011.05.17.05.08.08 (version=TLSv1/SSLv3 cipher=OTHER); Tue, 17 May 2011 05:08:10 -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 V3] kvm tools: Add interval red-black tree helper Date: Tue, 17 May 2011 15:07:59 +0300 Message-Id: <1305634080-24789-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 (demeter1.kernel.org [140.211.167.41]); Tue, 17 May 2011 12:08:26 +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. Acked-by: Ingo Molnar Signed-off-by: Sasha Levin --- 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 +#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/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 +#include + +#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); + +}