Re: [PATCH 02/11] lib/interval-tree: add an equivalent tree with [a,b) intervals

From: Michel Lespinasse <walken@google.com>
To: Davidlohr Bueso <dave@stgolabs.net>
Cc: akpm@linux-foundation.org, peterz@infradead.org,
	linux-kernel@vger.kernel.org, linux-mm@kvack.org,
	dri-devel@lists.freedesktop.org, linux-rdma@vger.kernel.org,
	Davidlohr Bueso <dbueso@suse.de>
Subject: Re: [PATCH 02/11] lib/interval-tree: add an equivalent tree with [a,b) intervals
Date: Fri, 4 Oct 2019 04:02:24 -0700	[thread overview]
Message-ID: <20191004110224.GA253758@google.com> (raw)
In-Reply-To: <20191003201858.11666-3-dave@stgolabs.net>

On Thu, Oct 03, 2019 at 01:18:49PM -0700, Davidlohr Bueso wrote:
> +/*									      \
> + * 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		      \
Should be 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)		      \
Should be start < node->ITSUBTREE
> +					continue;			      \
> +			}						      \
> +		}							      \
> +		return NULL;	/* No match */				      \
> +	}								      \
> +}									      \

Other than that, the change looks good to me.

This is something I might use, regardless of the status of converting
other current users.

The name "interval_tree_gen.h" makes it ambiguous wether gen stands
for "generic" or "generator". This may sounds like a criticism,
but it's not - I think it really stands for both :)

Reviewed-by: Michel Lespinasse <walken@google.com>

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.