Branch data Line data Source code
1 : : /* GLIB - Library of useful routines for C programming
2 : : * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
3 : : *
4 : : * SPDX-License-Identifier: LGPL-2.1-or-later
5 : : *
6 : : * This library is free software; you can redistribute it and/or
7 : : * modify it under the terms of the GNU Lesser General Public
8 : : * License as published by the Free Software Foundation; either
9 : : * version 2.1 of the License, or (at your option) any later version.
10 : : *
11 : : * This library is distributed in the hope that it will be useful,
12 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 : : * Lesser General Public License for more details.
15 : : *
16 : : * You should have received a copy of the GNU Lesser General Public
17 : : * License along with this library; if not, see <http://www.gnu.org/licenses/>.
18 : : */
19 : :
20 : : /*
21 : : * Modified by the GLib Team and others 1997-2000. See the AUTHORS
22 : : * file for a list of people on the GLib Team. See the ChangeLog
23 : : * files for a list of changes. These files are distributed with
24 : : * GLib at ftp://ftp.gtk.org/pub/gtk/.
25 : : */
26 : :
27 : : /*
28 : : * MT safe
29 : : */
30 : :
31 : : #include "config.h"
32 : :
33 : : #include "gtree.h"
34 : :
35 : : #include "gatomic.h"
36 : : #include "gtestutils.h"
37 : : #include "gslice.h"
38 : :
39 : : #define MAX_GTREE_HEIGHT 40
40 : : /* G_MAXUINT nodes will be covered by tree height of log2(G_MAXUINT) + 2. */
41 : : G_STATIC_ASSERT ((G_GUINT64_CONSTANT (1) << (MAX_GTREE_HEIGHT - 2)) >= G_MAXUINT);
42 : :
43 : : /**
44 : : * GTree:
45 : : *
46 : : * The GTree struct is an opaque data structure representing a
47 : : * [balanced binary tree][glib-Balanced-Binary-Trees]. It should be
48 : : * accessed only by using the following functions.
49 : : */
50 : : struct _GTree
51 : : {
52 : : GTreeNode *root;
53 : : GCompareDataFunc key_compare;
54 : : GDestroyNotify key_destroy_func;
55 : : GDestroyNotify value_destroy_func;
56 : : gpointer key_compare_data;
57 : : guint nnodes;
58 : : gint ref_count;
59 : : };
60 : :
61 : : struct _GTreeNode
62 : : {
63 : : gpointer key; /* key for this node */
64 : : gpointer value; /* value stored at this node */
65 : : GTreeNode *left; /* left subtree */
66 : : GTreeNode *right; /* right subtree */
67 : : gint8 balance; /* height (right) - height (left) */
68 : : guint8 left_child;
69 : : guint8 right_child;
70 : : };
71 : :
72 : :
73 : : static GTreeNode* g_tree_node_new (gpointer key,
74 : : gpointer value);
75 : : static GTreeNode *g_tree_insert_internal (GTree *tree,
76 : : gpointer key,
77 : : gpointer value,
78 : : gboolean replace,
79 : : gboolean null_ret_ok);
80 : : static gboolean g_tree_remove_internal (GTree *tree,
81 : : gconstpointer key,
82 : : gboolean steal);
83 : : static GTreeNode* g_tree_node_balance (GTreeNode *node);
84 : : static GTreeNode *g_tree_find_node (GTree *tree,
85 : : gconstpointer key);
86 : : static gint g_tree_node_pre_order (GTreeNode *node,
87 : : GTraverseFunc traverse_func,
88 : : gpointer data);
89 : : static gint g_tree_node_in_order (GTreeNode *node,
90 : : GTraverseFunc traverse_func,
91 : : gpointer data);
92 : : static gint g_tree_node_post_order (GTreeNode *node,
93 : : GTraverseFunc traverse_func,
94 : : gpointer data);
95 : : static GTreeNode *g_tree_node_search (GTreeNode *node,
96 : : GCompareFunc search_func,
97 : : gconstpointer data);
98 : : static GTreeNode* g_tree_node_rotate_left (GTreeNode *node);
99 : : static GTreeNode* g_tree_node_rotate_right (GTreeNode *node);
100 : : #ifdef G_TREE_DEBUG
101 : : static void g_tree_node_check (GTreeNode *node);
102 : : #endif
103 : :
104 : :
105 : : static GTreeNode*
106 : 606 : g_tree_node_new (gpointer key,
107 : : gpointer value)
108 : : {
109 : 606 : GTreeNode *node = g_slice_new (GTreeNode);
110 : :
111 : 606 : node->balance = 0;
112 : 606 : node->left = NULL;
113 : 606 : node->right = NULL;
114 : 606 : node->left_child = FALSE;
115 : 606 : node->right_child = FALSE;
116 : 606 : node->key = key;
117 : 606 : node->value = value;
118 : :
119 : 606 : return node;
120 : : }
121 : :
122 : : /**
123 : : * g_tree_new: (constructor)
124 : : * @key_compare_func: the function used to order the nodes in the #GTree.
125 : : * It should return values similar to the standard strcmp() function -
126 : : * 0 if the two arguments are equal, a negative value if the first argument
127 : : * comes before the second, or a positive value if the first argument comes
128 : : * after the second.
129 : : *
130 : : * Creates a new #GTree.
131 : : *
132 : : * Returns: a newly allocated #GTree
133 : : */
134 : : GTree *
135 : 8 : g_tree_new (GCompareFunc key_compare_func)
136 : : {
137 : 8 : g_return_val_if_fail (key_compare_func != NULL, NULL);
138 : :
139 : 8 : return g_tree_new_full ((GCompareDataFunc) key_compare_func, NULL,
140 : : NULL, NULL);
141 : : }
142 : :
143 : : /**
144 : : * g_tree_new_with_data:
145 : : * @key_compare_func: qsort()-style comparison function
146 : : * @key_compare_data: data to pass to comparison function
147 : : *
148 : : * Creates a new #GTree with a comparison function that accepts user data.
149 : : * See g_tree_new() for more details.
150 : : *
151 : : * Returns: a newly allocated #GTree
152 : : */
153 : : GTree *
154 : 1 : g_tree_new_with_data (GCompareDataFunc key_compare_func,
155 : : gpointer key_compare_data)
156 : : {
157 : 1 : g_return_val_if_fail (key_compare_func != NULL, NULL);
158 : :
159 : 1 : return g_tree_new_full (key_compare_func, key_compare_data,
160 : : NULL, NULL);
161 : : }
162 : :
163 : : /**
164 : : * g_tree_new_full:
165 : : * @key_compare_func: qsort()-style comparison function
166 : : * @key_compare_data: data to pass to comparison function
167 : : * @key_destroy_func: a function to free the memory allocated for the key
168 : : * used when removing the entry from the #GTree or %NULL if you don't
169 : : * want to supply such a function
170 : : * @value_destroy_func: a function to free the memory allocated for the
171 : : * value used when removing the entry from the #GTree or %NULL if you
172 : : * don't want to supply such a function
173 : : *
174 : : * Creates a new #GTree like g_tree_new() and allows to specify functions
175 : : * to free the memory allocated for the key and value that get called when
176 : : * removing the entry from the #GTree.
177 : : *
178 : : * Returns: a newly allocated #GTree
179 : : */
180 : : GTree *
181 : 38 : g_tree_new_full (GCompareDataFunc key_compare_func,
182 : : gpointer key_compare_data,
183 : : GDestroyNotify key_destroy_func,
184 : : GDestroyNotify value_destroy_func)
185 : : {
186 : : GTree *tree;
187 : :
188 : 38 : g_return_val_if_fail (key_compare_func != NULL, NULL);
189 : :
190 : 38 : tree = g_slice_new (GTree);
191 : 38 : tree->root = NULL;
192 : 38 : tree->key_compare = key_compare_func;
193 : 38 : tree->key_destroy_func = key_destroy_func;
194 : 38 : tree->value_destroy_func = value_destroy_func;
195 : 38 : tree->key_compare_data = key_compare_data;
196 : 38 : tree->nnodes = 0;
197 : 38 : tree->ref_count = 1;
198 : :
199 : 38 : return tree;
200 : : }
201 : :
202 : : /**
203 : : * g_tree_node_first:
204 : : * @tree: a #GTree
205 : : *
206 : : * Returns the first in-order node of the tree, or %NULL
207 : : * for an empty tree.
208 : : *
209 : : * Returns: (nullable) (transfer none): the first node in the tree
210 : : *
211 : : * Since: 2.68
212 : : */
213 : : GTreeNode *
214 : 141 : g_tree_node_first (GTree *tree)
215 : : {
216 : : GTreeNode *tmp;
217 : :
218 : 141 : g_return_val_if_fail (tree != NULL, NULL);
219 : :
220 : 141 : if (!tree->root)
221 : 17 : return NULL;
222 : :
223 : 124 : tmp = tree->root;
224 : :
225 : 390 : while (tmp->left_child)
226 : 266 : tmp = tmp->left;
227 : :
228 : 124 : return tmp;
229 : : }
230 : :
231 : : /**
232 : : * g_tree_node_last:
233 : : * @tree: a #GTree
234 : : *
235 : : * Returns the last in-order node of the tree, or %NULL
236 : : * for an empty tree.
237 : : *
238 : : * Returns: (nullable) (transfer none): the last node in the tree
239 : : *
240 : : * Since: 2.68
241 : : */
242 : : GTreeNode *
243 : 66 : g_tree_node_last (GTree *tree)
244 : : {
245 : : GTreeNode *tmp;
246 : :
247 : 66 : g_return_val_if_fail (tree != NULL, NULL);
248 : :
249 : 66 : if (!tree->root)
250 : 0 : return NULL;
251 : :
252 : 66 : tmp = tree->root;
253 : :
254 : 242 : while (tmp->right_child)
255 : 176 : tmp = tmp->right;
256 : :
257 : 66 : return tmp;
258 : : }
259 : :
260 : : /**
261 : : * g_tree_node_previous
262 : : * @node: a #GTree node
263 : : *
264 : : * Returns the previous in-order node of the tree, or %NULL
265 : : * if the passed node was already the first one.
266 : : *
267 : : * Returns: (nullable) (transfer none): the previous node in the tree
268 : : *
269 : : * Since: 2.68
270 : : */
271 : : GTreeNode *
272 : 52 : g_tree_node_previous (GTreeNode *node)
273 : : {
274 : : GTreeNode *tmp;
275 : :
276 : 52 : g_return_val_if_fail (node != NULL, NULL);
277 : :
278 : 52 : tmp = node->left;
279 : :
280 : 52 : if (node->left_child)
281 : 25 : while (tmp->right_child)
282 : 10 : tmp = tmp->right;
283 : :
284 : 52 : return tmp;
285 : : }
286 : :
287 : : /**
288 : : * g_tree_node_next
289 : : * @node: a #GTree node
290 : : *
291 : : * Returns the next in-order node of the tree, or %NULL
292 : : * if the passed node was already the last one.
293 : : *
294 : : * Returns: (nullable) (transfer none): the next node in the tree
295 : : *
296 : : * Since: 2.68
297 : : */
298 : : GTreeNode *
299 : 1021 : g_tree_node_next (GTreeNode *node)
300 : : {
301 : : GTreeNode *tmp;
302 : :
303 : 1021 : g_return_val_if_fail (node != NULL, NULL);
304 : :
305 : 1021 : tmp = node->right;
306 : :
307 : 1021 : if (node->right_child)
308 : 839 : while (tmp->left_child)
309 : 359 : tmp = tmp->left;
310 : :
311 : 1021 : return tmp;
312 : : }
313 : :
314 : : /**
315 : : * g_tree_remove_all:
316 : : * @tree: a #GTree
317 : : *
318 : : * Removes all nodes from a #GTree and destroys their keys and values,
319 : : * then resets the #GTree’s root to %NULL.
320 : : *
321 : : * Since: 2.70
322 : : */
323 : : void
324 : 42 : g_tree_remove_all (GTree *tree)
325 : : {
326 : : GTreeNode *node;
327 : : GTreeNode *next;
328 : :
329 : 42 : g_return_if_fail (tree != NULL);
330 : :
331 : 42 : node = g_tree_node_first (tree);
332 : :
333 : 544 : while (node)
334 : : {
335 : 502 : next = g_tree_node_next (node);
336 : :
337 : 502 : if (tree->key_destroy_func)
338 : 130 : tree->key_destroy_func (node->key);
339 : 502 : if (tree->value_destroy_func)
340 : 130 : tree->value_destroy_func (node->value);
341 : 502 : g_slice_free (GTreeNode, node);
342 : :
343 : : #ifdef G_TREE_DEBUG
344 : : g_assert (tree->nnodes > 0);
345 : : tree->nnodes--;
346 : : #endif
347 : :
348 : 502 : node = next;
349 : : }
350 : :
351 : : #ifdef G_TREE_DEBUG
352 : : g_assert (tree->nnodes == 0);
353 : : #endif
354 : :
355 : 42 : tree->root = NULL;
356 : : #ifndef G_TREE_DEBUG
357 : 42 : tree->nnodes = 0;
358 : : #endif
359 : : }
360 : :
361 : : /**
362 : : * g_tree_ref:
363 : : * @tree: a #GTree
364 : : *
365 : : * Increments the reference count of @tree by one.
366 : : *
367 : : * It is safe to call this function from any thread.
368 : : *
369 : : * Returns: the passed in #GTree
370 : : *
371 : : * Since: 2.22
372 : : */
373 : : GTree *
374 : 2 : g_tree_ref (GTree *tree)
375 : : {
376 : 2 : g_return_val_if_fail (tree != NULL, NULL);
377 : :
378 : 2 : g_atomic_int_inc (&tree->ref_count);
379 : :
380 : 2 : return tree;
381 : : }
382 : :
383 : : /**
384 : : * g_tree_unref:
385 : : * @tree: a #GTree
386 : : *
387 : : * Decrements the reference count of @tree by one.
388 : : * If the reference count drops to 0, all keys and values will
389 : : * be destroyed (if destroy functions were specified) and all
390 : : * memory allocated by @tree will be released.
391 : : *
392 : : * It is safe to call this function from any thread.
393 : : *
394 : : * Since: 2.22
395 : : */
396 : : void
397 : 40 : g_tree_unref (GTree *tree)
398 : : {
399 : 40 : g_return_if_fail (tree != NULL);
400 : :
401 : 40 : if (g_atomic_int_dec_and_test (&tree->ref_count))
402 : : {
403 : 38 : g_tree_remove_all (tree);
404 : 38 : g_slice_free (GTree, tree);
405 : : }
406 : : }
407 : :
408 : : /**
409 : : * g_tree_destroy:
410 : : * @tree: a #GTree
411 : : *
412 : : * Removes all keys and values from the #GTree and decreases its
413 : : * reference count by one. If keys and/or values are dynamically
414 : : * allocated, you should either free them first or create the #GTree
415 : : * using g_tree_new_full(). In the latter case the destroy functions
416 : : * you supplied will be called on all keys and values before destroying
417 : : * the #GTree.
418 : : */
419 : : void
420 : 3 : g_tree_destroy (GTree *tree)
421 : : {
422 : 3 : g_return_if_fail (tree != NULL);
423 : :
424 : 3 : g_tree_remove_all (tree);
425 : 3 : g_tree_unref (tree);
426 : : }
427 : :
428 : : static GTreeNode *
429 : 613 : g_tree_insert_replace_node_internal (GTree *tree,
430 : : gpointer key,
431 : : gpointer value,
432 : : gboolean replace,
433 : : gboolean null_ret_ok)
434 : : {
435 : : GTreeNode *node;
436 : :
437 : 613 : g_return_val_if_fail (tree != NULL, NULL);
438 : :
439 : 613 : node = g_tree_insert_internal (tree, key, value, replace, null_ret_ok);
440 : :
441 : : #ifdef G_TREE_DEBUG
442 : : g_tree_node_check (tree->root);
443 : : #endif
444 : :
445 : 613 : return node;
446 : : }
447 : :
448 : : /**
449 : : * g_tree_insert_node:
450 : : * @tree: a #GTree
451 : : * @key: the key to insert
452 : : * @value: the value corresponding to the key
453 : : *
454 : : * Inserts a key/value pair into a #GTree.
455 : : *
456 : : * If the given key already exists in the #GTree its corresponding value
457 : : * is set to the new value. If you supplied a @value_destroy_func when
458 : : * creating the #GTree, the old value is freed using that function. If
459 : : * you supplied a @key_destroy_func when creating the #GTree, the passed
460 : : * key is freed using that function.
461 : : *
462 : : * The tree is automatically 'balanced' as new key/value pairs are added,
463 : : * so that the distance from the root to every leaf is as small as possible.
464 : : * The cost of maintaining a balanced tree while inserting new key/value
465 : : * result in a O(n log(n)) operation where most of the other operations
466 : : * are O(log(n)).
467 : : *
468 : : * Returns: (transfer none) (nullable): the inserted (or set) node or %NULL
469 : : * if insertion would overflow the tree node counter.
470 : : *
471 : : * Since: 2.68
472 : : */
473 : : GTreeNode *
474 : 63 : g_tree_insert_node (GTree *tree,
475 : : gpointer key,
476 : : gpointer value)
477 : : {
478 : 63 : return g_tree_insert_replace_node_internal (tree, key, value, FALSE, TRUE);
479 : : }
480 : :
481 : : /**
482 : : * g_tree_insert:
483 : : * @tree: a #GTree
484 : : * @key: the key to insert
485 : : * @value: the value corresponding to the key
486 : : *
487 : : * Inserts a key/value pair into a #GTree.
488 : : *
489 : : * Inserts a new key and value into a #GTree as g_tree_insert_node() does,
490 : : * only this function does not return the inserted or set node.
491 : : */
492 : : void
493 : 548 : g_tree_insert (GTree *tree,
494 : : gpointer key,
495 : : gpointer value)
496 : : {
497 : 548 : g_tree_insert_replace_node_internal (tree, key, value, FALSE, FALSE);
498 : 548 : }
499 : :
500 : : /**
501 : : * g_tree_replace_node:
502 : : * @tree: a #GTree
503 : : * @key: the key to insert
504 : : * @value: the value corresponding to the key
505 : : *
506 : : * Inserts a new key and value into a #GTree similar to g_tree_insert_node().
507 : : * The difference is that if the key already exists in the #GTree, it gets
508 : : * replaced by the new key. If you supplied a @value_destroy_func when
509 : : * creating the #GTree, the old value is freed using that function. If you
510 : : * supplied a @key_destroy_func when creating the #GTree, the old key is
511 : : * freed using that function.
512 : : *
513 : : * The tree is automatically 'balanced' as new key/value pairs are added,
514 : : * so that the distance from the root to every leaf is as small as possible.
515 : : *
516 : : * Returns: (transfer none) (nullable): the inserted (or set) node or %NULL
517 : : * if insertion would overflow the tree node counter.
518 : : *
519 : : * Since: 2.68
520 : : */
521 : : GTreeNode *
522 : 1 : g_tree_replace_node (GTree *tree,
523 : : gpointer key,
524 : : gpointer value)
525 : : {
526 : 1 : return g_tree_insert_replace_node_internal (tree, key, value, TRUE, TRUE);
527 : : }
528 : :
529 : : /**
530 : : * g_tree_replace:
531 : : * @tree: a #GTree
532 : : * @key: the key to insert
533 : : * @value: the value corresponding to the key
534 : : *
535 : : * Inserts a new key and value into a #GTree as g_tree_replace_node() does,
536 : : * only this function does not return the inserted or set node.
537 : : */
538 : : void
539 : 1 : g_tree_replace (GTree *tree,
540 : : gpointer key,
541 : : gpointer value)
542 : : {
543 : 1 : g_tree_insert_replace_node_internal (tree, key, value, TRUE, FALSE);
544 : 1 : }
545 : :
546 : : /* internal checked nnodes increment routine */
547 : : static gboolean
548 : 578 : g_tree_nnodes_inc_checked (GTree *tree, gboolean overflow_fatal)
549 : : {
550 : 578 : if (G_UNLIKELY (tree->nnodes == G_MAXUINT))
551 : : {
552 : 0 : if (overflow_fatal)
553 : : {
554 : 0 : g_error ("Incrementing GTree nnodes counter would overflow");
555 : : }
556 : :
557 : 0 : return FALSE;
558 : : }
559 : :
560 : 578 : tree->nnodes++;
561 : :
562 : 578 : return TRUE;
563 : : }
564 : :
565 : : /* internal insert routine */
566 : : static GTreeNode *
567 : 613 : g_tree_insert_internal (GTree *tree,
568 : : gpointer key,
569 : : gpointer value,
570 : : gboolean replace,
571 : : gboolean null_ret_ok)
572 : : {
573 : : GTreeNode *node, *retnode;
574 : : GTreeNode *path[MAX_GTREE_HEIGHT];
575 : : int idx;
576 : :
577 : 613 : g_return_val_if_fail (tree != NULL, NULL);
578 : :
579 : 613 : if (!tree->root)
580 : : {
581 : 28 : tree->root = g_tree_node_new (key, value);
582 : :
583 : : #ifdef G_TREE_DEBUG
584 : : g_assert (tree->nnodes == 0);
585 : : #endif
586 : 28 : tree->nnodes++;
587 : :
588 : 28 : return tree->root;
589 : : }
590 : :
591 : 585 : idx = 0;
592 : 585 : path[idx++] = NULL;
593 : 585 : node = tree->root;
594 : :
595 : : while (1)
596 : 2353 : {
597 : 2938 : int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
598 : :
599 : 2938 : if (cmp == 0)
600 : : {
601 : 7 : if (tree->value_destroy_func)
602 : 7 : tree->value_destroy_func (node->value);
603 : :
604 : 7 : node->value = value;
605 : :
606 : 7 : if (replace)
607 : : {
608 : 2 : if (tree->key_destroy_func)
609 : 2 : tree->key_destroy_func (node->key);
610 : :
611 : 2 : node->key = key;
612 : : }
613 : : else
614 : : {
615 : : /* free the passed key */
616 : 5 : if (tree->key_destroy_func)
617 : 5 : tree->key_destroy_func (key);
618 : : }
619 : :
620 : 7 : return node;
621 : : }
622 : 2931 : else if (cmp < 0)
623 : : {
624 : 715 : if (node->left_child)
625 : : {
626 : 570 : path[idx++] = node;
627 : 570 : node = node->left;
628 : : }
629 : : else
630 : : {
631 : : GTreeNode *child;
632 : :
633 : 145 : if (!g_tree_nnodes_inc_checked (tree, !null_ret_ok))
634 : : {
635 : 0 : return NULL;
636 : : }
637 : :
638 : 145 : child = g_tree_node_new (key, value);
639 : 145 : child->left = node->left;
640 : 145 : child->right = node;
641 : 145 : node->left = child;
642 : 145 : node->left_child = TRUE;
643 : 145 : node->balance -= 1;
644 : :
645 : 145 : retnode = child;
646 : 145 : break;
647 : : }
648 : : }
649 : : else
650 : : {
651 : 2216 : if (node->right_child)
652 : : {
653 : 1783 : path[idx++] = node;
654 : 1783 : node = node->right;
655 : : }
656 : : else
657 : : {
658 : : GTreeNode *child;
659 : :
660 : 433 : if (!g_tree_nnodes_inc_checked (tree, !null_ret_ok))
661 : : {
662 : 0 : return NULL;
663 : : }
664 : :
665 : 433 : child = g_tree_node_new (key, value);
666 : 433 : child->right = node->right;
667 : 433 : child->left = node;
668 : 433 : node->right = child;
669 : 433 : node->right_child = TRUE;
670 : 433 : node->balance += 1;
671 : :
672 : 433 : retnode = child;
673 : 433 : break;
674 : : }
675 : : }
676 : : }
677 : :
678 : : /* Restore balance. This is the goodness of a non-recursive
679 : : * implementation, when we are done with balancing we 'break'
680 : : * the loop and we are done.
681 : : */
682 : : while (1)
683 : 1014 : {
684 : 1592 : GTreeNode *bparent = path[--idx];
685 : 1592 : gboolean left_node = (bparent && node == bparent->left);
686 : 1592 : g_assert (!bparent || bparent->left == node || bparent->right == node);
687 : :
688 : 1592 : if (node->balance < -1 || node->balance > 1)
689 : : {
690 : 474 : node = g_tree_node_balance (node);
691 : 474 : if (bparent == NULL)
692 : 39 : tree->root = node;
693 : 435 : else if (left_node)
694 : 83 : bparent->left = node;
695 : : else
696 : 352 : bparent->right = node;
697 : : }
698 : :
699 : 1592 : if (node->balance == 0 || bparent == NULL)
700 : : break;
701 : :
702 : 1014 : if (left_node)
703 : 245 : bparent->balance -= 1;
704 : : else
705 : 769 : bparent->balance += 1;
706 : :
707 : 1014 : node = bparent;
708 : : }
709 : :
710 : 578 : return retnode;
711 : : }
712 : :
713 : : /**
714 : : * g_tree_remove:
715 : : * @tree: a #GTree
716 : : * @key: the key to remove
717 : : *
718 : : * Removes a key/value pair from a #GTree.
719 : : *
720 : : * If the #GTree was created using g_tree_new_full(), the key and value
721 : : * are freed using the supplied destroy functions, otherwise you have to
722 : : * make sure that any dynamically allocated values are freed yourself.
723 : : * If the key does not exist in the #GTree, the function does nothing.
724 : : *
725 : : * The cost of maintaining a balanced tree while removing a key/value
726 : : * result in a O(n log(n)) operation where most of the other operations
727 : : * are O(log(n)).
728 : : *
729 : : * Returns: %TRUE if the key was found (prior to 2.8, this function
730 : : * returned nothing)
731 : : */
732 : : gboolean
733 : 104 : g_tree_remove (GTree *tree,
734 : : gconstpointer key)
735 : : {
736 : : gboolean removed;
737 : :
738 : 104 : g_return_val_if_fail (tree != NULL, FALSE);
739 : :
740 : 104 : removed = g_tree_remove_internal (tree, key, FALSE);
741 : :
742 : : #ifdef G_TREE_DEBUG
743 : : g_tree_node_check (tree->root);
744 : : #endif
745 : :
746 : 104 : return removed;
747 : : }
748 : :
749 : : /**
750 : : * g_tree_steal:
751 : : * @tree: a #GTree
752 : : * @key: the key to remove
753 : : *
754 : : * Removes a key and its associated value from a #GTree without calling
755 : : * the key and value destroy functions.
756 : : *
757 : : * If the key does not exist in the #GTree, the function does nothing.
758 : : *
759 : : * Returns: %TRUE if the key was found (prior to 2.8, this function
760 : : * returned nothing)
761 : : */
762 : : gboolean
763 : 1 : g_tree_steal (GTree *tree,
764 : : gconstpointer key)
765 : : {
766 : : gboolean removed;
767 : :
768 : 1 : g_return_val_if_fail (tree != NULL, FALSE);
769 : :
770 : 1 : removed = g_tree_remove_internal (tree, key, TRUE);
771 : :
772 : : #ifdef G_TREE_DEBUG
773 : : g_tree_node_check (tree->root);
774 : : #endif
775 : :
776 : 1 : return removed;
777 : : }
778 : :
779 : : /* internal remove routine */
780 : : static gboolean
781 : 105 : g_tree_remove_internal (GTree *tree,
782 : : gconstpointer key,
783 : : gboolean steal)
784 : : {
785 : : GTreeNode *node, *parent, *balance;
786 : : GTreeNode *path[MAX_GTREE_HEIGHT];
787 : : int idx;
788 : : gboolean left_node;
789 : :
790 : 105 : g_return_val_if_fail (tree != NULL, FALSE);
791 : :
792 : 105 : if (!tree->root)
793 : 0 : return FALSE;
794 : :
795 : 105 : idx = 0;
796 : 105 : path[idx++] = NULL;
797 : 105 : node = tree->root;
798 : :
799 : : while (1)
800 : 287 : {
801 : 392 : int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
802 : :
803 : 392 : if (cmp == 0)
804 : 104 : break;
805 : 288 : else if (cmp < 0)
806 : : {
807 : 247 : if (!node->left_child)
808 : 1 : return FALSE;
809 : :
810 : 246 : path[idx++] = node;
811 : 246 : node = node->left;
812 : : }
813 : : else
814 : : {
815 : 41 : if (!node->right_child)
816 : 0 : return FALSE;
817 : :
818 : 41 : path[idx++] = node;
819 : 41 : node = node->right;
820 : : }
821 : : }
822 : :
823 : : /* The following code is almost equal to g_tree_remove_node,
824 : : * except that we do not have to call g_tree_node_parent.
825 : : */
826 : 104 : balance = parent = path[--idx];
827 : 104 : g_assert (!parent || parent->left == node || parent->right == node);
828 : 104 : left_node = (parent && node == parent->left);
829 : :
830 : 104 : if (!node->left_child)
831 : : {
832 : 76 : if (!node->right_child)
833 : : {
834 : 48 : if (!parent)
835 : 3 : tree->root = NULL;
836 : 45 : else if (left_node)
837 : : {
838 : 38 : parent->left_child = FALSE;
839 : 38 : parent->left = node->left;
840 : 38 : parent->balance += 1;
841 : : }
842 : : else
843 : : {
844 : 7 : parent->right_child = FALSE;
845 : 7 : parent->right = node->right;
846 : 7 : parent->balance -= 1;
847 : : }
848 : : }
849 : : else /* node has a right child */
850 : : {
851 : 28 : GTreeNode *tmp = g_tree_node_next (node);
852 : 28 : tmp->left = node->left;
853 : :
854 : 28 : if (!parent)
855 : 2 : tree->root = node->right;
856 : 26 : else if (left_node)
857 : : {
858 : 26 : parent->left = node->right;
859 : 26 : parent->balance += 1;
860 : : }
861 : : else
862 : : {
863 : 0 : parent->right = node->right;
864 : 0 : parent->balance -= 1;
865 : : }
866 : : }
867 : : }
868 : : else /* node has a left child */
869 : : {
870 : 28 : if (!node->right_child)
871 : : {
872 : 1 : GTreeNode *tmp = g_tree_node_previous (node);
873 : 1 : tmp->right = node->right;
874 : :
875 : 1 : if (parent == NULL)
876 : 0 : tree->root = node->left;
877 : 1 : else if (left_node)
878 : : {
879 : 0 : parent->left = node->left;
880 : 0 : parent->balance += 1;
881 : : }
882 : : else
883 : : {
884 : 1 : parent->right = node->left;
885 : 1 : parent->balance -= 1;
886 : : }
887 : : }
888 : : else /* node has a both children (pant, pant!) */
889 : : {
890 : 27 : GTreeNode *prev = node->left;
891 : 27 : GTreeNode *next = node->right;
892 : 27 : GTreeNode *nextp = node;
893 : 27 : int old_idx = idx + 1;
894 : 27 : idx++;
895 : :
896 : : /* path[idx] == parent */
897 : : /* find the immediately next node (and its parent) */
898 : 68 : while (next->left_child)
899 : : {
900 : 41 : path[++idx] = nextp = next;
901 : 41 : next = next->left;
902 : : }
903 : :
904 : 27 : path[old_idx] = next;
905 : 27 : balance = path[idx];
906 : :
907 : : /* remove 'next' from the tree */
908 : 27 : if (nextp != node)
909 : : {
910 : 21 : if (next->right_child)
911 : 8 : nextp->left = next->right;
912 : : else
913 : 13 : nextp->left_child = FALSE;
914 : 21 : nextp->balance += 1;
915 : :
916 : 21 : next->right_child = TRUE;
917 : 21 : next->right = node->right;
918 : : }
919 : : else
920 : 6 : node->balance -= 1;
921 : :
922 : : /* set the prev to point to the right place */
923 : 46 : while (prev->right_child)
924 : 19 : prev = prev->right;
925 : 27 : prev->right = next;
926 : :
927 : : /* prepare 'next' to replace 'node' */
928 : 27 : next->left_child = TRUE;
929 : 27 : next->left = node->left;
930 : 27 : next->balance = node->balance;
931 : :
932 : 27 : if (!parent)
933 : 5 : tree->root = next;
934 : 22 : else if (left_node)
935 : 13 : parent->left = next;
936 : : else
937 : 9 : parent->right = next;
938 : : }
939 : : }
940 : :
941 : : /* restore balance */
942 : 104 : if (balance)
943 : : while (1)
944 : 46 : {
945 : 145 : GTreeNode *bparent = path[--idx];
946 : 145 : g_assert (!bparent || bparent->left == balance || bparent->right == balance);
947 : 145 : left_node = (bparent && balance == bparent->left);
948 : :
949 : 145 : if(balance->balance < -1 || balance->balance > 1)
950 : : {
951 : 40 : balance = g_tree_node_balance (balance);
952 : 40 : if (!bparent)
953 : 4 : tree->root = balance;
954 : 36 : else if (left_node)
955 : 30 : bparent->left = balance;
956 : : else
957 : 6 : bparent->right = balance;
958 : : }
959 : :
960 : 145 : if (balance->balance != 0 || !bparent)
961 : : break;
962 : :
963 : 46 : if (left_node)
964 : 37 : bparent->balance += 1;
965 : : else
966 : 9 : bparent->balance -= 1;
967 : :
968 : 46 : balance = bparent;
969 : : }
970 : :
971 : 104 : if (!steal)
972 : : {
973 : 103 : if (tree->key_destroy_func)
974 : 15 : tree->key_destroy_func (node->key);
975 : 103 : if (tree->value_destroy_func)
976 : 15 : tree->value_destroy_func (node->value);
977 : : }
978 : :
979 : 104 : g_slice_free (GTreeNode, node);
980 : :
981 : 104 : tree->nnodes--;
982 : :
983 : 104 : return TRUE;
984 : : }
985 : :
986 : : /**
987 : : * g_tree_node_key:
988 : : * @node: a #GTree node
989 : : *
990 : : * Gets the key stored at a particular tree node.
991 : : *
992 : : * Returns: (nullable) (transfer none): the key at the node.
993 : : *
994 : : * Since: 2.68
995 : : */
996 : : gpointer
997 : 113 : g_tree_node_key (GTreeNode *node)
998 : : {
999 : 113 : g_return_val_if_fail (node != NULL, NULL);
1000 : :
1001 : 113 : return node->key;
1002 : : }
1003 : :
1004 : : /**
1005 : : * g_tree_node_value:
1006 : : * @node: a #GTree node
1007 : : *
1008 : : * Gets the value stored at a particular tree node.
1009 : : *
1010 : : * Returns: (nullable) (transfer none): the value at the node.
1011 : : *
1012 : : * Since: 2.68
1013 : : */
1014 : : gpointer
1015 : 62 : g_tree_node_value (GTreeNode *node)
1016 : : {
1017 : 62 : g_return_val_if_fail (node != NULL, NULL);
1018 : :
1019 : 62 : return node->value;
1020 : : }
1021 : :
1022 : : /**
1023 : : * g_tree_lookup_node:
1024 : : * @tree: a #GTree
1025 : : * @key: the key to look up
1026 : : *
1027 : : * Gets the tree node corresponding to the given key. Since a #GTree is
1028 : : * automatically balanced as key/value pairs are added, key lookup
1029 : : * is O(log n) (where n is the number of key/value pairs in the tree).
1030 : : *
1031 : : * Returns: (nullable) (transfer none): the tree node corresponding to
1032 : : * the key, or %NULL if the key was not found
1033 : : *
1034 : : * Since: 2.68
1035 : : */
1036 : : GTreeNode *
1037 : 12 : g_tree_lookup_node (GTree *tree,
1038 : : gconstpointer key)
1039 : : {
1040 : 12 : g_return_val_if_fail (tree != NULL, NULL);
1041 : :
1042 : 12 : return g_tree_find_node (tree, key);
1043 : : }
1044 : :
1045 : : /**
1046 : : * g_tree_lookup:
1047 : : * @tree: a #GTree
1048 : : * @key: the key to look up
1049 : : *
1050 : : * Gets the value corresponding to the given key. Since a #GTree is
1051 : : * automatically balanced as key/value pairs are added, key lookup
1052 : : * is O(log n) (where n is the number of key/value pairs in the tree).
1053 : : *
1054 : : * Returns: the value corresponding to the key, or %NULL
1055 : : * if the key was not found
1056 : : */
1057 : : gpointer
1058 : 12 : g_tree_lookup (GTree *tree,
1059 : : gconstpointer key)
1060 : : {
1061 : : GTreeNode *node;
1062 : :
1063 : 12 : node = g_tree_lookup_node (tree, key);
1064 : :
1065 : 12 : return node ? node->value : NULL;
1066 : : }
1067 : :
1068 : : /**
1069 : : * g_tree_lookup_extended:
1070 : : * @tree: a #GTree
1071 : : * @lookup_key: the key to look up
1072 : : * @orig_key: (out) (optional) (nullable): returns the original key
1073 : : * @value: (out) (optional) (nullable): returns the value associated with the key
1074 : : *
1075 : : * Looks up a key in the #GTree, returning the original key and the
1076 : : * associated value. This is useful if you need to free the memory
1077 : : * allocated for the original key, for example before calling
1078 : : * g_tree_remove().
1079 : : *
1080 : : * Returns: %TRUE if the key was found in the #GTree
1081 : : */
1082 : : gboolean
1083 : 16 : g_tree_lookup_extended (GTree *tree,
1084 : : gconstpointer lookup_key,
1085 : : gpointer *orig_key,
1086 : : gpointer *value)
1087 : : {
1088 : : GTreeNode *node;
1089 : :
1090 : 16 : g_return_val_if_fail (tree != NULL, FALSE);
1091 : :
1092 : 16 : node = g_tree_find_node (tree, lookup_key);
1093 : :
1094 : 16 : if (node)
1095 : : {
1096 : 6 : if (orig_key)
1097 : 1 : *orig_key = node->key;
1098 : 6 : if (value)
1099 : 6 : *value = node->value;
1100 : 6 : return TRUE;
1101 : : }
1102 : : else
1103 : 10 : return FALSE;
1104 : : }
1105 : :
1106 : : /**
1107 : : * g_tree_foreach:
1108 : : * @tree: a #GTree
1109 : : * @func: (scope call): the function to call for each node visited.
1110 : : * If this function returns %TRUE, the traversal is stopped.
1111 : : * @user_data: user data to pass to the function
1112 : : *
1113 : : * Calls the given function for each of the key/value pairs in the #GTree.
1114 : : * The function is passed the key and value of each pair, and the given
1115 : : * @data parameter. The tree is traversed in sorted order.
1116 : : *
1117 : : * The tree may not be modified while iterating over it (you can't
1118 : : * add/remove items). To remove all items matching a predicate, you need
1119 : : * to add each item to a list in your #GTraverseFunc as you walk over
1120 : : * the tree, then walk the list and remove each item.
1121 : : */
1122 : : void
1123 : 48 : g_tree_foreach (GTree *tree,
1124 : : GTraverseFunc func,
1125 : : gpointer user_data)
1126 : : {
1127 : : GTreeNode *node;
1128 : :
1129 : 48 : g_return_if_fail (tree != NULL);
1130 : :
1131 : 48 : if (!tree->root)
1132 : 0 : return;
1133 : :
1134 : 48 : node = g_tree_node_first (tree);
1135 : :
1136 : 488 : while (node)
1137 : : {
1138 : 442 : if ((*func) (node->key, node->value, user_data))
1139 : 2 : break;
1140 : :
1141 : 440 : node = g_tree_node_next (node);
1142 : : }
1143 : : }
1144 : :
1145 : : /**
1146 : : * g_tree_foreach_node:
1147 : : * @tree: a #GTree
1148 : : * @func: (scope call): the function to call for each node visited.
1149 : : * If this function returns %TRUE, the traversal is stopped.
1150 : : * @user_data: user data to pass to the function
1151 : : *
1152 : : * Calls the given function for each of the nodes in the #GTree.
1153 : : * The function is passed the pointer to the particular node, and the given
1154 : : * @data parameter. The tree traversal happens in-order.
1155 : : *
1156 : : * The tree may not be modified while iterating over it (you can't
1157 : : * add/remove items). To remove all items matching a predicate, you need
1158 : : * to add each item to a list in your #GTraverseFunc as you walk over
1159 : : * the tree, then walk the list and remove each item.
1160 : : *
1161 : : * Since: 2.68
1162 : : */
1163 : : void
1164 : 0 : g_tree_foreach_node (GTree *tree,
1165 : : GTraverseNodeFunc func,
1166 : : gpointer user_data)
1167 : : {
1168 : : GTreeNode *node;
1169 : :
1170 : 0 : g_return_if_fail (tree != NULL);
1171 : :
1172 : 0 : if (!tree->root)
1173 : 0 : return;
1174 : :
1175 : 0 : node = g_tree_node_first (tree);
1176 : :
1177 : 0 : while (node)
1178 : : {
1179 : 0 : if ((*func) (node, user_data))
1180 : 0 : break;
1181 : :
1182 : 0 : node = g_tree_node_next (node);
1183 : : }
1184 : : }
1185 : :
1186 : : /**
1187 : : * g_tree_traverse:
1188 : : * @tree: a #GTree
1189 : : * @traverse_func: (scope call): the function to call for each node visited. If this
1190 : : * function returns %TRUE, the traversal is stopped.
1191 : : * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
1192 : : * %G_PRE_ORDER and %G_POST_ORDER
1193 : : * @user_data: user data to pass to the function
1194 : : *
1195 : : * Calls the given function for each node in the #GTree.
1196 : : *
1197 : : * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary.
1198 : : * If you just want to visit all nodes in sorted order, use
1199 : : * g_tree_foreach() instead. If you really need to visit nodes in
1200 : : * a different order, consider using an [n-ary tree][glib-N-ary-Trees].
1201 : : */
1202 : : /**
1203 : : * GTraverseFunc:
1204 : : * @key: a key of a #GTree node
1205 : : * @value: the value corresponding to the key
1206 : : * @data: user data passed to g_tree_traverse()
1207 : : *
1208 : : * Specifies the type of function passed to g_tree_traverse(). It is
1209 : : * passed the key and value of each node, together with the @user_data
1210 : : * parameter passed to g_tree_traverse(). If the function returns
1211 : : * %TRUE, the traversal is stopped.
1212 : : *
1213 : : * Returns: %TRUE to stop the traversal
1214 : : */
1215 : : void
1216 : 45 : g_tree_traverse (GTree *tree,
1217 : : GTraverseFunc traverse_func,
1218 : : GTraverseType traverse_type,
1219 : : gpointer user_data)
1220 : : {
1221 : 45 : g_return_if_fail (tree != NULL);
1222 : :
1223 : 45 : if (!tree->root)
1224 : 0 : return;
1225 : :
1226 : 45 : switch (traverse_type)
1227 : : {
1228 : 15 : case G_PRE_ORDER:
1229 : 15 : g_tree_node_pre_order (tree->root, traverse_func, user_data);
1230 : 15 : break;
1231 : :
1232 : 15 : case G_IN_ORDER:
1233 : 15 : g_tree_node_in_order (tree->root, traverse_func, user_data);
1234 : 15 : break;
1235 : :
1236 : 15 : case G_POST_ORDER:
1237 : 15 : g_tree_node_post_order (tree->root, traverse_func, user_data);
1238 : 15 : break;
1239 : :
1240 : 0 : case G_LEVEL_ORDER:
1241 : 0 : g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
1242 : 0 : break;
1243 : : }
1244 : : }
1245 : :
1246 : : /**
1247 : : * g_tree_search_node:
1248 : : * @tree: a #GTree
1249 : : * @search_func: (scope call): a function used to search the #GTree
1250 : : * @user_data: the data passed as the second argument to @search_func
1251 : : *
1252 : : * Searches a #GTree using @search_func.
1253 : : *
1254 : : * The @search_func is called with a pointer to the key of a key/value
1255 : : * pair in the tree, and the passed in @user_data. If @search_func returns
1256 : : * 0 for a key/value pair, then the corresponding node is returned as
1257 : : * the result of g_tree_search(). If @search_func returns -1, searching
1258 : : * will proceed among the key/value pairs that have a smaller key; if
1259 : : * @search_func returns 1, searching will proceed among the key/value
1260 : : * pairs that have a larger key.
1261 : : *
1262 : : * Returns: (nullable) (transfer none): the node corresponding to the
1263 : : * found key, or %NULL if the key was not found
1264 : : *
1265 : : * Since: 2.68
1266 : : */
1267 : : GTreeNode *
1268 : 7 : g_tree_search_node (GTree *tree,
1269 : : GCompareFunc search_func,
1270 : : gconstpointer user_data)
1271 : : {
1272 : 7 : g_return_val_if_fail (tree != NULL, NULL);
1273 : :
1274 : 7 : if (!tree->root)
1275 : 0 : return NULL;
1276 : :
1277 : 7 : return g_tree_node_search (tree->root, search_func, user_data);
1278 : : }
1279 : :
1280 : : /**
1281 : : * g_tree_search:
1282 : : * @tree: a #GTree
1283 : : * @search_func: (scope call): a function used to search the #GTree
1284 : : * @user_data: the data passed as the second argument to @search_func
1285 : : *
1286 : : * Searches a #GTree using @search_func.
1287 : : *
1288 : : * The @search_func is called with a pointer to the key of a key/value
1289 : : * pair in the tree, and the passed in @user_data. If @search_func returns
1290 : : * 0 for a key/value pair, then the corresponding value is returned as
1291 : : * the result of g_tree_search(). If @search_func returns -1, searching
1292 : : * will proceed among the key/value pairs that have a smaller key; if
1293 : : * @search_func returns 1, searching will proceed among the key/value
1294 : : * pairs that have a larger key.
1295 : : *
1296 : : * Returns: the value corresponding to the found key, or %NULL
1297 : : * if the key was not found
1298 : : */
1299 : : gpointer
1300 : 7 : g_tree_search (GTree *tree,
1301 : : GCompareFunc search_func,
1302 : : gconstpointer user_data)
1303 : : {
1304 : : GTreeNode *node;
1305 : :
1306 : 7 : node = g_tree_search_node (tree, search_func, user_data);
1307 : :
1308 : 7 : return node ? node->value : NULL;
1309 : : }
1310 : :
1311 : : /**
1312 : : * g_tree_lower_bound:
1313 : : * @tree: a #GTree
1314 : : * @key: the key to calculate the lower bound for
1315 : : *
1316 : : * Gets the lower bound node corresponding to the given key,
1317 : : * or %NULL if the tree is empty or all the nodes in the tree
1318 : : * have keys that are strictly lower than the searched key.
1319 : : *
1320 : : * The lower bound is the first node that has its key greater
1321 : : * than or equal to the searched key.
1322 : : *
1323 : : * Returns: (nullable) (transfer none): the tree node corresponding to
1324 : : * the lower bound, or %NULL if the tree is empty or has only
1325 : : * keys strictly lower than the searched key.
1326 : : *
1327 : : * Since: 2.68
1328 : : */
1329 : : GTreeNode *
1330 : 44 : g_tree_lower_bound (GTree *tree,
1331 : : gconstpointer key)
1332 : : {
1333 : : GTreeNode *node, *result;
1334 : : gint cmp;
1335 : :
1336 : 44 : g_return_val_if_fail (tree != NULL, NULL);
1337 : :
1338 : 44 : node = tree->root;
1339 : 44 : if (!node)
1340 : 11 : return NULL;
1341 : :
1342 : 33 : result = NULL;
1343 : : while (1)
1344 : : {
1345 : 142 : cmp = tree->key_compare (key, node->key, tree->key_compare_data);
1346 : 142 : if (cmp <= 0)
1347 : : {
1348 : 84 : result = node;
1349 : :
1350 : 84 : if (!node->left_child)
1351 : 20 : return result;
1352 : :
1353 : 64 : node = node->left;
1354 : : }
1355 : : else
1356 : : {
1357 : 58 : if (!node->right_child)
1358 : 13 : return result;
1359 : :
1360 : 45 : node = node->right;
1361 : : }
1362 : : }
1363 : : }
1364 : :
1365 : : /**
1366 : : * g_tree_upper_bound:
1367 : : * @tree: a #GTree
1368 : : * @key: the key to calculate the upper bound for
1369 : : *
1370 : : * Gets the upper bound node corresponding to the given key,
1371 : : * or %NULL if the tree is empty or all the nodes in the tree
1372 : : * have keys that are lower than or equal to the searched key.
1373 : : *
1374 : : * The upper bound is the first node that has its key strictly greater
1375 : : * than the searched key.
1376 : : *
1377 : : * Returns: (nullable) (transfer none): the tree node corresponding to the
1378 : : * upper bound, or %NULL if the tree is empty or has only keys
1379 : : * lower than or equal to the searched key.
1380 : : *
1381 : : * Since: 2.68
1382 : : */
1383 : : GTreeNode *
1384 : 44 : g_tree_upper_bound (GTree *tree,
1385 : : gconstpointer key)
1386 : : {
1387 : : GTreeNode *node, *result;
1388 : : gint cmp;
1389 : :
1390 : 44 : g_return_val_if_fail (tree != NULL, NULL);
1391 : :
1392 : 44 : node = tree->root;
1393 : 44 : if (!node)
1394 : 11 : return NULL;
1395 : :
1396 : 33 : result = NULL;
1397 : : while (1)
1398 : : {
1399 : 137 : cmp = tree->key_compare (key, node->key, tree->key_compare_data);
1400 : 137 : if (cmp < 0)
1401 : : {
1402 : 76 : result = node;
1403 : :
1404 : 76 : if (!node->left_child)
1405 : 17 : return result;
1406 : :
1407 : 59 : node = node->left;
1408 : : }
1409 : : else
1410 : : {
1411 : 61 : if (!node->right_child)
1412 : 16 : return result;
1413 : :
1414 : 45 : node = node->right;
1415 : : }
1416 : : }
1417 : : }
1418 : :
1419 : : /**
1420 : : * g_tree_height:
1421 : : * @tree: a #GTree
1422 : : *
1423 : : * Gets the height of a #GTree.
1424 : : *
1425 : : * If the #GTree contains no nodes, the height is 0.
1426 : : * If the #GTree contains only one root node the height is 1.
1427 : : * If the root node has children the height is 2, etc.
1428 : : *
1429 : : * Returns: the height of @tree
1430 : : */
1431 : : gint
1432 : 7 : g_tree_height (GTree *tree)
1433 : : {
1434 : : GTreeNode *node;
1435 : : gint height;
1436 : :
1437 : 7 : g_return_val_if_fail (tree != NULL, 0);
1438 : :
1439 : 7 : if (!tree->root)
1440 : 1 : return 0;
1441 : :
1442 : 6 : height = 0;
1443 : 6 : node = tree->root;
1444 : :
1445 : : while (1)
1446 : : {
1447 : 37 : height += 1 + MAX(node->balance, 0);
1448 : :
1449 : 37 : if (!node->left_child)
1450 : 6 : return height;
1451 : :
1452 : 31 : node = node->left;
1453 : : }
1454 : : }
1455 : :
1456 : : /**
1457 : : * g_tree_nnodes:
1458 : : * @tree: a #GTree
1459 : : *
1460 : : * Gets the number of nodes in a #GTree.
1461 : : *
1462 : : * Returns: the number of nodes in @tree
1463 : : *
1464 : : * The node counter value type is really a #guint,
1465 : : * but it is returned as a #gint due to backward
1466 : : * compatibility issues (can be cast back to #guint to
1467 : : * support its full range of values).
1468 : : */
1469 : : gint
1470 : 107 : g_tree_nnodes (GTree *tree)
1471 : : {
1472 : 107 : g_return_val_if_fail (tree != NULL, 0);
1473 : :
1474 : 107 : return tree->nnodes;
1475 : : }
1476 : :
1477 : : static GTreeNode *
1478 : 514 : g_tree_node_balance (GTreeNode *node)
1479 : : {
1480 : 514 : if (node->balance < -1)
1481 : : {
1482 : 106 : if (node->left->balance > 0)
1483 : 22 : node->left = g_tree_node_rotate_left (node->left);
1484 : 106 : node = g_tree_node_rotate_right (node);
1485 : : }
1486 : 408 : else if (node->balance > 1)
1487 : : {
1488 : 408 : if (node->right->balance < 0)
1489 : 27 : node->right = g_tree_node_rotate_right (node->right);
1490 : 408 : node = g_tree_node_rotate_left (node);
1491 : : }
1492 : :
1493 : 514 : return node;
1494 : : }
1495 : :
1496 : : static GTreeNode *
1497 : 28 : g_tree_find_node (GTree *tree,
1498 : : gconstpointer key)
1499 : : {
1500 : : GTreeNode *node;
1501 : : gint cmp;
1502 : :
1503 : 28 : node = tree->root;
1504 : 28 : if (!node)
1505 : 11 : return NULL;
1506 : :
1507 : : while (1)
1508 : : {
1509 : 54 : cmp = tree->key_compare (key, node->key, tree->key_compare_data);
1510 : 54 : if (cmp == 0)
1511 : 14 : return node;
1512 : 40 : else if (cmp < 0)
1513 : : {
1514 : 25 : if (!node->left_child)
1515 : 2 : return NULL;
1516 : :
1517 : 23 : node = node->left;
1518 : : }
1519 : : else
1520 : : {
1521 : 15 : if (!node->right_child)
1522 : 1 : return NULL;
1523 : :
1524 : 14 : node = node->right;
1525 : : }
1526 : : }
1527 : : }
1528 : :
1529 : : static gint
1530 : 167 : g_tree_node_pre_order (GTreeNode *node,
1531 : : GTraverseFunc traverse_func,
1532 : : gpointer data)
1533 : : {
1534 : 167 : if ((*traverse_func) (node->key, node->value, data))
1535 : 14 : return TRUE;
1536 : :
1537 : 153 : if (node->left_child)
1538 : : {
1539 : 96 : if (g_tree_node_pre_order (node->left, traverse_func, data))
1540 : 41 : return TRUE;
1541 : : }
1542 : :
1543 : 112 : if (node->right_child)
1544 : : {
1545 : 56 : if (g_tree_node_pre_order (node->right, traverse_func, data))
1546 : 10 : return TRUE;
1547 : : }
1548 : :
1549 : 102 : return FALSE;
1550 : : }
1551 : :
1552 : : static gint
1553 : 212 : g_tree_node_in_order (GTreeNode *node,
1554 : : GTraverseFunc traverse_func,
1555 : : gpointer data)
1556 : : {
1557 : 212 : if (node->left_child)
1558 : : {
1559 : 124 : if (g_tree_node_in_order (node->left, traverse_func, data))
1560 : 45 : return TRUE;
1561 : : }
1562 : :
1563 : 167 : if ((*traverse_func) (node->key, node->value, data))
1564 : 14 : return TRUE;
1565 : :
1566 : 153 : if (node->right_child)
1567 : : {
1568 : 73 : if (g_tree_node_in_order (node->right, traverse_func, data))
1569 : 14 : return TRUE;
1570 : : }
1571 : :
1572 : 139 : return FALSE;
1573 : : }
1574 : :
1575 : : static gint
1576 : 229 : g_tree_node_post_order (GTreeNode *node,
1577 : : GTraverseFunc traverse_func,
1578 : : gpointer data)
1579 : : {
1580 : 229 : if (node->left_child)
1581 : : {
1582 : 129 : if (g_tree_node_post_order (node->left, traverse_func, data))
1583 : 45 : return TRUE;
1584 : : }
1585 : :
1586 : 184 : if (node->right_child)
1587 : : {
1588 : 85 : if (g_tree_node_post_order (node->right, traverse_func, data))
1589 : 17 : return TRUE;
1590 : : }
1591 : :
1592 : 167 : if ((*traverse_func) (node->key, node->value, data))
1593 : 14 : return TRUE;
1594 : :
1595 : 153 : return FALSE;
1596 : : }
1597 : :
1598 : : static GTreeNode *
1599 : 7 : g_tree_node_search (GTreeNode *node,
1600 : : GCompareFunc search_func,
1601 : : gconstpointer data)
1602 : : {
1603 : : gint dir;
1604 : :
1605 : 7 : if (!node)
1606 : 0 : return NULL;
1607 : :
1608 : : while (1)
1609 : : {
1610 : 39 : dir = (* search_func) (node->key, data);
1611 : 39 : if (dir == 0)
1612 : 4 : return node;
1613 : 35 : else if (dir < 0)
1614 : : {
1615 : 20 : if (!node->left_child)
1616 : 2 : return NULL;
1617 : :
1618 : 18 : node = node->left;
1619 : : }
1620 : : else
1621 : : {
1622 : 15 : if (!node->right_child)
1623 : 1 : return NULL;
1624 : :
1625 : 14 : node = node->right;
1626 : : }
1627 : : }
1628 : : }
1629 : :
1630 : : static GTreeNode *
1631 : 430 : g_tree_node_rotate_left (GTreeNode *node)
1632 : : {
1633 : : GTreeNode *right;
1634 : : gint a_bal;
1635 : : gint b_bal;
1636 : :
1637 : 430 : right = node->right;
1638 : :
1639 : 430 : if (right->left_child)
1640 : 204 : node->right = right->left;
1641 : : else
1642 : : {
1643 : 226 : node->right_child = FALSE;
1644 : 226 : right->left_child = TRUE;
1645 : : }
1646 : 430 : right->left = node;
1647 : :
1648 : 430 : a_bal = node->balance;
1649 : 430 : b_bal = right->balance;
1650 : :
1651 : 430 : if (b_bal <= 0)
1652 : : {
1653 : 40 : if (a_bal >= 1)
1654 : 40 : right->balance = b_bal - 1;
1655 : : else
1656 : 0 : right->balance = a_bal + b_bal - 2;
1657 : 40 : node->balance = a_bal - 1;
1658 : : }
1659 : : else
1660 : : {
1661 : 390 : if (a_bal <= b_bal)
1662 : 4 : right->balance = a_bal - 2;
1663 : : else
1664 : 386 : right->balance = b_bal - 1;
1665 : 390 : node->balance = a_bal - b_bal - 1;
1666 : : }
1667 : :
1668 : 430 : return right;
1669 : : }
1670 : :
1671 : : static GTreeNode *
1672 : 133 : g_tree_node_rotate_right (GTreeNode *node)
1673 : : {
1674 : : GTreeNode *left;
1675 : : gint a_bal;
1676 : : gint b_bal;
1677 : :
1678 : 133 : left = node->left;
1679 : :
1680 : 133 : if (left->right_child)
1681 : 47 : node->left = left->right;
1682 : : else
1683 : : {
1684 : 86 : node->left_child = FALSE;
1685 : 86 : left->right_child = TRUE;
1686 : : }
1687 : 133 : left->right = node;
1688 : :
1689 : 133 : a_bal = node->balance;
1690 : 133 : b_bal = left->balance;
1691 : :
1692 : 133 : if (b_bal <= 0)
1693 : : {
1694 : 131 : if (b_bal > a_bal)
1695 : 118 : left->balance = b_bal + 1;
1696 : : else
1697 : 13 : left->balance = a_bal + 2;
1698 : 131 : node->balance = a_bal - b_bal + 1;
1699 : : }
1700 : : else
1701 : : {
1702 : 2 : if (a_bal <= -1)
1703 : 2 : left->balance = b_bal + 1;
1704 : : else
1705 : 0 : left->balance = a_bal + b_bal + 2;
1706 : 2 : node->balance = a_bal + 1;
1707 : : }
1708 : :
1709 : 133 : return left;
1710 : : }
1711 : :
1712 : : #ifdef G_TREE_DEBUG
1713 : : static gint
1714 : : g_tree_node_height (GTreeNode *node)
1715 : : {
1716 : : gint left_height;
1717 : : gint right_height;
1718 : :
1719 : : if (node)
1720 : : {
1721 : : left_height = 0;
1722 : : right_height = 0;
1723 : :
1724 : : if (node->left_child)
1725 : : left_height = g_tree_node_height (node->left);
1726 : :
1727 : : if (node->right_child)
1728 : : right_height = g_tree_node_height (node->right);
1729 : :
1730 : : return MAX (left_height, right_height) + 1;
1731 : : }
1732 : :
1733 : : return 0;
1734 : : }
1735 : :
1736 : : static void
1737 : : g_tree_node_check (GTreeNode *node)
1738 : : {
1739 : : gint left_height;
1740 : : gint right_height;
1741 : : gint balance;
1742 : : GTreeNode *tmp;
1743 : :
1744 : : if (node)
1745 : : {
1746 : : if (node->left_child)
1747 : : {
1748 : : tmp = g_tree_node_previous (node);
1749 : : g_assert (tmp->right == node);
1750 : : }
1751 : :
1752 : : if (node->right_child)
1753 : : {
1754 : : tmp = g_tree_node_next (node);
1755 : : g_assert (tmp->left == node);
1756 : : }
1757 : :
1758 : : left_height = 0;
1759 : : right_height = 0;
1760 : :
1761 : : if (node->left_child)
1762 : : left_height = g_tree_node_height (node->left);
1763 : : if (node->right_child)
1764 : : right_height = g_tree_node_height (node->right);
1765 : :
1766 : : balance = right_height - left_height;
1767 : : g_assert (balance == node->balance);
1768 : :
1769 : : if (node->left_child)
1770 : : g_tree_node_check (node->left);
1771 : : if (node->right_child)
1772 : : g_tree_node_check (node->right);
1773 : : }
1774 : : }
1775 : :
1776 : : static void
1777 : : g_tree_node_dump (GTreeNode *node,
1778 : : gint indent)
1779 : : {
1780 : : g_print ("%*s%c\n", indent, "", *(char *)node->key);
1781 : :
1782 : : if (node->left_child)
1783 : : {
1784 : : g_print ("%*sLEFT\n", indent, "");
1785 : : g_tree_node_dump (node->left, indent + 2);
1786 : : }
1787 : : else if (node->left)
1788 : : g_print ("%*s<%c\n", indent + 2, "", *(char *)node->left->key);
1789 : :
1790 : : if (node->right_child)
1791 : : {
1792 : : g_print ("%*sRIGHT\n", indent, "");
1793 : : g_tree_node_dump (node->right, indent + 2);
1794 : : }
1795 : : else if (node->right)
1796 : : g_print ("%*s>%c\n", indent + 2, "", *(char *)node->right->key);
1797 : : }
1798 : :
1799 : : void
1800 : : g_tree_dump (GTree *tree)
1801 : : {
1802 : : if (tree->root)
1803 : : g_tree_node_dump (tree->root, 0);
1804 : : }
1805 : : #endif
|
