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.
31 struct _GAllocator
/* from gmem.c */
39 GNode
*free_nodes
; /* implementation specific */
42 G_LOCK_DECLARE_STATIC (current_allocator
);
43 static GAllocator
*current_allocator
= NULL
;
45 /* HOLDS: current_allocator_lock */
47 g_node_validate_allocator (GAllocator
*allocator
)
49 g_return_if_fail (allocator
!= NULL
);
50 g_return_if_fail (allocator
->is_unused
== TRUE
);
52 if (allocator
->type
!= G_ALLOCATOR_NODE
)
54 allocator
->type
= G_ALLOCATOR_NODE
;
55 if (allocator
->mem_chunk
)
57 g_mem_chunk_destroy (allocator
->mem_chunk
);
58 allocator
->mem_chunk
= NULL
;
62 if (!allocator
->mem_chunk
)
64 allocator
->mem_chunk
= g_mem_chunk_new (allocator
->name
,
66 sizeof (GNode
) * allocator
->n_preallocs
,
68 allocator
->free_nodes
= NULL
;
71 allocator
->is_unused
= FALSE
;
75 g_node_push_allocator (GAllocator
*allocator
)
77 G_LOCK (current_allocator
);
78 g_node_validate_allocator ( allocator
);
79 allocator
->last
= current_allocator
;
80 current_allocator
= allocator
;
81 G_UNLOCK (current_allocator
);
85 g_node_pop_allocator (void)
87 G_LOCK (current_allocator
);
88 if (current_allocator
)
90 GAllocator
*allocator
;
92 allocator
= current_allocator
;
93 current_allocator
= allocator
->last
;
94 allocator
->last
= NULL
;
95 allocator
->is_unused
= TRUE
;
97 G_UNLOCK (current_allocator
);
101 /* --- functions --- */
103 g_node_new (gpointer data
)
107 G_LOCK (current_allocator
);
108 if (!current_allocator
)
110 GAllocator
*allocator
= g_allocator_new ("GLib default GNode allocator",
112 g_node_validate_allocator (allocator
);
113 allocator
->last
= NULL
;
114 current_allocator
= allocator
;
116 if (!current_allocator
->free_nodes
)
117 node
= g_chunk_new (GNode
, current_allocator
->mem_chunk
);
120 node
= current_allocator
->free_nodes
;
121 current_allocator
->free_nodes
= node
->next
;
123 G_UNLOCK (current_allocator
);
129 node
->children
= NULL
;
135 g_nodes_free (GNode
*node
)
142 if (parent
->children
)
143 g_nodes_free (parent
->children
);
145 parent
= parent
->next
;
150 G_LOCK (current_allocator
);
151 parent
->next
= current_allocator
->free_nodes
;
152 current_allocator
->free_nodes
= node
;
153 G_UNLOCK (current_allocator
);
157 g_node_destroy (GNode
*root
)
159 g_return_if_fail (root
!= NULL
);
161 if (!G_NODE_IS_ROOT (root
))
162 g_node_unlink (root
);
168 g_node_unlink (GNode
*node
)
170 g_return_if_fail (node
!= NULL
);
173 node
->prev
->next
= node
->next
;
174 else if (node
->parent
)
175 node
->parent
->children
= node
->next
;
179 node
->next
->prev
= node
->prev
;
186 g_node_insert (GNode
*parent
,
190 g_return_val_if_fail (parent
!= NULL
, node
);
191 g_return_val_if_fail (node
!= NULL
, node
);
192 g_return_val_if_fail (G_NODE_IS_ROOT (node
), node
);
195 return g_node_insert_before (parent
,
196 g_node_nth_child (parent
, position
),
198 else if (position
== 0)
199 return g_node_prepend (parent
, node
);
200 else /* if (position < 0) */
201 return g_node_append (parent
, node
);
205 g_node_insert_before (GNode
*parent
,
209 g_return_val_if_fail (parent
!= NULL
, node
);
210 g_return_val_if_fail (node
!= NULL
, node
);
211 g_return_val_if_fail (G_NODE_IS_ROOT (node
), node
);
213 g_return_val_if_fail (sibling
->parent
== parent
, node
);
215 node
->parent
= parent
;
221 node
->prev
= sibling
->prev
;
222 node
->prev
->next
= node
;
223 node
->next
= sibling
;
224 sibling
->prev
= node
;
228 node
->parent
->children
= node
;
229 node
->next
= sibling
;
230 sibling
->prev
= node
;
235 if (parent
->children
)
237 sibling
= parent
->children
;
238 while (sibling
->next
)
239 sibling
= sibling
->next
;
240 node
->prev
= sibling
;
241 sibling
->next
= node
;
244 node
->parent
->children
= node
;
251 g_node_prepend (GNode
*parent
,
254 g_return_val_if_fail (parent
!= NULL
, node
);
256 return g_node_insert_before (parent
, parent
->children
, node
);
260 g_node_get_root (GNode
*node
)
262 g_return_val_if_fail (node
!= NULL
, NULL
);
271 g_node_is_ancestor (GNode
*node
,
274 g_return_val_if_fail (node
!= NULL
, FALSE
);
275 g_return_val_if_fail (descendant
!= NULL
, FALSE
);
279 if (descendant
->parent
== node
)
282 descendant
= descendant
->parent
;
288 /* returns 1 for root, 2 for first level children,
289 * 3 for children's children...
292 g_node_depth (GNode
*node
)
294 register guint depth
= 0;
306 g_node_reverse_children (GNode
*node
)
311 g_return_if_fail (node
!= NULL
);
313 child
= node
->children
;
319 last
->next
= last
->prev
;
322 node
->children
= last
;
326 g_node_max_height (GNode
*root
)
328 register GNode
*child
;
329 register guint max_height
= 0;
334 child
= root
->children
;
337 register guint tmp_height
;
339 tmp_height
= g_node_max_height (child
);
340 if (tmp_height
> max_height
)
341 max_height
= tmp_height
;
345 return max_height
+ 1;
349 g_node_traverse_pre_order (GNode
*node
,
350 GTraverseFlags flags
,
351 GNodeTraverseFunc func
,
358 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
362 child
= node
->children
;
365 register GNode
*current
;
368 child
= current
->next
;
369 if (g_node_traverse_pre_order (current
, flags
, func
, data
))
373 else if ((flags
& G_TRAVERSE_LEAFS
) &&
381 g_node_depth_traverse_pre_order (GNode
*node
,
382 GTraverseFlags flags
,
384 GNodeTraverseFunc func
,
391 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
399 child
= node
->children
;
402 register GNode
*current
;
405 child
= current
->next
;
406 if (g_node_depth_traverse_pre_order (current
, flags
, depth
, func
, data
))
410 else if ((flags
& G_TRAVERSE_LEAFS
) &&
418 g_node_traverse_post_order (GNode
*node
,
419 GTraverseFlags flags
,
420 GNodeTraverseFunc func
,
427 child
= node
->children
;
430 register GNode
*current
;
433 child
= current
->next
;
434 if (g_node_traverse_post_order (current
, flags
, func
, data
))
438 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
443 else if ((flags
& G_TRAVERSE_LEAFS
) &&
451 g_node_depth_traverse_post_order (GNode
*node
,
452 GTraverseFlags flags
,
454 GNodeTraverseFunc func
,
464 child
= node
->children
;
467 register GNode
*current
;
470 child
= current
->next
;
471 if (g_node_depth_traverse_post_order (current
, flags
, depth
, func
, data
))
476 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
481 else if ((flags
& G_TRAVERSE_LEAFS
) &&
489 g_node_traverse_in_order (GNode
*node
,
490 GTraverseFlags flags
,
491 GNodeTraverseFunc func
,
497 register GNode
*current
;
499 child
= node
->children
;
501 child
= current
->next
;
503 if (g_node_traverse_in_order (current
, flags
, func
, data
))
506 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
513 child
= current
->next
;
514 if (g_node_traverse_in_order (current
, flags
, func
, data
))
518 else if ((flags
& G_TRAVERSE_LEAFS
) &&
526 g_node_depth_traverse_in_order (GNode
*node
,
527 GTraverseFlags flags
,
529 GNodeTraverseFunc func
,
538 register GNode
*current
;
540 child
= node
->children
;
542 child
= current
->next
;
544 if (g_node_depth_traverse_in_order (current
, flags
, depth
, func
, data
))
547 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
554 child
= current
->next
;
555 if (g_node_depth_traverse_in_order (current
, flags
, depth
, func
, data
))
559 else if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
563 else if ((flags
& G_TRAVERSE_LEAFS
) &&
571 g_node_traverse_children (GNode
*node
,
572 GTraverseFlags flags
,
573 GNodeTraverseFunc func
,
578 child
= node
->children
;
582 register GNode
*current
;
585 child
= current
->next
;
587 if (current
->children
)
589 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
590 func (current
, data
))
593 else if ((flags
& G_TRAVERSE_LEAFS
) &&
594 func (current
, data
))
598 child
= node
->children
;
602 register GNode
*current
;
605 child
= current
->next
;
607 if (current
->children
&&
608 g_node_traverse_children (current
, flags
, func
, data
))
616 g_node_depth_traverse_children (GNode
*node
,
617 GTraverseFlags flags
,
619 GNodeTraverseFunc func
,
624 child
= node
->children
;
628 register GNode
*current
;
631 child
= current
->next
;
633 if (current
->children
)
635 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
636 func (current
, data
))
639 else if ((flags
& G_TRAVERSE_LEAFS
) &&
640 func (current
, data
))
648 child
= node
->children
;
652 register GNode
*current
;
655 child
= current
->next
;
657 if (current
->children
&&
658 g_node_depth_traverse_children (current
, flags
, depth
, func
, data
))
666 g_node_traverse (GNode
*root
,
668 GTraverseFlags flags
,
670 GNodeTraverseFunc func
,
673 g_return_if_fail (root
!= NULL
);
674 g_return_if_fail (func
!= NULL
);
675 g_return_if_fail (order
<= G_LEVEL_ORDER
);
676 g_return_if_fail (flags
<= G_TRAVERSE_MASK
);
677 g_return_if_fail (depth
== -1 || depth
> 0);
683 g_node_traverse_pre_order (root
, flags
, func
, data
);
685 g_node_depth_traverse_pre_order (root
, flags
, depth
, func
, data
);
689 g_node_traverse_post_order (root
, flags
, func
, data
);
691 g_node_depth_traverse_post_order (root
, flags
, depth
, func
, data
);
695 g_node_traverse_in_order (root
, flags
, func
, data
);
697 g_node_depth_traverse_in_order (root
, flags
, depth
, func
, data
);
702 if (!((flags
& G_TRAVERSE_NON_LEAFS
) &&
706 g_node_traverse_children (root
, flags
, func
, data
);
711 g_node_depth_traverse_children (root
, flags
, depth
, func
, data
);
715 else if (flags
& G_TRAVERSE_LEAFS
)
722 g_node_find_func (GNode
*node
,
725 register gpointer
*d
= data
;
727 if (*d
!= node
->data
)
736 g_node_find (GNode
*root
,
738 GTraverseFlags flags
,
743 g_return_val_if_fail (root
!= NULL
, NULL
);
744 g_return_val_if_fail (order
<= G_LEVEL_ORDER
, NULL
);
745 g_return_val_if_fail (flags
<= G_TRAVERSE_MASK
, NULL
);
750 g_node_traverse (root
, order
, flags
, -1, g_node_find_func
, d
);
756 g_node_count_func (GNode
*node
,
757 GTraverseFlags flags
,
764 if (flags
& G_TRAVERSE_NON_LEAFS
)
767 child
= node
->children
;
770 g_node_count_func (child
, flags
, n
);
774 else if (flags
& G_TRAVERSE_LEAFS
)
779 g_node_n_nodes (GNode
*root
,
780 GTraverseFlags flags
)
784 g_return_val_if_fail (root
!= NULL
, 0);
785 g_return_val_if_fail (flags
<= G_TRAVERSE_MASK
, 0);
787 g_node_count_func (root
, flags
, &n
);
793 g_node_last_child (GNode
*node
)
795 g_return_val_if_fail (node
!= NULL
, NULL
);
797 node
= node
->children
;
806 g_node_nth_child (GNode
*node
,
809 g_return_val_if_fail (node
!= NULL
, NULL
);
811 node
= node
->children
;
813 while ((n
-- > 0) && node
)
820 g_node_n_children (GNode
*node
)
824 g_return_val_if_fail (node
!= NULL
, 0);
826 node
= node
->children
;
837 g_node_find_child (GNode
*node
,
838 GTraverseFlags flags
,
841 g_return_val_if_fail (node
!= NULL
, NULL
);
842 g_return_val_if_fail (flags
<= G_TRAVERSE_MASK
, NULL
);
844 node
= node
->children
;
847 if (node
->data
== data
)
849 if (G_NODE_IS_LEAF (node
))
851 if (flags
& G_TRAVERSE_LEAFS
)
856 if (flags
& G_TRAVERSE_NON_LEAFS
)
867 g_node_child_position (GNode
*node
,
870 register guint n
= 0;
872 g_return_val_if_fail (node
!= NULL
, -1);
873 g_return_val_if_fail (child
!= NULL
, -1);
874 g_return_val_if_fail (child
->parent
== node
, -1);
876 node
= node
->children
;
889 g_node_child_index (GNode
*node
,
892 register guint n
= 0;
894 g_return_val_if_fail (node
!= NULL
, -1);
896 node
= node
->children
;
899 if (node
->data
== data
)
909 g_node_first_sibling (GNode
*node
)
911 g_return_val_if_fail (node
!= NULL
, NULL
);
920 g_node_last_sibling (GNode
*node
)
922 g_return_val_if_fail (node
!= NULL
, NULL
);
931 g_node_children_foreach (GNode
*node
,
932 GTraverseFlags flags
,
933 GNodeForeachFunc func
,
936 g_return_if_fail (node
!= NULL
);
937 g_return_if_fail (flags
<= G_TRAVERSE_MASK
);
938 g_return_if_fail (func
!= NULL
);
940 node
= node
->children
;
943 register GNode
*current
;
946 node
= current
->next
;
947 if (G_NODE_IS_LEAF (current
))
949 if (flags
& G_TRAVERSE_LEAFS
)
950 func (current
, data
);
954 if (flags
& G_TRAVERSE_NON_LEAFS
)
955 func (current
, data
);