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
);