Generic getdtsz.c.
[kopensolaris-gnu/glibc.git] / misc / tst-tsearch.c
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
41 enum order
42 {
43   ascending,
44   descending,
45   randomorder
46 };
47
48 enum action
49 {
50   build,
51   build_and_del,
52   delete,
53   find
54 };
55
56 /* Set to 1 if a test is flunked.  */
57 static int error = 0;
58
59 /* The keys we add to the tree.  */
60 static int x[SIZE];
61
62 /* Pointers into the key array, possibly permutated, to define an order
63    for insertion/removal.  */
64 static int y[SIZE];
65
66 /* Flags set for each element visited during a tree walk.  */
67 static int z[SIZE];
68
69 /* Depths for all the elements, to check that the depth is constant for
70    all three visits.  */
71 static int depths[SIZE];
72
73 /* Maximum depth during a tree walk.  */
74 static int max_depth;
75
76 static int stack_align_check[2];
77
78 /* Compare two keys.  */
79 static int
80 cmp_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.  */
88 static void
89 memfry (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
106 static void
107 walk_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
131 static void
132 walk_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       fputs ("Depth too large during tree walk.\n", stdout);
154       error = 1;
155     }
156 }
157
158 /* Perform an operation on a tree.  */
159 static void
160 mangle_tree (enum order how, enum action what, void **root, int lag)
161 {
162   int i;
163
164   if (how == randomorder)
165     {
166       for (i = 0; i < SIZE; ++i)
167         y[i] = i;
168       memfry (y);
169     }
170
171   for (i = 0; i < SIZE + lag; ++i)
172     {
173       void *elem;
174       int j, k;
175
176       switch (how)
177         {
178         case randomorder:
179           if (i >= lag)
180             k = y[i - lag];
181           else
182             /* Ensure that the array index is within bounds.  */
183             k = y[(SIZE - i - 1 + lag) % SIZE];
184           j = y[i % SIZE];
185           break;
186
187         case ascending:
188           k = i - lag;
189           j = i;
190           break;
191
192         case descending:
193           k = SIZE - i - 1 + lag;
194           j = SIZE - i - 1;
195           break;
196
197         default:
198           /* This never should happen, but gcc isn't smart enough to
199              recognize it.  */
200           abort ();
201         }
202
203       switch (what)
204         {
205         case build_and_del:
206         case build:
207           if (i < SIZE)
208             {
209               if (tfind (x + j, (void *const *) root, cmp_fn) != NULL)
210                 {
211                   fputs ("Found element which is not in tree yet.\n", stdout);
212                   error = 1;
213                 }
214               elem = tsearch (x + j, root, cmp_fn);
215               if (elem == 0
216                   || tfind (x + j, (void *const *) root, cmp_fn) == NULL)
217                 {
218                   fputs ("Couldn't find element after it was added.\n",
219                          stdout);
220                   error = 1;
221                 }
222             }
223
224           if (what == build || i < lag)
225             break;
226
227           j = k;
228           /* fall through */
229
230         case delete:
231           elem = tfind (x + j, (void *const *) root, cmp_fn);
232           if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
233             {
234               fputs ("Error deleting element.\n", stdout);
235               error = 1;
236             }
237           break;
238
239         case find:
240           if (tfind (x + j, (void *const *) root, cmp_fn) == NULL)
241             {
242               fputs ("Couldn't find element after it was added.\n", stdout);
243               error = 1;
244             }
245           break;
246
247         }
248     }
249 }
250
251
252 int
253 main (int argc, char **argv)
254 {
255   int total_error = 0;
256   static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
257   void *root = NULL;
258   int i, j;
259
260   initstate (SEED, state, 8);
261
262   for (i = 0; i < SIZE; ++i)
263     x[i] = i;
264
265   /* Do this loop several times to get different permutations for the
266      random case.  */
267   fputs ("Series I\n", stdout);
268   for (i = 0; i < PASSES; ++i)
269     {
270       fprintf (stdout, "Pass %d... ", i + 1);
271       fflush (stdout);
272       error = 0;
273
274       mangle_tree (ascending, build, &root, 0);
275       mangle_tree (ascending, find, &root, 0);
276       mangle_tree (descending, find, &root, 0);
277       mangle_tree (randomorder, find, &root, 0);
278       walk_tree (root, SIZE);
279       mangle_tree (ascending, delete, &root, 0);
280
281       mangle_tree (ascending, build, &root, 0);
282       walk_tree (root, SIZE);
283       mangle_tree (descending, delete, &root, 0);
284
285       mangle_tree (ascending, build, &root, 0);
286       walk_tree (root, SIZE);
287       mangle_tree (randomorder, delete, &root, 0);
288
289       mangle_tree (descending, build, &root, 0);
290       mangle_tree (ascending, find, &root, 0);
291       mangle_tree (descending, find, &root, 0);
292       mangle_tree (randomorder, find, &root, 0);
293       walk_tree (root, SIZE);
294       mangle_tree (descending, delete, &root, 0);
295
296       mangle_tree (descending, build, &root, 0);
297       walk_tree (root, SIZE);
298       mangle_tree (descending, delete, &root, 0);
299
300       mangle_tree (descending, build, &root, 0);
301       walk_tree (root, SIZE);
302       mangle_tree (randomorder, delete, &root, 0);
303
304       mangle_tree (randomorder, build, &root, 0);
305       mangle_tree (ascending, find, &root, 0);
306       mangle_tree (descending, find, &root, 0);
307       mangle_tree (randomorder, find, &root, 0);
308       walk_tree (root, SIZE);
309       mangle_tree (randomorder, delete, &root, 0);
310
311       for (j = 1; j < SIZE; j *= 2)
312         {
313           mangle_tree (randomorder, build_and_del, &root, j);
314         }
315
316       fputs (error ? " failed!\n" : " ok.\n", stdout);
317       total_error |= error;
318     }
319
320   fputs ("Series II\n", stdout);
321   for (i = 1; i < SIZE; i *= 2)
322     {
323       fprintf (stdout, "For size %d... ", i);
324       fflush (stdout);
325       error = 0;
326
327       mangle_tree (ascending, build_and_del, &root, i);
328       mangle_tree (descending, build_and_del, &root, i);
329       mangle_tree (ascending, build_and_del, &root, i);
330       mangle_tree (descending, build_and_del, &root, i);
331       mangle_tree (ascending, build_and_del, &root, i);
332       mangle_tree (descending, build_and_del, &root, i);
333       mangle_tree (ascending, build_and_del, &root, i);
334       mangle_tree (descending, build_and_del, &root, i);
335
336       fputs (error ? " failed!\n" : " ok.\n", stdout);
337       total_error |= error;
338     }
339
340   for (i = 0; i < 2; ++i)
341     if (stack_align_check[i] == 0)
342       {
343         printf ("stack alignment check %d not run\n", i);
344         total_error |= 1;
345       }
346     else if (stack_align_check[i] != 1)
347       {
348         printf ("stack insufficiently aligned in check %d\n", i);
349         total_error |= 1;
350       }
351
352   return total_error;
353 }