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/.
40 #ifndef DISABLE_MEM_POOLS
43 struct _GAllocator
/* from gmem.c */
51 GNode
*free_nodes
; /* implementation specific */
54 G_LOCK_DEFINE_STATIC (current_allocator
);
55 static GAllocator
*current_allocator
= NULL
;
57 /* HOLDS: current_allocator_lock */
59 g_node_validate_allocator (GAllocator
*allocator
)
61 g_return_if_fail (allocator
!= NULL
);
62 g_return_if_fail (allocator
->is_unused
== TRUE
);
64 if (allocator
->type
!= G_ALLOCATOR_NODE
)
66 allocator
->type
= G_ALLOCATOR_NODE
;
67 if (allocator
->mem_chunk
)
69 g_mem_chunk_destroy (allocator
->mem_chunk
);
70 allocator
->mem_chunk
= NULL
;
74 if (!allocator
->mem_chunk
)
76 allocator
->mem_chunk
= g_mem_chunk_new (allocator
->name
,
78 sizeof (GNode
) * allocator
->n_preallocs
,
80 allocator
->free_nodes
= NULL
;
83 allocator
->is_unused
= FALSE
;
87 g_node_push_allocator (GAllocator
*allocator
)
89 G_LOCK (current_allocator
);
90 g_node_validate_allocator (allocator
);
91 allocator
->last
= current_allocator
;
92 current_allocator
= allocator
;
93 G_UNLOCK (current_allocator
);
97 g_node_pop_allocator (void)
99 G_LOCK (current_allocator
);
100 if (current_allocator
)
102 GAllocator
*allocator
;
104 allocator
= current_allocator
;
105 current_allocator
= allocator
->last
;
106 allocator
->last
= NULL
;
107 allocator
->is_unused
= TRUE
;
109 G_UNLOCK (current_allocator
);
113 /* --- functions --- */
115 g_node_new (gpointer data
)
119 G_LOCK (current_allocator
);
120 if (!current_allocator
)
122 GAllocator
*allocator
= g_allocator_new ("GLib default GNode allocator",
124 g_node_validate_allocator (allocator
);
125 allocator
->last
= NULL
;
126 current_allocator
= allocator
;
128 if (!current_allocator
->free_nodes
)
129 node
= g_chunk_new (GNode
, current_allocator
->mem_chunk
);
132 node
= current_allocator
->free_nodes
;
133 current_allocator
->free_nodes
= node
->next
;
135 G_UNLOCK (current_allocator
);
141 node
->children
= NULL
;
147 g_nodes_free (GNode
*node
)
154 if (parent
->children
)
155 g_nodes_free (parent
->children
);
157 #ifdef ENABLE_GC_FRIENDLY
160 parent
->parent
= NULL
;
161 parent
->children
= NULL
;
162 #endif /* ENABLE_GC_FRIENDLY */
165 parent
= parent
->next
;
170 G_LOCK (current_allocator
);
171 parent
->next
= current_allocator
->free_nodes
;
172 current_allocator
->free_nodes
= node
;
173 G_UNLOCK (current_allocator
);
175 #else /* DISABLE_MEM_POOLS */
178 g_node_new (gpointer data
)
182 node
= g_new0 (GNode
, 1);
190 g_nodes_free (GNode
*root
)
198 g_nodes_free (node
->children
);
206 g_node_destroy (GNode
*root
)
208 g_return_if_fail (root
!= NULL
);
210 if (!G_NODE_IS_ROOT (root
))
211 g_node_unlink (root
);
217 g_node_unlink (GNode
*node
)
219 g_return_if_fail (node
!= NULL
);
222 node
->prev
->next
= node
->next
;
223 else if (node
->parent
)
224 node
->parent
->children
= node
->next
;
228 node
->next
->prev
= node
->prev
;
235 g_node_copy (GNode
*node
)
237 GNode
*new_node
= NULL
;
243 new_node
= g_node_new (node
->data
);
245 for (child
= g_node_last_child (node
); child
; child
= child
->prev
)
246 g_node_prepend (new_node
, g_node_copy (child
));
253 g_node_insert (GNode
*parent
,
257 g_return_val_if_fail (parent
!= NULL
, node
);
258 g_return_val_if_fail (node
!= NULL
, node
);
259 g_return_val_if_fail (G_NODE_IS_ROOT (node
), node
);
262 return g_node_insert_before (parent
,
263 g_node_nth_child (parent
, position
),
265 else if (position
== 0)
266 return g_node_prepend (parent
, node
);
267 else /* if (position < 0) */
268 return g_node_append (parent
, node
);
272 g_node_insert_before (GNode
*parent
,
276 g_return_val_if_fail (parent
!= NULL
, node
);
277 g_return_val_if_fail (node
!= NULL
, node
);
278 g_return_val_if_fail (G_NODE_IS_ROOT (node
), node
);
280 g_return_val_if_fail (sibling
->parent
== parent
, node
);
282 node
->parent
= parent
;
288 node
->prev
= sibling
->prev
;
289 node
->prev
->next
= node
;
290 node
->next
= sibling
;
291 sibling
->prev
= node
;
295 node
->parent
->children
= node
;
296 node
->next
= sibling
;
297 sibling
->prev
= node
;
302 if (parent
->children
)
304 sibling
= parent
->children
;
305 while (sibling
->next
)
306 sibling
= sibling
->next
;
307 node
->prev
= sibling
;
308 sibling
->next
= node
;
311 node
->parent
->children
= node
;
318 g_node_insert_after (GNode
*parent
,
322 g_return_val_if_fail (parent
!= NULL
, node
);
323 g_return_val_if_fail (node
!= NULL
, node
);
324 g_return_val_if_fail (G_NODE_IS_ROOT (node
), node
);
326 g_return_val_if_fail (sibling
->parent
== parent
, node
);
328 node
->parent
= parent
;
334 sibling
->next
->prev
= node
;
336 node
->next
= sibling
->next
;
337 node
->prev
= sibling
;
338 sibling
->next
= node
;
342 if (parent
->children
)
344 node
->next
= parent
->children
;
345 parent
->children
->prev
= node
;
347 parent
->children
= node
;
354 g_node_prepend (GNode
*parent
,
357 g_return_val_if_fail (parent
!= NULL
, node
);
359 return g_node_insert_before (parent
, parent
->children
, node
);
363 g_node_get_root (GNode
*node
)
365 g_return_val_if_fail (node
!= NULL
, NULL
);
374 g_node_is_ancestor (GNode
*node
,
377 g_return_val_if_fail (node
!= NULL
, FALSE
);
378 g_return_val_if_fail (descendant
!= NULL
, FALSE
);
382 if (descendant
->parent
== node
)
385 descendant
= descendant
->parent
;
391 /* returns 1 for root, 2 for first level children,
392 * 3 for children's children...
395 g_node_depth (GNode
*node
)
397 register guint depth
= 0;
409 g_node_reverse_children (GNode
*node
)
414 g_return_if_fail (node
!= NULL
);
416 child
= node
->children
;
422 last
->next
= last
->prev
;
425 node
->children
= last
;
429 g_node_max_height (GNode
*root
)
431 register GNode
*child
;
432 register guint max_height
= 0;
437 child
= root
->children
;
440 register guint tmp_height
;
442 tmp_height
= g_node_max_height (child
);
443 if (tmp_height
> max_height
)
444 max_height
= tmp_height
;
448 return max_height
+ 1;
452 g_node_traverse_pre_order (GNode
*node
,
453 GTraverseFlags flags
,
454 GNodeTraverseFunc func
,
461 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
465 child
= node
->children
;
468 register GNode
*current
;
471 child
= current
->next
;
472 if (g_node_traverse_pre_order (current
, flags
, func
, data
))
476 else if ((flags
& G_TRAVERSE_LEAFS
) &&
484 g_node_depth_traverse_pre_order (GNode
*node
,
485 GTraverseFlags flags
,
487 GNodeTraverseFunc func
,
494 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
502 child
= node
->children
;
505 register GNode
*current
;
508 child
= current
->next
;
509 if (g_node_depth_traverse_pre_order (current
, flags
, depth
, func
, data
))
513 else if ((flags
& G_TRAVERSE_LEAFS
) &&
521 g_node_traverse_post_order (GNode
*node
,
522 GTraverseFlags flags
,
523 GNodeTraverseFunc func
,
530 child
= node
->children
;
533 register GNode
*current
;
536 child
= current
->next
;
537 if (g_node_traverse_post_order (current
, flags
, func
, data
))
541 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
546 else if ((flags
& G_TRAVERSE_LEAFS
) &&
554 g_node_depth_traverse_post_order (GNode
*node
,
555 GTraverseFlags flags
,
557 GNodeTraverseFunc func
,
567 child
= node
->children
;
570 register GNode
*current
;
573 child
= current
->next
;
574 if (g_node_depth_traverse_post_order (current
, flags
, depth
, func
, data
))
579 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
584 else if ((flags
& G_TRAVERSE_LEAFS
) &&
592 g_node_traverse_in_order (GNode
*node
,
593 GTraverseFlags flags
,
594 GNodeTraverseFunc func
,
600 register GNode
*current
;
602 child
= node
->children
;
604 child
= current
->next
;
606 if (g_node_traverse_in_order (current
, flags
, func
, data
))
609 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
616 child
= current
->next
;
617 if (g_node_traverse_in_order (current
, flags
, func
, data
))
621 else if ((flags
& G_TRAVERSE_LEAFS
) &&
629 g_node_depth_traverse_in_order (GNode
*node
,
630 GTraverseFlags flags
,
632 GNodeTraverseFunc func
,
641 register GNode
*current
;
643 child
= node
->children
;
645 child
= current
->next
;
647 if (g_node_depth_traverse_in_order (current
, flags
, depth
, func
, data
))
650 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
657 child
= current
->next
;
658 if (g_node_depth_traverse_in_order (current
, flags
, depth
, func
, data
))
662 else if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
666 else if ((flags
& G_TRAVERSE_LEAFS
) &&
674 g_node_traverse_children (GNode
*node
,
675 GTraverseFlags flags
,
676 GNodeTraverseFunc func
,
681 child
= node
->children
;
685 register GNode
*current
;
688 child
= current
->next
;
690 if (current
->children
)
692 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
693 func (current
, data
))
696 else if ((flags
& G_TRAVERSE_LEAFS
) &&
697 func (current
, data
))
701 child
= node
->children
;
705 register GNode
*current
;
708 child
= current
->next
;
710 if (current
->children
&&
711 g_node_traverse_children (current
, flags
, func
, data
))
719 g_node_depth_traverse_children (GNode
*node
,
720 GTraverseFlags flags
,
722 GNodeTraverseFunc func
,
727 child
= node
->children
;
731 register GNode
*current
;
734 child
= current
->next
;
736 if (current
->children
)
738 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
739 func (current
, data
))
742 else if ((flags
& G_TRAVERSE_LEAFS
) &&
743 func (current
, data
))
751 child
= node
->children
;
755 register GNode
*current
;
758 child
= current
->next
;
760 if (current
->children
&&
761 g_node_depth_traverse_children (current
, flags
, depth
, func
, data
))
769 g_node_traverse (GNode
*root
,
771 GTraverseFlags flags
,
773 GNodeTraverseFunc func
,
776 g_return_if_fail (root
!= NULL
);
777 g_return_if_fail (func
!= NULL
);
778 g_return_if_fail (order
<= G_LEVEL_ORDER
);
779 g_return_if_fail (flags
<= G_TRAVERSE_MASK
);
780 g_return_if_fail (depth
== -1 || depth
> 0);
786 g_node_traverse_pre_order (root
, flags
, func
, data
);
788 g_node_depth_traverse_pre_order (root
, flags
, depth
, func
, data
);
792 g_node_traverse_post_order (root
, flags
, func
, data
);
794 g_node_depth_traverse_post_order (root
, flags
, depth
, func
, data
);
798 g_node_traverse_in_order (root
, flags
, func
, data
);
800 g_node_depth_traverse_in_order (root
, flags
, depth
, func
, data
);
805 if (!((flags
& G_TRAVERSE_NON_LEAFS
) &&
809 g_node_traverse_children (root
, flags
, func
, data
);
814 g_node_depth_traverse_children (root
, flags
, depth
, func
, data
);
818 else if (flags
& G_TRAVERSE_LEAFS
)
825 g_node_find_func (GNode
*node
,
828 register gpointer
*d
= data
;
830 if (*d
!= node
->data
)
839 g_node_find (GNode
*root
,
841 GTraverseFlags flags
,
846 g_return_val_if_fail (root
!= NULL
, NULL
);
847 g_return_val_if_fail (order
<= G_LEVEL_ORDER
, NULL
);
848 g_return_val_if_fail (flags
<= G_TRAVERSE_MASK
, NULL
);
853 g_node_traverse (root
, order
, flags
, -1, g_node_find_func
, d
);
859 g_node_count_func (GNode
*node
,
860 GTraverseFlags flags
,
867 if (flags
& G_TRAVERSE_NON_LEAFS
)
870 child
= node
->children
;
873 g_node_count_func (child
, flags
, n
);
877 else if (flags
& G_TRAVERSE_LEAFS
)
882 g_node_n_nodes (GNode
*root
,
883 GTraverseFlags flags
)
887 g_return_val_if_fail (root
!= NULL
, 0);
888 g_return_val_if_fail (flags
<= G_TRAVERSE_MASK
, 0);
890 g_node_count_func (root
, flags
, &n
);
896 g_node_last_child (GNode
*node
)
898 g_return_val_if_fail (node
!= NULL
, NULL
);
900 node
= node
->children
;
909 g_node_nth_child (GNode
*node
,
912 g_return_val_if_fail (node
!= NULL
, NULL
);
914 node
= node
->children
;
916 while ((n
-- > 0) && node
)
923 g_node_n_children (GNode
*node
)
927 g_return_val_if_fail (node
!= NULL
, 0);
929 node
= node
->children
;
940 g_node_find_child (GNode
*node
,
941 GTraverseFlags flags
,
944 g_return_val_if_fail (node
!= NULL
, NULL
);
945 g_return_val_if_fail (flags
<= G_TRAVERSE_MASK
, NULL
);
947 node
= node
->children
;
950 if (node
->data
== data
)
952 if (G_NODE_IS_LEAF (node
))
954 if (flags
& G_TRAVERSE_LEAFS
)
959 if (flags
& G_TRAVERSE_NON_LEAFS
)
970 g_node_child_position (GNode
*node
,
973 register guint n
= 0;
975 g_return_val_if_fail (node
!= NULL
, -1);
976 g_return_val_if_fail (child
!= NULL
, -1);
977 g_return_val_if_fail (child
->parent
== node
, -1);
979 node
= node
->children
;
992 g_node_child_index (GNode
*node
,
995 register guint n
= 0;
997 g_return_val_if_fail (node
!= NULL
, -1);
999 node
= node
->children
;
1002 if (node
->data
== data
)
1012 g_node_first_sibling (GNode
*node
)
1014 g_return_val_if_fail (node
!= NULL
, NULL
);
1017 return node
->parent
->children
;
1026 g_node_last_sibling (GNode
*node
)
1028 g_return_val_if_fail (node
!= NULL
, NULL
);
1037 g_node_children_foreach (GNode
*node
,
1038 GTraverseFlags flags
,
1039 GNodeForeachFunc func
,
1042 g_return_if_fail (node
!= NULL
);
1043 g_return_if_fail (flags
<= G_TRAVERSE_MASK
);
1044 g_return_if_fail (func
!= NULL
);
1046 node
= node
->children
;
1049 register GNode
*current
;
1052 node
= current
->next
;
1053 if (G_NODE_IS_LEAF (current
))
1055 if (flags
& G_TRAVERSE_LEAFS
)
1056 func (current
, data
);
1060 if (flags
& G_TRAVERSE_NON_LEAFS
)
1061 func (current
, data
);