Re: [Qemu-devel] [PATCH 07/10] util: implement simple interval tree logic

[Jason Wang <jasowang@redhat.com>]

On 2018年04月25日 12:51, Peter Xu wrote:
> Introduce a simplest interval tree implementation based on GTree.
> Current implementation is mostly tailored to maintain and trace device
> mapped IOVA ranges, but still it might be useful to other modules in the
> future.
>
> It is naive in that it even does not allow user to pass in private
> structs along with the ranges.  However it's good in that the tree can
> do mergings of ranges when necessary when without such information.
>
> Signed-off-by: Peter Xu <peterx@redhat.com>
> ---
>   include/qemu/interval-tree.h | 130 ++++++++++++++++++++++++++
>   util/interval-tree.c         | 217 +++++++++++++++++++++++++++++++++++++++++++
>   util/Makefile.objs           |   1 +
>   3 files changed, 348 insertions(+)
>   create mode 100644 include/qemu/interval-tree.h
>   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..4485f4b338
> --- /dev/null
> +++ b/include/qemu/interval-tree.h
> @@ -0,0 +1,130 @@
> +/*
> + * An very simplified interval tree implementation based on GTree.
> + *
> + * Copyright 2018 Red Hat, Inc.
> + *
> + * Authors:
> + *  Peter Xu <peterx@redhat.com>
> + *
> + * This work is licensed under the terms of the GNU GPL, version 2 or later.
> + */
> +#ifndef __INTERVAL_TREE_H__
> +#define __INTERVAL_TREE_H__
> +
> +/*
> + * Currently the interval tree will only allow to keep ranges
> + * information, and no extra user data is allowed for each element.  A
> + * benefit is that we can merge adjacent ranges internally within the
> + * tree.  It can save a lot of memory when the ranges are splitted but
> + * mostly continuous.
> + *
> + * Note that current implementation does not provide any thread
> + * protections.  Callers of the interval tree should be responsible
> + * for the thread safety issue.
> + */
> +
> +#include <glib.h>
> +
> +#define  IT_OK           (0)
> +#define  IT_ERR_OVERLAP  (-1)
> +
> +typedef unsigned long long ITValue;
> +typedef struct ITTree ITTree;
> +typedef gboolean (*it_tree_iterator)(ITValue start, ITValue end);
> +
> +struct ITRange {
> +    ITValue start;
> +    ITValue end;
> +};
> +typedef struct ITRange ITRange;
> +
> +/**
> + * it_tree_new:
> + *
> + * Create a new interval tree.
> + *
> + * Returns: the tree pointer when succeeded, or NULL if error.
> + */
> +ITTree *it_tree_new(void);
> +
> +/**
> + * it_tree_insert:
> + *
> + * @tree: the interval tree to insert
> + * @start: the start of range, inclusive
> + * @end: the end of range, inclusive
> + *
> + * Insert an interval range to the tree.  If there is overlapped
> + * ranges, IT_ERR_OVERLAP will be returned.
> + *
> + * Return: 0 if succeeded, or <0 if error.
> + */
> +int it_tree_insert(ITTree *tree, ITValue start, ITValue end);
> +
> +/**
> + * it_tree_remove:
> + *
> + * @tree: the interval tree to remove range from
> + * @start: the start of range, inclusive
> + * @end: the end of range, inclusive
> + *
> + * Remove an range from the tree.  The range does not need to be
> + * exactly what has inserted.  All the ranges that are included in the
> + * provided range will be removed from the tree.
> + *
> + * Return: 0 if succeeded, or <0 if error.
> + */
> +int it_tree_remove(ITTree *tree, ITValue start, ITValue end);
> +
> +/**
> + * it_tree_find:
> + *
> + * @tree: the interval tree to search from
> + * @start: the start of range, inclusive
> + * @end: the end of range, inclusive
> + *
> + * Search for a range in the interval tree that overlaps with the
> + * range specified.  Only the first found range will be returned.
> + *
> + * Return: ITRange if found, or NULL if not found.  Note: the returned
> + * ITRange pointer is maintained internally.  User should only read
> + * the content but never modify or free the content.
> + */
> +ITRange *it_tree_find(ITTree *tree, ITValue start, ITValue end);
> +
> +/**
> + * it_tree_find_value:
> + *
> + * @tree: the interval tree to search from
> + * @value: the value to find
> + *
> + * Similar to it_tree_find(), but it tries to find range (value, value).
> + *
> + * Return: same as it_tree_find().
> + */
> +ITRange *it_tree_find_value(ITTree *tree, ITValue value);
> +
> +/**
> + * it_tree_foreach:
> + *
> + * @tree: the interval tree to iterate on
> + * @iterator: the interator for the ranges, return true to stop
> + *
> + * Search for a range in the interval tree.
> + *
> + * Return: 1 if found any overlap, 0 if not, <0 if error.
> + */
> +void it_tree_foreach(ITTree *tree, it_tree_iterator iterator);
> +
> +/**
> + * it_tree_destroy:
> + *
> + * @tree: the interval tree to destroy
> + *
> + * Destroy an existing interval tree.
> + *
> + * Return: None.
> + */
> +void it_tree_destroy(ITTree *tree);
> +
> +#endif
> diff --git a/util/interval-tree.c b/util/interval-tree.c
> new file mode 100644
> index 0000000000..0e7a37c2c6
> --- /dev/null
> +++ b/util/interval-tree.c
> @@ -0,0 +1,217 @@
> +/*
> + * An very simplified interval tree implementation based on GTree.
> + *
> + * Copyright 2018 Red Hat, Inc.
> + *
> + * Authors:
> + *  Peter Xu <peterx@redhat.com>
> + *
> + * This work is licensed under the terms of the GNU GPL, version 2 or later.
> + */
> +
> +#include <glib.h>
> +#include "qemu/interval-tree.h"
> +
> +/*
> + * Each element of the internal tree is an ITRange.  It is shared
> + * between the key and value of the element, or we can see it a tree
> + * with keys only but no values.
> + */
> +
> +struct ITTree {
> +    GTree *tree;
> +};
> +
> +static int it_tree_compare(gconstpointer a, gconstpointer b, gpointer data)
> +{
> +    const ITRange *r1 = a, *r2 = b;
> +
> +    if (r1->start > r2->end) {
> +        return 1;
> +    }
> +
> +    if (r1->end < r2->start) {
> +        return -1;
> +    }
> +
> +    /* Overlapped */
> +    return 0;
> +}
> +
> +/* Find out intersection of range A and B, put into OUT */
> +static inline void it_range_and(ITRange *out, ITRange *a, ITRange *b)
> +{
> +    out->start = MAX(a->start, b->start);
> +    out->end = MIN(a->end, b->end);
> +}
> +
> +static inline gboolean it_range_equal(ITRange *a, ITRange *b)
> +{
> +    return a->start == b->start && a->end == b->end;
> +}
> +
> +/* Whether ITRange A is superset of B? */
> +static inline gboolean it_range_cover(ITRange *a, ITRange *b)
> +{
> +    return a->start <= b->start && a->end >= b->end;
> +}
> +
> +ITTree *it_tree_new(void)
> +{
> +    ITTree *ittree = g_new0(ITTree, 1);
> +
> +    /* We don't have values actually, no need to free */
> +    ittree->tree = g_tree_new_full(it_tree_compare, NULL, g_free, NULL);
> +
> +    return ittree;
> +}
> +
> +ITRange *it_tree_find(ITTree *tree, ITValue start, ITValue end)
> +{
> +    ITRange range;
> +
> +    g_assert(tree);
> +
> +    range.start = start;
> +    range.end = end;
> +
> +    return g_tree_lookup(tree->tree, &range);
> +}
> +
> +ITRange *it_tree_find_value(ITTree *tree, ITValue value)
> +{
> +    return it_tree_find(tree, value, value);
> +}
> +
> +static inline void it_tree_insert_internal(GTree *gtree, ITRange *range)
> +{
> +    /* Key and value are sharing the same range data */
> +    g_tree_insert(gtree, range, range);
> +}
> +
> +int it_tree_insert(ITTree *tree, ITValue start, ITValue end)
> +{
> +    ITRange *range = g_new0(ITRange, 1), *overlap;
> +    GTree *gtree;
> +
> +    g_assert(tree);
> +    g_assert(start <= end);
> +
> +    gtree = tree->tree;
> +
> +    range->start = start;
> +    range->end = end;
> +
> +    /* We don't allow to insert range that overlaps with existings */
> +    if (g_tree_lookup(gtree, range)) {
> +        g_free(range);
> +        return IT_ERR_OVERLAP;
> +    }
> +
> +    /* Merge left adjacent range */
> +    overlap = it_tree_find_value(tree, start - 1);
> +    if (overlap) {
> +        range->start = overlap->start;
> +        g_tree_remove(gtree, overlap);
> +    }
> +
> +    /* Merge right adjacent range */
> +    overlap = it_tree_find_value(tree, end + 1);
> +    if (overlap) {
> +        range->end = overlap->end;
> +        g_tree_remove(gtree, overlap);
> +    }
> +
> +    /* Key and value are sharing the same range data */
> +    it_tree_insert_internal(gtree, range);

A small optimization here is to delay the allocation until you're sure 
there's not overlapping.

> +
> +    return IT_OK;
> +}
> +
> +static gboolean it_tree_traverse(gpointer key, gpointer value,
> +                                gpointer data)
> +{
> +    it_tree_iterator iterator = data;
> +    ITRange *range = key;
> +
> +    g_assert(key == value);
> +
> +    return iterator(range->start, range->end);
> +}
> +
> +void it_tree_foreach(ITTree *tree, it_tree_iterator iterator)
> +{
> +    g_assert(tree && iterator);
> +    g_tree_foreach(tree->tree, it_tree_traverse, iterator);
> +}
> +
> +/* Remove subset `range', which is part of `overlap'. */
> +static void it_tree_remove_subset(GTree *gtree, const ITRange *overlap,
> +                                  const ITRange *range)
> +{
> +    ITRange *range1, *range2;
> +
> +    if (overlap->start < range->start) {
> +        range1 = g_new0(ITRange, 1);
> +        range1->start = overlap->start;
> +        range1->end = range->start - 1;
> +    } else {
> +        range1 = NULL;
> +    }
> +    if (range->end < overlap->end) {
> +        range2 = g_new0(ITRange, 1);
> +        range2->start = range->end + 1;
> +        range2->end = overlap->end;
> +    } else {
> +        range2 = NULL;
> +    }
> +
> +    g_tree_remove(gtree, overlap);
> +
> +    if (range1) {
> +        it_tree_insert_internal(gtree, range1);
> +    }
> +    if (range2) {
> +        it_tree_insert_internal(gtree, range2);
> +    }
> +}
> +
> +int it_tree_remove(ITTree *tree, ITValue start, ITValue end)
> +{
> +    ITRange range = { .start = start, .end = end }, *overlap, and;
> +    GTree *gtree;
> +
> +    g_assert(tree);
> +
> +    gtree = tree->tree;
> +    while ((overlap = g_tree_lookup(gtree, &range))) {
> +        if (it_range_equal(overlap, &range)) {
> +            /* Exactly what we want to remove; done */
> +            g_tree_remove(gtree, overlap);
> +            break;
> +        } else if (it_range_cover(overlap, &range)) {
> +            /* Split existing range into two; done */
> +            it_tree_remove_subset(gtree, overlap, &range);
> +            break;
> +        } else if (it_range_cover(&range, overlap)) {
> +            /* Drop this range and continue */
> +            g_tree_remove(gtree, overlap);
> +        } else {
> +            /*
> +             * The range to remove has intersection with existing
> +             * ranges.  Remove part of the range and continue
> +             */
> +            it_range_and(&and, overlap, &range);
> +            g_assert(and.start <= and.end);
> +            it_tree_remove_subset(gtree, overlap, &and);
> +        }
> +    }
> +

Looks like what we need here is just calculate the intersection part the 
remove it.

Thanks

> +    return IT_OK;
> +}
> +
> +void it_tree_destroy(ITTree *tree)
> +{
> +    g_tree_destroy(tree->tree);
> +    g_free(tree);
> +}
> diff --git a/util/Makefile.objs b/util/Makefile.objs
> index 728c3541db..4ac33910ed 100644
> --- a/util/Makefile.objs
> +++ b/util/Makefile.objs
> @@ -47,4 +47,5 @@ util-obj-y += qht.o
>   util-obj-y += range.o
>   util-obj-y += stats64.o
>   util-obj-y += systemd.o
> +util-obj-y += interval-tree.o
>   util-obj-$(CONFIG_LINUX) += vfio-helpers.o