]>
sourceware.org Git - glibc.git/blob - misc/tst-tsearch.c
1 /* Test program for tsearch et al.
2 Copyright (C) 1997, 2000, 2001 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, write to the Free
17 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21 # define _GNU_SOURCE 1
55 /* Set to 1 if a test is flunked. */
58 /* The keys we add to the tree. */
61 /* Pointers into the key array, possibly permutated, to define an order
62 for insertion/removal. */
65 /* Flags set for each element visited during a tree walk. */
68 /* Depths for all the elements, to check that the depth is constant for
70 static int depths
[SIZE
];
72 /* Maximum depth during a tree walk. */
75 /* Compare two keys. */
77 cmp_fn (const void *a
, const void *b
)
79 return *(const int *) a
- *(const int *) b
;
82 /* Permute an array of integers. */
88 for (i
= 0; i
< SIZE
; ++i
)
96 string
[i
] = string
[j
];
102 walk_action (const void *nodep
, const VISIT which
, const int depth
)
104 int key
= **(int **) nodep
;
106 if (depth
> max_depth
)
108 if (which
== leaf
|| which
== preorder
)
115 if (depths
[key
] != depth
)
117 fputs ("Depth for one element is not constant during tree walk.\n",
124 walk_tree (void *root
, int expected_count
)
128 memset (z
, 0, sizeof z
);
131 twalk (root
, walk_action
);
132 for (i
= 0; i
< expected_count
; ++i
)
135 fputs ("Node was not visited.\n", stdout
);
140 if (max_depth
> log (expected_count
) * 2 + 2)
142 if (max_depth
> expected_count
)
145 fputs ("Depth too large during tree walk.\n", stdout
);
150 /* Perform an operation on a tree. */
152 mangle_tree (enum order how
, enum action what
, void **root
, int lag
)
156 if (how
== randomorder
)
158 for (i
= 0; i
< SIZE
; ++i
)
163 for (i
= 0; i
< SIZE
+ lag
; ++i
)
174 /* Ensure that the array index is within bounds. */
175 k
= y
[(SIZE
- i
- 1 + lag
) % SIZE
];
185 k
= SIZE
- i
- 1 + lag
;
190 /* This never should happen, but gcc isn't smart enough to
201 if (tfind (x
+ j
, (void *const *) root
, cmp_fn
) != NULL
)
203 fputs ("Found element which is not in tree yet.\n", stdout
);
206 elem
= tsearch (x
+ j
, root
, cmp_fn
);
208 || tfind (x
+ j
, (void *const *) root
, cmp_fn
) == NULL
)
210 fputs ("Couldn't find element after it was added.\n",
216 if (what
== build
|| i
< lag
)
223 elem
= tfind (x
+ j
, (void *const *) root
, cmp_fn
);
224 if (elem
== NULL
|| tdelete (x
+ j
, root
, cmp_fn
) == NULL
)
226 fputs ("Error deleting element.\n", stdout
);
232 if (tfind (x
+ j
, (void *const *) root
, cmp_fn
) == NULL
)
234 fputs ("Couldn't find element after it was added.\n", stdout
);
245 main (int argc
, char **argv
)
248 static char state
[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
252 initstate (SEED
, state
, 8);
254 for (i
= 0; i
< SIZE
; ++i
)
257 /* Do this loop several times to get different permutations for the
259 fputs ("Series I\n", stdout
);
260 for (i
= 0; i
< PASSES
; ++i
)
262 fprintf (stdout
, "Pass %d... ", i
+ 1);
266 mangle_tree (ascending
, build
, &root
, 0);
267 mangle_tree (ascending
, find
, &root
, 0);
268 mangle_tree (descending
, find
, &root
, 0);
269 mangle_tree (randomorder
, find
, &root
, 0);
270 walk_tree (root
, SIZE
);
271 mangle_tree (ascending
, delete, &root
, 0);
273 mangle_tree (ascending
, build
, &root
, 0);
274 walk_tree (root
, SIZE
);
275 mangle_tree (descending
, delete, &root
, 0);
277 mangle_tree (ascending
, build
, &root
, 0);
278 walk_tree (root
, SIZE
);
279 mangle_tree (randomorder
, delete, &root
, 0);
281 mangle_tree (descending
, build
, &root
, 0);
282 mangle_tree (ascending
, find
, &root
, 0);
283 mangle_tree (descending
, find
, &root
, 0);
284 mangle_tree (randomorder
, find
, &root
, 0);
285 walk_tree (root
, SIZE
);
286 mangle_tree (descending
, delete, &root
, 0);
288 mangle_tree (descending
, build
, &root
, 0);
289 walk_tree (root
, SIZE
);
290 mangle_tree (descending
, delete, &root
, 0);
292 mangle_tree (descending
, build
, &root
, 0);
293 walk_tree (root
, SIZE
);
294 mangle_tree (randomorder
, delete, &root
, 0);
296 mangle_tree (randomorder
, build
, &root
, 0);
297 mangle_tree (ascending
, find
, &root
, 0);
298 mangle_tree (descending
, find
, &root
, 0);
299 mangle_tree (randomorder
, find
, &root
, 0);
300 walk_tree (root
, SIZE
);
301 mangle_tree (randomorder
, delete, &root
, 0);
303 for (j
= 1; j
< SIZE
; j
*= 2)
305 mangle_tree (randomorder
, build_and_del
, &root
, j
);
308 fputs (error
? " failed!\n" : " ok.\n", stdout
);
309 total_error
|= error
;
312 fputs ("Series II\n", stdout
);
313 for (i
= 1; i
< SIZE
; i
*= 2)
315 fprintf (stdout
, "For size %d... ", i
);
319 mangle_tree (ascending
, build_and_del
, &root
, i
);
320 mangle_tree (descending
, build_and_del
, &root
, i
);
321 mangle_tree (ascending
, build_and_del
, &root
, i
);
322 mangle_tree (descending
, build_and_del
, &root
, i
);
323 mangle_tree (ascending
, build_and_del
, &root
, i
);
324 mangle_tree (descending
, build_and_del
, &root
, i
);
325 mangle_tree (ascending
, build_and_del
, &root
, i
);
326 mangle_tree (descending
, build_and_del
, &root
, i
);
328 fputs (error
? " failed!\n" : " ok.\n", stdout
);
329 total_error
|= error
;
This page took 0.045539 seconds and 5 git commands to generate.