  `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 convertingother current users.The name "interval_tree_gen.h" makes it ambiguous wether gen standsfor "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" LespinasseA program is never fully debugged until the last user dies.`   