nexmon – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 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 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.
46 *
47 * To create a new #GTree use g_tree_new().
48 *
49 * To insert a key/value pair into a #GTree use g_tree_insert().
50 *
51 * To lookup the value corresponding to a given key, use
52 * g_tree_lookup() and g_tree_lookup_extended().
53 *
54 * To find out the number of nodes in a #GTree, use g_tree_nnodes(). To
55 * get the height of a #GTree, use g_tree_height().
56 *
57 * To traverse a #GTree, calling a function for each node visited in
58 * the traversal, use g_tree_foreach().
59 *
60 * To remove a key/value pair use g_tree_remove().
61 *
62 * To destroy a #GTree, use g_tree_destroy().
63 **/
64  
65 #undef G_TREE_DEBUG
66  
67 #define MAX_GTREE_HEIGHT 40
68  
69 typedef struct _GTreeNode GTreeNode;
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 void 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 gpointer 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 ((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 static inline GTreeNode *
230 g_tree_first_node (GTree *tree)
231 {
232 GTreeNode *tmp;
233  
234 if (!tree->root)
235 return NULL;
236  
237 tmp = tree->root;
238  
239 while (tmp->left_child)
240 tmp = tmp->left;
241  
242 return tmp;
243 }
244  
245 static inline GTreeNode *
246 g_tree_node_previous (GTreeNode *node)
247 {
248 GTreeNode *tmp;
249  
250 tmp = node->left;
251  
252 if (node->left_child)
253 while (tmp->right_child)
254 tmp = tmp->right;
255  
256 return tmp;
257 }
258  
259 static inline GTreeNode *
260 g_tree_node_next (GTreeNode *node)
261 {
262 GTreeNode *tmp;
263  
264 tmp = node->right;
265  
266 if (node->right_child)
267 while (tmp->left_child)
268 tmp = tmp->left;
269  
270 return tmp;
271 }
272  
273 static void
274 g_tree_remove_all (GTree *tree)
275 {
276 GTreeNode *node;
277 GTreeNode *next;
278  
279 g_return_if_fail (tree != NULL);
280  
281 node = g_tree_first_node (tree);
282  
283 while (node)
284 {
285 next = g_tree_node_next (node);
286  
287 if (tree->key_destroy_func)
288 tree->key_destroy_func (node->key);
289 if (tree->value_destroy_func)
290 tree->value_destroy_func (node->value);
291 g_slice_free (GTreeNode, node);
292  
293 node = next;
294 }
295  
296 tree->root = NULL;
297 tree->nnodes = 0;
298 }
299  
300 /**
301 * g_tree_ref:
302 * @tree: a #GTree
303 *
304 * Increments the reference count of @tree by one.
305 *
306 * It is safe to call this function from any thread.
307 *
308 * Returns: the passed in #GTree
309 *
310 * Since: 2.22
311 */
312 GTree *
313 g_tree_ref (GTree *tree)
314 {
315 g_return_val_if_fail (tree != NULL, NULL);
316  
317 g_atomic_int_inc (&tree->ref_count);
318  
319 return tree;
320 }
321  
322 /**
323 * g_tree_unref:
324 * @tree: a #GTree
325 *
326 * Decrements the reference count of @tree by one.
327 * If the reference count drops to 0, all keys and values will
328 * be destroyed (if destroy functions were specified) and all
329 * memory allocated by @tree will be released.
330 *
331 * It is safe to call this function from any thread.
332 *
333 * Since: 2.22
334 */
335 void
336 g_tree_unref (GTree *tree)
337 {
338 g_return_if_fail (tree != NULL);
339  
340 if (g_atomic_int_dec_and_test (&tree->ref_count))
341 {
342 g_tree_remove_all (tree);
343 g_slice_free (GTree, tree);
344 }
345 }
346  
347 /**
348 * g_tree_destroy:
349 * @tree: a #GTree
350 *
351 * Removes all keys and values from the #GTree and decreases its
352 * reference count by one. If keys and/or values are dynamically
353 * allocated, you should either free them first or create the #GTree
354 * using g_tree_new_full(). In the latter case the destroy functions
355 * you supplied will be called on all keys and values before destroying
356 * the #GTree.
357 */
358 void
359 g_tree_destroy (GTree *tree)
360 {
361 g_return_if_fail (tree != NULL);
362  
363 g_tree_remove_all (tree);
364 g_tree_unref (tree);
365 }
366  
367 /**
368 * g_tree_insert:
369 * @tree: a #GTree
370 * @key: the key to insert
371 * @value: the value corresponding to the key
372 *
373 * Inserts a key/value pair into a #GTree.
374 *
375 * If the given key already exists in the #GTree its corresponding value
376 * is set to the new value. If you supplied a @value_destroy_func when
377 * creating the #GTree, the old value is freed using that function. If
378 * you supplied a @key_destroy_func when creating the #GTree, the passed
379 * key is freed using that function.
380 *
381 * The tree is automatically 'balanced' as new key/value pairs are added,
382 * so that the distance from the root to every leaf is as small as possible.
383 */
384 void
385 g_tree_insert (GTree *tree,
386 gpointer key,
387 gpointer value)
388 {
389 g_return_if_fail (tree != NULL);
390  
391 g_tree_insert_internal (tree, key, value, FALSE);
392  
393 #ifdef G_TREE_DEBUG
394 g_tree_node_check (tree->root);
395 #endif
396 }
397  
398 /**
399 * g_tree_replace:
400 * @tree: a #GTree
401 * @key: the key to insert
402 * @value: the value corresponding to the key
403 *
404 * Inserts a new key and value into a #GTree similar to g_tree_insert().
405 * The difference is that if the key already exists in the #GTree, it gets
406 * replaced by the new key. If you supplied a @value_destroy_func when
407 * creating the #GTree, the old value is freed using that function. If you
408 * supplied a @key_destroy_func when creating the #GTree, the old key is
409 * freed using that function.
410 *
411 * The tree is automatically 'balanced' as new key/value pairs are added,
412 * so that the distance from the root to every leaf is as small as possible.
413 */
414 void
415 g_tree_replace (GTree *tree,
416 gpointer key,
417 gpointer value)
418 {
419 g_return_if_fail (tree != NULL);
420  
421 g_tree_insert_internal (tree, key, value, TRUE);
422  
423 #ifdef G_TREE_DEBUG
424 g_tree_node_check (tree->root);
425 #endif
426 }
427  
428 /* internal insert routine */
429 static void
430 g_tree_insert_internal (GTree *tree,
431 gpointer key,
432 gpointer value,
433 gboolean replace)
434 {
435 GTreeNode *node;
436 GTreeNode *path[MAX_GTREE_HEIGHT];
437 int idx;
438  
439 g_return_if_fail (tree != NULL);
440  
441 if (!tree->root)
442 {
443 tree->root = g_tree_node_new (key, value);
444 tree->nnodes++;
445 return;
446 }
447  
448 idx = 0;
449 path[idx++] = NULL;
450 node = tree->root;
451  
452 while (1)
453 {
454 int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
455  
456 if (cmp == 0)
457 {
458 if (tree->value_destroy_func)
459 tree->value_destroy_func (node->value);
460  
461 node->value = value;
462  
463 if (replace)
464 {
465 if (tree->key_destroy_func)
466 tree->key_destroy_func (node->key);
467  
468 node->key = key;
469 }
470 else
471 {
472 /* free the passed key */
473 if (tree->key_destroy_func)
474 tree->key_destroy_func (key);
475 }
476  
477 return;
478 }
479 else if (cmp < 0)
480 {
481 if (node->left_child)
482 {
483 path[idx++] = node;
484 node = node->left;
485 }
486 else
487 {
488 GTreeNode *child = g_tree_node_new (key, value);
489  
490 child->left = node->left;
491 child->right = node;
492 node->left = child;
493 node->left_child = TRUE;
494 node->balance -= 1;
495  
496 tree->nnodes++;
497  
498 break;
499 }
500 }
501 else
502 {
503 if (node->right_child)
504 {
505 path[idx++] = node;
506 node = node->right;
507 }
508 else
509 {
510 GTreeNode *child = g_tree_node_new (key, value);
511  
512 child->right = node->right;
513 child->left = node;
514 node->right = child;
515 node->right_child = TRUE;
516 node->balance += 1;
517  
518 tree->nnodes++;
519  
520 break;
521 }
522 }
523 }
524  
525 /* Restore balance. This is the goodness of a non-recursive
526 * implementation, when we are done with balancing we 'break'
527 * the loop and we are done.
528 */
529 while (1)
530 {
531 GTreeNode *bparent = path[--idx];
532 gboolean left_node = (bparent && node == bparent->left);
533 g_assert (!bparent || bparent->left == node || bparent->right == node);
534  
535 if (node->balance < -1 || node->balance > 1)
536 {
537 node = g_tree_node_balance (node);
538 if (bparent == NULL)
539 tree->root = node;
540 else if (left_node)
541 bparent->left = node;
542 else
543 bparent->right = node;
544 }
545  
546 if (node->balance == 0 || bparent == NULL)
547 break;
548  
549 if (left_node)
550 bparent->balance -= 1;
551 else
552 bparent->balance += 1;
553  
554 node = bparent;
555 }
556 }
557  
558 /**
559 * g_tree_remove:
560 * @tree: a #GTree
561 * @key: the key to remove
562 *
563 * Removes a key/value pair from a #GTree.
564 *
565 * If the #GTree was created using g_tree_new_full(), the key and value
566 * are freed using the supplied destroy functions, otherwise you have to
567 * make sure that any dynamically allocated values are freed yourself.
568 * If the key does not exist in the #GTree, the function does nothing.
569 *
570 * Returns: %TRUE if the key was found (prior to 2.8, this function
571 * returned nothing)
572 */
573 gboolean
574 g_tree_remove (GTree *tree,
575 gconstpointer key)
576 {
577 gboolean removed;
578  
579 g_return_val_if_fail (tree != NULL, FALSE);
580  
581 removed = g_tree_remove_internal (tree, key, FALSE);
582  
583 #ifdef G_TREE_DEBUG
584 g_tree_node_check (tree->root);
585 #endif
586  
587 return removed;
588 }
589  
590 /**
591 * g_tree_steal:
592 * @tree: a #GTree
593 * @key: the key to remove
594 *
595 * Removes a key and its associated value from a #GTree without calling
596 * the key and value destroy functions.
597 *
598 * If the key does not exist in the #GTree, the function does nothing.
599 *
600 * Returns: %TRUE if the key was found (prior to 2.8, this function
601 * returned nothing)
602 */
603 gboolean
604 g_tree_steal (GTree *tree,
605 gconstpointer key)
606 {
607 gboolean removed;
608  
609 g_return_val_if_fail (tree != NULL, FALSE);
610  
611 removed = g_tree_remove_internal (tree, key, TRUE);
612  
613 #ifdef G_TREE_DEBUG
614 g_tree_node_check (tree->root);
615 #endif
616  
617 return removed;
618 }
619  
620 /* internal remove routine */
621 static gboolean
622 g_tree_remove_internal (GTree *tree,
623 gconstpointer key,
624 gboolean steal)
625 {
626 GTreeNode *node, *parent, *balance;
627 GTreeNode *path[MAX_GTREE_HEIGHT];
628 int idx;
629 gboolean left_node;
630  
631 g_return_val_if_fail (tree != NULL, FALSE);
632  
633 if (!tree->root)
634 return FALSE;
635  
636 idx = 0;
637 path[idx++] = NULL;
638 node = tree->root;
639  
640 while (1)
641 {
642 int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
643  
644 if (cmp == 0)
645 break;
646 else if (cmp < 0)
647 {
648 if (!node->left_child)
649 return FALSE;
650  
651 path[idx++] = node;
652 node = node->left;
653 }
654 else
655 {
656 if (!node->right_child)
657 return FALSE;
658  
659 path[idx++] = node;
660 node = node->right;
661 }
662 }
663  
664 /* The following code is almost equal to g_tree_remove_node,
665 * except that we do not have to call g_tree_node_parent.
666 */
667 balance = parent = path[--idx];
668 g_assert (!parent || parent->left == node || parent->right == node);
669 left_node = (parent && node == parent->left);
670  
671 if (!node->left_child)
672 {
673 if (!node->right_child)
674 {
675 if (!parent)
676 tree->root = NULL;
677 else if (left_node)
678 {
679 parent->left_child = FALSE;
680 parent->left = node->left;
681 parent->balance += 1;
682 }
683 else
684 {
685 parent->right_child = FALSE;
686 parent->right = node->right;
687 parent->balance -= 1;
688 }
689 }
690 else /* node has a right child */
691 {
692 GTreeNode *tmp = g_tree_node_next (node);
693 tmp->left = node->left;
694  
695 if (!parent)
696 tree->root = node->right;
697 else if (left_node)
698 {
699 parent->left = node->right;
700 parent->balance += 1;
701 }
702 else
703 {
704 parent->right = node->right;
705 parent->balance -= 1;
706 }
707 }
708 }
709 else /* node has a left child */
710 {
711 if (!node->right_child)
712 {
713 GTreeNode *tmp = g_tree_node_previous (node);
714 tmp->right = node->right;
715  
716 if (parent == NULL)
717 tree->root = node->left;
718 else if (left_node)
719 {
720 parent->left = node->left;
721 parent->balance += 1;
722 }
723 else
724 {
725 parent->right = node->left;
726 parent->balance -= 1;
727 }
728 }
729 else /* node has a both children (pant, pant!) */
730 {
731 GTreeNode *prev = node->left;
732 GTreeNode *next = node->right;
733 GTreeNode *nextp = node;
734 int old_idx = idx + 1;
735 idx++;
736  
737 /* path[idx] == parent */
738 /* find the immediately next node (and its parent) */
739 while (next->left_child)
740 {
741 path[++idx] = nextp = next;
742 next = next->left;
743 }
744  
745 path[old_idx] = next;
746 balance = path[idx];
747  
748 /* remove 'next' from the tree */
749 if (nextp != node)
750 {
751 if (next->right_child)
752 nextp->left = next->right;
753 else
754 nextp->left_child = FALSE;
755 nextp->balance += 1;
756  
757 next->right_child = TRUE;
758 next->right = node->right;
759 }
760 else
761 node->balance -= 1;
762  
763 /* set the prev to point to the right place */
764 while (prev->right_child)
765 prev = prev->right;
766 prev->right = next;
767  
768 /* prepare 'next' to replace 'node' */
769 next->left_child = TRUE;
770 next->left = node->left;
771 next->balance = node->balance;
772  
773 if (!parent)
774 tree->root = next;
775 else if (left_node)
776 parent->left = next;
777 else
778 parent->right = next;
779 }
780 }
781  
782 /* restore balance */
783 if (balance)
784 while (1)
785 {
786 GTreeNode *bparent = path[--idx];
787 g_assert (!bparent || bparent->left == balance || bparent->right == balance);
788 left_node = (bparent && balance == bparent->left);
789  
790 if(balance->balance < -1 || balance->balance > 1)
791 {
792 balance = g_tree_node_balance (balance);
793 if (!bparent)
794 tree->root = balance;
795 else if (left_node)
796 bparent->left = balance;
797 else
798 bparent->right = balance;
799 }
800  
801 if (balance->balance != 0 || !bparent)
802 break;
803  
804 if (left_node)
805 bparent->balance += 1;
806 else
807 bparent->balance -= 1;
808  
809 balance = bparent;
810 }
811  
812 if (!steal)
813 {
814 if (tree->key_destroy_func)
815 tree->key_destroy_func (node->key);
816 if (tree->value_destroy_func)
817 tree->value_destroy_func (node->value);
818 }
819  
820 g_slice_free (GTreeNode, node);
821  
822 tree->nnodes--;
823  
824 return TRUE;
825 }
826  
827 /**
828 * g_tree_lookup:
829 * @tree: a #GTree
830 * @key: the key to look up
831 *
832 * Gets the value corresponding to the given key. Since a #GTree is
833 * automatically balanced as key/value pairs are added, key lookup
834 * is O(log n) (where n is the number of key/value pairs in the tree).
835 *
836 * Returns: the value corresponding to the key, or %NULL
837 * if the key was not found
838 */
839 gpointer
840 g_tree_lookup (GTree *tree,
841 gconstpointer key)
842 {
843 GTreeNode *node;
844  
845 g_return_val_if_fail (tree != NULL, NULL);
846  
847 node = g_tree_find_node (tree, key);
848  
849 return node ? node->value : NULL;
850 }
851  
852 /**
853 * g_tree_lookup_extended:
854 * @tree: a #GTree
855 * @lookup_key: the key to look up
856 * @orig_key: (optional) (nullable): returns the original key
857 * @value: (optional) (nullable): returns the value associated with the key
858 *
859 * Looks up a key in the #GTree, returning the original key and the
860 * associated value. This is useful if you need to free the memory
861 * allocated for the original key, for example before calling
862 * g_tree_remove().
863 *
864 * Returns: %TRUE if the key was found in the #GTree
865 */
866 gboolean
867 g_tree_lookup_extended (GTree *tree,
868 gconstpointer lookup_key,
869 gpointer *orig_key,
870 gpointer *value)
871 {
872 GTreeNode *node;
873  
874 g_return_val_if_fail (tree != NULL, FALSE);
875  
876 node = g_tree_find_node (tree, lookup_key);
877  
878 if (node)
879 {
880 if (orig_key)
881 *orig_key = node->key;
882 if (value)
883 *value = node->value;
884 return TRUE;
885 }
886 else
887 return FALSE;
888 }
889  
890 /**
891 * g_tree_foreach:
892 * @tree: a #GTree
893 * @func: the function to call for each node visited.
894 * If this function returns %TRUE, the traversal is stopped.
895 * @user_data: user data to pass to the function
896 *
897 * Calls the given function for each of the key/value pairs in the #GTree.
898 * The function is passed the key and value of each pair, and the given
899 * @data parameter. The tree is traversed in sorted order.
900 *
901 * The tree may not be modified while iterating over it (you can't
902 * add/remove items). To remove all items matching a predicate, you need
903 * to add each item to a list in your #GTraverseFunc as you walk over
904 * the tree, then walk the list and remove each item.
905 */
906 void
907 g_tree_foreach (GTree *tree,
908 GTraverseFunc func,
909 gpointer user_data)
910 {
911 GTreeNode *node;
912  
913 g_return_if_fail (tree != NULL);
914  
915 if (!tree->root)
916 return;
917  
918 node = g_tree_first_node (tree);
919  
920 while (node)
921 {
922 if ((*func) (node->key, node->value, user_data))
923 break;
924  
925 node = g_tree_node_next (node);
926 }
927 }
928  
929 /**
930 * g_tree_traverse:
931 * @tree: a #GTree
932 * @traverse_func: the function to call for each node visited. If this
933 * function returns %TRUE, the traversal is stopped.
934 * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
935 * %G_PRE_ORDER and %G_POST_ORDER
936 * @user_data: user data to pass to the function
937 *
938 * Calls the given function for each node in the #GTree.
939 *
940 * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary.
941 * If you just want to visit all nodes in sorted order, use
942 * g_tree_foreach() instead. If you really need to visit nodes in
943 * a different order, consider using an [n-ary tree][glib-N-ary-Trees].
944 */
945 /**
946 * GTraverseFunc:
947 * @key: a key of a #GTree node
948 * @value: the value corresponding to the key
949 * @data: user data passed to g_tree_traverse()
950 *
951 * Specifies the type of function passed to g_tree_traverse(). It is
952 * passed the key and value of each node, together with the @user_data
953 * parameter passed to g_tree_traverse(). If the function returns
954 * %TRUE, the traversal is stopped.
955 *
956 * Returns: %TRUE to stop the traversal
957 */
958 void
959 g_tree_traverse (GTree *tree,
960 GTraverseFunc traverse_func,
961 GTraverseType traverse_type,
962 gpointer user_data)
963 {
964 g_return_if_fail (tree != NULL);
965  
966 if (!tree->root)
967 return;
968  
969 switch (traverse_type)
970 {
971 case G_PRE_ORDER:
972 g_tree_node_pre_order (tree->root, traverse_func, user_data);
973 break;
974  
975 case G_IN_ORDER:
976 g_tree_node_in_order (tree->root, traverse_func, user_data);
977 break;
978  
979 case G_POST_ORDER:
980 g_tree_node_post_order (tree->root, traverse_func, user_data);
981 break;
982  
983 case G_LEVEL_ORDER:
984 g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
985 break;
986 }
987 }
988  
989 /**
990 * g_tree_search:
991 * @tree: a #GTree
992 * @search_func: a function used to search the #GTree
993 * @user_data: the data passed as the second argument to @search_func
994 *
995 * Searches a #GTree using @search_func.
996 *
997 * The @search_func is called with a pointer to the key of a key/value
998 * pair in the tree, and the passed in @user_data. If @search_func returns
999 * 0 for a key/value pair, then the corresponding value is returned as
1000 * the result of g_tree_search(). If @search_func returns -1, searching
1001 * will proceed among the key/value pairs that have a smaller key; if
1002 * @search_func returns 1, searching will proceed among the key/value
1003 * pairs that have a larger key.
1004 *
1005 * Returns: the value corresponding to the found key, or %NULL
1006 * if the key was not found
1007 */
1008 gpointer
1009 g_tree_search (GTree *tree,
1010 GCompareFunc search_func,
1011 gconstpointer user_data)
1012 {
1013 g_return_val_if_fail (tree != NULL, NULL);
1014  
1015 if (tree->root)
1016 return g_tree_node_search (tree->root, search_func, user_data);
1017 else
1018 return NULL;
1019 }
1020  
1021 /**
1022 * g_tree_height:
1023 * @tree: a #GTree
1024 *
1025 * Gets the height of a #GTree.
1026 *
1027 * If the #GTree contains no nodes, the height is 0.
1028 * If the #GTree contains only one root node the height is 1.
1029 * If the root node has children the height is 2, etc.
1030 *
1031 * Returns: the height of @tree
1032 */
1033 gint
1034 g_tree_height (GTree *tree)
1035 {
1036 GTreeNode *node;
1037 gint height;
1038  
1039 g_return_val_if_fail (tree != NULL, 0);
1040  
1041 if (!tree->root)
1042 return 0;
1043  
1044 height = 0;
1045 node = tree->root;
1046  
1047 while (1)
1048 {
1049 height += 1 + MAX(node->balance, 0);
1050  
1051 if (!node->left_child)
1052 return height;
1053  
1054 node = node->left;
1055 }
1056 }
1057  
1058 /**
1059 * g_tree_nnodes:
1060 * @tree: a #GTree
1061 *
1062 * Gets the number of nodes in a #GTree.
1063 *
1064 * Returns: the number of nodes in @tree
1065 */
1066 gint
1067 g_tree_nnodes (GTree *tree)
1068 {
1069 g_return_val_if_fail (tree != NULL, 0);
1070  
1071 return tree->nnodes;
1072 }
1073  
1074 static GTreeNode *
1075 g_tree_node_balance (GTreeNode *node)
1076 {
1077 if (node->balance < -1)
1078 {
1079 if (node->left->balance > 0)
1080 node->left = g_tree_node_rotate_left (node->left);
1081 node = g_tree_node_rotate_right (node);
1082 }
1083 else if (node->balance > 1)
1084 {
1085 if (node->right->balance < 0)
1086 node->right = g_tree_node_rotate_right (node->right);
1087 node = g_tree_node_rotate_left (node);
1088 }
1089  
1090 return node;
1091 }
1092  
1093 static GTreeNode *
1094 g_tree_find_node (GTree *tree,
1095 gconstpointer key)
1096 {
1097 GTreeNode *node;
1098 gint cmp;
1099  
1100 node = tree->root;
1101 if (!node)
1102 return NULL;
1103  
1104 while (1)
1105 {
1106 cmp = tree->key_compare (key, node->key, tree->key_compare_data);
1107 if (cmp == 0)
1108 return node;
1109 else if (cmp < 0)
1110 {
1111 if (!node->left_child)
1112 return NULL;
1113  
1114 node = node->left;
1115 }
1116 else
1117 {
1118 if (!node->right_child)
1119 return NULL;
1120  
1121 node = node->right;
1122 }
1123 }
1124 }
1125  
1126 static gint
1127 g_tree_node_pre_order (GTreeNode *node,
1128 GTraverseFunc traverse_func,
1129 gpointer data)
1130 {
1131 if ((*traverse_func) (node->key, node->value, data))
1132 return TRUE;
1133  
1134 if (node->left_child)
1135 {
1136 if (g_tree_node_pre_order (node->left, traverse_func, data))
1137 return TRUE;
1138 }
1139  
1140 if (node->right_child)
1141 {
1142 if (g_tree_node_pre_order (node->right, traverse_func, data))
1143 return TRUE;
1144 }
1145  
1146 return FALSE;
1147 }
1148  
1149 static gint
1150 g_tree_node_in_order (GTreeNode *node,
1151 GTraverseFunc traverse_func,
1152 gpointer data)
1153 {
1154 if (node->left_child)
1155 {
1156 if (g_tree_node_in_order (node->left, traverse_func, data))
1157 return TRUE;
1158 }
1159  
1160 if ((*traverse_func) (node->key, node->value, data))
1161 return TRUE;
1162  
1163 if (node->right_child)
1164 {
1165 if (g_tree_node_in_order (node->right, traverse_func, data))
1166 return TRUE;
1167 }
1168  
1169 return FALSE;
1170 }
1171  
1172 static gint
1173 g_tree_node_post_order (GTreeNode *node,
1174 GTraverseFunc traverse_func,
1175 gpointer data)
1176 {
1177 if (node->left_child)
1178 {
1179 if (g_tree_node_post_order (node->left, traverse_func, data))
1180 return TRUE;
1181 }
1182  
1183 if (node->right_child)
1184 {
1185 if (g_tree_node_post_order (node->right, traverse_func, data))
1186 return TRUE;
1187 }
1188  
1189 if ((*traverse_func) (node->key, node->value, data))
1190 return TRUE;
1191  
1192 return FALSE;
1193 }
1194  
1195 static gpointer
1196 g_tree_node_search (GTreeNode *node,
1197 GCompareFunc search_func,
1198 gconstpointer data)
1199 {
1200 gint dir;
1201  
1202 if (!node)
1203 return NULL;
1204  
1205 while (1)
1206 {
1207 dir = (* search_func) (node->key, data);
1208 if (dir == 0)
1209 return node->value;
1210 else if (dir < 0)
1211 {
1212 if (!node->left_child)
1213 return NULL;
1214  
1215 node = node->left;
1216 }
1217 else
1218 {
1219 if (!node->right_child)
1220 return NULL;
1221  
1222 node = node->right;
1223 }
1224 }
1225 }
1226  
1227 static GTreeNode *
1228 g_tree_node_rotate_left (GTreeNode *node)
1229 {
1230 GTreeNode *right;
1231 gint a_bal;
1232 gint b_bal;
1233  
1234 right = node->right;
1235  
1236 if (right->left_child)
1237 node->right = right->left;
1238 else
1239 {
1240 node->right_child = FALSE;
1241 right->left_child = TRUE;
1242 }
1243 right->left = node;
1244  
1245 a_bal = node->balance;
1246 b_bal = right->balance;
1247  
1248 if (b_bal <= 0)
1249 {
1250 if (a_bal >= 1)
1251 right->balance = b_bal - 1;
1252 else
1253 right->balance = a_bal + b_bal - 2;
1254 node->balance = a_bal - 1;
1255 }
1256 else
1257 {
1258 if (a_bal <= b_bal)
1259 right->balance = a_bal - 2;
1260 else
1261 right->balance = b_bal - 1;
1262 node->balance = a_bal - b_bal - 1;
1263 }
1264  
1265 return right;
1266 }
1267  
1268 static GTreeNode *
1269 g_tree_node_rotate_right (GTreeNode *node)
1270 {
1271 GTreeNode *left;
1272 gint a_bal;
1273 gint b_bal;
1274  
1275 left = node->left;
1276  
1277 if (left->right_child)
1278 node->left = left->right;
1279 else
1280 {
1281 node->left_child = FALSE;
1282 left->right_child = TRUE;
1283 }
1284 left->right = node;
1285  
1286 a_bal = node->balance;
1287 b_bal = left->balance;
1288  
1289 if (b_bal <= 0)
1290 {
1291 if (b_bal > a_bal)
1292 left->balance = b_bal + 1;
1293 else
1294 left->balance = a_bal + 2;
1295 node->balance = a_bal - b_bal + 1;
1296 }
1297 else
1298 {
1299 if (a_bal <= -1)
1300 left->balance = b_bal + 1;
1301 else
1302 left->balance = a_bal + b_bal + 2;
1303 node->balance = a_bal + 1;
1304 }
1305  
1306 return left;
1307 }
1308  
1309 #ifdef G_TREE_DEBUG
1310 static gint
1311 g_tree_node_height (GTreeNode *node)
1312 {
1313 gint left_height;
1314 gint right_height;
1315  
1316 if (node)
1317 {
1318 left_height = 0;
1319 right_height = 0;
1320  
1321 if (node->left_child)
1322 left_height = g_tree_node_height (node->left);
1323  
1324 if (node->right_child)
1325 right_height = g_tree_node_height (node->right);
1326  
1327 return MAX (left_height, right_height) + 1;
1328 }
1329  
1330 return 0;
1331 }
1332  
1333 static void
1334 g_tree_node_check (GTreeNode *node)
1335 {
1336 gint left_height;
1337 gint right_height;
1338 gint balance;
1339 GTreeNode *tmp;
1340  
1341 if (node)
1342 {
1343 if (node->left_child)
1344 {
1345 tmp = g_tree_node_previous (node);
1346 g_assert (tmp->right == node);
1347 }
1348  
1349 if (node->right_child)
1350 {
1351 tmp = g_tree_node_next (node);
1352 g_assert (tmp->left == node);
1353 }
1354  
1355 left_height = 0;
1356 right_height = 0;
1357  
1358 if (node->left_child)
1359 left_height = g_tree_node_height (node->left);
1360 if (node->right_child)
1361 right_height = g_tree_node_height (node->right);
1362  
1363 balance = right_height - left_height;
1364 g_assert (balance == node->balance);
1365  
1366 if (node->left_child)
1367 g_tree_node_check (node->left);
1368 if (node->right_child)
1369 g_tree_node_check (node->right);
1370 }
1371 }
1372  
1373 static void
1374 g_tree_node_dump (GTreeNode *node,
1375 gint indent)
1376 {
1377 g_print ("%*s%c\n", indent, "", *(char *)node->key);
1378  
1379 if (node->left_child)
1380 g_tree_node_dump (node->left, indent + 2);
1381 else if (node->left)
1382 g_print ("%*s<%c\n", indent + 2, "", *(char *)node->left->key);
1383  
1384 if (node->right_child)
1385 g_tree_node_dump (node->right, indent + 2);
1386 else if (node->right)
1387 g_print ("%*s>%c\n", indent + 2, "", *(char *)node->right->key);
1388 }
1389  
1390  
1391 void
1392 g_tree_dump (GTree *tree)
1393 {
1394 if (tree->root)
1395 g_tree_node_dump (tree->root, 0);
1396 }
1397 #endif