Update.
[glibc.git] / misc / tst-tsearch.c
blob06f743bc053af8337a55103d90d926fbffee910e
1 /* Test program for tsearch et al.
2 Copyright (C) 1997, 2000 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 Library General Public License as
7 published by the Free Software Foundation; either version 2 of the
8 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 Library General Public License for more details.
15 You should have received a copy of the GNU Library General Public
16 License along with the GNU C Library; see the file COPYING.LIB. If not,
17 write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA. */
20 #ifndef _GNU_SOURCE
21 # define _GNU_SOURCE 1
22 #endif
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <search.h>
29 #define SEED 0
30 #define BALANCED 1
31 #define PASSES 100
33 #if BALANCED
34 #include <math.h>
35 #define SIZE 1000
36 #else
37 #define SIZE 100
38 #endif
40 enum order
42 ascending,
43 descending,
44 randomorder
47 enum action
49 build,
50 build_and_del,
51 delete,
52 find
55 /* Set to 1 if a test is flunked. */
56 static int error = 0;
58 /* The keys we add to the tree. */
59 static int x[SIZE];
61 /* Pointers into the key array, possibly permutated, to define an order
62 for insertion/removal. */
63 static int y[SIZE];
65 /* Flags set for each element visited during a tree walk. */
66 static int z[SIZE];
68 /* Depths for all the elements, to check that the depth is constant for
69 all three visits. */
70 static int depths[SIZE];
72 /* Maximum depth during a tree walk. */
73 static int max_depth;
75 /* Compare two keys. */
76 static int
77 cmp_fn (const void *a, const void *b)
79 return *(const int *) a - *(const int *) b;
82 /* Permute an array of integers. */
83 static void
84 memfry (int *string)
86 int i;
88 for (i = 0; i < SIZE; ++i)
90 int32_t j;
91 int c;
93 j = random () % SIZE;
95 c = string[i];
96 string[i] = string[j];
97 string[j] = c;
101 static void
102 walk_action (const void *nodep, const VISIT which, const int depth)
104 int key = **(int **) nodep;
106 if (depth > max_depth)
107 max_depth = depth;
108 if (which == leaf || which == preorder)
110 ++z[key];
111 depths[key] = depth;
113 else
115 if (depths[key] != depth)
117 fputs ("Depth for one element is not constant during tree walk.\n",
118 stdout);
123 static void
124 walk_tree (void *root, int expected_count)
126 int i;
128 memset (z, 0, sizeof z);
129 max_depth = 0;
131 twalk (root, walk_action);
132 for (i = 0; i < expected_count; ++i)
133 if (z[i] != 1)
135 fputs ("Node was not visited.\n", stdout);
136 error = 1;
139 #if BALANCED
140 if (max_depth > log (expected_count) * 2 + 2)
141 #else
142 if (max_depth > expected_count)
143 #endif
145 fputs ("Depth too large during tree walk.\n", stdout);
146 error = 1;
150 /* Perform an operation on a tree. */
151 static void
152 mangle_tree (enum order how, enum action what, void **root, int lag)
154 int i;
156 if (how == randomorder)
158 for (i = 0; i < SIZE; ++i)
159 y[i] = i;
160 memfry (y);
163 for (i = 0; i < SIZE + lag; ++i)
165 void *elem;
166 int j, k;
168 switch (how)
170 case randomorder:
171 if (i >= lag)
172 k = y[i - lag];
173 else
174 k = y[SIZE - i - 1 + lag];
175 j = y[i];
176 break;
178 case ascending:
179 k = i - lag;
180 j = i;
181 break;
183 case descending:
184 k = SIZE - i - 1 + lag;
185 j = SIZE - i - 1;
186 break;
188 default:
189 /* This never should happen, but gcc isn't smart enough to
190 recognize it. */
191 abort ();
194 switch (what)
196 case build_and_del:
197 case build:
198 if (i < SIZE)
200 if (tfind (x + j, (void *const *) root, cmp_fn) != NULL)
202 fputs ("Found element which is not in tree yet.\n", stdout);
203 error = 1;
205 elem = tsearch (x + j, root, cmp_fn);
206 if (elem == 0
207 || tfind (x + j, (void *const *) root, cmp_fn) == NULL)
209 fputs ("Couldn't find element after it was added.\n",
210 stdout);
211 error = 1;
215 if (what == build || i < lag)
216 break;
218 j = k;
219 /* fall through */
221 case delete:
222 elem = tfind (x + j, (void *const *) root, cmp_fn);
223 if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
225 fputs ("Error deleting element.\n", stdout);
226 error = 1;
228 break;
230 case find:
231 if (tfind (x + j, (void *const *) root, cmp_fn) == NULL)
233 fputs ("Couldn't find element after it was added.\n", stdout);
234 error = 1;
236 break;
244 main (int argc, char **argv)
246 int total_error = 0;
247 static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
248 void *root = NULL;
249 int i, j;
251 initstate (SEED, state, 8);
253 for (i = 0; i < SIZE; ++i)
254 x[i] = i;
256 /* Do this loop several times to get different permutations for the
257 random case. */
258 fputs ("Series I\n", stdout);
259 for (i = 0; i < PASSES; ++i)
261 fprintf (stdout, "Pass %d... ", i + 1);
262 fflush (stdout);
263 error = 0;
265 mangle_tree (ascending, build, &root, 0);
266 mangle_tree (ascending, find, &root, 0);
267 mangle_tree (descending, find, &root, 0);
268 mangle_tree (randomorder, find, &root, 0);
269 walk_tree (root, SIZE);
270 mangle_tree (ascending, delete, &root, 0);
272 mangle_tree (ascending, build, &root, 0);
273 walk_tree (root, SIZE);
274 mangle_tree (descending, delete, &root, 0);
276 mangle_tree (ascending, build, &root, 0);
277 walk_tree (root, SIZE);
278 mangle_tree (randomorder, delete, &root, 0);
280 mangle_tree (descending, build, &root, 0);
281 mangle_tree (ascending, find, &root, 0);
282 mangle_tree (descending, find, &root, 0);
283 mangle_tree (randomorder, find, &root, 0);
284 walk_tree (root, SIZE);
285 mangle_tree (descending, delete, &root, 0);
287 mangle_tree (descending, build, &root, 0);
288 walk_tree (root, SIZE);
289 mangle_tree (descending, delete, &root, 0);
291 mangle_tree (descending, build, &root, 0);
292 walk_tree (root, SIZE);
293 mangle_tree (randomorder, delete, &root, 0);
295 mangle_tree (randomorder, build, &root, 0);
296 mangle_tree (ascending, find, &root, 0);
297 mangle_tree (descending, find, &root, 0);
298 mangle_tree (randomorder, find, &root, 0);
299 walk_tree (root, SIZE);
300 mangle_tree (randomorder, delete, &root, 0);
302 for (j = 1; j < SIZE; j *= 2)
304 mangle_tree (randomorder, build_and_del, &root, j);
307 fputs (error ? " failed!\n" : " ok.\n", stdout);
308 total_error |= error;
311 fputs ("Series II\n", stdout);
312 for (i = 1; i < SIZE; i *= 2)
314 fprintf (stdout, "For size %d... ", i);
315 fflush (stdout);
316 error = 0;
318 mangle_tree (ascending, build_and_del, &root, i);
319 mangle_tree (descending, build_and_del, &root, i);
320 mangle_tree (ascending, build_and_del, &root, i);
321 mangle_tree (descending, build_and_del, &root, i);
322 mangle_tree (ascending, build_and_del, &root, i);
323 mangle_tree (descending, build_and_del, &root, i);
324 mangle_tree (ascending, build_and_del, &root, i);
325 mangle_tree (descending, build_and_del, &root, i);
327 fputs (error ? " failed!\n" : " ok.\n", stdout);
328 total_error |= error;
331 return total_error;