@samitouri / QOSamiQemu
Code Commits Issues Pulls Sessions CI/CD
master
master
h 200 lines 6.32 KB
Raw
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 */