1e3feb2ccSEmilio Cota /* 2e3feb2ccSEmilio Cota * GLIB - Library of useful routines for C programming 3e3feb2ccSEmilio Cota * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald 4e3feb2ccSEmilio Cota * 5e3feb2ccSEmilio Cota * SPDX-License-Identifier: LGPL-2.1-or-later 6e3feb2ccSEmilio Cota * 7e3feb2ccSEmilio Cota * This library is free software; you can redistribute it and/or 8e3feb2ccSEmilio Cota * modify it under the terms of the GNU Lesser General Public 9e3feb2ccSEmilio Cota * License as published by the Free Software Foundation; either 10e3feb2ccSEmilio Cota * version 2.1 of the License, or (at your option) any later version. 11e3feb2ccSEmilio Cota * 12e3feb2ccSEmilio Cota * This library is distributed in the hope that it will be useful, 13e3feb2ccSEmilio Cota * but WITHOUT ANY WARRANTY; without even the implied warranty of 14e3feb2ccSEmilio Cota * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15e3feb2ccSEmilio Cota * Lesser General Public License for more details. 16e3feb2ccSEmilio Cota * 17e3feb2ccSEmilio Cota * You should have received a copy of the GNU Lesser General Public 18e3feb2ccSEmilio Cota * License along with this library; if not, see <http://www.gnu.org/licenses/>. 19e3feb2ccSEmilio Cota */ 20e3feb2ccSEmilio Cota 21e3feb2ccSEmilio Cota /* 22e3feb2ccSEmilio Cota * Modified by the GLib Team and others 1997-2000. See the AUTHORS 23e3feb2ccSEmilio Cota * file for a list of people on the GLib Team. See the ChangeLog 24e3feb2ccSEmilio Cota * files for a list of changes. These files are distributed with 25e3feb2ccSEmilio Cota * GLib at ftp://ftp.gtk.org/pub/gtk/. 26e3feb2ccSEmilio Cota */ 27e3feb2ccSEmilio Cota 28e3feb2ccSEmilio Cota /* 29e3feb2ccSEmilio Cota * QTree is a partial import of Glib's GTree. The parts excluded correspond 30e3feb2ccSEmilio Cota * to API calls either deprecated (e.g. g_tree_traverse) or recently added 31e3feb2ccSEmilio Cota * (e.g. g_tree_search_node, added in 2.68); neither have callers in QEMU. 32e3feb2ccSEmilio Cota * 33e3feb2ccSEmilio Cota * The reason for this import is to allow us to control the memory allocator 34e3feb2ccSEmilio Cota * used by the tree implementation. Until Glib 2.75.3, GTree uses Glib's 35e3feb2ccSEmilio Cota * slice allocator, which causes problems when forking in user-mode; 36e3feb2ccSEmilio Cota * see https://gitlab.com/qemu-project/qemu/-/issues/285 and glib's 37e3feb2ccSEmilio Cota * "45b5a6c1e gslice: Remove slice allocator and use malloc() instead". 38e3feb2ccSEmilio Cota * 39e3feb2ccSEmilio Cota * TODO: remove QTree when QEMU's minimum Glib version is >= 2.75.3. 40e3feb2ccSEmilio Cota */ 41e3feb2ccSEmilio Cota 42e3feb2ccSEmilio Cota #ifndef QEMU_QTREE_H 43e3feb2ccSEmilio Cota #define QEMU_QTREE_H 44e3feb2ccSEmilio Cota 45e3feb2ccSEmilio Cota #include "qemu/osdep.h" 46e3feb2ccSEmilio Cota 47e3feb2ccSEmilio Cota #ifdef HAVE_GLIB_WITH_SLICE_ALLOCATOR 48e3feb2ccSEmilio Cota 49e3feb2ccSEmilio Cota typedef struct _QTree QTree; 50e3feb2ccSEmilio Cota 51e3feb2ccSEmilio Cota typedef struct _QTreeNode QTreeNode; 52e3feb2ccSEmilio Cota 53e3feb2ccSEmilio Cota typedef gboolean (*QTraverseNodeFunc)(QTreeNode *node, 54e3feb2ccSEmilio Cota gpointer user_data); 55e3feb2ccSEmilio Cota 56e3feb2ccSEmilio Cota /* 57e3feb2ccSEmilio Cota * Balanced binary trees 58e3feb2ccSEmilio Cota */ 59e3feb2ccSEmilio Cota QTree *q_tree_new(GCompareFunc key_compare_func); 60e3feb2ccSEmilio Cota QTree *q_tree_new_with_data(GCompareDataFunc key_compare_func, 61e3feb2ccSEmilio Cota gpointer key_compare_data); 62e3feb2ccSEmilio Cota QTree *q_tree_new_full(GCompareDataFunc key_compare_func, 63e3feb2ccSEmilio Cota gpointer key_compare_data, 64e3feb2ccSEmilio Cota GDestroyNotify key_destroy_func, 65e3feb2ccSEmilio Cota GDestroyNotify value_destroy_func); 66e3feb2ccSEmilio Cota QTree *q_tree_ref(QTree *tree); 67e3feb2ccSEmilio Cota void q_tree_unref(QTree *tree); 68e3feb2ccSEmilio Cota void q_tree_destroy(QTree *tree); 69e3feb2ccSEmilio Cota void q_tree_insert(QTree *tree, 70e3feb2ccSEmilio Cota gpointer key, 71e3feb2ccSEmilio Cota gpointer value); 72e3feb2ccSEmilio Cota void q_tree_replace(QTree *tree, 73e3feb2ccSEmilio Cota gpointer key, 74e3feb2ccSEmilio Cota gpointer value); 75e3feb2ccSEmilio Cota gboolean q_tree_remove(QTree *tree, 76e3feb2ccSEmilio Cota gconstpointer key); 77e3feb2ccSEmilio Cota gboolean q_tree_steal(QTree *tree, 78e3feb2ccSEmilio Cota gconstpointer key); 79e3feb2ccSEmilio Cota gpointer q_tree_lookup(QTree *tree, 80e3feb2ccSEmilio Cota gconstpointer key); 81e3feb2ccSEmilio Cota gboolean q_tree_lookup_extended(QTree *tree, 82e3feb2ccSEmilio Cota gconstpointer lookup_key, 83e3feb2ccSEmilio Cota gpointer *orig_key, 84e3feb2ccSEmilio Cota gpointer *value); 85e3feb2ccSEmilio Cota void q_tree_foreach(QTree *tree, 86e3feb2ccSEmilio Cota GTraverseFunc func, 87e3feb2ccSEmilio Cota gpointer user_data); 88e3feb2ccSEmilio Cota gpointer q_tree_search(QTree *tree, 89e3feb2ccSEmilio Cota GCompareFunc search_func, 90e3feb2ccSEmilio Cota gconstpointer user_data); 91e3feb2ccSEmilio Cota gint q_tree_height(QTree *tree); 92e3feb2ccSEmilio Cota gint q_tree_nnodes(QTree *tree); 93e3feb2ccSEmilio Cota 94e3feb2ccSEmilio Cota #else /* !HAVE_GLIB_WITH_SLICE_ALLOCATOR */ 95e3feb2ccSEmilio Cota 96e3feb2ccSEmilio Cota typedef GTree QTree; 97e3feb2ccSEmilio Cota typedef GTreeNode QTreeNode; 98e3feb2ccSEmilio Cota typedef GTraverseNodeFunc QTraverseNodeFunc; 99e3feb2ccSEmilio Cota 100e3feb2ccSEmilio Cota static inline QTree *q_tree_new(GCompareFunc key_compare_func) 101e3feb2ccSEmilio Cota { 102e3feb2ccSEmilio Cota return g_tree_new(key_compare_func); 103e3feb2ccSEmilio Cota } 104e3feb2ccSEmilio Cota 105e3feb2ccSEmilio Cota static inline QTree *q_tree_new_with_data(GCompareDataFunc key_compare_func, 106e3feb2ccSEmilio Cota gpointer key_compare_data) 107e3feb2ccSEmilio Cota { 108e3feb2ccSEmilio Cota return g_tree_new_with_data(key_compare_func, key_compare_data); 109e3feb2ccSEmilio Cota } 110e3feb2ccSEmilio Cota 111e3feb2ccSEmilio Cota static inline QTree *q_tree_new_full(GCompareDataFunc key_compare_func, 112e3feb2ccSEmilio Cota gpointer key_compare_data, 113e3feb2ccSEmilio Cota GDestroyNotify key_destroy_func, 114e3feb2ccSEmilio Cota GDestroyNotify value_destroy_func) 115e3feb2ccSEmilio Cota { 116e3feb2ccSEmilio Cota return g_tree_new_full(key_compare_func, key_compare_data, 117e3feb2ccSEmilio Cota key_destroy_func, value_destroy_func); 118e3feb2ccSEmilio Cota } 119e3feb2ccSEmilio Cota 120e3feb2ccSEmilio Cota static inline QTree *q_tree_ref(QTree *tree) 121e3feb2ccSEmilio Cota { 122e3feb2ccSEmilio Cota return g_tree_ref(tree); 123e3feb2ccSEmilio Cota } 124e3feb2ccSEmilio Cota 125e3feb2ccSEmilio Cota static inline void q_tree_unref(QTree *tree) 126e3feb2ccSEmilio Cota { 127e3feb2ccSEmilio Cota g_tree_unref(tree); 128e3feb2ccSEmilio Cota } 129e3feb2ccSEmilio Cota 130e3feb2ccSEmilio Cota static inline void q_tree_destroy(QTree *tree) 131e3feb2ccSEmilio Cota { 132e3feb2ccSEmilio Cota g_tree_destroy(tree); 133e3feb2ccSEmilio Cota } 134e3feb2ccSEmilio Cota 135e3feb2ccSEmilio Cota static inline void q_tree_insert(QTree *tree, 136e3feb2ccSEmilio Cota gpointer key, 137e3feb2ccSEmilio Cota gpointer value) 138e3feb2ccSEmilio Cota { 139e3feb2ccSEmilio Cota g_tree_insert(tree, key, value); 140e3feb2ccSEmilio Cota } 141e3feb2ccSEmilio Cota 142e3feb2ccSEmilio Cota static inline void q_tree_replace(QTree *tree, 143e3feb2ccSEmilio Cota gpointer key, 144e3feb2ccSEmilio Cota gpointer value) 145e3feb2ccSEmilio Cota { 146e3feb2ccSEmilio Cota g_tree_replace(tree, key, value); 147e3feb2ccSEmilio Cota } 148e3feb2ccSEmilio Cota 149e3feb2ccSEmilio Cota static inline gboolean q_tree_remove(QTree *tree, 150e3feb2ccSEmilio Cota gconstpointer key) 151e3feb2ccSEmilio Cota { 152e3feb2ccSEmilio Cota return g_tree_remove(tree, key); 153e3feb2ccSEmilio Cota } 154e3feb2ccSEmilio Cota 155e3feb2ccSEmilio Cota static inline gboolean q_tree_steal(QTree *tree, 156e3feb2ccSEmilio Cota gconstpointer key) 157e3feb2ccSEmilio Cota { 158e3feb2ccSEmilio Cota return g_tree_steal(tree, key); 159e3feb2ccSEmilio Cota } 160e3feb2ccSEmilio Cota 161e3feb2ccSEmilio Cota static inline gpointer q_tree_lookup(QTree *tree, 162e3feb2ccSEmilio Cota gconstpointer key) 163e3feb2ccSEmilio Cota { 164e3feb2ccSEmilio Cota return g_tree_lookup(tree, key); 165e3feb2ccSEmilio Cota } 166e3feb2ccSEmilio Cota 167e3feb2ccSEmilio Cota static inline gboolean q_tree_lookup_extended(QTree *tree, 168e3feb2ccSEmilio Cota gconstpointer lookup_key, 169e3feb2ccSEmilio Cota gpointer *orig_key, 170e3feb2ccSEmilio Cota gpointer *value) 171e3feb2ccSEmilio Cota { 172e3feb2ccSEmilio Cota return g_tree_lookup_extended(tree, lookup_key, orig_key, value); 173e3feb2ccSEmilio Cota } 174e3feb2ccSEmilio Cota 175e3feb2ccSEmilio Cota static inline void q_tree_foreach(QTree *tree, 176e3feb2ccSEmilio Cota GTraverseFunc func, 177e3feb2ccSEmilio Cota gpointer user_data) 178e3feb2ccSEmilio Cota { 179e3feb2ccSEmilio Cota return g_tree_foreach(tree, func, user_data); 180e3feb2ccSEmilio Cota } 181e3feb2ccSEmilio Cota 182e3feb2ccSEmilio Cota static inline gpointer q_tree_search(QTree *tree, 183e3feb2ccSEmilio Cota GCompareFunc search_func, 184e3feb2ccSEmilio Cota gconstpointer user_data) 185e3feb2ccSEmilio Cota { 186e3feb2ccSEmilio Cota return g_tree_search(tree, search_func, user_data); 187e3feb2ccSEmilio Cota } 188e3feb2ccSEmilio Cota 189e3feb2ccSEmilio Cota static inline gint q_tree_height(QTree *tree) 190e3feb2ccSEmilio Cota { 191e3feb2ccSEmilio Cota return g_tree_height(tree); 192e3feb2ccSEmilio Cota } 193e3feb2ccSEmilio Cota 194e3feb2ccSEmilio Cota static inline gint q_tree_nnodes(QTree *tree) 195e3feb2ccSEmilio Cota { 196e3feb2ccSEmilio Cota return g_tree_nnodes(tree); 197e3feb2ccSEmilio Cota } 198e3feb2ccSEmilio Cota 199e3feb2ccSEmilio Cota #endif /* HAVE_GLIB_WITH_SLICE_ALLOCATOR */ 200e3feb2ccSEmilio Cota 201e3feb2ccSEmilio Cota #endif /* QEMU_QTREE_H */ 202