Re: [PATCH 01/23] util/interval-tree: Introduce interval_tree_free_nodes

[Pierrick Bouvier <pierrick.bouvier@linaro.org>]

On 10/9/24 08:08, Richard Henderson wrote:
> Provide a general-purpose release-all-nodes operation, that allows
> for the IntervalTreeNode to be embeded within a larger structure.
> 
> Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
> ---
>   include/qemu/interval-tree.h | 11 +++++++++++
>   util/interval-tree.c         | 20 ++++++++++++++++++++
>   util/selfmap.c               | 13 +------------
>   3 files changed, 32 insertions(+), 12 deletions(-)
> 
> diff --git a/include/qemu/interval-tree.h b/include/qemu/interval-tree.h
> index 25006debe8..d90ea6d17f 100644
> --- a/include/qemu/interval-tree.h
> +++ b/include/qemu/interval-tree.h
> @@ -96,4 +96,15 @@ IntervalTreeNode *interval_tree_iter_first(IntervalTreeRoot *root,
>   IntervalTreeNode *interval_tree_iter_next(IntervalTreeNode *node,
>                                             uint64_t start, uint64_t last);
>   
> +/**
> + * interval_tree_free_nodes:
> + * @root: root of the tree
> + * @it_offset: offset from outermost type to IntervalTreeNode
> + *
> + * Free, via g_free, all nodes under @root.  IntervalTreeNode may
> + * not be the true type of the nodes allocated; @it_offset gives
> + * the offset from the outermost type to the IntervalTreeNode member.
> + */
> +void interval_tree_free_nodes(IntervalTreeRoot *root, size_t it_offset);
> +
>   #endif /* QEMU_INTERVAL_TREE_H */
> diff --git a/util/interval-tree.c b/util/interval-tree.c
> index 53465182e6..663d3ec222 100644
> --- a/util/interval-tree.c
> +++ b/util/interval-tree.c
> @@ -639,6 +639,16 @@ static void rb_erase_augmented_cached(RBNode *node, RBRootLeftCached *root,
>       rb_erase_augmented(node, &root->rb_root, augment);
>   }
>   
> +static void rb_node_free(RBNode *rb, size_t rb_offset)
> +{
> +    if (rb->rb_left) {
> +        rb_node_free(rb->rb_left, rb_offset);
> +    }
> +    if (rb->rb_right) {
> +        rb_node_free(rb->rb_right, rb_offset);
> +    }
> +    g_free((void *)rb - rb_offset);
> +}
>   
>   /*
>    * Interval trees.
> @@ -870,6 +880,16 @@ IntervalTreeNode *interval_tree_iter_next(IntervalTreeNode *node,
>       }
>   }
>   
> +void interval_tree_free_nodes(IntervalTreeRoot *root, size_t it_offset)
> +{
> +    if (root && root->rb_root.rb_node) {
> +        rb_node_free(root->rb_root.rb_node,
> +                     it_offset + offsetof(IntervalTreeNode, rb));
> +        root->rb_root.rb_node = NULL;
> +        root->rb_leftmost = NULL;
> +    }
> +}
> +
>   /* Occasionally useful for calling from within the debugger. */
>   #if 0
>   static void debug_interval_tree_int(IntervalTreeNode *node,
> diff --git a/util/selfmap.c b/util/selfmap.c
> index 483cb617e2..d2b86da301 100644
> --- a/util/selfmap.c
> +++ b/util/selfmap.c
> @@ -87,23 +87,12 @@ IntervalTreeRoot *read_self_maps(void)
>    * @root: an interval tree
>    *
>    * Free a tree of MapInfo structures.
> - * Since we allocated each MapInfo in one chunk, we need not consider the
> - * contents and can simply free each RBNode.
>    */
>   
> -static void free_rbnode(RBNode *n)
> -{
> -    if (n) {
> -        free_rbnode(n->rb_left);
> -        free_rbnode(n->rb_right);
> -        g_free(n);
> -    }
> -}
> -
>   void free_self_maps(IntervalTreeRoot *root)
>   {
>       if (root) {
> -        free_rbnode(root->rb_root.rb_node);
> +        interval_tree_free_nodes(root, offsetof(MapInfo, itree));
>           g_free(root);
>       }
>   }

Reviewed-by: Pierrick Bouvier <pierrick.bouvier@linaro.org>