Re: [PATCH v3 1/8] util: Add interval-tree.c

[Philippe Mathieu-Daudé]

On 9/12/22 06:19, Richard Henderson wrote:
> Copy and simplify the Linux kernel's interval_tree_generic.h,
> instantiating for uint64_t.
>
> Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
> Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
> ---
>   include/qemu/interval-tree.h    |  99 ++++
>   tests/unit/test-interval-tree.c | 209 ++++++++
>   util/interval-tree.c            | 882 ++++++++++++++++++++++++++++++++
>   tests/unit/meson.build          |   1 +
>   util/meson.build                |   1 +
>   5 files changed, 1192 insertions(+)
>   create mode 100644 include/qemu/interval-tree.h
>   create mode 100644 tests/unit/test-interval-tree.c
>   create mode 100644 util/interval-tree.c
>
> diff --git a/include/qemu/interval-tree.h b/include/qemu/interval-tree.h
> new file mode 100644
> index 0000000000..25006debe8
> --- /dev/null
> +++ b/include/qemu/interval-tree.h
> @@ -0,0 +1,99 @@
> +/* SPDX-License-Identifier: GPL-2.0-or-later */
> +/*
> + * Interval trees.
> + *
> + * Derived from include/linux/interval_tree.h and its dependencies.
> + */
> +
> +#ifndef QEMU_INTERVAL_TREE_H
> +#define QEMU_INTERVAL_TREE_H

> +
> +#endif /* QEMU_INTERVAL_TREE_H */
> diff --git a/tests/unit/test-interval-tree.c b/tests/unit/test-interval-tree.c
> new file mode 100644
> index 0000000000..119817a019
> --- /dev/null
> +++ b/tests/unit/test-interval-tree.c



> +/* Occasionally useful for calling from within the debugger. */
> +#if 0
> +static void debug_interval_tree_int(IntervalTreeNode *node,
> +                                    const char *dir, int level)
> +{
> +    printf("%4d %*s %s [%" PRIu64 ",%" PRIu64 "] subtree_last:%" PRIu64 "\n",
> +           level, level + 1, dir, rb_is_red(&node->rb) ? "r" : "b",
> +           node->start, node->last, node->subtree_last);
> +
> +    if (node->rb.rb_left) {
> +        debug_interval_tree_int(rb_to_itree(node->rb.rb_left), "<", level + 1);
> +    }
> +    if (node->rb.rb_right) {
> +        debug_interval_tree_int(rb_to_itree(node->rb.rb_right), ">", level + 
> 1);
> +    }
> +}
> +
> +void debug_interval_tree(IntervalTreeNode *node);

If you think this function is helpful, shouldn't we declare it in the
header within CONFIG_DEBUG_TCG guards?

> +void debug_interval_tree(IntervalTreeNode *node)
> +{
> +    if (node) {
> +        debug_interval_tree_int(node, "*", 0);
> +    } else {
> +        printf("null\n");
> +    }
> +}
> +#endif