From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752358AbaEBNxH (ORCPT ); Fri, 2 May 2014 09:53:07 -0400 Received: from mail-qg0-f48.google.com ([209.85.192.48]:57497 "EHLO mail-qg0-f48.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752172AbaEBNxE (ORCPT ); Fri, 2 May 2014 09:53:04 -0400 From: j.glisse@gmail.com To: linux-mm@kvack.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Cc: =?UTF-8?q?J=C3=A9r=C3=B4me=20Glisse?= Subject: [PATCH 04/11] interval_tree: helper to find previous item of a node in rb interval tree Date: Fri, 2 May 2014 09:52:03 -0400 Message-Id: <1399038730-25641-5-git-send-email-j.glisse@gmail.com> X-Mailer: git-send-email 1.9.0 In-Reply-To: <1399038730-25641-1-git-send-email-j.glisse@gmail.com> References: <1399038730-25641-1-git-send-email-j.glisse@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Jérôme Glisse It is often usefull to find the entry right before a given one in an rb interval tree. Signed-off-by: Jérôme Glisse --- include/linux/interval_tree_generic.h | 79 +++++++++++++++++++++++++++++++++++ 1 file changed, 79 insertions(+) diff --git a/include/linux/interval_tree_generic.h b/include/linux/interval_tree_generic.h index 58370e1..97dd71b 100644 --- a/include/linux/interval_tree_generic.h +++ b/include/linux/interval_tree_generic.h @@ -188,4 +188,83 @@ ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ else if (start <= ITLAST(node)) /* Cond2 */ \ return node; \ } \ +} \ + \ +static ITSTRUCT * \ +ITPREFIX ## _subtree_rmost(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ +{ \ + while (true) { \ + /* \ + * Loop invariant: last >= ITSTART(node) \ + * (Cond1 is satisfied) \ + */ \ + if (node->ITRB.rb_right) { \ + ITSTRUCT *right = rb_entry(node->ITRB.rb_right, \ + ITSTRUCT, ITRB); \ + if (last >= ITSTART(right)) { \ + /* \ + * Some nodes in right subtree satisfy Cond1. \ + * Iterate to find the rightmost such node N. \ + * If it also satisfies Cond2, that's the \ + * match we are looking for. \ + */ \ + node = right; \ + continue; \ + } \ + /* Left branch might still have a candidate. */ \ + if (right->ITRB.rb_left) { \ + right = rb_entry(right->ITRB.rb_left, \ + ITSTRUCT, ITRB); \ + if (last >= ITSTART(right)) { \ + node = right; \ + continue; \ + } \ + } \ + } \ + /* At this point node is the rightmost candidate. */ \ + if (last >= ITSTART(node)) { /* Cond1 */ \ + if (start <= ITLAST(node)) /* Cond2 */ \ + return node; /* node is rightmost match */ \ + } \ + return NULL; /* No match */ \ + } \ +} \ + \ +ITSTATIC ITSTRUCT * \ +ITPREFIX ## _iter_prev(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ +{ \ + struct rb_node *rb = node->ITRB.rb_left, *prev; \ + \ + while (true) { \ + /* \ + * Loop invariants: \ + * Cond2: start <= ITLAST(node) \ + * rb == node->ITRB.rb_left \ + * \ + * First, search left subtree if suitable \ + */ \ + if (rb) { \ + ITSTRUCT *left = rb_entry(rb, ITSTRUCT, ITRB); \ + if (start <= left->ITSUBTREE) \ + return ITPREFIX ## _subtree_rmost(left, \ + start, \ + last); \ + } \ + \ + /* Move up the tree until we come from a node's right child */\ + do { \ + rb = rb_parent(&node->ITRB); \ + if (!rb) \ + return NULL; \ + prev = &node->ITRB; \ + node = rb_entry(rb, ITSTRUCT, ITRB); \ + rb = node->ITRB.rb_left; \ + } while (prev == rb); \ + \ + /* Check if the node intersects [start;last] */ \ + if (start > ITLAST(node)) /* !Cond2 */ \ + return NULL; \ + else if (ITSTART(node) <= last) /* Cond1 */ \ + return node; \ + } \ } -- 1.9.0 From mboxrd@z Thu Jan 1 00:00:00 1970 From: j.glisse@gmail.com Subject: [PATCH 04/11] interval_tree: helper to find previous item of a node in rb interval tree Date: Fri, 2 May 2014 09:52:03 -0400 Message-ID: <1399038730-25641-5-git-send-email-j.glisse@gmail.com> References: <1399038730-25641-1-git-send-email-j.glisse@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Cc: =?UTF-8?q?J=C3=A9r=C3=B4me=20Glisse?= To: linux-mm@kvack.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Return-path: In-Reply-To: <1399038730-25641-1-git-send-email-j.glisse@gmail.com> Sender: owner-linux-mm@kvack.org List-Id: linux-fsdevel.vger.kernel.org From: J=C3=A9r=C3=B4me Glisse It is often usefull to find the entry right before a given one in an rb interval tree. Signed-off-by: J=C3=A9r=C3=B4me Glisse --- include/linux/interval_tree_generic.h | 79 +++++++++++++++++++++++++++++= ++++++ 1 file changed, 79 insertions(+) diff --git a/include/linux/interval_tree_generic.h b/include/linux/interv= al_tree_generic.h index 58370e1..97dd71b 100644 --- a/include/linux/interval_tree_generic.h +++ b/include/linux/interval_tree_generic.h @@ -188,4 +188,83 @@ ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start,= ITTYPE last) \ else if (start <=3D ITLAST(node)) /* Cond2 */ \ return node; \ } \ +} \ + \ +static ITSTRUCT * \ +ITPREFIX ## _subtree_rmost(ITSTRUCT *node, ITTYPE start, ITTYPE last) = \ +{ \ + while (true) { \ + /* \ + * Loop invariant: last >=3D ITSTART(node) \ + * (Cond1 is satisfied) \ + */ \ + if (node->ITRB.rb_right) { \ + ITSTRUCT *right =3D rb_entry(node->ITRB.rb_right, \ + ITSTRUCT, ITRB); \ + if (last >=3D ITSTART(right)) { \ + /* \ + * Some nodes in right subtree satisfy Cond1. \ + * Iterate to find the rightmost such node N. \ + * If it also satisfies Cond2, that's the \ + * match we are looking for. \ + */ \ + node =3D right; \ + continue; \ + } \ + /* Left branch might still have a candidate. */ \ + if (right->ITRB.rb_left) { \ + right =3D rb_entry(right->ITRB.rb_left, \ + ITSTRUCT, ITRB); \ + if (last >=3D ITSTART(right)) { \ + node =3D right; \ + continue; \ + } \ + } \ + } \ + /* At this point node is the rightmost candidate. */ \ + if (last >=3D ITSTART(node)) { /* Cond1 */ \ + if (start <=3D ITLAST(node)) /* Cond2 */ \ + return node; /* node is rightmost match */ \ + } \ + return NULL; /* No match */ \ + } \ +} \ + \ +ITSTATIC ITSTRUCT * \ +ITPREFIX ## _iter_prev(ITSTRUCT *node, ITTYPE start, ITTYPE last) = \ +{ \ + struct rb_node *rb =3D node->ITRB.rb_left, *prev; \ + \ + while (true) { \ + /* \ + * Loop invariants: \ + * Cond2: start <=3D ITLAST(node) \ + * rb =3D=3D node->ITRB.rb_left \ + * \ + * First, search left subtree if suitable \ + */ \ + if (rb) { \ + ITSTRUCT *left =3D rb_entry(rb, ITSTRUCT, ITRB); \ + if (start <=3D left->ITSUBTREE) \ + return ITPREFIX ## _subtree_rmost(left, \ + start, \ + last); \ + } \ + \ + /* Move up the tree until we come from a node's right child */\ + do { \ + rb =3D rb_parent(&node->ITRB); \ + if (!rb) \ + return NULL; \ + prev =3D &node->ITRB; \ + node =3D rb_entry(rb, ITSTRUCT, ITRB); \ + rb =3D node->ITRB.rb_left; \ + } while (prev =3D=3D rb); \ + \ + /* Check if the node intersects [start;last] */ \ + if (start > ITLAST(node)) /* !Cond2 */ \ + return NULL; \ + else if (ITSTART(node) <=3D last) /* Cond1 */ \ + return node; \ + } \ } --=20 1.9.0 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qc0-f181.google.com (mail-qc0-f181.google.com [209.85.216.181]) by kanga.kvack.org (Postfix) with ESMTP id 2E7386B0044 for ; Fri, 2 May 2014 09:53:04 -0400 (EDT) Received: by mail-qc0-f181.google.com with SMTP id m20so1633023qcx.12 for ; Fri, 02 May 2014 06:53:03 -0700 (PDT) Received: from mail-qa0-x22e.google.com (mail-qa0-x22e.google.com [2607:f8b0:400d:c00::22e]) by mx.google.com with ESMTPS id c43si14185480qge.49.2014.05.02.06.53.03 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 02 May 2014 06:53:03 -0700 (PDT) Received: by mail-qa0-f46.google.com with SMTP id w8so4344116qac.33 for ; Fri, 02 May 2014 06:53:03 -0700 (PDT) From: j.glisse@gmail.com Subject: [PATCH 04/11] interval_tree: helper to find previous item of a node in rb interval tree Date: Fri, 2 May 2014 09:52:03 -0400 Message-Id: <1399038730-25641-5-git-send-email-j.glisse@gmail.com> In-Reply-To: <1399038730-25641-1-git-send-email-j.glisse@gmail.com> References: <1399038730-25641-1-git-send-email-j.glisse@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Sender: owner-linux-mm@kvack.org List-ID: To: linux-mm@kvack.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Cc: =?UTF-8?q?J=C3=A9r=C3=B4me=20Glisse?= From: JA(C)rA'me Glisse It is often usefull to find the entry right before a given one in an rb interval tree. Signed-off-by: JA(C)rA'me Glisse --- include/linux/interval_tree_generic.h | 79 +++++++++++++++++++++++++++++++++++ 1 file changed, 79 insertions(+) diff --git a/include/linux/interval_tree_generic.h b/include/linux/interval_tree_generic.h index 58370e1..97dd71b 100644 --- a/include/linux/interval_tree_generic.h +++ b/include/linux/interval_tree_generic.h @@ -188,4 +188,83 @@ ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ else if (start <= ITLAST(node)) /* Cond2 */ \ return node; \ } \ +} \ + \ +static ITSTRUCT * \ +ITPREFIX ## _subtree_rmost(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ +{ \ + while (true) { \ + /* \ + * Loop invariant: last >= ITSTART(node) \ + * (Cond1 is satisfied) \ + */ \ + if (node->ITRB.rb_right) { \ + ITSTRUCT *right = rb_entry(node->ITRB.rb_right, \ + ITSTRUCT, ITRB); \ + if (last >= ITSTART(right)) { \ + /* \ + * Some nodes in right subtree satisfy Cond1. \ + * Iterate to find the rightmost such node N. \ + * If it also satisfies Cond2, that's the \ + * match we are looking for. \ + */ \ + node = right; \ + continue; \ + } \ + /* Left branch might still have a candidate. */ \ + if (right->ITRB.rb_left) { \ + right = rb_entry(right->ITRB.rb_left, \ + ITSTRUCT, ITRB); \ + if (last >= ITSTART(right)) { \ + node = right; \ + continue; \ + } \ + } \ + } \ + /* At this point node is the rightmost candidate. */ \ + if (last >= ITSTART(node)) { /* Cond1 */ \ + if (start <= ITLAST(node)) /* Cond2 */ \ + return node; /* node is rightmost match */ \ + } \ + return NULL; /* No match */ \ + } \ +} \ + \ +ITSTATIC ITSTRUCT * \ +ITPREFIX ## _iter_prev(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ +{ \ + struct rb_node *rb = node->ITRB.rb_left, *prev; \ + \ + while (true) { \ + /* \ + * Loop invariants: \ + * Cond2: start <= ITLAST(node) \ + * rb == node->ITRB.rb_left \ + * \ + * First, search left subtree if suitable \ + */ \ + if (rb) { \ + ITSTRUCT *left = rb_entry(rb, ITSTRUCT, ITRB); \ + if (start <= left->ITSUBTREE) \ + return ITPREFIX ## _subtree_rmost(left, \ + start, \ + last); \ + } \ + \ + /* Move up the tree until we come from a node's right child */\ + do { \ + rb = rb_parent(&node->ITRB); \ + if (!rb) \ + return NULL; \ + prev = &node->ITRB; \ + node = rb_entry(rb, ITSTRUCT, ITRB); \ + rb = node->ITRB.rb_left; \ + } while (prev == rb); \ + \ + /* Check if the node intersects [start;last] */ \ + if (start > ITLAST(node)) /* !Cond2 */ \ + return NULL; \ + else if (ITSTART(node) <= last) /* Cond1 */ \ + return node; \ + } \ } -- 1.9.0 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org