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.
24 * Modified by the GLib Team and others 1997-1999. 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 parent = parent->next;
157 G_LOCK (current_allocator);
158 parent->next = current_allocator->free_nodes;
159 current_allocator->free_nodes = node;
160 G_UNLOCK (current_allocator);
164 g_node_destroy (GNode *root)
166 g_return_if_fail (root != NULL);
168 if (!G_NODE_IS_ROOT (root))
169 g_node_unlink (root);
175 g_node_unlink (GNode *node)
177 g_return_if_fail (node != NULL);
180 node->prev->next = node->next;
181 else if (node->parent)
182 node->parent->children = node->next;
186 node->next->prev = node->prev;
193 g_node_insert (GNode *parent,
197 g_return_val_if_fail (parent != NULL, node);
198 g_return_val_if_fail (node != NULL, node);
199 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
202 return g_node_insert_before (parent,
203 g_node_nth_child (parent, position),
205 else if (position == 0)
206 return g_node_prepend (parent, node);
207 else /* if (position < 0) */
208 return g_node_append (parent, node);
212 g_node_insert_before (GNode *parent,
216 g_return_val_if_fail (parent != NULL, node);
217 g_return_val_if_fail (node != NULL, node);
218 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
220 g_return_val_if_fail (sibling->parent == parent, node);
222 node->parent = parent;
228 node->prev = sibling->prev;
229 node->prev->next = node;
230 node->next = sibling;
231 sibling->prev = node;
235 node->parent->children = node;
236 node->next = sibling;
237 sibling->prev = node;
242 if (parent->children)
244 sibling = parent->children;
245 while (sibling->next)
246 sibling = sibling->next;
247 node->prev = sibling;
248 sibling->next = node;
251 node->parent->children = node;
258 g_node_prepend (GNode *parent,
261 g_return_val_if_fail (parent != NULL, node);
263 return g_node_insert_before (parent, parent->children, node);
267 g_node_get_root (GNode *node)
269 g_return_val_if_fail (node != NULL, NULL);
278 g_node_is_ancestor (GNode *node,
281 g_return_val_if_fail (node != NULL, FALSE);
282 g_return_val_if_fail (descendant != NULL, FALSE);
286 if (descendant->parent == node)
289 descendant = descendant->parent;
295 /* returns 1 for root, 2 for first level children,
296 * 3 for children's children...
299 g_node_depth (GNode *node)
301 register guint depth = 0;
313 g_node_reverse_children (GNode *node)
318 g_return_if_fail (node != NULL);
320 child = node->children;
326 last->next = last->prev;
329 node->children = last;
333 g_node_max_height (GNode *root)
335 register GNode *child;
336 register guint max_height = 0;
341 child = root->children;
344 register guint tmp_height;
346 tmp_height = g_node_max_height (child);
347 if (tmp_height > max_height)
348 max_height = tmp_height;
352 return max_height + 1;
356 g_node_traverse_pre_order (GNode *node,
357 GTraverseFlags flags,
358 GNodeTraverseFunc func,
365 if ((flags & G_TRAVERSE_NON_LEAFS) &&
369 child = node->children;
372 register GNode *current;
375 child = current->next;
376 if (g_node_traverse_pre_order (current, flags, func, data))
380 else if ((flags & G_TRAVERSE_LEAFS) &&
388 g_node_depth_traverse_pre_order (GNode *node,
389 GTraverseFlags flags,
391 GNodeTraverseFunc func,
398 if ((flags & G_TRAVERSE_NON_LEAFS) &&
406 child = node->children;
409 register GNode *current;
412 child = current->next;
413 if (g_node_depth_traverse_pre_order (current, flags, depth, func, data))
417 else if ((flags & G_TRAVERSE_LEAFS) &&
425 g_node_traverse_post_order (GNode *node,
426 GTraverseFlags flags,
427 GNodeTraverseFunc func,
434 child = node->children;
437 register GNode *current;
440 child = current->next;
441 if (g_node_traverse_post_order (current, flags, func, data))
445 if ((flags & G_TRAVERSE_NON_LEAFS) &&
450 else if ((flags & G_TRAVERSE_LEAFS) &&
458 g_node_depth_traverse_post_order (GNode *node,
459 GTraverseFlags flags,
461 GNodeTraverseFunc func,
471 child = node->children;
474 register GNode *current;
477 child = current->next;
478 if (g_node_depth_traverse_post_order (current, flags, depth, func, data))
483 if ((flags & G_TRAVERSE_NON_LEAFS) &&
488 else if ((flags & G_TRAVERSE_LEAFS) &&
496 g_node_traverse_in_order (GNode *node,
497 GTraverseFlags flags,
498 GNodeTraverseFunc func,
504 register GNode *current;
506 child = node->children;
508 child = current->next;
510 if (g_node_traverse_in_order (current, flags, func, data))
513 if ((flags & G_TRAVERSE_NON_LEAFS) &&
520 child = current->next;
521 if (g_node_traverse_in_order (current, flags, func, data))
525 else if ((flags & G_TRAVERSE_LEAFS) &&
533 g_node_depth_traverse_in_order (GNode *node,
534 GTraverseFlags flags,
536 GNodeTraverseFunc func,
545 register GNode *current;
547 child = node->children;
549 child = current->next;
551 if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
554 if ((flags & G_TRAVERSE_NON_LEAFS) &&
561 child = current->next;
562 if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
566 else if ((flags & G_TRAVERSE_NON_LEAFS) &&
570 else if ((flags & G_TRAVERSE_LEAFS) &&
578 g_node_traverse_children (GNode *node,
579 GTraverseFlags flags,
580 GNodeTraverseFunc func,
585 child = node->children;
589 register GNode *current;
592 child = current->next;
594 if (current->children)
596 if ((flags & G_TRAVERSE_NON_LEAFS) &&
597 func (current, data))
600 else if ((flags & G_TRAVERSE_LEAFS) &&
601 func (current, data))
605 child = node->children;
609 register GNode *current;
612 child = current->next;
614 if (current->children &&
615 g_node_traverse_children (current, flags, func, data))
623 g_node_depth_traverse_children (GNode *node,
624 GTraverseFlags flags,
626 GNodeTraverseFunc func,
631 child = node->children;
635 register GNode *current;
638 child = current->next;
640 if (current->children)
642 if ((flags & G_TRAVERSE_NON_LEAFS) &&
643 func (current, data))
646 else if ((flags & G_TRAVERSE_LEAFS) &&
647 func (current, data))
655 child = node->children;
659 register GNode *current;
662 child = current->next;
664 if (current->children &&
665 g_node_depth_traverse_children (current, flags, depth, func, data))
673 g_node_traverse (GNode *root,
675 GTraverseFlags flags,
677 GNodeTraverseFunc func,
680 g_return_if_fail (root != NULL);
681 g_return_if_fail (func != NULL);
682 g_return_if_fail (order <= G_LEVEL_ORDER);
683 g_return_if_fail (flags <= G_TRAVERSE_MASK);
684 g_return_if_fail (depth == -1 || depth > 0);
690 g_node_traverse_pre_order (root, flags, func, data);
692 g_node_depth_traverse_pre_order (root, flags, depth, func, data);
696 g_node_traverse_post_order (root, flags, func, data);
698 g_node_depth_traverse_post_order (root, flags, depth, func, data);
702 g_node_traverse_in_order (root, flags, func, data);
704 g_node_depth_traverse_in_order (root, flags, depth, func, data);
709 if (!((flags & G_TRAVERSE_NON_LEAFS) &&
713 g_node_traverse_children (root, flags, func, data);
718 g_node_depth_traverse_children (root, flags, depth, func, data);
722 else if (flags & G_TRAVERSE_LEAFS)
729 g_node_find_func (GNode *node,
732 register gpointer *d = data;
734 if (*d != node->data)
743 g_node_find (GNode *root,
745 GTraverseFlags flags,
750 g_return_val_if_fail (root != NULL, NULL);
751 g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
752 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
757 g_node_traverse (root, order, flags, -1, g_node_find_func, d);
763 g_node_count_func (GNode *node,
764 GTraverseFlags flags,
771 if (flags & G_TRAVERSE_NON_LEAFS)
774 child = node->children;
777 g_node_count_func (child, flags, n);
781 else if (flags & G_TRAVERSE_LEAFS)
786 g_node_n_nodes (GNode *root,
787 GTraverseFlags flags)
791 g_return_val_if_fail (root != NULL, 0);
792 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
794 g_node_count_func (root, flags, &n);
800 g_node_last_child (GNode *node)
802 g_return_val_if_fail (node != NULL, NULL);
804 node = node->children;
813 g_node_nth_child (GNode *node,
816 g_return_val_if_fail (node != NULL, NULL);
818 node = node->children;
820 while ((n-- > 0) && node)
827 g_node_n_children (GNode *node)
831 g_return_val_if_fail (node != NULL, 0);
833 node = node->children;
844 g_node_find_child (GNode *node,
845 GTraverseFlags flags,
848 g_return_val_if_fail (node != NULL, NULL);
849 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
851 node = node->children;
854 if (node->data == data)
856 if (G_NODE_IS_LEAF (node))
858 if (flags & G_TRAVERSE_LEAFS)
863 if (flags & G_TRAVERSE_NON_LEAFS)
874 g_node_child_position (GNode *node,
877 register guint n = 0;
879 g_return_val_if_fail (node != NULL, -1);
880 g_return_val_if_fail (child != NULL, -1);
881 g_return_val_if_fail (child->parent == node, -1);
883 node = node->children;
896 g_node_child_index (GNode *node,
899 register guint n = 0;
901 g_return_val_if_fail (node != NULL, -1);
903 node = node->children;
906 if (node->data == data)
916 g_node_first_sibling (GNode *node)
918 g_return_val_if_fail (node != NULL, NULL);
927 g_node_last_sibling (GNode *node)
929 g_return_val_if_fail (node != NULL, NULL);
938 g_node_children_foreach (GNode *node,
939 GTraverseFlags flags,
940 GNodeForeachFunc func,
943 g_return_if_fail (node != NULL);
944 g_return_if_fail (flags <= G_TRAVERSE_MASK);
945 g_return_if_fail (func != NULL);
947 node = node->children;
950 register GNode *current;
953 node = current->next;
954 if (G_NODE_IS_LEAF (current))
956 if (flags & G_TRAVERSE_LEAFS)
957 func (current, data);
961 if (flags & G_TRAVERSE_NON_LEAFS)
962 func (current, data);