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