1/*
2 * bitset_container_unit.c
3 *
4 */
5
6#include <assert.h>
7#include <stdint.h>
8#include <stdio.h>
9#include <stdlib.h>
10
11#include <roaring/containers/bitset.h>
12#include <roaring/misc/configreport.h>
13#include <roaring/bitset_util.h>
14#include "test.h"
15
16void test_bitset_lenrange_cardinality() {
17 uint64_t words[] = {~UINT64_C(0), ~UINT64_C(0), ~UINT64_C(0), ~UINT64_C(0), 0, 0, 0, 0};
18 for(int k = 0; k < 64 * 4; k++) {
19 assert(bitset_lenrange_cardinality(words, 0, k) == k + 1); // ok
20 }
21 for(int k = 64 * 4; k < 64 * 8; k++) {
22 assert(bitset_lenrange_cardinality(words, 0, k) == 4 * 64); // ok
23 }
24}
25
26void test_bitset_compute_cardinality() {
27 // check that overflow doesn't happen
28 bitset_container_t *b = bitset_container_create();
29 bitset_container_add_from_range(b, 0, 0x10000, 1);
30 assert(bitset_container_compute_cardinality(b) == 0x10000);
31 bitset_container_free(b);
32}
33
34void printf_test() {
35 bitset_container_t* B = bitset_container_create();
36 assert_non_null(B);
37
38 bitset_container_set(B, 1U);
39 bitset_container_set(B, 2U);
40 bitset_container_set(B, 3U);
41 bitset_container_set(B, 10U);
42 bitset_container_set(B, 10000U);
43
44 bitset_container_printf(B); // does it crash?
45 printf("\n");
46
47 bitset_container_free(B);
48}
49
50void set_get_test() {
51 bitset_container_t* B = bitset_container_create();
52 assert_non_null(B);
53
54 for (size_t x = 0; x < 1 << 16; x++) {
55 assert_false(bitset_container_get(B, x));
56 }
57
58 for (size_t x = 0; x < 1 << 16; x += 3) {
59 assert_int_equal(bitset_container_cardinality(B), x / 3);
60
61 assert_false(bitset_container_get(B, x));
62 bitset_container_set(B, x);
63 assert(bitset_container_get(B, x));
64
65 assert_int_equal(bitset_container_cardinality(B), x / 3 + 1);
66 }
67
68 for (size_t x = 0; x < 1 << 16; x++) {
69 assert_int_equal(bitset_container_get(B, x), (x / 3 * 3 == x));
70 }
71
72 assert_int_equal(bitset_container_cardinality(B), (1 << 16) / 3 + 1);
73 assert_int_equal(bitset_container_compute_cardinality(B),
74 (1 << 16) / 3 + 1);
75
76 for (size_t x = 0; x < 1 << 16; x += 3) {
77 bitset_container_unset(B, x);
78 }
79
80 assert_int_equal(bitset_container_cardinality(B), 0);
81 assert_int_equal(bitset_container_compute_cardinality(B), 0);
82
83 bitset_container_free(B);
84}
85
86void and_or_test() {
87 bitset_container_t* B1 = bitset_container_create();
88 bitset_container_t* B2 = bitset_container_create();
89 bitset_container_t* BI = bitset_container_create();
90 bitset_container_t* BO = bitset_container_create();
91
92 assert_non_null(B1);
93 assert_non_null(B2);
94 assert_non_null(BI);
95 assert_non_null(BO);
96
97 for (size_t x = 0; x < (1 << 16); x += 3) {
98 bitset_container_set(B1, x);
99 bitset_container_set(BI, x);
100 }
101
102 // important: 62 is not divisible by 3
103 for (size_t x = 0; x < (1 << 16); x += 62) {
104 bitset_container_set(B2, x);
105 bitset_container_set(BI, x);
106 }
107
108 for (size_t x = 0; x < (1 << 16); x += 62 * 3) {
109 bitset_container_set(BO, x);
110 }
111
112 const int card_union = bitset_container_compute_cardinality(BI);
113 const int card_inter = bitset_container_compute_cardinality(BO);
114
115 bitset_container_and_nocard(B1, B2, BI);
116 assert_int_not_equal(bitset_container_compute_cardinality(BI), card_union);
117 assert_int_not_equal(bitset_container_and(B1, B2, BI), card_union);
118
119 bitset_container_or_nocard(B1, B2, BO);
120 assert_int_not_equal(bitset_container_compute_cardinality(BO), card_inter);
121 assert_int_not_equal(bitset_container_or(B1, B2, BO), card_inter);
122
123 bitset_container_free(B1);
124 bitset_container_free(B2);
125 bitset_container_free(BI);
126 bitset_container_free(BO);
127}
128
129void xor_test() {
130 bitset_container_t* B1 = bitset_container_create();
131 bitset_container_t* B2 = bitset_container_create();
132 bitset_container_t* BI = bitset_container_create();
133 bitset_container_t* TMP = bitset_container_create();
134
135 assert_non_null(B1);
136 assert_non_null(B2);
137 assert_non_null(BI);
138 assert_non_null(TMP);
139
140 for (size_t x = 0; x < (1 << 16); x += 3) {
141 bitset_container_set(B1, x);
142 bitset_container_set(BI, x);
143 }
144
145 // important: 62 is not divisible by 3
146 for (size_t x = 0; x < (1 << 16); x += 62) {
147 bitset_container_set(B2, x);
148 bitset_container_set(BI, x);
149 }
150
151 for (size_t x = 0; x < (1 << 16); x += 62 * 3) {
152 bitset_container_unset(BI, x);
153 }
154
155 bitset_container_xor(B1, B2, TMP);
156 assert_true(bitset_container_equals(TMP, BI));
157
158 bitset_container_free(B1);
159 bitset_container_free(B2);
160 bitset_container_free(BI);
161 bitset_container_free(TMP);
162}
163
164void andnot_test() {
165 bitset_container_t* B1 = bitset_container_create();
166 bitset_container_t* B2 = bitset_container_create();
167 bitset_container_t* BI = bitset_container_create();
168 bitset_container_t* TMP = bitset_container_create();
169
170 assert_non_null(B1);
171 assert_non_null(B2);
172 assert_non_null(BI);
173 assert_non_null(TMP);
174
175 for (size_t x = 0; x < (1 << 16); x += 3) {
176 bitset_container_set(B1, x);
177 bitset_container_set(BI, x);
178 }
179
180 // important: 62 is not divisible by 3
181 for (size_t x = 0; x < (1 << 16); x += 62) {
182 bitset_container_set(B2, x);
183 bitset_container_unset(BI, x);
184 }
185
186 const int expected = bitset_container_compute_cardinality(BI);
187
188 bitset_container_andnot_nocard(B1, B2, TMP);
189
190 assert_int_equal(expected, bitset_container_compute_cardinality(TMP));
191 assert_true(bitset_container_equals(BI, TMP));
192
193 assert_int_equal(expected, bitset_container_andnot(B1, B2, TMP));
194 assert_true(bitset_container_equals(BI, TMP));
195
196 bitset_container_free(B1);
197 bitset_container_free(B2);
198 bitset_container_free(BI);
199 bitset_container_free(TMP);
200}
201
202void to_uint32_array_test() {
203 for (size_t offset = 1; offset < 128; offset *= 2) {
204 bitset_container_t* B = bitset_container_create();
205 assert_non_null(B);
206
207 for (size_t k = 0; k < (1 << 16); k += offset) {
208 bitset_container_set(B, k);
209 }
210
211 int card = bitset_container_cardinality(B);
212
213 uint32_t* out = malloc(sizeof(uint32_t) * card);
214 assert_non_null(out);
215
216 int nc = bitset_container_to_uint32_array(out, B, 0);
217
218 assert_int_equal(card, nc);
219
220 for (int k = 1; k < nc; ++k) {
221 assert_int_equal(out[k], offset + out[k - 1]);
222 }
223
224 free(out);
225 bitset_container_free(B);
226 }
227}
228
229void select_test() {
230 bitset_container_t* B = bitset_container_create();
231 assert_non_null(B);
232 uint16_t base = 27;
233 for (uint16_t value = base; value < base + 200; value += 5) {
234 bitset_container_add(B, value);
235 }
236 uint32_t i = 0;
237 uint32_t element = 0;
238 uint32_t start_rank;
239 for (uint16_t value = base; value < base + 200; value += 5) {
240 start_rank = 12;
241 assert_true(bitset_container_select(B, &start_rank, i + 12, &element));
242 assert_int_equal(element, value);
243 i++;
244 }
245 start_rank = 12;
246 assert_false(bitset_container_select(B, &start_rank, i + 12, &element));
247 assert_int_equal(start_rank, i + 12);
248 bitset_container_free(B);
249}
250
251int main() {
252 const struct CMUnitTest tests[] = {
253 cmocka_unit_test(test_bitset_lenrange_cardinality),
254 cmocka_unit_test(printf_test), cmocka_unit_test(set_get_test),
255 cmocka_unit_test(and_or_test), cmocka_unit_test(xor_test),
256 cmocka_unit_test(andnot_test), cmocka_unit_test(to_uint32_array_test),
257 cmocka_unit_test(select_test),
258 cmocka_unit_test(test_bitset_compute_cardinality),
259 };
260
261 return cmocka_run_group_tests(tests, NULL, NULL);
262}
263