/* unit-bitset-tree.c - test bitset-tree.c
*
****************************************************************
* Copyright (C) 2000 Thomas Lord
*
* See the file "COPYING" for further information about
* the copyright and warranty status of this work.
*/
#include "hackerlab/char/str.h"
#include "hackerlab/bitsets/bitset-tree.h"
#include "hackerlab/cmd/main.h"
static t_uchar * program_name = "unit-bitset-tree";
static t_uchar * usage = "[options]";
static t_uchar * version_string = "1.0";
#define OPTS(OP, OP2) \
OP (opt_help_msg, "h", "help", 0, \
"Display a help message and exit.") \
OP (opt_version, "V", "version", 0, \
"Display a release identifier string") \
OP2 (opt_version, 0, 0, 0, "and exit.") \
OP (opt_iterations, "i", "iterations n", 1, \
"Run all tests `n' times.")
enum options
{
OPTS (OPT_ENUM, OPT_IGN)
};
struct opt_desc opts[] =
{
OPTS (OPT_DESC, OPT_DESC)
{-1, 0, 0, 0, 0}
};
#if 1
struct bits_tree_rule rules[] = {{16, 256*16, 12, 0xfff}, {16, 256, 0, 0}, {0, 256, 0, 0}};
#else
struct bits_tree_rule rules[] = {{256, 256, 8, 0xff}, {0, 256, 0, 0}};
#endif
static bits_tree
make_test_set (bitset members)
{
bits_tree answer;
int x;
answer = bits_tree_alloc (0, rules);
for (x = 0; x < 65536; ++x)
if (bitset_is_member (members, x))
bits_tree_adjoin (0, rules, answer, x);
bits_tree_compact (0, rules, answer);
return answer;
}
static int test_no = 0;
static int
compare_test_result (bits_tree test_answer, bitset answer)
{
int x;
for (x = 0; x < 65536; ++x)
if (bitset_is_member (answer, x) != bits_tree_is_member (0, rules, test_answer, x))
panic ("test failed");
bits_tree_compact (0, rules, test_answer);
for (x = 0; x < 65536; ++x)
if (bitset_is_member (answer, x) != bits_tree_is_member (0, rules, test_answer, x))
panic ("test failed");
return 1;
}
static void
free_test_set (bits_tree b)
{
bits_tree_free (0, rules, b);
}
static bitset
make_empty_bitset (void)
{
return bitset_alloc (lim_use_must_malloc, 65536);
}
static bitset
make_full_bitset (void)
{
bitset b;
b = bitset_alloc (lim_use_must_malloc, 65536);
bitset_fill (65536, b);
return b;
}
static bitset
make_random_bitset (void)
{
bitset b;
int x;
b = bitset_alloc (lim_use_must_malloc, 65536);
for (x = 0; x < 65536; ++x)
if (random () & 1)
bitset_adjoin (b, x);
return b;
}
static bitset (*contents_fns[])(void) =
{
make_empty_bitset,
make_full_bitset,
make_random_bitset,
0
};
static int
make_zero_index (void)
{
return 0;
}
static int
make_max_index (void)
{
return 65535;
}
static int
make_random_index (void)
{
return random () % 65536;
}
static int (*index_fns[])(void) =
{
make_zero_index,
make_max_index,
make_random_index,
0
};
static void
make_full_range (int * from, int * to)
{
*from = 0;
*to = 65536;
}
static void
make_empty_range (int * from, int * to)
{
*from = random () % 65537;
if (!*from)
*to = 0;
else
*to = random () % *from;
}
static void
make_small_random_range (int * from, int * to)
{
*from = random () % (65536 - 256);
*to = *from + random () % 256;
}
static void
make_medium_random_range (int * from, int * to)
{
*from = random () % (65536 - 256);
*to = *from + random () % 256;
}
static void
make_large_random_range (int * from, int * to)
{
*to = 1024 + (random () % (65537 - 1024));
*from = random () % (*to - 768);
}
static void
make_tail_range (int * from, int * to)
{
*from = random () % 65537;
*to = 65536;
}
static void
make_head_range (int * from, int * to)
{
*from = 0;
*to = random () % 65537;
}
static void (*range_fns[])(int *, int *) =
{
make_full_range,
make_empty_range,
make_small_random_range,
make_medium_random_range,
make_large_random_range,
make_tail_range,
make_head_range,
0
};
int
main (int argc, char * argv[])
{
int errn;
int o;
struct opt_parsed * option;
int iterations;
option = 0;
iterations = 1;
while (1)
{
o = opt_standard (lim_use_must_malloc, &option, opts, &argc, argv, program_name, usage, version_string, 0, opt_help_msg, opt_none, opt_version);
if (o == opt_none)
break;
switch (o)
{
default:
safe_printfmt (2, "unhandled option `%s'\n", option->opt_string);
panic ("internal error parsing arguments");
usage_error:
opt_usage (2, argv[0], program_name, usage, 1);
panic_exit ();
bogus_arg:
safe_printfmt (2, "ill-formed argument for `%s' (`%s')\n", option->opt_string, option->arg_string);
goto usage_error;
case opt_iterations:
if (cvt_decimal_to_uint (&errn, &iterations, option->arg_string, str_length (option->arg_string)))
goto bogus_arg;
break;
}
}
while (iterations--)
{
/* functions that operate on a bitset */
{
int contents_fn;
for (contents_fn = 0; contents_fns [contents_fn]; ++contents_fn)
{
enum bitset_fn
{
is_empty,
is_full,
population,
clear,
fill,
complement,
ffs,
ffc,
max_bitset_fn = ffc
} fn;
for (fn = 0; fn <= max_bitset_fn; ++fn)
{
bitset b;
bits_tree b16;
++test_no;
b = contents_fns[contents_fn]();
b16 = make_test_set (b);
switch (fn)
{
default:
panic ("missing test fn");
case is_empty:
if (!(bitset_is_empty (65536, b) == bits_tree_is_empty (0, rules, b16)))
panic ("bitset_is_empty test failed");
break;
case is_full:
if (!(bitset_is_full (65536, b) == bits_tree_is_full (0, rules, b16)))
panic ("bitset_is_full test failed");
break;
case population:
if (!(bitset_population (65536, b) == bits_tree_population (0, rules, b16)))
panic ("bitset_population test failed");
break;
case ffs:
if (!(bitset_ffs (65536, b) == bits_tree_ffs (0, rules, b16)))
panic ("bitset_ffs test failed");
break;
case ffc:
if (!(bitset_ffc (65536, b) == bits_tree_ffc (0, rules, b16)))
panic ("bitset_ffc test failed");
break;
case clear:
bitset_clear (65536, b);
bits_tree_clear (0, rules, b16);
compare_test_result (b16, b);
break;
case fill:
bitset_fill (65536, b);
bits_tree_fill (0, rules, b16);
compare_test_result (b16, b);
break;
case complement:
bitset_complement (65536, b);
bits_tree_complement (0, rules, b16);
compare_test_result (b16, b);
break;
}
free_test_set (b16);
bitset_free (lim_use_must_malloc, b);
}
}
}
/* functions that operate on a bitset and index */
{
int contents_fn;
for (contents_fn = 0; contents_fns [contents_fn]; ++contents_fn)
{
int index_fn;
for (index_fn = 0; index_fns [index_fn]; ++index_fn)
{
enum bitset_n_fn
{
is_member,
adjoin,
remove,
toggle,
max_bitset_n_fn = toggle
} fn;
for (fn = 0; fn <= max_bitset_n_fn; ++fn)
{
bitset b;
bits_tree b16;
int n;
++test_no;
b = contents_fns[contents_fn] ();
b16 = make_test_set (b);
n = index_fns[index_fn] ();
switch (fn)
{
default:
panic ("missing test fn");
case is_member:
if (bitset_is_member (b, n) != bits_tree_is_member (0, rules, b16, n))
panic ("bitset_is_member test failed");
break;
case adjoin:
bitset_adjoin (b, n);
bits_tree_adjoin (0, rules, b16, n);
compare_test_result (b16, b);
break;
case remove:
bitset_remove (b, n);
bits_tree_remove (0, rules, b16, n);
compare_test_result (b16, b);
break;
case toggle:
bitset_toggle (b, n);
bits_tree_toggle (0, rules, b16, n);
compare_test_result (b16, b);
break;
}
free_test_set (b16);
bitset_free (lim_use_must_malloc, b);
}
}
}
}
/* functions that operate on a bitset and range */
{
int contents_fn;
for (contents_fn = 0; contents_fns [contents_fn]; ++contents_fn)
{
int range_fn;
for (range_fn = 0; range_fns [range_fn]; ++range_fn)
{
enum bitset_range_fn
{
is_empty_range,
is_full_range,
clear_range,
fill_range,
population_range,
ffs_range,
ffc_range,
max_bitset_range_fn = ffc_range
} fn;
for (fn = 0; fn <= max_bitset_range_fn; ++fn)
{
bitset b;
bits_tree b16;
int from;
int to;
++test_no;
b = contents_fns[contents_fn]();
b16 = make_test_set (b);
range_fns[range_fn] (&from, &to);
switch (fn)
{
default:
panic ("missing test fn");
case is_empty_range:
if (bitset_is_empty_range (b, from, to) != bits_tree_is_empty_range (0, rules, b16, from, to))
panic ("bitset_is_empty_range test failed");
break;
case is_full_range:
if (bitset_is_full_range (b, from, to) != bits_tree_is_full_range (0, rules, b16, from, to))
panic ("bitset_is_empty_range test failed");
break;
case population_range:
if (bitset_population_range (b, from, to) != bits_tree_population_range (0, rules, b16, from, to))
panic ("bitset_population_range test failed");
break;
case ffs_range:
if (bitset_ffs_range (b, from, to) != bits_tree_ffs_range (0, rules, b16, from, to))
panic ("bitset_ffs_range test failed");
break;
case ffc_range:
if (bitset_ffc_range (b, from, to) != bits_tree_ffc_range (0, rules, b16, from, to))
panic ("bitset_ffc_range test failed");
break;
case clear_range:
bitset_clear_range (b, from, to);
bits_tree_clear_range (0, rules, b16, from, to);
compare_test_result (b16, b);
break;
case fill_range:
bitset_fill_range (b, from, to);
bits_tree_fill_range (0, rules, b16, from, to);
compare_test_result (b16, b);
break;
}
free_test_set (b16);
bitset_free (lim_use_must_malloc, b);
}
}
}
}
/*
* two_bitsets;
*/
{
int contents_fn_a;
for (contents_fn_a = 0; contents_fns [contents_fn_a]; ++contents_fn_a)
{
int contents_fn_b;
for (contents_fn_b = 0; contents_fns [contents_fn_b]; ++contents_fn_b)
{
enum two_bitsets_fn
{
is_equal,
is_subset,
assign,
union_,
intersection,
difference,
revdifference,
xor,
max_two_bitsets_fn = xor
} fn;
for (fn = 0; fn <= max_two_bitsets_fn; ++fn)
{
bitset a;
bitset b;
bits_tree a16;
bits_tree b16;
++test_no;
a = contents_fns[contents_fn_a]();
b = contents_fns[contents_fn_b]();
a16 = make_test_set (a);
b16 = make_test_set (b);
switch (fn)
{
default:
panic ("missing test fn");
case is_equal:
if (!(bitset_is_equal (65536, a, b) == bits_tree_is_equal (0, rules, a16, b16)))
panic ("bitset_is_equal test failed");
break;
case is_subset:
if (!(bitset_is_subset (65536, a, b) == bits_tree_is_subset (0, rules, a16, b16)))
panic ("bitset_is_subset test failed");
break;
case assign:
bitset_assign (65536, a, b);
bits_tree_assign (0, rules, a16, b16);
compare_test_result (a16, a);
break;
case union_:
bitset_union (65536, a, b);
bits_tree_union (0, rules, a16, b16);
compare_test_result (a16, a);
break;
case intersection:
bitset_intersection (65536, a, b);
bits_tree_intersection (0, rules, a16, b16);
compare_test_result (a16, a);
break;
case difference:
bitset_difference (65536, a, b);
bits_tree_difference (0, rules, a16, b16);
compare_test_result (a16, a);
break;
case revdifference:
bitset_revdifference (65536, a, b);
bits_tree_revdifference (0, rules, a16, b16);
compare_test_result (a16, a);
break;
case xor:
bitset_xor (65536, a, b);
bits_tree_xor (0, rules, a16, b16);
compare_test_result (a16, a);
break;
}
free_test_set (a16);
free_test_set (b16);
bitset_free (lim_use_must_malloc, a);
bitset_free (lim_use_must_malloc, b);
}
}
}
}
}
safe_printfmt (1, "completed %d tests\n", test_no);
return 0;
}
syntax highlighted by Code2HTML, v. 0.9.1