]>
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 | * MT safe | |
30 | */ | |
31 | ||
32 | #include "qemu/osdep.h" | |
33 | #include "qemu/qtree.h" | |
34 | ||
35 | /** | |
36 | * SECTION:trees-binary | |
37 | * @title: Balanced Binary Trees | |
38 | * @short_description: a sorted collection of key/value pairs optimized | |
39 | * for searching and traversing in order | |
40 | * | |
41 | * The #QTree structure and its associated functions provide a sorted | |
42 | * collection of key/value pairs optimized for searching and traversing | |
43 | * in order. This means that most of the operations (access, search, | |
44 | * insertion, deletion, ...) on #QTree are O(log(n)) in average and O(n) | |
45 | * in worst case for time complexity. But, note that maintaining a | |
46 | * balanced sorted #QTree of n elements is done in time O(n log(n)). | |
47 | * | |
48 | * To create a new #QTree use q_tree_new(). | |
49 | * | |
50 | * To insert a key/value pair into a #QTree use q_tree_insert() | |
51 | * (O(n log(n))). | |
52 | * | |
53 | * To remove a key/value pair use q_tree_remove() (O(n log(n))). | |
54 | * | |
55 | * To look up the value corresponding to a given key, use | |
56 | * q_tree_lookup() and q_tree_lookup_extended(). | |
57 | * | |
58 | * To find out the number of nodes in a #QTree, use q_tree_nnodes(). To | |
59 | * get the height of a #QTree, use q_tree_height(). | |
60 | * | |
61 | * To traverse a #QTree, calling a function for each node visited in | |
62 | * the traversal, use q_tree_foreach(). | |
63 | * | |
64 | * To destroy a #QTree, use q_tree_destroy(). | |
65 | **/ | |
66 | ||
67 | #define MAX_GTREE_HEIGHT 40 | |
68 | ||
69 | /** | |
70 | * QTree: | |
71 | * | |
72 | * The QTree struct is an opaque data structure representing a | |
73 | * [balanced binary tree][glib-Balanced-Binary-Trees]. It should be | |
74 | * accessed only by using the following functions. | |
75 | */ | |
76 | struct _QTree { | |
77 | QTreeNode *root; | |
78 | GCompareDataFunc key_compare; | |
79 | GDestroyNotify key_destroy_func; | |
80 | GDestroyNotify value_destroy_func; | |
81 | gpointer key_compare_data; | |
82 | guint nnodes; | |
83 | gint ref_count; | |
84 | }; | |
85 | ||
86 | struct _QTreeNode { | |
87 | gpointer key; /* key for this node */ | |
88 | gpointer value; /* value stored at this node */ | |
89 | QTreeNode *left; /* left subtree */ | |
90 | QTreeNode *right; /* right subtree */ | |
91 | gint8 balance; /* height (right) - height (left) */ | |
92 | guint8 left_child; | |
93 | guint8 right_child; | |
94 | }; | |
95 | ||
96 | ||
97 | static QTreeNode *q_tree_node_new(gpointer key, | |
98 | gpointer value); | |
99 | static QTreeNode *q_tree_insert_internal(QTree *tree, | |
100 | gpointer key, | |
101 | gpointer value, | |
102 | gboolean replace); | |
103 | static gboolean q_tree_remove_internal(QTree *tree, | |
104 | gconstpointer key, | |
105 | gboolean steal); | |
106 | static QTreeNode *q_tree_node_balance(QTreeNode *node); | |
107 | static QTreeNode *q_tree_find_node(QTree *tree, | |
108 | gconstpointer key); | |
109 | static QTreeNode *q_tree_node_search(QTreeNode *node, | |
110 | GCompareFunc search_func, | |
111 | gconstpointer data); | |
112 | static QTreeNode *q_tree_node_rotate_left(QTreeNode *node); | |
113 | static QTreeNode *q_tree_node_rotate_right(QTreeNode *node); | |
114 | #ifdef Q_TREE_DEBUG | |
115 | static void q_tree_node_check(QTreeNode *node); | |
116 | #endif | |
117 | ||
118 | static QTreeNode* | |
119 | q_tree_node_new(gpointer key, | |
120 | gpointer value) | |
121 | { | |
122 | QTreeNode *node = g_new(QTreeNode, 1); | |
123 | ||
124 | node->balance = 0; | |
125 | node->left = NULL; | |
126 | node->right = NULL; | |
127 | node->left_child = FALSE; | |
128 | node->right_child = FALSE; | |
129 | node->key = key; | |
130 | node->value = value; | |
131 | ||
132 | return node; | |
133 | } | |
134 | ||
135 | /** | |
136 | * q_tree_new: | |
137 | * @key_compare_func: the function used to order the nodes in the #QTree. | |
138 | * It should return values similar to the standard strcmp() function - | |
139 | * 0 if the two arguments are equal, a negative value if the first argument | |
140 | * comes before the second, or a positive value if the first argument comes | |
141 | * after the second. | |
142 | * | |
143 | * Creates a new #QTree. | |
144 | * | |
145 | * Returns: a newly allocated #QTree | |
146 | */ | |
147 | QTree * | |
148 | q_tree_new(GCompareFunc key_compare_func) | |
149 | { | |
150 | g_return_val_if_fail(key_compare_func != NULL, NULL); | |
151 | ||
152 | return q_tree_new_full((GCompareDataFunc) key_compare_func, NULL, | |
153 | NULL, NULL); | |
154 | } | |
155 | ||
156 | /** | |
157 | * q_tree_new_with_data: | |
158 | * @key_compare_func: qsort()-style comparison function | |
159 | * @key_compare_data: data to pass to comparison function | |
160 | * | |
161 | * Creates a new #QTree with a comparison function that accepts user data. | |
162 | * See q_tree_new() for more details. | |
163 | * | |
164 | * Returns: a newly allocated #QTree | |
165 | */ | |
166 | QTree * | |
167 | q_tree_new_with_data(GCompareDataFunc key_compare_func, | |
168 | gpointer key_compare_data) | |
169 | { | |
170 | g_return_val_if_fail(key_compare_func != NULL, NULL); | |
171 | ||
172 | return q_tree_new_full(key_compare_func, key_compare_data, | |
173 | NULL, NULL); | |
174 | } | |
175 | ||
176 | /** | |
177 | * q_tree_new_full: | |
178 | * @key_compare_func: qsort()-style comparison function | |
179 | * @key_compare_data: data to pass to comparison function | |
180 | * @key_destroy_func: a function to free the memory allocated for the key | |
181 | * used when removing the entry from the #QTree or %NULL if you don't | |
182 | * want to supply such a function | |
183 | * @value_destroy_func: a function to free the memory allocated for the | |
184 | * value used when removing the entry from the #QTree or %NULL if you | |
185 | * don't want to supply such a function | |
186 | * | |
187 | * Creates a new #QTree like q_tree_new() and allows to specify functions | |
188 | * to free the memory allocated for the key and value that get called when | |
189 | * removing the entry from the #QTree. | |
190 | * | |
191 | * Returns: a newly allocated #QTree | |
192 | */ | |
193 | QTree * | |
194 | q_tree_new_full(GCompareDataFunc key_compare_func, | |
195 | gpointer key_compare_data, | |
196 | GDestroyNotify key_destroy_func, | |
197 | GDestroyNotify value_destroy_func) | |
198 | { | |
199 | QTree *tree; | |
200 | ||
201 | g_return_val_if_fail(key_compare_func != NULL, NULL); | |
202 | ||
203 | tree = g_new(QTree, 1); | |
204 | tree->root = NULL; | |
205 | tree->key_compare = key_compare_func; | |
206 | tree->key_destroy_func = key_destroy_func; | |
207 | tree->value_destroy_func = value_destroy_func; | |
208 | tree->key_compare_data = key_compare_data; | |
209 | tree->nnodes = 0; | |
210 | tree->ref_count = 1; | |
211 | ||
212 | return tree; | |
213 | } | |
214 | ||
215 | /** | |
216 | * q_tree_node_first: | |
217 | * @tree: a #QTree | |
218 | * | |
219 | * Returns the first in-order node of the tree, or %NULL | |
220 | * for an empty tree. | |
221 | * | |
222 | * Returns: (nullable) (transfer none): the first node in the tree | |
223 | * | |
224 | * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. | |
225 | */ | |
226 | static QTreeNode * | |
227 | q_tree_node_first(QTree *tree) | |
228 | { | |
229 | QTreeNode *tmp; | |
230 | ||
231 | g_return_val_if_fail(tree != NULL, NULL); | |
232 | ||
233 | if (!tree->root) { | |
234 | return NULL; | |
235 | } | |
236 | ||
237 | tmp = tree->root; | |
238 | ||
239 | while (tmp->left_child) { | |
240 | tmp = tmp->left; | |
241 | } | |
242 | ||
243 | return tmp; | |
244 | } | |
245 | ||
246 | /** | |
247 | * q_tree_node_previous | |
248 | * @node: a #QTree node | |
249 | * | |
250 | * Returns the previous in-order node of the tree, or %NULL | |
251 | * if the passed node was already the first one. | |
252 | * | |
253 | * Returns: (nullable) (transfer none): the previous node in the tree | |
254 | * | |
255 | * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. | |
256 | */ | |
257 | static QTreeNode * | |
258 | q_tree_node_previous(QTreeNode *node) | |
259 | { | |
260 | QTreeNode *tmp; | |
261 | ||
262 | g_return_val_if_fail(node != NULL, NULL); | |
263 | ||
264 | tmp = node->left; | |
265 | ||
266 | if (node->left_child) { | |
267 | while (tmp->right_child) { | |
268 | tmp = tmp->right; | |
269 | } | |
270 | } | |
271 | ||
272 | return tmp; | |
273 | } | |
274 | ||
275 | /** | |
276 | * q_tree_node_next | |
277 | * @node: a #QTree node | |
278 | * | |
279 | * Returns the next in-order node of the tree, or %NULL | |
280 | * if the passed node was already the last one. | |
281 | * | |
282 | * Returns: (nullable) (transfer none): the next node in the tree | |
283 | * | |
284 | * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. | |
285 | */ | |
286 | static QTreeNode * | |
287 | q_tree_node_next(QTreeNode *node) | |
288 | { | |
289 | QTreeNode *tmp; | |
290 | ||
291 | g_return_val_if_fail(node != NULL, NULL); | |
292 | ||
293 | tmp = node->right; | |
294 | ||
295 | if (node->right_child) { | |
296 | while (tmp->left_child) { | |
297 | tmp = tmp->left; | |
298 | } | |
299 | } | |
300 | ||
301 | return tmp; | |
302 | } | |
303 | ||
304 | /** | |
305 | * q_tree_remove_all: | |
306 | * @tree: a #QTree | |
307 | * | |
308 | * Removes all nodes from a #QTree and destroys their keys and values, | |
309 | * then resets the #QTree’s root to %NULL. | |
310 | * | |
311 | * Since: 2.70 in GLib. Internal in Qtree, i.e. not in the public API. | |
312 | */ | |
1ff4a81b | 313 | static void QEMU_DISABLE_CFI |
e3feb2cc EC |
314 | q_tree_remove_all(QTree *tree) |
315 | { | |
316 | QTreeNode *node; | |
317 | QTreeNode *next; | |
318 | ||
319 | g_return_if_fail(tree != NULL); | |
320 | ||
321 | node = q_tree_node_first(tree); | |
322 | ||
323 | while (node) { | |
324 | next = q_tree_node_next(node); | |
325 | ||
326 | if (tree->key_destroy_func) { | |
327 | tree->key_destroy_func(node->key); | |
328 | } | |
329 | if (tree->value_destroy_func) { | |
330 | tree->value_destroy_func(node->value); | |
331 | } | |
332 | g_free(node); | |
333 | ||
334 | #ifdef Q_TREE_DEBUG | |
335 | g_assert(tree->nnodes > 0); | |
336 | tree->nnodes--; | |
337 | #endif | |
338 | ||
339 | node = next; | |
340 | } | |
341 | ||
342 | #ifdef Q_TREE_DEBUG | |
343 | g_assert(tree->nnodes == 0); | |
344 | #endif | |
345 | ||
346 | tree->root = NULL; | |
347 | #ifndef Q_TREE_DEBUG | |
348 | tree->nnodes = 0; | |
349 | #endif | |
350 | } | |
351 | ||
352 | /** | |
353 | * q_tree_ref: | |
354 | * @tree: a #QTree | |
355 | * | |
356 | * Increments the reference count of @tree by one. | |
357 | * | |
358 | * It is safe to call this function from any thread. | |
359 | * | |
360 | * Returns: the passed in #QTree | |
361 | * | |
362 | * Since: 2.22 | |
363 | */ | |
364 | QTree * | |
365 | q_tree_ref(QTree *tree) | |
366 | { | |
367 | g_return_val_if_fail(tree != NULL, NULL); | |
368 | ||
369 | g_atomic_int_inc(&tree->ref_count); | |
370 | ||
371 | return tree; | |
372 | } | |
373 | ||
374 | /** | |
375 | * q_tree_unref: | |
376 | * @tree: a #QTree | |
377 | * | |
378 | * Decrements the reference count of @tree by one. | |
379 | * If the reference count drops to 0, all keys and values will | |
380 | * be destroyed (if destroy functions were specified) and all | |
381 | * memory allocated by @tree will be released. | |
382 | * | |
383 | * It is safe to call this function from any thread. | |
384 | * | |
385 | * Since: 2.22 | |
386 | */ | |
387 | void | |
388 | q_tree_unref(QTree *tree) | |
389 | { | |
390 | g_return_if_fail(tree != NULL); | |
391 | ||
392 | if (g_atomic_int_dec_and_test(&tree->ref_count)) { | |
393 | q_tree_remove_all(tree); | |
394 | g_free(tree); | |
395 | } | |
396 | } | |
397 | ||
398 | /** | |
399 | * q_tree_destroy: | |
400 | * @tree: a #QTree | |
401 | * | |
402 | * Removes all keys and values from the #QTree and decreases its | |
403 | * reference count by one. If keys and/or values are dynamically | |
404 | * allocated, you should either free them first or create the #QTree | |
405 | * using q_tree_new_full(). In the latter case the destroy functions | |
406 | * you supplied will be called on all keys and values before destroying | |
407 | * the #QTree. | |
408 | */ | |
409 | void | |
410 | q_tree_destroy(QTree *tree) | |
411 | { | |
412 | g_return_if_fail(tree != NULL); | |
413 | ||
414 | q_tree_remove_all(tree); | |
415 | q_tree_unref(tree); | |
416 | } | |
417 | ||
418 | /** | |
419 | * q_tree_insert_node: | |
420 | * @tree: a #QTree | |
421 | * @key: the key to insert | |
422 | * @value: the value corresponding to the key | |
423 | * | |
424 | * Inserts a key/value pair into a #QTree. | |
425 | * | |
426 | * If the given key already exists in the #QTree its corresponding value | |
427 | * is set to the new value. If you supplied a @value_destroy_func when | |
428 | * creating the #QTree, the old value is freed using that function. If | |
429 | * you supplied a @key_destroy_func when creating the #QTree, the passed | |
430 | * key is freed using that function. | |
431 | * | |
432 | * The tree is automatically 'balanced' as new key/value pairs are added, | |
433 | * so that the distance from the root to every leaf is as small as possible. | |
434 | * The cost of maintaining a balanced tree while inserting new key/value | |
435 | * result in a O(n log(n)) operation where most of the other operations | |
436 | * are O(log(n)). | |
437 | * | |
438 | * Returns: (transfer none): the inserted (or set) node. | |
439 | * | |
440 | * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. | |
441 | */ | |
442 | static QTreeNode * | |
443 | q_tree_insert_node(QTree *tree, | |
444 | gpointer key, | |
445 | gpointer value) | |
446 | { | |
447 | QTreeNode *node; | |
448 | ||
449 | g_return_val_if_fail(tree != NULL, NULL); | |
450 | ||
451 | node = q_tree_insert_internal(tree, key, value, FALSE); | |
452 | ||
453 | #ifdef Q_TREE_DEBUG | |
454 | q_tree_node_check(tree->root); | |
455 | #endif | |
456 | ||
457 | return node; | |
458 | } | |
459 | ||
460 | /** | |
461 | * q_tree_insert: | |
462 | * @tree: a #QTree | |
463 | * @key: the key to insert | |
464 | * @value: the value corresponding to the key | |
465 | * | |
466 | * Inserts a key/value pair into a #QTree. | |
467 | * | |
468 | * Inserts a new key and value into a #QTree as q_tree_insert_node() does, | |
469 | * only this function does not return the inserted or set node. | |
470 | */ | |
471 | void | |
472 | q_tree_insert(QTree *tree, | |
473 | gpointer key, | |
474 | gpointer value) | |
475 | { | |
476 | q_tree_insert_node(tree, key, value); | |
477 | } | |
478 | ||
479 | /** | |
480 | * q_tree_replace_node: | |
481 | * @tree: a #QTree | |
482 | * @key: the key to insert | |
483 | * @value: the value corresponding to the key | |
484 | * | |
485 | * Inserts a new key and value into a #QTree similar to q_tree_insert_node(). | |
486 | * The difference is that if the key already exists in the #QTree, it gets | |
487 | * replaced by the new key. If you supplied a @value_destroy_func when | |
488 | * creating the #QTree, the old value is freed using that function. If you | |
489 | * supplied a @key_destroy_func when creating the #QTree, the old key is | |
490 | * freed using that function. | |
491 | * | |
492 | * The tree is automatically 'balanced' as new key/value pairs are added, | |
493 | * so that the distance from the root to every leaf is as small as possible. | |
494 | * | |
495 | * Returns: (transfer none): the inserted (or set) node. | |
496 | * | |
497 | * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. | |
498 | */ | |
499 | static QTreeNode * | |
500 | q_tree_replace_node(QTree *tree, | |
501 | gpointer key, | |
502 | gpointer value) | |
503 | { | |
504 | QTreeNode *node; | |
505 | ||
506 | g_return_val_if_fail(tree != NULL, NULL); | |
507 | ||
508 | node = q_tree_insert_internal(tree, key, value, TRUE); | |
509 | ||
510 | #ifdef Q_TREE_DEBUG | |
511 | q_tree_node_check(tree->root); | |
512 | #endif | |
513 | ||
514 | return node; | |
515 | } | |
516 | ||
517 | /** | |
518 | * q_tree_replace: | |
519 | * @tree: a #QTree | |
520 | * @key: the key to insert | |
521 | * @value: the value corresponding to the key | |
522 | * | |
523 | * Inserts a new key and value into a #QTree as q_tree_replace_node() does, | |
524 | * only this function does not return the inserted or set node. | |
525 | */ | |
526 | void | |
527 | q_tree_replace(QTree *tree, | |
528 | gpointer key, | |
529 | gpointer value) | |
530 | { | |
531 | q_tree_replace_node(tree, key, value); | |
532 | } | |
533 | ||
534 | /* internal insert routine */ | |
1ff4a81b | 535 | static QTreeNode * QEMU_DISABLE_CFI |
e3feb2cc EC |
536 | q_tree_insert_internal(QTree *tree, |
537 | gpointer key, | |
538 | gpointer value, | |
539 | gboolean replace) | |
540 | { | |
541 | QTreeNode *node, *retnode; | |
542 | QTreeNode *path[MAX_GTREE_HEIGHT]; | |
543 | int idx; | |
544 | ||
545 | g_return_val_if_fail(tree != NULL, NULL); | |
546 | ||
547 | if (!tree->root) { | |
548 | tree->root = q_tree_node_new(key, value); | |
549 | tree->nnodes++; | |
550 | return tree->root; | |
551 | } | |
552 | ||
553 | idx = 0; | |
554 | path[idx++] = NULL; | |
555 | node = tree->root; | |
556 | ||
557 | while (1) { | |
558 | int cmp = tree->key_compare(key, node->key, tree->key_compare_data); | |
559 | ||
560 | if (cmp == 0) { | |
561 | if (tree->value_destroy_func) { | |
562 | tree->value_destroy_func(node->value); | |
563 | } | |
564 | ||
565 | node->value = value; | |
566 | ||
567 | if (replace) { | |
568 | if (tree->key_destroy_func) { | |
569 | tree->key_destroy_func(node->key); | |
570 | } | |
571 | ||
572 | node->key = key; | |
573 | } else { | |
574 | /* free the passed key */ | |
575 | if (tree->key_destroy_func) { | |
576 | tree->key_destroy_func(key); | |
577 | } | |
578 | } | |
579 | ||
580 | return node; | |
581 | } else if (cmp < 0) { | |
582 | if (node->left_child) { | |
583 | path[idx++] = node; | |
584 | node = node->left; | |
585 | } else { | |
586 | QTreeNode *child = q_tree_node_new(key, value); | |
587 | ||
588 | child->left = node->left; | |
589 | child->right = node; | |
590 | node->left = child; | |
591 | node->left_child = TRUE; | |
592 | node->balance -= 1; | |
593 | ||
594 | tree->nnodes++; | |
595 | ||
596 | retnode = child; | |
597 | break; | |
598 | } | |
599 | } else { | |
600 | if (node->right_child) { | |
601 | path[idx++] = node; | |
602 | node = node->right; | |
603 | } else { | |
604 | QTreeNode *child = q_tree_node_new(key, value); | |
605 | ||
606 | child->right = node->right; | |
607 | child->left = node; | |
608 | node->right = child; | |
609 | node->right_child = TRUE; | |
610 | node->balance += 1; | |
611 | ||
612 | tree->nnodes++; | |
613 | ||
614 | retnode = child; | |
615 | break; | |
616 | } | |
617 | } | |
618 | } | |
619 | ||
620 | /* | |
621 | * Restore balance. This is the goodness of a non-recursive | |
622 | * implementation, when we are done with balancing we 'break' | |
623 | * the loop and we are done. | |
624 | */ | |
625 | while (1) { | |
626 | QTreeNode *bparent = path[--idx]; | |
627 | gboolean left_node = (bparent && node == bparent->left); | |
628 | g_assert(!bparent || bparent->left == node || bparent->right == node); | |
629 | ||
630 | if (node->balance < -1 || node->balance > 1) { | |
631 | node = q_tree_node_balance(node); | |
632 | if (bparent == NULL) { | |
633 | tree->root = node; | |
634 | } else if (left_node) { | |
635 | bparent->left = node; | |
636 | } else { | |
637 | bparent->right = node; | |
638 | } | |
639 | } | |
640 | ||
641 | if (node->balance == 0 || bparent == NULL) { | |
642 | break; | |
643 | } | |
644 | ||
645 | if (left_node) { | |
646 | bparent->balance -= 1; | |
647 | } else { | |
648 | bparent->balance += 1; | |
649 | } | |
650 | ||
651 | node = bparent; | |
652 | } | |
653 | ||
654 | return retnode; | |
655 | } | |
656 | ||
657 | /** | |
658 | * q_tree_remove: | |
659 | * @tree: a #QTree | |
660 | * @key: the key to remove | |
661 | * | |
662 | * Removes a key/value pair from a #QTree. | |
663 | * | |
664 | * If the #QTree was created using q_tree_new_full(), the key and value | |
665 | * are freed using the supplied destroy functions, otherwise you have to | |
666 | * make sure that any dynamically allocated values are freed yourself. | |
667 | * If the key does not exist in the #QTree, the function does nothing. | |
668 | * | |
669 | * The cost of maintaining a balanced tree while removing a key/value | |
670 | * result in a O(n log(n)) operation where most of the other operations | |
671 | * are O(log(n)). | |
672 | * | |
673 | * Returns: %TRUE if the key was found (prior to 2.8, this function | |
674 | * returned nothing) | |
675 | */ | |
676 | gboolean | |
677 | q_tree_remove(QTree *tree, | |
678 | gconstpointer key) | |
679 | { | |
680 | gboolean removed; | |
681 | ||
682 | g_return_val_if_fail(tree != NULL, FALSE); | |
683 | ||
684 | removed = q_tree_remove_internal(tree, key, FALSE); | |
685 | ||
686 | #ifdef Q_TREE_DEBUG | |
687 | q_tree_node_check(tree->root); | |
688 | #endif | |
689 | ||
690 | return removed; | |
691 | } | |
692 | ||
693 | /** | |
694 | * q_tree_steal: | |
695 | * @tree: a #QTree | |
696 | * @key: the key to remove | |
697 | * | |
698 | * Removes a key and its associated value from a #QTree without calling | |
699 | * the key and value destroy functions. | |
700 | * | |
701 | * If the key does not exist in the #QTree, the function does nothing. | |
702 | * | |
703 | * Returns: %TRUE if the key was found (prior to 2.8, this function | |
704 | * returned nothing) | |
705 | */ | |
706 | gboolean | |
707 | q_tree_steal(QTree *tree, | |
708 | gconstpointer key) | |
709 | { | |
710 | gboolean removed; | |
711 | ||
712 | g_return_val_if_fail(tree != NULL, FALSE); | |
713 | ||
714 | removed = q_tree_remove_internal(tree, key, TRUE); | |
715 | ||
716 | #ifdef Q_TREE_DEBUG | |
717 | q_tree_node_check(tree->root); | |
718 | #endif | |
719 | ||
720 | return removed; | |
721 | } | |
722 | ||
723 | /* internal remove routine */ | |
1ff4a81b | 724 | static gboolean QEMU_DISABLE_CFI |
e3feb2cc EC |
725 | q_tree_remove_internal(QTree *tree, |
726 | gconstpointer key, | |
727 | gboolean steal) | |
728 | { | |
729 | QTreeNode *node, *parent, *balance; | |
730 | QTreeNode *path[MAX_GTREE_HEIGHT]; | |
731 | int idx; | |
732 | gboolean left_node; | |
733 | ||
734 | g_return_val_if_fail(tree != NULL, FALSE); | |
735 | ||
736 | if (!tree->root) { | |
737 | return FALSE; | |
738 | } | |
739 | ||
740 | idx = 0; | |
741 | path[idx++] = NULL; | |
742 | node = tree->root; | |
743 | ||
744 | while (1) { | |
745 | int cmp = tree->key_compare(key, node->key, tree->key_compare_data); | |
746 | ||
747 | if (cmp == 0) { | |
748 | break; | |
749 | } else if (cmp < 0) { | |
750 | if (!node->left_child) { | |
751 | return FALSE; | |
752 | } | |
753 | ||
754 | path[idx++] = node; | |
755 | node = node->left; | |
756 | } else { | |
757 | if (!node->right_child) { | |
758 | return FALSE; | |
759 | } | |
760 | ||
761 | path[idx++] = node; | |
762 | node = node->right; | |
763 | } | |
764 | } | |
765 | ||
766 | /* | |
767 | * The following code is almost equal to q_tree_remove_node, | |
768 | * except that we do not have to call q_tree_node_parent. | |
769 | */ | |
770 | balance = parent = path[--idx]; | |
771 | g_assert(!parent || parent->left == node || parent->right == node); | |
772 | left_node = (parent && node == parent->left); | |
773 | ||
774 | if (!node->left_child) { | |
775 | if (!node->right_child) { | |
776 | if (!parent) { | |
777 | tree->root = NULL; | |
778 | } else if (left_node) { | |
779 | parent->left_child = FALSE; | |
780 | parent->left = node->left; | |
781 | parent->balance += 1; | |
782 | } else { | |
783 | parent->right_child = FALSE; | |
784 | parent->right = node->right; | |
785 | parent->balance -= 1; | |
786 | } | |
787 | } else { | |
788 | /* node has a right child */ | |
789 | QTreeNode *tmp = q_tree_node_next(node); | |
790 | tmp->left = node->left; | |
791 | ||
792 | if (!parent) { | |
793 | tree->root = node->right; | |
794 | } else if (left_node) { | |
795 | parent->left = node->right; | |
796 | parent->balance += 1; | |
797 | } else { | |
798 | parent->right = node->right; | |
799 | parent->balance -= 1; | |
800 | } | |
801 | } | |
802 | } else { | |
803 | /* node has a left child */ | |
804 | if (!node->right_child) { | |
805 | QTreeNode *tmp = q_tree_node_previous(node); | |
806 | tmp->right = node->right; | |
807 | ||
808 | if (parent == NULL) { | |
809 | tree->root = node->left; | |
810 | } else if (left_node) { | |
811 | parent->left = node->left; | |
812 | parent->balance += 1; | |
813 | } else { | |
814 | parent->right = node->left; | |
815 | parent->balance -= 1; | |
816 | } | |
817 | } else { | |
818 | /* node has a both children (pant, pant!) */ | |
819 | QTreeNode *prev = node->left; | |
820 | QTreeNode *next = node->right; | |
821 | QTreeNode *nextp = node; | |
822 | int old_idx = idx + 1; | |
823 | idx++; | |
824 | ||
825 | /* path[idx] == parent */ | |
826 | /* find the immediately next node (and its parent) */ | |
827 | while (next->left_child) { | |
828 | path[++idx] = nextp = next; | |
829 | next = next->left; | |
830 | } | |
831 | ||
832 | path[old_idx] = next; | |
833 | balance = path[idx]; | |
834 | ||
835 | /* remove 'next' from the tree */ | |
836 | if (nextp != node) { | |
837 | if (next->right_child) { | |
838 | nextp->left = next->right; | |
839 | } else { | |
840 | nextp->left_child = FALSE; | |
841 | } | |
842 | nextp->balance += 1; | |
843 | ||
844 | next->right_child = TRUE; | |
845 | next->right = node->right; | |
846 | } else { | |
847 | node->balance -= 1; | |
848 | } | |
849 | ||
850 | /* set the prev to point to the right place */ | |
851 | while (prev->right_child) { | |
852 | prev = prev->right; | |
853 | } | |
854 | prev->right = next; | |
855 | ||
856 | /* prepare 'next' to replace 'node' */ | |
857 | next->left_child = TRUE; | |
858 | next->left = node->left; | |
859 | next->balance = node->balance; | |
860 | ||
861 | if (!parent) { | |
862 | tree->root = next; | |
863 | } else if (left_node) { | |
864 | parent->left = next; | |
865 | } else { | |
866 | parent->right = next; | |
867 | } | |
868 | } | |
869 | } | |
870 | ||
871 | /* restore balance */ | |
872 | if (balance) { | |
873 | while (1) { | |
874 | QTreeNode *bparent = path[--idx]; | |
875 | g_assert(!bparent || | |
876 | bparent->left == balance || | |
877 | bparent->right == balance); | |
878 | left_node = (bparent && balance == bparent->left); | |
879 | ||
880 | if (balance->balance < -1 || balance->balance > 1) { | |
881 | balance = q_tree_node_balance(balance); | |
882 | if (!bparent) { | |
883 | tree->root = balance; | |
884 | } else if (left_node) { | |
885 | bparent->left = balance; | |
886 | } else { | |
887 | bparent->right = balance; | |
888 | } | |
889 | } | |
890 | ||
891 | if (balance->balance != 0 || !bparent) { | |
892 | break; | |
893 | } | |
894 | ||
895 | if (left_node) { | |
896 | bparent->balance += 1; | |
897 | } else { | |
898 | bparent->balance -= 1; | |
899 | } | |
900 | ||
901 | balance = bparent; | |
902 | } | |
903 | } | |
904 | ||
905 | if (!steal) { | |
906 | if (tree->key_destroy_func) { | |
907 | tree->key_destroy_func(node->key); | |
908 | } | |
909 | if (tree->value_destroy_func) { | |
910 | tree->value_destroy_func(node->value); | |
911 | } | |
912 | } | |
913 | ||
914 | g_free(node); | |
915 | ||
916 | tree->nnodes--; | |
917 | ||
918 | return TRUE; | |
919 | } | |
920 | ||
921 | /** | |
922 | * q_tree_lookup_node: | |
923 | * @tree: a #QTree | |
924 | * @key: the key to look up | |
925 | * | |
926 | * Gets the tree node corresponding to the given key. Since a #QTree is | |
927 | * automatically balanced as key/value pairs are added, key lookup | |
928 | * is O(log n) (where n is the number of key/value pairs in the tree). | |
929 | * | |
930 | * Returns: (nullable) (transfer none): the tree node corresponding to | |
931 | * the key, or %NULL if the key was not found | |
932 | * | |
933 | * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. | |
934 | */ | |
935 | static QTreeNode * | |
936 | q_tree_lookup_node(QTree *tree, | |
937 | gconstpointer key) | |
938 | { | |
939 | g_return_val_if_fail(tree != NULL, NULL); | |
940 | ||
941 | return q_tree_find_node(tree, key); | |
942 | } | |
943 | ||
944 | /** | |
945 | * q_tree_lookup: | |
946 | * @tree: a #QTree | |
947 | * @key: the key to look up | |
948 | * | |
949 | * Gets the value corresponding to the given key. Since a #QTree is | |
950 | * automatically balanced as key/value pairs are added, key lookup | |
951 | * is O(log n) (where n is the number of key/value pairs in the tree). | |
952 | * | |
953 | * Returns: the value corresponding to the key, or %NULL | |
954 | * if the key was not found | |
955 | */ | |
956 | gpointer | |
957 | q_tree_lookup(QTree *tree, | |
958 | gconstpointer key) | |
959 | { | |
960 | QTreeNode *node; | |
961 | ||
962 | node = q_tree_lookup_node(tree, key); | |
963 | ||
964 | return node ? node->value : NULL; | |
965 | } | |
966 | ||
967 | /** | |
968 | * q_tree_lookup_extended: | |
969 | * @tree: a #QTree | |
970 | * @lookup_key: the key to look up | |
971 | * @orig_key: (out) (optional) (nullable): returns the original key | |
972 | * @value: (out) (optional) (nullable): returns the value associated with | |
973 | * the key | |
974 | * | |
975 | * Looks up a key in the #QTree, returning the original key and the | |
976 | * associated value. This is useful if you need to free the memory | |
977 | * allocated for the original key, for example before calling | |
978 | * q_tree_remove(). | |
979 | * | |
980 | * Returns: %TRUE if the key was found in the #QTree | |
981 | */ | |
982 | gboolean | |
983 | q_tree_lookup_extended(QTree *tree, | |
984 | gconstpointer lookup_key, | |
985 | gpointer *orig_key, | |
986 | gpointer *value) | |
987 | { | |
988 | QTreeNode *node; | |
989 | ||
990 | g_return_val_if_fail(tree != NULL, FALSE); | |
991 | ||
992 | node = q_tree_find_node(tree, lookup_key); | |
993 | ||
994 | if (node) { | |
995 | if (orig_key) { | |
996 | *orig_key = node->key; | |
997 | } | |
998 | if (value) { | |
999 | *value = node->value; | |
1000 | } | |
1001 | return TRUE; | |
1002 | } else { | |
1003 | return FALSE; | |
1004 | } | |
1005 | } | |
1006 | ||
1007 | /** | |
1008 | * q_tree_foreach: | |
1009 | * @tree: a #QTree | |
1010 | * @func: the function to call for each node visited. | |
1011 | * If this function returns %TRUE, the traversal is stopped. | |
1012 | * @user_data: user data to pass to the function | |
1013 | * | |
1014 | * Calls the given function for each of the key/value pairs in the #QTree. | |
1015 | * The function is passed the key and value of each pair, and the given | |
1016 | * @data parameter. The tree is traversed in sorted order. | |
1017 | * | |
1018 | * The tree may not be modified while iterating over it (you can't | |
1019 | * add/remove items). To remove all items matching a predicate, you need | |
1020 | * to add each item to a list in your #GTraverseFunc as you walk over | |
1021 | * the tree, then walk the list and remove each item. | |
1022 | */ | |
1023 | void | |
1024 | q_tree_foreach(QTree *tree, | |
1025 | GTraverseFunc func, | |
1026 | gpointer user_data) | |
1027 | { | |
1028 | QTreeNode *node; | |
1029 | ||
1030 | g_return_if_fail(tree != NULL); | |
1031 | ||
1032 | if (!tree->root) { | |
1033 | return; | |
1034 | } | |
1035 | ||
1036 | node = q_tree_node_first(tree); | |
1037 | ||
1038 | while (node) { | |
1039 | if ((*func)(node->key, node->value, user_data)) { | |
1040 | break; | |
1041 | } | |
1042 | ||
1043 | node = q_tree_node_next(node); | |
1044 | } | |
1045 | } | |
1046 | ||
1047 | /** | |
1048 | * q_tree_search_node: | |
1049 | * @tree: a #QTree | |
1050 | * @search_func: a function used to search the #QTree | |
1051 | * @user_data: the data passed as the second argument to @search_func | |
1052 | * | |
1053 | * Searches a #QTree using @search_func. | |
1054 | * | |
1055 | * The @search_func is called with a pointer to the key of a key/value | |
1056 | * pair in the tree, and the passed in @user_data. If @search_func returns | |
1057 | * 0 for a key/value pair, then the corresponding node is returned as | |
1058 | * the result of q_tree_search(). If @search_func returns -1, searching | |
1059 | * will proceed among the key/value pairs that have a smaller key; if | |
1060 | * @search_func returns 1, searching will proceed among the key/value | |
1061 | * pairs that have a larger key. | |
1062 | * | |
1063 | * Returns: (nullable) (transfer none): the node corresponding to the | |
1064 | * found key, or %NULL if the key was not found | |
1065 | * | |
1066 | * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API. | |
1067 | */ | |
1068 | static QTreeNode * | |
1069 | q_tree_search_node(QTree *tree, | |
1070 | GCompareFunc search_func, | |
1071 | gconstpointer user_data) | |
1072 | { | |
1073 | g_return_val_if_fail(tree != NULL, NULL); | |
1074 | ||
1075 | if (!tree->root) { | |
1076 | return NULL; | |
1077 | } | |
1078 | ||
1079 | return q_tree_node_search(tree->root, search_func, user_data); | |
1080 | } | |
1081 | ||
1082 | /** | |
1083 | * q_tree_search: | |
1084 | * @tree: a #QTree | |
1085 | * @search_func: a function used to search the #QTree | |
1086 | * @user_data: the data passed as the second argument to @search_func | |
1087 | * | |
1088 | * Searches a #QTree using @search_func. | |
1089 | * | |
1090 | * The @search_func is called with a pointer to the key of a key/value | |
1091 | * pair in the tree, and the passed in @user_data. If @search_func returns | |
1092 | * 0 for a key/value pair, then the corresponding value is returned as | |
1093 | * the result of q_tree_search(). If @search_func returns -1, searching | |
1094 | * will proceed among the key/value pairs that have a smaller key; if | |
1095 | * @search_func returns 1, searching will proceed among the key/value | |
1096 | * pairs that have a larger key. | |
1097 | * | |
1098 | * Returns: the value corresponding to the found key, or %NULL | |
1099 | * if the key was not found | |
1100 | */ | |
1101 | gpointer | |
1102 | q_tree_search(QTree *tree, | |
1103 | GCompareFunc search_func, | |
1104 | gconstpointer user_data) | |
1105 | { | |
1106 | QTreeNode *node; | |
1107 | ||
1108 | node = q_tree_search_node(tree, search_func, user_data); | |
1109 | ||
1110 | return node ? node->value : NULL; | |
1111 | } | |
1112 | ||
1113 | /** | |
1114 | * q_tree_height: | |
1115 | * @tree: a #QTree | |
1116 | * | |
1117 | * Gets the height of a #QTree. | |
1118 | * | |
1119 | * If the #QTree contains no nodes, the height is 0. | |
1120 | * If the #QTree contains only one root node the height is 1. | |
1121 | * If the root node has children the height is 2, etc. | |
1122 | * | |
1123 | * Returns: the height of @tree | |
1124 | */ | |
1125 | gint | |
1126 | q_tree_height(QTree *tree) | |
1127 | { | |
1128 | QTreeNode *node; | |
1129 | gint height; | |
1130 | ||
1131 | g_return_val_if_fail(tree != NULL, 0); | |
1132 | ||
1133 | if (!tree->root) { | |
1134 | return 0; | |
1135 | } | |
1136 | ||
1137 | height = 0; | |
1138 | node = tree->root; | |
1139 | ||
1140 | while (1) { | |
1141 | height += 1 + MAX(node->balance, 0); | |
1142 | ||
1143 | if (!node->left_child) { | |
1144 | return height; | |
1145 | } | |
1146 | ||
1147 | node = node->left; | |
1148 | } | |
1149 | } | |
1150 | ||
1151 | /** | |
1152 | * q_tree_nnodes: | |
1153 | * @tree: a #QTree | |
1154 | * | |
1155 | * Gets the number of nodes in a #QTree. | |
1156 | * | |
1157 | * Returns: the number of nodes in @tree | |
1158 | */ | |
1159 | gint | |
1160 | q_tree_nnodes(QTree *tree) | |
1161 | { | |
1162 | g_return_val_if_fail(tree != NULL, 0); | |
1163 | ||
1164 | return tree->nnodes; | |
1165 | } | |
1166 | ||
1167 | static QTreeNode * | |
1168 | q_tree_node_balance(QTreeNode *node) | |
1169 | { | |
1170 | if (node->balance < -1) { | |
1171 | if (node->left->balance > 0) { | |
1172 | node->left = q_tree_node_rotate_left(node->left); | |
1173 | } | |
1174 | node = q_tree_node_rotate_right(node); | |
1175 | } else if (node->balance > 1) { | |
1176 | if (node->right->balance < 0) { | |
1177 | node->right = q_tree_node_rotate_right(node->right); | |
1178 | } | |
1179 | node = q_tree_node_rotate_left(node); | |
1180 | } | |
1181 | ||
1182 | return node; | |
1183 | } | |
1184 | ||
1ff4a81b | 1185 | static QTreeNode * QEMU_DISABLE_CFI |
e3feb2cc EC |
1186 | q_tree_find_node(QTree *tree, |
1187 | gconstpointer key) | |
1188 | { | |
1189 | QTreeNode *node; | |
1190 | gint cmp; | |
1191 | ||
1192 | node = tree->root; | |
1193 | if (!node) { | |
1194 | return NULL; | |
1195 | } | |
1196 | ||
1197 | while (1) { | |
1198 | cmp = tree->key_compare(key, node->key, tree->key_compare_data); | |
1199 | if (cmp == 0) { | |
1200 | return node; | |
1201 | } else if (cmp < 0) { | |
1202 | if (!node->left_child) { | |
1203 | return NULL; | |
1204 | } | |
1205 | ||
1206 | node = node->left; | |
1207 | } else { | |
1208 | if (!node->right_child) { | |
1209 | return NULL; | |
1210 | } | |
1211 | ||
1212 | node = node->right; | |
1213 | } | |
1214 | } | |
1215 | } | |
1216 | ||
1217 | static QTreeNode * | |
1218 | q_tree_node_search(QTreeNode *node, | |
1219 | GCompareFunc search_func, | |
1220 | gconstpointer data) | |
1221 | { | |
1222 | gint dir; | |
1223 | ||
1224 | if (!node) { | |
1225 | return NULL; | |
1226 | } | |
1227 | ||
1228 | while (1) { | |
1229 | dir = (*search_func)(node->key, data); | |
1230 | if (dir == 0) { | |
1231 | return node; | |
1232 | } else if (dir < 0) { | |
1233 | if (!node->left_child) { | |
1234 | return NULL; | |
1235 | } | |
1236 | ||
1237 | node = node->left; | |
1238 | } else { | |
1239 | if (!node->right_child) { | |
1240 | return NULL; | |
1241 | } | |
1242 | ||
1243 | node = node->right; | |
1244 | } | |
1245 | } | |
1246 | } | |
1247 | ||
1248 | static QTreeNode * | |
1249 | q_tree_node_rotate_left(QTreeNode *node) | |
1250 | { | |
1251 | QTreeNode *right; | |
1252 | gint a_bal; | |
1253 | gint b_bal; | |
1254 | ||
1255 | right = node->right; | |
1256 | ||
1257 | if (right->left_child) { | |
1258 | node->right = right->left; | |
1259 | } else { | |
1260 | node->right_child = FALSE; | |
1261 | right->left_child = TRUE; | |
1262 | } | |
1263 | right->left = node; | |
1264 | ||
1265 | a_bal = node->balance; | |
1266 | b_bal = right->balance; | |
1267 | ||
1268 | if (b_bal <= 0) { | |
1269 | if (a_bal >= 1) { | |
1270 | right->balance = b_bal - 1; | |
1271 | } else { | |
1272 | right->balance = a_bal + b_bal - 2; | |
1273 | } | |
1274 | node->balance = a_bal - 1; | |
1275 | } else { | |
1276 | if (a_bal <= b_bal) { | |
1277 | right->balance = a_bal - 2; | |
1278 | } else { | |
1279 | right->balance = b_bal - 1; | |
1280 | } | |
1281 | node->balance = a_bal - b_bal - 1; | |
1282 | } | |
1283 | ||
1284 | return right; | |
1285 | } | |
1286 | ||
1287 | static QTreeNode * | |
1288 | q_tree_node_rotate_right(QTreeNode *node) | |
1289 | { | |
1290 | QTreeNode *left; | |
1291 | gint a_bal; | |
1292 | gint b_bal; | |
1293 | ||
1294 | left = node->left; | |
1295 | ||
1296 | if (left->right_child) { | |
1297 | node->left = left->right; | |
1298 | } else { | |
1299 | node->left_child = FALSE; | |
1300 | left->right_child = TRUE; | |
1301 | } | |
1302 | left->right = node; | |
1303 | ||
1304 | a_bal = node->balance; | |
1305 | b_bal = left->balance; | |
1306 | ||
1307 | if (b_bal <= 0) { | |
1308 | if (b_bal > a_bal) { | |
1309 | left->balance = b_bal + 1; | |
1310 | } else { | |
1311 | left->balance = a_bal + 2; | |
1312 | } | |
1313 | node->balance = a_bal - b_bal + 1; | |
1314 | } else { | |
1315 | if (a_bal <= -1) { | |
1316 | left->balance = b_bal + 1; | |
1317 | } else { | |
1318 | left->balance = a_bal + b_bal + 2; | |
1319 | } | |
1320 | node->balance = a_bal + 1; | |
1321 | } | |
1322 | ||
1323 | return left; | |
1324 | } | |
1325 | ||
1326 | #ifdef Q_TREE_DEBUG | |
1327 | static gint | |
1328 | q_tree_node_height(QTreeNode *node) | |
1329 | { | |
1330 | gint left_height; | |
1331 | gint right_height; | |
1332 | ||
1333 | if (node) { | |
1334 | left_height = 0; | |
1335 | right_height = 0; | |
1336 | ||
1337 | if (node->left_child) { | |
1338 | left_height = q_tree_node_height(node->left); | |
1339 | } | |
1340 | ||
1341 | if (node->right_child) { | |
1342 | right_height = q_tree_node_height(node->right); | |
1343 | } | |
1344 | ||
1345 | return MAX(left_height, right_height) + 1; | |
1346 | } | |
1347 | ||
1348 | return 0; | |
1349 | } | |
1350 | ||
1351 | static void q_tree_node_check(QTreeNode *node) | |
1352 | { | |
1353 | gint left_height; | |
1354 | gint right_height; | |
1355 | gint balance; | |
1356 | QTreeNode *tmp; | |
1357 | ||
1358 | if (node) { | |
1359 | if (node->left_child) { | |
1360 | tmp = q_tree_node_previous(node); | |
1361 | g_assert(tmp->right == node); | |
1362 | } | |
1363 | ||
1364 | if (node->right_child) { | |
1365 | tmp = q_tree_node_next(node); | |
1366 | g_assert(tmp->left == node); | |
1367 | } | |
1368 | ||
1369 | left_height = 0; | |
1370 | right_height = 0; | |
1371 | ||
1372 | if (node->left_child) { | |
1373 | left_height = q_tree_node_height(node->left); | |
1374 | } | |
1375 | if (node->right_child) { | |
1376 | right_height = q_tree_node_height(node->right); | |
1377 | } | |
1378 | ||
1379 | balance = right_height - left_height; | |
1380 | g_assert(balance == node->balance); | |
1381 | ||
1382 | if (node->left_child) { | |
1383 | q_tree_node_check(node->left); | |
1384 | } | |
1385 | if (node->right_child) { | |
1386 | q_tree_node_check(node->right); | |
1387 | } | |
1388 | } | |
1389 | } | |
1390 | #endif |