#include <stdlib.h>
#include "cunit/cyrunit.h"
#include "bitvector.h"
#include "util.h"
static void test_free(void)
{
bitvector_t bv = BV_INITIALIZER;
/* it's ok to call free() even if we never
* set or cleared any bits */
bv_fini(&bv);
}
static void test_basic(void)
{
bitvector_t bv = BV_INITIALIZER;
/* read-only operations do not expand the vector */
CU_ASSERT_EQUAL(0, bv.length);
CU_ASSERT_EQUAL(0, bv.alloc);
CU_ASSERT_EQUAL(0, bv_isset(&bv, 0));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 7));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 23));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 104));
CU_ASSERT_EQUAL(0, bv.length);
CU_ASSERT_EQUAL(0, bv.alloc);
/* can set bit0 and get it back */
bv_set(&bv, 0);
CU_ASSERT_EQUAL(1, bv.length);
CU_ASSERT_EQUAL(0, bv.alloc);
CU_ASSERT_EQUAL(1, bv_isset(&bv, 0));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 7));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 23));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 104));
CU_ASSERT_EQUAL(1, bv.length);
CU_ASSERT_EQUAL(0, bv.alloc);
/* can set bit23 and get it back */
bv_set(&bv, 23);
CU_ASSERT_EQUAL(24, bv.length);
CU_ASSERT_EQUAL(0, bv.alloc);
CU_ASSERT_EQUAL(1, bv_isset(&bv, 0));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 7));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 23));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 104));
CU_ASSERT_EQUAL(24, bv.length);
CU_ASSERT_EQUAL(0, bv.alloc);
/* can set all bits, does not change length */
bv_setall(&bv);
CU_ASSERT_EQUAL(24, bv.length);
CU_ASSERT_EQUAL(0, bv.alloc);
CU_ASSERT_EQUAL(1, bv_isset(&bv, 0));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 7));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 23));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 104));
CU_ASSERT_EQUAL(24, bv.length);
CU_ASSERT_EQUAL(0, bv.alloc);
/* can clear all bits, does not change length */
bv_clearall(&bv);
CU_ASSERT_EQUAL(24, bv.length);
CU_ASSERT_EQUAL(0, bv.alloc);
CU_ASSERT_EQUAL(0, bv_isset(&bv, 0));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 7));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 23));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 104));
CU_ASSERT_EQUAL(24, bv.length);
CU_ASSERT_EQUAL(0, bv.alloc);
/* can set the size, does not change existing bits */
bv_set(&bv, 0);
bv_set(&bv, 23);
bv_setsize(&bv, 105);
CU_ASSERT_EQUAL(105, bv.length);
CU_ASSERT_NOT_EQUAL(0, bv.alloc);
CU_ASSERT_EQUAL(1, bv_isset(&bv, 0));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 7));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 23));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 104));
CU_ASSERT_EQUAL(105, bv.length);
CU_ASSERT_NOT_EQUAL(0, bv.alloc);
/* bits are now heap-allocated */
/* can set bit63 and get it back */
bv_set(&bv, 63);
CU_ASSERT_EQUAL(105, bv.length);
CU_ASSERT_NOT_EQUAL(0, bv.alloc);
CU_ASSERT_EQUAL(1, bv_isset(&bv, 0));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 7));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 23));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 63));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 104));
CU_ASSERT_EQUAL(105, bv.length);
CU_ASSERT_NOT_EQUAL(0, bv.alloc);
/* setall now works on the new size */
bv_setall(&bv);
CU_ASSERT_EQUAL(105, bv.length);
CU_ASSERT_NOT_EQUAL(0, bv.alloc);
CU_ASSERT_EQUAL(1, bv_isset(&bv, 0));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 7));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 23));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 104));
CU_ASSERT_EQUAL(105, bv.length);
CU_ASSERT_NOT_EQUAL(0, bv.alloc);
/* can set all bits, does not change length */
bv_setall(&bv);
CU_ASSERT_EQUAL(105, bv.length);
CU_ASSERT_NOT_EQUAL(0, bv.alloc);
CU_ASSERT_EQUAL(1, bv_isset(&bv, 0));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 7));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 23));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 104));
CU_ASSERT_EQUAL(105, bv.length);
CU_ASSERT_NOT_EQUAL(0, bv.alloc);
/* can clear all bits, does not change length */
bv_clearall(&bv);
CU_ASSERT_EQUAL(105, bv.length);
CU_ASSERT_NOT_EQUAL(0, bv.alloc);
CU_ASSERT_EQUAL(0, bv_isset(&bv, 0));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 7));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 23));
CU_ASSERT_EQUAL(0, bv_isset(&bv, 104));
CU_ASSERT_EQUAL(105, bv.length);
CU_ASSERT_NOT_EQUAL(0, bv.alloc);
bv_fini(&bv);
}
static void test_andeq(void)
{
bitvector_t a = BV_INITIALIZER;
bitvector_t b = BV_INITIALIZER;
bv_set(&a, 0);
bv_set(&a, 3);
CU_ASSERT_EQUAL(4, a.length);
CU_ASSERT_EQUAL(1, bv_isset(&a, 0));
CU_ASSERT_EQUAL(1, bv_isset(&a, 3));
bv_set(&b, 0);
bv_set(&b, 23);
CU_ASSERT_EQUAL(24, b.length);
CU_ASSERT_EQUAL(1, bv_isset(&b, 0));
CU_ASSERT_EQUAL(1, bv_isset(&b, 23));
bv_andeq(&a, &b);
CU_ASSERT_EQUAL(24, a.length);
CU_ASSERT_EQUAL(1, bv_isset(&a, 0));
CU_ASSERT_EQUAL(0, bv_isset(&a, 3));
CU_ASSERT_EQUAL(0, bv_isset(&a, 23));
bv_fini(&a);
bv_fini(&b);
}
static void test_andeq_noexpand(void)
{
bitvector_t a = BV_INITIALIZER;
bitvector_t b = BV_INITIALIZER;
bv_set(&a, 0);
bv_set(&a, 23);
CU_ASSERT_EQUAL(24, a.length);
CU_ASSERT_EQUAL(1, bv_isset(&a, 0));
CU_ASSERT_EQUAL(1, bv_isset(&a, 23));
bv_set(&b, 0);
bv_set(&b, 3);
bv_set(&b, 7);
CU_ASSERT_EQUAL(8, b.length);
CU_ASSERT_EQUAL(1, bv_isset(&b, 0));
CU_ASSERT_EQUAL(1, bv_isset(&b, 3));
CU_ASSERT_EQUAL(1, bv_isset(&b, 7));
bv_andeq(&a, &b);
CU_ASSERT_EQUAL(24, a.length);
CU_ASSERT_EQUAL(1, bv_isset(&a, 0));
CU_ASSERT_EQUAL(0, bv_isset(&a, 3));
CU_ASSERT_EQUAL(0, bv_isset(&a, 7));
CU_ASSERT_EQUAL(0, bv_isset(&a, 23));
bv_fini(&a);
bv_fini(&b);
}
static void test_oreq(void)
{
bitvector_t a = BV_INITIALIZER;
bitvector_t b = BV_INITIALIZER;
bv_set(&a, 0);
bv_set(&a, 3);
CU_ASSERT_EQUAL(4, a.length);
CU_ASSERT_EQUAL(1, bv_isset(&a, 0));
CU_ASSERT_EQUAL(1, bv_isset(&a, 3));
bv_set(&b, 0);
bv_set(&b, 23);
CU_ASSERT_EQUAL(24, b.length);
CU_ASSERT_EQUAL(1, bv_isset(&b, 0));
CU_ASSERT_EQUAL(1, bv_isset(&b, 23));
bv_oreq(&a, &b);
CU_ASSERT_EQUAL(24, a.length);
CU_ASSERT_EQUAL(1, bv_isset(&a, 0));
CU_ASSERT_EQUAL(1, bv_isset(&a, 3));
CU_ASSERT_EQUAL(1, bv_isset(&a, 23));
bv_fini(&a);
bv_fini(&b);
}
static void test_oreq_empty(void)
{
bitvector_t a = BV_INITIALIZER;
bitvector_t b = BV_INITIALIZER;
bv_set(&b, 0);
bv_set(&b, 23);
CU_ASSERT_EQUAL(24, b.length);
CU_ASSERT_EQUAL(1, bv_isset(&b, 0));
CU_ASSERT_EQUAL(1, bv_isset(&b, 23));
bv_oreq(&a, &b);
CU_ASSERT_EQUAL(24, a.length);
CU_ASSERT_EQUAL(1, bv_isset(&a, 0));
CU_ASSERT_EQUAL(1, bv_isset(&a, 23));
bv_fini(&a);
bv_fini(&b);
}
static void test_oreq_noexpand(void)
{
bitvector_t a = BV_INITIALIZER;
bitvector_t b = BV_INITIALIZER;
bv_set(&a, 0);
bv_set(&a, 23);
CU_ASSERT_EQUAL(24, a.length);
CU_ASSERT_EQUAL(1, bv_isset(&a, 0));
CU_ASSERT_EQUAL(1, bv_isset(&a, 23));
bv_set(&b, 0);
bv_set(&b, 3);
CU_ASSERT_EQUAL(4, b.length);
CU_ASSERT_EQUAL(1, bv_isset(&b, 0));
CU_ASSERT_EQUAL(1, bv_isset(&b, 3));
bv_oreq(&a, &b);
CU_ASSERT_EQUAL(24, a.length);
CU_ASSERT_EQUAL(1, bv_isset(&a, 0));
CU_ASSERT_EQUAL(1, bv_isset(&a, 3));
CU_ASSERT_EQUAL(1, bv_isset(&a, 23));
bv_fini(&a);
bv_fini(&b);
}
static void test_shrink_expand(void)
{
bitvector_t bv = BV_INITIALIZER;
int i;
/* set up some bits */
bv_setsize(&bv, 59);
bv_setall(&bv);
CU_ASSERT_EQUAL(59, bv.length);
CU_ASSERT_EQUAL(1, bv_isset(&bv, 0));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 3));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 4));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 23));
CU_ASSERT_EQUAL(1, bv_isset(&bv, 58));
for (i = 55 ; i >= 4 ; i--) {
/* explicitly shrink the vector - bits off
* the end are now gone */
bv_setsize(&bv, i);
CU_ASSERT_EQUAL(i, bv.length);
CU_ASSERT_EQUAL(1, bv_isset(&bv, i-2));
CU_ASSERT_EQUAL(1, bv_isset(&bv, i-1));
CU_ASSERT_EQUAL(0, bv_isset(&bv, i));
CU_ASSERT_EQUAL(0, bv_isset(&bv, i+1));
CU_ASSERT_EQUAL(0, bv_isset(&bv, i+2));
/* implicitly expand the vector - old bits
* do not come back */
bv_set(&bv, 58);
CU_ASSERT_EQUAL(59, bv.length);
CU_ASSERT_EQUAL(1, bv_isset(&bv, 0));
CU_ASSERT_EQUAL(1, bv_isset(&bv, i-2));
CU_ASSERT_EQUAL(1, bv_isset(&bv, i-1));
CU_ASSERT_EQUAL(0, bv_isset(&bv, i));
CU_ASSERT_EQUAL(0, bv_isset(&bv, i+1));
CU_ASSERT_EQUAL(0, bv_isset(&bv, i+2));
bv_setall(&bv);
}
bv_fini(&bv);
}
static void test_copy(void)
{
bitvector_t dst = BV_INITIALIZER;
bitvector_t src = BV_INITIALIZER;
/* test copying of empty sets */
bv_copy(&dst, &src);
CU_ASSERT_EQUAL(0, dst.length);
/* set up some bits */
bv_set(&src, 0);
bv_set(&src, 11);
bv_set(&src, 23);
CU_ASSERT_EQUAL(24, src.length);
CU_ASSERT_EQUAL(1, bv_isset(&src, 0));
CU_ASSERT_EQUAL(0, bv_isset(&src, 1));
CU_ASSERT_EQUAL(0, bv_isset(&src, 10));
CU_ASSERT_EQUAL(1, bv_isset(&src, 11));
CU_ASSERT_EQUAL(0, bv_isset(&src, 12));
CU_ASSERT_EQUAL(0, bv_isset(&src, 22));
CU_ASSERT_EQUAL(1, bv_isset(&src, 23));
CU_ASSERT_EQUAL(0, bv_isset(&src, 24));
/* copy and check the bits are now in both */
bv_copy(&dst, &src);
CU_ASSERT_EQUAL(24, dst.length);
CU_ASSERT_EQUAL(1, bv_isset(&dst, 0));
CU_ASSERT_EQUAL(0, bv_isset(&dst, 1));
CU_ASSERT_EQUAL(0, bv_isset(&dst, 10));
CU_ASSERT_EQUAL(1, bv_isset(&dst, 11));
CU_ASSERT_EQUAL(0, bv_isset(&dst, 12));
CU_ASSERT_EQUAL(0, bv_isset(&dst, 22));
CU_ASSERT_EQUAL(1, bv_isset(&dst, 23));
CU_ASSERT_EQUAL(0, bv_isset(&dst, 24));
CU_ASSERT_EQUAL(24, src.length);
CU_ASSERT_EQUAL(1, bv_isset(&src, 0));
CU_ASSERT_EQUAL(0, bv_isset(&src, 1));
CU_ASSERT_EQUAL(0, bv_isset(&src, 10));
CU_ASSERT_EQUAL(1, bv_isset(&src, 11));
CU_ASSERT_EQUAL(0, bv_isset(&src, 12));
CU_ASSERT_EQUAL(0, bv_isset(&src, 22));
CU_ASSERT_EQUAL(1, bv_isset(&src, 23));
CU_ASSERT_EQUAL(0, bv_isset(&src, 24));
bv_fini(&dst);
bv_fini(&src);
}
static void test_cstring(void)
{
bitvector_t bv = BV_INITIALIZER;
char *s;
/* test empty set */
s = bv_cstring(&bv);
CU_ASSERT_STRING_EQUAL(s, "[]");
free(s);
/* set a bit */
bv_set(&bv, 11);
s = bv_cstring(&bv);
CU_ASSERT_STRING_EQUAL(s, "0008[11]");
free(s);
/* set another bit, not adjacent */
bv_set(&bv, 3);
s = bv_cstring(&bv);
CU_ASSERT_STRING_EQUAL(s, "0808[3,11]");
free(s);
/* set another bit, adjacent */
bv_clear(&bv, 3);
bv_set(&bv, 10);
s = bv_cstring(&bv);
CU_ASSERT_STRING_EQUAL(s, "000c[10-11]");
free(s);
/* set more bits, adjacent */
bv_set(&bv, 9);
bv_set(&bv, 12);
s = bv_cstring(&bv);
CU_ASSERT_STRING_EQUAL(s, "001e[9-12]");
free(s);
/* set a bit at the start */
bv_clearall(&bv);
bv_set(&bv, 0);
s = bv_cstring(&bv);
CU_ASSERT_STRING_EQUAL(s, "0100[0]");
free(s);
/* set another bit adjacent to the start */
bv_set(&bv, 1);
s = bv_cstring(&bv);
CU_ASSERT_STRING_EQUAL(s, "0300[0-1]");
free(s);
/* set every 2nd bit */
bv_clearall(&bv);
bv_set(&bv, 1);
bv_set(&bv, 3);
bv_set(&bv, 5);
bv_set(&bv, 7);
bv_set(&bv, 9);
bv_set(&bv, 11);
s = bv_cstring(&bv);
CU_ASSERT_STRING_EQUAL(s, "aa0a[1,3,5,7,9,11]");
free(s);
bv_fini(&bv);
}
static void test_next_set(void)
{
#define TESTCASE(...) \
{ \
static const int _in[] = {__VA_ARGS__}; \
bitvector_t bv = BV_INITIALIZER; \
int bit = -1; \
int i; \
for (i = 0 ; i < (int)VECTOR_SIZE(_in) ; i++) \
bv_set(&bv, _in[i]); \
for (i = 0 ; i < (int)VECTOR_SIZE(_in) ; i++) { \
bit = bv_next_set(&bv, bit+1); \
CU_ASSERT_EQUAL(bit, _in[i]); \
} \
bit = bv_next_set(&bv, bit+1); \
CU_ASSERT_EQUAL(bit, -1); \
bv_fini(&bv); \
}
/* empty vector never reports any set bits */
TESTCASE();
/* vector with a single bit reports only that bit */
TESTCASE(0);
TESTCASE(3);
TESTCASE(7);
TESTCASE(8);
TESTCASE(15);
TESTCASE(16);
TESTCASE(128);
/* vector with several bits reports them all */
TESTCASE(1,2,3,4,7,11,12,63,64,65);
/* vector with all bits reports them all */
TESTCASE(0,1,2,3,4,5,6,7);
TESTCASE(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15);
TESTCASE(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23);
#undef TESTCASE
}
static void test_prev_set(void)
{
#define TESTCASE(...) \
{ \
static const int _in[] = {__VA_ARGS__}; \
bitvector_t bv = BV_INITIALIZER; \
int bit; \
int i; \
for (i = 0 ; i < (int)VECTOR_SIZE(_in) ; i++) \
bv_set(&bv, _in[i]); \
bit = bv.length; \
for (i = (int)VECTOR_SIZE(_in)-1 ; i >= 0 ; i--) { \
bit = bv_prev_set(&bv, bit-1); \
CU_ASSERT_EQUAL(bit, _in[i]); \
} \
bit = bv_prev_set(&bv, bit-1); \
CU_ASSERT_EQUAL(bit, -1); \
bv_fini(&bv); \
}
/* empty vector never reports any set bits */
TESTCASE();
/* vector with a single bit reports only that bit */
TESTCASE(0);
TESTCASE(3);
TESTCASE(7);
TESTCASE(8);
TESTCASE(15);
TESTCASE(16);
TESTCASE(128);
/* vector with several bits reports them all */
TESTCASE(1,2,3,4,7,11,12,63,64,65);
/* vector with all bits reports them all */
TESTCASE(0,1,2,3,4,5,6,7);
TESTCASE(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15);
TESTCASE(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23);
#undef TESTCASE
}
static void test_count(void)
{
#define TESTCASE(...) \
{ \
static const int _in[] = {__VA_ARGS__}; \
bitvector_t bv = BV_INITIALIZER; \
int count; \
int i; \
for (i = 0 ; i < (int)VECTOR_SIZE(_in) ; i++) \
bv_set(&bv, _in[i]); \
count = bv_count(&bv); \
CU_ASSERT_EQUAL(count, VECTOR_SIZE(_in)); \
bv_fini(&bv); \
}
/* empty vector */
TESTCASE();
/* vector with a single bit */
TESTCASE(0);
TESTCASE(3);
TESTCASE(7);
TESTCASE(8);
TESTCASE(15);
TESTCASE(16);
TESTCASE(128);
/* vector with several bits */
TESTCASE(1,2,3,4,7,11,12,63,64,65);
/* vector with all bits */
TESTCASE(0,1,2,3,4,5,6,7);
TESTCASE(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15);
TESTCASE(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23);
#undef TESTCASE
}
static void test_andeq_valgrind(void)
{
bitvector_t a = BV_INITIALIZER;
bitvector_t b = BV_INITIALIZER;
bv_set(&a, 5);
bv_set(&b, 65535);
bv_set(&a, 257);
bv_set(&b, 257);
bv_andeq(&a, &b);
CU_ASSERT_EQUAL(257, bv_next_set(&a, 0));
CU_ASSERT_EQUAL(-1, bv_next_set(&a, 257+1));
bv_fini(&a);
bv_fini(&b);
}
static void test_oreq_valgrind(void)
{
bitvector_t a = BV_INITIALIZER;
bitvector_t b = BV_INITIALIZER;
bv_set(&a, 5);
bv_set(&b, 65535);
bv_set(&a, 257);
bv_set(&b, 257);
bv_oreq(&a, &b);
CU_ASSERT_EQUAL(5, bv_next_set(&a, 0));
CU_ASSERT_EQUAL(257, bv_next_set(&a, 5+1));
CU_ASSERT_EQUAL(65535, bv_next_set(&a, 257+1));
CU_ASSERT_EQUAL(-1, bv_next_set(&a, 65535+1));
bv_fini(&a);
bv_fini(&b);
}
/* vim: set ft=c: */