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