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_level (GNode
*node
,
675 GTraverseFlags flags
,
677 GNodeTraverseFunc func
,
679 gboolean
*more_levels
)
686 return (flags
& G_TRAVERSE_NON_LEAFS
) && func (node
, data
);
690 return (flags
& G_TRAVERSE_LEAFS
) && func (node
, data
);
695 node
= node
->children
;
699 if (g_node_traverse_level (node
, flags
, level
- 1, func
, data
, more_levels
))
710 g_node_depth_traverse_level (GNode
*node
,
711 GTraverseFlags flags
,
713 GNodeTraverseFunc func
,
717 gboolean more_levels
;
720 while (level
!= depth
)
723 if (g_node_traverse_level (node
, flags
, level
, func
, data
, &more_levels
))
733 g_node_traverse (GNode
*root
,
735 GTraverseFlags flags
,
737 GNodeTraverseFunc func
,
740 g_return_if_fail (root
!= NULL
);
741 g_return_if_fail (func
!= NULL
);
742 g_return_if_fail (order
<= G_LEVEL_ORDER
);
743 g_return_if_fail (flags
<= G_TRAVERSE_MASK
);
744 g_return_if_fail (depth
== -1 || depth
> 0);
750 g_node_traverse_pre_order (root
, flags
, func
, data
);
752 g_node_depth_traverse_pre_order (root
, flags
, depth
, func
, data
);
756 g_node_traverse_post_order (root
, flags
, func
, data
);
758 g_node_depth_traverse_post_order (root
, flags
, depth
, func
, data
);
762 g_node_traverse_in_order (root
, flags
, func
, data
);
764 g_node_depth_traverse_in_order (root
, flags
, depth
, func
, data
);
767 g_node_depth_traverse_level (root
, flags
, depth
, func
, data
);
773 g_node_find_func (GNode
*node
,
776 register gpointer
*d
= data
;
778 if (*d
!= node
->data
)
787 g_node_find (GNode
*root
,
789 GTraverseFlags flags
,
794 g_return_val_if_fail (root
!= NULL
, NULL
);
795 g_return_val_if_fail (order
<= G_LEVEL_ORDER
, NULL
);
796 g_return_val_if_fail (flags
<= G_TRAVERSE_MASK
, NULL
);
801 g_node_traverse (root
, order
, flags
, -1, g_node_find_func
, d
);
807 g_node_count_func (GNode
*node
,
808 GTraverseFlags flags
,
815 if (flags
& G_TRAVERSE_NON_LEAFS
)
818 child
= node
->children
;
821 g_node_count_func (child
, flags
, n
);
825 else if (flags
& G_TRAVERSE_LEAFS
)
830 g_node_n_nodes (GNode
*root
,
831 GTraverseFlags flags
)
835 g_return_val_if_fail (root
!= NULL
, 0);
836 g_return_val_if_fail (flags
<= G_TRAVERSE_MASK
, 0);
838 g_node_count_func (root
, flags
, &n
);
844 g_node_last_child (GNode
*node
)
846 g_return_val_if_fail (node
!= NULL
, NULL
);
848 node
= node
->children
;
857 g_node_nth_child (GNode
*node
,
860 g_return_val_if_fail (node
!= NULL
, NULL
);
862 node
= node
->children
;
864 while ((n
-- > 0) && node
)
871 g_node_n_children (GNode
*node
)
875 g_return_val_if_fail (node
!= NULL
, 0);
877 node
= node
->children
;
888 g_node_find_child (GNode
*node
,
889 GTraverseFlags flags
,
892 g_return_val_if_fail (node
!= NULL
, NULL
);
893 g_return_val_if_fail (flags
<= G_TRAVERSE_MASK
, NULL
);
895 node
= node
->children
;
898 if (node
->data
== data
)
900 if (G_NODE_IS_LEAF (node
))
902 if (flags
& G_TRAVERSE_LEAFS
)
907 if (flags
& G_TRAVERSE_NON_LEAFS
)
918 g_node_child_position (GNode
*node
,
921 register guint n
= 0;
923 g_return_val_if_fail (node
!= NULL
, -1);
924 g_return_val_if_fail (child
!= NULL
, -1);
925 g_return_val_if_fail (child
->parent
== node
, -1);
927 node
= node
->children
;
940 g_node_child_index (GNode
*node
,
943 register guint n
= 0;
945 g_return_val_if_fail (node
!= NULL
, -1);
947 node
= node
->children
;
950 if (node
->data
== data
)
960 g_node_first_sibling (GNode
*node
)
962 g_return_val_if_fail (node
!= NULL
, NULL
);
965 return node
->parent
->children
;
974 g_node_last_sibling (GNode
*node
)
976 g_return_val_if_fail (node
!= NULL
, NULL
);
985 g_node_children_foreach (GNode
*node
,
986 GTraverseFlags flags
,
987 GNodeForeachFunc func
,
990 g_return_if_fail (node
!= NULL
);
991 g_return_if_fail (flags
<= G_TRAVERSE_MASK
);
992 g_return_if_fail (func
!= NULL
);
994 node
= node
->children
;
997 register GNode
*current
;
1000 node
= current
->next
;
1001 if (G_NODE_IS_LEAF (current
))
1003 if (flags
& G_TRAVERSE_LEAFS
)
1004 func (current
, data
);
1008 if (flags
& G_TRAVERSE_NON_LEAFS
)
1009 func (current
, data
);