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 Lesser 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 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser 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.
24 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
25 * file for a list of people on the GLib Team. See the ChangeLog
26 * files for a list of changes. These files are distributed with
27 * GLib at ftp://ftp.gtk.org/pub/gtk/.
39 void g_node_push_allocator (gpointer dummy) { /* present for binary compat only */ }
40 void g_node_pop_allocator (void) { /* present for binary compat only */ }
42 #define g_node_alloc0() g_slice_new0 (GNode)
43 #define g_node_free(node) g_slice_free (GNode, node)
45 /* --- functions --- */
47 g_node_new (gpointer data)
49 GNode *node = g_node_alloc0();
55 g_nodes_free (GNode *node)
59 GNode *next = node->next;
61 g_nodes_free (node->children);
68 g_node_destroy (GNode *root)
70 g_return_if_fail (root != NULL);
72 if (!G_NODE_IS_ROOT (root))
79 g_node_unlink (GNode *node)
81 g_return_if_fail (node != NULL);
84 node->prev->next = node->next;
85 else if (node->parent)
86 node->parent->children = node->next;
90 node->next->prev = node->prev;
99 * @copy_func: the function which is called to copy the data inside each node,
100 * or %NULL to use the original data.
101 * @data: data to pass to @copy_func
103 * Recursively copies a #GNode and its data.
105 * Return value: a new #GNode containing copies of the data in @node.
110 g_node_copy_deep (GNode *node,
114 GNode *new_node = NULL;
116 if (copy_func == NULL)
117 return g_node_copy (node);
121 GNode *child, *new_child;
123 new_node = g_node_new (copy_func (node->data, data));
125 for (child = g_node_last_child (node); child; child = child->prev)
127 new_child = g_node_copy_deep (child, copy_func, data);
128 g_node_prepend (new_node, new_child);
136 g_node_copy (GNode *node)
138 GNode *new_node = NULL;
144 new_node = g_node_new (node->data);
146 for (child = g_node_last_child (node); child; child = child->prev)
147 g_node_prepend (new_node, g_node_copy (child));
154 g_node_insert (GNode *parent,
158 g_return_val_if_fail (parent != NULL, node);
159 g_return_val_if_fail (node != NULL, node);
160 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
163 return g_node_insert_before (parent,
164 g_node_nth_child (parent, position),
166 else if (position == 0)
167 return g_node_prepend (parent, node);
168 else /* if (position < 0) */
169 return g_node_append (parent, node);
173 g_node_insert_before (GNode *parent,
177 g_return_val_if_fail (parent != NULL, node);
178 g_return_val_if_fail (node != NULL, node);
179 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
181 g_return_val_if_fail (sibling->parent == parent, node);
183 node->parent = parent;
189 node->prev = sibling->prev;
190 node->prev->next = node;
191 node->next = sibling;
192 sibling->prev = node;
196 node->parent->children = node;
197 node->next = sibling;
198 sibling->prev = node;
203 if (parent->children)
205 sibling = parent->children;
206 while (sibling->next)
207 sibling = sibling->next;
208 node->prev = sibling;
209 sibling->next = node;
212 node->parent->children = node;
219 g_node_insert_after (GNode *parent,
223 g_return_val_if_fail (parent != NULL, node);
224 g_return_val_if_fail (node != NULL, node);
225 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
227 g_return_val_if_fail (sibling->parent == parent, node);
229 node->parent = parent;
235 sibling->next->prev = node;
237 node->next = sibling->next;
238 node->prev = sibling;
239 sibling->next = node;
243 if (parent->children)
245 node->next = parent->children;
246 parent->children->prev = node;
248 parent->children = node;
255 g_node_prepend (GNode *parent,
258 g_return_val_if_fail (parent != NULL, node);
260 return g_node_insert_before (parent, parent->children, node);
264 g_node_get_root (GNode *node)
266 g_return_val_if_fail (node != NULL, NULL);
275 g_node_is_ancestor (GNode *node,
278 g_return_val_if_fail (node != NULL, FALSE);
279 g_return_val_if_fail (descendant != NULL, FALSE);
283 if (descendant->parent == node)
286 descendant = descendant->parent;
292 /* returns 1 for root, 2 for first level children,
293 * 3 for children's children...
296 g_node_depth (GNode *node)
298 register guint depth = 0;
310 g_node_reverse_children (GNode *node)
315 g_return_if_fail (node != NULL);
317 child = node->children;
323 last->next = last->prev;
326 node->children = last;
330 g_node_max_height (GNode *root)
332 register GNode *child;
333 register guint max_height = 0;
338 child = root->children;
341 register guint tmp_height;
343 tmp_height = g_node_max_height (child);
344 if (tmp_height > max_height)
345 max_height = tmp_height;
349 return max_height + 1;
353 g_node_traverse_pre_order (GNode *node,
354 GTraverseFlags flags,
355 GNodeTraverseFunc func,
362 if ((flags & G_TRAVERSE_NON_LEAFS) &&
366 child = node->children;
369 register GNode *current;
372 child = current->next;
373 if (g_node_traverse_pre_order (current, flags, func, data))
377 else if ((flags & G_TRAVERSE_LEAFS) &&
385 g_node_depth_traverse_pre_order (GNode *node,
386 GTraverseFlags flags,
388 GNodeTraverseFunc func,
395 if ((flags & G_TRAVERSE_NON_LEAFS) &&
403 child = node->children;
406 register GNode *current;
409 child = current->next;
410 if (g_node_depth_traverse_pre_order (current, flags, depth, func, data))
414 else if ((flags & G_TRAVERSE_LEAFS) &&
422 g_node_traverse_post_order (GNode *node,
423 GTraverseFlags flags,
424 GNodeTraverseFunc func,
431 child = node->children;
434 register GNode *current;
437 child = current->next;
438 if (g_node_traverse_post_order (current, flags, func, data))
442 if ((flags & G_TRAVERSE_NON_LEAFS) &&
447 else if ((flags & G_TRAVERSE_LEAFS) &&
455 g_node_depth_traverse_post_order (GNode *node,
456 GTraverseFlags flags,
458 GNodeTraverseFunc func,
468 child = node->children;
471 register GNode *current;
474 child = current->next;
475 if (g_node_depth_traverse_post_order (current, flags, depth, func, data))
480 if ((flags & G_TRAVERSE_NON_LEAFS) &&
485 else if ((flags & G_TRAVERSE_LEAFS) &&
493 g_node_traverse_in_order (GNode *node,
494 GTraverseFlags flags,
495 GNodeTraverseFunc func,
501 register GNode *current;
503 child = node->children;
505 child = current->next;
507 if (g_node_traverse_in_order (current, flags, func, data))
510 if ((flags & G_TRAVERSE_NON_LEAFS) &&
517 child = current->next;
518 if (g_node_traverse_in_order (current, flags, func, data))
522 else if ((flags & G_TRAVERSE_LEAFS) &&
530 g_node_depth_traverse_in_order (GNode *node,
531 GTraverseFlags flags,
533 GNodeTraverseFunc func,
542 register GNode *current;
544 child = node->children;
546 child = current->next;
548 if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
551 if ((flags & G_TRAVERSE_NON_LEAFS) &&
558 child = current->next;
559 if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
563 else if ((flags & G_TRAVERSE_NON_LEAFS) &&
567 else if ((flags & G_TRAVERSE_LEAFS) &&
575 g_node_traverse_level (GNode *node,
576 GTraverseFlags flags,
578 GNodeTraverseFunc func,
580 gboolean *more_levels)
587 return (flags & G_TRAVERSE_NON_LEAFS) && func (node, data);
591 return (flags & G_TRAVERSE_LEAFS) && func (node, data);
596 node = node->children;
600 if (g_node_traverse_level (node, flags, level - 1, func, data, more_levels))
611 g_node_depth_traverse_level (GNode *node,
612 GTraverseFlags flags,
614 GNodeTraverseFunc func,
618 gboolean more_levels;
621 while (level != depth)
624 if (g_node_traverse_level (node, flags, level, func, data, &more_levels))
634 g_node_traverse (GNode *root,
636 GTraverseFlags flags,
638 GNodeTraverseFunc func,
641 g_return_if_fail (root != NULL);
642 g_return_if_fail (func != NULL);
643 g_return_if_fail (order <= G_LEVEL_ORDER);
644 g_return_if_fail (flags <= G_TRAVERSE_MASK);
645 g_return_if_fail (depth == -1 || depth > 0);
651 g_node_traverse_pre_order (root, flags, func, data);
653 g_node_depth_traverse_pre_order (root, flags, depth, func, data);
657 g_node_traverse_post_order (root, flags, func, data);
659 g_node_depth_traverse_post_order (root, flags, depth, func, data);
663 g_node_traverse_in_order (root, flags, func, data);
665 g_node_depth_traverse_in_order (root, flags, depth, func, data);
668 g_node_depth_traverse_level (root, flags, depth, func, data);
674 g_node_find_func (GNode *node,
677 register gpointer *d = data;
679 if (*d != node->data)
688 g_node_find (GNode *root,
690 GTraverseFlags flags,
695 g_return_val_if_fail (root != NULL, NULL);
696 g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
697 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
702 g_node_traverse (root, order, flags, -1, g_node_find_func, d);
708 g_node_count_func (GNode *node,
709 GTraverseFlags flags,
716 if (flags & G_TRAVERSE_NON_LEAFS)
719 child = node->children;
722 g_node_count_func (child, flags, n);
726 else if (flags & G_TRAVERSE_LEAFS)
731 g_node_n_nodes (GNode *root,
732 GTraverseFlags flags)
736 g_return_val_if_fail (root != NULL, 0);
737 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
739 g_node_count_func (root, flags, &n);
745 g_node_last_child (GNode *node)
747 g_return_val_if_fail (node != NULL, NULL);
749 node = node->children;
758 g_node_nth_child (GNode *node,
761 g_return_val_if_fail (node != NULL, NULL);
763 node = node->children;
765 while ((n-- > 0) && node)
772 g_node_n_children (GNode *node)
776 g_return_val_if_fail (node != NULL, 0);
778 node = node->children;
789 g_node_find_child (GNode *node,
790 GTraverseFlags flags,
793 g_return_val_if_fail (node != NULL, NULL);
794 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
796 node = node->children;
799 if (node->data == data)
801 if (G_NODE_IS_LEAF (node))
803 if (flags & G_TRAVERSE_LEAFS)
808 if (flags & G_TRAVERSE_NON_LEAFS)
819 g_node_child_position (GNode *node,
822 register guint n = 0;
824 g_return_val_if_fail (node != NULL, -1);
825 g_return_val_if_fail (child != NULL, -1);
826 g_return_val_if_fail (child->parent == node, -1);
828 node = node->children;
841 g_node_child_index (GNode *node,
844 register guint n = 0;
846 g_return_val_if_fail (node != NULL, -1);
848 node = node->children;
851 if (node->data == data)
861 g_node_first_sibling (GNode *node)
863 g_return_val_if_fail (node != NULL, NULL);
866 return node->parent->children;
875 g_node_last_sibling (GNode *node)
877 g_return_val_if_fail (node != NULL, NULL);
886 g_node_children_foreach (GNode *node,
887 GTraverseFlags flags,
888 GNodeForeachFunc func,
891 g_return_if_fail (node != NULL);
892 g_return_if_fail (flags <= G_TRAVERSE_MASK);
893 g_return_if_fail (func != NULL);
895 node = node->children;
898 register GNode *current;
901 node = current->next;
902 if (G_NODE_IS_LEAF (current))
904 if (flags & G_TRAVERSE_LEAFS)
905 func (current, data);
909 if (flags & G_TRAVERSE_NON_LEAFS)
910 func (current, data);
916 #include "galiasdef.c"