include/qemu/qtree.h

   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 */