1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
4 * GNode: N-way tree implementation.
5 * Copyright (C) 1998 Tim Janik
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Library General Public
9 * License as published by the Free Software Foundation; either
10 * version 2 of the License, or (at your option) any later version.
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Library General Public License for more details.
17 * You should have received a copy of the GNU Library General Public
18 * License along with this library; if not, write to the
19 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
20 * Boston, MA 02111-1307, USA.
25 #define KEEP_NODES (1024)
28 /* --- variables --- */
29 static GMemChunk *g_tree_node_chunk = NULL;
30 static GNode *free_nodes = NULL;
31 static guint n_free_nodes = 0;
34 /* --- functions --- */
36 g_node_new (gpointer data)
40 if (!g_tree_node_chunk)
41 g_tree_node_chunk = g_mem_chunk_create (GNode, 1024, G_ALLOC_AND_FREE);
46 free_nodes = free_nodes->next;
50 node = g_chunk_new (GNode, g_tree_node_chunk);
55 node->children = NULL;
62 g_node_free (GNode *parent)
66 node = parent->children;
70 register GNode *free_node;
73 node = free_node->next;
74 g_node_free (free_node);
77 if (n_free_nodes < KEEP_NODES)
79 parent->next = free_nodes;
84 g_chunk_free (parent, g_tree_node_chunk);
88 g_node_destroy (GNode *root)
90 g_return_if_fail (root != NULL);
92 if (!G_NODE_IS_ROOT (root))
99 g_node_unlink (GNode *node)
101 g_return_if_fail (node != NULL);
104 node->prev->next = node->next;
105 else if (node->parent)
106 node->parent->children = node->next;
110 node->next->prev = node->prev;
117 g_node_insert (GNode *parent,
121 g_return_if_fail (parent != NULL);
122 g_return_if_fail (node != NULL);
123 g_return_if_fail (G_NODE_IS_ROOT (node));
126 g_node_insert_before (parent,
127 g_node_nth_child (parent, position),
129 else if (position == 0)
130 g_node_prepend (parent, node);
131 else if (position < 0)
132 g_node_append (parent, node);
136 g_node_insert_before (GNode *parent,
140 g_return_if_fail (parent != NULL);
141 g_return_if_fail (node != NULL);
142 g_return_if_fail (G_NODE_IS_ROOT (node));
144 g_return_if_fail (sibling->parent == parent);
146 node->parent = parent;
152 node->prev = sibling->prev;
153 node->prev->next = node;
154 node->next = sibling;
155 sibling->prev = node;
159 node->parent->children = node;
160 node->next = sibling;
161 sibling->prev = node;
166 if (parent->children)
168 sibling = parent->children;
169 while (sibling->next)
170 sibling = sibling->next;
171 node->prev = sibling;
172 sibling->next = node;
175 node->parent->children = node;
180 g_node_prepend (GNode *parent,
183 g_return_if_fail (parent != NULL);
185 g_node_insert_before (parent, parent->children, node);
189 g_node_get_root (GNode *node)
191 g_return_val_if_fail (node != NULL, NULL);
200 g_node_is_ancestor (GNode *node,
203 g_return_val_if_fail (node != NULL, FALSE);
204 g_return_val_if_fail (descendant != NULL, FALSE);
208 if (descendant->parent == node)
211 descendant = descendant->parent;
217 /* returns 1 for root, 2 for first level children,
218 * 3 for children's children...
221 g_node_depth (GNode *node)
223 register guint depth = 0;
235 g_node_reverse_children (GNode *node)
240 g_return_if_fail (node != NULL);
242 child = node->children;
248 last->next = last->prev;
251 node->children = last;
255 g_node_max_height (GNode *root)
257 register GNode *child;
258 register guint max_height = 0;
263 child = root->children;
266 register guint tmp_height;
268 tmp_height = g_node_max_height (child);
269 if (tmp_height > max_height)
270 max_height = tmp_height;
274 return max_height + 1;
278 g_node_traverse_pre_order (GNode *node,
279 GTraverseFlags flags,
280 GNodeTraverseFunc func,
287 if ((flags & G_TRAVERSE_NON_LEAFS) &&
291 child = node->children;
294 register GNode *current;
297 child = current->next;
298 if (g_node_traverse_pre_order (current, flags, func, data))
302 else if ((flags & G_TRAVERSE_LEAFS) &&
310 g_node_depth_traverse_pre_order (GNode *node,
311 GTraverseFlags flags,
313 GNodeTraverseFunc func,
320 if ((flags & G_TRAVERSE_NON_LEAFS) &&
328 child = node->children;
331 register GNode *current;
334 child = current->next;
335 if (g_node_depth_traverse_pre_order (current, flags, depth, func, data))
339 else if ((flags & G_TRAVERSE_LEAFS) &&
347 g_node_traverse_post_order (GNode *node,
348 GTraverseFlags flags,
349 GNodeTraverseFunc func,
356 child = node->children;
359 register GNode *current;
362 child = current->next;
363 if (g_node_traverse_post_order (current, flags, func, data))
367 if ((flags & G_TRAVERSE_NON_LEAFS) &&
372 else if ((flags & G_TRAVERSE_LEAFS) &&
380 g_node_depth_traverse_post_order (GNode *node,
381 GTraverseFlags flags,
383 GNodeTraverseFunc func,
393 child = node->children;
396 register GNode *current;
399 child = current->next;
400 if (g_node_depth_traverse_post_order (current, flags, depth, func, data))
405 if ((flags & G_TRAVERSE_NON_LEAFS) &&
410 else if ((flags & G_TRAVERSE_LEAFS) &&
418 g_node_traverse_in_order (GNode *node,
419 GTraverseFlags flags,
420 GNodeTraverseFunc func,
426 register GNode *current;
428 child = node->children;
430 child = current->next;
432 if (g_node_traverse_in_order (current, flags, func, data))
435 if ((flags & G_TRAVERSE_NON_LEAFS) &&
442 child = current->next;
443 if (g_node_traverse_in_order (current, flags, func, data))
447 else if ((flags & G_TRAVERSE_LEAFS) &&
455 g_node_depth_traverse_in_order (GNode *node,
456 GTraverseFlags flags,
458 GNodeTraverseFunc func,
467 register GNode *current;
469 child = node->children;
471 child = current->next;
473 if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
476 if ((flags & G_TRAVERSE_NON_LEAFS) &&
483 child = current->next;
484 if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
488 else if ((flags & G_TRAVERSE_NON_LEAFS) &&
492 else if ((flags & G_TRAVERSE_LEAFS) &&
500 g_node_traverse_children (GNode *node,
501 GTraverseFlags flags,
502 GNodeTraverseFunc func,
507 child = node->children;
511 register GNode *current;
514 child = current->next;
516 if (current->children)
518 if ((flags & G_TRAVERSE_NON_LEAFS) &&
519 func (current, data))
522 else if ((flags & G_TRAVERSE_LEAFS) &&
523 func (current, data))
527 child = node->children;
531 register GNode *current;
534 child = current->next;
536 if (current->children &&
537 g_node_traverse_children (current, flags, func, data))
545 g_node_depth_traverse_children (GNode *node,
546 GTraverseFlags flags,
548 GNodeTraverseFunc func,
553 child = node->children;
557 register GNode *current;
560 child = current->next;
562 if (current->children)
564 if ((flags & G_TRAVERSE_NON_LEAFS) &&
565 func (current, data))
568 else if ((flags & G_TRAVERSE_LEAFS) &&
569 func (current, data))
577 child = node->children;
581 register GNode *current;
584 child = current->next;
586 if (current->children &&
587 g_node_depth_traverse_children (current, flags, depth, func, data))
595 g_node_traverse (GNode *root,
597 GTraverseFlags flags,
599 GNodeTraverseFunc func,
602 g_return_if_fail (root != NULL);
603 g_return_if_fail (func != NULL);
604 g_return_if_fail (order <= G_LEVEL_ORDER);
605 g_return_if_fail (flags <= G_TRAVERSE_MASK);
606 g_return_if_fail (depth == -1 || depth > 0);
612 g_node_traverse_pre_order (root, flags, func, data);
614 g_node_depth_traverse_pre_order (root, flags, depth, func, data);
618 g_node_traverse_post_order (root, flags, func, data);
620 g_node_depth_traverse_post_order (root, flags, depth, func, data);
624 g_node_traverse_in_order (root, flags, func, data);
626 g_node_depth_traverse_in_order (root, flags, depth, func, data);
631 if (!((flags & G_TRAVERSE_NON_LEAFS) &&
635 g_node_traverse_children (root, flags, func, data);
640 g_node_depth_traverse_children (root, flags, depth, func, data);
644 else if (flags & G_TRAVERSE_LEAFS)
651 g_node_find_func (GNode *node,
654 register gpointer *d = data;
656 if (*d != node->data)
665 g_node_find (GNode *root,
667 GTraverseFlags flags,
672 g_return_val_if_fail (root != NULL, NULL);
673 g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
674 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
679 g_node_traverse (root, order, flags, -1, g_node_find_func, d);
685 g_node_count_func (GNode *node,
686 GTraverseFlags flags,
693 if (flags & G_TRAVERSE_NON_LEAFS)
696 child = node->children;
699 g_node_count_func (child, flags, n);
703 else if (flags & G_TRAVERSE_LEAFS)
708 g_node_n_nodes (GNode *root,
709 GTraverseFlags flags)
713 g_return_val_if_fail (root != NULL, 0);
714 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
716 g_node_count_func (root, flags, &n);
722 g_node_last_child (GNode *node)
724 g_return_val_if_fail (node != NULL, NULL);
726 node = node->children;
735 g_node_nth_child (GNode *node,
738 g_return_val_if_fail (node != NULL, NULL);
740 node = node->children;
742 while ((n-- > 0) && node)
749 g_node_n_children (GNode *node)
753 g_return_val_if_fail (node != NULL, 0);
755 node = node->children;
766 g_node_find_child (GNode *node,
767 GTraverseFlags flags,
770 g_return_val_if_fail (node != NULL, NULL);
771 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
773 node = node->children;
776 if (node->data == data)
778 if (G_NODE_IS_LEAF (node))
780 if (flags & G_TRAVERSE_LEAFS)
785 if (flags & G_TRAVERSE_NON_LEAFS)
796 g_node_child_position (GNode *node,
799 register guint n = 0;
801 g_return_val_if_fail (node != NULL, -1);
802 g_return_val_if_fail (child != NULL, -1);
803 g_return_val_if_fail (child->parent == node, -1);
805 node = node->children;
818 g_node_child_index (GNode *node,
821 register guint n = 0;
823 g_return_val_if_fail (node != NULL, -1);
825 node = node->children;
828 if (node->data == data)
838 g_node_first_sibling (GNode *node)
840 g_return_val_if_fail (node != NULL, NULL);
849 g_node_last_sibling (GNode *node)
851 g_return_val_if_fail (node != NULL, NULL);
860 g_node_children_foreach (GNode *node,
861 GTraverseFlags flags,
862 GNodeForeachFunc func,
865 g_return_if_fail (node != NULL);
866 g_return_if_fail (flags <= G_TRAVERSE_MASK);
867 g_return_if_fail (func != NULL);
869 node = node->children;
872 register GNode *current;
875 node = current->next;
876 if (G_NODE_IS_LEAF (node))
878 if (flags & G_TRAVERSE_LEAFS)
879 func (current, data);
883 if (flags & G_TRAVERSE_NON_LEAFS)
884 func (current, data);