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