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 #ifndef DISABLE_MEM_POOLS
41 struct _GAllocator /* from gmem.c */
49 GNode *free_nodes; /* implementation specific */
52 G_LOCK_DEFINE_STATIC (current_allocator);
53 static GAllocator *current_allocator = NULL;
55 /* HOLDS: current_allocator_lock */
57 g_node_validate_allocator (GAllocator *allocator)
59 g_return_if_fail (allocator != NULL);
60 g_return_if_fail (allocator->is_unused == TRUE);
62 if (allocator->type != G_ALLOCATOR_NODE)
64 allocator->type = G_ALLOCATOR_NODE;
65 if (allocator->mem_chunk)
67 g_mem_chunk_destroy (allocator->mem_chunk);
68 allocator->mem_chunk = NULL;
72 if (!allocator->mem_chunk)
74 allocator->mem_chunk = g_mem_chunk_new (allocator->name,
76 sizeof (GNode) * allocator->n_preallocs,
78 allocator->free_nodes = NULL;
81 allocator->is_unused = FALSE;
85 g_node_push_allocator (GAllocator *allocator)
87 G_LOCK (current_allocator);
88 g_node_validate_allocator (allocator);
89 allocator->last = current_allocator;
90 current_allocator = allocator;
91 G_UNLOCK (current_allocator);
95 g_node_pop_allocator (void)
97 G_LOCK (current_allocator);
98 if (current_allocator)
100 GAllocator *allocator;
102 allocator = current_allocator;
103 current_allocator = allocator->last;
104 allocator->last = NULL;
105 allocator->is_unused = TRUE;
107 G_UNLOCK (current_allocator);
111 /* --- functions --- */
113 g_node_new (gpointer data)
117 G_LOCK (current_allocator);
118 if (!current_allocator)
120 GAllocator *allocator = g_allocator_new ("GLib default GNode allocator",
122 g_node_validate_allocator (allocator);
123 allocator->last = NULL;
124 current_allocator = allocator;
126 if (!current_allocator->free_nodes)
127 node = g_chunk_new (GNode, current_allocator->mem_chunk);
130 node = current_allocator->free_nodes;
131 current_allocator->free_nodes = node->next;
133 G_UNLOCK (current_allocator);
139 node->children = NULL;
145 g_nodes_free (GNode *node)
152 if (parent->children)
153 g_nodes_free (parent->children);
155 #ifdef ENABLE_GC_FRIENDLY
158 parent->parent = NULL;
159 parent->children = NULL;
160 #endif /* ENABLE_GC_FRIENDLY */
163 parent = parent->next;
168 G_LOCK (current_allocator);
169 parent->next = current_allocator->free_nodes;
170 current_allocator->free_nodes = node;
171 G_UNLOCK (current_allocator);
173 #else /* DISABLE_MEM_POOLS */
176 g_node_new (gpointer data)
180 node = g_new0 (GNode, 1);
188 g_nodes_free (GNode *root)
196 g_nodes_free (node->children);
204 g_node_destroy (GNode *root)
206 g_return_if_fail (root != NULL);
208 if (!G_NODE_IS_ROOT (root))
209 g_node_unlink (root);
215 g_node_unlink (GNode *node)
217 g_return_if_fail (node != NULL);
220 node->prev->next = node->next;
221 else if (node->parent)
222 node->parent->children = node->next;
226 node->next->prev = node->prev;
233 g_node_copy (GNode *node)
235 GNode *new_node = NULL;
241 new_node = g_node_new (node->data);
243 for (child = g_node_last_child (node); child; child = child->prev)
244 g_node_prepend (new_node, g_node_copy (child));
251 g_node_insert (GNode *parent,
255 g_return_val_if_fail (parent != NULL, node);
256 g_return_val_if_fail (node != NULL, node);
257 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
260 return g_node_insert_before (parent,
261 g_node_nth_child (parent, position),
263 else if (position == 0)
264 return g_node_prepend (parent, node);
265 else /* if (position < 0) */
266 return g_node_append (parent, node);
270 g_node_insert_before (GNode *parent,
274 g_return_val_if_fail (parent != NULL, node);
275 g_return_val_if_fail (node != NULL, node);
276 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
278 g_return_val_if_fail (sibling->parent == parent, node);
280 node->parent = parent;
286 node->prev = sibling->prev;
287 node->prev->next = node;
288 node->next = sibling;
289 sibling->prev = node;
293 node->parent->children = node;
294 node->next = sibling;
295 sibling->prev = node;
300 if (parent->children)
302 sibling = parent->children;
303 while (sibling->next)
304 sibling = sibling->next;
305 node->prev = sibling;
306 sibling->next = node;
309 node->parent->children = node;
316 g_node_insert_after (GNode *parent,
320 g_return_val_if_fail (parent != NULL, node);
321 g_return_val_if_fail (node != NULL, node);
322 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
324 g_return_val_if_fail (sibling->parent == parent, node);
326 node->parent = parent;
332 sibling->next->prev = node;
334 node->next = sibling->next;
335 node->prev = sibling;
336 sibling->next = node;
340 if (parent->children)
342 node->next = parent->children;
343 parent->children->prev = node;
345 parent->children = node;
352 g_node_prepend (GNode *parent,
355 g_return_val_if_fail (parent != NULL, node);
357 return g_node_insert_before (parent, parent->children, node);
361 g_node_get_root (GNode *node)
363 g_return_val_if_fail (node != NULL, NULL);
372 g_node_is_ancestor (GNode *node,
375 g_return_val_if_fail (node != NULL, FALSE);
376 g_return_val_if_fail (descendant != NULL, FALSE);
380 if (descendant->parent == node)
383 descendant = descendant->parent;
389 /* returns 1 for root, 2 for first level children,
390 * 3 for children's children...
393 g_node_depth (GNode *node)
395 register guint depth = 0;
407 g_node_reverse_children (GNode *node)
412 g_return_if_fail (node != NULL);
414 child = node->children;
420 last->next = last->prev;
423 node->children = last;
427 g_node_max_height (GNode *root)
429 register GNode *child;
430 register guint max_height = 0;
435 child = root->children;
438 register guint tmp_height;
440 tmp_height = g_node_max_height (child);
441 if (tmp_height > max_height)
442 max_height = tmp_height;
446 return max_height + 1;
450 g_node_traverse_pre_order (GNode *node,
451 GTraverseFlags flags,
452 GNodeTraverseFunc func,
459 if ((flags & G_TRAVERSE_NON_LEAFS) &&
463 child = node->children;
466 register GNode *current;
469 child = current->next;
470 if (g_node_traverse_pre_order (current, flags, func, data))
474 else if ((flags & G_TRAVERSE_LEAFS) &&
482 g_node_depth_traverse_pre_order (GNode *node,
483 GTraverseFlags flags,
485 GNodeTraverseFunc func,
492 if ((flags & G_TRAVERSE_NON_LEAFS) &&
500 child = node->children;
503 register GNode *current;
506 child = current->next;
507 if (g_node_depth_traverse_pre_order (current, flags, depth, func, data))
511 else if ((flags & G_TRAVERSE_LEAFS) &&
519 g_node_traverse_post_order (GNode *node,
520 GTraverseFlags flags,
521 GNodeTraverseFunc func,
528 child = node->children;
531 register GNode *current;
534 child = current->next;
535 if (g_node_traverse_post_order (current, flags, func, data))
539 if ((flags & G_TRAVERSE_NON_LEAFS) &&
544 else if ((flags & G_TRAVERSE_LEAFS) &&
552 g_node_depth_traverse_post_order (GNode *node,
553 GTraverseFlags flags,
555 GNodeTraverseFunc func,
565 child = node->children;
568 register GNode *current;
571 child = current->next;
572 if (g_node_depth_traverse_post_order (current, flags, depth, func, data))
577 if ((flags & G_TRAVERSE_NON_LEAFS) &&
582 else if ((flags & G_TRAVERSE_LEAFS) &&
590 g_node_traverse_in_order (GNode *node,
591 GTraverseFlags flags,
592 GNodeTraverseFunc func,
598 register GNode *current;
600 child = node->children;
602 child = current->next;
604 if (g_node_traverse_in_order (current, flags, func, data))
607 if ((flags & G_TRAVERSE_NON_LEAFS) &&
614 child = current->next;
615 if (g_node_traverse_in_order (current, flags, func, data))
619 else if ((flags & G_TRAVERSE_LEAFS) &&
627 g_node_depth_traverse_in_order (GNode *node,
628 GTraverseFlags flags,
630 GNodeTraverseFunc func,
639 register GNode *current;
641 child = node->children;
643 child = current->next;
645 if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
648 if ((flags & G_TRAVERSE_NON_LEAFS) &&
655 child = current->next;
656 if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
660 else if ((flags & G_TRAVERSE_NON_LEAFS) &&
664 else if ((flags & G_TRAVERSE_LEAFS) &&
672 g_node_traverse_level (GNode *node,
673 GTraverseFlags flags,
675 GNodeTraverseFunc func,
677 gboolean *more_levels)
684 return (flags & G_TRAVERSE_NON_LEAFS) && func (node, data);
688 return (flags & G_TRAVERSE_LEAFS) && func (node, data);
693 node = node->children;
697 if (g_node_traverse_level (node, flags, level - 1, func, data, more_levels))
708 g_node_depth_traverse_level (GNode *node,
709 GTraverseFlags flags,
711 GNodeTraverseFunc func,
715 gboolean more_levels;
718 while (level != depth)
721 if (g_node_traverse_level (node, flags, level, func, data, &more_levels))
731 g_node_traverse (GNode *root,
733 GTraverseFlags flags,
735 GNodeTraverseFunc func,
738 g_return_if_fail (root != NULL);
739 g_return_if_fail (func != NULL);
740 g_return_if_fail (order <= G_LEVEL_ORDER);
741 g_return_if_fail (flags <= G_TRAVERSE_MASK);
742 g_return_if_fail (depth == -1 || depth > 0);
748 g_node_traverse_pre_order (root, flags, func, data);
750 g_node_depth_traverse_pre_order (root, flags, depth, func, data);
754 g_node_traverse_post_order (root, flags, func, data);
756 g_node_depth_traverse_post_order (root, flags, depth, func, data);
760 g_node_traverse_in_order (root, flags, func, data);
762 g_node_depth_traverse_in_order (root, flags, depth, func, data);
765 g_node_depth_traverse_level (root, flags, depth, func, data);
771 g_node_find_func (GNode *node,
774 register gpointer *d = data;
776 if (*d != node->data)
785 g_node_find (GNode *root,
787 GTraverseFlags flags,
792 g_return_val_if_fail (root != NULL, NULL);
793 g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
794 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
799 g_node_traverse (root, order, flags, -1, g_node_find_func, d);
805 g_node_count_func (GNode *node,
806 GTraverseFlags flags,
813 if (flags & G_TRAVERSE_NON_LEAFS)
816 child = node->children;
819 g_node_count_func (child, flags, n);
823 else if (flags & G_TRAVERSE_LEAFS)
828 g_node_n_nodes (GNode *root,
829 GTraverseFlags flags)
833 g_return_val_if_fail (root != NULL, 0);
834 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
836 g_node_count_func (root, flags, &n);
842 g_node_last_child (GNode *node)
844 g_return_val_if_fail (node != NULL, NULL);
846 node = node->children;
855 g_node_nth_child (GNode *node,
858 g_return_val_if_fail (node != NULL, NULL);
860 node = node->children;
862 while ((n-- > 0) && node)
869 g_node_n_children (GNode *node)
873 g_return_val_if_fail (node != NULL, 0);
875 node = node->children;
886 g_node_find_child (GNode *node,
887 GTraverseFlags flags,
890 g_return_val_if_fail (node != NULL, NULL);
891 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
893 node = node->children;
896 if (node->data == data)
898 if (G_NODE_IS_LEAF (node))
900 if (flags & G_TRAVERSE_LEAFS)
905 if (flags & G_TRAVERSE_NON_LEAFS)
916 g_node_child_position (GNode *node,
919 register guint n = 0;
921 g_return_val_if_fail (node != NULL, -1);
922 g_return_val_if_fail (child != NULL, -1);
923 g_return_val_if_fail (child->parent == node, -1);
925 node = node->children;
938 g_node_child_index (GNode *node,
941 register guint n = 0;
943 g_return_val_if_fail (node != NULL, -1);
945 node = node->children;
948 if (node->data == data)
958 g_node_first_sibling (GNode *node)
960 g_return_val_if_fail (node != NULL, NULL);
963 return node->parent->children;
972 g_node_last_sibling (GNode *node)
974 g_return_val_if_fail (node != NULL, NULL);
983 g_node_children_foreach (GNode *node,
984 GTraverseFlags flags,
985 GNodeForeachFunc func,
988 g_return_if_fail (node != NULL);
989 g_return_if_fail (flags <= G_TRAVERSE_MASK);
990 g_return_if_fail (func != NULL);
992 node = node->children;
995 register GNode *current;
998 node = current->next;
999 if (G_NODE_IS_LEAF (current))
1001 if (flags & G_TRAVERSE_LEAFS)
1002 func (current, data);
1006 if (flags & G_TRAVERSE_NON_LEAFS)
1007 func (current, data);