1/*
2 * mixed_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/containers.h>
12#include <roaring/containers/mixed_andnot.h>
13#include <roaring/containers/mixed_intersection.h>
14#include <roaring/containers/mixed_negation.h>
15#include <roaring/containers/mixed_union.h>
16#include <roaring/containers/mixed_xor.h>
17
18#include "test.h"
19
20//#define UNVERBOSE_MIXED_CONTAINER
21
22void array_bitset_and_or_xor_andnot_test() {
23 array_container_t* A1 = array_container_create();
24 array_container_t* A2 = array_container_create();
25 array_container_t* AI = array_container_create();
26 array_container_t* AO = array_container_create();
27 array_container_t* AX = array_container_create();
28 array_container_t* AM = array_container_create();
29 array_container_t* AM1 = array_container_create();
30 bitset_container_t* B1 = bitset_container_create();
31 bitset_container_t* B2 = bitset_container_create();
32 bitset_container_t* BI = bitset_container_create();
33 bitset_container_t* BO = bitset_container_create();
34 bitset_container_t* BX = bitset_container_create();
35 bitset_container_t* BM = bitset_container_create();
36 bitset_container_t* BM1 = bitset_container_create();
37
38 // nb, array containers will be illegally big.
39 for (int x = 0; x < (1 << 16); x += 3) {
40 array_container_add(A1, x);
41 array_container_add(AO, x);
42 bitset_container_set(B1, x);
43 bitset_container_set(BO, x);
44 }
45
46 // important: 62 is not divisible by 3
47 for (int x = 0; x < (1 << 16); x += 62) {
48 array_container_add(A2, x);
49 array_container_add(AO, x);
50 bitset_container_set(B2, x);
51 bitset_container_set(BO, x);
52 }
53
54 for (int x = 0; x < (1 << 16); x += 62 * 3) {
55 array_container_add(AI, x);
56 bitset_container_set(BI, x);
57 }
58
59 for (int x = 0; x < (1 << 16); x++) {
60 if ((x % 62 == 0) ^ (x % 3 == 0)) {
61 array_container_add(AX, x);
62 bitset_container_set(BX, x);
63 }
64 if ((x % 3 == 0) && !(x % 62 == 0)) {
65 array_container_add(AM, x);
66 bitset_container_set(BM, x);
67 }
68 if ((x % 62 == 0) && !(x % 3 == 0)) {
69 array_container_add(AM1, x);
70 bitset_container_set(BM1, x);
71 }
72 }
73 // we interleave O and I on purpose (to trigger bugs!)
74 int ci = array_container_cardinality(AI); // expected intersection
75 int co = array_container_cardinality(AO); // expected union
76 int cx = array_container_cardinality(AX); // expected xor
77 int cm = array_container_cardinality(AM); // expected minus (andNot)
78 int cm1 =
79 array_container_cardinality(AM1); // expected minus (andNot) reversed
80
81 assert_int_equal(ci, bitset_container_cardinality(BI));
82 assert_int_equal(co, bitset_container_cardinality(BO));
83
84 array_container_intersection(A1, A2, AI);
85 array_container_union(A1, A2, AO);
86 array_container_xor(A1, A2, AX);
87 array_container_andnot(A1, A2, AM);
88 array_container_andnot(A2, A1, AM1);
89 bitset_container_intersection(B1, B2, BI);
90 bitset_container_union(B1, B2, BO);
91 bitset_container_xor(B1, B2, BX);
92 bitset_container_andnot(B1, B2, BM);
93 bitset_container_andnot(B2, B1, BM1);
94
95 assert_int_equal(ci, bitset_container_cardinality(BI));
96 assert_int_equal(co, bitset_container_cardinality(BO));
97 assert_int_equal(cx, bitset_container_cardinality(BX));
98 assert_int_equal(cm, bitset_container_cardinality(BM));
99 assert_int_equal(cm1, bitset_container_cardinality(BM1));
100 assert_int_equal(ci, array_container_cardinality(AI));
101 assert_int_equal(co, array_container_cardinality(AO));
102 assert_int_equal(cx, array_container_cardinality(AX));
103 assert_int_equal(cm, array_container_cardinality(AM));
104 assert_int_equal(cm1, array_container_cardinality(AM1));
105
106 array_bitset_container_intersection(A1, B2, AI);
107 assert_int_equal(ci, array_container_cardinality(AI));
108
109 array_bitset_container_intersection(A2, B1, AI);
110 assert_int_equal(ci, array_container_cardinality(AI));
111
112 array_bitset_container_union(A1, B2, BO);
113 assert_int_equal(co, bitset_container_cardinality(BO));
114
115 array_bitset_container_union(A2, B1, BO);
116 assert_int_equal(co, bitset_container_cardinality(BO));
117
118 void* BX_1 = NULL;
119
120 assert_true(array_bitset_container_xor(A1, B2, &BX_1));
121 assert_int_equal(cx, bitset_container_cardinality(BX_1));
122
123 bitset_container_free(BX_1);
124 BX_1 = NULL;
125 assert_true(array_bitset_container_xor(A2, B1, &BX_1));
126 assert_int_equal(cx, bitset_container_cardinality(BX_1));
127
128 bitset_container_free(BX_1);
129 BX_1 = NULL;
130 assert_true(array_array_container_xor(A2, A1, &BX_1));
131 assert_int_equal(cx, bitset_container_cardinality(BX_1));
132
133 bitset_container_free(BX_1);
134 BX_1 = NULL;
135 assert_true(bitset_bitset_container_xor(B2, B1, &BX_1));
136 assert_int_equal(cx, bitset_container_cardinality(BX_1));
137
138 bitset_container_free(BX_1);
139 BX_1 = NULL;
140 // xoring something with itself, getting array
141 assert_false(array_bitset_container_xor(A2, B2, &BX_1));
142 assert_int_equal(0, array_container_cardinality(BX_1));
143
144 array_container_free(BX_1);
145 BX_1 = NULL;
146 // xoring array with itself, getting array
147 assert_false(array_array_container_xor(A2, A2, &BX_1));
148 assert_int_equal(0, array_container_cardinality(BX_1));
149
150 array_container_free(BX_1);
151 BX_1 = NULL;
152 // xoring bitset with itself, getting array
153 assert_false(bitset_bitset_container_xor(B2, B2, &BX_1));
154 assert_int_equal(0, array_container_cardinality(BX_1));
155
156 array_container_free(BX_1);
157 BX_1 = NULL;
158
159 array_bitset_container_andnot(A1, B2, AM);
160 assert_int_equal(cm, array_container_cardinality(AM));
161
162 array_bitset_container_andnot(A2, B1, AM1);
163 assert_int_equal(cm1, array_container_cardinality(AM1));
164
165 array_array_container_andnot(A2, A1, AM1);
166 assert_int_equal(cm1, array_container_cardinality(AM1));
167
168 array_array_container_andnot(A1, A2, AM);
169 assert_int_equal(cm, array_container_cardinality(AM));
170
171 void* some_container = NULL; // sometimes bitmap, sometimes array.
172
173 assert_true(bitset_bitset_container_andnot(B1, B2, &some_container));
174 assert_int_equal(cm, bitset_container_cardinality(some_container));
175 bitset_container_free(some_container);
176 some_container = NULL;
177
178 assert_true(bitset_array_container_andnot(B1, A2, &some_container));
179 assert_int_equal(cm, bitset_container_cardinality(some_container));
180 bitset_container_free(some_container);
181 some_container = NULL;
182
183 // Hopefully density means it will be an array
184 assert_false(bitset_bitset_container_andnot(B2, B1, &some_container));
185 assert_int_equal(cm1, array_container_cardinality(some_container));
186 array_container_free(some_container);
187 some_container = NULL;
188
189 // Hopefully density means it will be an array
190 assert_false(bitset_array_container_andnot(B2, A1, &some_container));
191 assert_int_equal(cm1, array_container_cardinality(some_container));
192 array_container_free(some_container);
193 some_container = NULL;
194
195 // subtracting something with itself, getting array
196 array_bitset_container_andnot(A2, B2, AM1);
197 assert_int_equal(0, array_container_cardinality(AM1));
198
199 // subtracting something with itself, getting array
200 bitset_array_container_andnot(B2, A2, &some_container);
201 assert_int_equal(0, array_container_cardinality(some_container));
202 array_container_free(some_container);
203 some_container = NULL;
204
205 // subtracting array with itself, getting array
206 array_array_container_andnot(A2, A2, AM1);
207 assert_int_equal(0, array_container_cardinality(AM1));
208
209 // subtracting bitset with itself, getting array
210 assert_false(bitset_bitset_container_andnot(B2, B2, &some_container));
211 assert_int_equal(0, array_container_cardinality(some_container));
212 array_container_free(some_container);
213
214 array_container_free(A1);
215 array_container_free(A2);
216 array_container_free(AI);
217 array_container_free(AO);
218 array_container_free(AX);
219 array_container_free(AM);
220 array_container_free(AM1);
221
222 bitset_container_free(B1);
223 bitset_container_free(B2);
224 bitset_container_free(BI);
225 bitset_container_free(BO);
226 bitset_container_free(BX);
227 bitset_container_free(BM);
228 bitset_container_free(BM1);
229 // bitset_container_free(BX_1);
230}
231
232// all xor routines with lazy option
233void array_bitset_run_lazy_xor_test() {
234 // not all these containers are currently used in tests
235 array_container_t* A1 = array_container_create();
236 array_container_t* A2 = array_container_create();
237 array_container_t* AX = array_container_create();
238 bitset_container_t* B1 = bitset_container_create();
239 bitset_container_t* B2 = bitset_container_create();
240 bitset_container_t* B2copy = bitset_container_create();
241 bitset_container_t* BX = bitset_container_create();
242 run_container_t* R1 = run_container_create();
243 run_container_t* R2 = run_container_create();
244 run_container_t* RX = run_container_create();
245
246 // nb, array and run containers will be illegally big.
247 for (int x = 0; x < (1 << 16); x += 3) {
248 array_container_add(A1, x);
249 bitset_container_set(B1, x);
250 run_container_add(R1, x);
251 }
252
253 // important: 62 is not divisible by 3
254 for (int x = 0; x < (1 << 16); x += 62) {
255 array_container_add(A2, x);
256 bitset_container_set(B2, x);
257 bitset_container_set(B2copy, x);
258 run_container_add(R2, x);
259 }
260
261 for (int x = 0; x < (1 << 16); x++)
262 if ((x % 62 == 0) ^ (x % 3 == 0)) {
263 array_container_add(AX, x);
264 bitset_container_set(BX, x);
265 run_container_add(RX, x);
266 }
267
268 // we interleave O and I on purpose (to trigger bugs!)
269 int cx = array_container_cardinality(AX); // expected xor
270
271 array_bitset_container_lazy_xor(A1, B2, BX);
272 assert_int_equal(BITSET_UNKNOWN_CARDINALITY,
273 bitset_container_cardinality(BX));
274 assert_int_equal(cx, bitset_container_compute_cardinality(BX));
275
276 array_bitset_container_lazy_xor(A1, B2, B2); // result onto B2, allowed
277 assert_int_equal(BITSET_UNKNOWN_CARDINALITY,
278 bitset_container_cardinality(B2));
279 assert_int_equal(cx, bitset_container_compute_cardinality(B2));
280 bitset_container_copy(B2copy, B2);
281
282 run_bitset_container_lazy_xor(R1, B2, BX);
283 assert_int_equal(BITSET_UNKNOWN_CARDINALITY,
284 bitset_container_cardinality(BX));
285 assert_int_equal(cx, bitset_container_compute_cardinality(BX));
286
287 run_bitset_container_lazy_xor(
288 R1, B2, B2); // result onto B2 : not sure it's allowed
289 assert_int_equal(BITSET_UNKNOWN_CARDINALITY,
290 bitset_container_cardinality(B2));
291 assert_int_equal(cx, bitset_container_compute_cardinality(B2));
292 bitset_container_copy(B2copy, B2);
293
294 void* ans = 0;
295 assert_true(array_array_container_lazy_xor(A1, A2, &ans));
296 assert_int_equal(BITSET_UNKNOWN_CARDINALITY,
297 bitset_container_cardinality(ans));
298 assert_int_equal(cx, bitset_container_compute_cardinality(ans));
299 bitset_container_free(ans);
300
301 array_run_container_lazy_xor(A1, R2, RX); // destroys content of RX
302 assert_int_equal(cx, run_container_cardinality(RX));
303
304 array_container_free(A1);
305 array_container_free(A2);
306 array_container_free(AX);
307
308 bitset_container_free(B1);
309 bitset_container_free(B2);
310 bitset_container_free(B2copy);
311 bitset_container_free(BX);
312
313 run_container_free(R1);
314 run_container_free(R2);
315 run_container_free(RX);
316}
317
318void array_bitset_ixor_test() {
319 array_container_t* A1 = array_container_create();
320 array_container_t* A1copy = array_container_create();
321 array_container_t* A1mod = array_container_create();
322 array_container_t* A2 = array_container_create();
323 array_container_t* AX = array_container_create();
324 bitset_container_t* B1 = bitset_container_create();
325 bitset_container_t* B1copy = bitset_container_create();
326 bitset_container_t* B1mod = bitset_container_create();
327 bitset_container_t* B2 = bitset_container_create();
328 bitset_container_t* BX = bitset_container_create();
329
330 // nb, array containers will be illegally big.
331 for (int x = 0; x < (1 << 16); x += 3) {
332 array_container_add(A1, x);
333 bitset_container_set(B1, x);
334 }
335
336 // important: 62 is not divisible by 3
337 for (int x = 0; x < (1 << 16); x += 62) {
338 array_container_add(A2, x);
339 bitset_container_set(B2, x);
340 }
341
342 for (int x = 0; x < (1 << 16); x++)
343 if ((x % 62 == 0) ^ (x % 3 == 0)) {
344 array_container_add(AX, x);
345 bitset_container_set(BX, x);
346 }
347
348 array_container_copy(A1, A1copy);
349 bitset_container_copy(B1, B1copy);
350 array_container_copy(A1, A1mod);
351 array_container_add(A1mod, 2);
352 bitset_container_copy(B1, B1mod);
353 bitset_container_add(B1mod, 2);
354
355 int cx = array_container_cardinality(AX); // expected xor
356
357 void* BX_1 = NULL;
358
359 assert_true(bitset_array_container_ixor(B2, A1, &BX_1));
360 assert_int_equal(cx, bitset_container_cardinality(BX_1));
361 // this case, result is inplace
362 assert_ptr_equal(BX_1, B2);
363
364 BX_1 = NULL;
365 assert_true(array_bitset_container_ixor(A2, B1, &BX_1));
366 assert_int_equal(cx, bitset_container_cardinality(BX_1));
367 assert_ptr_not_equal(BX_1, A2); // nb A2 is destroyed
368 // don't test a case where result can fit in the array
369 // until this is implemented...at that point, make sure
370
371 bitset_container_free(BX_1);
372 BX_1 = NULL;
373 // xoring something with itself, getting array
374 assert_false(array_bitset_container_ixor(A1, B1, &BX_1));
375 assert_int_equal(0, array_container_cardinality(BX_1));
376
377 array_container_free(BX_1);
378 BX_1 = NULL;
379
380 // B1mod and B1copy differ in position 2 only
381 assert_false(bitset_bitset_container_ixor(B1mod, B1copy, &BX_1));
382 assert_int_equal(1, array_container_cardinality(BX_1));
383
384 array_container_free(BX_1);
385 BX_1 = NULL;
386 assert_false(array_array_container_ixor(A1mod, A1copy, &BX_1));
387 assert_int_equal(1, array_container_cardinality(BX_1));
388
389 // array_container_free(A1); // disposed already
390 // array_container_free(A2); // has been disposed already
391 array_container_free(AX);
392 array_container_free(A1copy);
393
394 bitset_container_free(B1);
395 bitset_container_free(B1copy);
396 bitset_container_free(B2);
397 bitset_container_free(BX);
398 array_container_free(BX_1);
399}
400
401void array_bitset_iandnot_test() {
402 array_container_t* A1 = array_container_create();
403 array_container_t* AM = array_container_create();
404 array_container_t* AM1 = array_container_create();
405 array_container_t* A1copy = array_container_create();
406 array_container_t* A2copy = array_container_create();
407 array_container_t* A1mod = array_container_create();
408 array_container_t* A2 = array_container_create();
409 bitset_container_t* B1 = bitset_container_create();
410 bitset_container_t* BM = bitset_container_create();
411 bitset_container_t* BM1 = bitset_container_create();
412 bitset_container_t* B1copy = bitset_container_create();
413 bitset_container_t* B1mod = bitset_container_create();
414 bitset_container_t* B2 = bitset_container_create();
415 bitset_container_t* B2copy = bitset_container_create();
416
417 // nb, array containers will be illegally big.
418 for (int x = 0; x < (1 << 16); x += 3) {
419 array_container_add(A1, x);
420 bitset_container_set(B1, x);
421 }
422
423 // important: 62 is not divisible by 3
424 for (int x = 0; x < (1 << 16); x += 62) {
425 array_container_add(A2, x);
426 bitset_container_set(B2, x);
427 }
428
429 for (int x = 0; x < (1 << 16); x++) {
430 if ((x % 3 == 0) && !(x % 62 == 0)) {
431 array_container_add(AM, x);
432 bitset_container_set(BM, x);
433 }
434 if ((x % 62 == 0) && !(x % 3 == 0)) {
435 array_container_add(AM1, x);
436 bitset_container_set(BM1, x);
437 }
438 }
439
440 array_container_copy(A1, A1copy);
441 array_container_copy(A2, A2copy);
442 bitset_container_copy(B1, B1copy);
443 bitset_container_copy(B2, B2copy);
444 array_container_copy(A1, A1mod);
445 array_container_add(A1mod, 2);
446 bitset_container_copy(B1, B1mod);
447 bitset_container_add(B1mod, 2);
448
449 int cm = array_container_cardinality(AM); // expected difference
450 int cm1 = array_container_cardinality(AM1); // expected reverse difference
451
452 void* some_container = NULL;
453
454 assert_false(bitset_array_container_iandnot(B2, A1, &some_container));
455 assert_int_equal(cm1, array_container_cardinality(some_container));
456 // this case, result is not inplace
457 assert_ptr_not_equal(some_container, B2);
458 B2 = bitset_container_create(); // since B2 had been destroyed.
459 array_container_free(some_container);
460 bitset_container_copy(B2copy, B2);
461
462 assert_true(bitset_array_container_iandnot(B1, A2, &some_container));
463 assert_int_equal(cm, bitset_container_cardinality(some_container));
464 // this case, result is inplace
465 assert_ptr_equal(some_container, B1);
466 bitset_container_copy(B1copy, B1);
467
468 array_bitset_container_iandnot(A2, B1);
469 assert_int_equal(cm1, array_container_cardinality(A2));
470 array_container_copy(A2copy, A2);
471
472 // subtracting something from itself, getting array
473 array_bitset_container_iandnot(A1, B1);
474 assert_int_equal(0, array_container_cardinality(A1));
475 array_container_copy(A1copy, A1);
476
477 // B1mod and B1copy differ in position 2 only (B1mod has it)
478 assert_false(
479 bitset_bitset_container_iandnot(B1mod, B1copy, &some_container));
480 assert_int_equal(1, array_container_cardinality(some_container));
481 array_container_free(some_container);
482 some_container = NULL;
483
484 array_array_container_iandnot(A1mod, A1copy);
485 assert_int_equal(1, array_container_cardinality(A1mod));
486 // A1 mod now corrupted
487
488 array_container_free(A1);
489 array_container_free(A2);
490 array_container_free(AM);
491 array_container_free(AM1);
492 array_container_free(A1copy);
493 array_container_free(A2copy);
494 array_container_free(A1mod);
495
496 bitset_container_free(B1);
497 bitset_container_free(B1copy);
498 bitset_container_free(B2);
499 bitset_container_free(B2copy);
500 bitset_container_free(BM);
501 bitset_container_free(BM1);
502}
503
504// routines where one of the containers is a run container
505void run_xor_test() {
506 array_container_t* A1 = array_container_create();
507 array_container_t* A2 = array_container_create();
508 array_container_t* A3 = array_container_create();
509 array_container_t* AX = array_container_create();
510 bitset_container_t* B1 = bitset_container_create();
511 bitset_container_t* B2 = bitset_container_create();
512 bitset_container_t* B3 = bitset_container_create();
513 bitset_container_t* BX = bitset_container_create();
514 run_container_t* R1 = run_container_create();
515 run_container_t* R2 = run_container_create();
516 run_container_t* R3 = run_container_create();
517 run_container_t* R4 = run_container_create();
518
519 // B/A1 xor R1 is empty (array or run, I guess)
520 // B/A1 xor R2 is probably best left as runs
521 // B/A3 xor R1 is best as an array.
522 // B/A3 xor R4 is best as a bitmap
523
524 // nb, array containers will be illegally big.
525 for (int x = 0; x < (1 << 16); x++) {
526 if (x % 5 < 3) {
527 array_container_add(A1, x);
528 bitset_container_set(B1, x);
529 run_container_add(R1, x);
530 }
531 }
532
533 for (int x = 0; x < (1 << 16); x++) {
534 if (x % 62 < 37) {
535 array_container_add(A2, x);
536 bitset_container_set(B2, x);
537 run_container_add(R2, x);
538 }
539 }
540
541 for (int x = 0; x < (1 << 16); x++)
542 if ((x % 62 < 37) ^ (x % 5 < 3)) {
543 array_container_add(AX, x);
544 bitset_container_set(BX, x);
545 }
546
547 // the elements x%5 == 2 differ for less than 10k, otherwise same)
548 for (int x = 0; x < (1 << 16); x++) {
549 if ((x % 5 < 2) || ((x % 5 < 3) && (x > 10000))) {
550 array_container_add(A3, x);
551 bitset_container_set(B3, x);
552 run_container_add(R3, x);
553 }
554 }
555
556 int randstate = 1; // for Oakenfull RNG, hope LSBits are nice
557 for (int x = 0; x < (1 << 16); x++) {
558 if (randstate % 4) {
559 run_container_add(R4, x);
560 }
561 randstate = (3432 * randstate + 6789) % 9973;
562 }
563
564 int cx12 = array_container_cardinality(AX); // expected xor for ?1 and ?2
565
566 void* BX_1 = NULL;
567
568 assert_false(run_bitset_container_xor(R1, B1, &BX_1));
569 assert_int_equal(0, array_container_cardinality(BX_1));
570 array_container_free(BX_1);
571 BX_1 = NULL;
572
573 assert_int_equal(ARRAY_CONTAINER_TYPE_CODE,
574 array_run_container_xor(A1, R1, &BX_1));
575 assert_int_equal(0, array_container_cardinality(BX_1));
576 array_container_free(BX_1);
577 BX_1 = NULL;
578
579 // both run coding and array coding have same serialized size for
580 // empty
581 assert_int_equal(RUN_CONTAINER_TYPE_CODE,
582 run_run_container_xor(R1, R1, &BX_1));
583 assert_int_equal(0, run_container_cardinality(BX_1));
584 run_container_free(BX_1);
585 BX_1 = NULL;
586
587 assert_false(run_bitset_container_xor(R1, B3, &BX_1));
588 assert_int_equal(2000, array_container_cardinality(BX_1));
589 array_container_free(BX_1);
590 BX_1 = NULL;
591
592 assert_int_equal(ARRAY_CONTAINER_TYPE_CODE,
593 array_run_container_xor(A3, R1, &BX_1));
594 assert_int_equal(2000, array_container_cardinality(BX_1));
595 array_container_free(BX_1);
596 BX_1 = NULL;
597
598 assert_int_equal(ARRAY_CONTAINER_TYPE_CODE,
599 run_run_container_xor(R1, R3, &BX_1));
600 assert_int_equal(2000, array_container_cardinality(BX_1));
601 array_container_free(BX_1);
602 BX_1 = NULL;
603
604 assert_true(run_bitset_container_xor(R1, B2, &BX_1));
605 assert_int_equal(cx12, bitset_container_cardinality(BX_1));
606 bitset_container_free(BX_1);
607 BX_1 = NULL;
608
609 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
610 array_run_container_xor(A2, R1, &BX_1));
611 assert_int_equal(cx12, bitset_container_cardinality(BX_1));
612 bitset_container_free(BX_1);
613 BX_1 = NULL;
614
615 array_container_t* A_small = array_container_create();
616 for (int i = 1000; i < 1010; ++i) array_container_add(A_small, i);
617
618 assert_int_equal(RUN_CONTAINER_TYPE_CODE,
619 array_run_container_xor(A_small, R2, &BX_1));
620 assert_int_equal(0x98bd,
621 run_container_cardinality(BX_1)); // hopefully right...
622 run_container_free(BX_1);
623 BX_1 = NULL;
624
625 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
626 run_run_container_xor(R1, R2, &BX_1));
627 assert_int_equal(cx12, bitset_container_cardinality(BX_1));
628 bitset_container_free(BX_1);
629 BX_1 = NULL;
630
631 assert_true(run_bitset_container_xor(R4, B3, &BX_1));
632 int card_3_4 = bitset_container_cardinality(BX_1);
633 // assert_int_equal(card_3_4, bitset_container_cardinality(BX_1));
634 bitset_container_free(BX_1);
635 BX_1 = NULL;
636
637 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
638 array_run_container_xor(A3, R4, &BX_1));
639 // if this fails, either this bitset is wrong or the previous one...
640 assert_int_equal(card_3_4, bitset_container_cardinality(BX_1));
641 bitset_container_free(BX_1);
642 BX_1 = NULL;
643
644 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
645 run_run_container_xor(R4, R3, &BX_1));
646 assert_int_equal(card_3_4, bitset_container_cardinality(BX_1));
647 bitset_container_free(BX_1);
648 BX_1 = NULL;
649
650 array_container_free(A1);
651 array_container_free(A2);
652 array_container_free(A3);
653 array_container_free(AX);
654 array_container_free(A_small);
655
656 bitset_container_free(B1);
657 bitset_container_free(B2);
658 bitset_container_free(B3);
659 bitset_container_free(BX);
660
661 run_container_free(R1);
662 run_container_free(R2);
663 run_container_free(R3);
664 run_container_free(R4);
665}
666
667// routines where one of the containers is a run container, copied from xor code
668void run_andnot_test() {
669 array_container_t* A1 = array_container_create();
670 array_container_t* A2 = array_container_create();
671 array_container_t* A3 = array_container_create();
672 array_container_t* A4 = array_container_create();
673 array_container_t* AM = array_container_create();
674 bitset_container_t* B1 = bitset_container_create();
675 bitset_container_t* B2 = bitset_container_create();
676 bitset_container_t* B3 = bitset_container_create();
677 bitset_container_t* B4 = bitset_container_create();
678 bitset_container_t* BM = bitset_container_create();
679 run_container_t* R1 = run_container_create();
680 run_container_t* R2 = run_container_create();
681 run_container_t* R3 = run_container_create();
682 run_container_t* R4 = run_container_create();
683
684 // B/A1 minus R1 is empty (array or run, I guess)
685 // B/A1 minus R2 is probably best left as runs
686 // B/A3 minus R1 is best as an array.
687 // B/A3 minus R4 is best as a bitmap
688
689 // nb, array containers will be illegally big.
690 for (int x = 0; x < (1 << 16); x++) {
691 if (x % 5 < 3) {
692 array_container_add(A1, x);
693 bitset_container_set(B1, x);
694 run_container_add(R1, x);
695 }
696 }
697
698 for (int x = 0; x < (1 << 16); x++) {
699 if (x % 62 < 37) {
700 array_container_add(A2, x);
701 bitset_container_set(B2, x);
702 run_container_add(R2, x);
703 }
704 }
705
706 for (int x = 0; x < (1 << 16); x++)
707 if ((x % 5 < 3) && !(x % 62 < 37)) {
708 array_container_add(AM, x);
709 bitset_container_set(BM, x);
710 }
711
712 // the elements x%5 == 2 differ for less than 10k, otherwise same)
713 for (int x = 0; x < (1 << 16); x++) {
714 if ((x % 5 < 2) || ((x % 5 < 3) && (x > 10000))) {
715 array_container_add(A3, x);
716 bitset_container_set(B3, x);
717 run_container_add(R3, x);
718 }
719 }
720
721 int randstate = 1; // for Oakenfull RNG, hope LSBits are nice
722 for (int x = 0; x < (1 << 16); x++) {
723 if (randstate % 4) {
724 run_container_add(R4, x);
725 array_container_add(A4, x);
726 bitset_container_add(B4, x);
727 }
728 randstate = (3432 * randstate + 6789) % 9973;
729 }
730
731 int cm12 = array_container_cardinality(AM);
732
733 void* BM_1 = NULL;
734
735 assert_false(run_bitset_container_andnot(R1, B1, &BM_1));
736 assert_int_equal(0, array_container_cardinality(BM_1));
737 array_container_free(BM_1);
738 BM_1 = NULL;
739
740 array_run_container_andnot(A1, R1, AM);
741 assert_int_equal(0, array_container_cardinality(AM));
742
743 // both run coding and array coding have same serialized size for
744 // empty
745 assert_int_equal(RUN_CONTAINER_TYPE_CODE,
746 run_run_container_andnot(R1, R1, &BM_1));
747 assert_int_equal(0, run_container_cardinality(BM_1));
748 run_container_free(BM_1);
749 BM_1 = NULL;
750
751 assert_false(run_bitset_container_andnot(R1, B3, &BM_1));
752 assert_int_equal(2000, array_container_cardinality(BM_1));
753 array_container_free(BM_1);
754 BM_1 = NULL;
755
756 assert_false(bitset_run_container_andnot(B1, R3, &BM_1));
757 assert_int_equal(2000, array_container_cardinality(BM_1));
758 array_container_free(BM_1);
759 BM_1 = NULL;
760
761 array_run_container_andnot(A1, R3, AM);
762 assert_int_equal(2000, array_container_cardinality(AM));
763
764 assert_int_equal(ARRAY_CONTAINER_TYPE_CODE,
765 run_array_container_andnot(R1, A3, &BM_1));
766 assert_int_equal(2000, array_container_cardinality(BM_1));
767 array_container_free(BM_1);
768 BM_1 = NULL;
769
770 assert_int_equal(ARRAY_CONTAINER_TYPE_CODE,
771 run_run_container_andnot(R1, R3, &BM_1));
772 assert_int_equal(2000, array_container_cardinality(BM_1));
773 array_container_free(BM_1);
774 BM_1 = NULL;
775
776 assert_true(run_bitset_container_andnot(R1, B2, &BM_1));
777 assert_int_equal(cm12, bitset_container_cardinality(BM_1));
778 bitset_container_free(BM_1);
779 BM_1 = NULL;
780
781 array_run_container_andnot(A1, R2, AM);
782 assert_int_equal(cm12, array_container_cardinality(AM));
783
784 array_container_t* A_small = array_container_create();
785 for (int i = 990; i < 1000; ++i) array_container_add(A_small, i);
786
787 run_container_t* R_small = run_container_create();
788 for (int i = 990; i < 1000; ++i) run_container_add(R_small, i);
789
790 array_run_container_andnot(A_small, R2, AM);
791 assert_int_equal(2, // something like that
792 array_container_cardinality(AM)); // hopefully right...
793
794 assert_false(run_bitset_container_andnot(R_small, B2, &BM_1));
795 assert_int_equal(2, array_container_cardinality(BM_1));
796 array_container_free(BM_1);
797 BM_1 = NULL;
798
799 // note, result is equally small as an array or a run
800 assert_int_equal(RUN_CONTAINER_TYPE_CODE,
801 run_array_container_andnot(R_small, A2, &BM_1));
802 assert_int_equal(2, run_container_cardinality(BM_1));
803 array_container_free(BM_1);
804 BM_1 = NULL;
805
806 // test with more complicated small run structure (to do)
807 run_container_t* R_small_complex = run_container_create();
808 array_container_t* temp_ac = array_container_create();
809
810 for (int i = 0; i < 3; ++i) run_container_add(R_small_complex, i);
811 for (int i = 10; i < 12; ++i) run_container_add(R_small_complex, i);
812 for (int i = 990; i < 995; ++i) run_container_add(R_small_complex, i);
813 for (int i = 10000; i < 10003; ++i) run_container_add(R_small_complex, i);
814 for (int i = 20000; i < 20002; ++i) run_container_add(R_small_complex, i);
815
816 array_container_add(temp_ac, 993);
817 array_container_add(temp_ac, 994);
818 array_container_add(temp_ac, 2000);
819
820 assert_int_equal(
821 RUN_CONTAINER_TYPE_CODE,
822 run_array_container_andnot(R_small_complex, temp_ac, &BM_1));
823 assert_int_equal(13, run_container_cardinality(BM_1));
824 array_container_free(BM_1);
825 BM_1 = NULL;
826
827 array_container_free(temp_ac);
828 run_container_free(R_small_complex);
829
830 assert_int_equal(ARRAY_CONTAINER_TYPE_CODE,
831 run_array_container_andnot(R1, A3, &BM_1));
832 assert_int_equal(2000, array_container_cardinality(BM_1));
833 array_container_free(BM_1);
834 BM_1 = NULL;
835
836 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
837 run_run_container_andnot(R1, R2, &BM_1));
838 assert_int_equal(cm12, bitset_container_cardinality(BM_1));
839 bitset_container_free(BM_1);
840 BM_1 = NULL;
841
842 // compute the true card for cont4 - cont3 assuming that
843 // bitset-bitset implementation is known correct
844 assert_true(bitset_bitset_container_andnot(B4, B3, &BM_1));
845 int card_4_3 = bitset_container_cardinality(BM_1);
846 bitset_container_free(BM_1);
847 BM_1 = NULL;
848
849 assert_true(run_bitset_container_andnot(R4, B3, &BM_1));
850 assert_int_equal(card_4_3, bitset_container_cardinality(BM_1));
851 bitset_container_free(BM_1);
852 BM_1 = NULL;
853
854 array_run_container_andnot(A4, R3, AM);
855 // if this fails, either this bitset is wrong or the previous one...
856 assert_int_equal(card_4_3, array_container_cardinality(AM));
857
858 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
859 run_run_container_andnot(R4, R3, &BM_1));
860 assert_int_equal(card_4_3, bitset_container_cardinality(BM_1));
861 bitset_container_free(BM_1);
862 BM_1 = NULL;
863
864 array_container_free(A1);
865 array_container_free(A2);
866 array_container_free(A3);
867 array_container_free(A4);
868 array_container_free(AM);
869 array_container_free(A_small);
870
871 bitset_container_free(B1);
872 bitset_container_free(B2);
873 bitset_container_free(B3);
874 bitset_container_free(B4);
875 bitset_container_free(BM);
876
877 run_container_free(R1);
878 run_container_free(R2);
879 run_container_free(R3);
880 run_container_free(R4);
881 run_container_free(R_small);
882}
883
884// routines where one of the containers is a run container
885void run_ixor_test() {
886 array_container_t* A1 = array_container_create();
887 array_container_t* A2 = array_container_create();
888 array_container_t* A3 = array_container_create();
889 array_container_t* A4 = array_container_create();
890 array_container_t* AX = array_container_create();
891 bitset_container_t* B1 = bitset_container_create();
892 bitset_container_t* B2 = bitset_container_create();
893 bitset_container_t* B3 = bitset_container_create();
894 bitset_container_t* BX = bitset_container_create();
895 run_container_t* R1 = run_container_create();
896 run_container_t* R2 = run_container_create();
897 run_container_t* R3 = run_container_create();
898 run_container_t* R4 = run_container_create();
899
900 // B/A1 xor R1 is empty (array or run, I guess)
901 // B/A1 xor R2 is probably best left as runs
902 // B/A3 xor R1 is best as an array.
903 // B/A3 xor R4 is best as a bitmap
904
905 // nb, array containers will be illegally big.
906 for (int x = 0; x < (1 << 16); x++) {
907 if (x % 5 < 3) {
908 array_container_add(A1, x);
909 bitset_container_set(B1, x);
910 run_container_add(R1, x);
911 }
912 }
913
914 for (int x = 0; x < (1 << 16); x++) {
915 if (x % 62 < 37) {
916 array_container_add(A2, x);
917 bitset_container_set(B2, x);
918 run_container_add(R2, x);
919 }
920 }
921
922 for (int x = 0; x < (1 << 16); x++)
923 if ((x % 62 < 37) ^ (x % 5 < 3)) {
924 array_container_add(AX, x);
925 bitset_container_set(BX, x);
926 }
927
928 // the elements x%5 == 2 differ for less than 10k, otherwise same)
929 for (int x = 0; x < (1 << 16); x++) {
930 if ((x % 5 < 2) || ((x % 5 < 3) && (x > 10000))) {
931 array_container_add(A3, x);
932 bitset_container_set(B3, x);
933 run_container_add(R3, x);
934 }
935 }
936
937 int randstate = 1; // for Oakenfull RNG, hope LSBits are nice
938 for (int x = 0; x < (1 << 16); x++) {
939 if (randstate % 4) {
940 run_container_add(R4, x);
941 array_container_add(A4, x);
942 }
943 randstate = (3432 * randstate + 6789) % 9973;
944 }
945
946 int cx12 = array_container_cardinality(AX); // expected xor for ?1 and ?2
947
948 void* BX_1 = NULL;
949
950 run_container_t* temp_r = run_container_clone(R1);
951 assert_false(run_bitset_container_ixor(temp_r, B1, &BX_1));
952 assert_int_equal(0, array_container_cardinality(BX_1));
953 array_container_free(BX_1);
954 BX_1 = NULL;
955
956 bitset_container_t* temp_b = bitset_container_create();
957 bitset_container_copy(B1, temp_b);
958 assert_false(bitset_run_container_ixor(temp_b, R1, &BX_1));
959 assert_int_equal(0, array_container_cardinality(BX_1));
960 array_container_free(BX_1);
961 BX_1 = NULL;
962
963 array_container_t* temp_a = array_container_clone(A1);
964 assert_int_equal(ARRAY_CONTAINER_TYPE_CODE,
965 array_run_container_ixor(temp_a, R1, &BX_1));
966 assert_int_equal(0, array_container_cardinality(BX_1));
967 array_container_free(BX_1);
968 BX_1 = NULL;
969
970 temp_r = run_container_clone(R1);
971 assert_int_equal(ARRAY_CONTAINER_TYPE_CODE,
972 run_array_container_ixor(temp_r, A1, &BX_1));
973 assert_int_equal(0, array_container_cardinality(BX_1));
974 array_container_free(BX_1);
975 BX_1 = NULL;
976
977 // both run coding and array coding have same serialized size for
978 // empty
979 temp_r = run_container_clone(R1);
980 int ret_type = run_run_container_ixor(temp_r, R1, &BX_1);
981 assert_int_not_equal(BITSET_CONTAINER_TYPE_CODE, ret_type);
982 if (ret_type == RUN_CONTAINER_TYPE_CODE) {
983 assert_int_equal(0, run_container_cardinality(BX_1));
984 run_container_free(BX_1);
985 } else {
986 assert_int_equal(0, array_container_cardinality(BX_1));
987 array_container_free(BX_1);
988 }
989 BX_1 = NULL;
990
991 temp_r = run_container_clone(R1);
992 assert_false(run_bitset_container_ixor(temp_r, B3, &BX_1));
993 assert_int_equal(2000, array_container_cardinality(BX_1));
994 array_container_free(BX_1);
995 BX_1 = NULL;
996
997 temp_a = array_container_clone(A3);
998 assert_int_equal(ARRAY_CONTAINER_TYPE_CODE,
999 array_run_container_ixor(temp_a, R1, &BX_1));
1000 assert_int_equal(2000, array_container_cardinality(BX_1));
1001 array_container_free(BX_1);
1002 BX_1 = NULL;
1003
1004 temp_b = bitset_container_create();
1005 bitset_container_copy(B1, temp_b);
1006 assert_false(bitset_run_container_ixor(temp_b, R3, &BX_1));
1007 assert_int_equal(2000, array_container_cardinality(BX_1));
1008 array_container_free(BX_1);
1009 BX_1 = NULL;
1010
1011 temp_r = run_container_clone(R3);
1012 assert_int_equal(ARRAY_CONTAINER_TYPE_CODE,
1013 run_array_container_ixor(temp_r, A1, &BX_1));
1014 assert_int_equal(2000, array_container_cardinality(BX_1));
1015 array_container_free(BX_1);
1016 BX_1 = NULL;
1017
1018 temp_r = run_container_clone(R1);
1019 assert_int_equal(ARRAY_CONTAINER_TYPE_CODE,
1020 run_run_container_ixor(temp_r, R3, &BX_1));
1021 assert_int_equal(2000, array_container_cardinality(BX_1));
1022 array_container_free(BX_1);
1023 BX_1 = NULL;
1024
1025 temp_r = run_container_clone(R1);
1026 assert_true(run_bitset_container_ixor(temp_r, B2, &BX_1));
1027 assert_int_equal(cx12, bitset_container_cardinality(BX_1));
1028 bitset_container_free(BX_1);
1029 BX_1 = NULL;
1030
1031 temp_a = array_container_clone(A2);
1032 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
1033 array_run_container_ixor(temp_a, R1, &BX_1));
1034 assert_int_equal(cx12, bitset_container_cardinality(BX_1));
1035 bitset_container_free(BX_1);
1036 BX_1 = NULL;
1037
1038 temp_b = bitset_container_create();
1039 bitset_container_copy(B1, temp_b);
1040 assert_true(bitset_run_container_ixor(temp_b, R2, &BX_1));
1041 assert_int_equal(cx12, bitset_container_cardinality(BX_1));
1042 bitset_container_free(BX_1);
1043 BX_1 = NULL;
1044
1045 temp_r = run_container_clone(R1);
1046 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
1047 run_array_container_ixor(temp_r, A2, &BX_1));
1048 assert_int_equal(cx12, bitset_container_cardinality(BX_1));
1049 bitset_container_free(BX_1);
1050 BX_1 = NULL;
1051
1052 temp_r = run_container_clone(R1);
1053 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
1054 run_run_container_ixor(temp_r, R2, &BX_1));
1055 assert_int_equal(cx12, bitset_container_cardinality(BX_1));
1056 bitset_container_free(BX_1);
1057 BX_1 = NULL;
1058
1059 temp_r = run_container_clone(R4);
1060 assert_true(run_bitset_container_ixor(temp_r, B3, &BX_1));
1061 int card_3_4 = bitset_container_cardinality(BX_1);
1062 // assert_int_equal(card_3_4, bitset_container_cardinality(BX_1));
1063 bitset_container_free(BX_1);
1064 BX_1 = NULL;
1065
1066 temp_a = array_container_clone(A3);
1067 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
1068 array_run_container_ixor(temp_a, R4, &BX_1));
1069 // if this fails, either this bitset is wrong or the previous one...
1070 assert_int_equal(card_3_4, bitset_container_cardinality(BX_1));
1071 bitset_container_free(BX_1);
1072 BX_1 = NULL;
1073
1074 temp_b = bitset_container_create();
1075 bitset_container_copy(B3, temp_b);
1076 assert_true(bitset_run_container_ixor(temp_b, R4, &BX_1));
1077 assert_int_equal(card_3_4, bitset_container_cardinality(BX_1));
1078 bitset_container_free(BX_1);
1079 BX_1 = NULL;
1080
1081 temp_r = run_container_clone(R3);
1082 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
1083 run_array_container_ixor(temp_r, A4, &BX_1));
1084 assert_int_equal(card_3_4, bitset_container_cardinality(BX_1));
1085 bitset_container_free(BX_1);
1086 BX_1 = NULL;
1087
1088 temp_r = run_container_clone(R4);
1089 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
1090 run_run_container_ixor(temp_r, R3, &BX_1));
1091 assert_int_equal(card_3_4, bitset_container_cardinality(BX_1));
1092 bitset_container_free(BX_1);
1093 BX_1 = NULL;
1094
1095 array_container_free(A1);
1096 array_container_free(A2);
1097 array_container_free(A3);
1098 array_container_free(AX);
1099 array_container_free(A4);
1100
1101 bitset_container_free(B1);
1102 bitset_container_free(B2);
1103 bitset_container_free(B3);
1104 bitset_container_free(BX);
1105
1106 run_container_free(R1);
1107 run_container_free(R2);
1108 run_container_free(R3);
1109 run_container_free(R4);
1110}
1111
1112void run_iandnot_test() {
1113 array_container_t* A1 = array_container_create();
1114 array_container_t* A2 = array_container_create();
1115 array_container_t* A3 = array_container_create();
1116 array_container_t* A4 = array_container_create();
1117 array_container_t* AM = array_container_create();
1118 bitset_container_t* B1 = bitset_container_create();
1119 bitset_container_t* B2 = bitset_container_create();
1120 bitset_container_t* B3 = bitset_container_create();
1121 bitset_container_t* B4 = bitset_container_create();
1122 bitset_container_t* BM = bitset_container_create();
1123 run_container_t* R1 = run_container_create();
1124 run_container_t* R2 = run_container_create();
1125 run_container_t* R3 = run_container_create();
1126 run_container_t* R4 = run_container_create();
1127
1128 // nb, array containers will be illegally big.
1129 for (int x = 0; x < (1 << 16); x++) {
1130 if (x % 5 < 3) {
1131 array_container_add(A1, x);
1132 bitset_container_set(B1, x);
1133 run_container_add(R1, x);
1134 }
1135 }
1136
1137 for (int x = 0; x < (1 << 16); x++) {
1138 if (x % 62 < 37) {
1139 array_container_add(A2, x);
1140 bitset_container_set(B2, x);
1141 run_container_add(R2, x);
1142 }
1143 }
1144
1145 for (int x = 0; x < (1 << 16); x++)
1146 if ((x % 5 < 3) && !(x % 62 < 37)) {
1147 array_container_add(AM, x);
1148 bitset_container_set(BM, x);
1149 }
1150
1151 // the elements x%5 == 2 differ for less than 10k, otherwise same)
1152 for (int x = 0; x < (1 << 16); x++) {
1153 if ((x % 5 < 2) || ((x % 5 < 3) && (x > 10000))) {
1154 array_container_add(A3, x);
1155 bitset_container_set(B3, x);
1156 run_container_add(R3, x);
1157 }
1158 }
1159
1160 int randstate = 1; // for Oakenfull RNG, hope LSBits are nice
1161 for (int x = 0; x < (1 << 16); x++) {
1162 if (randstate % 4) {
1163 run_container_add(R4, x);
1164 array_container_add(A4, x);
1165 bitset_container_add(B4, x);
1166 }
1167 randstate = (3432 * randstate + 6789) % 9973;
1168 }
1169
1170 int cm12 = array_container_cardinality(AM); // expected xor for ?1 and ?2
1171
1172 void* BM_1 = NULL;
1173
1174 run_container_t* temp_r = run_container_clone(R1);
1175 assert_false(run_bitset_container_iandnot(temp_r, B1, &BM_1));
1176 assert_int_equal(0, array_container_cardinality(BM_1));
1177 array_container_free(BM_1);
1178 BM_1 = NULL;
1179
1180 bitset_container_t* temp_b = bitset_container_create();
1181 bitset_container_copy(B1, temp_b);
1182 assert_false(bitset_run_container_iandnot(temp_b, R1, &BM_1));
1183 assert_int_equal(0, array_container_cardinality(BM_1));
1184 array_container_free(BM_1);
1185 BM_1 = NULL;
1186
1187 array_container_t* temp_a = array_container_clone(A1);
1188 array_run_container_iandnot(temp_a, R1);
1189 assert_int_equal(0, array_container_cardinality(temp_a));
1190 array_container_free(temp_a);
1191
1192 temp_r = run_container_clone(R1);
1193 assert_int_equal(ARRAY_CONTAINER_TYPE_CODE,
1194 run_array_container_iandnot(temp_r, A1, &BM_1));
1195 assert_int_equal(0, array_container_cardinality(BM_1));
1196 array_container_free(BM_1);
1197 BM_1 = NULL;
1198
1199 // both run coding and array coding have same serialized size for
1200 // empty
1201 temp_r = run_container_clone(R1);
1202 int ret_type = run_run_container_iandnot(temp_r, R1, &BM_1);
1203 assert_int_not_equal(BITSET_CONTAINER_TYPE_CODE, ret_type);
1204 if (ret_type == RUN_CONTAINER_TYPE_CODE) {
1205 assert_int_equal(0, run_container_cardinality(BM_1));
1206 run_container_free(BM_1);
1207 } else {
1208 assert_int_equal(0, array_container_cardinality(BM_1));
1209 array_container_free(BM_1);
1210 }
1211 BM_1 = NULL;
1212
1213 temp_r = run_container_clone(R1);
1214 assert_false(run_bitset_container_iandnot(temp_r, B3, &BM_1));
1215 assert_int_equal(2000, array_container_cardinality(BM_1));
1216 array_container_free(BM_1);
1217 BM_1 = NULL;
1218
1219 temp_a = array_container_clone(A1);
1220 array_run_container_iandnot(temp_a, R3);
1221 assert_int_equal(2000, array_container_cardinality(temp_a));
1222 array_container_free(temp_a);
1223
1224 temp_b = bitset_container_create();
1225 bitset_container_copy(B1, temp_b);
1226 assert_false(bitset_run_container_iandnot(temp_b, R3, &BM_1));
1227 assert_int_equal(2000, array_container_cardinality(BM_1));
1228 array_container_free(BM_1);
1229 BM_1 = NULL;
1230
1231 temp_r = run_container_clone(R1);
1232 assert_int_equal(ARRAY_CONTAINER_TYPE_CODE,
1233 run_array_container_iandnot(temp_r, A3, &BM_1));
1234 assert_int_equal(2000, array_container_cardinality(BM_1));
1235 array_container_free(BM_1);
1236 BM_1 = NULL;
1237
1238 temp_r = run_container_clone(R1);
1239 assert_int_equal(ARRAY_CONTAINER_TYPE_CODE,
1240 run_run_container_iandnot(temp_r, R3, &BM_1));
1241 assert_int_equal(2000, array_container_cardinality(BM_1));
1242 array_container_free(BM_1);
1243 BM_1 = NULL;
1244
1245 temp_r = run_container_clone(R1);
1246 assert_true(run_bitset_container_iandnot(temp_r, B2, &BM_1));
1247 assert_int_equal(cm12, bitset_container_cardinality(BM_1));
1248 bitset_container_free(BM_1);
1249 BM_1 = NULL;
1250
1251 temp_a = array_container_clone(A1);
1252 array_run_container_iandnot(temp_a, R2);
1253 assert_int_equal(cm12, array_container_cardinality(temp_a));
1254 array_container_free(temp_a);
1255
1256 temp_b = bitset_container_create();
1257 bitset_container_copy(B1, temp_b);
1258 assert_true(bitset_run_container_iandnot(temp_b, R2, &BM_1));
1259 assert_int_equal(cm12, bitset_container_cardinality(BM_1));
1260 bitset_container_free(BM_1);
1261 BM_1 = NULL;
1262
1263 temp_r = run_container_clone(R1);
1264 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
1265 run_array_container_iandnot(temp_r, A2, &BM_1));
1266 assert_int_equal(cm12, bitset_container_cardinality(BM_1));
1267 bitset_container_free(BM_1);
1268 BM_1 = NULL;
1269
1270 temp_r = run_container_clone(R1);
1271 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
1272 run_run_container_iandnot(temp_r, R2, &BM_1));
1273 assert_int_equal(cm12, bitset_container_cardinality(BM_1));
1274 bitset_container_free(BM_1);
1275 BM_1 = NULL;
1276
1277 assert_true(bitset_bitset_container_andnot(B4, B3, &BM_1));
1278 int card_4_3 = bitset_container_cardinality(BM_1);
1279 bitset_container_free(BM_1);
1280 BM_1 = NULL;
1281
1282 temp_r = run_container_clone(R4);
1283 assert_true(run_bitset_container_iandnot(temp_r, B3, &BM_1));
1284 assert_int_equal(card_4_3, bitset_container_cardinality(BM_1));
1285 bitset_container_free(BM_1);
1286 BM_1 = NULL;
1287
1288 temp_a = array_container_clone(A4);
1289 array_run_container_iandnot(temp_a, R3);
1290 // if this fails, either this bitset is wrong or the previous one...
1291 assert_int_equal(card_4_3, array_container_cardinality(temp_a));
1292 array_container_free(temp_a);
1293
1294 temp_b = bitset_container_create();
1295 bitset_container_copy(B4, temp_b);
1296 assert_true(bitset_run_container_iandnot(temp_b, R3, &BM_1));
1297 assert_int_equal(card_4_3, bitset_container_cardinality(BM_1));
1298 bitset_container_free(BM_1);
1299 BM_1 = NULL;
1300
1301 temp_r = run_container_clone(R4);
1302 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
1303 run_array_container_iandnot(temp_r, A3, &BM_1));
1304 assert_int_equal(card_4_3, bitset_container_cardinality(BM_1));
1305 bitset_container_free(BM_1);
1306 BM_1 = NULL;
1307
1308 temp_r = run_container_clone(R4);
1309 assert_int_equal(BITSET_CONTAINER_TYPE_CODE,
1310 run_run_container_iandnot(temp_r, R3, &BM_1));
1311 assert_int_equal(card_4_3, bitset_container_cardinality(BM_1));
1312 bitset_container_free(BM_1);
1313 BM_1 = NULL;
1314
1315 array_container_free(A1);
1316 array_container_free(A2);
1317 array_container_free(A3);
1318 array_container_free(AM);
1319 array_container_free(A4);
1320
1321 bitset_container_free(B1);
1322 bitset_container_free(B2);
1323 bitset_container_free(B3);
1324 bitset_container_free(B4);
1325 bitset_container_free(BM);
1326
1327 run_container_free(R1);
1328 run_container_free(R2);
1329 run_container_free(R3);
1330 run_container_free(R4);
1331}
1332
1333/* test replicating bug seen on real data */
1334void run_array_andnot_bug_test() {
1335 int runcontents[] = {
1336 196608, 196611, 196612, 196613, 196616, 196619, 196621, 196623, 196628,
1337 196629, 196630, 196631, 196632, 196633, 196634, 196635, 196636, 196638,
1338 196639, 196640, 196641, 196642, 196644, 196645, 196646, 196647, 196648,
1339 196649, 196650, 196652, 196653, 196654, 196656, 196658, 196659, 196660,
1340 196662, 196663, 196664, 196665, 196666, 196667, 196669, 196670, 196671,
1341 196672, 196673, 196674, 196675, 196677, 196678, 196679, 196680, 196682,
1342 196684, 196685, 196686, 196688, 196689, 196690, 196691, 196692, 196693,
1343 196694, 196695, 196697, 196698, 196699, 196700, 196701, 196702, 196703,
1344 196704, 196705, 196706, 196707, 196708, 196709, 196710, 196711, 196712,
1345 196713, 196714, 196715, 196717, 196719, 196720, 196722, 196723, 196725,
1346 196726, 196727, 196728, 196729, -1};
1347 int arraycontents[] = {196722, 196824, 196989, -1};
1348
1349 run_container_t* r = run_container_create();
1350 array_container_t* a = array_container_create();
1351
1352 for (int* p = runcontents; *p != -1; ++p) run_container_add(r, *p % 65536);
1353 for (int* p = arraycontents; *p != -1; ++p)
1354 array_container_add(a, *p % 65536);
1355
1356 int kindofresult;
1357 void* result = 0;
1358 kindofresult = run_array_container_andnot(r, a, &result);
1359 assert_int_equal(ARRAY_CONTAINER_TYPE_CODE, kindofresult);
1360 assert_false(array_container_contains(result, 196722 % 65536));
1361
1362 run_container_free(r);
1363 array_container_free(a);
1364 array_container_free(result);
1365}
1366
1367void array_negation_empty_test() {
1368 array_container_t* AI = array_container_create();
1369 bitset_container_t* BO = bitset_container_create();
1370
1371 array_container_negation(AI, BO);
1372
1373 assert_int_equal(bitset_container_cardinality(BO), (1 << 16));
1374
1375 array_container_free(AI);
1376 bitset_container_free(BO);
1377}
1378
1379void array_negation_test() {
1380 int ctr = 0;
1381 array_container_t* AI = array_container_create();
1382 bitset_container_t* BO = bitset_container_create();
1383
1384 for (int x = 0; x < (1 << 16); x += 29) {
1385 array_container_add(AI, (uint16_t)x);
1386 ++ctr;
1387 }
1388
1389 array_container_negation(AI, BO);
1390 assert_int_equal(bitset_container_cardinality(BO), (1 << 16) - ctr);
1391
1392 for (int x = 0; x < (1 << 16); x++) {
1393 if (x % 29 == 0) {
1394 assert_false(bitset_container_contains(BO, (uint16_t)x));
1395 } else {
1396 assert_true(bitset_container_contains(BO, (uint16_t)x));
1397 }
1398 array_container_add(AI, (uint16_t)x);
1399 ++ctr;
1400 }
1401
1402 array_container_free(AI);
1403 bitset_container_free(BO);
1404}
1405
1406static int array_negation_range_test(int r_start, int r_end, bool is_bitset) {
1407 bool result_is_bitset;
1408 int result_size_should_be = 0;
1409
1410 array_container_t* AI = array_container_create();
1411 void* BO; // bitset or array
1412
1413 for (int x = 0; x < (1 << 16); x += 29) {
1414 array_container_add(AI, (uint16_t)x);
1415 }
1416
1417 for (int x = 0; x < (1 << 16); x++) {
1418 if (x >= r_start && x < r_end)
1419 if (x % 29 != 0)
1420 result_size_should_be++;
1421 else {
1422 }
1423 else if (x % 29 == 0)
1424 result_size_should_be++;
1425 }
1426
1427 result_is_bitset =
1428 array_container_negation_range(AI, r_start, r_end, (void**)&BO);
1429 uint8_t result_typecode = (result_is_bitset ? BITSET_CONTAINER_TYPE_CODE
1430 : ARRAY_CONTAINER_TYPE_CODE);
1431
1432 int result_card = container_get_cardinality(BO, result_typecode);
1433
1434 assert_int_equal(is_bitset, result_is_bitset);
1435 assert_int_equal(result_size_should_be, result_card);
1436
1437 for (int x = 0; x < (1 << 16); x++) {
1438 bool should_be_present;
1439 if (x >= r_start && x < r_end)
1440 should_be_present = (x % 29 != 0);
1441 else
1442 should_be_present = (x % 29 == 0);
1443
1444#ifndef UNVERBOSE_MIXED_CONTAINER
1445 if (should_be_present !=
1446 container_contains(BO, (uint16_t)x, result_typecode))
1447 printf("oops on %d\n", x);
1448#endif
1449 assert_int_equal(container_contains(BO, (uint16_t)x, result_typecode),
1450 should_be_present);
1451 }
1452 container_free(BO, result_typecode);
1453 array_container_free(AI);
1454 return 1;
1455}
1456
1457/* result is a bitset. Range fits neatly in words */
1458void array_negation_range_test1() {
1459 array_negation_range_test(0x4000, 0xc000, true);
1460}
1461
1462/* result is a bitset. Range begins and ends mid word */
1463void array_negation_range_test1a() {
1464 array_negation_range_test(0x4010, 0xc010, true);
1465}
1466/* result is an array */
1467void array_negation_range_test2() {
1468 array_negation_range_test(0x7f00, 0x8030, false);
1469}
1470/* Empty range. result is a clone */
1471void array_negation_range_test3() {
1472 array_negation_range_test(0x7800, 0x7800, false);
1473}
1474
1475/* sparsity parameter 1=empty; k: every kth is NOT set; k=100 will
1476 * negate to
1477 * sparse */
1478static int bitset_negation_range_tests(int sparsity, int r_start, int r_end,
1479 bool is_bitset, bool inplace) {
1480 int ctr = 0;
1481 bitset_container_t* BI = bitset_container_create();
1482 void* BO;
1483 bool result_is_bitset;
1484 int result_size_should_be = 0;
1485
1486 for (int x = 0; x < (1 << 16); x++) {
1487 if (x % sparsity) bitset_container_add(BI, (uint16_t)x);
1488 ++ctr;
1489 }
1490
1491 for (int x = 0; x < (1 << 16); x++) {
1492 if (x >= r_start && x < r_end)
1493 if (x % sparsity == 0)
1494 result_size_should_be++;
1495 else {
1496 }
1497 else if (x % sparsity)
1498 result_size_should_be++;
1499 }
1500
1501 if (inplace)
1502 result_is_bitset = bitset_container_negation_range_inplace(
1503 BI, r_start, r_end, (void**)&BO);
1504 else
1505 result_is_bitset =
1506 bitset_container_negation_range(BI, r_start, r_end, (void**)&BO);
1507
1508 uint8_t result_typecode = (result_is_bitset ? BITSET_CONTAINER_TYPE_CODE
1509 : ARRAY_CONTAINER_TYPE_CODE);
1510
1511 int result_card = container_get_cardinality(BO, result_typecode);
1512
1513 assert_int_equal(is_bitset, result_is_bitset);
1514
1515 if (is_bitset && inplace) {
1516 assert_true(BO == BI); // it really is inplace
1517 } else {
1518 assert_false(BO == BI); // it better not be inplace
1519 }
1520
1521 assert_int_equal(result_size_should_be, result_card);
1522
1523 for (int x = 0; x < (1 << 16); x++) {
1524 bool should_be_present;
1525 if (x >= r_start && x < r_end)
1526 should_be_present = (x % sparsity == 0);
1527 else
1528 should_be_present = (x % sparsity != 0);
1529
1530#ifndef UNVERBOSE_MIXED_CONTAINER
1531 if (should_be_present !=
1532 container_contains(BO, (uint16_t)x, result_typecode))
1533 printf("oops on %d\n", x);
1534#endif
1535 assert_int_equal(container_contains(BO, (uint16_t)x, result_typecode),
1536 should_be_present);
1537 }
1538 container_free(BO, result_typecode);
1539 if (!inplace) bitset_container_free(BI);
1540 // for inplace: input is either output, or it was already freed
1541 // internally
1542
1543 return 1;
1544}
1545
1546/* result is a bitset */
1547void bitset_negation_range_test1() {
1548 // 33% density will be a bitmap and remain so after any range
1549 // negated
1550 bitset_negation_range_tests(3, 0x7f00, 0x8030, true, false);
1551}
1552
1553/* result is a array */
1554void bitset_negation_range_test2() {
1555 // 99% density will be a bitmap and become array when mostly flipped
1556 bitset_negation_range_tests(100, 0x080, 0xff80, false, false);
1557}
1558
1559/* inplace: result is a bitset */
1560void bitset_negation_range_inplace_test1() {
1561 // 33% density will be a bitmap and remain so after any range
1562 // negated
1563 bitset_negation_range_tests(3, 0x7f00, 0x8030, true, true);
1564}
1565
1566/* inplace: result is a array */
1567void bitset_negation_range_inplace_test2() {
1568 // 99% density will be a bitmap and become array when mostly flipped
1569 bitset_negation_range_tests(100, 0x080, 0xff80, false, true);
1570}
1571
1572/* specify how often runs start (k). Runs are length h, h+1, .. k-1, 1,
1573 * 2...*/
1574/* start_offset allows for data that begins outside a run */
1575
1576static int run_negation_range_tests(int k, int h, int start_offset, int r_start,
1577 int r_end, int expected_type, bool inplace,
1578 bool expected_actual_inplace) {
1579 int card = 0;
1580 run_container_t* RI =
1581 run_container_create_given_capacity((1 << 16) / k + 1);
1582 void* BO;
1583 int returned_type;
1584 int result_size_should_be;
1585 bool result_should_be[1 << 16];
1586
1587 assert(h < k); // bad test call otherwise..not failure of code under test
1588
1589 int runlen = h;
1590 for (int x = 0; x < (1 << 16) - start_offset; x++) {
1591 int offsetx = x + start_offset;
1592 if (x % k == 0) {
1593 int actual_runlen = runlen;
1594 if (offsetx + runlen > (1 << 16))
1595 actual_runlen = (1 << 16) - offsetx;
1596
1597 // run_container_append does not dynamically increase its
1598 // array
1599 run_container_append_first(
1600 RI, (rle16_t){.value = offsetx, .length = actual_runlen - 1});
1601 card += actual_runlen;
1602 if (++runlen == k) runlen = h; // wrap after k-1 back to h.
1603 }
1604 }
1605
1606 result_size_should_be = 0;
1607
1608 for (int i = 0; i < (1 << 16); ++i) {
1609 bool in_zone = (i >= r_start && i < r_end);
1610 if (run_container_contains(RI, (uint16_t)i) ^ in_zone) {
1611 result_should_be[i] = true;
1612 ++result_size_should_be;
1613 } else
1614 result_should_be[i] = false;
1615 }
1616 if (inplace)
1617 returned_type = run_container_negation_range_inplace(RI, r_start, r_end,
1618 (void**)&BO);
1619 else
1620 returned_type =
1621 run_container_negation_range(RI, r_start, r_end, (void**)&BO);
1622
1623 uint8_t result_typecode = (uint8_t)returned_type;
1624
1625 int result_card = container_get_cardinality(BO, result_typecode);
1626
1627 assert_int_equal(expected_type, returned_type);
1628
1629 if (expected_actual_inplace) {
1630 assert_true(BO == RI); // it really is inplace
1631 } else {
1632 assert_false(BO == RI); // it better not be inplace
1633 }
1634
1635 assert_int_equal(result_size_should_be, result_card);
1636
1637 for (int x = 0; x < (1 << 16); x++) {
1638#ifndef UNVERBOSE_MIXED_CONTAINER
1639 if (container_contains(BO, (uint16_t)x, result_typecode) !=
1640 result_should_be[x])
1641 printf("problem at index %d should be (but isnt) %d\n", x,
1642 (int)result_should_be[x]);
1643#endif
1644 assert_int_equal(container_contains(BO, (uint16_t)x, result_typecode),
1645 result_should_be[x]);
1646 }
1647 // assert_int_equal(result_size_should_be, result_card);
1648 container_free(BO, result_typecode);
1649 if (!inplace) run_container_free(RI);
1650 // for inplace: input is either output, or it was already freed
1651 // internally
1652
1653 return 1;
1654}
1655
1656/* Version that does not check whether return types and inplaceness are
1657 * right */
1658
1659static int run_negation_range_tests_simpler(int k, int h, int start_offset,
1660 int r_start, int r_end,
1661 bool inplace) {
1662 int card = 0;
1663 run_container_t* RI =
1664 run_container_create_given_capacity((1 << 16) / k + 1);
1665 void* BO;
1666 int returned_type;
1667 int result_size_should_be;
1668 bool result_should_be[1 << 16];
1669
1670 assert(h < k);
1671
1672 int runlen = h;
1673 for (int x = 0; x < (1 << 16) - start_offset; x++) {
1674 int offsetx = x + start_offset;
1675 if (x % k == 0) {
1676 int actual_runlen = runlen;
1677 if (offsetx + runlen > (1 << 16))
1678 actual_runlen = (1 << 16) - offsetx;
1679
1680 run_container_append_first(
1681 RI, (rle16_t){.value = offsetx, .length = actual_runlen - 1});
1682 card += actual_runlen;
1683 if (++runlen == k) runlen = h;
1684 }
1685 }
1686
1687 result_size_should_be = 0;
1688
1689 for (int i = 0; i < (1 << 16); ++i) {
1690 bool in_zone = (i >= r_start && i < r_end);
1691 if (run_container_contains(RI, (uint16_t)i) ^ in_zone) {
1692 result_should_be[i] = true;
1693 ++result_size_should_be;
1694 } else
1695 result_should_be[i] = false;
1696 }
1697 if (inplace)
1698 returned_type = run_container_negation_range_inplace(RI, r_start, r_end,
1699 (void**)&BO);
1700 else
1701 returned_type =
1702 run_container_negation_range(RI, r_start, r_end, (void**)&BO);
1703
1704 uint8_t result_typecode = (uint8_t)returned_type;
1705
1706 int result_card = container_get_cardinality(BO, result_typecode);
1707
1708 assert_int_equal(result_size_should_be, result_card);
1709
1710 for (int x = 0; x < (1 << 16); x++) {
1711#ifndef UNVERBOSE_MIXED_CONTAINER
1712 if (container_contains(BO, (uint16_t)x, result_typecode) !=
1713 result_should_be[x])
1714 printf("problem at index %d should be (but isnt) %d\n", x,
1715 (int)result_should_be[x]);
1716#endif
1717 assert_int_equal(container_contains(BO, (uint16_t)x, result_typecode),
1718 result_should_be[x]);
1719 }
1720 container_free(BO, result_typecode);
1721 if (!inplace) run_container_free(RI);
1722 return 1;
1723}
1724
1725static int run_many_negation_range_tests_simpler(bool inplace) {
1726 for (int h = 1; h < 100; h *= 3) {
1727 printf("h=%d\n", h);
1728 for (int k = h + 1; k < 100; k = k * 1.5 + 1) {
1729 printf(" k=%d\n", k);
1730 for (int start_offset = 0; start_offset < 1000;
1731 start_offset = start_offset * 2.7 + 1) {
1732 for (int r_start = 0; r_start < 65535; r_start += 10013)
1733 for (int span = 0; r_start + span < 65536;
1734 span = span * 3 + 1) {
1735 run_negation_range_tests_simpler(
1736 k, h, start_offset, r_start, r_start + span,
1737 inplace);
1738 }
1739 }
1740 }
1741 }
1742 return 1;
1743}
1744
1745void run_many_negation_range_tests_simpler_notinplace() {
1746 run_many_negation_range_tests_simpler(false);
1747}
1748
1749void run_many_negation_range_tests_simpler_inplace() {
1750 run_many_negation_range_tests_simpler(true);
1751}
1752
1753/* result is a bitset */
1754void run_negation_range_inplace_test1() {
1755 // runs of length 7, 8, 9 begin every 10
1756 // starting at 0.
1757 // (should not have been run encoded, but...)
1758 // last run starts at 65530 hence we end in a
1759 // run
1760 // negation over whole range. Result should be
1761 // bitset
1762
1763 run_negation_range_tests(10, 7, 0, 0x0000, 0x10000,
1764 BITSET_CONTAINER_TYPE_CODE, true,
1765 false); // request but don't get inplace
1766}
1767
1768void run_negation_range_inplace_test2() {
1769 // runs of length 7, 8, 9 begin every 10
1770 // starting at 1.
1771 // last run starts at 65531 hence we end in a
1772 // run
1773 // negation over whole range. Result should be
1774 // bitset
1775
1776 run_negation_range_tests(10, 7, 1, 0x0000, 0x10000,
1777 BITSET_CONTAINER_TYPE_CODE, true,
1778 false); // request but don't get inplace
1779}
1780
1781void run_negation_range_inplace_test3() {
1782 // runs of length 2,3,..9 begin every 10
1783 // starting at 1.
1784 // last run starts at 65531. Run length is (6553
1785 // % 8)+2 = 3.
1786 // So 65535 stores 0.
1787 // negation over whole range. Result should be
1788 // bitset
1789
1790 run_negation_range_tests(10, 2, 1, 0x0000, 0x10000,
1791 BITSET_CONTAINER_TYPE_CODE, true,
1792 false); // request but don't get inplace
1793}
1794
1795/* Results are going to be arrays*/
1796void run_negation_range_inplace_test4() {
1797 // runs of length 999 begin every 1000 starting
1798 // at 0.
1799 // last run starts at 65000 hence we end in a
1800 // run
1801 // negation over whole range.
1802 // Result should be array
1803
1804 run_negation_range_tests(1000, 999, 0, 0x0000, 0x10000,
1805 ARRAY_CONTAINER_TYPE_CODE, true,
1806 false); // request but don't get inplace
1807}
1808
1809void run_negation_range_inplace_test5() {
1810 // runs of length 999 begin every 10000 starting
1811 // at 1.
1812 // last run starts at 65001 hence we end in a
1813 // run.
1814 // negation over whole range. Result should be
1815 // bitset
1816
1817 run_negation_range_tests(1000, 999, 1, 0x0000, 0x10000,
1818 ARRAY_CONTAINER_TYPE_CODE, true,
1819 false); // request but don't get inplace
1820}
1821
1822void run_negation_range_inplace_test6() {
1823 // runs of length 999 begin every 10000 starting
1824 // at 536
1825 // last run starts at 64536.
1826 // So 65535 stores 0.
1827 // negation over whole range except some
1828 // initial. Result should be array
1829
1830 run_negation_range_tests(1000, 999, 536, 530, 0x10000,
1831 ARRAY_CONTAINER_TYPE_CODE, true,
1832 false); // request but don't get inplace
1833}
1834
1835/* Results are going to be runs*/
1836void run_negation_range_inplace_test7() {
1837 // short runs of length 2, 3, .. 67 begin every
1838 // 1000 starting at 550.
1839 // last run starts at 65550 hence we end in a
1840 // run.
1841 // negation over whole range. Result should be
1842 // run.
1843 // should always fit in the previous space
1844
1845 run_negation_range_tests(1000, 2, 550, 0x0000, 0x10000,
1846 RUN_CONTAINER_TYPE_CODE, true,
1847 true); // request and get inplace
1848}
1849
1850void run_negation_range_inplace_test8() {
1851 // runs of length 2..67 begin every 10000
1852 // starting at 0.
1853 // last run starts at 65000 hence we end outside
1854 // a run
1855 // negation over whole range. Result should be
1856 // run and will fit.
1857
1858 run_negation_range_tests(1000, 2, 0, 0x0000, 0x10000,
1859 RUN_CONTAINER_TYPE_CODE, true,
1860 true); // request, get inplace
1861}
1862
1863void run_negation_range_inplace_test9() {
1864 // runs of length 2..67 begin every 10000
1865 // starting at 1
1866 // last run starts at 64001.
1867 // So 65535 stores 0.
1868 // negation over whole range. Result should
1869 // have one run
1870 // more than original, and buffer happens to not
1871 // have any extra space.
1872
1873 run_negation_range_tests(1000, 2, 1, 0x0000, 0x10000,
1874 RUN_CONTAINER_TYPE_CODE, true,
1875 false); // request, but not get, inplace
1876}
1877
1878// now, 9 more tests that do not request inplace.
1879
1880/* result is a bitset */
1881void run_negation_range_test1() {
1882 // runs of length 7, 8, 9 begin every 10
1883 // starting at 0.
1884 // (should not have been run encoded, but...)
1885 // last run starts at 65530 hence we end in a
1886 // run
1887 // negation over whole range. Result should be
1888 // bitset
1889
1890 run_negation_range_tests(10, 7, 0, 0x0000, 0x10000,
1891 BITSET_CONTAINER_TYPE_CODE, false, false);
1892}
1893
1894void run_negation_range_test2() {
1895 // runs of length 7, 8, 9 begin every 10
1896 // starting at 1.
1897 // last run starts at 65531 hence we end in a
1898 // run
1899 // negation over whole range. Result should be
1900 // bitset
1901
1902 run_negation_range_tests(10, 7, 1, 0x0000, 0x10000,
1903 BITSET_CONTAINER_TYPE_CODE, false, false);
1904}
1905
1906void run_negation_range_test3() {
1907 // runs of length 2,3,..9 begin every 10
1908 // starting at 1.
1909 // last run starts at 65531. Run length is (6553
1910 // % 8)+2 = 3.
1911 // So 65535 stores 0.
1912 // negation over whole range. Result should be
1913 // bitset
1914
1915 run_negation_range_tests(10, 2, 1, 0x0000, 0x10000,
1916 BITSET_CONTAINER_TYPE_CODE, false,
1917 false); // request but don't get inplace
1918}
1919
1920/* Results are going to be arrays*/
1921void run_negation_range_test4() {
1922 // runs of length 999 begin every 1000 starting
1923 // at 0.
1924 // last run starts at 65000 hence we end in a
1925 // run
1926 // negation over whole range. Result should be
1927 // array
1928
1929 run_negation_range_tests(1000, 999, 0, 0x0000, 0x10000,
1930 ARRAY_CONTAINER_TYPE_CODE, false, false);
1931}
1932
1933void run_negation_range_test5() {
1934 // runs of length 999 begin every 10000 starting
1935 // at 1.
1936 // last run starts at 65001 hence we end in a
1937 // run
1938 // negation over whole range. Result should be
1939 // bitset
1940
1941 run_negation_range_tests(1000, 999, 1, 0x0000, 0x10000,
1942 ARRAY_CONTAINER_TYPE_CODE, false, false);
1943}
1944
1945void run_negation_range_test6() {
1946 // runs of length 999 begin every 10000 starting
1947 // at 536
1948 // last run starts at 64536.
1949 // So 65535 stores 0.
1950 // negation over whole range except initial
1951 // fragment. Result should be array
1952
1953 run_negation_range_tests(1000, 999, 536, 530, 0x10000,
1954 ARRAY_CONTAINER_TYPE_CODE, false, false);
1955}
1956
1957/* Results are going to be runs*/
1958void run_negation_range_test7() {
1959 // short runs of length 2, 3, .. 67 begin every
1960 // 1000 starting at 550.
1961 // last run starts at 65550 hence we end in a
1962 // run.
1963 // negation over whole range. Result should be
1964 // run.
1965 // should always fit in the previous space
1966
1967 run_negation_range_tests(1000, 2, 550, 0x0000, 0x10000,
1968 RUN_CONTAINER_TYPE_CODE, false, false);
1969}
1970
1971void run_negation_range_test8() {
1972 // runs of length 2..67 begin every 10000
1973 // starting at 0.
1974 // last run starts at 65000 hence we end outside
1975 // a run
1976 // negation over whole range. Result should be
1977 // run and will fit.
1978
1979 run_negation_range_tests(1000, 2, 0, 0x0000, 0x10000,
1980 RUN_CONTAINER_TYPE_CODE, false, false);
1981}
1982
1983void run_negation_range_test9() {
1984 // runs of length 2..67 begin every 10000
1985 // starting at 1
1986 // last run starts at 64001.
1987 // So 65535 stores 0.
1988 // negation over whole range. Result should be
1989 // have one run
1990 // more than original, but we think buffer will
1991 // usually have space :)
1992
1993 run_negation_range_tests(1000, 2, 1, 0x0000, 0x10000,
1994 RUN_CONTAINER_TYPE_CODE, false, false);
1995}
1996
1997int main() {
1998 const struct CMUnitTest tests[] = {
1999 cmocka_unit_test(array_bitset_and_or_xor_andnot_test),
2000 cmocka_unit_test(array_bitset_run_lazy_xor_test),
2001 cmocka_unit_test(run_xor_test),
2002 cmocka_unit_test(run_ixor_test),
2003 cmocka_unit_test(run_andnot_test),
2004 cmocka_unit_test(run_iandnot_test),
2005 cmocka_unit_test(run_array_andnot_bug_test),
2006 cmocka_unit_test(array_bitset_ixor_test),
2007 cmocka_unit_test(array_bitset_iandnot_test),
2008 cmocka_unit_test(array_negation_empty_test),
2009 cmocka_unit_test(array_negation_test),
2010 cmocka_unit_test(array_negation_range_test1),
2011 cmocka_unit_test(array_negation_range_test1a),
2012 cmocka_unit_test(array_negation_range_test2),
2013 cmocka_unit_test(array_negation_range_test3),
2014 cmocka_unit_test(bitset_negation_range_test1),
2015 cmocka_unit_test(bitset_negation_range_test2),
2016 cmocka_unit_test(bitset_negation_range_inplace_test1),
2017 cmocka_unit_test(bitset_negation_range_inplace_test2),
2018 cmocka_unit_test(run_negation_range_inplace_test1),
2019 cmocka_unit_test(run_negation_range_inplace_test2),
2020 cmocka_unit_test(run_negation_range_inplace_test3),
2021 cmocka_unit_test(run_negation_range_inplace_test4),
2022 cmocka_unit_test(run_negation_range_inplace_test5),
2023 cmocka_unit_test(run_negation_range_inplace_test6),
2024 cmocka_unit_test(run_negation_range_inplace_test7),
2025 cmocka_unit_test(run_negation_range_inplace_test8),
2026 cmocka_unit_test(run_negation_range_inplace_test9),
2027 cmocka_unit_test(run_negation_range_test1),
2028 cmocka_unit_test(run_negation_range_test2),
2029 cmocka_unit_test(run_negation_range_test3),
2030 cmocka_unit_test(run_negation_range_test4),
2031 cmocka_unit_test(run_negation_range_test5),
2032 cmocka_unit_test(run_negation_range_test6),
2033 cmocka_unit_test(run_negation_range_test7),
2034 cmocka_unit_test(run_negation_range_test8),
2035 cmocka_unit_test(run_negation_range_test9),
2036 /* two very expensive tests that probably should usually be
2037 omitted */
2038
2039 /*cmocka_unit_test(
2040 run_many_negation_range_tests_simpler_notinplace), // lots
2041 of
2042 //
2043 partial
2044 //
2045 ranges,
2046 cmocka_unit_test(run_many_negation_range_tests_simpler_inplace),*/
2047 /* */
2048 };
2049
2050 return cmocka_run_group_tests(tests, NULL, NULL);
2051}
2052