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@xxxxxxxxxx>
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
