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/.
38 struct _GAllocator /* from gmem.c */
46 GNode *free_nodes; /* implementation specific */
49 G_LOCK_DEFINE_STATIC (current_allocator);
50 static GAllocator *current_allocator = NULL;
52 /* HOLDS: current_allocator_lock */
54 g_node_validate_allocator (GAllocator *allocator)
56 g_return_if_fail (allocator != NULL);
57 g_return_if_fail (allocator->is_unused == TRUE);
59 if (allocator->type != G_ALLOCATOR_NODE)
61 allocator->type = G_ALLOCATOR_NODE;
62 if (allocator->mem_chunk)
64 g_mem_chunk_destroy (allocator->mem_chunk);
65 allocator->mem_chunk = NULL;
69 if (!allocator->mem_chunk)
71 allocator->mem_chunk = g_mem_chunk_new (allocator->name,
73 sizeof (GNode) * allocator->n_preallocs,
75 allocator->free_nodes = NULL;
78 allocator->is_unused = FALSE;
82 g_node_push_allocator (GAllocator *allocator)
84 G_LOCK (current_allocator);
85 g_node_validate_allocator (allocator);
86 allocator->last = current_allocator;
87 current_allocator = allocator;
88 G_UNLOCK (current_allocator);
92 g_node_pop_allocator (void)
94 G_LOCK (current_allocator);
95 if (current_allocator)
97 GAllocator *allocator;
99 allocator = current_allocator;
100 current_allocator = allocator->last;
101 allocator->last = NULL;
102 allocator->is_unused = TRUE;
104 G_UNLOCK (current_allocator);
108 /* --- functions --- */
110 g_node_new (gpointer data)
114 G_LOCK (current_allocator);
115 if (!current_allocator)
117 GAllocator *allocator = g_allocator_new ("GLib default GNode allocator",
119 g_node_validate_allocator (allocator);
120 allocator->last = NULL;
121 current_allocator = allocator;
123 if (!current_allocator->free_nodes)
124 node = g_chunk_new (GNode, current_allocator->mem_chunk);
127 node = current_allocator->free_nodes;
128 current_allocator->free_nodes = node->next;
130 G_UNLOCK (current_allocator);
136 node->children = NULL;
142 g_nodes_free (GNode *node)
149 if (parent->children)
150 g_nodes_free (parent->children);
152 #ifdef ENABLE_GC_FRIENDLY
155 parent->parent = NULL;
156 parent->children = NULL;
157 #endif /* ENABLE_GC_FRIENDLY */
160 parent = parent->next;
165 G_LOCK (current_allocator);
166 parent->next = current_allocator->free_nodes;
167 current_allocator->free_nodes = node;
168 G_UNLOCK (current_allocator);
172 g_node_destroy (GNode *root)
174 g_return_if_fail (root != NULL);
176 if (!G_NODE_IS_ROOT (root))
177 g_node_unlink (root);
183 g_node_unlink (GNode *node)
185 g_return_if_fail (node != NULL);
188 node->prev->next = node->next;
189 else if (node->parent)
190 node->parent->children = node->next;
194 node->next->prev = node->prev;
201 g_node_copy (GNode *node)
203 GNode *new_node = NULL;
209 new_node = g_node_new (node->data);
211 for (child = g_node_last_child (node); child; child = child->prev)
212 g_node_prepend (new_node, g_node_copy (child));
219 g_node_insert (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);
228 return g_node_insert_before (parent,
229 g_node_nth_child (parent, position),
231 else if (position == 0)
232 return g_node_prepend (parent, node);
233 else /* if (position < 0) */
234 return g_node_append (parent, node);
238 g_node_insert_before (GNode *parent,
242 g_return_val_if_fail (parent != NULL, node);
243 g_return_val_if_fail (node != NULL, node);
244 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
246 g_return_val_if_fail (sibling->parent == parent, node);
248 node->parent = parent;
254 node->prev = sibling->prev;
255 node->prev->next = node;
256 node->next = sibling;
257 sibling->prev = node;
261 node->parent->children = node;
262 node->next = sibling;
263 sibling->prev = node;
268 if (parent->children)
270 sibling = parent->children;
271 while (sibling->next)
272 sibling = sibling->next;
273 node->prev = sibling;
274 sibling->next = node;
277 node->parent->children = node;
284 g_node_insert_after (GNode *parent,
288 g_return_val_if_fail (parent != NULL, node);
289 g_return_val_if_fail (node != NULL, node);
290 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
292 g_return_val_if_fail (sibling->parent == parent, node);
294 node->parent = parent;
300 sibling->next->prev = node;
302 node->next = sibling->next;
303 node->prev = sibling;
304 sibling->next = node;
308 if (parent->children)
310 node->next = parent->children;
311 parent->children->prev = node;
313 parent->children = node;
320 g_node_prepend (GNode *parent,
323 g_return_val_if_fail (parent != NULL, node);
325 return g_node_insert_before (parent, parent->children, node);
329 g_node_get_root (GNode *node)
331 g_return_val_if_fail (node != NULL, NULL);
340 g_node_is_ancestor (GNode *node,
343 g_return_val_if_fail (node != NULL, FALSE);
344 g_return_val_if_fail (descendant != NULL, FALSE);
348 if (descendant->parent == node)
351 descendant = descendant->parent;
357 /* returns 1 for root, 2 for first level children,
358 * 3 for children's children...
361 g_node_depth (GNode *node)
363 register guint depth = 0;
375 g_node_reverse_children (GNode *node)
380 g_return_if_fail (node != NULL);
382 child = node->children;
388 last->next = last->prev;
391 node->children = last;
395 g_node_max_height (GNode *root)
397 register GNode *child;
398 register guint max_height = 0;
403 child = root->children;
406 register guint tmp_height;
408 tmp_height = g_node_max_height (child);
409 if (tmp_height > max_height)
410 max_height = tmp_height;
414 return max_height + 1;
418 g_node_traverse_pre_order (GNode *node,
419 GTraverseFlags flags,
420 GNodeTraverseFunc func,
427 if ((flags & G_TRAVERSE_NON_LEAFS) &&
431 child = node->children;
434 register GNode *current;
437 child = current->next;
438 if (g_node_traverse_pre_order (current, flags, func, data))
442 else if ((flags & G_TRAVERSE_LEAFS) &&
450 g_node_depth_traverse_pre_order (GNode *node,
451 GTraverseFlags flags,
453 GNodeTraverseFunc func,
460 if ((flags & G_TRAVERSE_NON_LEAFS) &&
468 child = node->children;
471 register GNode *current;
474 child = current->next;
475 if (g_node_depth_traverse_pre_order (current, flags, depth, func, data))
479 else if ((flags & G_TRAVERSE_LEAFS) &&
487 g_node_traverse_post_order (GNode *node,
488 GTraverseFlags flags,
489 GNodeTraverseFunc func,
496 child = node->children;
499 register GNode *current;
502 child = current->next;
503 if (g_node_traverse_post_order (current, flags, func, data))
507 if ((flags & G_TRAVERSE_NON_LEAFS) &&
512 else if ((flags & G_TRAVERSE_LEAFS) &&
520 g_node_depth_traverse_post_order (GNode *node,
521 GTraverseFlags flags,
523 GNodeTraverseFunc func,
533 child = node->children;
536 register GNode *current;
539 child = current->next;
540 if (g_node_depth_traverse_post_order (current, flags, depth, func, data))
545 if ((flags & G_TRAVERSE_NON_LEAFS) &&
550 else if ((flags & G_TRAVERSE_LEAFS) &&
558 g_node_traverse_in_order (GNode *node,
559 GTraverseFlags flags,
560 GNodeTraverseFunc func,
566 register GNode *current;
568 child = node->children;
570 child = current->next;
572 if (g_node_traverse_in_order (current, flags, func, data))
575 if ((flags & G_TRAVERSE_NON_LEAFS) &&
582 child = current->next;
583 if (g_node_traverse_in_order (current, flags, func, data))
587 else if ((flags & G_TRAVERSE_LEAFS) &&
595 g_node_depth_traverse_in_order (GNode *node,
596 GTraverseFlags flags,
598 GNodeTraverseFunc func,
607 register GNode *current;
609 child = node->children;
611 child = current->next;
613 if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
616 if ((flags & G_TRAVERSE_NON_LEAFS) &&
623 child = current->next;
624 if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
628 else if ((flags & G_TRAVERSE_NON_LEAFS) &&
632 else if ((flags & G_TRAVERSE_LEAFS) &&
640 g_node_traverse_children (GNode *node,
641 GTraverseFlags flags,
642 GNodeTraverseFunc func,
647 child = node->children;
651 register GNode *current;
654 child = current->next;
656 if (current->children)
658 if ((flags & G_TRAVERSE_NON_LEAFS) &&
659 func (current, data))
662 else if ((flags & G_TRAVERSE_LEAFS) &&
663 func (current, data))
667 child = node->children;
671 register GNode *current;
674 child = current->next;
676 if (current->children &&
677 g_node_traverse_children (current, flags, func, data))
685 g_node_depth_traverse_children (GNode *node,
686 GTraverseFlags flags,
688 GNodeTraverseFunc func,
693 child = node->children;
697 register GNode *current;
700 child = current->next;
702 if (current->children)
704 if ((flags & G_TRAVERSE_NON_LEAFS) &&
705 func (current, data))
708 else if ((flags & G_TRAVERSE_LEAFS) &&
709 func (current, data))
717 child = node->children;
721 register GNode *current;
724 child = current->next;
726 if (current->children &&
727 g_node_depth_traverse_children (current, flags, depth, func, data))
735 g_node_traverse (GNode *root,
737 GTraverseFlags flags,
739 GNodeTraverseFunc func,
742 g_return_if_fail (root != NULL);
743 g_return_if_fail (func != NULL);
744 g_return_if_fail (order <= G_LEVEL_ORDER);
745 g_return_if_fail (flags <= G_TRAVERSE_MASK);
746 g_return_if_fail (depth == -1 || depth > 0);
752 g_node_traverse_pre_order (root, flags, func, data);
754 g_node_depth_traverse_pre_order (root, flags, depth, func, data);
758 g_node_traverse_post_order (root, flags, func, data);
760 g_node_depth_traverse_post_order (root, flags, depth, func, data);
764 g_node_traverse_in_order (root, flags, func, data);
766 g_node_depth_traverse_in_order (root, flags, depth, func, data);
771 if (!((flags & G_TRAVERSE_NON_LEAFS) &&
775 g_node_traverse_children (root, flags, func, data);
780 g_node_depth_traverse_children (root, flags, depth, func, data);
784 else if (flags & G_TRAVERSE_LEAFS)
791 g_node_find_func (GNode *node,
794 register gpointer *d = data;
796 if (*d != node->data)
805 g_node_find (GNode *root,
807 GTraverseFlags flags,
812 g_return_val_if_fail (root != NULL, NULL);
813 g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
814 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
819 g_node_traverse (root, order, flags, -1, g_node_find_func, d);
825 g_node_count_func (GNode *node,
826 GTraverseFlags flags,
833 if (flags & G_TRAVERSE_NON_LEAFS)
836 child = node->children;
839 g_node_count_func (child, flags, n);
843 else if (flags & G_TRAVERSE_LEAFS)
848 g_node_n_nodes (GNode *root,
849 GTraverseFlags flags)
853 g_return_val_if_fail (root != NULL, 0);
854 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
856 g_node_count_func (root, flags, &n);
862 g_node_last_child (GNode *node)
864 g_return_val_if_fail (node != NULL, NULL);
866 node = node->children;
875 g_node_nth_child (GNode *node,
878 g_return_val_if_fail (node != NULL, NULL);
880 node = node->children;
882 while ((n-- > 0) && node)
889 g_node_n_children (GNode *node)
893 g_return_val_if_fail (node != NULL, 0);
895 node = node->children;
906 g_node_find_child (GNode *node,
907 GTraverseFlags flags,
910 g_return_val_if_fail (node != NULL, NULL);
911 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
913 node = node->children;
916 if (node->data == data)
918 if (G_NODE_IS_LEAF (node))
920 if (flags & G_TRAVERSE_LEAFS)
925 if (flags & G_TRAVERSE_NON_LEAFS)
936 g_node_child_position (GNode *node,
939 register guint n = 0;
941 g_return_val_if_fail (node != NULL, -1);
942 g_return_val_if_fail (child != NULL, -1);
943 g_return_val_if_fail (child->parent == node, -1);
945 node = node->children;
958 g_node_child_index (GNode *node,
961 register guint n = 0;
963 g_return_val_if_fail (node != NULL, -1);
965 node = node->children;
968 if (node->data == data)
978 g_node_first_sibling (GNode *node)
980 g_return_val_if_fail (node != NULL, NULL);
983 return node->parent->children;
992 g_node_last_sibling (GNode *node)
994 g_return_val_if_fail (node != NULL, NULL);
1003 g_node_children_foreach (GNode *node,
1004 GTraverseFlags flags,
1005 GNodeForeachFunc func,
1008 g_return_if_fail (node != NULL);
1009 g_return_if_fail (flags <= G_TRAVERSE_MASK);
1010 g_return_if_fail (func != NULL);
1012 node = node->children;
1015 register GNode *current;
1018 node = current->next;
1019 if (G_NODE_IS_LEAF (current))
1021 if (flags & G_TRAVERSE_LEAFS)
1022 func (current, data);
1026 if (flags & G_TRAVERSE_NON_LEAFS)
1027 func (current, data);