Branch data Line data Source code
1 : : /* GLIB - Library of useful routines for C programming
2 : : * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
3 : : *
4 : : * SPDX-License-Identifier: LGPL-2.1-or-later
5 : : *
6 : : * This library is free software; you can redistribute it and/or
7 : : * modify it under the terms of the GNU Lesser General Public
8 : : * License as published by the Free Software Foundation; either
9 : : * version 2.1 of the License, or (at your option) any later version.
10 : : *
11 : : * This library is distributed in the hope that it will be useful,
12 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 : : * Lesser General Public License for more details.
15 : : *
16 : : * You should have received a copy of the GNU Lesser General Public
17 : : * License along with this library; if not, see <http://www.gnu.org/licenses/>.
18 : : */
19 : :
20 : : /*
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/.
25 : : */
26 : :
27 : : #undef G_DISABLE_ASSERT
28 : : #undef G_LOG_DOMAIN
29 : :
30 : : /* We are testing some deprecated APIs here */
31 : : #ifndef GLIB_DISABLE_DEPRECATION_WARNINGS
32 : : #define GLIB_DISABLE_DEPRECATION_WARNINGS
33 : : #endif
34 : :
35 : : #include <stdio.h>
36 : : #include <string.h>
37 : : #include "glib.h"
38 : :
39 : :
40 : : static gint
41 : 3106 : my_compare (gconstpointer a,
42 : : gconstpointer b)
43 : : {
44 : 3106 : const char *cha = a;
45 : 3106 : const char *chb = b;
46 : :
47 : 3106 : return *cha - *chb;
48 : : }
49 : :
50 : : static gint
51 : 584 : my_compare_with_data (gconstpointer a,
52 : : gconstpointer b,
53 : : gpointer user_data)
54 : : {
55 : 584 : const char *cha = a;
56 : 584 : const char *chb = b;
57 : :
58 : : /* just check that we got the right data */
59 : 584 : g_assert_cmpint (GPOINTER_TO_INT (user_data), ==, 123);
60 : :
61 : 584 : return *cha - *chb;
62 : : }
63 : :
64 : : static gint
65 : 39 : my_search (gconstpointer a,
66 : : gconstpointer b)
67 : : {
68 : 39 : return my_compare (b, a);
69 : : }
70 : :
71 : : static gpointer destroyed_key = NULL;
72 : : static gpointer destroyed_value = NULL;
73 : : static guint destroyed_key_count = 0;
74 : : static guint destroyed_value_count = 0;
75 : :
76 : : static void
77 : 127 : my_key_destroy (gpointer key)
78 : : {
79 : 127 : destroyed_key = key;
80 : 127 : destroyed_key_count++;
81 : 127 : }
82 : :
83 : : static void
84 : 127 : my_value_destroy (gpointer value)
85 : : {
86 : 127 : destroyed_value = value;
87 : 127 : destroyed_value_count++;
88 : 127 : }
89 : :
90 : : static gint
91 : 54 : my_traverse (gpointer key,
92 : : gpointer value,
93 : : gpointer data)
94 : : {
95 : 54 : char *ch = key;
96 : :
97 : 54 : g_assert_cmpint ((*ch), >, 0);
98 : :
99 [ + + ]: 54 : if (*ch == 'd')
100 : 2 : return TRUE;
101 : :
102 : 52 : return FALSE;
103 : : }
104 : :
105 : : char chars[] =
106 : : "0123456789"
107 : : "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
108 : : "abcdefghijklmnopqrstuvwxyz";
109 : :
110 : : char chars2[] =
111 : : "0123456789"
112 : : "abcdefghijklmnopqrstuvwxyz";
113 : :
114 : : static gint
115 : 346 : check_order (gpointer key,
116 : : gpointer value,
117 : : gpointer data)
118 : : {
119 : 346 : char **p = data;
120 : 346 : char *ch = key;
121 : :
122 : 346 : g_assert_cmpint (**p, ==, *ch);
123 : :
124 : 346 : (*p)++;
125 : :
126 : 346 : return FALSE;
127 : : }
128 : :
129 : : static void
130 : 1 : test_tree_search (void)
131 : : {
132 : : gint i;
133 : : GTree *tree;
134 : : gboolean removed;
135 : : gchar c;
136 : : gchar *p, *d;
137 : :
138 : 1 : tree = g_tree_new_with_data (my_compare_with_data, GINT_TO_POINTER(123));
139 : :
140 [ + + ]: 63 : for (i = 0; chars[i]; i++)
141 : 62 : g_tree_insert (tree, &chars[i], &chars[i]);
142 : :
143 : 1 : g_tree_foreach (tree, my_traverse, NULL);
144 : :
145 : 1 : g_assert_cmpint (g_tree_nnodes (tree), ==, strlen (chars));
146 : 1 : g_assert_cmpint (g_tree_height (tree), ==, 6);
147 : :
148 : 1 : p = chars;
149 : 1 : g_tree_foreach (tree, check_order, &p);
150 : :
151 [ + + ]: 27 : for (i = 0; i < 26; i++)
152 : : {
153 : 26 : removed = g_tree_remove (tree, &chars[i + 10]);
154 : 26 : g_assert_true (removed);
155 : : }
156 : :
157 : 1 : c = '\0';
158 : 1 : removed = g_tree_remove (tree, &c);
159 : 1 : g_assert_false (removed);
160 : :
161 : 1 : g_tree_foreach (tree, my_traverse, NULL);
162 : :
163 : 1 : g_assert_cmpint (g_tree_nnodes (tree), ==, strlen (chars2));
164 : 1 : g_assert_cmpint (g_tree_height (tree), ==, 6);
165 : :
166 : 1 : p = chars2;
167 : 1 : g_tree_foreach (tree, check_order, &p);
168 : :
169 [ + + ]: 27 : for (i = 25; i >= 0; i--)
170 : 26 : g_tree_insert (tree, &chars[i + 10], &chars[i + 10]);
171 : :
172 : 1 : p = chars;
173 : 1 : g_tree_foreach (tree, check_order, &p);
174 : :
175 : 1 : c = '0';
176 : 1 : p = g_tree_lookup (tree, &c);
177 : 1 : g_assert_true (p && *p == c);
178 : 1 : g_assert_true (g_tree_lookup_extended (tree, &c, (gpointer *)&d, (gpointer *)&p));
179 : 1 : g_assert_true (c == *d && c == *p);
180 : :
181 : 1 : c = 'A';
182 : 1 : p = g_tree_lookup (tree, &c);
183 : 1 : g_assert_true (p && *p == c);
184 : :
185 : 1 : c = 'a';
186 : 1 : p = g_tree_lookup (tree, &c);
187 : 1 : g_assert_true (p && *p == c);
188 : :
189 : 1 : c = 'z';
190 : 1 : p = g_tree_lookup (tree, &c);
191 : 1 : g_assert_true (p && *p == c);
192 : :
193 : 1 : c = '!';
194 : 1 : p = g_tree_lookup (tree, &c);
195 : 1 : g_assert_null (p);
196 : :
197 : 1 : c = '=';
198 : 1 : p = g_tree_lookup (tree, &c);
199 : 1 : g_assert_null (p);
200 : :
201 : 1 : c = '|';
202 : 1 : p = g_tree_lookup (tree, &c);
203 : 1 : g_assert_null (p);
204 : :
205 : 1 : c = '0';
206 : 1 : p = g_tree_search (tree, my_search, &c);
207 : 1 : g_assert_true (p && *p == c);
208 : :
209 : 1 : c = 'A';
210 : 1 : p = g_tree_search (tree, my_search, &c);
211 : 1 : g_assert_true (p && *p == c);
212 : :
213 : 1 : c = 'a';
214 : 1 : p = g_tree_search (tree, my_search, &c);
215 : 1 : g_assert_true (p &&*p == c);
216 : :
217 : 1 : c = 'z';
218 : 1 : p = g_tree_search (tree, my_search, &c);
219 : 1 : g_assert_true (p && *p == c);
220 : :
221 : 1 : c = '!';
222 : 1 : p = g_tree_search (tree, my_search, &c);
223 : 1 : g_assert_null (p);
224 : :
225 : 1 : c = '=';
226 : 1 : p = g_tree_search (tree, my_search, &c);
227 : 1 : g_assert_null (p);
228 : :
229 : 1 : c = '|';
230 : 1 : p = g_tree_search (tree, my_search, &c);
231 : 1 : g_assert_null (p);
232 : :
233 : 1 : g_tree_destroy (tree);
234 : 1 : }
235 : :
236 : : static void
237 : 1 : test_tree_remove (void)
238 : : {
239 : : GTree *tree;
240 : : char c, d, e, f;
241 : : gint i;
242 : : gboolean removed;
243 : : GTreeNode *node;
244 : : gchar *remove;
245 : :
246 : 1 : tree = g_tree_new_full ((GCompareDataFunc)my_compare, NULL,
247 : : my_key_destroy,
248 : : my_value_destroy);
249 : :
250 [ + + ]: 63 : for (i = 0; chars[i]; i++)
251 : 62 : g_tree_insert (tree, &chars[i], &chars[i]);
252 : :
253 : 1 : c = '0';
254 : 1 : g_tree_insert (tree, &c, &c);
255 : 1 : g_assert_true (destroyed_key == &c);
256 : 1 : g_assert_true (destroyed_value == &chars[0]);
257 : 1 : destroyed_key = NULL;
258 : 1 : destroyed_value = NULL;
259 : :
260 : 1 : d = '1';
261 : 1 : g_tree_replace (tree, &d, &d);
262 : 1 : g_assert_true (destroyed_key == &chars[1]);
263 : 1 : g_assert_true (destroyed_value == &chars[1]);
264 : 1 : destroyed_key = NULL;
265 : 1 : destroyed_value = NULL;
266 : :
267 : 1 : e = '\xff';
268 : 1 : node = g_tree_insert_node (tree, &e, &e);
269 : 1 : g_assert_nonnull (node);
270 : 1 : g_assert_null (destroyed_key);
271 : 1 : g_assert_null (destroyed_value);
272 : :
273 : 1 : c = '2';
274 : 1 : removed = g_tree_remove (tree, &c);
275 : 1 : g_assert_true (removed);
276 : 1 : g_assert_true (destroyed_key == &chars[2]);
277 : 1 : g_assert_true (destroyed_value == &chars[2]);
278 : 1 : destroyed_key = NULL;
279 : 1 : destroyed_value = NULL;
280 : :
281 : 1 : c = '3';
282 : 1 : removed = g_tree_steal (tree, &c);
283 : 1 : g_assert_true (removed);
284 : 1 : g_assert_null (destroyed_key);
285 : 1 : g_assert_null (destroyed_value);
286 : :
287 : 1 : f = '4';
288 : 1 : node = g_tree_replace_node (tree, &f, &f);
289 : 1 : g_assert_nonnull (node);
290 : 1 : g_assert_true (destroyed_key == &chars[4]);
291 : 1 : g_assert_true (destroyed_value == &chars[4]);
292 : 1 : destroyed_key = NULL;
293 : 1 : destroyed_value = NULL;
294 : :
295 : 1 : remove = "omkjigfedba";
296 [ + + ]: 12 : for (i = 0; remove[i]; i++)
297 : : {
298 : 11 : removed = g_tree_remove (tree, &remove[i]);
299 : 11 : g_assert_true (removed);
300 : : }
301 : :
302 : 1 : g_tree_destroy (tree);
303 : 1 : }
304 : :
305 : : static void
306 : 1 : test_tree_remove_all (void)
307 : : {
308 : : GTree *tree;
309 : : gsize i;
310 : :
311 : 1 : tree = g_tree_new_full ((GCompareDataFunc)my_compare, NULL,
312 : : my_key_destroy,
313 : : my_value_destroy);
314 : :
315 [ + + ]: 63 : for (i = 0; chars[i]; i++)
316 : 62 : g_tree_insert (tree, &chars[i], &chars[i]);
317 : :
318 : 1 : destroyed_key_count = 0;
319 : 1 : destroyed_value_count = 0;
320 : :
321 : 1 : g_tree_remove_all (tree);
322 : :
323 : 1 : g_assert_cmpuint (destroyed_key_count, ==, strlen (chars));
324 : 1 : g_assert_cmpuint (destroyed_value_count, ==, strlen (chars));
325 : 1 : g_assert_cmpint (g_tree_height (tree), ==, 0);
326 : 1 : g_assert_cmpint (g_tree_nnodes (tree), ==, 0);
327 : :
328 : 1 : g_tree_unref (tree);
329 : 1 : }
330 : :
331 : : static void
332 : 1 : test_tree_destroy (void)
333 : : {
334 : : GTree *tree;
335 : : gint i;
336 : :
337 : 1 : tree = g_tree_new (my_compare);
338 : :
339 [ + + ]: 63 : for (i = 0; chars[i]; i++)
340 : 62 : g_tree_insert (tree, &chars[i], &chars[i]);
341 : :
342 : 1 : g_assert_cmpint (g_tree_nnodes (tree), ==, strlen (chars));
343 : :
344 : 1 : g_tree_ref (tree);
345 : 1 : g_tree_destroy (tree);
346 : :
347 : 1 : g_assert_cmpint (g_tree_nnodes (tree), ==, 0);
348 : :
349 : 1 : g_tree_unref (tree);
350 : 1 : }
351 : :
352 : : typedef struct {
353 : : GString *s;
354 : : gint count;
355 : : } CallbackData;
356 : :
357 : : static gboolean
358 : 501 : traverse_func (gpointer key, gpointer value, gpointer data)
359 : : {
360 : 501 : CallbackData *d = data;
361 : :
362 : 501 : gchar *c = value;
363 [ + - ]: 501 : g_string_append_c (d->s, *c);
364 : :
365 : 501 : d->count--;
366 : :
367 [ + + ]: 501 : if (d->count == 0)
368 : 42 : return TRUE;
369 : :
370 : 459 : return FALSE;
371 : : }
372 : :
373 : : typedef struct {
374 : : GTraverseType traverse;
375 : : gint limit;
376 : : const gchar *expected;
377 : : } TraverseData;
378 : :
379 : : static void
380 : 1 : test_tree_traverse (void)
381 : : {
382 : : GTree *tree;
383 : : gsize i;
384 : 1 : TraverseData orders[] = {
385 : : { G_IN_ORDER, -1, "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" },
386 : : { G_IN_ORDER, 1, "0" },
387 : : { G_IN_ORDER, 2, "01" },
388 : : { G_IN_ORDER, 3, "012" },
389 : : { G_IN_ORDER, 4, "0123" },
390 : : { G_IN_ORDER, 5, "01234" },
391 : : { G_IN_ORDER, 6, "012345" },
392 : : { G_IN_ORDER, 7, "0123456" },
393 : : { G_IN_ORDER, 8, "01234567" },
394 : : { G_IN_ORDER, 9, "012345678" },
395 : : { G_IN_ORDER, 10, "0123456789" },
396 : : { G_IN_ORDER, 11, "0123456789A" },
397 : : { G_IN_ORDER, 12, "0123456789AB" },
398 : : { G_IN_ORDER, 13, "0123456789ABC" },
399 : : { G_IN_ORDER, 14, "0123456789ABCD" },
400 : :
401 : : { G_PRE_ORDER, -1, "VF73102546B98ADCENJHGILKMRPOQTSUldZXWYbachfegjiktpnmorqsxvuwyz" },
402 : : { G_PRE_ORDER, 1, "V" },
403 : : { G_PRE_ORDER, 2, "VF" },
404 : : { G_PRE_ORDER, 3, "VF7" },
405 : : { G_PRE_ORDER, 4, "VF73" },
406 : : { G_PRE_ORDER, 5, "VF731" },
407 : : { G_PRE_ORDER, 6, "VF7310" },
408 : : { G_PRE_ORDER, 7, "VF73102" },
409 : : { G_PRE_ORDER, 8, "VF731025" },
410 : : { G_PRE_ORDER, 9, "VF7310254" },
411 : : { G_PRE_ORDER, 10, "VF73102546" },
412 : : { G_PRE_ORDER, 11, "VF73102546B" },
413 : : { G_PRE_ORDER, 12, "VF73102546B9" },
414 : : { G_PRE_ORDER, 13, "VF73102546B98" },
415 : : { G_PRE_ORDER, 14, "VF73102546B98A" },
416 : :
417 : : { G_POST_ORDER, -1, "02146538A9CEDB7GIHKMLJOQPSUTRNFWYXacbZegfikjhdmonqsrpuwvzyxtlV" },
418 : : { G_POST_ORDER, 1, "0" },
419 : : { G_POST_ORDER, 2, "02" },
420 : : { G_POST_ORDER, 3, "021" },
421 : : { G_POST_ORDER, 4, "0214" },
422 : : { G_POST_ORDER, 5, "02146" },
423 : : { G_POST_ORDER, 6, "021465" },
424 : : { G_POST_ORDER, 7, "0214653" },
425 : : { G_POST_ORDER, 8, "02146538" },
426 : : { G_POST_ORDER, 9, "02146538A" },
427 : : { G_POST_ORDER, 10, "02146538A9" },
428 : : { G_POST_ORDER, 11, "02146538A9C" },
429 : : { G_POST_ORDER, 12, "02146538A9CE" },
430 : : { G_POST_ORDER, 13, "02146538A9CED" },
431 : : { G_POST_ORDER, 14, "02146538A9CEDB" }
432 : : };
433 : : CallbackData data;
434 : :
435 : 1 : tree = g_tree_new (my_compare);
436 : :
437 [ + + ]: 63 : for (i = 0; chars[i]; i++)
438 : 62 : g_tree_insert (tree, &chars[i], &chars[i]);
439 : :
440 : 1 : data.s = g_string_new ("");
441 [ + + ]: 46 : for (i = 0; i < G_N_ELEMENTS (orders); i++)
442 : : {
443 : 45 : g_string_set_size (data.s, 0);
444 : 45 : data.count = orders[i].limit;
445 : 45 : g_tree_traverse (tree, traverse_func, orders[i].traverse, &data);
446 : 45 : g_assert_cmpstr (data.s->str, ==, orders[i].expected);
447 : : }
448 : :
449 : 1 : g_tree_unref (tree);
450 : 1 : g_string_free (data.s, TRUE);
451 : 1 : }
452 : :
453 : : static void
454 : 1 : test_tree_insert (void)
455 : : {
456 : : GTree *tree;
457 : : gchar *p;
458 : : gint i;
459 : : gchar *scrambled;
460 : :
461 : 1 : tree = g_tree_new (my_compare);
462 : :
463 [ + + ]: 63 : for (i = 0; chars[i]; i++)
464 : 62 : g_tree_insert (tree, &chars[i], &chars[i]);
465 : 1 : p = chars;
466 : 1 : g_tree_foreach (tree, check_order, &p);
467 : :
468 : 1 : g_tree_unref (tree);
469 : 1 : tree = g_tree_new (my_compare);
470 : :
471 [ + + ]: 63 : for (i = strlen (chars) - 1; i >= 0; i--)
472 : 62 : g_tree_insert (tree, &chars[i], &chars[i]);
473 : 1 : p = chars;
474 : 1 : g_tree_foreach (tree, check_order, &p);
475 : :
476 : 1 : g_tree_unref (tree);
477 : 1 : tree = g_tree_new (my_compare);
478 : :
479 : 1 : scrambled = g_strdup (chars);
480 : :
481 [ + + ]: 31 : for (i = 0; i < 30; i++)
482 : : {
483 : : gchar tmp;
484 : : gint a, b;
485 : :
486 : 30 : a = g_random_int_range (0, strlen (scrambled));
487 : 30 : b = g_random_int_range (0, strlen (scrambled));
488 : 30 : tmp = scrambled[a];
489 : 30 : scrambled[a] = scrambled[b];
490 : 30 : scrambled[b] = tmp;
491 : : }
492 : :
493 [ + + ]: 63 : for (i = 0; scrambled[i]; i++)
494 : 62 : g_tree_insert (tree, &scrambled[i], &scrambled[i]);
495 : 1 : p = chars;
496 : 1 : g_tree_foreach (tree, check_order, &p);
497 : :
498 : 1 : g_free (scrambled);
499 : 1 : g_tree_unref (tree);
500 : 1 : }
501 : :
502 : : static void
503 : 88 : binary_tree_bound (GTree *tree,
504 : : char c,
505 : : char expected,
506 : : int lower)
507 : : {
508 : : GTreeNode *node;
509 : :
510 [ + + ]: 88 : if (lower)
511 : 44 : node = g_tree_lower_bound (tree, &c);
512 : : else
513 : 44 : node = g_tree_upper_bound (tree, &c);
514 : :
515 [ - + ]: 88 : if (g_test_verbose ())
516 [ # # ]: 0 : g_test_message ("%c %s: ", c, lower ? "lower" : "upper");
517 : :
518 [ + + ]: 88 : if (!node)
519 : : {
520 [ + + ]: 37 : if (!g_tree_nnodes (tree))
521 : : {
522 [ - + ]: 22 : if (g_test_verbose ())
523 : 0 : g_test_message ("empty tree");
524 : : }
525 : : else
526 : : {
527 : 15 : GTreeNode *last = g_tree_node_last (tree);
528 : :
529 : 15 : g_assert_nonnull (last);
530 [ - + ]: 15 : if (g_test_verbose ())
531 : 0 : g_test_message ("past end last %c",
532 : 0 : *(char *) g_tree_node_key (last));
533 : : }
534 : 37 : g_assert_cmpint (expected, ==, '\x00');
535 : : }
536 : : else
537 : : {
538 : 51 : GTreeNode *begin = g_tree_node_first (tree);
539 : 51 : GTreeNode *last = g_tree_node_last (tree);
540 : 51 : GTreeNode *prev = g_tree_node_previous (node);
541 : 51 : GTreeNode *next = g_tree_node_next (node);
542 : :
543 : 51 : g_assert_cmpint (expected, !=, '\x00');
544 : 51 : g_assert_cmpint (expected, ==, *(char *) g_tree_node_key (node));
545 : :
546 [ - + ]: 51 : if (g_test_verbose ())
547 : 0 : g_test_message ("%c", *(char *) g_tree_node_key (node));
548 : :
549 [ + + ]: 51 : if (node != begin)
550 : : {
551 : 20 : g_assert_nonnull (prev);
552 [ - + ]: 20 : if (g_test_verbose ())
553 : 0 : g_test_message (" prev %c", *(char *) g_tree_node_key (prev));
554 : : }
555 : : else
556 : : {
557 : 31 : g_assert_null (prev);
558 [ - + ]: 31 : if (g_test_verbose ())
559 : 0 : g_test_message (" no prev, it's the first one");
560 : : }
561 : :
562 [ + + ]: 51 : if (node != last)
563 : : {
564 : 32 : g_assert_nonnull (next);
565 [ - + ]: 32 : if (g_test_verbose ())
566 : 0 : g_test_message (" next %c", *(char *) g_tree_node_key (next));
567 : : }
568 : : else
569 : : {
570 : 19 : g_assert_null (next);
571 [ - + ]: 19 : if (g_test_verbose ())
572 : 0 : g_test_message (" no next, it's the last one");
573 : : }
574 : : }
575 : :
576 [ - + ]: 88 : if (g_test_verbose ())
577 : 0 : g_test_message ("\n");
578 : 88 : }
579 : :
580 : : static void
581 : 44 : binary_tree_bounds (GTree *tree,
582 : : char c,
583 : : int mode)
584 : : {
585 : : char expectedl, expectedu;
586 [ + + + + ]: 44 : char first = mode == 0 ? '0' : mode == 1 ? 'A' : 'z';
587 : :
588 : 44 : g_assert_true (mode >= 0 && mode <= 3);
589 : :
590 [ + + ]: 44 : if (c < first)
591 : 22 : expectedl = first;
592 [ + + ]: 22 : else if (c > 'z')
593 : 8 : expectedl = '\x00';
594 : : else
595 : 14 : expectedl = c;
596 : :
597 [ + + ]: 44 : if (c < first)
598 : 22 : expectedu = first;
599 [ + + ]: 22 : else if (c >= 'z')
600 : 12 : expectedu = '\x00';
601 : : else
602 [ + + + + ]: 10 : expectedu = c == '9' ? 'A' : c == 'Z' ? 'a' : c + 1;
603 : :
604 [ + + ]: 44 : if (mode == 3)
605 : : {
606 : 11 : expectedl = '\x00';
607 : 11 : expectedu = '\x00';
608 : : }
609 : :
610 : 44 : binary_tree_bound (tree, c, expectedl, 1);
611 : 44 : binary_tree_bound (tree, c, expectedu, 0);
612 : 44 : }
613 : :
614 : : static void
615 : 4 : binary_tree_bounds_test (GTree *tree,
616 : : int mode)
617 : : {
618 : 4 : binary_tree_bounds (tree, 'a', mode);
619 : 4 : binary_tree_bounds (tree, 'A', mode);
620 : 4 : binary_tree_bounds (tree, 'z', mode);
621 : 4 : binary_tree_bounds (tree, 'Z', mode);
622 : 4 : binary_tree_bounds (tree, 'Y', mode);
623 : 4 : binary_tree_bounds (tree, '0', mode);
624 : 4 : binary_tree_bounds (tree, '9', mode);
625 : 4 : binary_tree_bounds (tree, '0' - 1, mode);
626 : 4 : binary_tree_bounds (tree, 'z' + 1, mode);
627 : 4 : binary_tree_bounds (tree, '0' - 2, mode);
628 : 4 : binary_tree_bounds (tree, 'z' + 2, mode);
629 : 4 : }
630 : :
631 : : static void
632 : 1 : test_tree_bounds (void)
633 : : {
634 : 1 : GQueue queue = G_QUEUE_INIT;
635 : : GTree *tree;
636 : : char chars[62];
637 : : guint i, j;
638 : :
639 : 1 : tree = g_tree_new (my_compare);
640 : :
641 : 1 : i = 0;
642 [ + + ]: 11 : for (j = 0; j < 10; j++, i++)
643 : : {
644 : 10 : chars[i] = '0' + j;
645 : 10 : g_queue_push_tail (&queue, &chars[i]);
646 : : }
647 : :
648 [ + + ]: 27 : for (j = 0; j < 26; j++, i++)
649 : : {
650 : 26 : chars[i] = 'A' + j;
651 : 26 : g_queue_push_tail (&queue, &chars[i]);
652 : : }
653 : :
654 [ + + ]: 27 : for (j = 0; j < 26; j++, i++)
655 : : {
656 : 26 : chars[i] = 'a' + j;
657 : 26 : g_queue_push_tail (&queue, &chars[i]);
658 : : }
659 : :
660 [ - + ]: 1 : if (g_test_verbose ())
661 : 0 : g_test_message ("tree insert: ");
662 : :
663 [ + + ]: 64 : while (!g_queue_is_empty (&queue))
664 : : {
665 : 62 : gint32 which = g_random_int_range (0, g_queue_get_length (&queue));
666 : 62 : gpointer elem = g_queue_pop_nth (&queue, which);
667 : : GTreeNode *node;
668 : :
669 [ - + ]: 62 : if (g_test_verbose ())
670 : 0 : g_test_message ("%c ", *(char *) elem);
671 : :
672 : 62 : node = g_tree_insert_node (tree, elem, elem);
673 : 62 : g_assert_nonnull (node);
674 : 62 : g_assert_true (g_tree_node_key (node) == elem);
675 : 62 : g_assert_true (g_tree_node_value (node) == elem);
676 : : }
677 : :
678 [ - + ]: 1 : if (g_test_verbose ())
679 : 0 : g_test_message ("\n");
680 : :
681 : 1 : g_assert_cmpint (g_tree_nnodes (tree), ==, 10 + 26 + 26);
682 : 1 : g_assert_cmpint (g_tree_height (tree), >=, 6);
683 : 1 : g_assert_cmpint (g_tree_height (tree), <=, 8);
684 : :
685 [ - + ]: 1 : if (g_test_verbose ())
686 : : {
687 : 0 : g_test_message ("tree: ");
688 : 0 : g_tree_foreach (tree, my_traverse, NULL);
689 : 0 : g_test_message ("\n");
690 : : }
691 : :
692 : 1 : binary_tree_bounds_test (tree, 0);
693 : :
694 [ + + ]: 11 : for (i = 0; i < 10; i++)
695 : 10 : g_tree_remove (tree, &chars[i]);
696 : :
697 : 1 : g_assert_cmpint (g_tree_nnodes (tree), ==, 26 + 26);
698 : 1 : g_assert_cmpint (g_tree_height (tree), >=, 6);
699 : 1 : g_assert_cmpint (g_tree_height (tree), <=, 8);
700 : :
701 [ - + ]: 1 : if (g_test_verbose ())
702 : : {
703 : 0 : g_test_message ("tree: ");
704 : 0 : g_tree_foreach (tree, my_traverse, NULL);
705 : 0 : g_test_message ("\n");
706 : : }
707 : :
708 : 1 : binary_tree_bounds_test (tree, 1);
709 : :
710 [ + + ]: 52 : for (i = 10; i < 10 + 26 + 26 - 1; i++)
711 : 51 : g_tree_remove (tree, &chars[i]);
712 : :
713 [ - + ]: 1 : if (g_test_verbose ())
714 : : {
715 : 0 : g_test_message ("tree: ");
716 : 0 : g_tree_foreach (tree, my_traverse, NULL);
717 : 0 : g_test_message ("\n");
718 : : }
719 : :
720 : 1 : binary_tree_bounds_test (tree, 2);
721 : :
722 : 1 : g_tree_remove (tree, &chars[10 + 26 + 26 - 1]);
723 : :
724 [ - + ]: 1 : if (g_test_verbose ())
725 : 0 : g_test_message ("empty tree\n");
726 : :
727 : 1 : binary_tree_bounds_test (tree, 3);
728 : :
729 : 1 : g_tree_unref (tree);
730 : 1 : }
731 : :
732 : : int
733 : 1 : main (int argc, char *argv[])
734 : : {
735 : 1 : g_test_init (&argc, &argv, NULL);
736 : :
737 : 1 : g_test_add_func ("/tree/search", test_tree_search);
738 : 1 : g_test_add_func ("/tree/remove", test_tree_remove);
739 : 1 : g_test_add_func ("/tree/destroy", test_tree_destroy);
740 : 1 : g_test_add_func ("/tree/traverse", test_tree_traverse);
741 : 1 : g_test_add_func ("/tree/insert", test_tree_insert);
742 : 1 : g_test_add_func ("/tree/bounds", test_tree_bounds);
743 : 1 : g_test_add_func ("/tree/remove-all", test_tree_remove_all);
744 : :
745 : 1 : return g_test_run ();
746 : : }
|