1 | /* GLIB - Library of useful routines for C programming |
2 | * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald |
3 | * |
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.1 of the License, or (at your option) any later version. |
8 | * |
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. |
13 | * |
14 | * You should have received a copy of the GNU Lesser General Public |
15 | * License along with this library; if not, see <http://www.gnu.org/licenses/>. |
16 | */ |
17 | |
18 | /* |
19 | * Modified by the GLib Team and others 1997-2000. See the AUTHORS |
20 | * file for a list of people on the GLib Team. See the ChangeLog |
21 | * files for a list of changes. These files are distributed with |
22 | * GLib at ftp://ftp.gtk.org/pub/gtk/. |
23 | */ |
24 | |
25 | #undef G_DISABLE_ASSERT |
26 | #undef G_LOG_DOMAIN |
27 | |
28 | /* We are testing some deprecated APIs here */ |
29 | #ifndef GLIB_DISABLE_DEPRECATION_WARNINGS |
30 | #define GLIB_DISABLE_DEPRECATION_WARNINGS |
31 | #endif |
32 | |
33 | #include <stdio.h> |
34 | #include <string.h> |
35 | #include "glib.h" |
36 | |
37 | |
38 | static gint |
39 | my_compare (gconstpointer a, |
40 | gconstpointer b) |
41 | { |
42 | const char *cha = a; |
43 | const char *chb = b; |
44 | |
45 | return *cha - *chb; |
46 | } |
47 | |
48 | static gint |
49 | my_compare_with_data (gconstpointer a, |
50 | gconstpointer b, |
51 | gpointer user_data) |
52 | { |
53 | const char *cha = a; |
54 | const char *chb = b; |
55 | |
56 | /* just check that we got the right data */ |
57 | g_assert (GPOINTER_TO_INT(user_data) == 123); |
58 | |
59 | return *cha - *chb; |
60 | } |
61 | |
62 | static gint |
63 | my_search (gconstpointer a, |
64 | gconstpointer b) |
65 | { |
66 | return my_compare (a: b, b: a); |
67 | } |
68 | |
69 | static gpointer destroyed_key = NULL; |
70 | static gpointer destroyed_value = NULL; |
71 | |
72 | static void |
73 | my_key_destroy (gpointer key) |
74 | { |
75 | destroyed_key = key; |
76 | } |
77 | |
78 | static void |
79 | my_value_destroy (gpointer value) |
80 | { |
81 | destroyed_value = value; |
82 | } |
83 | |
84 | static gint |
85 | my_traverse (gpointer key, |
86 | gpointer value, |
87 | gpointer data) |
88 | { |
89 | char *ch = key; |
90 | |
91 | g_assert ((*ch) > 0); |
92 | |
93 | if (*ch == 'd') |
94 | return TRUE; |
95 | |
96 | return FALSE; |
97 | } |
98 | |
99 | char chars[] = |
100 | "0123456789" |
101 | "ABCDEFGHIJKLMNOPQRSTUVWXYZ" |
102 | "abcdefghijklmnopqrstuvwxyz" ; |
103 | |
104 | char chars2[] = |
105 | "0123456789" |
106 | "abcdefghijklmnopqrstuvwxyz" ; |
107 | |
108 | static gint |
109 | check_order (gpointer key, |
110 | gpointer value, |
111 | gpointer data) |
112 | { |
113 | char **p = data; |
114 | char *ch = key; |
115 | |
116 | g_assert (**p == *ch); |
117 | |
118 | (*p)++; |
119 | |
120 | return FALSE; |
121 | } |
122 | |
123 | static void |
124 | test_tree_search (void) |
125 | { |
126 | gint i; |
127 | GTree *tree; |
128 | gboolean removed; |
129 | gchar c; |
130 | gchar *p, *d; |
131 | |
132 | tree = g_tree_new_with_data (key_compare_func: my_compare_with_data, GINT_TO_POINTER(123)); |
133 | |
134 | for (i = 0; chars[i]; i++) |
135 | g_tree_insert (tree, key: &chars[i], value: &chars[i]); |
136 | |
137 | g_tree_foreach (tree, func: my_traverse, NULL); |
138 | |
139 | g_assert_cmpint (g_tree_nnodes (tree), ==, strlen (chars)); |
140 | g_assert_cmpint (g_tree_height (tree), ==, 6); |
141 | |
142 | p = chars; |
143 | g_tree_foreach (tree, func: check_order, user_data: &p); |
144 | |
145 | for (i = 0; i < 26; i++) |
146 | { |
147 | removed = g_tree_remove (tree, key: &chars[i + 10]); |
148 | g_assert (removed); |
149 | } |
150 | |
151 | c = '\0'; |
152 | removed = g_tree_remove (tree, key: &c); |
153 | g_assert (!removed); |
154 | |
155 | g_tree_foreach (tree, func: my_traverse, NULL); |
156 | |
157 | g_assert_cmpint (g_tree_nnodes (tree), ==, strlen (chars2)); |
158 | g_assert_cmpint (g_tree_height (tree), ==, 6); |
159 | |
160 | p = chars2; |
161 | g_tree_foreach (tree, func: check_order, user_data: &p); |
162 | |
163 | for (i = 25; i >= 0; i--) |
164 | g_tree_insert (tree, key: &chars[i + 10], value: &chars[i + 10]); |
165 | |
166 | p = chars; |
167 | g_tree_foreach (tree, func: check_order, user_data: &p); |
168 | |
169 | c = '0'; |
170 | p = g_tree_lookup (tree, key: &c); |
171 | g_assert (p && *p == c); |
172 | g_assert (g_tree_lookup_extended (tree, &c, (gpointer *)&d, (gpointer *)&p)); |
173 | g_assert (c == *d && c == *p); |
174 | |
175 | c = 'A'; |
176 | p = g_tree_lookup (tree, key: &c); |
177 | g_assert (p && *p == c); |
178 | |
179 | c = 'a'; |
180 | p = g_tree_lookup (tree, key: &c); |
181 | g_assert (p && *p == c); |
182 | |
183 | c = 'z'; |
184 | p = g_tree_lookup (tree, key: &c); |
185 | g_assert (p && *p == c); |
186 | |
187 | c = '!'; |
188 | p = g_tree_lookup (tree, key: &c); |
189 | g_assert (p == NULL); |
190 | |
191 | c = '='; |
192 | p = g_tree_lookup (tree, key: &c); |
193 | g_assert (p == NULL); |
194 | |
195 | c = '|'; |
196 | p = g_tree_lookup (tree, key: &c); |
197 | g_assert (p == NULL); |
198 | |
199 | c = '0'; |
200 | p = g_tree_search (tree, search_func: my_search, user_data: &c); |
201 | g_assert (p && *p == c); |
202 | |
203 | c = 'A'; |
204 | p = g_tree_search (tree, search_func: my_search, user_data: &c); |
205 | g_assert (p && *p == c); |
206 | |
207 | c = 'a'; |
208 | p = g_tree_search (tree, search_func: my_search, user_data: &c); |
209 | g_assert (p &&*p == c); |
210 | |
211 | c = 'z'; |
212 | p = g_tree_search (tree, search_func: my_search, user_data: &c); |
213 | g_assert (p && *p == c); |
214 | |
215 | c = '!'; |
216 | p = g_tree_search (tree, search_func: my_search, user_data: &c); |
217 | g_assert (p == NULL); |
218 | |
219 | c = '='; |
220 | p = g_tree_search (tree, search_func: my_search, user_data: &c); |
221 | g_assert (p == NULL); |
222 | |
223 | c = '|'; |
224 | p = g_tree_search (tree, search_func: my_search, user_data: &c); |
225 | g_assert (p == NULL); |
226 | |
227 | g_tree_destroy (tree); |
228 | } |
229 | |
230 | static void |
231 | test_tree_remove (void) |
232 | { |
233 | GTree *tree; |
234 | char c, d; |
235 | gint i; |
236 | gboolean removed; |
237 | gchar *remove; |
238 | |
239 | tree = g_tree_new_full (key_compare_func: (GCompareDataFunc)my_compare, NULL, |
240 | key_destroy_func: my_key_destroy, |
241 | value_destroy_func: my_value_destroy); |
242 | |
243 | for (i = 0; chars[i]; i++) |
244 | g_tree_insert (tree, key: &chars[i], value: &chars[i]); |
245 | |
246 | c = '0'; |
247 | g_tree_insert (tree, key: &c, value: &c); |
248 | g_assert (destroyed_key == &c); |
249 | g_assert (destroyed_value == &chars[0]); |
250 | destroyed_key = NULL; |
251 | destroyed_value = NULL; |
252 | |
253 | d = '1'; |
254 | g_tree_replace (tree, key: &d, value: &d); |
255 | g_assert (destroyed_key == &chars[1]); |
256 | g_assert (destroyed_value == &chars[1]); |
257 | destroyed_key = NULL; |
258 | destroyed_value = NULL; |
259 | |
260 | c = '2'; |
261 | removed = g_tree_remove (tree, key: &c); |
262 | g_assert (removed); |
263 | g_assert (destroyed_key == &chars[2]); |
264 | g_assert (destroyed_value == &chars[2]); |
265 | destroyed_key = NULL; |
266 | destroyed_value = NULL; |
267 | |
268 | c = '3'; |
269 | removed = g_tree_steal (tree, key: &c); |
270 | g_assert (removed); |
271 | g_assert (destroyed_key == NULL); |
272 | g_assert (destroyed_value == NULL); |
273 | |
274 | remove = "omkjigfedba" ; |
275 | for (i = 0; remove[i]; i++) |
276 | { |
277 | removed = g_tree_remove (tree, key: &remove[i]); |
278 | g_assert (removed); |
279 | } |
280 | |
281 | g_tree_destroy (tree); |
282 | } |
283 | |
284 | static void |
285 | test_tree_destroy (void) |
286 | { |
287 | GTree *tree; |
288 | gint i; |
289 | |
290 | tree = g_tree_new (key_compare_func: my_compare); |
291 | |
292 | for (i = 0; chars[i]; i++) |
293 | g_tree_insert (tree, key: &chars[i], value: &chars[i]); |
294 | |
295 | g_assert_cmpint (g_tree_nnodes (tree), ==, strlen (chars)); |
296 | |
297 | g_tree_ref (tree); |
298 | g_tree_destroy (tree); |
299 | |
300 | g_assert_cmpint (g_tree_nnodes (tree), ==, 0); |
301 | |
302 | g_tree_unref (tree); |
303 | } |
304 | |
305 | typedef struct { |
306 | GString *s; |
307 | gint count; |
308 | } CallbackData; |
309 | |
310 | static gboolean |
311 | traverse_func (gpointer key, gpointer value, gpointer data) |
312 | { |
313 | CallbackData *d = data; |
314 | |
315 | gchar *c = value; |
316 | g_string_append_c (d->s, *c); |
317 | |
318 | d->count--; |
319 | |
320 | if (d->count == 0) |
321 | return TRUE; |
322 | |
323 | return FALSE; |
324 | } |
325 | |
326 | typedef struct { |
327 | GTraverseType traverse; |
328 | gint limit; |
329 | const gchar *expected; |
330 | } TraverseData; |
331 | |
332 | static void |
333 | test_tree_traverse (void) |
334 | { |
335 | GTree *tree; |
336 | gsize i; |
337 | TraverseData orders[] = { |
338 | { G_IN_ORDER, -1, "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" }, |
339 | { G_IN_ORDER, 1, "0" }, |
340 | { G_IN_ORDER, 2, "01" }, |
341 | { G_IN_ORDER, 3, "012" }, |
342 | { G_IN_ORDER, 4, "0123" }, |
343 | { G_IN_ORDER, 5, "01234" }, |
344 | { G_IN_ORDER, 6, "012345" }, |
345 | { G_IN_ORDER, 7, "0123456" }, |
346 | { G_IN_ORDER, 8, "01234567" }, |
347 | { G_IN_ORDER, 9, "012345678" }, |
348 | { G_IN_ORDER, 10, "0123456789" }, |
349 | { G_IN_ORDER, 11, "0123456789A" }, |
350 | { G_IN_ORDER, 12, "0123456789AB" }, |
351 | { G_IN_ORDER, 13, "0123456789ABC" }, |
352 | { G_IN_ORDER, 14, "0123456789ABCD" }, |
353 | |
354 | { G_PRE_ORDER, -1, "VF73102546B98ADCENJHGILKMRPOQTSUldZXWYbachfegjiktpnmorqsxvuwyz" }, |
355 | { G_PRE_ORDER, 1, "V" }, |
356 | { G_PRE_ORDER, 2, "VF" }, |
357 | { G_PRE_ORDER, 3, "VF7" }, |
358 | { G_PRE_ORDER, 4, "VF73" }, |
359 | { G_PRE_ORDER, 5, "VF731" }, |
360 | { G_PRE_ORDER, 6, "VF7310" }, |
361 | { G_PRE_ORDER, 7, "VF73102" }, |
362 | { G_PRE_ORDER, 8, "VF731025" }, |
363 | { G_PRE_ORDER, 9, "VF7310254" }, |
364 | { G_PRE_ORDER, 10, "VF73102546" }, |
365 | { G_PRE_ORDER, 11, "VF73102546B" }, |
366 | { G_PRE_ORDER, 12, "VF73102546B9" }, |
367 | { G_PRE_ORDER, 13, "VF73102546B98" }, |
368 | { G_PRE_ORDER, 14, "VF73102546B98A" }, |
369 | |
370 | { G_POST_ORDER, -1, "02146538A9CEDB7GIHKMLJOQPSUTRNFWYXacbZegfikjhdmonqsrpuwvzyxtlV" }, |
371 | { G_POST_ORDER, 1, "0" }, |
372 | { G_POST_ORDER, 2, "02" }, |
373 | { G_POST_ORDER, 3, "021" }, |
374 | { G_POST_ORDER, 4, "0214" }, |
375 | { G_POST_ORDER, 5, "02146" }, |
376 | { G_POST_ORDER, 6, "021465" }, |
377 | { G_POST_ORDER, 7, "0214653" }, |
378 | { G_POST_ORDER, 8, "02146538" }, |
379 | { G_POST_ORDER, 9, "02146538A" }, |
380 | { G_POST_ORDER, 10, "02146538A9" }, |
381 | { G_POST_ORDER, 11, "02146538A9C" }, |
382 | { G_POST_ORDER, 12, "02146538A9CE" }, |
383 | { G_POST_ORDER, 13, "02146538A9CED" }, |
384 | { G_POST_ORDER, 14, "02146538A9CEDB" } |
385 | }; |
386 | CallbackData data; |
387 | |
388 | tree = g_tree_new (key_compare_func: my_compare); |
389 | |
390 | for (i = 0; chars[i]; i++) |
391 | g_tree_insert (tree, key: &chars[i], value: &chars[i]); |
392 | |
393 | data.s = g_string_new (init: "" ); |
394 | for (i = 0; i < G_N_ELEMENTS (orders); i++) |
395 | { |
396 | g_string_set_size (string: data.s, len: 0); |
397 | data.count = orders[i].limit; |
398 | g_tree_traverse (tree, traverse_func, traverse_type: orders[i].traverse, user_data: &data); |
399 | g_assert_cmpstr (data.s->str, ==, orders[i].expected); |
400 | } |
401 | |
402 | g_tree_unref (tree); |
403 | g_string_free (string: data.s, TRUE); |
404 | } |
405 | |
406 | static void |
407 | test_tree_insert (void) |
408 | { |
409 | GTree *tree; |
410 | gchar *p; |
411 | gint i; |
412 | gchar *scrambled; |
413 | |
414 | tree = g_tree_new (key_compare_func: my_compare); |
415 | |
416 | for (i = 0; chars[i]; i++) |
417 | g_tree_insert (tree, key: &chars[i], value: &chars[i]); |
418 | p = chars; |
419 | g_tree_foreach (tree, func: check_order, user_data: &p); |
420 | |
421 | g_tree_unref (tree); |
422 | tree = g_tree_new (key_compare_func: my_compare); |
423 | |
424 | for (i = strlen (s: chars) - 1; i >= 0; i--) |
425 | g_tree_insert (tree, key: &chars[i], value: &chars[i]); |
426 | p = chars; |
427 | g_tree_foreach (tree, func: check_order, user_data: &p); |
428 | |
429 | g_tree_unref (tree); |
430 | tree = g_tree_new (key_compare_func: my_compare); |
431 | |
432 | scrambled = g_strdup (str: chars); |
433 | |
434 | for (i = 0; i < 30; i++) |
435 | { |
436 | gchar tmp; |
437 | gint a, b; |
438 | |
439 | a = g_random_int_range (begin: 0, end: strlen (s: scrambled)); |
440 | b = g_random_int_range (begin: 0, end: strlen (s: scrambled)); |
441 | tmp = scrambled[a]; |
442 | scrambled[a] = scrambled[b]; |
443 | scrambled[b] = tmp; |
444 | } |
445 | |
446 | for (i = 0; scrambled[i]; i++) |
447 | g_tree_insert (tree, key: &scrambled[i], value: &scrambled[i]); |
448 | p = chars; |
449 | g_tree_foreach (tree, func: check_order, user_data: &p); |
450 | |
451 | g_free (mem: scrambled); |
452 | g_tree_unref (tree); |
453 | } |
454 | |
455 | int |
456 | main (int argc, char *argv[]) |
457 | { |
458 | g_test_init (argc: &argc, argv: &argv, NULL); |
459 | |
460 | g_test_add_func (testpath: "/tree/search" , test_func: test_tree_search); |
461 | g_test_add_func (testpath: "/tree/remove" , test_func: test_tree_remove); |
462 | g_test_add_func (testpath: "/tree/destroy" , test_func: test_tree_destroy); |
463 | g_test_add_func (testpath: "/tree/traverse" , test_func: test_tree_traverse); |
464 | g_test_add_func (testpath: "/tree/insert" , test_func: test_tree_insert); |
465 | |
466 | return g_test_run (); |
467 | } |
468 | |