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