1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
/*
* GLIB - Library of useful routines for C programming
* Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
*
* SPDX-License-Identifier: LGPL-2.1-or-later
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, see <http://www.gnu.org/licenses/>.
*/
/*
* Modified by the GLib Team and others 1997-2000. See the AUTHORS
* file for a list of people on the GLib Team. See the ChangeLog
* files for a list of changes. These files are distributed with
* GLib at ftp://ftp.gtk.org/pub/gtk/.
*/
/*
* QTree is a partial import of Glib's GTree. The parts excluded correspond
* to API calls either deprecated (e.g. g_tree_traverse) or recently added
* (e.g. g_tree_search_node, added in 2.68); neither have callers in QEMU.
*
* The reason for this import is to allow us to control the memory allocator
* used by the tree implementation. Until Glib 2.75.3, GTree uses Glib's
* slice allocator, which causes problems when forking in user-mode;
* see https://gitlab.com/qemu-project/qemu/-/issues/285 and glib's
* "45b5a6c1e gslice: Remove slice allocator and use malloc() instead".
*
* TODO: remove QTree when QEMU's minimum Glib version is >= 2.75.3.
*/
#ifndef QEMU_QTREE_H
#define QEMU_QTREE_H
#include "qemu/osdep.h"
#ifdef HAVE_GLIB_WITH_SLICE_ALLOCATOR
typedef struct _QTree QTree;
typedef struct _QTreeNode QTreeNode;
typedef gboolean (*QTraverseNodeFunc)(QTreeNode *node,
gpointer user_data);
/*
* Balanced binary trees
*/
QTree *q_tree_new(GCompareFunc key_compare_func);
QTree *q_tree_new_with_data(GCompareDataFunc key_compare_func,
gpointer key_compare_data);
QTree *q_tree_new_full(GCompareDataFunc key_compare_func,
gpointer key_compare_data,
GDestroyNotify key_destroy_func,
GDestroyNotify value_destroy_func);
QTree *q_tree_ref(QTree *tree);
void q_tree_unref(QTree *tree);
void q_tree_destroy(QTree *tree);
void q_tree_insert(QTree *tree,
gpointer key,
gpointer value);
void q_tree_replace(QTree *tree,
gpointer key,
gpointer value);
gboolean q_tree_remove(QTree *tree,
gconstpointer key);
gboolean q_tree_steal(QTree *tree,
gconstpointer key);
gpointer q_tree_lookup(QTree *tree,
gconstpointer key);
gboolean q_tree_lookup_extended(QTree *tree,
gconstpointer lookup_key,
gpointer *orig_key,
gpointer *value);
void q_tree_foreach(QTree *tree,
GTraverseFunc func,
gpointer user_data);
gpointer q_tree_search(QTree *tree,
GCompareFunc search_func,
gconstpointer user_data);
gint q_tree_height(QTree *tree);
gint q_tree_nnodes(QTree *tree);
#else /* !HAVE_GLIB_WITH_SLICE_ALLOCATOR */
typedef GTree QTree;
typedef GTreeNode QTreeNode;
typedef GTraverseNodeFunc QTraverseNodeFunc;
static inline QTree *q_tree_new(GCompareFunc key_compare_func)
{
return g_tree_new(key_compare_func);
}
static inline QTree *q_tree_new_with_data(GCompareDataFunc key_compare_func,
gpointer key_compare_data)
{
return g_tree_new_with_data(key_compare_func, key_compare_data);
}
static inline QTree *q_tree_new_full(GCompareDataFunc key_compare_func,
gpointer key_compare_data,
GDestroyNotify key_destroy_func,
GDestroyNotify value_destroy_func)
{
return g_tree_new_full(key_compare_func, key_compare_data,
key_destroy_func, value_destroy_func);
}
static inline QTree *q_tree_ref(QTree *tree)
{
return g_tree_ref(tree);
}
static inline void q_tree_unref(QTree *tree)
{
g_tree_unref(tree);
}
static inline void q_tree_destroy(QTree *tree)
{
g_tree_destroy(tree);
}
static inline void q_tree_insert(QTree *tree,
gpointer key,
gpointer value)
{
g_tree_insert(tree, key, value);
}
static inline void q_tree_replace(QTree *tree,
gpointer key,
gpointer value)
{
g_tree_replace(tree, key, value);
}
static inline gboolean q_tree_remove(QTree *tree,
gconstpointer key)
{
return g_tree_remove(tree, key);
}
static inline gboolean q_tree_steal(QTree *tree,
gconstpointer key)
{
return g_tree_steal(tree, key);
}
static inline gpointer q_tree_lookup(QTree *tree,
gconstpointer key)
{
return g_tree_lookup(tree, key);
}
static inline gboolean q_tree_lookup_extended(QTree *tree,
gconstpointer lookup_key,
gpointer *orig_key,
gpointer *value)
{
return g_tree_lookup_extended(tree, lookup_key, orig_key, value);
}
static inline void q_tree_foreach(QTree *tree,
GTraverseFunc func,
gpointer user_data)
{
return g_tree_foreach(tree, func, user_data);
}
static inline gpointer q_tree_search(QTree *tree,
GCompareFunc search_func,
gconstpointer user_data)
{
return g_tree_search(tree, search_func, user_data);
}
static inline gint q_tree_height(QTree *tree)
{
return g_tree_height(tree);
}
static inline gint q_tree_nnodes(QTree *tree)
{
return g_tree_nnodes(tree);
}
#endif /* HAVE_GLIB_WITH_SLICE_ALLOCATOR */
#endif /* QEMU_QTREE_H */
|
