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