]>
Commit | Line | Data |
---|---|---|
993b3242 | 1 | /* Test program for tsearch et al. |
688903eb | 2 | Copyright (C) 1997-2018 Free Software Foundation, Inc. |
993b3242 UD |
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 | |
41bdb6e2 AJ |
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. | |
993b3242 UD |
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 | |
41bdb6e2 | 13 | Lesser General Public License for more details. |
993b3242 | 14 | |
41bdb6e2 | 15 | You should have received a copy of the GNU Lesser General Public |
59ba27a6 PE |
16 | License along with the GNU C Library; if not, see |
17 | <http://www.gnu.org/licenses/>. */ | |
993b3242 | 18 | |
c131718c UD |
19 | #ifndef _GNU_SOURCE |
20 | # define _GNU_SOURCE 1 | |
21 | #endif | |
993b3242 UD |
22 | |
23 | #include <stdio.h> | |
24 | #include <stdlib.h> | |
c131718c | 25 | #include <string.h> |
993b3242 | 26 | #include <search.h> |
06f6ca90 | 27 | #include <tst-stack-align.h> |
993b3242 UD |
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 | ||
06f6ca90 UD |
75 | static int stack_align_check[2]; |
76 | ||
993b3242 UD |
77 | /* Compare two keys. */ |
78 | static int | |
79 | cmp_fn (const void *a, const void *b) | |
80 | { | |
06f6ca90 UD |
81 | if (!stack_align_check[0]) |
82 | stack_align_check[0] = TEST_STACK_ALIGN () ? -1 : 1; | |
993b3242 UD |
83 | return *(const int *) a - *(const int *) b; |
84 | } | |
85 | ||
86 | /* Permute an array of integers. */ | |
87 | static void | |
88 | memfry (int *string) | |
89 | { | |
90 | int i; | |
91 | ||
92 | for (i = 0; i < SIZE; ++i) | |
93 | { | |
94 | int32_t j; | |
95 | int c; | |
96 | ||
97 | j = random () % SIZE; | |
98 | ||
99 | c = string[i]; | |
100 | string[i] = string[j]; | |
101 | string[j] = c; | |
102 | } | |
103 | } | |
104 | ||
105 | static void | |
106 | walk_action (const void *nodep, const VISIT which, const int depth) | |
107 | { | |
108 | int key = **(int **) nodep; | |
109 | ||
06f6ca90 UD |
110 | if (!stack_align_check[1]) |
111 | stack_align_check[1] = TEST_STACK_ALIGN () ? -1 : 1; | |
112 | ||
993b3242 UD |
113 | if (depth > max_depth) |
114 | max_depth = depth; | |
115 | if (which == leaf || which == preorder) | |
116 | { | |
117 | ++z[key]; | |
118 | depths[key] = depth; | |
119 | } | |
120 | else | |
121 | { | |
122 | if (depths[key] != depth) | |
123 | { | |
124 | fputs ("Depth for one element is not constant during tree walk.\n", | |
5929563f | 125 | stdout); |
993b3242 UD |
126 | } |
127 | } | |
128 | } | |
129 | ||
130 | static void | |
131 | walk_tree (void *root, int expected_count) | |
132 | { | |
133 | int i; | |
134 | ||
135 | memset (z, 0, sizeof z); | |
136 | max_depth = 0; | |
137 | ||
138 | twalk (root, walk_action); | |
139 | for (i = 0; i < expected_count; ++i) | |
140 | if (z[i] != 1) | |
141 | { | |
5929563f | 142 | fputs ("Node was not visited.\n", stdout); |
993b3242 UD |
143 | error = 1; |
144 | } | |
145 | ||
146 | #if BALANCED | |
147 | if (max_depth > log (expected_count) * 2 + 2) | |
148 | #else | |
149 | if (max_depth > expected_count) | |
150 | #endif | |
151 | { | |
5929563f | 152 | fputs ("Depth too large during tree walk.\n", stdout); |
993b3242 UD |
153 | error = 1; |
154 | } | |
155 | } | |
156 | ||
157 | /* Perform an operation on a tree. */ | |
158 | static void | |
159 | mangle_tree (enum order how, enum action what, void **root, int lag) | |
160 | { | |
161 | int i; | |
162 | ||
163 | if (how == randomorder) | |
164 | { | |
165 | for (i = 0; i < SIZE; ++i) | |
166 | y[i] = i; | |
167 | memfry (y); | |
168 | } | |
169 | ||
170 | for (i = 0; i < SIZE + lag; ++i) | |
171 | { | |
172 | void *elem; | |
173 | int j, k; | |
174 | ||
175 | switch (how) | |
176 | { | |
177 | case randomorder: | |
178 | if (i >= lag) | |
179 | k = y[i - lag]; | |
180 | else | |
673c34e0 AJ |
181 | /* Ensure that the array index is within bounds. */ |
182 | k = y[(SIZE - i - 1 + lag) % SIZE]; | |
183 | j = y[i % SIZE]; | |
993b3242 UD |
184 | break; |
185 | ||
186 | case ascending: | |
187 | k = i - lag; | |
188 | j = i; | |
189 | break; | |
190 | ||
191 | case descending: | |
192 | k = SIZE - i - 1 + lag; | |
193 | j = SIZE - i - 1; | |
194 | break; | |
195 | ||
196 | default: | |
197 | /* This never should happen, but gcc isn't smart enough to | |
198 | recognize it. */ | |
199 | abort (); | |
200 | } | |
201 | ||
202 | switch (what) | |
203 | { | |
204 | case build_and_del: | |
205 | case build: | |
206 | if (i < SIZE) | |
207 | { | |
f671aeab | 208 | if (tfind (x + j, (void *const *) root, cmp_fn) != NULL) |
993b3242 | 209 | { |
5929563f | 210 | fputs ("Found element which is not in tree yet.\n", stdout); |
993b3242 UD |
211 | error = 1; |
212 | } | |
213 | elem = tsearch (x + j, root, cmp_fn); | |
214 | if (elem == 0 | |
f671aeab | 215 | || tfind (x + j, (void *const *) root, cmp_fn) == NULL) |
993b3242 UD |
216 | { |
217 | fputs ("Couldn't find element after it was added.\n", | |
5929563f | 218 | stdout); |
993b3242 UD |
219 | error = 1; |
220 | } | |
221 | } | |
222 | ||
223 | if (what == build || i < lag) | |
224 | break; | |
225 | ||
226 | j = k; | |
227 | /* fall through */ | |
228 | ||
229 | case delete: | |
f671aeab | 230 | elem = tfind (x + j, (void *const *) root, cmp_fn); |
993b3242 UD |
231 | if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL) |
232 | { | |
5929563f | 233 | fputs ("Error deleting element.\n", stdout); |
993b3242 UD |
234 | error = 1; |
235 | } | |
236 | break; | |
237 | ||
238 | case find: | |
f671aeab | 239 | if (tfind (x + j, (void *const *) root, cmp_fn) == NULL) |
993b3242 | 240 | { |
5929563f | 241 | fputs ("Couldn't find element after it was added.\n", stdout); |
993b3242 UD |
242 | error = 1; |
243 | } | |
244 | break; | |
245 | ||
246 | } | |
247 | } | |
248 | } | |
249 | ||
250 | ||
c1f41083 AS |
251 | static int |
252 | do_test (void) | |
993b3242 UD |
253 | { |
254 | int total_error = 0; | |
621d9092 | 255 | static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 }; |
993b3242 UD |
256 | void *root = NULL; |
257 | int i, j; | |
258 | ||
259 | initstate (SEED, state, 8); | |
260 | ||
261 | for (i = 0; i < SIZE; ++i) | |
262 | x[i] = i; | |
263 | ||
264 | /* Do this loop several times to get different permutations for the | |
265 | random case. */ | |
5929563f | 266 | fputs ("Series I\n", stdout); |
993b3242 UD |
267 | for (i = 0; i < PASSES; ++i) |
268 | { | |
5929563f | 269 | fprintf (stdout, "Pass %d... ", i + 1); |
993b3242 UD |
270 | fflush (stdout); |
271 | error = 0; | |
272 | ||
273 | mangle_tree (ascending, build, &root, 0); | |
274 | mangle_tree (ascending, find, &root, 0); | |
275 | mangle_tree (descending, find, &root, 0); | |
276 | mangle_tree (randomorder, find, &root, 0); | |
277 | walk_tree (root, SIZE); | |
278 | mangle_tree (ascending, delete, &root, 0); | |
279 | ||
280 | mangle_tree (ascending, build, &root, 0); | |
281 | walk_tree (root, SIZE); | |
282 | mangle_tree (descending, delete, &root, 0); | |
283 | ||
284 | mangle_tree (ascending, build, &root, 0); | |
285 | walk_tree (root, SIZE); | |
286 | mangle_tree (randomorder, delete, &root, 0); | |
287 | ||
288 | mangle_tree (descending, build, &root, 0); | |
289 | mangle_tree (ascending, find, &root, 0); | |
290 | mangle_tree (descending, find, &root, 0); | |
291 | mangle_tree (randomorder, find, &root, 0); | |
292 | walk_tree (root, SIZE); | |
293 | mangle_tree (descending, delete, &root, 0); | |
294 | ||
295 | mangle_tree (descending, build, &root, 0); | |
296 | walk_tree (root, SIZE); | |
297 | mangle_tree (descending, delete, &root, 0); | |
298 | ||
299 | mangle_tree (descending, build, &root, 0); | |
300 | walk_tree (root, SIZE); | |
301 | mangle_tree (randomorder, delete, &root, 0); | |
302 | ||
303 | mangle_tree (randomorder, build, &root, 0); | |
304 | mangle_tree (ascending, find, &root, 0); | |
305 | mangle_tree (descending, find, &root, 0); | |
306 | mangle_tree (randomorder, find, &root, 0); | |
307 | walk_tree (root, SIZE); | |
308 | mangle_tree (randomorder, delete, &root, 0); | |
309 | ||
310 | for (j = 1; j < SIZE; j *= 2) | |
311 | { | |
312 | mangle_tree (randomorder, build_and_del, &root, j); | |
313 | } | |
314 | ||
5929563f | 315 | fputs (error ? " failed!\n" : " ok.\n", stdout); |
993b3242 UD |
316 | total_error |= error; |
317 | } | |
318 | ||
5929563f | 319 | fputs ("Series II\n", stdout); |
993b3242 UD |
320 | for (i = 1; i < SIZE; i *= 2) |
321 | { | |
5929563f | 322 | fprintf (stdout, "For size %d... ", i); |
993b3242 UD |
323 | fflush (stdout); |
324 | error = 0; | |
325 | ||
326 | mangle_tree (ascending, build_and_del, &root, i); | |
327 | mangle_tree (descending, build_and_del, &root, i); | |
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 | ||
5929563f | 335 | fputs (error ? " failed!\n" : " ok.\n", stdout); |
993b3242 UD |
336 | total_error |= error; |
337 | } | |
338 | ||
06f6ca90 UD |
339 | for (i = 0; i < 2; ++i) |
340 | if (stack_align_check[i] == 0) | |
341 | { | |
342 | printf ("stack alignment check %d not run\n", i); | |
343 | total_error |= 1; | |
344 | } | |
345 | else if (stack_align_check[i] != 1) | |
346 | { | |
347 | printf ("stack insufficiently aligned in check %d\n", i); | |
348 | total_error |= 1; | |
349 | } | |
350 | ||
993b3242 UD |
351 | return total_error; |
352 | } | |
c1f41083 AS |
353 | |
354 | #define TEST_FUNCTION do_test () | |
355 | #include "../test-skeleton.c" |