1 /* unit-bits.c - test bits.c
2 *
3 ****************************************************************
4 * Copyright (C) 2000 Thomas Lord
5 *
6 * See the file "COPYING" for further information about
7 * the copyright and warranty status of this work.
8 */
9
10
11
12 #include "hackerlab/char/str.h"
13 #include "hackerlab/bitsets/bits.h"
14 #include "hackerlab/cmd/main.h"
15
16
17
18 static t_uchar * program_name = "unit-bits";
19 static t_uchar * usage = "[options]";
20 static t_uchar * version_string = "1.0";
21
22 #define OPTS(OP, OP2) \
23 OP (opt_help_msg, "h", "help", 0, \
24 "Display a help message and exit.") \
25 OP (opt_version, "V", "version", 0, \
26 "Display a release identifier string") \
27 OP2 (opt_version, 0, 0, 0, "and exit.") \
28 OP (opt_iterations, "i", "iterations n", 1, \
29 "Run all tests `n' times.")
30
31 enum options
32 {
33 OPTS (OPT_ENUM, OPT_IGN)
34 };
35
36 struct opt_desc opts[] =
37 {
38 OPTS (OPT_DESC, OPT_DESC)
39 {-1, 0, 0, 0, 0}
40 };
41
42
43
44
45 #if 1
46 struct bits_tree_rule rules[] = {{16, 256*16, 12, 0xfff}, {16, 256, 0, 0}, {0, 256, 0, 0}};
47 #else
48 struct bits_tree_rule rules[] = {{256, 256, 8, 0xff}, {0, 256, 0, 0}};
49 #endif
50
51 static bits
make_test_set(bitset members)52 make_test_set (bitset members)
53 {
54 bits answer;
55 int x;
56
57 answer = bits_alloc (0, rules);
58 for (x = 0; x < 65536; ++x)
59 if (bitset_is_member (members, x))
60 bits_adjoin (answer, x);
61 bits_compact (answer);
62 return answer;
63 }
64
65 static int test_no = 0;
66
67 static int
compare_test_result(bits test_answer,bitset answer)68 compare_test_result (bits test_answer, bitset answer)
69 {
70 int x;
71
72 for (x = 0; x < 65536; ++x)
73 if (bitset_is_member (answer, x) != bits_is_member (test_answer, x))
74 panic ("test failed");
75 bits_compact (test_answer);
76 for (x = 0; x < 65536; ++x)
77 if (bitset_is_member (answer, x) != bits_is_member (test_answer, x))
78 panic ("test failed");
79 return 1;
80 }
81
82 static void
free_test_set(bits b)83 free_test_set (bits b)
84 {
85 bits_free (b);
86 }
87
88
89
90 static bitset
make_empty_bitset(void)91 make_empty_bitset (void)
92 {
93 return bitset_alloc (lim_use_must_malloc, 65536);
94 }
95
96
97 static bitset
make_full_bitset(void)98 make_full_bitset (void)
99 {
100 bitset b;
101
102 b = bitset_alloc (lim_use_must_malloc, 65536);
103 bitset_fill (65536, b);
104 return b;
105 }
106
107
108 static bitset
make_random_bitset(void)109 make_random_bitset (void)
110 {
111 bitset b;
112 int x;
113
114 b = bitset_alloc (lim_use_must_malloc, 65536);
115 for (x = 0; x < 65536; ++x)
116 if (random () & 1)
117 bitset_adjoin (b, x);
118
119 return b;
120 }
121
122 static bitset (*contents_fns[])(void) =
123 {
124 make_empty_bitset,
125 make_full_bitset,
126 make_random_bitset,
127 0
128 };
129
130
131
132 static int
make_zero_index(void)133 make_zero_index (void)
134 {
135 return 0;
136 }
137
138 static int
make_max_index(void)139 make_max_index (void)
140 {
141 return 65535;
142 }
143
144 static int
make_random_index(void)145 make_random_index (void)
146 {
147 return random () % 65536;
148 }
149
150 static int (*index_fns[])(void) =
151 {
152 make_zero_index,
153 make_max_index,
154 make_random_index,
155 0
156 };
157
158
159
160
161 static void
make_full_range(int * from,int * to)162 make_full_range (int * from, int * to)
163 {
164 *from = 0;
165 *to = 65536;
166 }
167
168
169 static void
make_empty_range(int * from,int * to)170 make_empty_range (int * from, int * to)
171 {
172 *from = random () % 65537;
173 if (!*from)
174 *to = 0;
175 else
176 *to = random () % *from;
177 }
178
179
180 static void
make_small_random_range(int * from,int * to)181 make_small_random_range (int * from, int * to)
182 {
183 *from = random () % (65536 - 256);
184 *to = *from + random () % 256;
185 }
186
187
188 static void
make_medium_random_range(int * from,int * to)189 make_medium_random_range (int * from, int * to)
190 {
191 *from = random () % (65536 - 256);
192 *to = *from + random () % 256;
193 }
194
195
196 static void
make_large_random_range(int * from,int * to)197 make_large_random_range (int * from, int * to)
198 {
199 *to = 1024 + (random () % (65537 - 1024));
200 *from = random () % (*to - 768);
201 }
202
203
204 static void
make_tail_range(int * from,int * to)205 make_tail_range (int * from, int * to)
206 {
207 *from = random () % 65537;
208 *to = 65536;
209 }
210
211 static void
make_head_range(int * from,int * to)212 make_head_range (int * from, int * to)
213 {
214 *from = 0;
215 *to = random () % 65537;
216 }
217
218 static void (*range_fns[])(int *, int *) =
219 {
220 make_full_range,
221 make_empty_range,
222 make_small_random_range,
223 make_medium_random_range,
224 make_large_random_range,
225 make_tail_range,
226 make_head_range,
227 0
228 };
229
230
231
232
233 int
main(int argc,char * argv[])234 main (int argc, char * argv[])
235 {
236 int errn;
237 int o;
238 struct opt_parsed * option;
239 int iterations;
240
241 option = 0;
242 iterations = 1;
243
244 while (1)
245 {
246 o = opt_standard (lim_use_must_malloc, &option, opts, &argc, argv, program_name, usage, version_string, 0, opt_help_msg, opt_none, opt_version);
247
248 if (o == opt_none)
249 break;
250
251 switch (o)
252 {
253 default:
254 safe_printfmt (2, "unhandled option `%s'\n", option->opt_string);
255 panic ("internal error parsing arguments");
256
257 usage_error:
258 opt_usage (2, argv[0], program_name, usage, 1);
259 panic_exit ();
260
261 bogus_arg:
262 safe_printfmt (2, "ill-formed argument for `%s' (`%s')\n", option->opt_string, option->arg_string);
263 goto usage_error;
264
265 case opt_iterations:
266 if (cvt_decimal_to_uint (&errn, &iterations, option->arg_string, str_length (option->arg_string)))
267 goto bogus_arg;
268 break;
269 }
270 }
271
272 while (iterations--)
273 {
274 /* functions that operate on a bitset */
275 {
276 int contents_fn;
277
278 for (contents_fn = 0; contents_fns [contents_fn]; ++contents_fn)
279 {
280 enum bitset_fn
281 {
282 is_empty,
283 is_full,
284 population,
285 clear,
286 fill,
287 complement,
288 ffs,
289 ffc,
290 max_bitset_fn = ffc
291 } fn;
292
293 for (fn = 0; fn <= max_bitset_fn; ++fn)
294 {
295 bitset b;
296 bits b16;
297
298 ++test_no;
299 b = contents_fns[contents_fn]();
300 b16 = make_test_set (b);
301
302 switch (fn)
303 {
304 default:
305 panic ("missing test fn");
306 case is_empty:
307 if (!(bitset_is_empty (65536, b) == bits_is_empty (b16)))
308 panic ("bitset_is_empty test failed");
309 break;
310 case is_full:
311 if (!(bitset_is_full (65536, b) == bits_is_full (b16)))
312 panic ("bitset_is_full test failed");
313 break;
314 case population:
315 if (!(bitset_population (65536, b) == bits_population (b16)))
316 panic ("bitset_population test failed");
317 break;
318 case ffs:
319 if (!(bitset_ffs (65536, b) == bits_ffs (b16)))
320 panic ("bitset_ffs test failed");
321 break;
322 case ffc:
323 if (!(bitset_ffc (65536, b) == bits_ffc (b16)))
324 panic ("bitset_ffc test failed");
325 break;
326 case clear:
327 bitset_clear (65536, b);
328 bits_clear (b16);
329 compare_test_result (b16, b);
330 break;
331 case fill:
332 bitset_fill (65536, b);
333 bits_fill (b16);
334 compare_test_result (b16, b);
335 break;
336 case complement:
337 bitset_complement (65536, b);
338 bits_complement (b16);
339 compare_test_result (b16, b);
340 break;
341 }
342 free_test_set (b16);
343 bitset_free (lim_use_must_malloc, b);
344 }
345 }
346 }
347
348 /* functions that operate on a bitset and index */
349 {
350 int contents_fn;
351
352 for (contents_fn = 0; contents_fns [contents_fn]; ++contents_fn)
353 {
354 int index_fn;
355
356 for (index_fn = 0; index_fns [index_fn]; ++index_fn)
357 {
358 enum bitset_n_fn
359 {
360 is_member,
361 adjoin,
362 remove,
363 toggle,
364 max_bitset_n_fn = toggle
365 } fn;
366
367 for (fn = 0; fn <= max_bitset_n_fn; ++fn)
368 {
369 bitset b;
370 bits b16;
371 int n;
372
373 ++test_no;
374 b = contents_fns[contents_fn] ();
375 b16 = make_test_set (b);
376 n = index_fns[index_fn] ();
377
378 switch (fn)
379 {
380 default:
381 panic ("missing test fn");
382 case is_member:
383 if (bitset_is_member (b, n) != bits_is_member (b16, n))
384 panic ("bitset_is_member test failed");
385 break;
386 case adjoin:
387 bitset_adjoin (b, n);
388 bits_adjoin (b16, n);
389 compare_test_result (b16, b);
390 break;
391 case remove:
392 bitset_remove (b, n);
393 bits_remove (b16, n);
394 compare_test_result (b16, b);
395 break;
396 case toggle:
397 bitset_toggle (b, n);
398 bits_toggle (b16, n);
399 compare_test_result (b16, b);
400 break;
401 }
402 free_test_set (b16);
403 bitset_free (lim_use_must_malloc, b);
404 }
405 }
406 }
407 }
408
409 /* functions that operate on a bitset and range */
410 {
411 int contents_fn;
412
413 for (contents_fn = 0; contents_fns [contents_fn]; ++contents_fn)
414 {
415 int range_fn;
416
417 for (range_fn = 0; range_fns [range_fn]; ++range_fn)
418 {
419 enum bitset_range_fn
420 {
421 is_empty_range,
422 is_full_range,
423 clear_range,
424 fill_range,
425 population_range,
426 ffs_range,
427 ffc_range,
428 max_bitset_range_fn = ffc_range
429 } fn;
430
431 for (fn = 0; fn <= max_bitset_range_fn; ++fn)
432 {
433 bitset b;
434 bits b16;
435 int from;
436 int to;
437
438 ++test_no;
439 b = contents_fns[contents_fn]();
440 b16 = make_test_set (b);
441 range_fns[range_fn] (&from, &to);
442
443 switch (fn)
444 {
445 default:
446 panic ("missing test fn");
447 case is_empty_range:
448 if (bitset_is_empty_range (b, from, to) != bits_is_empty_range (b16, from, to))
449 panic ("bitset_is_empty_range test failed");
450 break;
451 case is_full_range:
452 if (bitset_is_full_range (b, from, to) != bits_is_full_range (b16, from, to))
453 panic ("bitset_is_empty_range test failed");
454 break;
455 case population_range:
456 if (bitset_population_range (b, from, to) != bits_population_range (b16, from, to))
457 panic ("bitset_population_range test failed");
458 break;
459 case ffs_range:
460 if (bitset_ffs_range (b, from, to) != bits_ffs_range (b16, from, to))
461 panic ("bitset_ffs_range test failed");
462 break;
463 case ffc_range:
464 if (bitset_ffc_range (b, from, to) != bits_ffc_range (b16, from, to))
465 panic ("bitset_ffc_range test failed");
466 break;
467 case clear_range:
468 bitset_clear_range (b, from, to);
469 bits_clear_range (b16, from, to);
470 compare_test_result (b16, b);
471 break;
472 case fill_range:
473 bitset_fill_range (b, from, to);
474 bits_fill_range (b16, from, to);
475 compare_test_result (b16, b);
476 break;
477 }
478 free_test_set (b16);
479 bitset_free (lim_use_must_malloc, b);
480 }
481 }
482 }
483 }
484
485 /*
486 * two_bitsets;
487 */
488 {
489 int contents_fn_a;
490
491 for (contents_fn_a = 0; contents_fns [contents_fn_a]; ++contents_fn_a)
492 {
493 int contents_fn_b;
494
495 for (contents_fn_b = 0; contents_fns [contents_fn_b]; ++contents_fn_b)
496 {
497 enum two_bitsets_fn
498 {
499 is_equal,
500 is_subset,
501 assign,
502 union_,
503 intersection,
504 difference,
505 revdifference,
506 xor,
507 max_two_bitsets_fn = xor
508 } fn;
509
510 for (fn = 0; fn <= max_two_bitsets_fn; ++fn)
511 {
512 bitset a;
513 bitset b;
514 bits a16;
515 bits b16;
516
517 ++test_no;
518 a = contents_fns[contents_fn_a]();
519 b = contents_fns[contents_fn_b]();
520 a16 = make_test_set (a);
521 b16 = make_test_set (b);
522
523 switch (fn)
524 {
525 default:
526 panic ("missing test fn");
527 case is_equal:
528 if (!(bitset_is_equal (65536, a, b) == bits_is_equal (a16, b16)))
529 panic ("bitset_is_equal test failed");
530 break;
531 case is_subset:
532 if (!(bitset_is_subset (65536, a, b) == bits_is_subset (a16, b16)))
533 panic ("bitset_is_subset test failed");
534 break;
535 case assign:
536 bitset_assign (65536, a, b);
537 bits_assign (a16, b16);
538 compare_test_result (a16, a);
539 break;
540 case union_:
541 bitset_union (65536, a, b);
542 bits_union (a16, b16);
543 compare_test_result (a16, a);
544 break;
545 case intersection:
546 bitset_intersection (65536, a, b);
547 bits_intersection (a16, b16);
548 compare_test_result (a16, a);
549 break;
550 case difference:
551 bitset_difference (65536, a, b);
552 bits_difference (a16, b16);
553 compare_test_result (a16, a);
554 break;
555 case revdifference:
556 bitset_revdifference (65536, a, b);
557 bits_revdifference (a16, b16);
558 compare_test_result (a16, a);
559 break;
560 case xor:
561 bitset_xor (65536, a, b);
562 bits_xor (a16, b16);
563 compare_test_result (a16, a);
564 break;
565 }
566 free_test_set (a16);
567 free_test_set (b16);
568 bitset_free (lim_use_must_malloc, a);
569 bitset_free (lim_use_must_malloc, b);
570 }
571 }
572 }
573 }
574 }
575 safe_printfmt (1, "completed %d tests\n", test_no);
576 return 0;
577 }
578
579