source: branches/libc-0.6/src/libctests/glibc/misc/tst-tsearch.c

Last change on this file was 2137, checked in by bird, 20 years ago

More libc.
  • Property cvs2svn:cvs-rev set to 1.2
  • Property svn:eol-style set to native
  • Property svn:executable set to *
  • Property svn:keywords set to Author Date Id Revision
File size: 8.0 KB
Line 
1/* Test program for tsearch et al.
2 Copyright (C) 1997, 2000, 2001, 2003 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4
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.
9
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.
14
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
18 02111-1307 USA. */
19
20#ifndef _GNU_SOURCE
21# define _GNU_SOURCE 1
22#endif
23
24#include <stdio.h>
25#include <stdlib.h>
26#include <string.h>
27#include <search.h>
28#include <tst-stack-align.h>
29
30#define SEED 0
31#define BALANCED 1
32#define PASSES 100
33
34#if BALANCED
35#include <math.h>
36#define SIZE 1000
37#else
38#define SIZE 100
39#endif
40
41enum order
42{
43 ascending,
44 descending,
45 randomorder
46};
47
48enum action
49{
50 build,
51 build_and_del,
52 delete,
53 find
54};
55
56/* Set to 1 if a test is flunked. */
57static int error = 0;
58
59/* The keys we add to the tree. */
60static int x[SIZE];
61
62/* Pointers into the key array, possibly permutated, to define an order
63 for insertion/removal. */
64static int y[SIZE];
65
66/* Flags set for each element visited during a tree walk. */
67static int z[SIZE];
68
69/* Depths for all the elements, to check that the depth is constant for
70 all three visits. */
71static int depths[SIZE];
72
73/* Maximum depth during a tree walk. */
74static int max_depth;
75
76static int stack_align_check[2];
77
78/* Compare two keys. */
79static int
80cmp_fn (const void *a, const void *b)
81{
82 if (!stack_align_check[0])
83 stack_align_check[0] = TEST_STACK_ALIGN () ? -1 : 1;
84 return *(const int *) a - *(const int *) b;
85}
86
87/* Permute an array of integers. */
88static void
89memfry (int *string)
90{
91 int i;
92
93 for (i = 0; i < SIZE; ++i)
94 {
95 int32_t j;
96 int c;
97
98 j = random () % SIZE;
99
100 c = string[i];
101 string[i] = string[j];
102 string[j] = c;
103 }
104}
105
106static void
107walk_action (const void *nodep, const VISIT which, const int depth)
108{
109 int key = **(int **) nodep;
110
111 if (!stack_align_check[1])
112 stack_align_check[1] = TEST_STACK_ALIGN () ? -1 : 1;
113
114 if (depth > max_depth)
115 max_depth = depth;
116 if (which == leaf || which == preorder)
117 {
118 ++z[key];
119 depths[key] = depth;
120 }
121 else
122 {
123 if (depths[key] != depth)
124 {
125 fputs ("Depth for one element is not constant during tree walk.\n",
126 stdout);
127 }
128 }
129}
130
131static void
132walk_tree (void *root, int expected_count)
133{
134 int i;
135
136 memset (z, 0, sizeof z);
137 max_depth = 0;
138
139 twalk (root, walk_action);
140 for (i = 0; i < expected_count; ++i)
141 if (z[i] != 1)
142 {
143 fputs ("Node was not visited.\n", stdout);
144 error = 1;
145 }
146
147#if BALANCED
148 if (max_depth > log (expected_count) * 2 + 2)
149#else
150 if (max_depth > expected_count)
151#endif
152 {
153 printf ("Depth too large during tree walk. max_depth=%d expected_count=%d (%d)\n",
154 max_depth, expected_count, log (expected_count) * 2 + 2);
155 error = 1;
156 }
157}
158
159/* Perform an operation on a tree. */
160static void
161mangle_tree (enum order how, enum action what, void **root, int lag)
162{
163 int i;
164
165 if (how == randomorder)
166 {
167 for (i = 0; i < SIZE; ++i)
168 y[i] = i;
169 memfry (y);
170 }
171
172 for (i = 0; i < SIZE + lag; ++i)
173 {
174 void *elem;
175 int j, k;
176
177 switch (how)
178 {
179 case randomorder:
180 if (i >= lag)
181 k = y[i - lag];
182 else
183 /* Ensure that the array index is within bounds. */
184 k = y[(SIZE - i - 1 + lag) % SIZE];
185 j = y[i % SIZE];
186 break;
187
188 case ascending:
189 k = i - lag;
190 j = i;
191 break;
192
193 case descending:
194 k = SIZE - i - 1 + lag;
195 j = SIZE - i - 1;
196 break;
197
198 default:
199 /* This never should happen, but gcc isn't smart enough to
200 recognize it. */
201 abort ();
202 }
203
204 switch (what)
205 {
206 case build_and_del:
207 case build:
208 if (i < SIZE)
209 {
210 if (tfind (x + j, (void *const *) root, cmp_fn) != NULL)
211 {
212 fputs ("Found element which is not in tree yet.\n", stdout);
213 error = 1;
214 }
215 elem = tsearch (x + j, root, cmp_fn);
216 if (elem == 0
217 || tfind (x + j, (void *const *) root, cmp_fn) == NULL)
218 {
219 fputs ("Couldn't find element after it was added.\n",
220 stdout);
221 error = 1;
222 }
223 }
224
225 if (what == build || i < lag)
226 break;
227
228 j = k;
229 /* fall through */
230
231 case delete:
232 elem = tfind (x + j, (void *const *) root, cmp_fn);
233 if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
234 {
235 fputs ("Error deleting element.\n", stdout);
236 error = 1;
237 }
238 break;
239
240 case find:
241 if (tfind (x + j, (void *const *) root, cmp_fn) == NULL)
242 {
243 fputs ("Couldn't find element after it was added.\n", stdout);
244 error = 1;
245 }
246 break;
247
248 }
249 }
250}
251
252
253int
254main (int argc, char **argv)
255{
256 int total_error = 0;
257 static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
258 void *root = NULL;
259 int i, j;
260
261 initstate (SEED, state, 8);
262
263 for (i = 0; i < SIZE; ++i)
264 x[i] = i;
265
266 /* Do this loop several times to get different permutations for the
267 random case. */
268 fputs ("Series I\n", stdout);
269 for (i = 0; i < PASSES; ++i)
270 {
271 fprintf (stdout, "Pass %d... ", i + 1);
272 fflush (stdout);
273 error = 0;
274
275 mangle_tree (ascending, build, &root, 0);
276 mangle_tree (ascending, find, &root, 0);
277 mangle_tree (descending, find, &root, 0);
278 mangle_tree (randomorder, find, &root, 0);
279 walk_tree (root, SIZE);
280 mangle_tree (ascending, delete, &root, 0);
281
282 mangle_tree (ascending, build, &root, 0);
283 walk_tree (root, SIZE);
284 mangle_tree (descending, delete, &root, 0);
285
286 mangle_tree (ascending, build, &root, 0);
287 walk_tree (root, SIZE);
288 mangle_tree (randomorder, delete, &root, 0);
289
290 mangle_tree (descending, build, &root, 0);
291 mangle_tree (ascending, find, &root, 0);
292 mangle_tree (descending, find, &root, 0);
293 mangle_tree (randomorder, find, &root, 0);
294 walk_tree (root, SIZE);
295 mangle_tree (descending, delete, &root, 0);
296
297 mangle_tree (descending, build, &root, 0);
298 walk_tree (root, SIZE);
299 mangle_tree (descending, delete, &root, 0);
300
301 mangle_tree (descending, build, &root, 0);
302 walk_tree (root, SIZE);
303 mangle_tree (randomorder, delete, &root, 0);
304
305 mangle_tree (randomorder, build, &root, 0);
306 mangle_tree (ascending, find, &root, 0);
307 mangle_tree (descending, find, &root, 0);
308 mangle_tree (randomorder, find, &root, 0);
309 walk_tree (root, SIZE);
310 mangle_tree (randomorder, delete, &root, 0);
311
312 for (j = 1; j < SIZE; j *= 2)
313 {
314 mangle_tree (randomorder, build_and_del, &root, j);
315 }
316
317 fputs (error ? " failed!\n" : " ok.\n", stdout);
318 total_error |= error;
319 }
320
321 fputs ("Series II\n", stdout);
322 for (i = 1; i < SIZE; i *= 2)
323 {
324 fprintf (stdout, "For size %d... ", i);
325 fflush (stdout);
326 error = 0;
327
328 mangle_tree (ascending, build_and_del, &root, i);
329 mangle_tree (descending, build_and_del, &root, i);
330 mangle_tree (ascending, build_and_del, &root, i);
331 mangle_tree (descending, build_and_del, &root, i);
332 mangle_tree (ascending, build_and_del, &root, i);
333 mangle_tree (descending, build_and_del, &root, i);
334 mangle_tree (ascending, build_and_del, &root, i);
335 mangle_tree (descending, build_and_del, &root, i);
336
337 fputs (error ? " failed!\n" : " ok.\n", stdout);
338 total_error |= error;
339 }
340
341 for (i = 0; i < 2; ++i)
342 if (stack_align_check[i] == 0)
343 {
344 printf ("stack alignment check %d not run\n", i);
345 total_error |= 1;
346 }
347 else if (stack_align_check[i] != 1)
348 {
349 printf ("stack insufficiently aligned in check %d\n", i);
350 total_error |= 1;
351 }
352
353 return total_error;
354}
Note: See TracBrowser for help on using the repository browser.