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 #ifndef DISABLE_MEM_POOLS
42 struct _GAllocator /* from gmem.c */
50 GNode *free_nodes; /* implementation specific */
53 G_LOCK_DEFINE_STATIC (current_allocator);
54 static GAllocator *current_allocator = NULL;
56 /* HOLDS: current_allocator_lock */
58 g_node_validate_allocator (GAllocator *allocator)
60 g_return_if_fail (allocator != NULL);
61 g_return_if_fail (allocator->is_unused == TRUE);
63 if (allocator->type != G_ALLOCATOR_NODE)
65 allocator->type = G_ALLOCATOR_NODE;
66 if (allocator->mem_chunk)
68 g_mem_chunk_destroy (allocator->mem_chunk);
69 allocator->mem_chunk = NULL;
73 if (!allocator->mem_chunk)
75 allocator->mem_chunk = g_mem_chunk_new (allocator->name,
77 sizeof (GNode) * allocator->n_preallocs,
79 allocator->free_nodes = NULL;
82 allocator->is_unused = FALSE;
86 g_node_push_allocator (GAllocator *allocator)
88 G_LOCK (current_allocator);
89 g_node_validate_allocator (allocator);
90 allocator->last = current_allocator;
91 current_allocator = allocator;
92 G_UNLOCK (current_allocator);
96 g_node_pop_allocator (void)
98 G_LOCK (current_allocator);
99 if (current_allocator)
101 GAllocator *allocator;
103 allocator = current_allocator;
104 current_allocator = allocator->last;
105 allocator->last = NULL;
106 allocator->is_unused = TRUE;
108 G_UNLOCK (current_allocator);
112 /* --- functions --- */
114 g_node_new (gpointer data)
118 G_LOCK (current_allocator);
119 if (!current_allocator)
121 GAllocator *allocator = g_allocator_new ("GLib default GNode allocator",
123 g_node_validate_allocator (allocator);
124 allocator->last = NULL;
125 current_allocator = allocator;
127 if (!current_allocator->free_nodes)
128 node = g_chunk_new (GNode, current_allocator->mem_chunk);
131 node = current_allocator->free_nodes;
132 current_allocator->free_nodes = node->next;
134 G_UNLOCK (current_allocator);
140 node->children = NULL;
146 g_nodes_free (GNode *node)
153 if (parent->children)
154 g_nodes_free (parent->children);
156 #ifdef ENABLE_GC_FRIENDLY
159 parent->parent = NULL;
160 parent->children = NULL;
161 #endif /* ENABLE_GC_FRIENDLY */
164 parent = parent->next;
169 G_LOCK (current_allocator);
170 parent->next = current_allocator->free_nodes;
171 current_allocator->free_nodes = node;
172 G_UNLOCK (current_allocator);
174 #else /* DISABLE_MEM_POOLS */
177 g_node_new (gpointer data)
181 node = g_new0 (GNode, 1);
189 g_nodes_free (GNode *root)
197 g_nodes_free (node->children);
205 g_node_destroy (GNode *root)
207 g_return_if_fail (root != NULL);
209 if (!G_NODE_IS_ROOT (root))
210 g_node_unlink (root);
216 g_node_unlink (GNode *node)
218 g_return_if_fail (node != NULL);
221 node->prev->next = node->next;
222 else if (node->parent)
223 node->parent->children = node->next;
227 node->next->prev = node->prev;
236 * @copy_func: the function which is called to copy the data inside each node,
237 * or %NULL to use the original data.
238 * @data: data to pass to @copy_func
240 * Recursively copies a #GNode and its data.
242 * Return value: a new #GNode containing copies of the data in @node.
247 g_node_copy_deep (GNode *node,
251 GNode *new_node = NULL;
253 if (copy_func == NULL)
254 return g_node_copy (node);
258 GNode *child, *new_child;
260 new_node = g_node_new (copy_func (node->data, data));
262 for (child = g_node_last_child (node); child; child = child->prev)
264 new_child = g_node_copy_deep (child, copy_func, data);
265 g_node_prepend (new_node, new_child);
273 g_node_copy (GNode *node)
275 GNode *new_node = NULL;
281 new_node = g_node_new (node->data);
283 for (child = g_node_last_child (node); child; child = child->prev)
284 g_node_prepend (new_node, g_node_copy (child));
291 g_node_insert (GNode *parent,
295 g_return_val_if_fail (parent != NULL, node);
296 g_return_val_if_fail (node != NULL, node);
297 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
300 return g_node_insert_before (parent,
301 g_node_nth_child (parent, position),
303 else if (position == 0)
304 return g_node_prepend (parent, node);
305 else /* if (position < 0) */
306 return g_node_append (parent, node);
310 g_node_insert_before (GNode *parent,
314 g_return_val_if_fail (parent != NULL, node);
315 g_return_val_if_fail (node != NULL, node);
316 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
318 g_return_val_if_fail (sibling->parent == parent, node);
320 node->parent = parent;
326 node->prev = sibling->prev;
327 node->prev->next = node;
328 node->next = sibling;
329 sibling->prev = node;
333 node->parent->children = node;
334 node->next = sibling;
335 sibling->prev = node;
340 if (parent->children)
342 sibling = parent->children;
343 while (sibling->next)
344 sibling = sibling->next;
345 node->prev = sibling;
346 sibling->next = node;
349 node->parent->children = node;
356 g_node_insert_after (GNode *parent,
360 g_return_val_if_fail (parent != NULL, node);
361 g_return_val_if_fail (node != NULL, node);
362 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
364 g_return_val_if_fail (sibling->parent == parent, node);
366 node->parent = parent;
372 sibling->next->prev = node;
374 node->next = sibling->next;
375 node->prev = sibling;
376 sibling->next = node;
380 if (parent->children)
382 node->next = parent->children;
383 parent->children->prev = node;
385 parent->children = node;
392 g_node_prepend (GNode *parent,
395 g_return_val_if_fail (parent != NULL, node);
397 return g_node_insert_before (parent, parent->children, node);
401 g_node_get_root (GNode *node)
403 g_return_val_if_fail (node != NULL, NULL);
412 g_node_is_ancestor (GNode *node,
415 g_return_val_if_fail (node != NULL, FALSE);
416 g_return_val_if_fail (descendant != NULL, FALSE);
420 if (descendant->parent == node)
423 descendant = descendant->parent;
429 /* returns 1 for root, 2 for first level children,
430 * 3 for children's children...
433 g_node_depth (GNode *node)
435 register guint depth = 0;
447 g_node_reverse_children (GNode *node)
452 g_return_if_fail (node != NULL);
454 child = node->children;
460 last->next = last->prev;
463 node->children = last;
467 g_node_max_height (GNode *root)
469 register GNode *child;
470 register guint max_height = 0;
475 child = root->children;
478 register guint tmp_height;
480 tmp_height = g_node_max_height (child);
481 if (tmp_height > max_height)
482 max_height = tmp_height;
486 return max_height + 1;
490 g_node_traverse_pre_order (GNode *node,
491 GTraverseFlags flags,
492 GNodeTraverseFunc func,
499 if ((flags & G_TRAVERSE_NON_LEAFS) &&
503 child = node->children;
506 register GNode *current;
509 child = current->next;
510 if (g_node_traverse_pre_order (current, flags, func, data))
514 else if ((flags & G_TRAVERSE_LEAFS) &&
522 g_node_depth_traverse_pre_order (GNode *node,
523 GTraverseFlags flags,
525 GNodeTraverseFunc func,
532 if ((flags & G_TRAVERSE_NON_LEAFS) &&
540 child = node->children;
543 register GNode *current;
546 child = current->next;
547 if (g_node_depth_traverse_pre_order (current, flags, depth, func, data))
551 else if ((flags & G_TRAVERSE_LEAFS) &&
559 g_node_traverse_post_order (GNode *node,
560 GTraverseFlags flags,
561 GNodeTraverseFunc func,
568 child = node->children;
571 register GNode *current;
574 child = current->next;
575 if (g_node_traverse_post_order (current, flags, func, data))
579 if ((flags & G_TRAVERSE_NON_LEAFS) &&
584 else if ((flags & G_TRAVERSE_LEAFS) &&
592 g_node_depth_traverse_post_order (GNode *node,
593 GTraverseFlags flags,
595 GNodeTraverseFunc func,
605 child = node->children;
608 register GNode *current;
611 child = current->next;
612 if (g_node_depth_traverse_post_order (current, flags, depth, func, data))
617 if ((flags & G_TRAVERSE_NON_LEAFS) &&
622 else if ((flags & G_TRAVERSE_LEAFS) &&
630 g_node_traverse_in_order (GNode *node,
631 GTraverseFlags flags,
632 GNodeTraverseFunc func,
638 register GNode *current;
640 child = node->children;
642 child = current->next;
644 if (g_node_traverse_in_order (current, flags, func, data))
647 if ((flags & G_TRAVERSE_NON_LEAFS) &&
654 child = current->next;
655 if (g_node_traverse_in_order (current, flags, func, data))
659 else if ((flags & G_TRAVERSE_LEAFS) &&
667 g_node_depth_traverse_in_order (GNode *node,
668 GTraverseFlags flags,
670 GNodeTraverseFunc func,
679 register GNode *current;
681 child = node->children;
683 child = current->next;
685 if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
688 if ((flags & G_TRAVERSE_NON_LEAFS) &&
695 child = current->next;
696 if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
700 else if ((flags & G_TRAVERSE_NON_LEAFS) &&
704 else if ((flags & G_TRAVERSE_LEAFS) &&
712 g_node_traverse_level (GNode *node,
713 GTraverseFlags flags,
715 GNodeTraverseFunc func,
717 gboolean *more_levels)
724 return (flags & G_TRAVERSE_NON_LEAFS) && func (node, data);
728 return (flags & G_TRAVERSE_LEAFS) && func (node, data);
733 node = node->children;
737 if (g_node_traverse_level (node, flags, level - 1, func, data, more_levels))
748 g_node_depth_traverse_level (GNode *node,
749 GTraverseFlags flags,
751 GNodeTraverseFunc func,
755 gboolean more_levels;
758 while (level != depth)
761 if (g_node_traverse_level (node, flags, level, func, data, &more_levels))
771 g_node_traverse (GNode *root,
773 GTraverseFlags flags,
775 GNodeTraverseFunc func,
778 g_return_if_fail (root != NULL);
779 g_return_if_fail (func != NULL);
780 g_return_if_fail (order <= G_LEVEL_ORDER);
781 g_return_if_fail (flags <= G_TRAVERSE_MASK);
782 g_return_if_fail (depth == -1 || depth > 0);
788 g_node_traverse_pre_order (root, flags, func, data);
790 g_node_depth_traverse_pre_order (root, flags, depth, func, data);
794 g_node_traverse_post_order (root, flags, func, data);
796 g_node_depth_traverse_post_order (root, flags, depth, func, data);
800 g_node_traverse_in_order (root, flags, func, data);
802 g_node_depth_traverse_in_order (root, flags, depth, func, data);
805 g_node_depth_traverse_level (root, flags, depth, func, data);
811 g_node_find_func (GNode *node,
814 register gpointer *d = data;
816 if (*d != node->data)
825 g_node_find (GNode *root,
827 GTraverseFlags flags,
832 g_return_val_if_fail (root != NULL, NULL);
833 g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
834 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
839 g_node_traverse (root, order, flags, -1, g_node_find_func, d);
845 g_node_count_func (GNode *node,
846 GTraverseFlags flags,
853 if (flags & G_TRAVERSE_NON_LEAFS)
856 child = node->children;
859 g_node_count_func (child, flags, n);
863 else if (flags & G_TRAVERSE_LEAFS)
868 g_node_n_nodes (GNode *root,
869 GTraverseFlags flags)
873 g_return_val_if_fail (root != NULL, 0);
874 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
876 g_node_count_func (root, flags, &n);
882 g_node_last_child (GNode *node)
884 g_return_val_if_fail (node != NULL, NULL);
886 node = node->children;
895 g_node_nth_child (GNode *node,
898 g_return_val_if_fail (node != NULL, NULL);
900 node = node->children;
902 while ((n-- > 0) && node)
909 g_node_n_children (GNode *node)
913 g_return_val_if_fail (node != NULL, 0);
915 node = node->children;
926 g_node_find_child (GNode *node,
927 GTraverseFlags flags,
930 g_return_val_if_fail (node != NULL, NULL);
931 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
933 node = node->children;
936 if (node->data == data)
938 if (G_NODE_IS_LEAF (node))
940 if (flags & G_TRAVERSE_LEAFS)
945 if (flags & G_TRAVERSE_NON_LEAFS)
956 g_node_child_position (GNode *node,
959 register guint n = 0;
961 g_return_val_if_fail (node != NULL, -1);
962 g_return_val_if_fail (child != NULL, -1);
963 g_return_val_if_fail (child->parent == node, -1);
965 node = node->children;
978 g_node_child_index (GNode *node,
981 register guint n = 0;
983 g_return_val_if_fail (node != NULL, -1);
985 node = node->children;
988 if (node->data == data)
998 g_node_first_sibling (GNode *node)
1000 g_return_val_if_fail (node != NULL, NULL);
1003 return node->parent->children;
1012 g_node_last_sibling (GNode *node)
1014 g_return_val_if_fail (node != NULL, NULL);
1023 g_node_children_foreach (GNode *node,
1024 GTraverseFlags flags,
1025 GNodeForeachFunc func,
1028 g_return_if_fail (node != NULL);
1029 g_return_if_fail (flags <= G_TRAVERSE_MASK);
1030 g_return_if_fail (func != NULL);
1032 node = node->children;
1035 register GNode *current;
1038 node = current->next;
1039 if (G_NODE_IS_LEAF (current))
1041 if (flags & G_TRAVERSE_LEAFS)
1042 func (current, data);
1046 if (flags & G_TRAVERSE_NON_LEAFS)
1047 func (current, data);