From: Davidlohr Bueso <dave@stgolabs.net>
To: akpm@linux-foundation.org
Cc: walken@google.com, peterz@infradead.org,
linux-kernel@vger.kernel.org, linux-mm@kvack.org,
dri-devel@lists.freedesktop.org, linux-rdma@vger.kernel.org,
dave@stgolabs.net, Davidlohr Bueso <dbueso@suse.de>
Subject: [PATCH 02/11] lib/interval-tree: add an equivalent tree with [a,b) intervals
Date: Thu, 3 Oct 2019 13:18:49 -0700 [thread overview]
Message-ID: <20191003201858.11666-3-dave@stgolabs.net> (raw)
In-Reply-To: <20191003201858.11666-1-dave@stgolabs.net>
While the kernel's interval tree implementation uses closed intervals, all
users (with the exception of query stabbing) really want half closed intervals,
specifically [a, b), and will explicitly correct this before calling the tree api.
This patch simply duplicates the include/linuxinterval_tree_generic.h header into
a interval_tree_gen.h (gen as in 'generic' and 'generate' :-) with two differences:
- The 'last' endpoint is renamed 'end'; this is something lib/interval_tree.c will
also need to update, but that is later in the series.
- The lookup calls have been adapted accordingly, such that users need not need to
do the subtraction by one fixup.
No users are ported over in this patch.
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
include/linux/interval_tree_gen.h | 179 ++++++++++++++++++++++++++++++++++++++
1 file changed, 179 insertions(+)
create mode 100644 include/linux/interval_tree_gen.h
diff --git a/include/linux/interval_tree_gen.h b/include/linux/interval_tree_gen.h
new file mode 100644
index 000000000000..5d446c0bd89a
--- /dev/null
+++ b/include/linux/interval_tree_gen.h
@@ -0,0 +1,179 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/*
+ Interval Trees
+ (C) 2012 Michel Lespinasse <walken@google.com>
+*/
+
+#include <linux/rbtree_augmented.h>
+
+/*
+ * Template for implementing interval trees
+ *
+ * ITSTRUCT: struct type of the interval tree nodes
+ * ITRB: name of struct rb_node field within ITSTRUCT
+ * ITTYPE: type of the interval endpoints
+ * ITSUBTREE: name of ITTYPE field within ITSTRUCT holding end-in-subtree
+ * ITSTART(n): start endpoint of ITSTRUCT node n
+ * ITEND(n): end/last endpoint of ITSTRUCT node n
+ * ITSTATIC: 'static' or empty
+ * ITPREFIX: prefix to use for the inline tree definitions
+ *
+ * Note - before using this, please consider if generic version
+ * (interval_tree.h) would work for you...
+ */
+
+#define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, \
+ ITSTART, ITEND, ITSTATIC, ITPREFIX) \
+ \
+/* Callbacks for augmented rbtree insert and remove */ \
+ \
+RB_DECLARE_CALLBACKS_MAX(static, ITPREFIX ## _augment, \
+ ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, ITEND) \
+ \
+/* Insert / remove interval nodes from the tree */ \
+ \
+ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, \
+ struct rb_root_cached *root) \
+{ \
+ struct rb_node **link = &root->rb_root.rb_node, *rb_parent = NULL; \
+ ITTYPE start = ITSTART(node), end = ITEND(node); \
+ ITSTRUCT *parent; \
+ bool leftmost = true; \
+ \
+ while (*link) { \
+ rb_parent = *link; \
+ parent = rb_entry(rb_parent, ITSTRUCT, ITRB); \
+ if (parent->ITSUBTREE < end) \
+ parent->ITSUBTREE = end; \
+ if (start < ITSTART(parent)) \
+ link = &parent->ITRB.rb_left; \
+ else { \
+ link = &parent->ITRB.rb_right; \
+ leftmost = false; \
+ } \
+ } \
+ \
+ node->ITSUBTREE = end; \
+ rb_link_node(&node->ITRB, rb_parent, link); \
+ rb_insert_augmented_cached(&node->ITRB, root, \
+ leftmost, &ITPREFIX ## _augment); \
+} \
+ \
+ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \
+ struct rb_root_cached *root) \
+{ \
+ rb_erase_augmented_cached(&node->ITRB, root, &ITPREFIX ## _augment); \
+} \
+ \
+/* \
+ * Iterate over intervals intersecting [start;end) \
+ * \
+ * Note that a node's interval intersects [start;end) iff: \
+ * Cond1: ITSTART(node) < end \
+ * and \
+ * Cond2: start < ITEND(node) \
+ */ \
+ \
+static ITSTRUCT * \
+ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE end) \
+{ \
+ while (true) { \
+ /* \
+ * Loop invariant: start <= node->ITSUBTREE \
+ * (Cond2 is satisfied by one of the subtree nodes) \
+ */ \
+ if (node->ITRB.rb_left) { \
+ ITSTRUCT *left = rb_entry(node->ITRB.rb_left, \
+ ITSTRUCT, ITRB); \
+ if (start < left->ITSUBTREE) { \
+ /* \
+ * Some nodes in left subtree satisfy Cond2. \
+ * Iterate to find the leftmost such node N. \
+ * If it also satisfies Cond1, that's the \
+ * match we are looking for. Otherwise, there \
+ * is no matching interval as nodes to the \
+ * right of N can't satisfy Cond1 either. \
+ */ \
+ node = left; \
+ continue; \
+ } \
+ } \
+ if (ITSTART(node) < end) { /* Cond1 */ \
+ if (start < ITEND(node)) /* Cond2 */ \
+ return node; /* node is leftmost match */ \
+ if (node->ITRB.rb_right) { \
+ node = rb_entry(node->ITRB.rb_right, \
+ ITSTRUCT, ITRB); \
+ if (start <= node->ITSUBTREE) \
+ continue; \
+ } \
+ } \
+ return NULL; /* No match */ \
+ } \
+} \
+ \
+ITSTATIC ITSTRUCT * \
+ITPREFIX ## _iter_first(struct rb_root_cached *root, \
+ ITTYPE start, ITTYPE end) \
+{ \
+ ITSTRUCT *node, *leftmost; \
+ \
+ if (!root->rb_root.rb_node) \
+ return NULL; \
+ \
+ /* \
+ * Fastpath range intersection/overlap where we compare the \
+ * smallest 'start' and largest 'end' in the tree. For the latter, \
+ * we rely on the root node, which by augmented interval tree \
+ * property, holds the largest value in its end-in-subtree. \
+ * This allows mitigating some of the tree walk overhead for \
+ * for non-intersecting ranges, maintained and consulted in O(1). \
+ */ \
+ node = rb_entry(root->rb_root.rb_node, ITSTRUCT, ITRB); \
+ if (node->ITSUBTREE <= start) /* !Cond2 */ \
+ return NULL; \
+ \
+ leftmost = rb_entry(root->rb_leftmost, ITSTRUCT, ITRB); \
+ if (ITSTART(leftmost) >= end) /* !Cond1 */ \
+ return NULL; \
+ \
+ return ITPREFIX ## _subtree_search(node, start, end); \
+} \
+ \
+ITSTATIC ITSTRUCT * \
+ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE end) \
+{ \
+ struct rb_node *rb = node->ITRB.rb_right, *prev; \
+ \
+ while (true) { \
+ /* \
+ * Loop invariants: \
+ * Cond1: ITSTART(node) < end \
+ * rb == node->ITRB.rb_right \
+ * \
+ * First, search right subtree if suitable \
+ */ \
+ if (rb) { \
+ ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB); \
+ if (start < right->ITSUBTREE) \
+ return ITPREFIX ## _subtree_search(right, \
+ start, end); \
+ } \
+ \
+ /* Move up the tree until we come from a node's left child */ \
+ do { \
+ rb = rb_parent(&node->ITRB); \
+ if (!rb) \
+ return NULL; \
+ prev = &node->ITRB; \
+ node = rb_entry(rb, ITSTRUCT, ITRB); \
+ rb = node->ITRB.rb_right; \
+ } while (prev == rb); \
+ \
+ /* Check if the node intersects [start;end) */ \
+ if (end <= ITSTART(node)) /* !Cond1 */ \
+ return NULL; \
+ else if (start < ITEND(node)) /* Cond2 */ \
+ return node; \
+ } \
+}
--
2.16.4
next prev parent reply other threads:[~2019-10-03 20:20 UTC|newest]
Thread overview: 38+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-10-03 20:18 [PATCH -next 00/11] lib/interval-tree: move to half closed intervals Davidlohr Bueso
2019-10-03 20:18 ` [PATCH 01/11] mm: introduce vma_interval_tree_foreach_stab() Davidlohr Bueso
2019-10-03 20:18 ` Davidlohr Bueso [this message]
2019-10-04 11:02 ` [PATCH 02/11] lib/interval-tree: add an equivalent tree with [a,b) intervals Michel Lespinasse
2019-10-03 20:18 ` [PATCH 03/11] drm/amdgpu: convert amdgpu_vm_it to half closed intervals Davidlohr Bueso
2019-10-04 6:54 ` Koenig, Christian
2019-10-04 11:36 ` Michel Lespinasse
2019-10-04 12:39 ` Christian König
2019-10-03 20:18 ` [PATCH 04/11] drm: convert drm_mm_interval_tree " Davidlohr Bueso
2019-10-03 20:18 ` [PATCH 05/11] IB/hfi1: convert __mmu_int_rb " Davidlohr Bueso
2019-10-04 11:50 ` Michel Lespinasse
2019-10-04 19:41 ` Davidlohr Bueso
2019-10-03 20:18 ` [PATCH 06/11] IB,usnic: convert usnic_uiom_interval_tree " Davidlohr Bueso
2019-10-03 20:18 ` [PATCH 07/11] vhost: convert vhost_umem_interval_tree " Davidlohr Bueso
2019-10-04 12:10 ` Michel Lespinasse
2019-10-04 19:44 ` Davidlohr Bueso
2019-10-10 5:49 ` Jason Wang
2019-10-03 20:18 ` [PATCH 08/11] mm: convert vma_interval_tree " Davidlohr Bueso
2019-10-03 20:41 ` Matthew Wilcox
2019-10-04 12:30 ` Michel Lespinasse
2019-10-03 20:18 ` [PATCH 09/11] lib/interval-tree: convert interval_tree " Davidlohr Bueso
2019-10-03 22:50 ` kbuild test robot
2019-10-04 6:57 ` Koenig, Christian
2019-10-04 7:20 ` Koenig, Christian
2019-10-08 16:59 ` Davidlohr Bueso
2019-10-03 20:18 ` [PATCH 10/11] lib: drop interval_tree_generic.h Davidlohr Bueso
2019-10-03 20:18 ` [PATCH 11/11] x86/mm, pat: convert pat tree to generic interval tree Davidlohr Bueso
2019-10-07 15:33 ` Ingo Molnar
2019-10-21 23:24 ` Davidlohr Bueso
2019-10-03 20:32 ` [PATCH -next 00/11] lib/interval-tree: move to half closed intervals Matthew Wilcox
2019-10-03 21:10 ` Davidlohr Bueso
2019-10-04 12:43 ` Michel Lespinasse
2019-10-04 0:26 ` Jason Gunthorpe
2019-10-04 2:48 ` Davidlohr Bueso
2019-10-04 13:15 ` Michel Lespinasse
2019-10-04 16:03 ` Matthew Wilcox
2019-10-04 19:35 ` Davidlohr Bueso
2019-10-04 17:45 ` Jason Gunthorpe
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20191003201858.11666-3-dave@stgolabs.net \
--to=dave@stgolabs.net \
--cc=akpm@linux-foundation.org \
--cc=dbueso@suse.de \
--cc=dri-devel@lists.freedesktop.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=linux-rdma@vger.kernel.org \
--cc=peterz@infradead.org \
--cc=walken@google.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).