]>
Commit | Line | Data |
---|---|---|
e3feb2cc EC |
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 | ||
e3feb2cc EC |
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 */ |