(libc) [GLIBC_PRIVATE]: Add __libc_readv and __libc_writev.
[kopensolaris-gnu/glibc.git] / 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.
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
29 #define SEED 0
30 #define BALANCED 1
31 #define PASSES 100
32
33 #if BALANCED
34 #include <math.h>
35 #define SIZE 1000
36 #else
37 #define SIZE 100
38 #endif
39
40 enum order
41 {
42   ascending,
43   descending,
44   randomorder
45 };
46
47 enum action
48 {
49   build,
50   build_and_del,
51   delete,
52   find
53 };
54
55 /* Set to 1 if a test is flunked.  */
56 static int error = 0;
57
58 /* The keys we add to the tree.  */
59 static int x[SIZE];
60
61 /* Pointers into the key array, possibly permutated, to define an order
62    for insertion/removal.  */
63 static int y[SIZE];
64
65 /* Flags set for each element visited during a tree walk.  */
66 static int z[SIZE];
67
68 /* Depths for all the elements, to check that the depth is constant for
69    all three visits.  */
70 static int depths[SIZE];
71
72 /* Maximum depth during a tree walk.  */
73 static int max_depth;
74
75 /* Compare two keys.  */
76 static int
77 cmp_fn (const void *a, const void *b)
78 {
79   return *(const int *) a - *(const int *) b;
80 }
81
82 /* Permute an array of integers.  */
83 static void
84 memfry (int *string)
85 {
86   int i;
87
88   for (i = 0; i < SIZE; ++i)
89     {
90       int32_t j;
91       int c;
92
93       j = random () % SIZE;
94
95       c = string[i];
96       string[i] = string[j];
97       string[j] = c;
98     }
99 }
100
101 static void
102 walk_action (const void *nodep, const VISIT which, const int depth)
103 {
104   int key = **(int **) nodep;
105
106   if (depth > max_depth)
107     max_depth = depth;
108   if (which == leaf || which == preorder)
109     {
110       ++z[key];
111       depths[key] = depth;
112     }
113   else
114     {
115       if (depths[key] != depth)
116         {
117           fputs ("Depth for one element is not constant during tree walk.\n",
118                  stdout);
119         }
120     }
121 }
122
123 static void
124 walk_tree (void *root, int expected_count)
125 {
126   int i;
127
128   memset (z, 0, sizeof z);
129   max_depth = 0;
130
131   twalk (root, walk_action);
132   for (i = 0; i < expected_count; ++i)
133     if (z[i] != 1)
134       {
135         fputs ("Node was not visited.\n", stdout);
136         error = 1;
137       }
138
139 #if BALANCED
140   if (max_depth > log (expected_count) * 2 + 2)
141 #else
142   if (max_depth > expected_count)
143 #endif
144     {
145       fputs ("Depth too large during tree walk.\n", stdout);
146       error = 1;
147     }
148 }
149
150 /* Perform an operation on a tree.  */
151 static void
152 mangle_tree (enum order how, enum action what, void **root, int lag)
153 {
154   int i;
155
156   if (how == randomorder)
157     {
158       for (i = 0; i < SIZE; ++i)
159         y[i] = i;
160       memfry (y);
161     }
162
163   for (i = 0; i < SIZE + lag; ++i)
164     {
165       void *elem;
166       int j, k;
167
168       switch (how)
169         {
170         case randomorder:
171           if (i >= lag)
172             k = y[i - lag];
173           else
174             /* Ensure that the array index is within bounds.  */
175             k = y[(SIZE - i - 1 + lag) % SIZE];
176           j = y[i % SIZE];
177           break;
178
179         case ascending:
180           k = i - lag;
181           j = i;
182           break;
183
184         case descending:
185           k = SIZE - i - 1 + lag;
186           j = SIZE - i - 1;
187           break;
188
189         default:
190           /* This never should happen, but gcc isn't smart enough to
191              recognize it.  */
192           abort ();
193         }
194
195       switch (what)
196         {
197         case build_and_del:
198         case build:
199           if (i < SIZE)
200             {
201               if (tfind (x + j, (void *const *) root, cmp_fn) != NULL)
202                 {
203                   fputs ("Found element which is not in tree yet.\n", stdout);
204                   error = 1;
205                 }
206               elem = tsearch (x + j, root, cmp_fn);
207               if (elem == 0
208                   || tfind (x + j, (void *const *) root, cmp_fn) == NULL)
209                 {
210                   fputs ("Couldn't find element after it was added.\n",
211                          stdout);
212                   error = 1;
213                 }
214             }
215
216           if (what == build || i < lag)
217             break;
218
219           j = k;
220           /* fall through */
221
222         case delete:
223           elem = tfind (x + j, (void *const *) root, cmp_fn);
224           if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
225             {
226               fputs ("Error deleting element.\n", stdout);
227               error = 1;
228             }
229           break;
230
231         case find:
232           if (tfind (x + j, (void *const *) root, cmp_fn) == NULL)
233             {
234               fputs ("Couldn't find element after it was added.\n", stdout);
235               error = 1;
236             }
237           break;
238
239         }
240     }
241 }
242
243
244 int
245 main (int argc, char **argv)
246 {
247   int total_error = 0;
248   static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
249   void *root = NULL;
250   int i, j;
251
252   initstate (SEED, state, 8);
253
254   for (i = 0; i < SIZE; ++i)
255     x[i] = i;
256
257   /* Do this loop several times to get different permutations for the
258      random case.  */
259   fputs ("Series I\n", stdout);
260   for (i = 0; i < PASSES; ++i)
261     {
262       fprintf (stdout, "Pass %d... ", i + 1);
263       fflush (stdout);
264       error = 0;
265
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);
272
273       mangle_tree (ascending, build, &root, 0);
274       walk_tree (root, SIZE);
275       mangle_tree (descending, delete, &root, 0);
276
277       mangle_tree (ascending, build, &root, 0);
278       walk_tree (root, SIZE);
279       mangle_tree (randomorder, delete, &root, 0);
280
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);
287
288       mangle_tree (descending, build, &root, 0);
289       walk_tree (root, SIZE);
290       mangle_tree (descending, delete, &root, 0);
291
292       mangle_tree (descending, build, &root, 0);
293       walk_tree (root, SIZE);
294       mangle_tree (randomorder, delete, &root, 0);
295
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);
302
303       for (j = 1; j < SIZE; j *= 2)
304         {
305           mangle_tree (randomorder, build_and_del, &root, j);
306         }
307
308       fputs (error ? " failed!\n" : " ok.\n", stdout);
309       total_error |= error;
310     }
311
312   fputs ("Series II\n", stdout);
313   for (i = 1; i < SIZE; i *= 2)
314     {
315       fprintf (stdout, "For size %d... ", i);
316       fflush (stdout);
317       error = 0;
318
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);
327
328       fputs (error ? " failed!\n" : " ok.\n", stdout);
329       total_error |= error;
330     }
331
332   return total_error;
333 }