@@ -231,6 +231,7 @@ safe_stack=""
use_containers="yes"
gdb_bin=$(command -v "gdb-multiarch" || command -v "gdb")
gdb_arches=""
+glib_has_gslice="no"
if test -e "$source_path/.git"
then
@@ -1494,6 +1495,17 @@ for i in $glib_modules; do
fi
done
+# Check whether glib has gslice, which we have to avoid for correctness.
+# TODO: remove this check and the corresponding workaround (qtree) when
+# the minimum supported glib is >= $glib_dropped_gslice_version.
+glib_dropped_gslice_version=2.75.3
+for i in $glib_modules; do
+ if ! $pkg_config --atleast-version=$glib_dropped_gslice_version $i; then
+ glib_has_gslice="yes"
+ break
+ fi
+done
+
glib_bindir="$($pkg_config --variable=bindir glib-2.0)"
if test -z "$glib_bindir" ; then
glib_bindir="$($pkg_config --variable=prefix glib-2.0)"/bin
@@ -2420,6 +2432,9 @@ echo "GLIB_CFLAGS=$glib_cflags" >> $config_host_mak
echo "GLIB_LIBS=$glib_libs" >> $config_host_mak
echo "GLIB_BINDIR=$glib_bindir" >> $config_host_mak
echo "GLIB_VERSION=$($pkg_config --modversion glib-2.0)" >> $config_host_mak
+if test "$glib_has_gslice" = "yes" ; then
+ echo "HAVE_GLIB_WITH_SLICE_ALLOCATOR=y" >> $config_host_mak
+fi
echo "QEMU_LDFLAGS=$QEMU_LDFLAGS" >> $config_host_mak
echo "EXESUF=$EXESUF" >> $config_host_mak
@@ -508,6 +508,10 @@ glib = declare_dependency(compile_args: config_host['GLIB_CFLAGS'].split(),
})
# override glib dep with the configure results (for subprojects)
meson.override_dependency('glib-2.0', glib)
+# pass down whether Glib has the slice allocator
+if config_host.has_key('HAVE_GLIB_WITH_SLICE_ALLOCATOR')
+ config_host_data.set('HAVE_GLIB_WITH_SLICE_ALLOCATOR', true)
+endif
gio = not_found
gdbus_codegen = not_found
new file mode 100644
@@ -0,0 +1,201 @@
+/*
+ * GLIB - Library of useful routines for C programming
+ * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
+ *
+ * SPDX-License-Identifier: LGPL-2.1-or-later
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+/*
+ * Modified by the GLib Team and others 1997-2000. See the AUTHORS
+ * file for a list of people on the GLib Team. See the ChangeLog
+ * files for a list of changes. These files are distributed with
+ * GLib at ftp://ftp.gtk.org/pub/gtk/.
+ */
+
+/*
+ * QTree is a partial import of Glib's GTree. The parts excluded correspond
+ * to API calls either deprecated (e.g. g_tree_traverse) or recently added
+ * (e.g. g_tree_search_node, added in 2.68); neither have callers in QEMU.
+ *
+ * The reason for this import is to allow us to control the memory allocator
+ * used by the tree implementation. Until Glib 2.75.3, GTree uses Glib's
+ * slice allocator, which causes problems when forking in user-mode;
+ * see https://gitlab.com/qemu-project/qemu/-/issues/285 and glib's
+ * "45b5a6c1e gslice: Remove slice allocator and use malloc() instead".
+ *
+ * TODO: remove QTree when QEMU's minimum Glib version is >= 2.75.3.
+ */
+
+#ifndef QEMU_QTREE_H
+#define QEMU_QTREE_H
+
+#include "qemu/osdep.h"
+
+#ifdef HAVE_GLIB_WITH_SLICE_ALLOCATOR
+
+typedef struct _QTree QTree;
+
+typedef struct _QTreeNode QTreeNode;
+
+typedef gboolean (*QTraverseNodeFunc)(QTreeNode *node,
+ gpointer user_data);
+
+/*
+ * Balanced binary trees
+ */
+QTree *q_tree_new(GCompareFunc key_compare_func);
+QTree *q_tree_new_with_data(GCompareDataFunc key_compare_func,
+ gpointer key_compare_data);
+QTree *q_tree_new_full(GCompareDataFunc key_compare_func,
+ gpointer key_compare_data,
+ GDestroyNotify key_destroy_func,
+ GDestroyNotify value_destroy_func);
+QTree *q_tree_ref(QTree *tree);
+void q_tree_unref(QTree *tree);
+void q_tree_destroy(QTree *tree);
+void q_tree_insert(QTree *tree,
+ gpointer key,
+ gpointer value);
+void q_tree_replace(QTree *tree,
+ gpointer key,
+ gpointer value);
+gboolean q_tree_remove(QTree *tree,
+ gconstpointer key);
+gboolean q_tree_steal(QTree *tree,
+ gconstpointer key);
+gpointer q_tree_lookup(QTree *tree,
+ gconstpointer key);
+gboolean q_tree_lookup_extended(QTree *tree,
+ gconstpointer lookup_key,
+ gpointer *orig_key,
+ gpointer *value);
+void q_tree_foreach(QTree *tree,
+ GTraverseFunc func,
+ gpointer user_data);
+gpointer q_tree_search(QTree *tree,
+ GCompareFunc search_func,
+ gconstpointer user_data);
+gint q_tree_height(QTree *tree);
+gint q_tree_nnodes(QTree *tree);
+
+#else /* !HAVE_GLIB_WITH_SLICE_ALLOCATOR */
+
+typedef GTree QTree;
+typedef GTreeNode QTreeNode;
+typedef GTraverseNodeFunc QTraverseNodeFunc;
+
+static inline QTree *q_tree_new(GCompareFunc key_compare_func)
+{
+ return g_tree_new(key_compare_func);
+}
+
+static inline QTree *q_tree_new_with_data(GCompareDataFunc key_compare_func,
+ gpointer key_compare_data)
+{
+ return g_tree_new_with_data(key_compare_func, key_compare_data);
+}
+
+static inline QTree *q_tree_new_full(GCompareDataFunc key_compare_func,
+ gpointer key_compare_data,
+ GDestroyNotify key_destroy_func,
+ GDestroyNotify value_destroy_func)
+{
+ return g_tree_new_full(key_compare_func, key_compare_data,
+ key_destroy_func, value_destroy_func);
+}
+
+static inline QTree *q_tree_ref(QTree *tree)
+{
+ return g_tree_ref(tree);
+}
+
+static inline void q_tree_unref(QTree *tree)
+{
+ g_tree_unref(tree);
+}
+
+static inline void q_tree_destroy(QTree *tree)
+{
+ g_tree_destroy(tree);
+}
+
+static inline void q_tree_insert(QTree *tree,
+ gpointer key,
+ gpointer value)
+{
+ g_tree_insert(tree, key, value);
+}
+
+static inline void q_tree_replace(QTree *tree,
+ gpointer key,
+ gpointer value)
+{
+ g_tree_replace(tree, key, value);
+}
+
+static inline gboolean q_tree_remove(QTree *tree,
+ gconstpointer key)
+{
+ return g_tree_remove(tree, key);
+}
+
+static inline gboolean q_tree_steal(QTree *tree,
+ gconstpointer key)
+{
+ return g_tree_steal(tree, key);
+}
+
+static inline gpointer q_tree_lookup(QTree *tree,
+ gconstpointer key)
+{
+ return g_tree_lookup(tree, key);
+}
+
+static inline gboolean q_tree_lookup_extended(QTree *tree,
+ gconstpointer lookup_key,
+ gpointer *orig_key,
+ gpointer *value)
+{
+ return g_tree_lookup_extended(tree, lookup_key, orig_key, value);
+}
+
+static inline void q_tree_foreach(QTree *tree,
+ GTraverseFunc func,
+ gpointer user_data)
+{
+ return g_tree_foreach(tree, func, user_data);
+}
+
+static inline gpointer q_tree_search(QTree *tree,
+ GCompareFunc search_func,
+ gconstpointer user_data)
+{
+ return g_tree_search(tree, search_func, user_data);
+}
+
+static inline gint q_tree_height(QTree *tree)
+{
+ return g_tree_height(tree);
+}
+
+static inline gint q_tree_nnodes(QTree *tree)
+{
+ return g_tree_nnodes(tree);
+}
+
+#endif /* HAVE_GLIB_WITH_SLICE_ALLOCATOR */
+
+#endif /* QEMU_QTREE_H */
new file mode 100644
@@ -0,0 +1,286 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+#include "qemu/osdep.h"
+#include "qemu/qtree.h"
+#include "qemu/timer.h"
+
+enum tree_op {
+ OP_LOOKUP,
+ OP_INSERT,
+ OP_REMOVE,
+ OP_REMOVE_ALL,
+ OP_TRAVERSE,
+};
+
+struct benchmark {
+ const char * const name;
+ enum tree_op op;
+ bool fill_on_init;
+};
+
+enum impl_type {
+ IMPL_GTREE,
+ IMPL_QTREE,
+};
+
+struct tree_implementation {
+ const char * const name;
+ enum impl_type type;
+};
+
+static const struct benchmark benchmarks[] = {
+ {
+ .name = "Lookup",
+ .op = OP_LOOKUP,
+ .fill_on_init = true,
+ },
+ {
+ .name = "Insert",
+ .op = OP_INSERT,
+ .fill_on_init = false,
+ },
+ {
+ .name = "Remove",
+ .op = OP_REMOVE,
+ .fill_on_init = true,
+ },
+ {
+ .name = "RemoveAll",
+ .op = OP_REMOVE_ALL,
+ .fill_on_init = true,
+ },
+ {
+ .name = "Traverse",
+ .op = OP_TRAVERSE,
+ .fill_on_init = true,
+ },
+};
+
+static const struct tree_implementation impls[] = {
+ {
+ .name = "GTree",
+ .type = IMPL_GTREE,
+ },
+ {
+ .name = "QTree",
+ .type = IMPL_QTREE,
+ },
+};
+
+static int compare_func(const void *ap, const void *bp)
+{
+ const size_t *a = ap;
+ const size_t *b = bp;
+
+ return *a - *b;
+}
+
+static void init_empty_tree_and_keys(enum impl_type impl,
+ void **ret_tree, size_t **ret_keys,
+ size_t n_elems)
+{
+ size_t *keys = g_malloc_n(n_elems, sizeof(*keys));
+ for (size_t i = 0; i < n_elems; i++) {
+ keys[i] = i;
+ }
+
+ void *tree;
+ switch (impl) {
+ case IMPL_GTREE:
+ tree = g_tree_new(compare_func);
+ break;
+ case IMPL_QTREE:
+ tree = q_tree_new(compare_func);
+ break;
+ default:
+ g_assert_not_reached();
+ }
+
+ *ret_tree = tree;
+ *ret_keys = keys;
+}
+
+static gboolean traverse_func(gpointer key, gpointer value, gpointer data)
+{
+ return FALSE;
+}
+
+static inline void remove_all(void *tree, enum impl_type impl)
+{
+ switch (impl) {
+ case IMPL_GTREE:
+ g_tree_destroy(tree);
+ break;
+ case IMPL_QTREE:
+ q_tree_destroy(tree);
+ break;
+ default:
+ g_assert_not_reached();
+ }
+}
+
+static int64_t run_benchmark(const struct benchmark *bench,
+ enum impl_type impl,
+ size_t n_elems)
+{
+ void *tree;
+ size_t *keys;
+
+ init_empty_tree_and_keys(impl, &tree, &keys, n_elems);
+ if (bench->fill_on_init) {
+ for (size_t i = 0; i < n_elems; i++) {
+ switch (impl) {
+ case IMPL_GTREE:
+ g_tree_insert(tree, &keys[i], &keys[i]);
+ break;
+ case IMPL_QTREE:
+ q_tree_insert(tree, &keys[i], &keys[i]);
+ break;
+ default:
+ g_assert_not_reached();
+ }
+ }
+ }
+
+ int64_t start_ns = get_clock();
+ switch (bench->op) {
+ case OP_LOOKUP:
+ for (size_t i = 0; i < n_elems; i++) {
+ void *value;
+ switch (impl) {
+ case IMPL_GTREE:
+ value = g_tree_lookup(tree, &keys[i]);
+ break;
+ case IMPL_QTREE:
+ value = q_tree_lookup(tree, &keys[i]);
+ break;
+ default:
+ g_assert_not_reached();
+ }
+ (void)value;
+ }
+ break;
+ case OP_INSERT:
+ for (size_t i = 0; i < n_elems; i++) {
+ switch (impl) {
+ case IMPL_GTREE:
+ g_tree_insert(tree, &keys[i], &keys[i]);
+ break;
+ case IMPL_QTREE:
+ q_tree_insert(tree, &keys[i], &keys[i]);
+ break;
+ default:
+ g_assert_not_reached();
+ }
+ }
+ break;
+ case OP_REMOVE:
+ for (size_t i = 0; i < n_elems; i++) {
+ switch (impl) {
+ case IMPL_GTREE:
+ g_tree_remove(tree, &keys[i]);
+ break;
+ case IMPL_QTREE:
+ q_tree_remove(tree, &keys[i]);
+ break;
+ default:
+ g_assert_not_reached();
+ }
+ }
+ break;
+ case OP_REMOVE_ALL:
+ remove_all(tree, impl);
+ break;
+ case OP_TRAVERSE:
+ switch (impl) {
+ case IMPL_GTREE:
+ g_tree_foreach(tree, traverse_func, NULL);
+ break;
+ case IMPL_QTREE:
+ q_tree_foreach(tree, traverse_func, NULL);
+ break;
+ default:
+ g_assert_not_reached();
+ }
+ break;
+ default:
+ g_assert_not_reached();
+ }
+ int64_t ns = get_clock() - start_ns;
+
+ if (bench->op != OP_REMOVE_ALL) {
+ remove_all(tree, impl);
+ }
+ g_free(keys);
+
+ return ns;
+}
+
+int main(int argc, char *argv[])
+{
+ size_t sizes[] = {
+ 32,
+ 1024,
+ 1024 * 4,
+ 1024 * 128,
+ 1024 * 1024,
+ };
+
+ double res[ARRAY_SIZE(benchmarks)][ARRAY_SIZE(impls)][ARRAY_SIZE(sizes)];
+ for (int i = 0; i < ARRAY_SIZE(sizes); i++) {
+ size_t size = sizes[i];
+ for (int j = 0; j < ARRAY_SIZE(impls); j++) {
+ const struct tree_implementation *impl = &impls[j];
+ for (int k = 0; k < ARRAY_SIZE(benchmarks); k++) {
+ const struct benchmark *bench = &benchmarks[k];
+
+ /* warm-up run */
+ run_benchmark(bench, impl->type, size);
+
+ int64_t total_ns = 0;
+ int64_t n_runs = 0;
+ while (total_ns < 2e8 || n_runs < 5) {
+ total_ns += run_benchmark(bench, impl->type, size);
+ n_runs++;
+ }
+ double ns_per_run = (double)total_ns / n_runs;
+
+ /* Throughput, in Mops/s */
+ res[k][j][i] = size / ns_per_run * 1e3;
+ }
+ }
+ }
+
+ printf("# Results' breakdown: Tree, Op and #Elements. Units: Mops/s\n");
+ printf("%5s %10s ", "Tree", "Op");
+ for (int i = 0; i < ARRAY_SIZE(sizes); i++) {
+ printf("%7zu ", sizes[i]);
+ }
+ printf("\n");
+ char separator[97];
+ for (int i = 0; i < ARRAY_SIZE(separator) - 1; i++) {
+ separator[i] = '-';
+ }
+ separator[ARRAY_SIZE(separator) - 1] = '\0';
+ printf("%s\n", separator);
+ for (int i = 0; i < ARRAY_SIZE(benchmarks); i++) {
+ for (int j = 0; j < ARRAY_SIZE(impls); j++) {
+ printf("%5s %10s ", impls[j].name, benchmarks[i].name);
+ for (int k = 0; k < ARRAY_SIZE(sizes); k++) {
+ printf("%7.2f ", res[i][j][k]);
+ if (j == 0) {
+ printf(" ");
+ } else {
+ if (res[i][0][k] != 0) {
+ double speedup = res[i][j][k] / res[i][0][k];
+ printf("(%4.2fx) ", speedup);
+ } else {
+ printf("( ) ");
+ }
+ }
+ }
+ printf("\n");
+ }
+ }
+ printf("%s\n", separator);
+ return 0;
+}
new file mode 100644
@@ -0,0 +1,333 @@
+/*
+ * SPDX-License-Identifier: LGPL-2.1-or-later
+ *
+ * Tests for QTree.
+ * Original source: glib
+ * https://gitlab.gnome.org/GNOME/glib/-/blob/main/glib/tests/tree.c
+ * LGPL license.
+ * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
+ */
+
+#include "qemu/osdep.h"
+#include "qemu/qtree.h"
+
+static gint my_compare(gconstpointer a, gconstpointer b)
+{
+ const char *cha = a;
+ const char *chb = b;
+
+ return *cha - *chb;
+}
+
+static gint my_compare_with_data(gconstpointer a,
+ gconstpointer b,
+ gpointer user_data)
+{
+ const char *cha = a;
+ const char *chb = b;
+
+ /* just check that we got the right data */
+ g_assert(GPOINTER_TO_INT(user_data) == 123);
+
+ return *cha - *chb;
+}
+
+static gint my_search(gconstpointer a, gconstpointer b)
+{
+ return my_compare(b, a);
+}
+
+static gpointer destroyed_key;
+static gpointer destroyed_value;
+static guint destroyed_key_count;
+static guint destroyed_value_count;
+
+static void my_key_destroy(gpointer key)
+{
+ destroyed_key = key;
+ destroyed_key_count++;
+}
+
+static void my_value_destroy(gpointer value)
+{
+ destroyed_value = value;
+ destroyed_value_count++;
+}
+
+static gint my_traverse(gpointer key, gpointer value, gpointer data)
+{
+ char *ch = key;
+
+ g_assert((*ch) > 0);
+
+ if (*ch == 'd') {
+ return TRUE;
+ }
+
+ return FALSE;
+}
+
+char chars[] =
+ "0123456789"
+ "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+ "abcdefghijklmnopqrstuvwxyz";
+
+char chars2[] =
+ "0123456789"
+ "abcdefghijklmnopqrstuvwxyz";
+
+static gint check_order(gpointer key, gpointer value, gpointer data)
+{
+ char **p = data;
+ char *ch = key;
+
+ g_assert(**p == *ch);
+
+ (*p)++;
+
+ return FALSE;
+}
+
+static void test_tree_search(void)
+{
+ gint i;
+ QTree *tree;
+ gboolean removed;
+ gchar c;
+ gchar *p, *d;
+
+ tree = q_tree_new_with_data(my_compare_with_data, GINT_TO_POINTER(123));
+
+ for (i = 0; chars[i]; i++) {
+ q_tree_insert(tree, &chars[i], &chars[i]);
+ }
+
+ q_tree_foreach(tree, my_traverse, NULL);
+
+ g_assert(q_tree_nnodes(tree) == strlen(chars));
+ g_assert(q_tree_height(tree) == 6);
+
+ p = chars;
+ q_tree_foreach(tree, check_order, &p);
+
+ for (i = 0; i < 26; i++) {
+ removed = q_tree_remove(tree, &chars[i + 10]);
+ g_assert(removed);
+ }
+
+ c = '\0';
+ removed = q_tree_remove(tree, &c);
+ g_assert(!removed);
+
+ q_tree_foreach(tree, my_traverse, NULL);
+
+ g_assert(q_tree_nnodes(tree) == strlen(chars2));
+ g_assert(q_tree_height(tree) == 6);
+
+ p = chars2;
+ q_tree_foreach(tree, check_order, &p);
+
+ for (i = 25; i >= 0; i--) {
+ q_tree_insert(tree, &chars[i + 10], &chars[i + 10]);
+ }
+
+ p = chars;
+ q_tree_foreach(tree, check_order, &p);
+
+ c = '0';
+ p = q_tree_lookup(tree, &c);
+ g_assert(p && *p == c);
+ g_assert(q_tree_lookup_extended(tree, &c, (gpointer *)&d, (gpointer *)&p));
+ g_assert(c == *d && c == *p);
+
+ c = 'A';
+ p = q_tree_lookup(tree, &c);
+ g_assert(p && *p == c);
+
+ c = 'a';
+ p = q_tree_lookup(tree, &c);
+ g_assert(p && *p == c);
+
+ c = 'z';
+ p = q_tree_lookup(tree, &c);
+ g_assert(p && *p == c);
+
+ c = '!';
+ p = q_tree_lookup(tree, &c);
+ g_assert(p == NULL);
+
+ c = '=';
+ p = q_tree_lookup(tree, &c);
+ g_assert(p == NULL);
+
+ c = '|';
+ p = q_tree_lookup(tree, &c);
+ g_assert(p == NULL);
+
+ c = '0';
+ p = q_tree_search(tree, my_search, &c);
+ g_assert(p && *p == c);
+
+ c = 'A';
+ p = q_tree_search(tree, my_search, &c);
+ g_assert(p && *p == c);
+
+ c = 'a';
+ p = q_tree_search(tree, my_search, &c);
+ g_assert(p && *p == c);
+
+ c = 'z';
+ p = q_tree_search(tree, my_search, &c);
+ g_assert(p && *p == c);
+
+ c = '!';
+ p = q_tree_search(tree, my_search, &c);
+ g_assert(p == NULL);
+
+ c = '=';
+ p = q_tree_search(tree, my_search, &c);
+ g_assert(p == NULL);
+
+ c = '|';
+ p = q_tree_search(tree, my_search, &c);
+ g_assert(p == NULL);
+
+ q_tree_destroy(tree);
+}
+
+static void test_tree_remove(void)
+{
+ QTree *tree;
+ char c, d;
+ gint i;
+ gboolean removed;
+
+ tree = q_tree_new_full((GCompareDataFunc)my_compare, NULL,
+ my_key_destroy,
+ my_value_destroy);
+
+ for (i = 0; chars[i]; i++) {
+ q_tree_insert(tree, &chars[i], &chars[i]);
+ }
+
+ c = '0';
+ q_tree_insert(tree, &c, &c);
+ g_assert(destroyed_key == &c);
+ g_assert(destroyed_value == &chars[0]);
+ destroyed_key = NULL;
+ destroyed_value = NULL;
+
+ d = '1';
+ q_tree_replace(tree, &d, &d);
+ g_assert(destroyed_key == &chars[1]);
+ g_assert(destroyed_value == &chars[1]);
+ destroyed_key = NULL;
+ destroyed_value = NULL;
+
+ c = '2';
+ removed = q_tree_remove(tree, &c);
+ g_assert(removed);
+ g_assert(destroyed_key == &chars[2]);
+ g_assert(destroyed_value == &chars[2]);
+ destroyed_key = NULL;
+ destroyed_value = NULL;
+
+ c = '3';
+ removed = q_tree_steal(tree, &c);
+ g_assert(removed);
+ g_assert(destroyed_key == NULL);
+ g_assert(destroyed_value == NULL);
+
+ const gchar *remove = "omkjigfedba";
+ for (i = 0; remove[i]; i++) {
+ removed = q_tree_remove(tree, &remove[i]);
+ g_assert(removed);
+ }
+
+ q_tree_destroy(tree);
+}
+
+static void test_tree_destroy(void)
+{
+ QTree *tree;
+ gint i;
+
+ tree = q_tree_new(my_compare);
+
+ for (i = 0; chars[i]; i++) {
+ q_tree_insert(tree, &chars[i], &chars[i]);
+ }
+
+ g_assert(q_tree_nnodes(tree) == strlen(chars));
+
+ g_test_message("nnodes: %d", q_tree_nnodes(tree));
+ q_tree_ref(tree);
+ q_tree_destroy(tree);
+
+ g_test_message("nnodes: %d", q_tree_nnodes(tree));
+ g_assert(q_tree_nnodes(tree) == 0);
+
+ q_tree_unref(tree);
+}
+
+static void test_tree_insert(void)
+{
+ QTree *tree;
+ gchar *p;
+ gint i;
+ gchar *scrambled;
+
+ tree = q_tree_new(my_compare);
+
+ for (i = 0; chars[i]; i++) {
+ q_tree_insert(tree, &chars[i], &chars[i]);
+ }
+ p = chars;
+ q_tree_foreach(tree, check_order, &p);
+
+ q_tree_unref(tree);
+ tree = q_tree_new(my_compare);
+
+ for (i = strlen(chars) - 1; i >= 0; i--) {
+ q_tree_insert(tree, &chars[i], &chars[i]);
+ }
+ p = chars;
+ q_tree_foreach(tree, check_order, &p);
+
+ q_tree_unref(tree);
+ tree = q_tree_new(my_compare);
+
+ scrambled = g_strdup(chars);
+
+ for (i = 0; i < 30; i++) {
+ gchar tmp;
+ gint a, b;
+
+ a = g_random_int_range(0, strlen(scrambled));
+ b = g_random_int_range(0, strlen(scrambled));
+ tmp = scrambled[a];
+ scrambled[a] = scrambled[b];
+ scrambled[b] = tmp;
+ }
+
+ for (i = 0; scrambled[i]; i++) {
+ q_tree_insert(tree, &scrambled[i], &scrambled[i]);
+ }
+ p = chars;
+ q_tree_foreach(tree, check_order, &p);
+
+ g_free(scrambled);
+ q_tree_unref(tree);
+}
+
+int main(int argc, char *argv[])
+{
+ g_test_init(&argc, &argv, NULL);
+
+ g_test_add_func("/qtree/search", test_tree_search);
+ g_test_add_func("/qtree/remove", test_tree_remove);
+ g_test_add_func("/qtree/destroy", test_tree_destroy);
+ g_test_add_func("/qtree/insert", test_tree_insert);
+
+ return g_test_run();
+}
new file mode 100644
@@ -0,0 +1,1390 @@
+/*
+ * GLIB - Library of useful routines for C programming
+ * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
+ *
+ * SPDX-License-Identifier: LGPL-2.1-or-later
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+/*
+ * Modified by the GLib Team and others 1997-2000. See the AUTHORS
+ * file for a list of people on the GLib Team. See the ChangeLog
+ * files for a list of changes. These files are distributed with
+ * GLib at ftp://ftp.gtk.org/pub/gtk/.
+ */
+
+/*
+ * MT safe
+ */
+
+#include "qemu/osdep.h"
+#include "qemu/qtree.h"
+
+/**
+ * SECTION:trees-binary
+ * @title: Balanced Binary Trees
+ * @short_description: a sorted collection of key/value pairs optimized
+ * for searching and traversing in order
+ *
+ * The #QTree structure and its associated functions provide a sorted
+ * collection of key/value pairs optimized for searching and traversing
+ * in order. This means that most of the operations (access, search,
+ * insertion, deletion, ...) on #QTree are O(log(n)) in average and O(n)
+ * in worst case for time complexity. But, note that maintaining a
+ * balanced sorted #QTree of n elements is done in time O(n log(n)).
+ *
+ * To create a new #QTree use q_tree_new().
+ *
+ * To insert a key/value pair into a #QTree use q_tree_insert()
+ * (O(n log(n))).
+ *
+ * To remove a key/value pair use q_tree_remove() (O(n log(n))).
+ *
+ * To look up the value corresponding to a given key, use
+ * q_tree_lookup() and q_tree_lookup_extended().
+ *
+ * To find out the number of nodes in a #QTree, use q_tree_nnodes(). To
+ * get the height of a #QTree, use q_tree_height().
+ *
+ * To traverse a #QTree, calling a function for each node visited in
+ * the traversal, use q_tree_foreach().
+ *
+ * To destroy a #QTree, use q_tree_destroy().
+ **/
+
+#define MAX_GTREE_HEIGHT 40
+
+/**
+ * QTree:
+ *
+ * The QTree struct is an opaque data structure representing a
+ * [balanced binary tree][glib-Balanced-Binary-Trees]. It should be
+ * accessed only by using the following functions.
+ */
+struct _QTree {
+ QTreeNode *root;
+ GCompareDataFunc key_compare;
+ GDestroyNotify key_destroy_func;
+ GDestroyNotify value_destroy_func;
+ gpointer key_compare_data;
+ guint nnodes;
+ gint ref_count;
+};
+
+struct _QTreeNode {
+ gpointer key; /* key for this node */
+ gpointer value; /* value stored at this node */
+ QTreeNode *left; /* left subtree */
+ QTreeNode *right; /* right subtree */
+ gint8 balance; /* height (right) - height (left) */
+ guint8 left_child;
+ guint8 right_child;
+};
+
+
+static QTreeNode *q_tree_node_new(gpointer key,
+ gpointer value);
+static QTreeNode *q_tree_insert_internal(QTree *tree,
+ gpointer key,
+ gpointer value,
+ gboolean replace);
+static gboolean q_tree_remove_internal(QTree *tree,
+ gconstpointer key,
+ gboolean steal);
+static QTreeNode *q_tree_node_balance(QTreeNode *node);
+static QTreeNode *q_tree_find_node(QTree *tree,
+ gconstpointer key);
+static QTreeNode *q_tree_node_search(QTreeNode *node,
+ GCompareFunc search_func,
+ gconstpointer data);
+static QTreeNode *q_tree_node_rotate_left(QTreeNode *node);
+static QTreeNode *q_tree_node_rotate_right(QTreeNode *node);
+#ifdef Q_TREE_DEBUG
+static void q_tree_node_check(QTreeNode *node);
+#endif
+
+static QTreeNode*
+q_tree_node_new(gpointer key,
+ gpointer value)
+{
+ QTreeNode *node = g_new(QTreeNode, 1);
+
+ node->balance = 0;
+ node->left = NULL;
+ node->right = NULL;
+ node->left_child = FALSE;
+ node->right_child = FALSE;
+ node->key = key;
+ node->value = value;
+
+ return node;
+}
+
+/**
+ * q_tree_new:
+ * @key_compare_func: the function used to order the nodes in the #QTree.
+ * It should return values similar to the standard strcmp() function -
+ * 0 if the two arguments are equal, a negative value if the first argument
+ * comes before the second, or a positive value if the first argument comes
+ * after the second.
+ *
+ * Creates a new #QTree.
+ *
+ * Returns: a newly allocated #QTree
+ */
+QTree *
+q_tree_new(GCompareFunc key_compare_func)
+{
+ g_return_val_if_fail(key_compare_func != NULL, NULL);
+
+ return q_tree_new_full((GCompareDataFunc) key_compare_func, NULL,
+ NULL, NULL);
+}
+
+/**
+ * q_tree_new_with_data:
+ * @key_compare_func: qsort()-style comparison function
+ * @key_compare_data: data to pass to comparison function
+ *
+ * Creates a new #QTree with a comparison function that accepts user data.
+ * See q_tree_new() for more details.
+ *
+ * Returns: a newly allocated #QTree
+ */
+QTree *
+q_tree_new_with_data(GCompareDataFunc key_compare_func,
+ gpointer key_compare_data)
+{
+ g_return_val_if_fail(key_compare_func != NULL, NULL);
+
+ return q_tree_new_full(key_compare_func, key_compare_data,
+ NULL, NULL);
+}
+
+/**
+ * q_tree_new_full:
+ * @key_compare_func: qsort()-style comparison function
+ * @key_compare_data: data to pass to comparison function
+ * @key_destroy_func: a function to free the memory allocated for the key
+ * used when removing the entry from the #QTree or %NULL if you don't
+ * want to supply such a function
+ * @value_destroy_func: a function to free the memory allocated for the
+ * value used when removing the entry from the #QTree or %NULL if you
+ * don't want to supply such a function
+ *
+ * Creates a new #QTree like q_tree_new() and allows to specify functions
+ * to free the memory allocated for the key and value that get called when
+ * removing the entry from the #QTree.
+ *
+ * Returns: a newly allocated #QTree
+ */
+QTree *
+q_tree_new_full(GCompareDataFunc key_compare_func,
+ gpointer key_compare_data,
+ GDestroyNotify key_destroy_func,
+ GDestroyNotify value_destroy_func)
+{
+ QTree *tree;
+
+ g_return_val_if_fail(key_compare_func != NULL, NULL);
+
+ tree = g_new(QTree, 1);
+ tree->root = NULL;
+ tree->key_compare = key_compare_func;
+ tree->key_destroy_func = key_destroy_func;
+ tree->value_destroy_func = value_destroy_func;
+ tree->key_compare_data = key_compare_data;
+ tree->nnodes = 0;
+ tree->ref_count = 1;
+
+ return tree;
+}
+
+/**
+ * q_tree_node_first:
+ * @tree: a #QTree
+ *
+ * Returns the first in-order node of the tree, or %NULL
+ * for an empty tree.
+ *
+ * Returns: (nullable) (transfer none): the first node in the tree
+ *
+ * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
+ */
+static QTreeNode *
+q_tree_node_first(QTree *tree)
+{
+ QTreeNode *tmp;
+
+ g_return_val_if_fail(tree != NULL, NULL);
+
+ if (!tree->root) {
+ return NULL;
+ }
+
+ tmp = tree->root;
+
+ while (tmp->left_child) {
+ tmp = tmp->left;
+ }
+
+ return tmp;
+}
+
+/**
+ * q_tree_node_previous
+ * @node: a #QTree node
+ *
+ * Returns the previous in-order node of the tree, or %NULL
+ * if the passed node was already the first one.
+ *
+ * Returns: (nullable) (transfer none): the previous node in the tree
+ *
+ * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
+ */
+static QTreeNode *
+q_tree_node_previous(QTreeNode *node)
+{
+ QTreeNode *tmp;
+
+ g_return_val_if_fail(node != NULL, NULL);
+
+ tmp = node->left;
+
+ if (node->left_child) {
+ while (tmp->right_child) {
+ tmp = tmp->right;
+ }
+ }
+
+ return tmp;
+}
+
+/**
+ * q_tree_node_next
+ * @node: a #QTree node
+ *
+ * Returns the next in-order node of the tree, or %NULL
+ * if the passed node was already the last one.
+ *
+ * Returns: (nullable) (transfer none): the next node in the tree
+ *
+ * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
+ */
+static QTreeNode *
+q_tree_node_next(QTreeNode *node)
+{
+ QTreeNode *tmp;
+
+ g_return_val_if_fail(node != NULL, NULL);
+
+ tmp = node->right;
+
+ if (node->right_child) {
+ while (tmp->left_child) {
+ tmp = tmp->left;
+ }
+ }
+
+ return tmp;
+}
+
+/**
+ * q_tree_remove_all:
+ * @tree: a #QTree
+ *
+ * Removes all nodes from a #QTree and destroys their keys and values,
+ * then resets the #QTree’s root to %NULL.
+ *
+ * Since: 2.70 in GLib. Internal in Qtree, i.e. not in the public API.
+ */
+static void
+q_tree_remove_all(QTree *tree)
+{
+ QTreeNode *node;
+ QTreeNode *next;
+
+ g_return_if_fail(tree != NULL);
+
+ node = q_tree_node_first(tree);
+
+ while (node) {
+ next = q_tree_node_next(node);
+
+ if (tree->key_destroy_func) {
+ tree->key_destroy_func(node->key);
+ }
+ if (tree->value_destroy_func) {
+ tree->value_destroy_func(node->value);
+ }
+ g_free(node);
+
+#ifdef Q_TREE_DEBUG
+ g_assert(tree->nnodes > 0);
+ tree->nnodes--;
+#endif
+
+ node = next;
+ }
+
+#ifdef Q_TREE_DEBUG
+ g_assert(tree->nnodes == 0);
+#endif
+
+ tree->root = NULL;
+#ifndef Q_TREE_DEBUG
+ tree->nnodes = 0;
+#endif
+}
+
+/**
+ * q_tree_ref:
+ * @tree: a #QTree
+ *
+ * Increments the reference count of @tree by one.
+ *
+ * It is safe to call this function from any thread.
+ *
+ * Returns: the passed in #QTree
+ *
+ * Since: 2.22
+ */
+QTree *
+q_tree_ref(QTree *tree)
+{
+ g_return_val_if_fail(tree != NULL, NULL);
+
+ g_atomic_int_inc(&tree->ref_count);
+
+ return tree;
+}
+
+/**
+ * q_tree_unref:
+ * @tree: a #QTree
+ *
+ * Decrements the reference count of @tree by one.
+ * If the reference count drops to 0, all keys and values will
+ * be destroyed (if destroy functions were specified) and all
+ * memory allocated by @tree will be released.
+ *
+ * It is safe to call this function from any thread.
+ *
+ * Since: 2.22
+ */
+void
+q_tree_unref(QTree *tree)
+{
+ g_return_if_fail(tree != NULL);
+
+ if (g_atomic_int_dec_and_test(&tree->ref_count)) {
+ q_tree_remove_all(tree);
+ g_free(tree);
+ }
+}
+
+/**
+ * q_tree_destroy:
+ * @tree: a #QTree
+ *
+ * Removes all keys and values from the #QTree and decreases its
+ * reference count by one. If keys and/or values are dynamically
+ * allocated, you should either free them first or create the #QTree
+ * using q_tree_new_full(). In the latter case the destroy functions
+ * you supplied will be called on all keys and values before destroying
+ * the #QTree.
+ */
+void
+q_tree_destroy(QTree *tree)
+{
+ g_return_if_fail(tree != NULL);
+
+ q_tree_remove_all(tree);
+ q_tree_unref(tree);
+}
+
+/**
+ * q_tree_insert_node:
+ * @tree: a #QTree
+ * @key: the key to insert
+ * @value: the value corresponding to the key
+ *
+ * Inserts a key/value pair into a #QTree.
+ *
+ * If the given key already exists in the #QTree its corresponding value
+ * is set to the new value. If you supplied a @value_destroy_func when
+ * creating the #QTree, the old value is freed using that function. If
+ * you supplied a @key_destroy_func when creating the #QTree, the passed
+ * key is freed using that function.
+ *
+ * The tree is automatically 'balanced' as new key/value pairs are added,
+ * so that the distance from the root to every leaf is as small as possible.
+ * The cost of maintaining a balanced tree while inserting new key/value
+ * result in a O(n log(n)) operation where most of the other operations
+ * are O(log(n)).
+ *
+ * Returns: (transfer none): the inserted (or set) node.
+ *
+ * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
+ */
+static QTreeNode *
+q_tree_insert_node(QTree *tree,
+ gpointer key,
+ gpointer value)
+{
+ QTreeNode *node;
+
+ g_return_val_if_fail(tree != NULL, NULL);
+
+ node = q_tree_insert_internal(tree, key, value, FALSE);
+
+#ifdef Q_TREE_DEBUG
+ q_tree_node_check(tree->root);
+#endif
+
+ return node;
+}
+
+/**
+ * q_tree_insert:
+ * @tree: a #QTree
+ * @key: the key to insert
+ * @value: the value corresponding to the key
+ *
+ * Inserts a key/value pair into a #QTree.
+ *
+ * Inserts a new key and value into a #QTree as q_tree_insert_node() does,
+ * only this function does not return the inserted or set node.
+ */
+void
+q_tree_insert(QTree *tree,
+ gpointer key,
+ gpointer value)
+{
+ q_tree_insert_node(tree, key, value);
+}
+
+/**
+ * q_tree_replace_node:
+ * @tree: a #QTree
+ * @key: the key to insert
+ * @value: the value corresponding to the key
+ *
+ * Inserts a new key and value into a #QTree similar to q_tree_insert_node().
+ * The difference is that if the key already exists in the #QTree, it gets
+ * replaced by the new key. If you supplied a @value_destroy_func when
+ * creating the #QTree, the old value is freed using that function. If you
+ * supplied a @key_destroy_func when creating the #QTree, the old key is
+ * freed using that function.
+ *
+ * The tree is automatically 'balanced' as new key/value pairs are added,
+ * so that the distance from the root to every leaf is as small as possible.
+ *
+ * Returns: (transfer none): the inserted (or set) node.
+ *
+ * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
+ */
+static QTreeNode *
+q_tree_replace_node(QTree *tree,
+ gpointer key,
+ gpointer value)
+{
+ QTreeNode *node;
+
+ g_return_val_if_fail(tree != NULL, NULL);
+
+ node = q_tree_insert_internal(tree, key, value, TRUE);
+
+#ifdef Q_TREE_DEBUG
+ q_tree_node_check(tree->root);
+#endif
+
+ return node;
+}
+
+/**
+ * q_tree_replace:
+ * @tree: a #QTree
+ * @key: the key to insert
+ * @value: the value corresponding to the key
+ *
+ * Inserts a new key and value into a #QTree as q_tree_replace_node() does,
+ * only this function does not return the inserted or set node.
+ */
+void
+q_tree_replace(QTree *tree,
+ gpointer key,
+ gpointer value)
+{
+ q_tree_replace_node(tree, key, value);
+}
+
+/* internal insert routine */
+static QTreeNode *
+q_tree_insert_internal(QTree *tree,
+ gpointer key,
+ gpointer value,
+ gboolean replace)
+{
+ QTreeNode *node, *retnode;
+ QTreeNode *path[MAX_GTREE_HEIGHT];
+ int idx;
+
+ g_return_val_if_fail(tree != NULL, NULL);
+
+ if (!tree->root) {
+ tree->root = q_tree_node_new(key, value);
+ tree->nnodes++;
+ return tree->root;
+ }
+
+ idx = 0;
+ path[idx++] = NULL;
+ node = tree->root;
+
+ while (1) {
+ int cmp = tree->key_compare(key, node->key, tree->key_compare_data);
+
+ if (cmp == 0) {
+ if (tree->value_destroy_func) {
+ tree->value_destroy_func(node->value);
+ }
+
+ node->value = value;
+
+ if (replace) {
+ if (tree->key_destroy_func) {
+ tree->key_destroy_func(node->key);
+ }
+
+ node->key = key;
+ } else {
+ /* free the passed key */
+ if (tree->key_destroy_func) {
+ tree->key_destroy_func(key);
+ }
+ }
+
+ return node;
+ } else if (cmp < 0) {
+ if (node->left_child) {
+ path[idx++] = node;
+ node = node->left;
+ } else {
+ QTreeNode *child = q_tree_node_new(key, value);
+
+ child->left = node->left;
+ child->right = node;
+ node->left = child;
+ node->left_child = TRUE;
+ node->balance -= 1;
+
+ tree->nnodes++;
+
+ retnode = child;
+ break;
+ }
+ } else {
+ if (node->right_child) {
+ path[idx++] = node;
+ node = node->right;
+ } else {
+ QTreeNode *child = q_tree_node_new(key, value);
+
+ child->right = node->right;
+ child->left = node;
+ node->right = child;
+ node->right_child = TRUE;
+ node->balance += 1;
+
+ tree->nnodes++;
+
+ retnode = child;
+ break;
+ }
+ }
+ }
+
+ /*
+ * Restore balance. This is the goodness of a non-recursive
+ * implementation, when we are done with balancing we 'break'
+ * the loop and we are done.
+ */
+ while (1) {
+ QTreeNode *bparent = path[--idx];
+ gboolean left_node = (bparent && node == bparent->left);
+ g_assert(!bparent || bparent->left == node || bparent->right == node);
+
+ if (node->balance < -1 || node->balance > 1) {
+ node = q_tree_node_balance(node);
+ if (bparent == NULL) {
+ tree->root = node;
+ } else if (left_node) {
+ bparent->left = node;
+ } else {
+ bparent->right = node;
+ }
+ }
+
+ if (node->balance == 0 || bparent == NULL) {
+ break;
+ }
+
+ if (left_node) {
+ bparent->balance -= 1;
+ } else {
+ bparent->balance += 1;
+ }
+
+ node = bparent;
+ }
+
+ return retnode;
+}
+
+/**
+ * q_tree_remove:
+ * @tree: a #QTree
+ * @key: the key to remove
+ *
+ * Removes a key/value pair from a #QTree.
+ *
+ * If the #QTree was created using q_tree_new_full(), the key and value
+ * are freed using the supplied destroy functions, otherwise you have to
+ * make sure that any dynamically allocated values are freed yourself.
+ * If the key does not exist in the #QTree, the function does nothing.
+ *
+ * The cost of maintaining a balanced tree while removing a key/value
+ * result in a O(n log(n)) operation where most of the other operations
+ * are O(log(n)).
+ *
+ * Returns: %TRUE if the key was found (prior to 2.8, this function
+ * returned nothing)
+ */
+gboolean
+q_tree_remove(QTree *tree,
+ gconstpointer key)
+{
+ gboolean removed;
+
+ g_return_val_if_fail(tree != NULL, FALSE);
+
+ removed = q_tree_remove_internal(tree, key, FALSE);
+
+#ifdef Q_TREE_DEBUG
+ q_tree_node_check(tree->root);
+#endif
+
+ return removed;
+}
+
+/**
+ * q_tree_steal:
+ * @tree: a #QTree
+ * @key: the key to remove
+ *
+ * Removes a key and its associated value from a #QTree without calling
+ * the key and value destroy functions.
+ *
+ * If the key does not exist in the #QTree, the function does nothing.
+ *
+ * Returns: %TRUE if the key was found (prior to 2.8, this function
+ * returned nothing)
+ */
+gboolean
+q_tree_steal(QTree *tree,
+ gconstpointer key)
+{
+ gboolean removed;
+
+ g_return_val_if_fail(tree != NULL, FALSE);
+
+ removed = q_tree_remove_internal(tree, key, TRUE);
+
+#ifdef Q_TREE_DEBUG
+ q_tree_node_check(tree->root);
+#endif
+
+ return removed;
+}
+
+/* internal remove routine */
+static gboolean
+q_tree_remove_internal(QTree *tree,
+ gconstpointer key,
+ gboolean steal)
+{
+ QTreeNode *node, *parent, *balance;
+ QTreeNode *path[MAX_GTREE_HEIGHT];
+ int idx;
+ gboolean left_node;
+
+ g_return_val_if_fail(tree != NULL, FALSE);
+
+ if (!tree->root) {
+ return FALSE;
+ }
+
+ idx = 0;
+ path[idx++] = NULL;
+ node = tree->root;
+
+ while (1) {
+ int cmp = tree->key_compare(key, node->key, tree->key_compare_data);
+
+ if (cmp == 0) {
+ break;
+ } else if (cmp < 0) {
+ if (!node->left_child) {
+ return FALSE;
+ }
+
+ path[idx++] = node;
+ node = node->left;
+ } else {
+ if (!node->right_child) {
+ return FALSE;
+ }
+
+ path[idx++] = node;
+ node = node->right;
+ }
+ }
+
+ /*
+ * The following code is almost equal to q_tree_remove_node,
+ * except that we do not have to call q_tree_node_parent.
+ */
+ balance = parent = path[--idx];
+ g_assert(!parent || parent->left == node || parent->right == node);
+ left_node = (parent && node == parent->left);
+
+ if (!node->left_child) {
+ if (!node->right_child) {
+ if (!parent) {
+ tree->root = NULL;
+ } else if (left_node) {
+ parent->left_child = FALSE;
+ parent->left = node->left;
+ parent->balance += 1;
+ } else {
+ parent->right_child = FALSE;
+ parent->right = node->right;
+ parent->balance -= 1;
+ }
+ } else {
+ /* node has a right child */
+ QTreeNode *tmp = q_tree_node_next(node);
+ tmp->left = node->left;
+
+ if (!parent) {
+ tree->root = node->right;
+ } else if (left_node) {
+ parent->left = node->right;
+ parent->balance += 1;
+ } else {
+ parent->right = node->right;
+ parent->balance -= 1;
+ }
+ }
+ } else {
+ /* node has a left child */
+ if (!node->right_child) {
+ QTreeNode *tmp = q_tree_node_previous(node);
+ tmp->right = node->right;
+
+ if (parent == NULL) {
+ tree->root = node->left;
+ } else if (left_node) {
+ parent->left = node->left;
+ parent->balance += 1;
+ } else {
+ parent->right = node->left;
+ parent->balance -= 1;
+ }
+ } else {
+ /* node has a both children (pant, pant!) */
+ QTreeNode *prev = node->left;
+ QTreeNode *next = node->right;
+ QTreeNode *nextp = node;
+ int old_idx = idx + 1;
+ idx++;
+
+ /* path[idx] == parent */
+ /* find the immediately next node (and its parent) */
+ while (next->left_child) {
+ path[++idx] = nextp = next;
+ next = next->left;
+ }
+
+ path[old_idx] = next;
+ balance = path[idx];
+
+ /* remove 'next' from the tree */
+ if (nextp != node) {
+ if (next->right_child) {
+ nextp->left = next->right;
+ } else {
+ nextp->left_child = FALSE;
+ }
+ nextp->balance += 1;
+
+ next->right_child = TRUE;
+ next->right = node->right;
+ } else {
+ node->balance -= 1;
+ }
+
+ /* set the prev to point to the right place */
+ while (prev->right_child) {
+ prev = prev->right;
+ }
+ prev->right = next;
+
+ /* prepare 'next' to replace 'node' */
+ next->left_child = TRUE;
+ next->left = node->left;
+ next->balance = node->balance;
+
+ if (!parent) {
+ tree->root = next;
+ } else if (left_node) {
+ parent->left = next;
+ } else {
+ parent->right = next;
+ }
+ }
+ }
+
+ /* restore balance */
+ if (balance) {
+ while (1) {
+ QTreeNode *bparent = path[--idx];
+ g_assert(!bparent ||
+ bparent->left == balance ||
+ bparent->right == balance);
+ left_node = (bparent && balance == bparent->left);
+
+ if (balance->balance < -1 || balance->balance > 1) {
+ balance = q_tree_node_balance(balance);
+ if (!bparent) {
+ tree->root = balance;
+ } else if (left_node) {
+ bparent->left = balance;
+ } else {
+ bparent->right = balance;
+ }
+ }
+
+ if (balance->balance != 0 || !bparent) {
+ break;
+ }
+
+ if (left_node) {
+ bparent->balance += 1;
+ } else {
+ bparent->balance -= 1;
+ }
+
+ balance = bparent;
+ }
+ }
+
+ if (!steal) {
+ if (tree->key_destroy_func) {
+ tree->key_destroy_func(node->key);
+ }
+ if (tree->value_destroy_func) {
+ tree->value_destroy_func(node->value);
+ }
+ }
+
+ g_free(node);
+
+ tree->nnodes--;
+
+ return TRUE;
+}
+
+/**
+ * q_tree_lookup_node:
+ * @tree: a #QTree
+ * @key: the key to look up
+ *
+ * Gets the tree node corresponding to the given key. Since a #QTree is
+ * automatically balanced as key/value pairs are added, key lookup
+ * is O(log n) (where n is the number of key/value pairs in the tree).
+ *
+ * Returns: (nullable) (transfer none): the tree node corresponding to
+ * the key, or %NULL if the key was not found
+ *
+ * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
+ */
+static QTreeNode *
+q_tree_lookup_node(QTree *tree,
+ gconstpointer key)
+{
+ g_return_val_if_fail(tree != NULL, NULL);
+
+ return q_tree_find_node(tree, key);
+}
+
+/**
+ * q_tree_lookup:
+ * @tree: a #QTree
+ * @key: the key to look up
+ *
+ * Gets the value corresponding to the given key. Since a #QTree is
+ * automatically balanced as key/value pairs are added, key lookup
+ * is O(log n) (where n is the number of key/value pairs in the tree).
+ *
+ * Returns: the value corresponding to the key, or %NULL
+ * if the key was not found
+ */
+gpointer
+q_tree_lookup(QTree *tree,
+ gconstpointer key)
+{
+ QTreeNode *node;
+
+ node = q_tree_lookup_node(tree, key);
+
+ return node ? node->value : NULL;
+}
+
+/**
+ * q_tree_lookup_extended:
+ * @tree: a #QTree
+ * @lookup_key: the key to look up
+ * @orig_key: (out) (optional) (nullable): returns the original key
+ * @value: (out) (optional) (nullable): returns the value associated with
+ * the key
+ *
+ * Looks up a key in the #QTree, returning the original key and the
+ * associated value. This is useful if you need to free the memory
+ * allocated for the original key, for example before calling
+ * q_tree_remove().
+ *
+ * Returns: %TRUE if the key was found in the #QTree
+ */
+gboolean
+q_tree_lookup_extended(QTree *tree,
+ gconstpointer lookup_key,
+ gpointer *orig_key,
+ gpointer *value)
+{
+ QTreeNode *node;
+
+ g_return_val_if_fail(tree != NULL, FALSE);
+
+ node = q_tree_find_node(tree, lookup_key);
+
+ if (node) {
+ if (orig_key) {
+ *orig_key = node->key;
+ }
+ if (value) {
+ *value = node->value;
+ }
+ return TRUE;
+ } else {
+ return FALSE;
+ }
+}
+
+/**
+ * q_tree_foreach:
+ * @tree: a #QTree
+ * @func: the function to call for each node visited.
+ * If this function returns %TRUE, the traversal is stopped.
+ * @user_data: user data to pass to the function
+ *
+ * Calls the given function for each of the key/value pairs in the #QTree.
+ * The function is passed the key and value of each pair, and the given
+ * @data parameter. The tree is traversed in sorted order.
+ *
+ * The tree may not be modified while iterating over it (you can't
+ * add/remove items). To remove all items matching a predicate, you need
+ * to add each item to a list in your #GTraverseFunc as you walk over
+ * the tree, then walk the list and remove each item.
+ */
+void
+q_tree_foreach(QTree *tree,
+ GTraverseFunc func,
+ gpointer user_data)
+{
+ QTreeNode *node;
+
+ g_return_if_fail(tree != NULL);
+
+ if (!tree->root) {
+ return;
+ }
+
+ node = q_tree_node_first(tree);
+
+ while (node) {
+ if ((*func)(node->key, node->value, user_data)) {
+ break;
+ }
+
+ node = q_tree_node_next(node);
+ }
+}
+
+/**
+ * q_tree_search_node:
+ * @tree: a #QTree
+ * @search_func: a function used to search the #QTree
+ * @user_data: the data passed as the second argument to @search_func
+ *
+ * Searches a #QTree using @search_func.
+ *
+ * The @search_func is called with a pointer to the key of a key/value
+ * pair in the tree, and the passed in @user_data. If @search_func returns
+ * 0 for a key/value pair, then the corresponding node is returned as
+ * the result of q_tree_search(). If @search_func returns -1, searching
+ * will proceed among the key/value pairs that have a smaller key; if
+ * @search_func returns 1, searching will proceed among the key/value
+ * pairs that have a larger key.
+ *
+ * Returns: (nullable) (transfer none): the node corresponding to the
+ * found key, or %NULL if the key was not found
+ *
+ * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
+ */
+static QTreeNode *
+q_tree_search_node(QTree *tree,
+ GCompareFunc search_func,
+ gconstpointer user_data)
+{
+ g_return_val_if_fail(tree != NULL, NULL);
+
+ if (!tree->root) {
+ return NULL;
+ }
+
+ return q_tree_node_search(tree->root, search_func, user_data);
+}
+
+/**
+ * q_tree_search:
+ * @tree: a #QTree
+ * @search_func: a function used to search the #QTree
+ * @user_data: the data passed as the second argument to @search_func
+ *
+ * Searches a #QTree using @search_func.
+ *
+ * The @search_func is called with a pointer to the key of a key/value
+ * pair in the tree, and the passed in @user_data. If @search_func returns
+ * 0 for a key/value pair, then the corresponding value is returned as
+ * the result of q_tree_search(). If @search_func returns -1, searching
+ * will proceed among the key/value pairs that have a smaller key; if
+ * @search_func returns 1, searching will proceed among the key/value
+ * pairs that have a larger key.
+ *
+ * Returns: the value corresponding to the found key, or %NULL
+ * if the key was not found
+ */
+gpointer
+q_tree_search(QTree *tree,
+ GCompareFunc search_func,
+ gconstpointer user_data)
+{
+ QTreeNode *node;
+
+ node = q_tree_search_node(tree, search_func, user_data);
+
+ return node ? node->value : NULL;
+}
+
+/**
+ * q_tree_height:
+ * @tree: a #QTree
+ *
+ * Gets the height of a #QTree.
+ *
+ * If the #QTree contains no nodes, the height is 0.
+ * If the #QTree contains only one root node the height is 1.
+ * If the root node has children the height is 2, etc.
+ *
+ * Returns: the height of @tree
+ */
+gint
+q_tree_height(QTree *tree)
+{
+ QTreeNode *node;
+ gint height;
+
+ g_return_val_if_fail(tree != NULL, 0);
+
+ if (!tree->root) {
+ return 0;
+ }
+
+ height = 0;
+ node = tree->root;
+
+ while (1) {
+ height += 1 + MAX(node->balance, 0);
+
+ if (!node->left_child) {
+ return height;
+ }
+
+ node = node->left;
+ }
+}
+
+/**
+ * q_tree_nnodes:
+ * @tree: a #QTree
+ *
+ * Gets the number of nodes in a #QTree.
+ *
+ * Returns: the number of nodes in @tree
+ */
+gint
+q_tree_nnodes(QTree *tree)
+{
+ g_return_val_if_fail(tree != NULL, 0);
+
+ return tree->nnodes;
+}
+
+static QTreeNode *
+q_tree_node_balance(QTreeNode *node)
+{
+ if (node->balance < -1) {
+ if (node->left->balance > 0) {
+ node->left = q_tree_node_rotate_left(node->left);
+ }
+ node = q_tree_node_rotate_right(node);
+ } else if (node->balance > 1) {
+ if (node->right->balance < 0) {
+ node->right = q_tree_node_rotate_right(node->right);
+ }
+ node = q_tree_node_rotate_left(node);
+ }
+
+ return node;
+}
+
+static QTreeNode *
+q_tree_find_node(QTree *tree,
+ gconstpointer key)
+{
+ QTreeNode *node;
+ gint cmp;
+
+ node = tree->root;
+ if (!node) {
+ return NULL;
+ }
+
+ while (1) {
+ cmp = tree->key_compare(key, node->key, tree->key_compare_data);
+ if (cmp == 0) {
+ return node;
+ } else if (cmp < 0) {
+ if (!node->left_child) {
+ return NULL;
+ }
+
+ node = node->left;
+ } else {
+ if (!node->right_child) {
+ return NULL;
+ }
+
+ node = node->right;
+ }
+ }
+}
+
+static QTreeNode *
+q_tree_node_search(QTreeNode *node,
+ GCompareFunc search_func,
+ gconstpointer data)
+{
+ gint dir;
+
+ if (!node) {
+ return NULL;
+ }
+
+ while (1) {
+ dir = (*search_func)(node->key, data);
+ if (dir == 0) {
+ return node;
+ } else if (dir < 0) {
+ if (!node->left_child) {
+ return NULL;
+ }
+
+ node = node->left;
+ } else {
+ if (!node->right_child) {
+ return NULL;
+ }
+
+ node = node->right;
+ }
+ }
+}
+
+static QTreeNode *
+q_tree_node_rotate_left(QTreeNode *node)
+{
+ QTreeNode *right;
+ gint a_bal;
+ gint b_bal;
+
+ right = node->right;
+
+ if (right->left_child) {
+ node->right = right->left;
+ } else {
+ node->right_child = FALSE;
+ right->left_child = TRUE;
+ }
+ right->left = node;
+
+ a_bal = node->balance;
+ b_bal = right->balance;
+
+ if (b_bal <= 0) {
+ if (a_bal >= 1) {
+ right->balance = b_bal - 1;
+ } else {
+ right->balance = a_bal + b_bal - 2;
+ }
+ node->balance = a_bal - 1;
+ } else {
+ if (a_bal <= b_bal) {
+ right->balance = a_bal - 2;
+ } else {
+ right->balance = b_bal - 1;
+ }
+ node->balance = a_bal - b_bal - 1;
+ }
+
+ return right;
+}
+
+static QTreeNode *
+q_tree_node_rotate_right(QTreeNode *node)
+{
+ QTreeNode *left;
+ gint a_bal;
+ gint b_bal;
+
+ left = node->left;
+
+ if (left->right_child) {
+ node->left = left->right;
+ } else {
+ node->left_child = FALSE;
+ left->right_child = TRUE;
+ }
+ left->right = node;
+
+ a_bal = node->balance;
+ b_bal = left->balance;
+
+ if (b_bal <= 0) {
+ if (b_bal > a_bal) {
+ left->balance = b_bal + 1;
+ } else {
+ left->balance = a_bal + 2;
+ }
+ node->balance = a_bal - b_bal + 1;
+ } else {
+ if (a_bal <= -1) {
+ left->balance = b_bal + 1;
+ } else {
+ left->balance = a_bal + b_bal + 2;
+ }
+ node->balance = a_bal + 1;
+ }
+
+ return left;
+}
+
+#ifdef Q_TREE_DEBUG
+static gint
+q_tree_node_height(QTreeNode *node)
+{
+ gint left_height;
+ gint right_height;
+
+ if (node) {
+ left_height = 0;
+ right_height = 0;
+
+ if (node->left_child) {
+ left_height = q_tree_node_height(node->left);
+ }
+
+ if (node->right_child) {
+ right_height = q_tree_node_height(node->right);
+ }
+
+ return MAX(left_height, right_height) + 1;
+ }
+
+ return 0;
+}
+
+static void q_tree_node_check(QTreeNode *node)
+{
+ gint left_height;
+ gint right_height;
+ gint balance;
+ QTreeNode *tmp;
+
+ if (node) {
+ if (node->left_child) {
+ tmp = q_tree_node_previous(node);
+ g_assert(tmp->right == node);
+ }
+
+ if (node->right_child) {
+ tmp = q_tree_node_next(node);
+ g_assert(tmp->left == node);
+ }
+
+ left_height = 0;
+ right_height = 0;
+
+ if (node->left_child) {
+ left_height = q_tree_node_height(node->left);
+ }
+ if (node->right_child) {
+ right_height = q_tree_node_height(node->right);
+ }
+
+ balance = right_height - left_height;
+ g_assert(balance == node->balance);
+
+ if (node->left_child) {
+ q_tree_node_check(node->left);
+ }
+ if (node->right_child) {
+ q_tree_node_check(node->right);
+ }
+ }
+}
+#endif
@@ -9,6 +9,10 @@ xbzrle_bench = executable('xbzrle-bench',
dependencies: [qemuutil,migration])
endif
+qtree_bench = executable('qtree-bench',
+ sources: 'qtree-bench.c',
+ dependencies: [qemuutil])
+
executable('atomic_add-bench',
sources: files('atomic_add-bench.c'),
dependencies: [qemuutil],
@@ -36,6 +36,7 @@ tests = {
'test-rcu-slist': [],
'test-qdist': [],
'test-qht': [],
+ 'test-qtree': [],
'test-bitops': [],
'test-bitcnt': [],
'test-qgraph': ['../qtest/libqos/qgraph.c'],
@@ -26,6 +26,7 @@ util_ss.add(when: 'CONFIG_WIN32', if_true: files('oslib-win32.c'))
util_ss.add(when: 'CONFIG_WIN32', if_true: files('qemu-thread-win32.c'))
util_ss.add(when: 'CONFIG_WIN32', if_true: winmm)
util_ss.add(when: 'CONFIG_WIN32', if_true: pathcch)
+util_ss.add(when: 'HAVE_GLIB_WITH_SLICE_ALLOCATOR', if_true: files('qtree.c'))
util_ss.add(files('envlist.c', 'path.c', 'module.c'))
util_ss.add(files('host-utils.c'))
util_ss.add(files('bitmap.c', 'bitops.c'))