(distribute): Add README.utmpd.
[kopensolaris-gnu/glibc.git] / misc / tst-tsearch.c
1 /* Test program for tsearch et al.
2    Copyright (C) 1997 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 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.
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    Library General Public License for more details.
14
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.  */
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             k = y[SIZE - i - 1 + lag];
175           j = y[i];
176           break;
177
178         case ascending:
179           k = i - lag;
180           j = i;
181           break;
182
183         case descending:
184           k = SIZE - i - 1 + lag;
185           j = SIZE - i - 1;
186           break;
187
188         default:
189           /* This never should happen, but gcc isn't smart enough to
190              recognize it.  */
191           abort ();
192         }
193
194       switch (what)
195         {
196         case build_and_del:
197         case build:
198           if (i < SIZE)
199             {
200               if (tfind (x + j, (void *const *) root, cmp_fn) != NULL)
201                 {
202                   fputs ("Found element which is not in tree yet.\n", stdout);
203                   error = 1;
204                 }
205               elem = tsearch (x + j, root, cmp_fn);
206               if (elem == 0
207                   || tfind (x + j, (void *const *) root, cmp_fn) == NULL)
208                 {
209                   fputs ("Couldn't find element after it was added.\n",
210                          stdout);
211                   error = 1;
212                 }
213             }
214
215           if (what == build || i < lag)
216             break;
217
218           j = k;
219           /* fall through */
220
221         case delete:
222           elem = tfind (x + j, (void *const *) root, cmp_fn);
223           if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
224             {
225               fputs ("Error deleting element.\n", stdout);
226               error = 1;
227             }
228           break;
229
230         case find:
231           if (tfind (x + j, (void *const *) root, cmp_fn) == NULL)
232             {
233               fputs ("Couldn't find element after it was added.\n", stdout);
234               error = 1;
235             }
236           break;
237
238         }
239     }
240 }
241
242
243 int
244 main (int argc, char **argv)
245 {
246   int total_error = 0;
247   static int state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
248   void *root = NULL;
249   int i, j;
250
251   initstate (SEED, state, 8);
252
253   for (i = 0; i < SIZE; ++i)
254     x[i] = i;
255
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)
260     {
261       fprintf (stdout, "Pass %d... ", i + 1);
262       fflush (stdout);
263       error = 0;
264
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);
271
272       mangle_tree (ascending, build, &root, 0);
273       walk_tree (root, SIZE);
274       mangle_tree (descending, delete, &root, 0);
275
276       mangle_tree (ascending, build, &root, 0);
277       walk_tree (root, SIZE);
278       mangle_tree (randomorder, delete, &root, 0);
279
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);
286
287       mangle_tree (descending, build, &root, 0);
288       walk_tree (root, SIZE);
289       mangle_tree (descending, delete, &root, 0);
290
291       mangle_tree (descending, build, &root, 0);
292       walk_tree (root, SIZE);
293       mangle_tree (randomorder, delete, &root, 0);
294
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);
301
302       for (j = 1; j < SIZE; j *= 2)
303         {
304           mangle_tree (randomorder, build_and_del, &root, j);
305         }
306
307       fputs (error ? " failed!\n" : " ok.\n", stdout);
308       total_error |= error;
309     }
310
311   fputs ("Series II\n", stdout);
312   for (i = 1; i < SIZE; i *= 2)
313     {
314       fprintf (stdout, "For size %d... ", i);
315       fflush (stdout);
316       error = 0;
317
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);
326
327       fputs (error ? " failed!\n" : " ok.\n", stdout);
328       total_error |= error;
329     }
330
331   return total_error;
332 }