1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
21 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
22 * file for a list of people on the GLib Team. See the ChangeLog
23 * files for a list of changes. These files are distributed with
24 * GLib at ftp://ftp.gtk.org/pub/gtk/.
27 #undef G_DISABLE_ASSERT
44 #define C2P(c) ((gpointer) ((long) (c)))
45 #define P2C(p) ((gchar) ((long) (p)))
48 node_build_string (GNode
*node
,
55 c
[0] = P2C (node
->data
);
57 string
= g_strconcat (*p
? *p
: "", c
, NULL
);
78 root
= g_node_new (C2P ('A'));
79 node_B
= g_node_new (C2P ('B'));
80 g_node_append (root
, node_B
);
81 g_node_append_data (node_B
, C2P ('E'));
82 g_node_prepend_data (node_B
, C2P ('C'));
83 node_D
= g_node_new (C2P ('D'));
84 g_node_insert (node_B
, 1, node_D
);
85 node_F
= g_node_new (C2P ('F'));
86 g_node_append (root
, node_F
);
87 node_G
= g_node_new (C2P ('G'));
88 g_node_append (node_F
, node_G
);
89 node_J
= g_node_new (C2P ('J'));
90 g_node_prepend (node_G
, node_J
);
91 g_node_insert (node_G
, 42, g_node_new (C2P ('K')));
92 g_node_insert_data (node_G
, 0, C2P ('H'));
93 g_node_insert (node_G
, 1, g_node_new (C2P ('I')));
103 * for in-order traversal, 'G' is considered to be the "left"
104 * child of 'F', which will cause 'F' to be the last node visited.
107 node_C
= node_B
->children
;
108 node_E
= node_D
->next
;
110 n
= g_node_last_sibling (node_C
);
111 g_assert (n
== node_E
);
112 n
= g_node_last_sibling (node_D
);
113 g_assert (n
== node_E
);
114 n
= g_node_last_sibling (node_E
);
115 g_assert (n
== node_E
);
118 g_node_traverse (root
, G_PRE_ORDER
, G_TRAVERSE_ALL
, -1, node_build_string
, &tstring
);
119 g_assert_cmpstr (tstring
, ==, "ABCDEFGHIJK");
120 g_free (tstring
); tstring
= NULL
;
121 g_node_traverse (root
, G_PRE_ORDER
, G_TRAVERSE_ALL
, 2, node_build_string
, &tstring
);
122 g_assert_cmpstr (tstring
, ==, "ABF");
123 g_free (tstring
); tstring
= NULL
;
124 g_node_traverse (root
, G_POST_ORDER
, G_TRAVERSE_ALL
, -1, node_build_string
, &tstring
);
125 g_assert_cmpstr (tstring
, ==, "CDEBHIJKGFA");
126 g_free (tstring
); tstring
= NULL
;
127 g_node_traverse (root
, G_POST_ORDER
, G_TRAVERSE_ALL
, 2, node_build_string
, &tstring
);
128 g_assert_cmpstr (tstring
, ==, "BFA");
129 g_free (tstring
); tstring
= NULL
;
130 g_node_traverse (root
, G_IN_ORDER
, G_TRAVERSE_ALL
, -1, node_build_string
, &tstring
);
131 g_assert_cmpstr (tstring
, ==, "CBDEAHGIJKF");
132 g_free (tstring
); tstring
= NULL
;
133 g_node_traverse (root
, G_IN_ORDER
, G_TRAVERSE_ALL
, 2, node_build_string
, &tstring
);
134 g_assert_cmpstr (tstring
, ==, "BAF");
135 g_free (tstring
); tstring
= NULL
;
136 g_node_traverse (root
, G_LEVEL_ORDER
, G_TRAVERSE_ALL
, -1, node_build_string
, &tstring
);
137 g_assert_cmpstr (tstring
, ==, "ABFCDEGHIJK");
138 g_free (tstring
); tstring
= NULL
;
139 g_node_traverse (root
, G_LEVEL_ORDER
, G_TRAVERSE_ALL
, 2, node_build_string
, &tstring
);
140 g_assert_cmpstr (tstring
, ==, "ABF");
141 g_free (tstring
); tstring
= NULL
;
143 g_node_traverse (root
, G_LEVEL_ORDER
, G_TRAVERSE_LEAFS
, -1, node_build_string
, &tstring
);
144 g_assert_cmpstr (tstring
, ==, "CDEHIJK");
145 g_free (tstring
); tstring
= NULL
;
146 g_node_traverse (root
, G_PRE_ORDER
, G_TRAVERSE_NON_LEAFS
, -1, node_build_string
, &tstring
);
147 g_assert_cmpstr (tstring
, ==, "ABFG");
148 g_free (tstring
); tstring
= NULL
;
150 g_node_reverse_children (node_B
);
151 g_node_reverse_children (node_G
);
153 g_node_traverse (root
, G_LEVEL_ORDER
, G_TRAVERSE_ALL
, -1, node_build_string
, &tstring
);
154 g_assert_cmpstr (tstring
, ==, "ABFEDCGKJIH");
155 g_free (tstring
); tstring
= NULL
;
157 g_node_append (node_D
, g_node_new (C2P ('L')));
158 g_node_append (node_D
, g_node_new (C2P ('M')));
160 g_node_traverse (root
, G_LEVEL_ORDER
, G_TRAVERSE_ALL
, -1, node_build_string
, &tstring
);
161 g_assert_cmpstr (tstring
, ==, "ABFEDCGLMKJIH");
162 g_free (tstring
); tstring
= NULL
;
164 g_node_destroy (root
);
168 construct_test (void)
179 root
= g_node_new (C2P ('A'));
180 g_assert_cmpint (g_node_depth (root
), ==, 1);
181 g_assert_cmpint (g_node_max_height (root
), ==, 1);
183 node_B
= g_node_new (C2P ('B'));
184 g_node_append (root
, node_B
);
185 g_assert (root
->children
== node_B
);
187 g_node_append_data (node_B
, C2P ('E'));
188 g_node_prepend_data (node_B
, C2P ('C'));
189 node_D
= g_node_new (C2P ('D'));
190 g_node_insert (node_B
, 1, node_D
);
192 node_F
= g_node_new (C2P ('F'));
193 g_node_append (root
, node_F
);
194 g_assert (root
->children
->next
== node_F
);
196 node_G
= g_node_new (C2P ('G'));
197 g_node_append (node_F
, node_G
);
198 node_J
= g_node_new (C2P ('J'));
199 g_node_prepend (node_G
, node_J
);
200 g_node_insert (node_G
, 42, g_node_new (C2P ('K')));
201 g_node_insert_data (node_G
, 0, C2P ('H'));
202 g_node_insert (node_G
, 1, g_node_new (C2P ('I')));
212 g_assert_cmpint (g_node_depth (root
), ==, 1);
213 g_assert_cmpint (g_node_max_height (root
), ==, 4);
214 g_assert_cmpint (g_node_depth (node_G
->children
->next
), ==, 4);
215 g_assert_cmpint (g_node_n_nodes (root
, G_TRAVERSE_LEAFS
), ==, 7);
216 g_assert_cmpint (g_node_n_nodes (root
, G_TRAVERSE_NON_LEAFS
), ==, 4);
217 g_assert_cmpint (g_node_n_nodes (root
, G_TRAVERSE_ALL
), ==, 11);
218 g_assert_cmpint (g_node_max_height (node_F
), ==, 3);
219 g_assert_cmpint (g_node_n_children (node_G
), ==, 4);
220 g_assert (g_node_find_child (root
, G_TRAVERSE_ALL
, C2P ('F')) == node_F
);
221 g_assert (g_node_find (root
, G_LEVEL_ORDER
, G_TRAVERSE_NON_LEAFS
, C2P ('I')) == NULL
);
222 g_assert (g_node_find (root
, G_IN_ORDER
, G_TRAVERSE_LEAFS
, C2P ('J')) == node_J
);
224 for (i
= 0; i
< g_node_n_children (node_B
); i
++)
226 node
= g_node_nth_child (node_B
, i
);
227 g_assert_cmpint (P2C (node
->data
), ==, ('C' + i
));
230 for (i
= 0; i
< g_node_n_children (node_G
); i
++)
231 g_assert_cmpint (g_node_child_position (node_G
, g_node_nth_child (node_G
, i
)), ==, i
);
233 g_node_destroy (root
);
237 allocation_test (void)
243 root
= g_node_new (NULL
);
246 for (i
= 0; i
< 2048; i
++)
248 g_node_append (node
, g_node_new (NULL
));
250 node
= node
->children
->next
;
252 g_assert_cmpint (g_node_max_height (root
), >, 100);
253 g_assert_cmpint (g_node_n_nodes (root
, G_TRAVERSE_ALL
), ==, 1 + 2048);
255 g_node_destroy (root
);
269 root
= g_node_new (C2P ('A'));
270 node_B
= g_node_new (C2P ('B'));
271 g_node_append (root
, node_B
);
272 node_D
= g_node_new (C2P ('D'));
273 g_node_append (root
, node_D
);
274 node_C
= g_node_new (C2P ('C'));
275 g_node_insert_after (root
, node_B
, node_C
);
276 node_E
= g_node_new (C2P ('E'));
277 g_node_append (node_C
, node_E
);
279 g_assert (g_node_get_root (node_E
) == root
);
280 g_assert (g_node_is_ancestor (root
, node_B
));
281 g_assert (g_node_is_ancestor (root
, node_E
));
282 g_assert (!g_node_is_ancestor (node_B
, node_D
));
283 g_assert (g_node_first_sibling (node_D
) == node_B
);
284 g_assert (g_node_first_sibling (node_E
) == node_E
);
285 g_assert_cmpint (g_node_child_index (root
, C2P ('B')), ==, 0);
286 g_assert_cmpint (g_node_child_index (root
, C2P ('C')), ==, 1);
287 g_assert_cmpint (g_node_child_index (root
, C2P ('D')), ==, 2);
288 g_assert_cmpint (g_node_child_index (root
, C2P ('E')), ==, -1);
291 g_node_children_foreach (root
, G_TRAVERSE_ALL
, (GNodeForeachFunc
)node_build_string
, &tstring
);
292 g_assert_cmpstr (tstring
, ==, "BCD");
293 g_free (tstring
); tstring
= NULL
;
295 g_node_children_foreach (root
, G_TRAVERSE_LEAVES
, (GNodeForeachFunc
)node_build_string
, &tstring
);
296 g_assert_cmpstr (tstring
, ==, "BD");
297 g_free (tstring
); tstring
= NULL
;
299 g_node_children_foreach (root
, G_TRAVERSE_NON_LEAVES
, (GNodeForeachFunc
)node_build_string
, &tstring
);
300 g_assert_cmpstr (tstring
, ==, "C");
301 g_free (tstring
); tstring
= NULL
;
303 g_node_destroy (root
);
307 check_order (GNode
*node
,
310 gchar
**expected
= data
;
313 d
= GPOINTER_TO_INT (node
->data
);
314 g_assert_cmpint (d
, ==, **expected
);
329 * -------- a --------
337 root
= g_node_new (C2P ('a'));
338 node
= g_node_append_data (root
, C2P ('b'));
339 g_node_append_data (node
, C2P ('e'));
340 g_node_append_data (node
, C2P ('f'));
341 g_node_append_data (node
, C2P ('g'));
343 node
= cnode
= g_node_append_data (root
, C2P ('c'));
344 g_node_append_data (node
, C2P ('h'));
345 g_node_append_data (node
, C2P ('i'));
346 g_node_append_data (node
, C2P ('j'));
348 node
= g_node_append_data (root
, C2P ('d'));
349 g_node_append_data (node
, C2P ('k'));
350 g_node_append_data (node
, C2P ('l'));
351 g_node_append_data (node
, C2P ('m'));
353 g_node_unlink (cnode
);
355 expected
= "abdefgklm";
356 g_node_traverse (root
, G_LEVEL_ORDER
, G_TRAVERSE_ALL
, -1, check_order
, &expected
);
359 g_node_traverse (cnode
, G_LEVEL_ORDER
, G_TRAVERSE_ALL
, -1, check_order
, &expected
);
361 g_node_destroy (root
);
362 g_node_destroy (cnode
);
366 copy_up (gconstpointer src
,
371 l
= GPOINTER_TO_INT (src
);
372 u
= g_ascii_toupper (l
);
374 return GINT_TO_POINTER ((int)u
);
384 root
= g_node_new (C2P ('a'));
385 g_node_append_data (root
, C2P ('b'));
386 g_node_append_data (root
, C2P ('c'));
387 g_node_append_data (root
, C2P ('d'));
390 g_node_traverse (root
, G_LEVEL_ORDER
, G_TRAVERSE_ALL
, -1, check_order
, &expected
);
392 copy
= g_node_copy (root
);
395 g_node_traverse (copy
, G_LEVEL_ORDER
, G_TRAVERSE_ALL
, -1, check_order
, &expected
);
397 g_node_destroy (copy
);
399 copy
= g_node_copy_deep (root
, copy_up
, NULL
);
402 g_node_traverse (copy
, G_LEVEL_ORDER
, G_TRAVERSE_ALL
, -1, check_order
, &expected
);
404 g_node_destroy (copy
);
406 g_node_destroy (root
);
413 g_test_init (&argc
, &argv
, NULL
);
415 g_test_add_func ("/node/allocation", allocation_test
);
416 g_test_add_func ("/node/construction", construct_test
);
417 g_test_add_func ("/node/traversal", traversal_test
);
418 g_test_add_func ("/node/misc", misc_test
);
419 g_test_add_func ("/node/unlink", unlink_test
);
420 g_test_add_func ("/node/copy", copy_test
);
422 return g_test_run ();