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 46 #ifdef HAVE_GLIB_WITH_SLICE_ALLOCATOR 47 48 typedef struct _QTree QTree; 49 50 typedef struct _QTreeNode QTreeNode; 51 52 typedef gboolean (*QTraverseNodeFunc)(QTreeNode *node, 53 gpointer user_data); 54 55 /* 56 * Balanced binary trees 57 */ 58 QTree *q_tree_new(GCompareFunc key_compare_func); 59 QTree *q_tree_new_with_data(GCompareDataFunc key_compare_func, 60 gpointer key_compare_data); 61 QTree *q_tree_new_full(GCompareDataFunc key_compare_func, 62 gpointer key_compare_data, 63 GDestroyNotify key_destroy_func, 64 GDestroyNotify value_destroy_func); 65 QTree *q_tree_ref(QTree *tree); 66 void q_tree_unref(QTree *tree); 67 void q_tree_destroy(QTree *tree); 68 void q_tree_insert(QTree *tree, 69 gpointer key, 70 gpointer value); 71 void q_tree_replace(QTree *tree, 72 gpointer key, 73 gpointer value); 74 gboolean q_tree_remove(QTree *tree, 75 gconstpointer key); 76 gboolean q_tree_steal(QTree *tree, 77 gconstpointer key); 78 gpointer q_tree_lookup(QTree *tree, 79 gconstpointer key); 80 gboolean q_tree_lookup_extended(QTree *tree, 81 gconstpointer lookup_key, 82 gpointer *orig_key, 83 gpointer *value); 84 void q_tree_foreach(QTree *tree, 85 GTraverseFunc func, 86 gpointer user_data); 87 gpointer q_tree_search(QTree *tree, 88 GCompareFunc search_func, 89 gconstpointer user_data); 90 gint q_tree_height(QTree *tree); 91 gint q_tree_nnodes(QTree *tree); 92 93 #else /* !HAVE_GLIB_WITH_SLICE_ALLOCATOR */ 94 95 typedef GTree QTree; 96 typedef GTreeNode QTreeNode; 97 typedef GTraverseNodeFunc QTraverseNodeFunc; 98 99 static inline QTree *q_tree_new(GCompareFunc key_compare_func) 100 { 101 return g_tree_new(key_compare_func); 102 } 103 104 static inline QTree *q_tree_new_with_data(GCompareDataFunc key_compare_func, 105 gpointer key_compare_data) 106 { 107 return g_tree_new_with_data(key_compare_func, key_compare_data); 108 } 109 110 static inline QTree *q_tree_new_full(GCompareDataFunc key_compare_func, 111 gpointer key_compare_data, 112 GDestroyNotify key_destroy_func, 113 GDestroyNotify value_destroy_func) 114 { 115 return g_tree_new_full(key_compare_func, key_compare_data, 116 key_destroy_func, value_destroy_func); 117 } 118 119 static inline QTree *q_tree_ref(QTree *tree) 120 { 121 return g_tree_ref(tree); 122 } 123 124 static inline void q_tree_unref(QTree *tree) 125 { 126 g_tree_unref(tree); 127 } 128 129 static inline void q_tree_destroy(QTree *tree) 130 { 131 g_tree_destroy(tree); 132 } 133 134 static inline void q_tree_insert(QTree *tree, 135 gpointer key, 136 gpointer value) 137 { 138 g_tree_insert(tree, key, value); 139 } 140 141 static inline void q_tree_replace(QTree *tree, 142 gpointer key, 143 gpointer value) 144 { 145 g_tree_replace(tree, key, value); 146 } 147 148 static inline gboolean q_tree_remove(QTree *tree, 149 gconstpointer key) 150 { 151 return g_tree_remove(tree, key); 152 } 153 154 static inline gboolean q_tree_steal(QTree *tree, 155 gconstpointer key) 156 { 157 return g_tree_steal(tree, key); 158 } 159 160 static inline gpointer q_tree_lookup(QTree *tree, 161 gconstpointer key) 162 { 163 return g_tree_lookup(tree, key); 164 } 165 166 static inline gboolean q_tree_lookup_extended(QTree *tree, 167 gconstpointer lookup_key, 168 gpointer *orig_key, 169 gpointer *value) 170 { 171 return g_tree_lookup_extended(tree, lookup_key, orig_key, value); 172 } 173 174 static inline void q_tree_foreach(QTree *tree, 175 GTraverseFunc func, 176 gpointer user_data) 177 { 178 return g_tree_foreach(tree, func, user_data); 179 } 180 181 static inline gpointer q_tree_search(QTree *tree, 182 GCompareFunc search_func, 183 gconstpointer user_data) 184 { 185 return g_tree_search(tree, search_func, user_data); 186 } 187 188 static inline gint q_tree_height(QTree *tree) 189 { 190 return g_tree_height(tree); 191 } 192 193 static inline gint q_tree_nnodes(QTree *tree) 194 { 195 return g_tree_nnodes(tree); 196 } 197 198 #endif /* HAVE_GLIB_WITH_SLICE_ALLOCATOR */ 199 200 #endif /* QEMU_QTREE_H */ 201