1#include <assert.h>
2#include <stdio.h>
3#include <stdlib.h>
4#include <string.h>
5#include <time.h>
6
7#include <roaring/roaring.h>
8
9#include "test.h"
10
11static unsigned int seed = 123456789;
12static const int OUR_RAND_MAX = (1 << 30) - 1;
13inline static unsigned int our_rand() { // we do not want to depend on a system-specific
14 // random number generator
15 seed = (1103515245 * seed + 12345);
16 return seed & OUR_RAND_MAX;
17}
18
19static inline uint32_t minimum_uint32(uint32_t a, uint32_t b) {
20 return (a < b) ? a : b;
21}
22
23// arrays expected to both be sorted.
24static int array_equals(uint32_t *a1, int32_t size1, uint32_t *a2,
25 int32_t size2) {
26 if (size1 != size2) return 0;
27 for (int i = 0; i < size1; ++i) {
28 if (a1[i] != a2[i]) {
29 return 0;
30 }
31 }
32 return 1;
33}
34
35bool roaring_iterator_sumall(uint32_t value, void *param) {
36 *(uint32_t *)param += value;
37 return true; // continue till the end
38}
39
40
41void range_contains() {
42 uint32_t end = 2073952257;
43 uint32_t start = end-2;
44 roaring_bitmap_t *bm = roaring_bitmap_from_range(start, end-1, 1);
45 roaring_bitmap_printf_describe(bm);printf("\n");
46 roaring_bitmap_contains_range(bm, start, end);
47 roaring_bitmap_free(bm);
48}
49
50void is_really_empty() {
51 roaring_bitmap_t *bm = roaring_bitmap_create();
52 assert_true(roaring_bitmap_is_empty(bm));
53 assert_false(roaring_bitmap_contains(bm, 0));
54 roaring_bitmap_free(bm);
55}
56
57void inplaceorwide() {
58 uint64_t end = 4294901761;
59 roaring_bitmap_t *r1 = roaring_bitmap_from_range(0,1,1);
60 roaring_bitmap_t *r2 = roaring_bitmap_from_range(0,end,1);
61 roaring_bitmap_or_inplace(r1, r2);
62 assert_true(roaring_bitmap_get_cardinality(r1) == end);
63 roaring_bitmap_free(r1);
64 roaring_bitmap_free(r2);
65}
66
67void can_copy_empty(bool copy_on_write) {
68 roaring_bitmap_t *bm1 = roaring_bitmap_create();
69 roaring_bitmap_set_copy_on_write(bm1, copy_on_write);
70 roaring_bitmap_t *bm2 = roaring_bitmap_copy(bm1);
71 assert(roaring_bitmap_get_cardinality(bm1) == 0);
72 assert(roaring_bitmap_get_cardinality(bm2) == 0);
73 assert(roaring_bitmap_is_empty(bm1));
74 assert(roaring_bitmap_is_empty(bm2));
75 roaring_bitmap_add(bm1, 3);
76 roaring_bitmap_add(bm2, 5);
77 assert(roaring_bitmap_get_cardinality(bm1) == 1);
78 assert(roaring_bitmap_get_cardinality(bm2) == 1);
79 assert(roaring_bitmap_contains(bm1,3));
80 assert(roaring_bitmap_contains(bm2,5));
81 assert(!roaring_bitmap_contains(bm2,3));
82 assert(!roaring_bitmap_contains(bm1,5));
83 roaring_bitmap_free(bm1);
84 roaring_bitmap_free(bm2);
85}
86
87void issue208() {
88 roaring_bitmap_t *r = roaring_bitmap_create();
89 for (uint32_t i = 1; i < 8194; i+=2) {
90 roaring_bitmap_add(r, i);
91 }
92 uint32_t rank = roaring_bitmap_rank(r, 63);
93 assert(rank == 32);
94 roaring_bitmap_free(r);
95}
96
97void issue208b() {
98 roaring_bitmap_t *r = roaring_bitmap_create();
99 for (uint32_t i = 65536 - 64; i < 65536; i++) {
100 roaring_bitmap_add(r, i);
101 }
102 for (uint32_t i = 0; i < 8196; i+=2) {
103 roaring_bitmap_add(r, i);
104 }
105 for (uint32_t i = 65536 - 64; i < 65536; i++) {
106 uint32_t expected = i - (65536 - 64) + 8196 / 2 + 1;
107 uint32_t rank = roaring_bitmap_rank(r, i);
108 assert(rank == expected);
109 }
110 roaring_bitmap_free(r);
111}
112
113
114void can_copy_empty_true() {
115 can_copy_empty(true);
116}
117
118void can_copy_empty_false() {
119 can_copy_empty(false);
120}
121
122void can_add_to_copies(bool copy_on_write) {
123 roaring_bitmap_t *bm1 = roaring_bitmap_create();
124 roaring_bitmap_set_copy_on_write(bm1, copy_on_write);
125 roaring_bitmap_add(bm1, 3);
126 roaring_bitmap_t *bm2 = roaring_bitmap_copy(bm1);
127 assert(roaring_bitmap_get_cardinality(bm1) == 1);
128 assert(roaring_bitmap_get_cardinality(bm2) == 1);
129 roaring_bitmap_add(bm2, 4);
130 roaring_bitmap_add(bm1, 5);
131 assert(roaring_bitmap_get_cardinality(bm1) == 2);
132 assert(roaring_bitmap_get_cardinality(bm2) == 2);
133 roaring_bitmap_free(bm1);
134 roaring_bitmap_free(bm2);
135}
136
137void convert_all_containers(roaring_bitmap_t* r, uint8_t dst_type) {
138 for (int32_t i = 0; i < r->high_low_container.size; i++) {
139 // first step: convert src_type to ARRAY
140 if (r->high_low_container.typecodes[i] == BITSET_CONTAINER_TYPE_CODE) {
141 array_container_t* dst_container = array_container_from_bitset(r->high_low_container.containers[i]);
142 bitset_container_free(r->high_low_container.containers[i]);
143 r->high_low_container.containers[i] = dst_container;
144 r->high_low_container.typecodes[i] = ARRAY_CONTAINER_TYPE_CODE;
145 } else if (r->high_low_container.typecodes[i] == RUN_CONTAINER_TYPE_CODE) {
146 array_container_t* dst_container = array_container_from_run(r->high_low_container.containers[i]);
147 run_container_free(r->high_low_container.containers[i]);
148 r->high_low_container.containers[i] = dst_container;
149 r->high_low_container.typecodes[i] = ARRAY_CONTAINER_TYPE_CODE;
150 }
151 assert(r->high_low_container.typecodes[i] == ARRAY_CONTAINER_TYPE_CODE);
152
153 // second step: convert ARRAY to dst_type
154 if (dst_type == BITSET_CONTAINER_TYPE_CODE) {
155 bitset_container_t* dst_container = bitset_container_from_array(r->high_low_container.containers[i]);
156 array_container_free(r->high_low_container.containers[i]);
157 r->high_low_container.containers[i] = dst_container;
158 r->high_low_container.typecodes[i] = BITSET_CONTAINER_TYPE_CODE;
159 } else if (dst_type == RUN_CONTAINER_TYPE_CODE) {
160 run_container_t* dst_container = run_container_from_array(r->high_low_container.containers[i]);
161 array_container_free(r->high_low_container.containers[i]);
162 r->high_low_container.containers[i] = dst_container;
163 r->high_low_container.typecodes[i] = RUN_CONTAINER_TYPE_CODE;
164 }
165 assert(r->high_low_container.typecodes[i] == dst_type);
166 }
167}
168
169/*
170 * Tiny framework to compare roaring bitmap vs reference implementation
171 * side by side
172 */
173struct sbs_s {
174 roaring_bitmap_t *roaring;
175
176 // reference implementation
177 uint64_t *words;
178 uint32_t size; // number of words
179};
180typedef struct sbs_s sbs_t;
181
182sbs_t *sbs_create() {
183 sbs_t *sbs = malloc(sizeof(sbs_t));
184 sbs->roaring = roaring_bitmap_create();
185 sbs->size = 1;
186 sbs->words = malloc(sbs->size * sizeof(uint64_t));
187 for (uint32_t i = 0; i < sbs->size; i++) {
188 sbs->words[i] = 0;
189 }
190 return sbs;
191}
192
193void sbs_free(sbs_t *sbs) {
194 roaring_bitmap_free(sbs->roaring);
195 free(sbs->words);
196 free(sbs);
197}
198
199void sbs_convert(sbs_t *sbs, uint8_t code) {
200 convert_all_containers(sbs->roaring, code);
201}
202
203void sbs_ensure_room(sbs_t *sbs, uint32_t v) {
204 uint32_t i = v / 64;
205 if (i >= sbs->size) {
206 uint32_t new_size = (i+1) * 3 / 2;
207 sbs->words = realloc(sbs->words, new_size*sizeof(uint64_t));
208 for (uint32_t j = sbs->size; j < new_size; j++) {
209 sbs->words[j] = 0;
210 }
211 sbs->size = new_size;
212 }
213}
214
215void sbs_add_value(sbs_t *sbs, uint32_t v) {
216 roaring_bitmap_add(sbs->roaring, v);
217
218 sbs_ensure_room(sbs, v);
219 sbs->words[v/64] |= UINT64_C(1) << (v % 64);
220}
221
222void sbs_add_range(sbs_t *sbs, uint64_t min, uint64_t max) {
223 sbs_ensure_room(sbs, max);
224 for (uint64_t v = min; v <= max; v++) {
225 sbs->words[v/64] |= UINT64_C(1) << (v % 64);
226 }
227
228 roaring_bitmap_add_range(sbs->roaring, min, max + 1);
229}
230
231void sbs_remove_range(sbs_t *sbs, uint64_t min, uint64_t max) {
232 sbs_ensure_room(sbs, max);
233 for (uint64_t v = min; v <= max; v++) {
234 sbs->words[v/64] &= ~(UINT64_C(1) << (v % 64));
235 }
236
237 roaring_bitmap_remove_range(sbs->roaring, min, max + 1);
238}
239
240void sbs_remove_many(sbs_t *sbs, size_t n_args, uint32_t *vals) {
241 for (size_t i = 0; i < n_args; i++) {
242 uint32_t v = vals[i];
243 sbs_ensure_room(sbs, v);
244 sbs->words[v/64] &= ~(UINT64_C(1) << (v % 64));
245 }
246 roaring_bitmap_remove_many(sbs->roaring, n_args, vals);
247}
248
249bool sbs_check_type(sbs_t *sbs, uint8_t type) {
250 bool answer = true;
251 for (int32_t i = 0; i < sbs->roaring->high_low_container.size; i++) {
252 answer = answer && (sbs->roaring->high_low_container.typecodes[i] == type);
253 }
254 return answer;
255}
256
257bool sbs_is_empty(sbs_t *sbs) {
258 return sbs->roaring->high_low_container.size == 0;
259}
260
261void sbs_compare(sbs_t *sbs) {
262 uint32_t expected_cardinality = 0;
263 for (uint32_t i = 0; i < sbs->size; i++) {
264 uint64_t word = sbs->words[i];
265 while (word != 0) {
266 expected_cardinality += 1;
267 word = word & (word - 1);
268 }
269 }
270 uint32_t *expected_values = malloc(expected_cardinality * sizeof(uint32_t));
271 memset(expected_values, 0, expected_cardinality * sizeof(uint32_t));
272 for (uint32_t i = 0, dst = 0; i < sbs->size; i++) {
273 for (uint32_t j = 0; j < 64; j++) {
274 if ((sbs->words[i] & (UINT64_C(1) << j)) != 0) {
275 expected_values[dst++] = i*64 + j;
276 }
277 }
278 }
279
280 uint32_t actual_cardinality = roaring_bitmap_get_cardinality(sbs->roaring);
281 uint32_t *actual_values = malloc(actual_cardinality * sizeof(uint32_t));
282 memset(actual_values, 0, actual_cardinality * sizeof(uint32_t));
283 roaring_bitmap_to_uint32_array(sbs->roaring, actual_values);
284
285 bool ok = array_equals(actual_values, actual_cardinality,
286 expected_values, expected_cardinality);
287 if (!ok) {
288 printf("Expected: ");
289 for (uint32_t i = 0; i < expected_cardinality; i++) {
290 printf("%u ", expected_values[i]);
291 }
292 printf("\n");
293
294 printf("Actual: ");
295 roaring_bitmap_printf(sbs->roaring);
296 printf("\n");
297 }
298 free(actual_values);
299 free(expected_values);
300 assert_true(ok);
301}
302
303void test_stats() {
304 // create a new empty bitmap
305 roaring_bitmap_t *r1 = roaring_bitmap_create();
306 assert_non_null(r1);
307 // then we can add values
308 for (uint32_t i = 100; i < 1000; i++) {
309 roaring_bitmap_add(r1, i);
310 }
311 for (uint32_t i = 1000; i < 100000; i += 10) {
312 roaring_bitmap_add(r1, i);
313 }
314 roaring_bitmap_add(r1, 100000);
315
316 roaring_statistics_t stats;
317 roaring_bitmap_statistics(r1, &stats);
318 assert_true(stats.cardinality == roaring_bitmap_get_cardinality(r1));
319 assert_true(stats.min_value == 100);
320 assert_true(stats.max_value == 100000);
321 roaring_bitmap_free(r1);
322}
323
324// this should expose memory leaks
325// (https://github.com/RoaringBitmap/CRoaring/pull/70)
326void leaks_with_empty(bool copy_on_write) {
327 roaring_bitmap_t *empty = roaring_bitmap_create();
328 roaring_bitmap_set_copy_on_write(empty, copy_on_write);
329 roaring_bitmap_t *r1 = roaring_bitmap_create();
330 roaring_bitmap_set_copy_on_write(r1, copy_on_write);
331 for (uint32_t i = 100; i < 70000; i += 3) {
332 roaring_bitmap_add(r1, i);
333 }
334 roaring_bitmap_t *ror = roaring_bitmap_or(r1, empty);
335 roaring_bitmap_t *rxor = roaring_bitmap_xor(r1, empty);
336 roaring_bitmap_t *rand = roaring_bitmap_and(r1, empty);
337 roaring_bitmap_t *randnot = roaring_bitmap_andnot(r1, empty);
338 roaring_bitmap_free(empty);
339 assert_true(roaring_bitmap_equals(ror, r1));
340 roaring_bitmap_free(ror);
341 assert_true(roaring_bitmap_equals(rxor, r1));
342 roaring_bitmap_free(rxor);
343 assert_true(roaring_bitmap_equals(randnot, r1));
344 roaring_bitmap_free(randnot);
345 roaring_bitmap_free(r1);
346 assert_true(roaring_bitmap_is_empty(rand));
347 roaring_bitmap_free(rand);
348}
349
350void leaks_with_empty_true() { leaks_with_empty(true); }
351
352void leaks_with_empty_false() { leaks_with_empty(false); }
353
354void check_interval() {
355 // create a new bitmap with varargs
356 roaring_bitmap_t *r = roaring_bitmap_of(4, 1, 2, 3, 1000);
357 assert_non_null(r);
358
359 roaring_bitmap_printf(r);
360
361
362 roaring_bitmap_t *range = roaring_bitmap_from_range(10, 1000+1, 1);
363 assert_non_null(range);
364 assert_true(roaring_bitmap_intersect(r,range));
365 roaring_bitmap_t *range2 = roaring_bitmap_from_range(10, 1000, 1);
366 assert_non_null(range2);
367 assert_false(roaring_bitmap_intersect(r,range2));
368
369 roaring_bitmap_free(r);
370 roaring_bitmap_free(range);
371 roaring_bitmap_free(range2);
372
373}
374
375void check_full_inplace_flip() {
376 roaring_bitmap_t *r1 = roaring_bitmap_create();
377 uint64_t bignumber = UINT64_C(0x100000000);
378 roaring_bitmap_flip_inplace(r1, 0, bignumber);
379 assert_true(roaring_bitmap_get_cardinality(r1) == bignumber);
380 roaring_bitmap_free(r1);
381}
382
383void check_iterate_to_end() {
384 uint64_t bignumber = UINT64_C(0x100000000);
385 for(uint64_t s = 0; s < 1024; s++) {
386 roaring_bitmap_t *r1 = roaring_bitmap_create();
387 roaring_bitmap_flip_inplace(r1, bignumber - s, bignumber);
388 roaring_uint32_iterator_t iterator;
389 roaring_init_iterator(r1, &iterator);
390 uint64_t count = 0;
391 while(iterator.has_value) {
392 assert(iterator.current_value + (s - count) == bignumber);
393 count++;
394 roaring_advance_uint32_iterator(&iterator);
395 }
396 assert_true(count == s);
397 assert_true(roaring_bitmap_get_cardinality(r1) == s);
398 roaring_bitmap_free(r1);
399 }
400}
401
402void check_iterate_to_beginning() {
403 uint64_t bignumber = UINT64_C(0x100000000);
404 for(uint64_t s = 0; s < 1024; s++) {
405 roaring_bitmap_t *r1 = roaring_bitmap_create();
406 roaring_bitmap_flip_inplace(r1, bignumber - s, bignumber);
407 roaring_uint32_iterator_t iterator;
408 roaring_init_iterator_last(r1, &iterator);
409 uint64_t count = 0;
410 while(iterator.has_value) {
411 count++;
412 assert(iterator.current_value + count == bignumber);
413 roaring_previous_uint32_iterator(&iterator);
414 }
415 assert_true(count == s);
416 assert_true(roaring_bitmap_get_cardinality(r1) == s);
417 roaring_bitmap_free(r1);
418 }
419}
420
421void check_range_contains_from_end() {
422 uint64_t bignumber = UINT64_C(0x100000000);
423 for(uint64_t s = 0; s < 1024 * 1024; s++) {
424 roaring_bitmap_t *r1 = roaring_bitmap_create();
425 roaring_bitmap_add_range(r1, bignumber - s, bignumber);
426 assert_true(roaring_bitmap_get_cardinality(r1) == s);
427 if(s>0) {
428 assert_true(roaring_bitmap_contains_range(r1, bignumber - s, bignumber - 1));
429 }
430 assert_true(roaring_bitmap_contains_range(r1, bignumber - s, bignumber));
431 assert_false(roaring_bitmap_contains_range(r1, bignumber - s - 1, bignumber));
432 assert_true(roaring_bitmap_get_cardinality(r1) == s);
433 roaring_bitmap_free(r1);
434 }
435}
436
437void check_full_flip() {
438 roaring_bitmap_t *rorg = roaring_bitmap_create();
439 uint64_t bignumber = UINT64_C(0x100000000);
440 roaring_bitmap_t *r1 = roaring_bitmap_flip(rorg, 0, bignumber);
441 assert_true(roaring_bitmap_get_cardinality(r1) == bignumber);
442 roaring_bitmap_free(r1);
443 roaring_bitmap_free(rorg);
444}
445
446void test_stress_memory(bool copy_on_write) {
447 for (size_t i = 0; i < 5; i++) {
448 roaring_bitmap_t *r1 = roaring_bitmap_create();
449 roaring_bitmap_set_copy_on_write(r1, copy_on_write);
450 assert_non_null(r1);
451 for (size_t k = 0; k < 1000000; k++) {
452 uint32_t j = rand() % (100000000);
453 roaring_bitmap_add(r1, j);
454 }
455 roaring_bitmap_run_optimize(r1);
456 uint32_t compact_size = roaring_bitmap_portable_size_in_bytes(r1);
457 char * serializedbytes = (char *) malloc(compact_size);
458 size_t actualsize = roaring_bitmap_portable_serialize(r1, serializedbytes);
459 assert_int_equal(actualsize, compact_size);
460 roaring_bitmap_t *t = roaring_bitmap_portable_deserialize(serializedbytes);
461 assert_true(roaring_bitmap_equals(r1, t));
462 roaring_bitmap_free(t);
463 free(serializedbytes);
464 roaring_bitmap_free(r1);
465 }
466}
467
468void test_stress_memory_true() {
469 test_stress_memory(true);
470}
471
472void test_stress_memory_false() {
473 test_stress_memory(false);
474}
475
476
477void test_example(bool copy_on_write) {
478 // create a new empty bitmap
479 roaring_bitmap_t *r1 = roaring_bitmap_create();
480 roaring_bitmap_set_copy_on_write(r1, copy_on_write);
481 assert_non_null(r1);
482
483 // then we can add values
484 for (uint32_t i = 100; i < 1000; i++) {
485 roaring_bitmap_add(r1, i);
486 }
487
488 // check whether a value is contained
489 assert_true(roaring_bitmap_contains(r1, 500));
490
491 // compute how many bits there are:
492 uint32_t cardinality = roaring_bitmap_get_cardinality(r1);
493 printf("Cardinality = %d \n", cardinality);
494
495 // if your bitmaps have long runs, you can compress them by calling
496 // run_optimize
497 uint32_t size = roaring_bitmap_portable_size_in_bytes(r1);
498 roaring_bitmap_run_optimize(r1);
499 uint32_t compact_size = roaring_bitmap_portable_size_in_bytes(r1);
500
501 printf("size before run optimize %d bytes, and after %d bytes\n", size,
502 compact_size);
503
504 // create a new bitmap with varargs
505 roaring_bitmap_t *r2 = roaring_bitmap_of(5, 1, 2, 3, 5, 6);
506 assert_non_null(r2);
507
508 roaring_bitmap_printf(r2);
509
510 // we can also create a bitmap from a pointer to 32-bit integers
511 const uint32_t values[] = {2, 3, 4};
512 roaring_bitmap_t *r3 = roaring_bitmap_of_ptr(3, values);
513 roaring_bitmap_set_copy_on_write(r3, copy_on_write);
514
515 // we can also go in reverse and go from arrays to bitmaps
516 uint64_t card1 = roaring_bitmap_get_cardinality(r1);
517 uint32_t *arr1 = (uint32_t *)malloc(card1 * sizeof(uint32_t));
518 assert(arr1 != NULL);
519 roaring_bitmap_to_uint32_array(r1, arr1);
520
521 // we can go from arrays to bitmaps from "offset" by "limit"
522 size_t offset = 100;
523 size_t limit = 1000;
524 uint32_t *arr3 = (uint32_t *)malloc(limit * sizeof(uint32_t));
525 assert(arr3 != NULL);
526 roaring_bitmap_range_uint32_array(r1, offset, limit, arr3);
527 free(arr3);
528
529
530 roaring_bitmap_t *r1f = roaring_bitmap_of_ptr(card1, arr1);
531 free(arr1);
532 assert_non_null(r1f);
533
534 // bitmaps shall be equal
535 assert_true(roaring_bitmap_equals(r1, r1f));
536 roaring_bitmap_free(r1f);
537
538 // we can copy and compare bitmaps
539 roaring_bitmap_t *z = roaring_bitmap_copy(r3);
540 roaring_bitmap_set_copy_on_write(z, copy_on_write);
541 assert_true(roaring_bitmap_equals(r3, z));
542
543 roaring_bitmap_free(z);
544
545 // we can compute union two-by-two
546 roaring_bitmap_t *r1_2_3 = roaring_bitmap_or(r1, r2);
547 assert_true(roaring_bitmap_get_cardinality(r1_2_3) ==
548 roaring_bitmap_or_cardinality(r1, r2));
549
550 roaring_bitmap_set_copy_on_write(r1_2_3, copy_on_write);
551 roaring_bitmap_or_inplace(r1_2_3, r3);
552
553 // we can compute a big union
554 const roaring_bitmap_t *allmybitmaps[] = {r1, r2, r3};
555 roaring_bitmap_t *bigunion = roaring_bitmap_or_many(3, allmybitmaps);
556 assert_true(roaring_bitmap_equals(r1_2_3, bigunion));
557 roaring_bitmap_t *bigunionheap =
558 roaring_bitmap_or_many_heap(3, allmybitmaps);
559 assert_true(roaring_bitmap_equals(r1_2_3, bigunionheap));
560 roaring_bitmap_free(r1_2_3);
561 roaring_bitmap_free(bigunion);
562 roaring_bitmap_free(bigunionheap);
563
564 // we can compute xor two-by-two
565 roaring_bitmap_t *rx1_2_3 = roaring_bitmap_xor(r1, r2);
566 roaring_bitmap_set_copy_on_write(rx1_2_3, copy_on_write);
567 roaring_bitmap_xor_inplace(rx1_2_3, r3);
568
569 // we can compute a big xor
570 const roaring_bitmap_t *allmybitmaps_x[] = {r1, r2, r3};
571 roaring_bitmap_t *bigxor = roaring_bitmap_xor_many(3, allmybitmaps_x);
572 assert_true(roaring_bitmap_equals(rx1_2_3, bigxor));
573
574 roaring_bitmap_free(rx1_2_3);
575 roaring_bitmap_free(bigxor);
576
577 // we can compute intersection two-by-two
578 roaring_bitmap_t *i1_2 = roaring_bitmap_and(r1, r2);
579 assert_true(roaring_bitmap_get_cardinality(i1_2) ==
580 roaring_bitmap_and_cardinality(r1, r2));
581
582 roaring_bitmap_free(i1_2);
583
584 // we can write a bitmap to a pointer and recover it later
585 uint32_t expectedsize = roaring_bitmap_portable_size_in_bytes(r1);
586 char *serializedbytes = malloc(expectedsize);
587 size_t actualsize = roaring_bitmap_portable_serialize(r1, serializedbytes);
588 assert_int_equal(actualsize, expectedsize);
589 roaring_bitmap_t *t = roaring_bitmap_portable_deserialize(serializedbytes);
590 assert_true(roaring_bitmap_equals(r1, t));
591 roaring_bitmap_free(t);
592 // we can also check whether there is a bitmap at a memory location without reading it
593 size_t sizeofbitmap = roaring_bitmap_portable_deserialize_size(serializedbytes,expectedsize);
594 assert(sizeofbitmap == expectedsize); // sizeofbitmap would be zero if no bitmap were found
595 // we can also read the bitmap "safely" by specifying a byte size limit:
596 t = roaring_bitmap_portable_deserialize_safe(serializedbytes,expectedsize);
597 assert(roaring_bitmap_equals(r1, t)); // what we recover is equal
598 roaring_bitmap_free(t);
599 free(serializedbytes);
600
601 // we can iterate over all values using custom functions
602 uint32_t counter = 0;
603 roaring_iterate(r1, roaring_iterator_sumall, &counter);
604
605 /**
606 * bool roaring_iterator_sumall(uint32_t value, void *param) {
607 * *(uint32_t *) param += value;
608 * return true; // continue till the end
609 * }
610 *
611 */
612
613 // we can also create iterator structs
614 counter = 0;
615 roaring_uint32_iterator_t *i = roaring_create_iterator(r1);
616 while (i->has_value) {
617 counter++;
618 roaring_advance_uint32_iterator(i);
619 }
620 roaring_free_uint32_iterator(i);
621 assert_true(roaring_bitmap_get_cardinality(r1) == counter);
622
623
624 // for greater speed, you can iterate over the data in bulk
625 i = roaring_create_iterator(r1);
626 uint32_t buffer[256];
627 while (1) {
628 uint32_t ret = roaring_read_uint32_iterator(i, buffer, 256);
629 for (uint32_t j = 0; j < ret; j++) {
630 counter += buffer[j];
631 }
632 if (ret < 256) {
633 break;
634 }
635 }
636 roaring_free_uint32_iterator(i);
637
638 roaring_bitmap_free(r1);
639 roaring_bitmap_free(r2);
640 roaring_bitmap_free(r3);
641}
642
643void test_uint32_iterator(bool run) {
644 roaring_bitmap_t *r1 = roaring_bitmap_create();
645 for (uint32_t i = 0; i < 66000; i += 3) {
646 roaring_bitmap_add(r1, i);
647 }
648 for (uint32_t i = 100000; i < 200000; i++) {
649 roaring_bitmap_add(r1, i);
650 }
651 for (uint32_t i = 300000; i < 500000; i += 100) {
652 roaring_bitmap_add(r1, i);
653 }
654 for (uint32_t i = 600000; i < 700000; i += 1) {
655 roaring_bitmap_add(r1, i);
656 }
657 for (uint32_t i = 800000; i < 900000; i += 7) {
658 roaring_bitmap_add(r1, i);
659 }
660 if(run) roaring_bitmap_run_optimize(r1);
661 roaring_uint32_iterator_t *iter = roaring_create_iterator(r1);
662 for (uint32_t i = 0; i < 66000; i += 3) {
663 assert_true(iter->has_value);
664 assert_true(iter->current_value == i);
665 roaring_move_uint32_iterator_equalorlarger(iter,i);
666 assert_true(iter->has_value);
667 assert_true(iter->current_value == i);
668 roaring_advance_uint32_iterator(iter);
669 }
670 for (uint32_t i = 100000; i < 200000; i++) {
671 assert_true(iter->has_value);
672 assert_true(iter->current_value == i);
673 roaring_move_uint32_iterator_equalorlarger(iter,i);
674 assert_true(iter->has_value);
675 assert_true(iter->current_value == i);
676 roaring_advance_uint32_iterator(iter);
677 }
678 for (uint32_t i = 300000; i < 500000; i += 100) {
679 assert_true(iter->has_value);
680 assert_true(iter->current_value == i);
681 roaring_move_uint32_iterator_equalorlarger(iter,i);
682 assert_true(iter->has_value);
683 assert_true(iter->current_value == i);
684 roaring_advance_uint32_iterator(iter);
685 }
686 for (uint32_t i = 600000; i < 700000; i += 1) {
687 assert_true(iter->has_value);
688 assert_true(iter->current_value == i);
689 roaring_move_uint32_iterator_equalorlarger(iter,i);
690 assert_true(iter->has_value);
691 assert_true(iter->current_value == i);
692 roaring_advance_uint32_iterator(iter);
693 }
694 for (uint32_t i = 800000; i < 900000; i += 7) {
695 assert_true(iter->has_value);
696 assert_true(iter->current_value == i);
697 roaring_move_uint32_iterator_equalorlarger(iter,i);
698 assert_true(iter->has_value);
699 assert_true(iter->current_value == i);
700 roaring_advance_uint32_iterator(iter);
701 }
702 assert_false(iter->has_value);
703 roaring_move_uint32_iterator_equalorlarger(iter,0);
704 assert_true(iter->has_value);
705 assert_true(iter->current_value == 0);
706 roaring_move_uint32_iterator_equalorlarger(iter,66000);
707 assert_true(iter->has_value);
708 assert_true(iter->current_value == 100000);
709 roaring_move_uint32_iterator_equalorlarger(iter,100000);
710 assert_true(iter->has_value);
711 assert_true(iter->current_value == 100000);
712 roaring_move_uint32_iterator_equalorlarger(iter,200000);
713 assert_true(iter->has_value);
714 assert_true(iter->current_value == 300000);
715 roaring_move_uint32_iterator_equalorlarger(iter,300000);
716 assert_true(iter->has_value);
717 assert_true(iter->current_value == 300000);
718 roaring_move_uint32_iterator_equalorlarger(iter,500000);
719 assert_true(iter->has_value);
720 assert_true(iter->current_value == 600000);
721 roaring_move_uint32_iterator_equalorlarger(iter,600000);
722 assert_true(iter->has_value);
723 assert_true(iter->current_value == 600000);
724 roaring_move_uint32_iterator_equalorlarger(iter,700000);
725 assert_true(iter->has_value);
726 assert_true(iter->current_value == 800000);
727 roaring_move_uint32_iterator_equalorlarger(iter,800000);
728 assert_true(iter->has_value);
729 assert_true(iter->current_value == 800000);
730 roaring_move_uint32_iterator_equalorlarger(iter,900000);
731 assert_false(iter->has_value);
732 roaring_move_uint32_iterator_equalorlarger(iter,0);
733 for (uint32_t i = 0; i < 66000; i += 3) {
734 assert_true(iter->has_value);
735 assert_true(iter->current_value == i);
736 roaring_move_uint32_iterator_equalorlarger(iter,i+1);
737 }
738 for (uint32_t i = 100000; i < 200000; i++) {
739 assert_true(iter->has_value);
740 assert_true(iter->current_value == i);
741 roaring_move_uint32_iterator_equalorlarger(iter,i+1);
742 }
743 for (uint32_t i = 300000; i < 500000; i += 100) {
744 assert_true(iter->has_value);
745 assert_true(iter->current_value == i);
746 roaring_move_uint32_iterator_equalorlarger(iter,i+1);
747 }
748 for (uint32_t i = 600000; i < 700000; i += 1) {
749 assert_true(iter->has_value);
750 assert_true(iter->current_value == i);
751 roaring_move_uint32_iterator_equalorlarger(iter,i+1);
752 }
753 for (uint32_t i = 800000; i < 900000; i += 7) {
754 assert_true(iter->has_value);
755 assert_true(iter->current_value == i);
756 roaring_move_uint32_iterator_equalorlarger(iter,i+1);
757 }
758 assert_false(iter->has_value);
759
760 roaring_free_uint32_iterator(iter);
761 roaring_bitmap_free(r1);
762}
763
764void test_uint32_iterator_true() { test_uint32_iterator(true); }
765
766void test_uint32_iterator_false() { test_uint32_iterator(false); }
767
768void test_example_true() { test_example(true); }
769
770void test_example_false() { test_example(false); }
771
772void can_remove_from_copies(bool copy_on_write) {
773 roaring_bitmap_t *bm1 = roaring_bitmap_create();
774 roaring_bitmap_set_copy_on_write(bm1, copy_on_write);
775 roaring_bitmap_add(bm1, 3);
776 roaring_bitmap_t *bm2 = roaring_bitmap_copy(bm1);
777 assert(roaring_bitmap_get_cardinality(bm1) == 1);
778 assert(roaring_bitmap_get_cardinality(bm2) == 1);
779 roaring_bitmap_add(bm2, 4);
780 roaring_bitmap_add(bm1, 5);
781 assert(roaring_bitmap_get_cardinality(bm1) == 2);
782 assert(roaring_bitmap_get_cardinality(bm2) == 2);
783 roaring_bitmap_remove(bm1, 5);
784 assert(roaring_bitmap_get_cardinality(bm1) == 1);
785 roaring_bitmap_remove(bm1, 4);
786 assert(roaring_bitmap_get_cardinality(bm1) == 1);
787 assert(roaring_bitmap_get_cardinality(bm2) == 2);
788 roaring_bitmap_remove(bm2, 4);
789 assert(roaring_bitmap_get_cardinality(bm2) == 1);
790 roaring_bitmap_free(bm1);
791 roaring_bitmap_free(bm2);
792}
793
794void test_basic_add() {
795 roaring_bitmap_t *bm = roaring_bitmap_create();
796 roaring_bitmap_add(bm, 0);
797 roaring_bitmap_remove(bm, 0);
798 roaring_bitmap_free(bm);
799}
800
801void test_addremove() {
802 roaring_bitmap_t *bm = roaring_bitmap_create();
803 for (uint32_t value = 33057; value < 147849; value += 8) {
804 roaring_bitmap_add(bm, value);
805 }
806 for (uint32_t value = 33057; value < 147849; value += 8) {
807 roaring_bitmap_remove(bm, value);
808 }
809 assert_true(roaring_bitmap_is_empty(bm));
810 roaring_bitmap_free(bm);
811}
812
813void test_addremoverun() {
814 roaring_bitmap_t *bm = roaring_bitmap_create();
815 for (uint32_t value = 33057; value < 147849; value += 8) {
816 roaring_bitmap_add(bm, value);
817 }
818 roaring_bitmap_run_optimize(bm);
819 for (uint32_t value = 33057; value < 147849; value += 8) {
820 roaring_bitmap_remove(bm, value);
821 }
822 assert_true(roaring_bitmap_is_empty(bm));
823 roaring_bitmap_free(bm);
824}
825
826void test_clear() {
827 roaring_bitmap_t *bm = roaring_bitmap_create();
828 for (uint32_t value = 33057; value < 147849; value += 8) {
829 roaring_bitmap_add(bm, value);
830 }
831 roaring_bitmap_clear(bm);
832 assert_true(roaring_bitmap_is_empty(bm));
833 size_t expected_card = 0;
834 for (uint32_t value = 33057; value < 147849; value += 8) {
835 roaring_bitmap_add(bm, value);
836 expected_card ++;
837 }
838 assert_true(roaring_bitmap_get_cardinality(bm) == expected_card);
839 roaring_bitmap_clear(bm);
840 assert_true(roaring_bitmap_is_empty(bm));
841 roaring_bitmap_free(bm);
842}
843
844
845void test_remove_from_copies_true() { can_remove_from_copies(true); }
846
847void test_remove_from_copies_false() { can_remove_from_copies(false); }
848
849bool check_bitmap_from_range(uint32_t min, uint64_t max, uint32_t step) {
850 roaring_bitmap_t *result = roaring_bitmap_from_range(min, max, step);
851 assert_non_null(result);
852 roaring_bitmap_t *expected = roaring_bitmap_create();
853 assert_non_null(expected);
854 for (uint32_t value = min; value < max; value += step) {
855 roaring_bitmap_add(expected, value);
856 }
857 bool is_equal = roaring_bitmap_equals(expected, result);
858 if (!is_equal) {
859 fprintf(stderr, "[ERROR] check_bitmap_from_range(%u, %u, %u)\n",
860 (unsigned)min, (unsigned)max, (unsigned)step);
861 }
862 roaring_bitmap_free(expected);
863 roaring_bitmap_free(result);
864 return is_equal;
865}
866
867void test_silly_range() {
868 check_bitmap_from_range(0, 1, 1);
869 check_bitmap_from_range(0, 2, 1);
870 roaring_bitmap_t *bm1 = roaring_bitmap_from_range(0, 1, 1);
871 roaring_bitmap_t *bm2 = roaring_bitmap_from_range(0, 2, 1);
872 assert_false(roaring_bitmap_equals(bm1, bm2));
873 roaring_bitmap_free(bm1);
874 roaring_bitmap_free(bm2);
875}
876
877void test_adversarial_range() {
878 roaring_bitmap_t *bm1 = roaring_bitmap_from_range(0, UINT64_C(0x100000000), 1);
879 assert_true(roaring_bitmap_get_cardinality(bm1) == UINT64_C(0x100000000));
880 roaring_bitmap_free(bm1);
881}
882
883void test_range_and_serialize() {
884 roaring_bitmap_t *old_bm = roaring_bitmap_from_range(65520, 131057, 16);
885 size_t size = roaring_bitmap_portable_size_in_bytes(old_bm);
886 char *buff = malloc(size);
887 size_t actualsize = roaring_bitmap_portable_serialize(old_bm, buff);
888 assert_int_equal(actualsize, size);
889 roaring_bitmap_t *new_bm = roaring_bitmap_portable_deserialize(buff);
890 assert_true(roaring_bitmap_equals(old_bm, new_bm));
891 roaring_bitmap_free(old_bm);
892 roaring_bitmap_free(new_bm);
893 free(buff);
894}
895
896void test_bitmap_from_range() {
897 assert_true(roaring_bitmap_from_range(1, 10, 0) ==
898 NULL); // undefined range
899 assert_true(roaring_bitmap_from_range(5, 1, 3) == NULL); // empty range
900 for (uint32_t i = 16; i < 1 << 18; i *= 2) {
901 uint32_t min = i - 10;
902 for (uint32_t delta = 16; delta < 1 << 18; delta *= 2) {
903 uint32_t max = i + delta;
904 for (uint32_t step = 1; step <= 64;
905 step *= 2) { // check powers of 2
906 assert_true(check_bitmap_from_range(min, max, step));
907 }
908 for (uint32_t step = 1; step <= 81;
909 step *= 3) { // check powers of 3
910 assert_true(check_bitmap_from_range(min, max, step));
911 }
912 for (uint32_t step = 1; step <= 125;
913 step *= 5) { // check powers of 5
914 assert_true(check_bitmap_from_range(min, max, step));
915 }
916 }
917 }
918
919 // max range
920 roaring_bitmap_t *r = roaring_bitmap_from_range(0, UINT64_MAX, 1);
921 assert_true(roaring_bitmap_get_cardinality(r) == UINT64_C(0x100000000));
922 roaring_bitmap_free(r);
923}
924
925void test_printf() {
926 roaring_bitmap_t *r1 =
927 roaring_bitmap_of(8, 1, 2, 3, 100, 1000, 10000, 1000000, 20000000);
928 assert_non_null(r1);
929 roaring_bitmap_printf(r1);
930 roaring_bitmap_free(r1);
931 printf("\n");
932}
933
934void test_printf_withbitmap() {
935 roaring_bitmap_t *r1 = roaring_bitmap_create();
936 assert_non_null(r1);
937 roaring_bitmap_printf(r1);
938 /* Add some values to the bitmap */
939 for (int i = 0, top_val = 4097; i < top_val; i++)
940 roaring_bitmap_add(r1, 2 * i);
941 roaring_bitmap_printf(r1);
942 roaring_bitmap_free(r1);
943 printf("\n");
944}
945
946void test_printf_withrun() {
947 roaring_bitmap_t *r1 = roaring_bitmap_create();
948 assert_non_null(r1);
949 roaring_bitmap_printf(r1);
950 /* Add some values to the bitmap */
951 for (int i = 100, top_val = 200; i < top_val; i++)
952 roaring_bitmap_add(r1, i);
953 roaring_bitmap_run_optimize(r1);
954 roaring_bitmap_printf(r1); // does it crash?
955 roaring_bitmap_free(r1);
956 printf("\n");
957}
958
959bool dummy_iterator(uint32_t value, void *param) {
960 (void)value;
961
962 uint32_t *num = (uint32_t *)param;
963 (*num)++;
964 return true;
965}
966
967void test_iterate() {
968 roaring_bitmap_t *r1 =
969 roaring_bitmap_of(8, 1, 2, 3, 100, 1000, 10000, 1000000, 20000000);
970 assert_non_null(r1);
971
972 uint32_t num = 0;
973 /* Add some values to the bitmap */
974 for (int i = 0, top_val = 384000; i < top_val; i++)
975 roaring_bitmap_add(r1, 3 * i);
976
977 roaring_iterate(r1, dummy_iterator, (void *)&num);
978
979 assert_int_equal(roaring_bitmap_get_cardinality(r1), num);
980 roaring_bitmap_free(r1);
981}
982
983void test_iterate_empty() {
984 roaring_bitmap_t *r1 = roaring_bitmap_create();
985 assert_non_null(r1);
986 uint32_t num = 0;
987
988 roaring_iterate(r1, dummy_iterator, (void *)&num);
989
990 assert_int_equal(roaring_bitmap_get_cardinality(r1), 0);
991 assert_int_equal(roaring_bitmap_get_cardinality(r1), num);
992 roaring_bitmap_free(r1);
993}
994
995void test_iterate_withbitmap() {
996 roaring_bitmap_t *r1 = roaring_bitmap_create();
997 assert_non_null(r1);
998 /* Add some values to the bitmap */
999 for (int i = 0, top_val = 4097; i < top_val; i++)
1000 roaring_bitmap_add(r1, 2 * i);
1001 uint32_t num = 0;
1002
1003 roaring_iterate(r1, dummy_iterator, (void *)&num);
1004
1005 assert_int_equal(roaring_bitmap_get_cardinality(r1), num);
1006 roaring_bitmap_free(r1);
1007}
1008
1009void test_iterate_withrun() {
1010 roaring_bitmap_t *r1 = roaring_bitmap_create();
1011 assert_non_null(r1);
1012 /* Add some values to the bitmap */
1013 for (int i = 100, top_val = 200; i < top_val; i++)
1014 roaring_bitmap_add(r1, i);
1015 roaring_bitmap_run_optimize(r1);
1016 uint32_t num = 0;
1017 roaring_iterate(r1, dummy_iterator, (void *)&num);
1018
1019 assert_int_equal(roaring_bitmap_get_cardinality(r1), num);
1020 roaring_bitmap_free(r1);
1021}
1022
1023void test_remove_withrun() {
1024 roaring_bitmap_t *r1 = roaring_bitmap_create();
1025 assert_non_null(r1);
1026 /* Add some values to the bitmap */
1027 for (int i = 100, top_val = 20000; i < top_val; i++)
1028 roaring_bitmap_add(r1, i);
1029 assert_int_equal(roaring_bitmap_get_cardinality(r1), 20000 - 100);
1030 roaring_bitmap_remove(r1, 1000);
1031 assert_int_equal(roaring_bitmap_get_cardinality(r1), 20000 - 100 - 1);
1032 roaring_bitmap_run_optimize(r1);
1033 assert_int_equal(roaring_bitmap_get_cardinality(r1), 20000 - 100 - 1);
1034 roaring_bitmap_remove(r1, 2000);
1035 assert_int_equal(roaring_bitmap_get_cardinality(r1), 20000 - 100 - 1 - 1);
1036 roaring_bitmap_free(r1);
1037}
1038
1039void test_portable_serialize() {
1040 roaring_bitmap_t *r1 =
1041 roaring_bitmap_of(8, 1, 2, 3, 100, 1000, 10000, 1000000, 20000000);
1042 assert_non_null(r1);
1043
1044 uint32_t serialize_len;
1045 roaring_bitmap_t *r2;
1046
1047 for (int i = 0, top_val = 384000; i < top_val; i++)
1048 roaring_bitmap_add(r1, 3 * i);
1049
1050 uint32_t expectedsize = roaring_bitmap_portable_size_in_bytes(r1);
1051 char *serialized = malloc(expectedsize);
1052 serialize_len = roaring_bitmap_portable_serialize(r1, serialized);
1053 assert_int_equal(serialize_len, expectedsize);
1054 assert_int_equal(serialize_len, expectedsize);
1055 r2 = roaring_bitmap_portable_deserialize(serialized);
1056 assert_non_null(r2);
1057
1058 uint64_t card1 = roaring_bitmap_get_cardinality(r1);
1059 uint32_t *arr1 = (uint32_t *)malloc(card1 * sizeof(uint32_t));
1060 roaring_bitmap_to_uint32_array(r1, arr1);
1061
1062 uint64_t card2 = roaring_bitmap_get_cardinality(r2);
1063 uint32_t *arr2 = (uint32_t *)malloc(card2 * sizeof(uint32_t));
1064 roaring_bitmap_to_uint32_array(r2, arr2);
1065
1066 assert_true(array_equals(arr1, card1, arr2, card2));
1067 assert_true(roaring_bitmap_equals(r1, r2));
1068 free(arr1);
1069 free(arr2);
1070 free(serialized);
1071 roaring_bitmap_free(r1);
1072 roaring_bitmap_free(r2);
1073
1074 r1 = roaring_bitmap_of(6, 2946000, 2997491, 10478289, 10490227, 10502444,
1075 19866827);
1076 expectedsize = roaring_bitmap_portable_size_in_bytes(r1);
1077 serialized = malloc(expectedsize);
1078 serialize_len = roaring_bitmap_portable_serialize(r1, serialized);
1079 assert_int_equal(serialize_len, expectedsize);
1080 assert_int_equal(serialize_len, expectedsize);
1081
1082 r2 = roaring_bitmap_portable_deserialize(serialized);
1083 assert_non_null(r2);
1084
1085 card1 = roaring_bitmap_get_cardinality(r1);
1086 arr1 = (uint32_t *)malloc(card1 * sizeof(uint32_t));
1087 roaring_bitmap_to_uint32_array(r1, arr1);
1088
1089 card2 = roaring_bitmap_get_cardinality(r2);
1090 arr2 = (uint32_t *)malloc(card2 * sizeof(uint32_t));
1091 roaring_bitmap_to_uint32_array(r2, arr2);
1092
1093 assert_true(array_equals(arr1, card1, arr2, card2));
1094 assert_true(roaring_bitmap_equals(r1, r2));
1095 free(arr1);
1096 free(arr2);
1097 free(serialized);
1098 roaring_bitmap_free(r1);
1099 roaring_bitmap_free(r2);
1100
1101 r1 = roaring_bitmap_create();
1102 assert_non_null(r1);
1103
1104 for (uint32_t k = 100; k < 100000; ++k) {
1105 roaring_bitmap_add(r1, k);
1106 }
1107
1108 roaring_bitmap_run_optimize(r1);
1109 expectedsize = roaring_bitmap_portable_size_in_bytes(r1);
1110 serialized = malloc(expectedsize);
1111 serialize_len = roaring_bitmap_portable_serialize(r1, serialized);
1112 assert_int_equal(serialize_len, expectedsize);
1113
1114 r2 = roaring_bitmap_portable_deserialize(serialized);
1115 assert_non_null(r2);
1116
1117 card1 = roaring_bitmap_get_cardinality(r1);
1118 arr1 = (uint32_t *)malloc(card1 * sizeof(uint32_t));
1119 roaring_bitmap_to_uint32_array(r1, arr1);
1120
1121 card2 = roaring_bitmap_get_cardinality(r2);
1122 arr2 = (uint32_t *)malloc(card2 * sizeof(uint32_t));
1123 roaring_bitmap_to_uint32_array(r2, arr2);
1124
1125 assert(array_equals(arr1, card1, arr2, card2));
1126 assert(roaring_bitmap_equals(r1, r2));
1127 free(arr1);
1128 free(arr2);
1129 free(serialized);
1130 roaring_bitmap_free(r1);
1131 roaring_bitmap_free(r2);
1132}
1133
1134void test_serialize() {
1135 roaring_bitmap_t *r1 =
1136 roaring_bitmap_of(8, 1, 2, 3, 100, 1000, 10000, 1000000, 20000000);
1137 assert_non_null(r1);
1138
1139 uint32_t serialize_len;
1140 char *serialized;
1141 roaring_bitmap_t *r2;
1142
1143 /* Add some values to the bitmap */
1144 for (int i = 0, top_val = 384000; i < top_val; i++)
1145 roaring_bitmap_add(r1, 3 * i);
1146 serialized = malloc(roaring_bitmap_size_in_bytes(r1));
1147 serialize_len = roaring_bitmap_serialize(r1, serialized);
1148 assert_int_equal(serialize_len, roaring_bitmap_size_in_bytes(r1));
1149 r2 = roaring_bitmap_deserialize(serialized);
1150 assert_non_null(r2);
1151
1152 uint64_t card1 = roaring_bitmap_get_cardinality(r1);
1153 uint32_t *arr1 = (uint32_t *)malloc(card1 * sizeof(uint32_t));
1154 roaring_bitmap_to_uint32_array(r1, arr1);
1155
1156 uint64_t card2 = roaring_bitmap_get_cardinality(r2);
1157 uint32_t *arr2 = (uint32_t *)malloc(card2 * sizeof(uint32_t));
1158 roaring_bitmap_to_uint32_array(r2, arr2);
1159
1160 assert_true(array_equals(arr1, card1, arr2, card2));
1161 assert_true(roaring_bitmap_equals(r1, r2));
1162 free(arr1);
1163 free(arr2);
1164 free(serialized);
1165 roaring_bitmap_free(r1);
1166 roaring_bitmap_free(r2);
1167
1168 run_container_t *run = run_container_create_given_capacity(1024);
1169 assert_non_null(run);
1170 for (int i = 0; i < 768; i++) run_container_add(run, 3 * i);
1171
1172 serialize_len = run_container_serialization_len(run);
1173 char *rbuf = malloc(serialize_len);
1174 assert_int_equal((int32_t)serialize_len,
1175 run_container_serialize(run, rbuf));
1176 run_container_t *run1 = run_container_deserialize(rbuf, serialize_len);
1177 free(rbuf);
1178
1179 run_container_free(run);
1180 run_container_free(run1);
1181
1182 r1 = roaring_bitmap_of(6, 2946000, 2997491, 10478289, 10490227, 10502444,
1183 19866827);
1184
1185 serialized = malloc(roaring_bitmap_size_in_bytes(r1));
1186 serialize_len = roaring_bitmap_serialize(r1, serialized);
1187 assert_int_equal(serialize_len, roaring_bitmap_size_in_bytes(r1));
1188 r2 = roaring_bitmap_deserialize(serialized);
1189 assert_non_null(r2);
1190
1191 card1 = roaring_bitmap_get_cardinality(r1);
1192 arr1 = (uint32_t *)malloc(card1 * sizeof(uint32_t));
1193 assert_non_null(arr1);
1194 roaring_bitmap_to_uint32_array(r1, arr1);
1195
1196 card2 = roaring_bitmap_get_cardinality(r2);
1197 arr2 = (uint32_t *)malloc(card2 * sizeof(uint32_t));
1198 assert_non_null(arr2);
1199 roaring_bitmap_to_uint32_array(r2, arr2);
1200
1201 assert_true(array_equals(arr1, card1, arr2, card2));
1202 assert_true(roaring_bitmap_equals(r1, r2));
1203 free(arr1);
1204 free(arr2);
1205 free(serialized);
1206 roaring_bitmap_free(r1);
1207 roaring_bitmap_free(r2);
1208
1209 r1 = roaring_bitmap_create();
1210 for (uint32_t k = 100; k < 100000; ++k) {
1211 roaring_bitmap_add(r1, k);
1212 }
1213 roaring_bitmap_run_optimize(r1);
1214 serialized = malloc(roaring_bitmap_size_in_bytes(r1));
1215 serialize_len = roaring_bitmap_serialize(r1, serialized);
1216 assert_int_equal(serialize_len, roaring_bitmap_size_in_bytes(r1));
1217 r2 = roaring_bitmap_deserialize(serialized);
1218
1219 card1 = roaring_bitmap_get_cardinality(r1);
1220 arr1 = (uint32_t *)malloc(card1 * sizeof(uint32_t));
1221 assert_non_null(arr1);
1222 roaring_bitmap_to_uint32_array(r1, arr1);
1223
1224 card2 = roaring_bitmap_get_cardinality(r2);
1225 arr2 = (uint32_t *)malloc(card2 * sizeof(uint32_t));
1226 assert_non_null(arr2);
1227 roaring_bitmap_to_uint32_array(r2, arr2);
1228
1229 assert_true(array_equals(arr1, card1, arr2, card2));
1230 assert_true(roaring_bitmap_equals(r1, r2));
1231 free(arr1);
1232 free(arr2);
1233 free(serialized);
1234 roaring_bitmap_free(r1);
1235 roaring_bitmap_free(r2);
1236
1237 /* ******* */
1238 roaring_bitmap_t *old_bm = roaring_bitmap_create();
1239 for (unsigned i = 0; i < 102; i++) roaring_bitmap_add(old_bm, i);
1240 char *buff = malloc(roaring_bitmap_size_in_bytes(old_bm));
1241 uint32_t size = roaring_bitmap_serialize(old_bm, buff);
1242 assert_int_equal(size, roaring_bitmap_size_in_bytes(old_bm));
1243 roaring_bitmap_t *new_bm = roaring_bitmap_deserialize(buff);
1244 free(buff);
1245 assert_true((unsigned int)roaring_bitmap_get_cardinality(old_bm) ==
1246 (unsigned int)roaring_bitmap_get_cardinality(new_bm));
1247 assert_true(roaring_bitmap_equals(old_bm, new_bm));
1248 roaring_bitmap_free(old_bm);
1249 roaring_bitmap_free(new_bm);
1250}
1251
1252void test_add() {
1253 roaring_bitmap_t *r1 = roaring_bitmap_create();
1254 assert_non_null(r1);
1255
1256 for (uint32_t i = 0; i < 10000; ++i) {
1257 assert_int_equal(roaring_bitmap_get_cardinality(r1), i);
1258 roaring_bitmap_add(r1, 200 * i);
1259 assert_int_equal(roaring_bitmap_get_cardinality(r1), i + 1);
1260 }
1261
1262 roaring_bitmap_free(r1);
1263}
1264
1265void test_add_checked() {
1266 roaring_bitmap_t *r1 = roaring_bitmap_create();
1267 assert_non_null(r1);
1268
1269 assert_true(roaring_bitmap_add_checked(r1, 999));
1270 for (uint32_t i = 0; i < 125; ++i) {
1271 assert_true(roaring_bitmap_add_checked(r1, 3823 * i));
1272 assert_false(roaring_bitmap_add_checked(r1, 3823 * i));
1273 }
1274 assert_false(roaring_bitmap_add_checked(r1, 999));
1275
1276 roaring_bitmap_free(r1);
1277}
1278
1279void test_remove_checked() {
1280 roaring_bitmap_t *bm = roaring_bitmap_create();
1281 for (uint32_t i = 0; i < 125; ++i) {
1282 roaring_bitmap_add(bm, i * 3533);
1283 }
1284 for (uint32_t i = 0; i < 125; ++i) {
1285 assert_true(roaring_bitmap_remove_checked(bm, i * 3533));
1286 assert_false(roaring_bitmap_remove_checked(bm, i * 3533));
1287 }
1288 assert_false(roaring_bitmap_remove_checked(bm, 999));
1289 roaring_bitmap_add(bm, 999);
1290 assert_true(roaring_bitmap_remove_checked(bm, 999));
1291 assert_true(roaring_bitmap_is_empty(bm));
1292 roaring_bitmap_free(bm);
1293}
1294
1295void test_contains() {
1296 roaring_bitmap_t *r1 = roaring_bitmap_create();
1297 assert_non_null(r1);
1298
1299 for (uint32_t i = 0; i < 10000; ++i) {
1300 assert_int_equal(roaring_bitmap_get_cardinality(r1), i);
1301 roaring_bitmap_add(r1, 200 * i);
1302 assert_int_equal(roaring_bitmap_get_cardinality(r1), i + 1);
1303 }
1304
1305 for (uint32_t i = 0; i < 200 * 10000; ++i) {
1306 assert_int_equal(roaring_bitmap_contains(r1, i), (i % 200 == 0));
1307 }
1308
1309 roaring_bitmap_free(r1);
1310}
1311
1312void test_contains_range() {
1313 uint32_t* values = malloc(100000 * sizeof(uint32_t));
1314 assert_non_null(values);
1315 for (uint32_t length_range = 1; length_range <= 64; ++length_range) {
1316 roaring_bitmap_t *r1 = roaring_bitmap_create();
1317 assert_non_null(r1);
1318 for (uint32_t i = 0; i < 100000; ++i){
1319 const uint32_t val = rand() % 200000;
1320 roaring_bitmap_add(r1, val);
1321 values[i] = val;
1322 }
1323 for (uint64_t i = 0; i < 100000; ++i){
1324 if (roaring_bitmap_contains_range(r1, values[i], values[i] + length_range)){
1325 for (uint32_t j = values[i]; j < values[i] + length_range; ++j) assert_true(roaring_bitmap_contains(r1, j));
1326 }
1327 else {
1328 uint32_t count = 0;
1329 for (uint32_t j = values[i]; j < values[i] + length_range; ++j){
1330 if (roaring_bitmap_contains(r1, j)) ++count;
1331 else break;
1332 }
1333 assert_true(count != length_range);
1334 }
1335 }
1336 roaring_bitmap_free(r1);
1337 }
1338 free(values);
1339 for (uint32_t length_range = 1; length_range <= 64; ++length_range) {
1340 roaring_bitmap_t *r1 = roaring_bitmap_create();
1341 assert_non_null(r1);
1342 const uint32_t length_range_twice = length_range * 2;
1343 for (uint32_t i = 0; i < 130000; i += length_range){
1344 if (i % length_range_twice == 0){
1345 for (uint32_t j = i; j < i + length_range; ++j) roaring_bitmap_add(r1, j);
1346 }
1347 }
1348 for (uint32_t i = 0; i < 130000; i += length_range){
1349 bool pres = roaring_bitmap_contains_range(r1, i, i + length_range);
1350 assert_true(((i % length_range_twice == 0) ? pres : !pres));
1351 }
1352 roaring_bitmap_free(r1);
1353 }
1354}
1355
1356void test_intersection_array_x_array() {
1357 roaring_bitmap_t *r1 = roaring_bitmap_create();
1358 assert_non_null(r1);
1359 roaring_bitmap_t *r2 = roaring_bitmap_create();
1360 assert_non_null(r2);
1361
1362 for (uint32_t i = 0; i < 100; ++i) {
1363 roaring_bitmap_add(r1, 2 * i);
1364 roaring_bitmap_add(r2, 3 * i);
1365 roaring_bitmap_add(r1, 5 * 65536 + 2 * i);
1366 roaring_bitmap_add(r2, 5 * 65536 + 3 * i);
1367
1368 assert_int_equal(roaring_bitmap_get_cardinality(r2), 2 * (i + 1));
1369 assert_int_equal(roaring_bitmap_get_cardinality(r1), 2 * (i + 1));
1370 }
1371
1372 roaring_bitmap_t *r1_and_r2 = roaring_bitmap_and(r1, r2);
1373 assert_true(roaring_bitmap_get_cardinality(r1_and_r2) ==
1374 roaring_bitmap_and_cardinality(r1, r2));
1375
1376 assert_non_null(r1_and_r2);
1377 assert_int_equal(roaring_bitmap_get_cardinality(r1_and_r2), 2 * 34);
1378
1379 roaring_bitmap_free(r1_and_r2);
1380 roaring_bitmap_free(r2);
1381 roaring_bitmap_free(r1);
1382}
1383
1384void test_intersection_array_x_array_inplace() {
1385 roaring_bitmap_t *r1 = roaring_bitmap_create();
1386 assert(r1);
1387 roaring_bitmap_t *r2 = roaring_bitmap_create();
1388 assert(r2);
1389
1390 for (uint32_t i = 0; i < 100; ++i) {
1391 roaring_bitmap_add(r1, 2 * i);
1392 roaring_bitmap_add(r2, 3 * i);
1393 roaring_bitmap_add(r1, 5 * 65536 + 2 * i);
1394 roaring_bitmap_add(r2, 5 * 65536 + 3 * i);
1395
1396 assert_int_equal(roaring_bitmap_get_cardinality(r2), 2 * (i + 1));
1397 assert_int_equal(roaring_bitmap_get_cardinality(r1), 2 * (i + 1));
1398 }
1399
1400 roaring_bitmap_and_inplace(r1, r2);
1401 assert_int_equal(roaring_bitmap_get_cardinality(r1), 2 * 34);
1402
1403 roaring_bitmap_free(r2);
1404 roaring_bitmap_free(r1);
1405}
1406
1407void test_intersection_bitset_x_bitset() {
1408 roaring_bitmap_t *r1 = roaring_bitmap_create();
1409 assert(r1);
1410 roaring_bitmap_t *r2 = roaring_bitmap_create();
1411 assert(r2);
1412
1413 for (uint32_t i = 0; i < 20000; ++i) {
1414 roaring_bitmap_add(r1, 2 * i);
1415 roaring_bitmap_add(r2, 3 * i);
1416 roaring_bitmap_add(r2, 3 * i + 1);
1417 roaring_bitmap_add(r1, 5 * 65536 + 2 * i);
1418 roaring_bitmap_add(r2, 5 * 65536 + 3 * i);
1419 roaring_bitmap_add(r2, 5 * 65536 + 3 * i + 1);
1420
1421 assert_int_equal(roaring_bitmap_get_cardinality(r1), 2 * (i + 1));
1422 assert_int_equal(roaring_bitmap_get_cardinality(r2), 4 * (i + 1));
1423 }
1424
1425 roaring_bitmap_t *r1_and_r2 = roaring_bitmap_and(r1, r2);
1426 assert_true(roaring_bitmap_get_cardinality(r1_and_r2) ==
1427 roaring_bitmap_and_cardinality(r1, r2));
1428
1429 assert_non_null(r1_and_r2);
1430
1431 // NOT analytically determined but seems reasonable
1432 assert_int_equal(roaring_bitmap_get_cardinality(r1_and_r2), 26666);
1433
1434 roaring_bitmap_free(r1_and_r2);
1435 roaring_bitmap_free(r2);
1436 roaring_bitmap_free(r1);
1437}
1438
1439void test_intersection_bitset_x_bitset_inplace() {
1440 roaring_bitmap_t *r1 = roaring_bitmap_create();
1441 assert(r1);
1442 roaring_bitmap_t *r2 = roaring_bitmap_create();
1443 assert(r2);
1444
1445 for (uint32_t i = 0; i < 20000; ++i) {
1446 roaring_bitmap_add(r1, 2 * i);
1447 roaring_bitmap_add(r2, 3 * i);
1448 roaring_bitmap_add(r2, 3 * i + 1);
1449 roaring_bitmap_add(r1, 5 * 65536 + 2 * i);
1450 roaring_bitmap_add(r2, 5 * 65536 + 3 * i);
1451 roaring_bitmap_add(r2, 5 * 65536 + 3 * i + 1);
1452
1453 assert_int_equal(roaring_bitmap_get_cardinality(r1), 2 * (i + 1));
1454 assert_int_equal(roaring_bitmap_get_cardinality(r2), 4 * (i + 1));
1455 }
1456
1457 roaring_bitmap_and_inplace(r1, r2);
1458
1459 assert_int_equal(roaring_bitmap_get_cardinality(r1), 26666);
1460 roaring_bitmap_free(r2);
1461 roaring_bitmap_free(r1);
1462}
1463
1464void test_union(bool copy_on_write) {
1465 roaring_bitmap_t *r1 = roaring_bitmap_create();
1466 roaring_bitmap_set_copy_on_write(r1, copy_on_write);
1467 assert(r1);
1468 roaring_bitmap_t *r2 = roaring_bitmap_create();
1469 roaring_bitmap_set_copy_on_write(r2, copy_on_write);
1470 assert(r2);
1471
1472 for (uint32_t i = 0; i < 100; ++i) {
1473 roaring_bitmap_add(r1, 2 * i);
1474 roaring_bitmap_add(r2, 3 * i);
1475 assert_int_equal(roaring_bitmap_get_cardinality(r2), i + 1);
1476 assert_int_equal(roaring_bitmap_get_cardinality(r1), i + 1);
1477 }
1478
1479 roaring_bitmap_t *r1_or_r2 = roaring_bitmap_or(r1, r2);
1480 assert_true(roaring_bitmap_get_cardinality(r1_or_r2) ==
1481 roaring_bitmap_or_cardinality(r1, r2));
1482
1483 roaring_bitmap_set_copy_on_write(r1_or_r2, copy_on_write);
1484 assert_int_equal(roaring_bitmap_get_cardinality(r1_or_r2), 166);
1485
1486 roaring_bitmap_free(r1_or_r2);
1487 roaring_bitmap_free(r2);
1488 roaring_bitmap_free(r1);
1489}
1490
1491void test_union_true() { test_union(true); }
1492
1493void test_union_false() { test_union(false); }
1494
1495// density factor changes as one gets further into bitmap
1496static roaring_bitmap_t *gen_bitmap(double start_density,
1497 double density_gradient, int run_length,
1498 int blank_range_start, int blank_range_end,
1499 int universe_size) {
1500 srand(2345);
1501 roaring_bitmap_t *ans = roaring_bitmap_create();
1502 double d = start_density;
1503
1504 for (int i = 0; i < universe_size; i += run_length) {
1505 d = start_density + i * density_gradient;
1506 double r = our_rand() / (double)OUR_RAND_MAX;
1507 assert(r <= 1.0);
1508 assert(r >= 0);
1509 if (r < d && !(i >= blank_range_start && i < blank_range_end))
1510 for (int j = 0; j < run_length; ++j) roaring_bitmap_add(ans, i + j);
1511 }
1512 roaring_bitmap_run_optimize(ans);
1513 return ans;
1514}
1515
1516static roaring_bitmap_t *synthesized_xor(roaring_bitmap_t *r1,
1517 roaring_bitmap_t *r2) {
1518 unsigned universe_size = 0;
1519 roaring_statistics_t stats;
1520 roaring_bitmap_statistics(r1, &stats);
1521 universe_size = stats.max_value;
1522 roaring_bitmap_statistics(r2, &stats);
1523 if (stats.max_value > universe_size) universe_size = stats.max_value;
1524
1525 roaring_bitmap_t *r1_or_r2 = roaring_bitmap_or(r1, r2);
1526 assert_true(roaring_bitmap_get_cardinality(r1_or_r2) ==
1527 roaring_bitmap_or_cardinality(r1, r2));
1528
1529 roaring_bitmap_t *r1_and_r2 = roaring_bitmap_and(r1, r2);
1530 assert_true(roaring_bitmap_get_cardinality(r1_and_r2) ==
1531 roaring_bitmap_and_cardinality(r1, r2));
1532
1533 roaring_bitmap_t *r1_nand_r2 =
1534 roaring_bitmap_flip(r1_and_r2, 0U, universe_size + 1U);
1535 roaring_bitmap_t *r1_xor_r2 = roaring_bitmap_and(r1_or_r2, r1_nand_r2);
1536 roaring_bitmap_free(r1_or_r2);
1537 roaring_bitmap_free(r1_and_r2);
1538 roaring_bitmap_free(r1_nand_r2);
1539 return r1_xor_r2;
1540}
1541
1542static roaring_bitmap_t *synthesized_andnot(roaring_bitmap_t *r1,
1543 roaring_bitmap_t *r2) {
1544 unsigned universe_size = 0;
1545 roaring_statistics_t stats;
1546 roaring_bitmap_statistics(r1, &stats);
1547 universe_size = stats.max_value;
1548 roaring_bitmap_statistics(r2, &stats);
1549 if (stats.max_value > universe_size) universe_size = stats.max_value;
1550
1551 roaring_bitmap_t *not_r2 = roaring_bitmap_flip(r2, 0U, universe_size + 1U);
1552 roaring_bitmap_t *r1_andnot_r2 = roaring_bitmap_and(r1, not_r2);
1553 roaring_bitmap_free(not_r2);
1554 return r1_andnot_r2;
1555}
1556
1557// only for valid for universe < 10M, could adapt with roaring_bitmap_statistics
1558static void show_difference(roaring_bitmap_t *result,
1559 roaring_bitmap_t *hopedfor) {
1560 int out_ctr = 0;
1561 for (int i = 0; i < 10000000; ++i) {
1562 if (roaring_bitmap_contains(result, i) &&
1563 !roaring_bitmap_contains(hopedfor, i)) {
1564 printf("result incorrectly has %d\n", i);
1565 ++out_ctr;
1566 }
1567 if (!roaring_bitmap_contains(result, i) &&
1568 roaring_bitmap_contains(hopedfor, i)) {
1569 printf("result incorrectly omits %d\n", i);
1570 ++out_ctr;
1571 }
1572 if (out_ctr > 20) {
1573 printf("20 errors seen, stopping comparison\n");
1574 break;
1575 }
1576 }
1577}
1578
1579void test_xor(bool copy_on_write) {
1580 roaring_bitmap_t *r1 = roaring_bitmap_create();
1581 roaring_bitmap_set_copy_on_write(r1, copy_on_write);
1582 roaring_bitmap_t *r2 = roaring_bitmap_create();
1583 roaring_bitmap_set_copy_on_write(r2, copy_on_write);
1584
1585 for (uint32_t i = 0; i < 300; ++i) {
1586 if (i % 2 == 0) roaring_bitmap_add(r1, i);
1587 if (i % 3 == 0) roaring_bitmap_add(r2, i);
1588 }
1589
1590 roaring_bitmap_t *r1_xor_r2 = roaring_bitmap_xor(r1, r2);
1591 roaring_bitmap_set_copy_on_write(r1_xor_r2, copy_on_write);
1592
1593 int ansctr = 0;
1594 for (int i = 0; i < 300; ++i) {
1595 if (((i % 2 == 0) || (i % 3 == 0)) && (i % 6 != 0)) {
1596 ansctr++;
1597 if (!roaring_bitmap_contains(r1_xor_r2, i))
1598 printf("missing %d\n", i);
1599 } else if (roaring_bitmap_contains(r1_xor_r2, i))
1600 printf("surplus %d\n", i);
1601 }
1602
1603 assert_int_equal(roaring_bitmap_get_cardinality(r1_xor_r2), ansctr);
1604
1605 roaring_bitmap_free(r1_xor_r2);
1606 roaring_bitmap_free(r2);
1607 roaring_bitmap_free(r1);
1608
1609 // some tougher tests on synthetic data
1610
1611 roaring_bitmap_t *r[] = {
1612 // ascending density, last containers might be runs
1613 gen_bitmap(0.0, 1e-6, 1, 0, 0, 1000000),
1614 // descending density, first containers might be runs
1615 gen_bitmap(1.0, -1e-6, 1, 0, 0, 1000000),
1616 // uniformly rather sparse
1617 gen_bitmap(1e-5, 0.0, 1, 0, 0, 2000000),
1618 // uniformly rather sparse with runs
1619 gen_bitmap(1e-5, 0.0, 3, 0, 0, 2000000),
1620 // uniformly rather dense
1621 gen_bitmap(1e-1, 0.0, 1, 0, 0, 2000000),
1622 // ascending density but never too dense
1623 gen_bitmap(0.001, 1e-7, 1, 0, 0, 1000000),
1624 // ascending density but very sparse
1625 gen_bitmap(0.0, 1e-10, 1, 0, 0, 1000000),
1626 // descending with a gap
1627 gen_bitmap(0.5, -1e-6, 1, 600000, 800000, 1000000),
1628 // gap elsewhere
1629 gen_bitmap(1, -1e-6, 1, 300000, 500000, 1000000),
1630 0 // sentinel
1631 };
1632
1633 for (int i = 0; r[i]; ++i) {
1634 for (int j = i; r[j]; ++j) {
1635 roaring_bitmap_t *expected = synthesized_xor(r[i], r[j]);
1636 roaring_bitmap_t *result = roaring_bitmap_xor(r[i], r[j]);
1637 assert_true(roaring_bitmap_get_cardinality(result) ==
1638 roaring_bitmap_xor_cardinality(r[i], r[j]));
1639
1640 bool is_equal = roaring_bitmap_equals(expected, result);
1641
1642 assert_true(is_equal);
1643 roaring_bitmap_free(expected);
1644 roaring_bitmap_free(result);
1645 }
1646 }
1647 for (int i = 0; r[i]; ++i) roaring_bitmap_free(r[i]);
1648}
1649
1650void test_xor_true() { test_xor(true); }
1651
1652void test_xor_false() { test_xor(false); }
1653
1654void test_xor_inplace(bool copy_on_write) {
1655 roaring_bitmap_t *r1 = roaring_bitmap_create();
1656 roaring_bitmap_set_copy_on_write(r1, copy_on_write);
1657 roaring_bitmap_t *r2 = roaring_bitmap_create();
1658 roaring_bitmap_set_copy_on_write(r2, copy_on_write);
1659
1660 for (uint32_t i = 0; i < 300; ++i) {
1661 if (i % 2 == 0) roaring_bitmap_add(r1, i);
1662 if (i % 3 == 0) roaring_bitmap_add(r2, i);
1663 }
1664 roaring_bitmap_xor_inplace(r1, r2);
1665 assert_int_equal(roaring_bitmap_get_cardinality(r1), 166 - 16);
1666
1667 roaring_bitmap_free(r2);
1668 roaring_bitmap_free(r1);
1669
1670 // some tougher tests on synthetic data
1671
1672 roaring_bitmap_t *r[] = {
1673 // ascending density, last containers might be runs
1674 gen_bitmap(0.0, 1e-6, 1, 0, 0, 1000000),
1675 // descending density, first containers might be runs
1676 gen_bitmap(1.0, -1e-6, 1, 0, 0, 1000000),
1677 // uniformly rather sparse
1678 gen_bitmap(1e-5, 0.0, 1, 0, 0, 2000000),
1679 // uniformly rather sparse with runs
1680 gen_bitmap(1e-5, 0.0, 3, 0, 0, 2000000),
1681 // uniformly rather dense
1682 gen_bitmap(1e-1, 0.0, 1, 0, 0, 2000000),
1683 // ascending density but never too dense
1684 gen_bitmap(0.001, 1e-7, 1, 0, 0, 1000000),
1685 // ascending density but very sparse
1686 gen_bitmap(0.0, 1e-10, 1, 0, 0, 1000000),
1687 // descending with a gap
1688 gen_bitmap(0.5, -1e-6, 1, 600000, 800000, 1000000),
1689 // gap elsewhere
1690 gen_bitmap(1, -1e-6, 1, 300000, 500000, 1000000),
1691 0 // sentinel
1692 };
1693
1694 for (int i = 0; r[i]; ++i) {
1695 for (int j = i + 1; r[j]; ++j) {
1696 roaring_bitmap_t *expected = synthesized_xor(r[i], r[j]);
1697 roaring_bitmap_t *copy = roaring_bitmap_copy(r[i]);
1698 roaring_bitmap_set_copy_on_write(copy, copy_on_write);
1699
1700 roaring_bitmap_xor_inplace(copy, r[j]);
1701
1702 bool is_equal = roaring_bitmap_equals(expected, copy);
1703 if (!is_equal) {
1704 printf("problem with i=%d j=%d\n", i, j);
1705 printf("copy's cardinality is %d and expected's is %d\n",
1706 (int)roaring_bitmap_get_cardinality(copy),
1707 (int)roaring_bitmap_get_cardinality(expected));
1708 show_difference(copy, expected);
1709 }
1710
1711 assert_true(is_equal);
1712 roaring_bitmap_free(expected);
1713 roaring_bitmap_free(copy);
1714 }
1715 }
1716 for (int i = 0; r[i]; ++i) roaring_bitmap_free(r[i]);
1717}
1718
1719void test_xor_inplace_true() { test_xor_inplace(true); }
1720
1721void test_xor_inplace_false() { test_xor_inplace(false); }
1722
1723void test_xor_lazy(bool copy_on_write) {
1724 roaring_bitmap_t *r1 = roaring_bitmap_create();
1725 roaring_bitmap_set_copy_on_write(r1, copy_on_write);
1726 roaring_bitmap_t *r2 = roaring_bitmap_create();
1727 roaring_bitmap_set_copy_on_write(r2, copy_on_write);
1728
1729 for (uint32_t i = 0; i < 300; ++i) {
1730 if (i % 2 == 0) roaring_bitmap_add(r1, i);
1731 if (i % 3 == 0) roaring_bitmap_add(r2, i);
1732 }
1733
1734 roaring_bitmap_t *r1_xor_r2 = roaring_bitmap_lazy_xor(r1, r2);
1735 roaring_bitmap_repair_after_lazy(r1_xor_r2);
1736
1737 roaring_bitmap_set_copy_on_write(r1_xor_r2, copy_on_write);
1738
1739 int ansctr = 0;
1740 for (int i = 0; i < 300; ++i) {
1741 if (((i % 2 == 0) || (i % 3 == 0)) && (i % 6 != 0)) {
1742 ansctr++;
1743 if (!roaring_bitmap_contains(r1_xor_r2, i))
1744 printf("missing %d\n", i);
1745 } else if (roaring_bitmap_contains(r1_xor_r2, i))
1746 printf("surplus %d\n", i);
1747 }
1748
1749 assert_int_equal(roaring_bitmap_get_cardinality(r1_xor_r2), ansctr);
1750
1751 roaring_bitmap_free(r1_xor_r2);
1752 roaring_bitmap_free(r2);
1753 roaring_bitmap_free(r1);
1754
1755 // some tougher tests on synthetic data
1756 roaring_bitmap_t *r[] = {
1757 // ascending density, last containers might be runs
1758 gen_bitmap(0.0, 1e-6, 1, 0, 0, 1000000),
1759 // descending density, first containers might be runs
1760 gen_bitmap(1.0, -1e-6, 1, 0, 0, 1000000),
1761 // uniformly rather sparse
1762 gen_bitmap(1e-5, 0.0, 1, 0, 0, 2000000),
1763 // uniformly rather sparse with runs
1764 gen_bitmap(1e-5, 0.0, 3, 0, 0, 2000000),
1765 // uniformly rather dense
1766 gen_bitmap(1e-1, 0.0, 1, 0, 0, 2000000),
1767 // ascending density but never too dense
1768 gen_bitmap(0.001, 1e-7, 1, 0, 0, 1000000),
1769 // ascending density but very sparse
1770 gen_bitmap(0.0, 1e-10, 1, 0, 0, 1000000),
1771 // descending with a gap
1772 gen_bitmap(0.5, -1e-6, 1, 600000, 800000, 1000000),
1773 // gap elsewhere
1774 gen_bitmap(1, -1e-6, 1, 300000, 500000, 1000000),
1775 0 // sentinel
1776 };
1777
1778 for (int i = 0; r[i]; ++i) {
1779 for (int j = i; r[j]; ++j) {
1780 roaring_bitmap_t *expected = synthesized_xor(r[i], r[j]);
1781
1782 roaring_bitmap_t *result = roaring_bitmap_lazy_xor(r[i], r[j]);
1783 roaring_bitmap_repair_after_lazy(result);
1784
1785 bool is_equal = roaring_bitmap_equals(expected, result);
1786 if (!is_equal) {
1787 printf("problem with i=%d j=%d\n", i, j);
1788 printf("result's cardinality is %d and expected's is %d\n",
1789 (int)roaring_bitmap_get_cardinality(result),
1790 (int)roaring_bitmap_get_cardinality(expected));
1791 show_difference(result, expected);
1792 }
1793
1794 assert_true(is_equal);
1795 roaring_bitmap_free(expected);
1796 roaring_bitmap_free(result);
1797 }
1798 }
1799 for (int i = 0; r[i]; ++i) roaring_bitmap_free(r[i]);
1800}
1801
1802void test_xor_lazy_true() { test_xor_lazy(true); }
1803
1804void test_xor_lazy_false() { test_xor_lazy(false); }
1805
1806void test_xor_lazy_inplace(bool copy_on_write) {
1807 roaring_bitmap_t *r1 = roaring_bitmap_create();
1808 roaring_bitmap_set_copy_on_write(r1, copy_on_write);
1809 roaring_bitmap_t *r2 = roaring_bitmap_create();
1810 roaring_bitmap_set_copy_on_write(r2, copy_on_write);
1811
1812 for (uint32_t i = 0; i < 300; ++i) {
1813 if (i % 2 == 0) roaring_bitmap_add(r1, i);
1814 if (i % 3 == 0) roaring_bitmap_add(r2, i);
1815 }
1816
1817 roaring_bitmap_t *r1_xor_r2 = roaring_bitmap_copy(r1);
1818 roaring_bitmap_set_copy_on_write(r1_xor_r2, copy_on_write);
1819
1820 roaring_bitmap_lazy_xor_inplace(r1_xor_r2, r2);
1821 roaring_bitmap_repair_after_lazy(r1_xor_r2);
1822
1823 int ansctr = 0;
1824 for (int i = 0; i < 300; ++i) {
1825 if (((i % 2 == 0) || (i % 3 == 0)) && (i % 6 != 0)) {
1826 ansctr++;
1827 if (!roaring_bitmap_contains(r1_xor_r2, i))
1828 printf("missing %d\n", i);
1829 } else if (roaring_bitmap_contains(r1_xor_r2, i))
1830 printf("surplus %d\n", i);
1831 }
1832
1833 assert_int_equal(roaring_bitmap_get_cardinality(r1_xor_r2), ansctr);
1834
1835 roaring_bitmap_free(r1_xor_r2);
1836 roaring_bitmap_free(r2);
1837 roaring_bitmap_free(r1);
1838
1839 // some tougher tests on synthetic data
1840 roaring_bitmap_t *r[] = {
1841 // ascending density, last containers might be runs
1842 gen_bitmap(0.0, 1e-6, 1, 0, 0, 1000000),
1843 // descending density, first containers might be runs
1844 gen_bitmap(1.0, -1e-6, 1, 0, 0, 1000000),
1845 // uniformly rather sparse
1846 gen_bitmap(1e-5, 0.0, 1, 0, 0, 2000000),
1847 // uniformly rather sparse with runs
1848 gen_bitmap(1e-5, 0.0, 3, 0, 0, 2000000),
1849 // uniformly rather dense
1850 gen_bitmap(1e-1, 0.0, 1, 0, 0, 2000000),
1851 // ascending density but never too dense
1852 gen_bitmap(0.001, 1e-7, 1, 0, 0, 1000000),
1853 // ascending density but very sparse
1854 gen_bitmap(0.0, 1e-10, 1, 0, 0, 1000000),
1855 // descending with a gap
1856 gen_bitmap(0.5, -1e-6, 1, 600000, 800000, 1000000),
1857 // gap elsewhere
1858 gen_bitmap(1, -1e-6, 1, 300000, 500000, 1000000),
1859 0 // sentinel
1860 };
1861
1862 for (int i = 0; r[i]; ++i) {
1863 for (int j = i; r[j]; ++j) {
1864 roaring_bitmap_t *expected = synthesized_xor(r[i], r[j]);
1865
1866 roaring_bitmap_t *result = roaring_bitmap_copy(r[i]);
1867 roaring_bitmap_lazy_xor_inplace(result, r[j]);
1868 roaring_bitmap_repair_after_lazy(result);
1869
1870 bool is_equal = roaring_bitmap_equals(expected, result);
1871 if (!is_equal) {
1872 printf("problem with i=%d j=%d\n", i, j);
1873 printf("result's cardinality is %d and expected's is %d\n",
1874 (int)roaring_bitmap_get_cardinality(result),
1875 (int)roaring_bitmap_get_cardinality(expected));
1876 show_difference(result, expected);
1877 }
1878
1879 assert_true(is_equal);
1880 roaring_bitmap_free(expected);
1881 roaring_bitmap_free(result);
1882 }
1883 }
1884 for (int i = 0; r[i]; ++i) roaring_bitmap_free(r[i]);
1885}
1886
1887void test_xor_lazy_inplace_true() { test_xor_lazy_inplace(true); }
1888
1889void test_xor_lazy_inplace_false() { test_xor_lazy_inplace(false); }
1890
1891static roaring_bitmap_t *roaring_from_sentinel_array(int *data,
1892 bool copy_on_write) {
1893 roaring_bitmap_t *ans = roaring_bitmap_create();
1894 roaring_bitmap_set_copy_on_write(ans, copy_on_write);
1895
1896 for (; *data != -1; ++data) {
1897 roaring_bitmap_add(ans, *data);
1898 }
1899 return ans;
1900}
1901
1902void test_andnot(bool copy_on_write) {
1903 roaring_bitmap_t *r1 = roaring_bitmap_create();
1904 roaring_bitmap_set_copy_on_write(r1, copy_on_write);
1905 roaring_bitmap_t *r2 = roaring_bitmap_create();
1906 roaring_bitmap_set_copy_on_write(r2, copy_on_write);
1907
1908 int data1[] = {1,
1909 2,
1910 65536 * 2 + 1,
1911 65536 * 2 + 2,
1912 65536 * 3 + 1,
1913 65536 * 3 + 2,
1914 65536 * 10 + 1,
1915 65536 * 10 + 2,
1916 65536 * 16 + 1,
1917 65536 * 16 + 2,
1918 65536 * 20 + 1,
1919 65536 * 21 + 1,
1920 -1};
1921 roaring_bitmap_t *rb1 = roaring_from_sentinel_array(data1, copy_on_write);
1922 int data2[] = {2,
1923 3,
1924 65536 * 10 + 2,
1925 65536 * 10 + 3,
1926 65536 * 12 + 2,
1927 65536 * 12 + 3,
1928 65536 * 14 + 2,
1929 65536 * 14 + 3,
1930 65536 * 16 + 2,
1931 65536 * 16 + 3,
1932 -1};
1933 roaring_bitmap_t *rb2 = roaring_from_sentinel_array(data2, copy_on_write);
1934
1935 int data3[] = {2,
1936 3,
1937 65536 * 10 + 1,
1938 65536 * 10 + 2,
1939 65536 * 12 + 2,
1940 65536 * 12 + 3,
1941 65536 * 14 + 2,
1942 65536 * 14 + 3,
1943 65536 * 16 + 2,
1944 65536 * 16 + 3,
1945 -1};
1946 roaring_bitmap_t *rb3 = roaring_from_sentinel_array(data3, copy_on_write);
1947 int d1_minus_d2[] = {1,
1948 65536 * 2 + 1,
1949 65536 * 2 + 2,
1950 65536 * 3 + 1,
1951 65536 * 3 + 2,
1952 65536 * 10 + 1,
1953 65536 * 16 + 1,
1954 65536 * 20 + 1,
1955 65536 * 21 + 1,
1956 -1};
1957 roaring_bitmap_t *rb1_minus_rb2 =
1958 roaring_from_sentinel_array(d1_minus_d2, copy_on_write);
1959
1960 int d1_minus_d3[] = {1, 65536 * 2 + 1, 65536 * 2 + 2, 65536 * 3 + 1,
1961 65536 * 3 + 2,
1962 // 65536*10+1,
1963 65536 * 16 + 1, 65536 * 20 + 1, 65536 * 21 + 1, -1};
1964 roaring_bitmap_t *rb1_minus_rb3 =
1965 roaring_from_sentinel_array(d1_minus_d3, copy_on_write);
1966
1967 int d2_minus_d1[] = {3,
1968 65536 * 10 + 3,
1969 65536 * 12 + 2,
1970 65536 * 12 + 3,
1971 65536 * 14 + 2,
1972 65536 * 14 + 3,
1973 65536 * 16 + 3,
1974 -1};
1975
1976 roaring_bitmap_t *rb2_minus_rb1 =
1977 roaring_from_sentinel_array(d2_minus_d1, copy_on_write);
1978
1979 int d3_minus_d1[] = {3,
1980 // 65536*10+3,
1981 65536 * 12 + 2, 65536 * 12 + 3, 65536 * 14 + 2,
1982 65536 * 14 + 3, 65536 * 16 + 3, -1};
1983 roaring_bitmap_t *rb3_minus_rb1 =
1984 roaring_from_sentinel_array(d3_minus_d1, copy_on_write);
1985
1986 int d3_minus_d2[] = {65536 * 10 + 1, -1};
1987 roaring_bitmap_t *rb3_minus_rb2 =
1988 roaring_from_sentinel_array(d3_minus_d2, copy_on_write);
1989
1990 roaring_bitmap_t *temp = roaring_bitmap_andnot(rb1, rb2);
1991 assert_true(roaring_bitmap_equals(rb1_minus_rb2, temp));
1992 roaring_bitmap_free(temp);
1993
1994 temp = roaring_bitmap_andnot(rb1, rb3);
1995 assert_true(roaring_bitmap_equals(rb1_minus_rb3, temp));
1996 roaring_bitmap_free(temp);
1997
1998 temp = roaring_bitmap_andnot(rb2, rb1);
1999 assert_true(roaring_bitmap_equals(rb2_minus_rb1, temp));
2000 roaring_bitmap_free(temp);
2001
2002 temp = roaring_bitmap_andnot(rb3, rb1);
2003 assert_true(roaring_bitmap_equals(rb3_minus_rb1, temp));
2004 roaring_bitmap_free(temp);
2005
2006 temp = roaring_bitmap_andnot(rb3, rb2);
2007 assert_true(roaring_bitmap_equals(rb3_minus_rb2, temp));
2008 roaring_bitmap_free(temp);
2009
2010 roaring_bitmap_t *large_run_bitmap =
2011 roaring_bitmap_from_range(2, 11 * 65536 + 27, 1);
2012 temp = roaring_bitmap_andnot(rb1, large_run_bitmap);
2013
2014 int d1_minus_largerun[] = {
2015 1, 65536 * 16 + 1, 65536 * 16 + 2, 65536 * 20 + 1, 65536 * 21 + 1, -1};
2016 roaring_bitmap_t *rb1_minus_largerun =
2017 roaring_from_sentinel_array(d1_minus_largerun, copy_on_write);
2018 assert_true(roaring_bitmap_equals(rb1_minus_largerun, temp));
2019 roaring_bitmap_free(temp);
2020
2021 roaring_bitmap_free(rb1);
2022 roaring_bitmap_free(rb2);
2023 roaring_bitmap_free(rb3);
2024 roaring_bitmap_free(rb1_minus_rb2);
2025 roaring_bitmap_free(rb1_minus_rb3);
2026 roaring_bitmap_free(rb2_minus_rb1);
2027 roaring_bitmap_free(rb3_minus_rb1);
2028 roaring_bitmap_free(rb3_minus_rb2);
2029 roaring_bitmap_free(rb1_minus_largerun);
2030 roaring_bitmap_free(large_run_bitmap);
2031
2032 for (uint32_t i = 0; i < 300; ++i) {
2033 if (i % 2 == 0) roaring_bitmap_add(r1, i);
2034 if (i % 3 == 0) roaring_bitmap_add(r2, i);
2035 }
2036
2037 roaring_bitmap_t *r1_andnot_r2 = roaring_bitmap_andnot(r1, r2);
2038 roaring_bitmap_set_copy_on_write(r1_andnot_r2, copy_on_write);
2039
2040 int ansctr = 0;
2041 for (int i = 0; i < 300; ++i) {
2042 if ((i % 2 == 0) && (i % 3 != 0)) {
2043 ansctr++;
2044 if (!roaring_bitmap_contains(r1_andnot_r2, i))
2045 printf("missing %d\n", i);
2046 } else if (roaring_bitmap_contains(r1_andnot_r2, i))
2047 printf("surplus %d\n", i);
2048 }
2049
2050 assert_int_equal(roaring_bitmap_get_cardinality(r1_andnot_r2), ansctr);
2051 roaring_bitmap_free(r1_andnot_r2);
2052 roaring_bitmap_free(r2);
2053 roaring_bitmap_free(r1);
2054
2055 // some tougher tests on synthetic data
2056
2057 roaring_bitmap_t *r[] = {
2058 // ascending density, last containers might be runs
2059 gen_bitmap(0.0, 1e-6, 1, 0, 0, 1000000),
2060 // descending density, first containers might be runs
2061 gen_bitmap(1.0, -1e-6, 1, 0, 0, 1000000),
2062 // uniformly rather sparse
2063 gen_bitmap(1e-5, 0.0, 1, 0, 0, 2000000),
2064 // uniformly rather sparse with runs
2065 gen_bitmap(1e-5, 0.0, 3, 0, 0, 2000000),
2066 // uniformly rather dense
2067 gen_bitmap(1e-1, 0.0, 1, 0, 0, 2000000),
2068 // ascending density but never too dense
2069 gen_bitmap(0.001, 1e-7, 1, 0, 0, 1000000),
2070 // ascending density but very sparse
2071 gen_bitmap(0.0, 1e-10, 1, 0, 0, 1000000),
2072 // descending with a gap
2073 gen_bitmap(0.5, -1e-6, 1, 600000, 800000, 1000000),
2074 // gap elsewhere
2075 gen_bitmap(1, -1e-6, 1, 300000, 500000, 1000000),
2076 0 // sentinel
2077 };
2078
2079 for (int i = 0; r[i]; ++i) {
2080 for (int j = i; r[j]; ++j) {
2081 roaring_bitmap_t *expected = synthesized_andnot(r[i], r[j]);
2082 roaring_bitmap_t *result = roaring_bitmap_andnot(r[i], r[j]);
2083
2084 bool is_equal = roaring_bitmap_equals(expected, result);
2085
2086 assert_true(is_equal);
2087 roaring_bitmap_free(expected);
2088 roaring_bitmap_free(result);
2089 }
2090 }
2091 for (int i = 0; r[i]; ++i) roaring_bitmap_free(r[i]);
2092}
2093
2094void test_andnot_true() { test_andnot(true); }
2095
2096void test_andnot_false() { test_andnot(false); }
2097
2098void test_andnot_inplace(bool copy_on_write) {
2099 roaring_bitmap_t *r1 = roaring_bitmap_create();
2100 roaring_bitmap_set_copy_on_write(r1, copy_on_write);
2101 roaring_bitmap_t *r2 = roaring_bitmap_create();
2102 roaring_bitmap_set_copy_on_write(r2, copy_on_write);
2103
2104 int data1[] = {1,
2105 2,
2106 65536 * 2 + 1,
2107 65536 * 2 + 2,
2108 65536 * 3 + 1,
2109 65536 * 3 + 2,
2110 65536 * 10 + 1,
2111 65536 * 10 + 2,
2112 65536 * 16 + 1,
2113 65536 * 16 + 2,
2114 65536 * 20 + 1,
2115 65536 * 21 + 1,
2116 -1};
2117 roaring_bitmap_t *rb1 = roaring_from_sentinel_array(data1, copy_on_write);
2118 int data2[] = {2,
2119 3,
2120 65536 * 10 + 2,
2121 65536 * 10 + 3,
2122 65536 * 12 + 2,
2123 65536 * 12 + 3,
2124 65536 * 14 + 2,
2125 65536 * 14 + 3,
2126 65536 * 16 + 2,
2127 65536 * 16 + 3,
2128 -1};
2129 roaring_bitmap_t *rb2 = roaring_from_sentinel_array(data2, copy_on_write);
2130
2131 int data3[] = {2,
2132 3,
2133 65536 * 10 + 1,
2134 65536 * 10 + 2,
2135 65536 * 12 + 2,
2136 65536 * 12 + 3,
2137 65536 * 14 + 2,
2138 65536 * 14 + 3,
2139 65536 * 16 + 2,
2140 65536 * 16 + 3,
2141 -1};
2142 roaring_bitmap_t *rb3 = roaring_from_sentinel_array(data3, copy_on_write);
2143 int d1_minus_d2[] = {1,
2144 65536 * 2 + 1,
2145 65536 * 2 + 2,
2146 65536 * 3 + 1,
2147 65536 * 3 + 2,
2148 65536 * 10 + 1,
2149 65536 * 16 + 1,
2150 65536 * 20 + 1,
2151 65536 * 21 + 1,
2152 -1};
2153 roaring_bitmap_t *rb1_minus_rb2 =
2154 roaring_from_sentinel_array(d1_minus_d2, copy_on_write);
2155
2156 int d1_minus_d3[] = {1, 65536 * 2 + 1, 65536 * 2 + 2, 65536 * 3 + 1,
2157 65536 * 3 + 2,
2158 // 65536*10+1,
2159 65536 * 16 + 1, 65536 * 20 + 1, 65536 * 21 + 1, -1};
2160 roaring_bitmap_t *rb1_minus_rb3 =
2161 roaring_from_sentinel_array(d1_minus_d3, copy_on_write);
2162
2163 int d2_minus_d1[] = {3,
2164 65536 * 10 + 3,
2165 65536 * 12 + 2,
2166 65536 * 12 + 3,
2167 65536 * 14 + 2,
2168 65536 * 14 + 3,
2169 65536 * 16 + 3,
2170 -1};
2171
2172 roaring_bitmap_t *rb2_minus_rb1 =
2173 roaring_from_sentinel_array(d2_minus_d1, copy_on_write);
2174
2175 int d3_minus_d1[] = {3,
2176 // 65536*10+3,
2177 65536 * 12 + 2, 65536 * 12 + 3, 65536 * 14 + 2,
2178 65536 * 14 + 3, 65536 * 16 + 3, -1};
2179 roaring_bitmap_t *rb3_minus_rb1 =
2180 roaring_from_sentinel_array(d3_minus_d1, copy_on_write);
2181
2182 int d3_minus_d2[] = {65536 * 10 + 1, -1};
2183 roaring_bitmap_t *rb3_minus_rb2 =
2184 roaring_from_sentinel_array(d3_minus_d2, copy_on_write);
2185
2186 roaring_bitmap_t *cpy = roaring_bitmap_copy(rb1);
2187 roaring_bitmap_andnot_inplace(cpy, rb2);
2188 assert_true(roaring_bitmap_equals(rb1_minus_rb2, cpy));
2189 roaring_bitmap_free(cpy);
2190
2191 cpy = roaring_bitmap_copy(rb1);
2192 roaring_bitmap_andnot_inplace(cpy, rb3);
2193 assert_true(roaring_bitmap_equals(rb1_minus_rb3, cpy));
2194 roaring_bitmap_free(cpy);
2195
2196 cpy = roaring_bitmap_copy(rb2);
2197 roaring_bitmap_andnot_inplace(cpy, rb1);
2198 assert_true(roaring_bitmap_equals(rb2_minus_rb1, cpy));
2199 roaring_bitmap_free(cpy);
2200
2201 cpy = roaring_bitmap_copy(rb3);
2202 roaring_bitmap_andnot_inplace(cpy, rb1);
2203 assert_true(roaring_bitmap_equals(rb3_minus_rb1, cpy));
2204 roaring_bitmap_free(cpy);
2205
2206 cpy = roaring_bitmap_copy(rb3);
2207 roaring_bitmap_andnot_inplace(cpy, rb2);
2208 assert_true(roaring_bitmap_equals(rb3_minus_rb2, cpy));
2209 roaring_bitmap_free(cpy);
2210
2211 roaring_bitmap_t *large_run_bitmap =
2212 roaring_bitmap_from_range(2, 11 * 65536 + 27, 1);
2213
2214 cpy = roaring_bitmap_copy(rb1);
2215 roaring_bitmap_andnot_inplace(cpy, large_run_bitmap);
2216
2217 int d1_minus_largerun[] = {
2218 1, 65536 * 16 + 1, 65536 * 16 + 2, 65536 * 20 + 1, 65536 * 21 + 1, -1};
2219 roaring_bitmap_t *rb1_minus_largerun =
2220 roaring_from_sentinel_array(d1_minus_largerun, copy_on_write);
2221 assert_true(roaring_bitmap_equals(rb1_minus_largerun, cpy));
2222 roaring_bitmap_free(cpy);
2223
2224 roaring_bitmap_free(rb1);
2225 roaring_bitmap_free(rb2);
2226 roaring_bitmap_free(rb3);
2227 roaring_bitmap_free(rb1_minus_rb2);
2228 roaring_bitmap_free(rb1_minus_rb3);
2229 roaring_bitmap_free(rb2_minus_rb1);
2230 roaring_bitmap_free(rb3_minus_rb1);
2231 roaring_bitmap_free(rb3_minus_rb2);
2232 roaring_bitmap_free(rb1_minus_largerun);
2233 roaring_bitmap_free(large_run_bitmap);
2234
2235 int diff_cardinality = 0;
2236 for (uint32_t i = 0; i < 300; ++i) {
2237 if (i % 2 == 0) roaring_bitmap_add(r1, i);
2238 if (i % 3 == 0) roaring_bitmap_add(r2, i);
2239 if ((i % 2 == 0) && (i % 3 != 0)) ++diff_cardinality;
2240 }
2241 roaring_bitmap_andnot_inplace(r1, r2);
2242 assert_int_equal(roaring_bitmap_get_cardinality(r1), diff_cardinality);
2243
2244 roaring_bitmap_free(r2);
2245 roaring_bitmap_free(r1);
2246
2247 // some tougher tests on synthetic data
2248
2249 roaring_bitmap_t *r[] = {
2250 // ascending density, last containers might be runs
2251 gen_bitmap(0.0, 1e-6, 1, 0, 0, 1000000),
2252 // descending density, first containers might be runs
2253 gen_bitmap(1.0, -1e-6, 1, 0, 0, 1000000),
2254 // uniformly rather sparse
2255 gen_bitmap(1e-5, 0.0, 1, 0, 0, 2000000),
2256 // uniformly rather sparse with runs
2257 gen_bitmap(1e-5, 0.0, 3, 0, 0, 2000000),
2258 // uniformly rather dense
2259 gen_bitmap(1e-1, 0.0, 1, 0, 0, 2000000),
2260 // ascending density but never too dense
2261 gen_bitmap(0.001, 1e-7, 1, 0, 0, 1000000),
2262 // ascending density but very sparse
2263 gen_bitmap(0.0, 1e-10, 1, 0, 0, 1000000),
2264 // descending with a gap
2265 gen_bitmap(0.5, -1e-6, 1, 600000, 800000, 1000000),
2266 // gap elsewhere
2267 gen_bitmap(1, -1e-6, 1, 300000, 500000, 1000000),
2268 0 // sentinel
2269 };
2270
2271 for (int i = 0; r[i]; ++i) {
2272 for (int j = i + 1; r[j]; ++j) {
2273 roaring_bitmap_t *expected = synthesized_andnot(r[i], r[j]);
2274 roaring_bitmap_t *copy = roaring_bitmap_copy(r[i]);
2275 roaring_bitmap_set_copy_on_write(copy, copy_on_write);
2276
2277 roaring_bitmap_andnot_inplace(copy, r[j]);
2278
2279 bool is_equal = roaring_bitmap_equals(expected, copy);
2280 if (!is_equal) {
2281 printf("problem with i=%d j=%d\n", i, j);
2282 printf("copy's cardinality is %d and expected's is %d\n",
2283 (int)roaring_bitmap_get_cardinality(copy),
2284 (int)roaring_bitmap_get_cardinality(expected));
2285 show_difference(copy, expected);
2286 }
2287
2288 assert_true(is_equal);
2289 roaring_bitmap_free(expected);
2290 roaring_bitmap_free(copy);
2291 }
2292 }
2293 for (int i = 0; r[i]; ++i) roaring_bitmap_free(r[i]);
2294}
2295
2296void test_andnot_inplace_true() { test_andnot_inplace(true); }
2297
2298void test_andnot_inplace_false() { test_xor_inplace(false); }
2299
2300static roaring_bitmap_t *make_roaring_from_array(uint32_t *a, int len) {
2301 roaring_bitmap_t *r1 = roaring_bitmap_create();
2302 for (int i = 0; i < len; ++i) roaring_bitmap_add(r1, a[i]);
2303 return r1;
2304}
2305
2306void test_conversion_to_int_array() {
2307 int ans_ctr = 0;
2308 uint32_t *ans = calloc(100000, sizeof(int32_t));
2309
2310 // a dense bitmap container (best done with runs)
2311 for (uint32_t i = 0; i < 50000; ++i) {
2312 if (i != 30000) { // making 2 runs
2313 ans[ans_ctr++] = i;
2314 }
2315 }
2316
2317 // a sparse one
2318 for (uint32_t i = 70000; i < 130000; i += 17) {
2319 ans[ans_ctr++] = i;
2320 }
2321
2322 // a dense one but not good for runs
2323
2324 for (uint32_t i = 65536 * 3; i < 65536 * 4; i++) {
2325 if (i % 3 != 0) {
2326 ans[ans_ctr++] = i;
2327 }
2328 }
2329
2330 roaring_bitmap_t *r1 = make_roaring_from_array(ans, ans_ctr);
2331
2332 uint64_t card = roaring_bitmap_get_cardinality(r1);
2333 uint32_t *arr = (uint32_t *)malloc(card * sizeof(uint32_t));
2334 roaring_bitmap_to_uint32_array(r1, arr);
2335
2336 assert_true(array_equals(arr, (int)card, ans, ans_ctr));
2337 roaring_bitmap_free(r1);
2338 free(arr);
2339 free(ans);
2340}
2341
2342void test_conversion_to_int_array_with_runoptimize() {
2343 roaring_bitmap_t *r1 = roaring_bitmap_create();
2344 int ans_ctr = 0;
2345 uint32_t *ans = calloc(100000, sizeof(int32_t));
2346
2347 // a dense bitmap container (best done with runs)
2348 for (uint32_t i = 0; i < 50000; ++i) {
2349 if (i != 30000) { // making 2 runs
2350 ans[ans_ctr++] = i;
2351 }
2352 }
2353
2354 // a sparse one
2355 for (uint32_t i = 70000; i < 130000; i += 17) {
2356 ans[ans_ctr++] = i;
2357 }
2358
2359 // a dense one but not good for runs
2360
2361 for (uint32_t i = 65536 * 3; i < 65536 * 4; i++) {
2362 if (i % 3 != 0) {
2363 ans[ans_ctr++] = i;
2364 }
2365 }
2366 roaring_bitmap_free(r1);
2367
2368 r1 = make_roaring_from_array(ans, ans_ctr);
2369 assert_true(roaring_bitmap_run_optimize(r1));
2370
2371 uint64_t card = roaring_bitmap_get_cardinality(r1);
2372 uint32_t *arr = (uint32_t *)malloc(card * sizeof(uint32_t));
2373 roaring_bitmap_to_uint32_array(r1, arr);
2374
2375 assert_true(array_equals(arr, (int)card, ans, ans_ctr));
2376 roaring_bitmap_free(r1);
2377 free(arr);
2378 free(ans);
2379}
2380
2381void test_array_to_run() {
2382 int ans_ctr = 0;
2383 uint32_t *ans = calloc(100000, sizeof(int32_t));
2384
2385 // array container (best done with runs)
2386 for (uint32_t i = 0; i < 500; ++i) {
2387 if (i != 300) { // making 2 runs
2388 ans[ans_ctr++] = 65536 + i;
2389 }
2390 }
2391
2392 roaring_bitmap_t *r1 = make_roaring_from_array(ans, ans_ctr);
2393 assert_true(roaring_bitmap_run_optimize(r1));
2394
2395 uint64_t card = roaring_bitmap_get_cardinality(r1);
2396 uint32_t *arr = (uint32_t *)malloc(card * sizeof(uint32_t));
2397 roaring_bitmap_to_uint32_array(r1, arr);
2398
2399 assert_true(array_equals(arr, (int)card, ans, ans_ctr));
2400 roaring_bitmap_free(r1);
2401 free(arr);
2402 free(ans);
2403}
2404
2405void test_array_to_self() {
2406 int ans_ctr = 0;
2407
2408 uint32_t *ans = calloc(100000, sizeof(int32_t));
2409
2410 // array container (best not done with runs)
2411 for (uint32_t i = 0; i < 500; i += 2) {
2412 if (i != 300) { // making 2 runs
2413 ans[ans_ctr++] = 65536 + i;
2414 }
2415 }
2416
2417 roaring_bitmap_t *r1 = make_roaring_from_array(ans, ans_ctr);
2418 assert_false(roaring_bitmap_run_optimize(r1));
2419
2420 uint64_t card = roaring_bitmap_get_cardinality(r1);
2421 uint32_t *arr = (uint32_t *)malloc(card * sizeof(uint32_t));
2422 roaring_bitmap_to_uint32_array(r1, arr);
2423
2424 assert_true(array_equals(arr, (int)card, ans, ans_ctr));
2425 roaring_bitmap_free(r1);
2426 free(arr);
2427 free(ans);
2428}
2429
2430void test_bitset_to_self() {
2431 int ans_ctr = 0;
2432 uint32_t *ans = calloc(100000, sizeof(int32_t));
2433
2434 // bitset container (best not done with runs)
2435 for (uint32_t i = 0; i < 50000; i += 2) {
2436 if (i != 300) { // making 2 runs
2437 ans[ans_ctr++] = 65536 + i;
2438 }
2439 }
2440
2441 roaring_bitmap_t *r1 = make_roaring_from_array(ans, ans_ctr);
2442 assert_false(roaring_bitmap_run_optimize(r1));
2443
2444 uint64_t card = roaring_bitmap_get_cardinality(r1);
2445 uint32_t *arr = (uint32_t *)malloc(card * sizeof(uint32_t));
2446 roaring_bitmap_to_uint32_array(r1, arr);
2447
2448 assert_true(array_equals(arr, (int)card, ans, ans_ctr));
2449 roaring_bitmap_free(r1);
2450 free(arr);
2451 free(ans);
2452}
2453
2454void test_bitset_to_run() {
2455 int ans_ctr = 0;
2456 uint32_t *ans = calloc(100000, sizeof(int32_t));
2457
2458 // bitset container (best done with runs)
2459 for (uint32_t i = 0; i < 50000; i++) {
2460 if (i != 300) { // making 2 runs
2461 ans[ans_ctr++] = 65536 + i;
2462 }
2463 }
2464
2465 roaring_bitmap_t *r1 = make_roaring_from_array(ans, ans_ctr);
2466 assert(roaring_bitmap_run_optimize(r1));
2467
2468 uint64_t card = roaring_bitmap_get_cardinality(r1);
2469 uint32_t *arr = (uint32_t *)malloc(card * sizeof(uint32_t));
2470 roaring_bitmap_to_uint32_array(r1, arr);
2471
2472 assert_true(array_equals(arr, (int)card, ans, ans_ctr));
2473 roaring_bitmap_free(r1);
2474 free(arr);
2475 free(ans);
2476}
2477
2478// not sure how to get containers that are runcontainers but not efficient
2479
2480void test_run_to_self() {
2481 int ans_ctr = 0;
2482 uint32_t *ans = calloc(100000, sizeof(int32_t));
2483
2484 // bitset container (best done with runs)
2485 for (uint32_t i = 0; i < 50000; i++) {
2486 if (i != 300) { // making 2 runs
2487 ans[ans_ctr++] = 65536 + i;
2488 }
2489 }
2490
2491 roaring_bitmap_t *r1 = make_roaring_from_array(ans, ans_ctr);
2492 bool b = roaring_bitmap_run_optimize(r1); // will make a run container
2493 b = roaring_bitmap_run_optimize(r1); // we hope it will keep it
2494 assert_true(b); // still true there is a runcontainer
2495
2496 uint64_t card = roaring_bitmap_get_cardinality(r1);
2497 uint32_t *arr = (uint32_t *)malloc(card * sizeof(uint32_t));
2498 roaring_bitmap_to_uint32_array(r1, arr);
2499
2500 assert_true(array_equals(arr, (int)card, ans, ans_ctr));
2501 roaring_bitmap_free(r1);
2502 free(arr);
2503 free(ans);
2504}
2505
2506void test_remove_run_to_bitset() {
2507 int ans_ctr = 0;
2508 uint32_t *ans = calloc(100000, sizeof(int32_t));
2509
2510 // bitset container (best done with runs)
2511 for (uint32_t i = 0; i < 50000; i++) {
2512 if (i != 300) { // making 2 runs
2513 ans[ans_ctr++] = 65536 + i;
2514 }
2515 }
2516
2517 roaring_bitmap_t *r1 = make_roaring_from_array(ans, ans_ctr);
2518 assert_true(roaring_bitmap_run_optimize(r1)); // will make a run container
2519 assert_true(roaring_bitmap_remove_run_compression(r1)); // removal done
2520 assert_true(
2521 roaring_bitmap_run_optimize(r1)); // there is again a run container
2522
2523 uint64_t card = roaring_bitmap_get_cardinality(r1);
2524 uint32_t *arr = (uint32_t *)malloc(card * sizeof(uint32_t));
2525 roaring_bitmap_to_uint32_array(r1, arr);
2526
2527 assert_true(array_equals(arr, (int)card, ans, ans_ctr));
2528 roaring_bitmap_free(r1);
2529 free(arr);
2530 free(ans);
2531}
2532
2533void test_remove_run_to_array() {
2534 int ans_ctr = 0;
2535 uint32_t *ans = calloc(100000, sizeof(int32_t));
2536
2537 // array (best done with runs)
2538 for (uint32_t i = 0; i < 500; i++) {
2539 if (i != 300) { // making 2 runs
2540 ans[ans_ctr++] = 65536 + i;
2541 }
2542 }
2543
2544 roaring_bitmap_t *r1 = make_roaring_from_array(ans, ans_ctr);
2545 assert_true(roaring_bitmap_run_optimize(r1)); // will make a run container
2546 assert_true(roaring_bitmap_remove_run_compression(r1)); // removal done
2547 assert_true(
2548 roaring_bitmap_run_optimize(r1)); // there is again a run container
2549
2550 uint64_t card = roaring_bitmap_get_cardinality(r1);
2551 uint32_t *arr = (uint32_t *)malloc(card * sizeof(uint32_t));
2552 roaring_bitmap_to_uint32_array(r1, arr);
2553
2554 assert_true(array_equals(arr, (int)card, ans, ans_ctr));
2555 roaring_bitmap_free(r1);
2556 free(arr);
2557 free(ans);
2558}
2559
2560// array in, array out
2561void test_negation_array0() {
2562 roaring_bitmap_t *r1 = roaring_bitmap_create();
2563 assert_non_null(r1);
2564
2565 roaring_bitmap_t *notted_r1 = roaring_bitmap_flip(r1, 200U, 500U);
2566 assert_non_null(notted_r1);
2567 assert_int_equal(300, roaring_bitmap_get_cardinality(notted_r1));
2568
2569 roaring_bitmap_free(notted_r1);
2570 roaring_bitmap_free(r1);
2571}
2572
2573// array in, array out
2574void test_negation_array1() {
2575 roaring_bitmap_t *r1 = roaring_bitmap_create();
2576 assert_non_null(r1);
2577
2578 roaring_bitmap_add(r1, 1);
2579 roaring_bitmap_add(r1, 2);
2580 // roaring_bitmap_add(r1,3);
2581 roaring_bitmap_add(r1, 4);
2582 roaring_bitmap_add(r1, 5);
2583 roaring_bitmap_t *notted_r1 = roaring_bitmap_flip(r1, 2U, 5U);
2584 assert_non_null(notted_r1);
2585 assert_int_equal(3, roaring_bitmap_get_cardinality(notted_r1));
2586
2587 roaring_bitmap_free(notted_r1);
2588 roaring_bitmap_free(r1);
2589}
2590
2591// arrays to bitmaps and runs
2592void test_negation_array2() {
2593 roaring_bitmap_t *r1 = roaring_bitmap_create();
2594 assert_non_null(r1);
2595
2596 for (uint32_t i = 0; i < 100; ++i) {
2597 roaring_bitmap_add(r1, 2 * i);
2598 roaring_bitmap_add(r1, 5 * 65536 + 2 * i);
2599 }
2600
2601 assert_int_equal(roaring_bitmap_get_cardinality(r1), 200);
2602
2603 // get the first batch of ones but not the second
2604 roaring_bitmap_t *notted_r1 = roaring_bitmap_flip(r1, 0U, 100000U);
2605 assert_non_null(notted_r1);
2606
2607 // lose 100 for key 0, but gain 100 for key 5
2608 assert_int_equal(100000, roaring_bitmap_get_cardinality(notted_r1));
2609 roaring_bitmap_free(notted_r1);
2610
2611 // flip all ones and beyond
2612 notted_r1 = roaring_bitmap_flip(r1, 0U, 1000000U);
2613 assert_non_null(notted_r1);
2614 assert_int_equal(1000000 - 200, roaring_bitmap_get_cardinality(notted_r1));
2615 roaring_bitmap_free(notted_r1);
2616
2617 // Flip some bits in the middle
2618 notted_r1 = roaring_bitmap_flip(r1, 100000U, 200000U);
2619 assert_non_null(notted_r1);
2620 assert_int_equal(100000 + 200, roaring_bitmap_get_cardinality(notted_r1));
2621 roaring_bitmap_free(notted_r1);
2622
2623 // flip almost all of the bits, end at an even boundary
2624 notted_r1 = roaring_bitmap_flip(r1, 1U, 65536 * 6);
2625 assert_non_null(notted_r1);
2626 assert_int_equal(65536 * 6 - 200 + 1,
2627 roaring_bitmap_get_cardinality(notted_r1));
2628 roaring_bitmap_free(notted_r1);
2629
2630 // flip first bunch of the bits, end at an even boundary
2631 notted_r1 = roaring_bitmap_flip(r1, 1U, 65536 * 5);
2632 assert_non_null(notted_r1);
2633 assert_int_equal(65536 * 5 - 100 + 1 + 100,
2634 roaring_bitmap_get_cardinality(notted_r1));
2635 roaring_bitmap_free(notted_r1);
2636
2637 roaring_bitmap_free(r1);
2638}
2639
2640// bitmaps to bitmaps and runs
2641void test_negation_bitset1() {
2642 roaring_bitmap_t *r1 = roaring_bitmap_create();
2643 assert_non_null(r1);
2644
2645 for (uint32_t i = 0; i < 25000; ++i) {
2646 roaring_bitmap_add(r1, 2 * i);
2647 roaring_bitmap_add(r1, 5 * 65536 + 2 * i);
2648 }
2649
2650 assert_int_equal(roaring_bitmap_get_cardinality(r1), 50000);
2651
2652 // get the first batch of ones but not the second
2653 roaring_bitmap_t *notted_r1 = roaring_bitmap_flip(r1, 0U, 100000U);
2654 assert_non_null(notted_r1);
2655
2656 // lose 25000 for key 0, but gain 25000 for key 5
2657 assert_int_equal(100000, roaring_bitmap_get_cardinality(notted_r1));
2658 roaring_bitmap_free(notted_r1);
2659
2660 // flip all ones and beyond
2661 notted_r1 = roaring_bitmap_flip(r1, 0U, 1000000U);
2662 assert_non_null(notted_r1);
2663 assert_int_equal(1000000 - 50000,
2664 roaring_bitmap_get_cardinality(notted_r1));
2665 roaring_bitmap_free(notted_r1);
2666
2667 // Flip some bits in the middle
2668 notted_r1 = roaring_bitmap_flip(r1, 100000U, 200000U);
2669 assert_non_null(notted_r1);
2670 assert_int_equal(100000 + 50000, roaring_bitmap_get_cardinality(notted_r1));
2671 roaring_bitmap_free(notted_r1);
2672
2673 // flip almost all of the bits, end at an even boundary
2674 notted_r1 = roaring_bitmap_flip(r1, 1U, 65536 * 6);
2675 assert_non_null(notted_r1);
2676 assert_int_equal(65536 * 6 - 50000 + 1,
2677 roaring_bitmap_get_cardinality(notted_r1));
2678 roaring_bitmap_free(notted_r1);
2679
2680 // flip first bunch of the bits, end at an even boundary
2681 notted_r1 = roaring_bitmap_flip(r1, 1U, 65536 * 5);
2682 assert_non_null(notted_r1);
2683 assert_int_equal(65536 * 5 - 25000 + 1 + 25000,
2684 roaring_bitmap_get_cardinality(notted_r1));
2685 roaring_bitmap_free(notted_r1);
2686
2687 roaring_bitmap_free(r1);
2688}
2689
2690void test_negation_helper(bool runopt, uint32_t gap) {
2691 roaring_bitmap_t *r1 = roaring_bitmap_create();
2692 assert_non_null(r1);
2693
2694 for (uint32_t i = 0; i < 65536; ++i) {
2695 if (i % 147 < gap) continue;
2696 roaring_bitmap_add(r1, i);
2697 roaring_bitmap_add(r1, 5 * 65536 + i);
2698 }
2699 if (runopt) {
2700 bool hasrun = roaring_bitmap_run_optimize(r1);
2701 assert_true(hasrun);
2702 }
2703
2704 int orig_card = (int) roaring_bitmap_get_cardinality(r1);
2705
2706 // get the first batch of ones but not the second
2707 roaring_bitmap_t *notted_r1 = roaring_bitmap_flip(r1, 0U, 100000U);
2708 assert_non_null(notted_r1);
2709
2710 // lose some for key 0, but gain same num for key 5
2711 assert_int_equal(100000, roaring_bitmap_get_cardinality(notted_r1));
2712 roaring_bitmap_free(notted_r1);
2713
2714 // flip all ones and beyond
2715 notted_r1 = roaring_bitmap_flip(r1, 0U, 1000000U);
2716 assert_non_null(notted_r1);
2717 assert_int_equal(1000000 - orig_card,
2718 roaring_bitmap_get_cardinality(notted_r1));
2719 roaring_bitmap_free(notted_r1);
2720
2721 // Flip some bits in the middle
2722 notted_r1 = roaring_bitmap_flip(r1, 100000U, 200000U);
2723 assert_non_null(notted_r1);
2724 assert_int_equal(100000 + orig_card,
2725 roaring_bitmap_get_cardinality(notted_r1));
2726 roaring_bitmap_free(notted_r1);
2727
2728 // flip almost all of the bits, end at an even boundary
2729 notted_r1 = roaring_bitmap_flip(r1, 1U, 65536 * 6);
2730 assert_non_null(notted_r1);
2731 assert_int_equal((65536 * 6 - 1) - orig_card,
2732 roaring_bitmap_get_cardinality(notted_r1));
2733 roaring_bitmap_free(notted_r1);
2734
2735 // flip first bunch of the bits, end at an even boundary
2736 notted_r1 = roaring_bitmap_flip(r1, 1U, 65536 * 5);
2737 assert_non_null(notted_r1);
2738 assert_int_equal(65536 * 5 - 1 - (orig_card / 2) + (orig_card / 2),
2739 roaring_bitmap_get_cardinality(notted_r1));
2740 roaring_bitmap_free(notted_r1);
2741
2742 roaring_bitmap_free(r1);
2743}
2744
2745// bitmaps to arrays and runs
2746void test_negation_bitset2() { test_negation_helper(false, 2); }
2747
2748// runs to arrays
2749void test_negation_run1() { test_negation_helper(true, 1); }
2750
2751// runs to runs
2752void test_negation_run2() { test_negation_helper(true, 30); }
2753
2754/* Now, same thing except inplace. At this level, cannot really know if
2755 * inplace
2756 * done */
2757
2758// array in, array out
2759void test_inplace_negation_array0() {
2760 roaring_bitmap_t *r1 = roaring_bitmap_create();
2761 assert_non_null(r1);
2762
2763 roaring_bitmap_flip_inplace(r1, 200U, 500U);
2764 assert_non_null(r1);
2765 assert_int_equal(300, roaring_bitmap_get_cardinality(r1));
2766
2767 roaring_bitmap_free(r1);
2768}
2769
2770// array in, array out
2771void test_inplace_negation_array1() {
2772 roaring_bitmap_t *r1 = roaring_bitmap_create();
2773 assert_non_null(r1);
2774
2775 roaring_bitmap_add(r1, 1);
2776 roaring_bitmap_add(r1, 2);
2777
2778 roaring_bitmap_add(r1, 4);
2779 roaring_bitmap_add(r1, 5);
2780 roaring_bitmap_flip_inplace(r1, 2U, 5U);
2781 assert_non_null(r1);
2782 assert_int_equal(3, roaring_bitmap_get_cardinality(r1));
2783
2784 roaring_bitmap_free(r1);
2785}
2786
2787// arrays to bitmaps and runs
2788void test_inplace_negation_array2() {
2789 roaring_bitmap_t *r1 = roaring_bitmap_create();
2790 assert_non_null(r1);
2791
2792 for (uint32_t i = 0; i < 100; ++i) {
2793 roaring_bitmap_add(r1, 2 * i);
2794 roaring_bitmap_add(r1, 5 * 65536 + 2 * i);
2795 }
2796 roaring_bitmap_t *r1_orig = roaring_bitmap_copy(r1);
2797
2798 assert_int_equal(roaring_bitmap_get_cardinality(r1), 200);
2799
2800 // get the first batch of ones but not the second
2801 roaring_bitmap_flip_inplace(r1, 0U, 100000U);
2802 assert_non_null(r1);
2803
2804 // lose 100 for key 0, but gain 100 for key 5
2805 assert_int_equal(100000, roaring_bitmap_get_cardinality(r1));
2806 roaring_bitmap_free(r1);
2807 r1 = roaring_bitmap_copy(r1_orig);
2808
2809 // flip all ones and beyond
2810 roaring_bitmap_flip_inplace(r1, 0U, 1000000U);
2811 assert_non_null(r1);
2812 assert_int_equal(1000000 - 200, roaring_bitmap_get_cardinality(r1));
2813 roaring_bitmap_free(r1);
2814 r1 = roaring_bitmap_copy(r1_orig);
2815
2816 // Flip some bits in the middle
2817 roaring_bitmap_flip_inplace(r1, 100000U, 200000U);
2818 assert_non_null(r1);
2819 assert_int_equal(100000 + 200, roaring_bitmap_get_cardinality(r1));
2820 roaring_bitmap_free(r1);
2821 r1 = roaring_bitmap_copy(r1_orig);
2822
2823 // flip almost all of the bits, end at an even boundary
2824 roaring_bitmap_flip_inplace(r1, 1U, 65536 * 6);
2825 assert_non_null(r1);
2826 assert_int_equal(65536 * 6 - 200 + 1, roaring_bitmap_get_cardinality(r1));
2827 roaring_bitmap_free(r1);
2828 r1 = roaring_bitmap_copy(r1_orig);
2829
2830 // flip first bunch of the bits, end at an even boundary
2831 roaring_bitmap_flip_inplace(r1, 1U, 65536 * 5);
2832 assert_non_null(r1);
2833 assert_int_equal(65536 * 5 - 100 + 1 + 100,
2834 roaring_bitmap_get_cardinality(r1));
2835 /* */
2836 roaring_bitmap_free(r1_orig);
2837 roaring_bitmap_free(r1);
2838}
2839
2840// bitmaps to bitmaps and runs
2841void test_inplace_negation_bitset1() {
2842 roaring_bitmap_t *r1 = roaring_bitmap_create();
2843 assert_non_null(r1);
2844
2845 for (uint32_t i = 0; i < 25000; ++i) {
2846 roaring_bitmap_add(r1, 2 * i);
2847 roaring_bitmap_add(r1, 5 * 65536 + 2 * i);
2848 }
2849
2850 roaring_bitmap_t *r1_orig = roaring_bitmap_copy(r1);
2851
2852 assert_int_equal(roaring_bitmap_get_cardinality(r1), 50000);
2853
2854 // get the first batch of ones but not the second
2855 roaring_bitmap_flip_inplace(r1, 0U, 100000U);
2856 assert_non_null(r1);
2857
2858 // lose 25000 for key 0, but gain 25000 for key 5
2859 assert_int_equal(100000, roaring_bitmap_get_cardinality(r1));
2860 roaring_bitmap_free(r1);
2861 r1 = roaring_bitmap_copy(r1_orig);
2862
2863 // flip all ones and beyond
2864 roaring_bitmap_flip_inplace(r1, 0U, 1000000U);
2865 assert_non_null(r1);
2866 assert_int_equal(1000000 - 50000, roaring_bitmap_get_cardinality(r1));
2867 roaring_bitmap_free(r1);
2868 r1 = roaring_bitmap_copy(r1_orig);
2869
2870 // Flip some bits in the middle
2871 roaring_bitmap_flip_inplace(r1, 100000U, 200000U);
2872 assert_non_null(r1);
2873 assert_int_equal(100000 + 50000, roaring_bitmap_get_cardinality(r1));
2874 roaring_bitmap_free(r1);
2875 r1 = roaring_bitmap_copy(r1_orig);
2876
2877 // flip almost all of the bits, end at an even boundary
2878 roaring_bitmap_flip_inplace(r1, 1U, 65536 * 6);
2879 assert_non_null(r1);
2880 assert_int_equal(65536 * 6 - 50000 + 1, roaring_bitmap_get_cardinality(r1));
2881 roaring_bitmap_free(r1);
2882 r1 = roaring_bitmap_copy(r1_orig);
2883
2884 // flip first bunch of the bits, end at an even boundary
2885 roaring_bitmap_flip_inplace(r1, 1U, 65536 * 5);
2886 assert_non_null(r1);
2887 assert_int_equal(65536 * 5 - 25000 + 1 + 25000,
2888 roaring_bitmap_get_cardinality(r1));
2889 roaring_bitmap_free(r1);
2890
2891 roaring_bitmap_free(r1_orig);
2892}
2893
2894void test_inplace_negation_helper(bool runopt, uint32_t gap) {
2895 roaring_bitmap_t *r1 = roaring_bitmap_create();
2896 assert_non_null(r1);
2897
2898 for (uint32_t i = 0; i < 65536; ++i) {
2899 if (i % 147 < gap) continue;
2900 roaring_bitmap_add(r1, i);
2901 roaring_bitmap_add(r1, 5 * 65536 + i);
2902 }
2903 if (runopt) {
2904 bool hasrun = roaring_bitmap_run_optimize(r1);
2905 assert_true(hasrun);
2906 }
2907
2908 int orig_card = (int) roaring_bitmap_get_cardinality(r1);
2909 roaring_bitmap_t *r1_orig = roaring_bitmap_copy(r1);
2910
2911 // get the first batch of ones but not the second
2912 roaring_bitmap_flip_inplace(r1, 0U, 100000U);
2913 assert_non_null(r1);
2914
2915 // lose some for key 0, but gain same num for key 5
2916 assert_int_equal(100000, roaring_bitmap_get_cardinality(r1));
2917 roaring_bitmap_free(r1);
2918
2919 // flip all ones and beyond
2920 r1 = roaring_bitmap_copy(r1_orig);
2921 roaring_bitmap_flip_inplace(r1, 0U, 1000000U);
2922 assert_non_null(r1);
2923 assert_int_equal(1000000 - orig_card, roaring_bitmap_get_cardinality(r1));
2924 roaring_bitmap_free(r1);
2925
2926 // Flip some bits in the middle
2927 r1 = roaring_bitmap_copy(r1_orig);
2928 roaring_bitmap_flip_inplace(r1, 100000U, 200000U);
2929 assert_non_null(r1);
2930 assert_int_equal(100000 + orig_card, roaring_bitmap_get_cardinality(r1));
2931 roaring_bitmap_free(r1);
2932
2933 // flip almost all of the bits, end at an even boundary
2934 r1 = roaring_bitmap_copy(r1_orig);
2935 roaring_bitmap_flip_inplace(r1, 1U, 65536 * 6);
2936 assert_non_null(r1);
2937 assert_int_equal((65536 * 6 - 1) - orig_card,
2938 roaring_bitmap_get_cardinality(r1));
2939 roaring_bitmap_free(r1);
2940
2941 // flip first bunch of the bits, end at an even boundary
2942 r1 = roaring_bitmap_copy(r1_orig);
2943 roaring_bitmap_flip_inplace(r1, 1U, 65536 * 5);
2944 assert_non_null(r1);
2945 assert_int_equal(65536 * 5 - 1 - (orig_card / 2) + (orig_card / 2),
2946 roaring_bitmap_get_cardinality(r1));
2947 roaring_bitmap_free(r1);
2948
2949 roaring_bitmap_free(r1_orig);
2950}
2951
2952// bitmaps to arrays and runs
2953void test_inplace_negation_bitset2() { test_inplace_negation_helper(false, 2); }
2954
2955// runs to arrays
2956void test_inplace_negation_run1() { test_inplace_negation_helper(true, 1); }
2957
2958// runs to runs
2959void test_inplace_negation_run2() { test_inplace_negation_helper(true, 30); }
2960
2961// runs to bitmaps is hard to do.
2962// TODO it
2963
2964void test_rand_flips() {
2965 srand(1234);
2966 const int min_runs = 1;
2967 const int flip_trials = 5; // these are expensive tests
2968 const int range = 2000000;
2969 char *input = malloc(range);
2970 char *output = malloc(range);
2971
2972 for (int card = 2; card < 1000000; card *= 8) {
2973 printf("test_rand_flips with attempted card %d", card);
2974
2975 roaring_bitmap_t *r = roaring_bitmap_create();
2976 memset(input, 0, range);
2977 for (int i = 0; i < card; ++i) {
2978 double f1 = our_rand() / (double)OUR_RAND_MAX;
2979 double f2 = our_rand() / (double)OUR_RAND_MAX;
2980 double f3 = our_rand() / (double)OUR_RAND_MAX;
2981 int pos = (int)(f1 * f2 * f3 *
2982 range); // denser at the start, sparser at end
2983 assert(pos < range);
2984 assert(pos >= 0);
2985 roaring_bitmap_add(r, pos);
2986 input[pos] = 1;
2987 }
2988 for (int i = 0; i < min_runs; ++i) {
2989 int startpos = our_rand() % (range / 2);
2990 for (int j = startpos; j < startpos + 65536 * 2; ++j)
2991 if (j % 147 < 100) {
2992 roaring_bitmap_add(r, j);
2993 input[j] = 1;
2994 }
2995 }
2996 roaring_bitmap_run_optimize(r);
2997 printf(" and actual card = %d\n",
2998 (int)roaring_bitmap_get_cardinality(r));
2999
3000 for (int i = 0; i < flip_trials; ++i) {
3001 int start = our_rand() % (range - 1);
3002 int len = our_rand() % (range - start);
3003 roaring_bitmap_t *ans = roaring_bitmap_flip(r, start, start + len);
3004 memcpy(output, input, range);
3005 for (int j = start; j < start + len; ++j) output[j] = 1 - input[j];
3006
3007 // verify answer
3008 for (int j = 0; j < range; ++j) {
3009 assert_true(((bool)output[j]) ==
3010 roaring_bitmap_contains(ans, j));
3011 }
3012
3013 roaring_bitmap_free(ans);
3014 }
3015 roaring_bitmap_free(r);
3016 }
3017 free(output);
3018 free(input);
3019}
3020
3021// randomized flipping test - inplace version
3022void test_inplace_rand_flips() {
3023 srand(1234);
3024 const int min_runs = 1;
3025 const int flip_trials = 5; // these are expensive tests
3026 const int range = 2000000;
3027 char *input = malloc(range);
3028 char *output = malloc(range);
3029
3030 for (int card = 2; card < 1000000; card *= 8) {
3031 roaring_bitmap_t *r = roaring_bitmap_create();
3032 memset(input, 0, range);
3033 for (int i = 0; i < card; ++i) {
3034 double f1 = our_rand() / (double)OUR_RAND_MAX;
3035 double f2 = our_rand() / (double)OUR_RAND_MAX;
3036 double f3 = our_rand() / (double)OUR_RAND_MAX;
3037 int pos = (int)(f1 * f2 * f3 *
3038 range); // denser at the start, sparser at end
3039 assert(pos < range);
3040 assert(pos >= 0);
3041 roaring_bitmap_add(r, pos);
3042 input[pos] = 1;
3043 }
3044 for (int i = 0; i < min_runs; ++i) {
3045 int startpos = our_rand() % (range / 2);
3046 for (int j = startpos; j < startpos + 65536 * 2; ++j)
3047 if (j % 147 < 100) {
3048 roaring_bitmap_add(r, j);
3049 input[j] = 1;
3050 }
3051 }
3052 roaring_bitmap_run_optimize(r);
3053
3054 roaring_bitmap_t *r_orig = roaring_bitmap_copy(r);
3055
3056 for (int i = 0; i < flip_trials; ++i) {
3057 int start = our_rand() % (range - 1);
3058 int len = our_rand() % (range - start);
3059
3060 roaring_bitmap_flip_inplace(r, start, start + len);
3061 memcpy(output, input, range);
3062 for (int j = start; j < start + len; ++j) output[j] = 1 - input[j];
3063
3064 // verify answer
3065 for (int j = 0; j < range; ++j) {
3066 assert_true(((bool)output[j]) == roaring_bitmap_contains(r, j));
3067 }
3068
3069 roaring_bitmap_free(r);
3070 r = roaring_bitmap_copy(r_orig);
3071 }
3072 roaring_bitmap_free(r_orig);
3073 roaring_bitmap_free(r);
3074 }
3075 free(output);
3076 free(input);
3077}
3078
3079void test_flip_array_container_removal() {
3080 roaring_bitmap_t *bm = roaring_bitmap_create();
3081 for (unsigned val = 0; val < 100; val++) {
3082 roaring_bitmap_add(bm, val);
3083 }
3084 roaring_bitmap_flip_inplace(bm, 0, 100);
3085 roaring_bitmap_free(bm);
3086}
3087
3088void test_flip_bitset_container_removal() {
3089 roaring_bitmap_t *bm = roaring_bitmap_create();
3090 for (unsigned val = 0; val < 10000; val++) {
3091 roaring_bitmap_add(bm, val);
3092 }
3093 roaring_bitmap_flip_inplace(bm, 0, 10000);
3094 roaring_bitmap_free(bm);
3095}
3096
3097void test_flip_run_container_removal() {
3098 roaring_bitmap_t *bm = roaring_bitmap_from_range(0, 10000, 1);
3099 roaring_bitmap_flip_inplace(bm, 0, 10000);
3100 roaring_bitmap_free(bm);
3101}
3102
3103void test_flip_run_container_removal2() {
3104 roaring_bitmap_t *bm = roaring_bitmap_from_range(0, 66002, 1);
3105 roaring_bitmap_flip_inplace(bm, 0, 987653576);
3106 roaring_bitmap_free(bm);
3107}
3108
3109// randomized test for rank query
3110void select_test() {
3111 srand(1234);
3112 const int min_runs = 1;
3113 const uint32_t range = 2000000;
3114 char *input = malloc(range);
3115
3116 for (int card = 2; card < 1000000; card *= 8) {
3117
3118 roaring_bitmap_t *r = roaring_bitmap_create();
3119 memset(input, 0, range);
3120 for (int i = 0; i < card; ++i) {
3121 double f1 = our_rand() / (double)OUR_RAND_MAX;
3122 double f2 = our_rand() / (double)OUR_RAND_MAX;
3123 double f3 = our_rand() / (double)OUR_RAND_MAX;
3124 uint32_t pos = (uint32_t)(f1 * f2 * f3 *
3125 range); // denser at the start, sparser at end
3126 assert(pos < range);
3127 roaring_bitmap_add(r, pos);
3128 input[pos] = 1;
3129 }
3130 for (int i = 0; i < min_runs; ++i) {
3131 int startpos = our_rand() % (range / 2);
3132 for (int j = startpos; j < startpos + 65536 * 2; ++j)
3133 if (j % 147 < 100) {
3134 roaring_bitmap_add(r, j);
3135 input[j] = 1;
3136 }
3137 }
3138 roaring_bitmap_run_optimize(r);
3139 uint64_t true_card = roaring_bitmap_get_cardinality(r);
3140
3141 roaring_bitmap_set_copy_on_write(r, true);
3142 roaring_bitmap_t *r_copy = roaring_bitmap_copy(r);
3143
3144 void *bitmaps[] = {r, r_copy};
3145 for (unsigned i_bm = 0; i_bm < 2; i_bm++) {
3146 uint32_t rank = 0;
3147 uint32_t element;
3148 for (uint32_t i = 0; i < true_card; i++) {
3149 if (input[i]) {
3150 assert_true(
3151 roaring_bitmap_select(bitmaps[i_bm], rank, &element));
3152 assert_int_equal(i, element);
3153 rank++;
3154 }
3155 }
3156 for (uint32_t n = 0; n < 10; n++) {
3157 assert_false(roaring_bitmap_select(bitmaps[i_bm], true_card + n,
3158 &element));
3159 }
3160 }
3161
3162 roaring_bitmap_free(r);
3163 roaring_bitmap_free(r_copy);
3164 }
3165 free(input);
3166}
3167
3168void test_maximum_minimum() {
3169 for (uint32_t mymin = 123; mymin < 1000000; mymin *= 2) {
3170 // just arrays
3171 roaring_bitmap_t *r = roaring_bitmap_create();
3172 uint32_t x = mymin;
3173 for (; x < 1000 + mymin; x += 100) {
3174 roaring_bitmap_add(r, x);
3175 }
3176 assert_true(roaring_bitmap_minimum(r) == mymin);
3177 assert_true(roaring_bitmap_maximum(r) == x - 100);
3178 // now bitmap
3179 x = mymin;
3180 for (; x < 64000 + mymin; x += 2) {
3181 roaring_bitmap_add(r, x);
3182 }
3183 assert_true(roaring_bitmap_minimum(r) == mymin);
3184 assert_true(roaring_bitmap_maximum(r) == x - 2);
3185 // now run
3186 x = mymin;
3187 for (; x < 64000 + mymin; x++) {
3188 roaring_bitmap_add(r, x);
3189 }
3190 roaring_bitmap_run_optimize(r);
3191 assert_true(roaring_bitmap_minimum(r) == mymin);
3192 assert_true(roaring_bitmap_maximum(r) == x - 1);
3193 roaring_bitmap_free(r);
3194 }
3195}
3196
3197static uint64_t rank(uint32_t *arr, size_t length, uint32_t x) {
3198 uint64_t sum = 0;
3199 for (size_t i = 0; i < length; ++i) {
3200 if (arr[i] > x) break;
3201 sum++;
3202 }
3203 return sum;
3204}
3205
3206void test_rank() {
3207 for (uint32_t mymin = 123; mymin < 1000000; mymin *= 2) {
3208 // just arrays
3209 roaring_bitmap_t *r = roaring_bitmap_create();
3210 uint32_t x = mymin;
3211 for (; x < 1000 + mymin; x += 100) {
3212 roaring_bitmap_add(r, x);
3213 }
3214 uint64_t card = roaring_bitmap_get_cardinality(r);
3215 uint32_t *ans = malloc(card * sizeof(uint32_t));
3216 roaring_bitmap_to_uint32_array(r, ans);
3217 for (uint32_t z = 0; z < 1000 + mymin + 10; z += 10) {
3218 uint64_t truerank = rank(ans, card, z);
3219 uint64_t computedrank = roaring_bitmap_rank(r, z);
3220 if (truerank != computedrank)
3221 printf("%d != %d \n", (int)truerank, (int)computedrank);
3222 assert_true(truerank == computedrank);
3223 }
3224 free(ans);
3225 // now bitmap
3226 x = mymin;
3227 for (; x < 64000 + mymin; x += 2) {
3228 roaring_bitmap_add(r, x);
3229 }
3230 card = roaring_bitmap_get_cardinality(r);
3231 ans = malloc(card * sizeof(uint32_t));
3232 roaring_bitmap_to_uint32_array(r, ans);
3233 for (uint32_t z = 0; z < 64000 + mymin + 10; z += 10) {
3234 uint64_t truerank = rank(ans, card, z);
3235 uint64_t computedrank = roaring_bitmap_rank(r, z);
3236 if (truerank != computedrank)
3237 printf("%d != %d \n", (int)truerank, (int)computedrank);
3238 assert_true(truerank == computedrank);
3239 }
3240 free(ans);
3241 // now run
3242 x = mymin;
3243 for (; x < 64000 + mymin; x++) {
3244 roaring_bitmap_add(r, x);
3245 }
3246 roaring_bitmap_run_optimize(r);
3247 card = roaring_bitmap_get_cardinality(r);
3248 ans = malloc(card * sizeof(uint32_t));
3249 roaring_bitmap_to_uint32_array(r, ans);
3250 for (uint32_t z = 0; z < 64000 + mymin + 10; z += 10) {
3251 uint64_t truerank = rank(ans, card, z);
3252 uint64_t computedrank = roaring_bitmap_rank(r, z);
3253 if (truerank != computedrank)
3254 printf("%d != %d \n", (int)truerank, (int)computedrank);
3255 assert_true(truerank == computedrank);
3256 }
3257 free(ans);
3258
3259 roaring_bitmap_free(r);
3260 }
3261}
3262
3263// Return a random value which does not belong to the roaring bitmap.
3264// Value will be lower than upper_bound.
3265uint32_t choose_missing_value(roaring_bitmap_t *rb, uint32_t upper_bound) {
3266 do {
3267 uint32_t value = our_rand() % upper_bound;
3268 if (!roaring_bitmap_contains(rb, value)) return value;
3269 } while (true);
3270}
3271
3272void test_intersect_small_run_bitset() {
3273 roaring_bitmap_t *rb1 = roaring_bitmap_from_range(0, 1, 1);
3274 roaring_bitmap_t *rb2 = roaring_bitmap_from_range(1, 8194, 2);
3275 assert_false(roaring_bitmap_intersect(rb1, rb2));
3276 roaring_bitmap_free(rb1);
3277 roaring_bitmap_free(rb2);
3278}
3279
3280void test_subset() {
3281 uint32_t value;
3282 roaring_bitmap_t *rb1 = roaring_bitmap_create();
3283 roaring_bitmap_t *rb2 = roaring_bitmap_create();
3284 assert_true(roaring_bitmap_is_subset(rb1, rb2));
3285 assert_false(roaring_bitmap_is_strict_subset(rb1, rb2));
3286 // Sparse values
3287 for (int i = 0; i < 1000; i++) {
3288 roaring_bitmap_add(rb2, choose_missing_value(rb2, UINT32_C(1) << 31));
3289 }
3290 assert_true(roaring_bitmap_is_subset(rb1, rb2));
3291 assert_true(roaring_bitmap_is_strict_subset(rb1, rb2));
3292 roaring_bitmap_or_inplace(rb1, rb2);
3293 assert_true(roaring_bitmap_is_subset(rb1, rb2));
3294 assert_false(roaring_bitmap_is_strict_subset(rb1, rb2));
3295 value = choose_missing_value(rb1, UINT32_C(1) << 31);
3296 roaring_bitmap_add(rb1, value);
3297 roaring_bitmap_add(rb2, choose_missing_value(rb1, UINT32_C(1) << 31));
3298 assert_false(roaring_bitmap_is_subset(rb1, rb2));
3299 assert_false(roaring_bitmap_is_strict_subset(rb1, rb2));
3300 roaring_bitmap_add(rb2, value);
3301 assert_true(roaring_bitmap_is_subset(rb1, rb2));
3302 assert_true(roaring_bitmap_is_strict_subset(rb1, rb2));
3303 // Dense values
3304 for (int i = 0; i < 50000; i++) {
3305 value = choose_missing_value(rb2, 1 << 17);
3306 roaring_bitmap_add(rb1, value);
3307 roaring_bitmap_add(rb2, value);
3308 }
3309 assert_true(roaring_bitmap_is_subset(rb1, rb2));
3310 assert_true(roaring_bitmap_is_strict_subset(rb1, rb2));
3311 value = choose_missing_value(rb2, 1 << 16);
3312 roaring_bitmap_add(rb1, value);
3313 roaring_bitmap_add(rb2, choose_missing_value(rb1, 1 << 16));
3314 assert_false(roaring_bitmap_is_subset(rb1, rb2));
3315 assert_false(roaring_bitmap_is_strict_subset(rb1, rb2));
3316 roaring_bitmap_add(rb2, value);
3317 assert_true(roaring_bitmap_is_subset(rb1, rb2));
3318 assert_true(roaring_bitmap_is_strict_subset(rb1, rb2));
3319 roaring_bitmap_free(rb1);
3320 roaring_bitmap_free(rb2);
3321}
3322
3323void test_or_many_memory_leak() {
3324 for(int i=0; i<10; i++) {
3325 roaring_bitmap_t *bm1 = roaring_bitmap_create();
3326 for(int j=0; j<10; j++) {
3327 roaring_bitmap_t *bm2 = roaring_bitmap_create();
3328 const roaring_bitmap_t *buff[] = {bm1, bm2};
3329 roaring_bitmap_t *bm3 = roaring_bitmap_or_many(2, buff);
3330 roaring_bitmap_free(bm2);
3331 roaring_bitmap_free(bm3);
3332 }
3333 roaring_bitmap_free(bm1);
3334 }
3335}
3336
3337void test_iterator_generate_data(uint32_t **values_out, uint32_t *count_out) {
3338 const size_t capacity = 1000*1000;
3339 uint32_t* values = malloc(sizeof(uint32_t) * capacity); // ascending order
3340 uint32_t count = 0;
3341 uint32_t base = 1234; // container index
3342
3343 // min allowed value
3344 values[count++] = 0;
3345
3346 // only the very first value in container is set
3347 values[count++] = base*65536;
3348 base += 2;
3349
3350 // only the very last value in container is set
3351 values[count++] = base*65536 + 65535;
3352 base += 2;
3353
3354 // fully filled container
3355 for (uint32_t i = 0; i < 65536; i++) {
3356 values[count++] = base*65536 + i;
3357 }
3358 base += 2;
3359
3360 // even values
3361 for (uint32_t i = 0; i < 65536; i += 2) {
3362 values[count++] = base*65536 + i;
3363 }
3364 base += 2;
3365
3366 // odd values
3367 for (uint32_t i = 1; i < 65536; i += 2) {
3368 values[count++] = base*65536 + i;
3369 }
3370 base += 2;
3371
3372 // each next 64-bit word is ROR'd by one
3373 for (uint32_t i = 0; i < 65536; i += 65) {
3374 values[count++] = base*65536 + i;
3375 }
3376 base += 2;
3377
3378 // runs of increasing length: 0, 1,0, 1,1,0, 1,1,1,0, ...
3379 for (uint32_t i = 0, run_index = 0; i < 65536; i++) {
3380 if (i != (run_index+1)*(run_index+2)/2-1) {
3381 values[count++] = base*65536 + i;
3382 } else {
3383 run_index++;
3384 }
3385 }
3386 base += 2;
3387
3388 // 00000XX, XXXXXX, XX0000
3389 for (uint32_t i = 65536-100; i < 65536; i++) {
3390 values[count++] = base*65536 + i;
3391 }
3392 base += 1;
3393 for (uint32_t i = 0; i < 65536; i++) {
3394 values[count++] = base*65536 + i;
3395 }
3396 base += 1;
3397 for (uint32_t i = 0; i < 100; i++) {
3398 values[count++] = base*65536 + i;
3399 }
3400 base += 2;
3401
3402 // random
3403 for (int i = 0; i < 65536; i += our_rand()%10+1) {
3404 values[count++] = base*65536 + i;
3405 }
3406 base += 2;
3407
3408 // max allowed value
3409 values[count++] = UINT32_MAX;
3410
3411 assert(count <= capacity);
3412 *values_out = values;
3413 *count_out = count;
3414}
3415
3416/*
3417 * Read bitmap in steps of given size, compare with reference values.
3418 * If step is UINT32_MAX (special value), then read single non-empty container at a time.
3419 */
3420void read_compare(roaring_bitmap_t* r, const uint32_t* ref_values, uint32_t ref_count, uint32_t step) {
3421 roaring_uint32_iterator_t *iter = roaring_create_iterator(r);
3422 uint32_t* buffer = malloc(sizeof(uint32_t) * (step == UINT32_MAX ? 65536 : step));
3423 while (ref_count > 0) {
3424 assert(iter->has_value == true);
3425 assert(iter->current_value == ref_values[0]);
3426
3427 uint32_t num_ask = step;
3428 if (step == UINT32_MAX) {
3429 num_ask = 0;
3430 for (uint32_t i = 0; i < ref_count; i++) {
3431 if ((ref_values[i]>>16) == (ref_values[0]>>16)) {
3432 num_ask++;
3433 } else {
3434 break;
3435 }
3436 }
3437 }
3438
3439 uint32_t num_got = roaring_read_uint32_iterator(iter, buffer, num_ask);
3440 assert(num_got == minimum_uint32(num_ask, ref_count));
3441 for (uint32_t i = 0; i < num_got; i++) {
3442 assert(ref_values[i] == buffer[i]);
3443 }
3444 ref_values += num_got;
3445 ref_count -= num_got;
3446 }
3447
3448 assert(iter->has_value == false);
3449 assert(iter->current_value == UINT32_MAX);
3450
3451 assert(roaring_read_uint32_iterator(iter, buffer, step) == 0);
3452 assert(iter->has_value == false);
3453 assert(iter->current_value == UINT32_MAX);
3454
3455 free(buffer);
3456 roaring_free_uint32_iterator(iter);
3457}
3458
3459void test_read_uint32_iterator(uint8_t type) {
3460 uint32_t* ref_values;
3461 uint32_t ref_count;
3462 test_iterator_generate_data(&ref_values, &ref_count);
3463
3464 roaring_bitmap_t *r = roaring_bitmap_create();
3465 for (uint32_t i = 0; i < ref_count; i++) {
3466 roaring_bitmap_add(r, ref_values[i]);
3467 }
3468 if (type != UINT8_MAX) {
3469 convert_all_containers(r, type);
3470 }
3471
3472 read_compare(r, ref_values, ref_count, 1);
3473 read_compare(r, ref_values, ref_count, 2);
3474 read_compare(r, ref_values, ref_count, 7);
3475 read_compare(r, ref_values, ref_count, ref_count-1);
3476 read_compare(r, ref_values, ref_count, ref_count);
3477 read_compare(r, ref_values, ref_count, UINT32_MAX); // special value
3478
3479 roaring_bitmap_free(r);
3480 free(ref_values);
3481}
3482
3483void test_read_uint32_iterator_array() {
3484 test_read_uint32_iterator(ARRAY_CONTAINER_TYPE_CODE);
3485}
3486void test_read_uint32_iterator_bitset() {
3487 test_read_uint32_iterator(BITSET_CONTAINER_TYPE_CODE);
3488}
3489void test_read_uint32_iterator_run() {
3490 test_read_uint32_iterator(RUN_CONTAINER_TYPE_CODE);
3491}
3492void test_read_uint32_iterator_native() {
3493 test_read_uint32_iterator(UINT8_MAX); // special value
3494}
3495
3496void test_previous_iterator(uint8_t type) {
3497 uint32_t* ref_values;
3498 uint32_t ref_count;
3499 test_iterator_generate_data(&ref_values, &ref_count);
3500
3501 roaring_bitmap_t *r = roaring_bitmap_create();
3502 for (uint32_t i = 0; i < ref_count; i++) {
3503 roaring_bitmap_add(r, ref_values[i]);
3504 }
3505 if (type != UINT8_MAX) {
3506 convert_all_containers(r, type);
3507 }
3508
3509 roaring_uint32_iterator_t iterator;
3510 roaring_init_iterator_last(r, &iterator);
3511 uint32_t count = 0;
3512
3513 do {
3514 assert(iterator.has_value);
3515 ++count;
3516 assert((int64_t)ref_count - (int64_t)count >= 0); // sanity check
3517 assert(ref_values[ref_count - count] == iterator.current_value);
3518 } while (roaring_previous_uint32_iterator(&iterator));
3519
3520 assert(ref_count == count);
3521
3522 roaring_bitmap_free(r);
3523 free(ref_values);
3524}
3525
3526void test_previous_iterator_array() {
3527 test_previous_iterator(ARRAY_CONTAINER_TYPE_CODE);
3528}
3529
3530void test_previous_iterator_bitset() {
3531 test_previous_iterator(BITSET_CONTAINER_TYPE_CODE);
3532}
3533
3534void test_previous_iterator_run() {
3535 test_previous_iterator(RUN_CONTAINER_TYPE_CODE);
3536}
3537
3538void test_previous_iterator_native() {
3539 test_previous_iterator(UINT8_MAX); // special value
3540}
3541
3542void test_iterator_reuse_retry_count(int retry_count){
3543 uint32_t* ref_values;
3544 uint32_t ref_count;
3545 test_iterator_generate_data(&ref_values, &ref_count);
3546
3547 roaring_bitmap_t* with_edges = roaring_bitmap_create();
3548 // We don't want min and max values inside this bitmap
3549 roaring_bitmap_t* without_edges = roaring_bitmap_create();
3550
3551 for (uint32_t i = 0; i < ref_count; i++) {
3552 roaring_bitmap_add(with_edges, ref_values[i]);
3553 if (i != 0 && i != ref_count - 1) {
3554 roaring_bitmap_add(without_edges, ref_values[i]);
3555 }
3556 }
3557
3558 // sanity checks
3559 assert(roaring_bitmap_contains(with_edges, 0));
3560 assert(roaring_bitmap_contains(with_edges, UINT32_MAX));
3561 assert(!roaring_bitmap_contains(without_edges, 0));
3562 assert(!roaring_bitmap_contains(without_edges, UINT32_MAX));
3563 assert(roaring_bitmap_get_cardinality(with_edges) - 2 == roaring_bitmap_get_cardinality(without_edges));
3564
3565 const roaring_bitmap_t* bitmaps[] = {with_edges, without_edges};
3566 int num_bitmaps = sizeof(bitmaps) / sizeof(bitmaps[0]);
3567
3568 for (int i = 0; i < num_bitmaps; ++i){
3569 roaring_uint32_iterator_t iterator;
3570 roaring_init_iterator(bitmaps[i], &iterator);
3571 assert(iterator.has_value);
3572 uint32_t first_value = iterator.current_value;
3573
3574 uint32_t count = 0;
3575 while (iterator.has_value) {
3576 count++;
3577 roaring_advance_uint32_iterator(&iterator);
3578 }
3579 assert(count == roaring_bitmap_get_cardinality(bitmaps[i]));
3580
3581 // Test advancing the iterator more times than necessary
3582 for (int retry = 0; retry < retry_count; ++retry) {
3583 roaring_advance_uint32_iterator(&iterator);
3584 }
3585
3586 // Using same iterator we want to go backwards through the list
3587 roaring_previous_uint32_iterator(&iterator);
3588 count = 0;
3589 while (iterator.has_value) {
3590 count++;
3591 roaring_previous_uint32_iterator(&iterator);
3592 }
3593 assert(count == roaring_bitmap_get_cardinality(bitmaps[i]));
3594
3595 // Test decrement the iterator more times than necessary
3596 for (int retry = 0; retry < retry_count; ++retry) {
3597 roaring_previous_uint32_iterator(&iterator);
3598 }
3599
3600 roaring_advance_uint32_iterator(&iterator);
3601 assert(iterator.has_value);
3602 assert(first_value == iterator.current_value);
3603 }
3604
3605
3606 roaring_bitmap_free(without_edges);
3607 roaring_bitmap_free(with_edges);
3608 free(ref_values);
3609}
3610
3611void test_iterator_reuse() {
3612 test_iterator_reuse_retry_count(0);
3613}
3614
3615void test_iterator_reuse_many() {
3616 test_iterator_reuse_retry_count(10);
3617}
3618
3619void test_add_range() {
3620 // autoconversion: BITSET -> BITSET -> RUN
3621 {
3622 sbs_t* sbs = sbs_create();
3623 sbs_add_value(sbs, 100);
3624 sbs_convert(sbs, BITSET_CONTAINER_TYPE_CODE);
3625 sbs_add_range(sbs, 0, 299);
3626 assert_true(sbs_check_type(sbs, BITSET_CONTAINER_TYPE_CODE));
3627 sbs_add_range(sbs, 301, 65535);
3628 assert_true(sbs_check_type(sbs, BITSET_CONTAINER_TYPE_CODE));
3629 // after and only after BITSET becomes [0, 65535], it is converted to RUN
3630 sbs_add_range(sbs, 300, 300);
3631 assert_true(sbs_check_type(sbs, RUN_CONTAINER_TYPE_CODE));
3632 sbs_compare(sbs);
3633 sbs_free(sbs);
3634 }
3635
3636 // autoconversion: ARRAY -> ARRAY -> BITSET
3637 {
3638 sbs_t* sbs = sbs_create();
3639 sbs_add_value(sbs, 100);
3640 sbs_convert(sbs, ARRAY_CONTAINER_TYPE_CODE);
3641
3642 // unless threshold was hit, it is still ARRAY
3643 for (int i = 0; i < 100; i += 2) {
3644 sbs_add_value(sbs, i);
3645 assert_true(sbs_check_type(sbs, ARRAY_CONTAINER_TYPE_CODE));
3646 }
3647
3648 // after threshold on number of elements was hit, it is converted to BITSET
3649 for (int i = 0; i < 65535; i += 2) {
3650 sbs_add_value(sbs, i);
3651 }
3652 assert_true(sbs_check_type(sbs, BITSET_CONTAINER_TYPE_CODE));
3653
3654 sbs_compare(sbs);
3655 sbs_free(sbs);
3656 }
3657
3658 // autoconversion: ARRAY -> RUN
3659 {
3660 sbs_t* sbs = sbs_create();
3661 sbs_add_range(sbs, 0, 100);
3662 sbs_convert(sbs, ARRAY_CONTAINER_TYPE_CODE);
3663
3664 // after ARRAY becomes full [0, 65535], it is converted to RUN
3665 sbs_add_range(sbs, 100, 65535);
3666 assert_true(sbs_check_type(sbs, RUN_CONTAINER_TYPE_CODE));
3667
3668 sbs_compare(sbs);
3669 sbs_free(sbs);
3670 }
3671 // autoconversion: RUN -> RUN -> BITSET
3672 {
3673 sbs_t* sbs = sbs_create();
3674 // by default, RUN container is used
3675 for (int i = 0; i < 100; i += 2) {
3676 sbs_add_range(sbs, 4*i, 4*i + 1);
3677 assert_true(sbs_check_type(sbs, RUN_CONTAINER_TYPE_CODE));
3678 }
3679 // after number of RLE runs exceeded threshold, it is converted to BITSET
3680 for (int i = 0; i < 65535; i += 2) {
3681 sbs_add_range(sbs, i, i);
3682 }
3683 assert_true(sbs_check_type(sbs, BITSET_CONTAINER_TYPE_CODE));
3684 sbs_compare(sbs);
3685 sbs_free(sbs);
3686 }
3687
3688 // autoconversion: ARRAY -> ARRAY -> BITSET
3689 {
3690 sbs_t* sbs = sbs_create();
3691 for (int i = 0; i < 100; i += 2) {
3692 sbs_add_range(sbs, i, i);
3693 assert_true(sbs_check_type(sbs, ARRAY_CONTAINER_TYPE_CODE));
3694 }
3695 // after number of RLE runs exceeded threshold, it is converted to BITSET
3696 for (int i = 0; i < 65535; i += 2) {
3697 sbs_add_range(sbs, i, i);
3698 }
3699 assert_true(sbs_check_type(sbs, BITSET_CONTAINER_TYPE_CODE));
3700 sbs_compare(sbs);
3701 sbs_free(sbs);
3702 }
3703
3704 // append new container to the end
3705 {
3706 sbs_t* sbs = sbs_create();
3707 sbs_add_value(sbs, 5);
3708 sbs_add_range(sbs, 65536+5, 65536+20);
3709 sbs_compare(sbs);
3710 sbs_free(sbs);
3711 }
3712
3713 // prepend new container to the beginning
3714 {
3715 sbs_t* sbs = sbs_create();
3716 sbs_add_value(sbs, 65536*1+5);
3717 sbs_add_range(sbs, 5, 20);
3718 sbs_compare(sbs);
3719 sbs_free(sbs);
3720 }
3721
3722 // add new container between existing ones
3723 {
3724 sbs_t* sbs = sbs_create();
3725 sbs_add_value(sbs, 65536*0+5);
3726 sbs_add_value(sbs, 65536*2+5);
3727 sbs_add_range(sbs, 65536*1+5, 65536*1+20);
3728 sbs_compare(sbs);
3729 sbs_free(sbs);
3730 }
3731
3732 // invalid range
3733 {
3734 sbs_t* sbs = sbs_create();
3735 sbs_add_range(sbs, 200, 100);
3736 sbs_compare(sbs);
3737 sbs_free(sbs);
3738 }
3739
3740 // random data inside [0..span)
3741 const uint32_t span = 16*65536;
3742 for (uint32_t range_length = 1; range_length < 16384; range_length *= 3) {
3743 sbs_t* sbs = sbs_create();
3744 for (int i = 0; i < 50; i++) {
3745 uint32_t value = our_rand() % span;
3746 sbs_add_value(sbs, value);
3747 }
3748 for (int i = 0; i < 50; i++) {
3749 uint64_t range_start = our_rand() % (span - range_length);
3750 sbs_add_range(sbs, range_start, range_start + range_length - 1);
3751 }
3752 sbs_compare(sbs);
3753 sbs_free(sbs);
3754 }
3755
3756 // max range
3757 {
3758 roaring_bitmap_t *r = roaring_bitmap_create();
3759 roaring_bitmap_add_range(r, 0, UINT32_MAX + UINT64_C(1));
3760 assert_true(roaring_bitmap_get_cardinality(r) == UINT64_C(0x100000000));
3761 roaring_bitmap_free(r);
3762 }
3763
3764 // bug: segfault
3765 {
3766 roaring_bitmap_t *r1 = roaring_bitmap_from_range(0, 1, 1);
3767 roaring_bitmap_set_copy_on_write(r1, true);
3768 roaring_bitmap_t *r2 = roaring_bitmap_copy(r1);
3769 roaring_bitmap_add_range(r1, 0, 1);
3770 assert(roaring_bitmap_get_cardinality(r1) == 1);
3771 assert(roaring_bitmap_get_cardinality(r2) == 1);
3772 roaring_bitmap_free(r2);
3773 roaring_bitmap_free(r1);
3774 }
3775}
3776
3777void test_remove_range() {
3778 // autoconversion: ARRAY -> ARRAY -> NULL
3779 {
3780 sbs_t *sbs = sbs_create();
3781 sbs_add_range(sbs, 100, 200);
3782 sbs_convert(sbs, ARRAY_CONTAINER_TYPE_CODE);
3783 sbs_remove_range(sbs, 100, 105);
3784 sbs_remove_range(sbs, 195, 200);
3785 sbs_remove_range(sbs, 150, 155);
3786 assert_true(sbs_check_type(sbs, ARRAY_CONTAINER_TYPE_CODE));
3787 sbs_compare(sbs);
3788 sbs_remove_range(sbs, 102, 198);
3789 assert_true(sbs_is_empty(sbs));
3790 sbs_free(sbs);
3791 }
3792
3793 // autoconversion: BITSET -> BITSET -> ARRAY
3794 {
3795 sbs_t *sbs = sbs_create();
3796 sbs_add_range(sbs, 0, 40000);
3797 sbs_convert(sbs, BITSET_CONTAINER_TYPE_CODE);
3798 sbs_remove_range(sbs, 100, 200);
3799 assert_true(sbs_check_type(sbs, BITSET_CONTAINER_TYPE_CODE));
3800 sbs_remove_range(sbs, 200, 39900);
3801 assert_true(sbs_check_type(sbs, ARRAY_CONTAINER_TYPE_CODE));
3802 sbs_compare(sbs);
3803 sbs_free(sbs);
3804 }
3805
3806 // autoconversion: BITSET -> NULL
3807 {
3808 sbs_t *sbs = sbs_create();
3809 sbs_add_range(sbs, 100, 200);
3810 sbs_convert(sbs, BITSET_CONTAINER_TYPE_CODE);
3811 sbs_remove_range(sbs, 50, 250);
3812 assert_true(sbs_is_empty(sbs));
3813 sbs_free(sbs);
3814 }
3815
3816 // autoconversion: RUN -> RUN -> BITSET
3817 {
3818 sbs_t *sbs = sbs_create();
3819 sbs_add_range(sbs, 0, 40000);
3820 sbs_add_range(sbs, 50000, 60000);
3821 sbs_convert(sbs, RUN_CONTAINER_TYPE_CODE);
3822 sbs_remove_range(sbs, 100, 200);
3823 sbs_remove_range(sbs, 40000, 50000);
3824 assert_true(sbs_check_type(sbs, RUN_CONTAINER_TYPE_CODE));
3825 for (int i = 0; i < 65535; i++) {
3826 if (i % 2 == 0) {
3827 sbs_remove_range(sbs, i, i);
3828 }
3829 }
3830 assert_true(sbs_check_type(sbs, BITSET_CONTAINER_TYPE_CODE));
3831 sbs_compare(sbs);
3832 sbs_free(sbs);
3833 }
3834
3835 // autoconversion: RUN -> NULL
3836 {
3837 sbs_t *sbs = sbs_create();
3838 sbs_add_range(sbs, 100, 200);
3839 sbs_add_range(sbs, 300, 400);
3840 sbs_convert(sbs, RUN_CONTAINER_TYPE_CODE);
3841 sbs_remove_range(sbs, 50, 450);
3842 assert_true(sbs_is_empty(sbs));
3843 sbs_free(sbs);
3844 }
3845
3846 // remove containers
3847 {
3848 sbs_t *sbs = sbs_create();
3849 sbs_add_value(sbs, 65536*1+100);
3850 sbs_add_value(sbs, 65536*3+100);
3851 sbs_add_value(sbs, 65536*5+100);
3852 sbs_add_value(sbs, 65536*7+100);
3853 sbs_remove_range(sbs, 65536*3+0, 65536*3+65535); // from the middle
3854 sbs_compare(sbs);
3855 sbs_remove_range(sbs, 65536*1+0, 65536*1+65535); // from the beginning
3856 sbs_compare(sbs);
3857 sbs_remove_range(sbs, 65536*7+0, 65536*7+65535); // from the end
3858 sbs_compare(sbs);
3859 sbs_remove_range(sbs, 65536*5+0, 65536*5+65535); // the last one
3860 sbs_compare(sbs);
3861 sbs_remove_range(sbs, 65536*9+0, 65536*9+65535); // non-existent
3862 sbs_compare(sbs);
3863 sbs_free(sbs);
3864 }
3865
3866 // random data inside [0..span)
3867 const uint32_t span = 16*65536;
3868 for (uint32_t range_length = 3; range_length <= 16384; range_length *= 3) {
3869 sbs_t* sbs = sbs_create();
3870 for (int i = 0; i < 50; i++) {
3871 uint64_t range_start = our_rand() % (span - range_length);
3872 sbs_add_range(sbs, range_start, range_start + range_length - 1);
3873 }
3874 for (int i = 0; i < 50; i++) {
3875 uint64_t range_start = our_rand() % (span - range_length);
3876 sbs_remove_range(sbs, range_start, range_start + range_length - 1);
3877 }
3878 sbs_compare(sbs);
3879 sbs_free(sbs);
3880 }
3881}
3882
3883void test_remove_many() {
3884 // multiple values per container (sorted)
3885 {
3886 sbs_t *sbs = sbs_create();
3887 sbs_add_range(sbs, 0, 65536*2-1);
3888 uint32_t values[] = {1, 3, 5, 7, 65536+1, 65536+3, 65536+5, 65536+7};
3889 sbs_remove_many(sbs, sizeof(values)/sizeof(values[0]), values);
3890 sbs_compare(sbs);
3891 sbs_free(sbs);
3892 }
3893
3894 // multiple values per container (interleaved)
3895 {
3896 sbs_t *sbs = sbs_create();
3897 sbs_add_range(sbs, 0, 65536*2-1);
3898 uint32_t values[] = {65536+7, 65536+5, 7, 5, 1, 65536+1, 65536+3, 3};
3899 sbs_remove_many(sbs, sizeof(values)/sizeof(values[0]), values);
3900 sbs_compare(sbs);
3901 sbs_free(sbs);
3902 }
3903
3904 // no-op checks
3905 {
3906 sbs_t *sbs = sbs_create();
3907 sbs_add_value(sbs, 500);
3908 uint32_t values[] = {501, 80000}; // non-existent value/container
3909 sbs_remove_many(sbs, sizeof(values)/sizeof(values[0]), values);
3910 sbs_remove_many(sbs, 0, NULL); // NULL ptr is not dereferenced
3911 sbs_compare(sbs);
3912 sbs_free(sbs);
3913 }
3914
3915 // container type changes and container removal
3916 {
3917 sbs_t *sbs = sbs_create();
3918 sbs_add_range(sbs, 0, 65535);
3919 for (uint32_t v = 0; v <= 65535; v++) {
3920 sbs_remove_many(sbs, 1, &v);
3921 assert(roaring_bitmap_get_cardinality(sbs->roaring) == 65535-v);
3922 }
3923 assert(sbs_is_empty(sbs));
3924 sbs_free(sbs);
3925 }
3926
3927}
3928
3929void test_range_cardinality() {
3930 const uint64_t s = 65536;
3931
3932 roaring_bitmap_t *r = roaring_bitmap_create();
3933 roaring_bitmap_add_range(r, s*2, s*10);
3934
3935 // single container (minhb == maxhb)
3936 assert(roaring_bitmap_range_cardinality(r, s*2, s*3) == s);
3937 assert(roaring_bitmap_range_cardinality(r, s*2+100, s*3) == s-100);
3938 assert(roaring_bitmap_range_cardinality(r, s*2, s*3-200) == s-200);
3939 assert(roaring_bitmap_range_cardinality(r, s*2+100, s*3-200) == s-300);
3940
3941 // multiple containers (maxhb > minhb)
3942 assert(roaring_bitmap_range_cardinality(r, s*2, s*5) == s*3);
3943 assert(roaring_bitmap_range_cardinality(r, s*2+100, s*5) == s*3-100);
3944 assert(roaring_bitmap_range_cardinality(r, s*2, s*5-200) == s*3-200);
3945 assert(roaring_bitmap_range_cardinality(r, s*2+100, s*5-200) == s*3-300);
3946
3947 // boundary checks
3948 assert(roaring_bitmap_range_cardinality(r, s*20, s*21) == 0);
3949 assert(roaring_bitmap_range_cardinality(r, 100, 100) == 0);
3950 assert(roaring_bitmap_range_cardinality(r, 0, s*7) == s*5);
3951 assert(roaring_bitmap_range_cardinality(r, s*7, UINT64_MAX) == s*3);
3952
3953 roaring_bitmap_free(r);
3954}
3955
3956void frozen_serialization_compare(roaring_bitmap_t *r1) {
3957 size_t num_bytes = roaring_bitmap_frozen_size_in_bytes(r1);
3958 char *buf = roaring_bitmap_aligned_malloc(32, num_bytes);
3959 roaring_bitmap_frozen_serialize(r1, buf);
3960
3961 const roaring_bitmap_t *r2 =
3962 roaring_bitmap_frozen_view(buf, num_bytes);
3963
3964 assert(roaring_bitmap_equals(r1, r2));
3965 assert(roaring_bitmap_frozen_view(buf+1, num_bytes-1) == NULL);
3966
3967 roaring_bitmap_free(r1);
3968 roaring_bitmap_free(r2);
3969 roaring_bitmap_aligned_free(buf);
3970}
3971
3972void test_frozen_serialization() {
3973 const uint64_t s = 65536;
3974
3975 roaring_bitmap_t *r = roaring_bitmap_create();
3976 roaring_bitmap_add(r, 0);
3977 roaring_bitmap_add(r, UINT32_MAX);
3978 roaring_bitmap_add(r, 1000);
3979 roaring_bitmap_add(r, 2000);
3980 roaring_bitmap_add(r, 100000);
3981 roaring_bitmap_add(r, 200000);
3982 roaring_bitmap_add_range(r, s*10 + 100, s*13 - 100);
3983 for (uint64_t i = 0; i < s*3; i += 2) {
3984 roaring_bitmap_add(r, s*20 + i);
3985 }
3986 roaring_bitmap_run_optimize(r);
3987 //roaring_bitmap_printf_describe(r);
3988 frozen_serialization_compare(r);
3989}
3990
3991void test_frozen_serialization_max_containers() {
3992 roaring_bitmap_t *r = roaring_bitmap_create();
3993 for (int64_t i = 0; i < 65536; i++) {
3994 roaring_bitmap_add(r, 65536 * i);
3995 }
3996 assert(r->high_low_container.size == 65536);
3997 frozen_serialization_compare(r);
3998}
3999
4000
4001int main() {
4002 const struct CMUnitTest tests[] = {
4003 cmocka_unit_test(issue208),
4004 cmocka_unit_test(issue208b),
4005 cmocka_unit_test(range_contains),
4006 cmocka_unit_test(inplaceorwide),
4007 cmocka_unit_test(test_contains_range),
4008 cmocka_unit_test(check_range_contains_from_end),
4009 cmocka_unit_test(check_iterate_to_end),
4010 cmocka_unit_test(check_iterate_to_beginning),
4011 cmocka_unit_test(test_iterator_reuse),
4012 cmocka_unit_test(check_full_flip),
4013 cmocka_unit_test(test_adversarial_range),
4014 cmocka_unit_test(check_full_inplace_flip),
4015 cmocka_unit_test(test_stress_memory_true),
4016 cmocka_unit_test(test_stress_memory_false),
4017 cmocka_unit_test(check_interval),
4018 cmocka_unit_test(test_uint32_iterator_true),
4019 cmocka_unit_test(test_example_true),
4020 cmocka_unit_test(test_example_false),
4021 cmocka_unit_test(test_clear),
4022 cmocka_unit_test(can_copy_empty_true),
4023 cmocka_unit_test(can_copy_empty_false),
4024 cmocka_unit_test(test_intersect_small_run_bitset),
4025 cmocka_unit_test(is_really_empty),
4026 cmocka_unit_test(test_rank),
4027 cmocka_unit_test(test_maximum_minimum),
4028 cmocka_unit_test(test_stats),
4029 cmocka_unit_test(test_addremove),
4030 cmocka_unit_test(test_addremoverun),
4031 cmocka_unit_test(test_basic_add),
4032 cmocka_unit_test(test_remove_withrun),
4033 cmocka_unit_test(test_remove_from_copies_true),
4034 cmocka_unit_test(test_remove_from_copies_false),
4035 cmocka_unit_test(test_range_and_serialize),
4036 cmocka_unit_test(test_silly_range),
4037 cmocka_unit_test(test_uint32_iterator_true),
4038 cmocka_unit_test(test_uint32_iterator_false),
4039 cmocka_unit_test(leaks_with_empty_true),
4040 cmocka_unit_test(leaks_with_empty_false),
4041 cmocka_unit_test(test_bitmap_from_range),
4042 cmocka_unit_test(test_printf),
4043 cmocka_unit_test(test_printf_withbitmap),
4044 cmocka_unit_test(test_printf_withrun),
4045 cmocka_unit_test(test_iterate),
4046 cmocka_unit_test(test_iterate_empty),
4047 cmocka_unit_test(test_iterate_withbitmap),
4048 cmocka_unit_test(test_iterate_withrun),
4049 cmocka_unit_test(test_serialize),
4050 cmocka_unit_test(test_portable_serialize),
4051 cmocka_unit_test(test_add),
4052 cmocka_unit_test(test_add_checked),
4053 cmocka_unit_test(test_remove_checked),
4054 cmocka_unit_test(test_contains),
4055 cmocka_unit_test(test_intersection_array_x_array),
4056 cmocka_unit_test(test_intersection_array_x_array_inplace),
4057 cmocka_unit_test(test_intersection_bitset_x_bitset),
4058 cmocka_unit_test(test_intersection_bitset_x_bitset_inplace),
4059 cmocka_unit_test(test_union_true),
4060 cmocka_unit_test(test_union_false),
4061 cmocka_unit_test(test_xor_false),
4062 cmocka_unit_test(test_xor_inplace_false),
4063 cmocka_unit_test(test_xor_lazy_false),
4064 cmocka_unit_test(test_xor_lazy_inplace_false),
4065 cmocka_unit_test(test_xor_true),
4066 cmocka_unit_test(test_xor_inplace_true),
4067 cmocka_unit_test(test_xor_lazy_true),
4068 cmocka_unit_test(test_xor_lazy_inplace_true),
4069 cmocka_unit_test(test_andnot_false),
4070 cmocka_unit_test(test_andnot_inplace_false),
4071 cmocka_unit_test(test_andnot_true),
4072 cmocka_unit_test(test_andnot_inplace_true),
4073 cmocka_unit_test(test_conversion_to_int_array),
4074 cmocka_unit_test(test_array_to_run),
4075 cmocka_unit_test(test_array_to_self),
4076 cmocka_unit_test(test_bitset_to_self),
4077 cmocka_unit_test(test_conversion_to_int_array_with_runoptimize),
4078 cmocka_unit_test(test_run_to_self),
4079 cmocka_unit_test(test_remove_run_to_bitset),
4080 cmocka_unit_test(test_remove_run_to_array),
4081 cmocka_unit_test(test_negation_array0),
4082 cmocka_unit_test(test_negation_array1),
4083 cmocka_unit_test(test_negation_array2),
4084 cmocka_unit_test(test_negation_bitset1),
4085 cmocka_unit_test(test_negation_bitset2),
4086 cmocka_unit_test(test_negation_run1),
4087 cmocka_unit_test(test_negation_run2),
4088 cmocka_unit_test(test_rand_flips),
4089 cmocka_unit_test(test_inplace_negation_array0),
4090 cmocka_unit_test(test_inplace_negation_array1),
4091 cmocka_unit_test(test_inplace_negation_array2),
4092 cmocka_unit_test(test_inplace_negation_bitset1),
4093 cmocka_unit_test(test_inplace_negation_bitset2),
4094 cmocka_unit_test(test_inplace_negation_run1),
4095 cmocka_unit_test(test_inplace_negation_run2),
4096 cmocka_unit_test(test_inplace_rand_flips),
4097 cmocka_unit_test(test_flip_array_container_removal),
4098 cmocka_unit_test(test_flip_bitset_container_removal),
4099 cmocka_unit_test(test_flip_run_container_removal),
4100 cmocka_unit_test(test_flip_run_container_removal2),
4101 cmocka_unit_test(select_test),
4102 cmocka_unit_test(test_subset),
4103 cmocka_unit_test(test_or_many_memory_leak),
4104 // cmocka_unit_test(test_run_to_bitset),
4105 // cmocka_unit_test(test_run_to_array),
4106 cmocka_unit_test(test_read_uint32_iterator_array),
4107 cmocka_unit_test(test_read_uint32_iterator_bitset),
4108 cmocka_unit_test(test_read_uint32_iterator_run),
4109 cmocka_unit_test(test_read_uint32_iterator_native),
4110 cmocka_unit_test(test_previous_iterator_array),
4111 cmocka_unit_test(test_previous_iterator_bitset),
4112 cmocka_unit_test(test_previous_iterator_run),
4113 cmocka_unit_test(test_previous_iterator_native),
4114 cmocka_unit_test(test_iterator_reuse),
4115 cmocka_unit_test(test_iterator_reuse_many),
4116 cmocka_unit_test(test_add_range),
4117 cmocka_unit_test(test_remove_range),
4118 cmocka_unit_test(test_remove_many),
4119 cmocka_unit_test(test_range_cardinality),
4120 cmocka_unit_test(test_frozen_serialization),
4121 cmocka_unit_test(test_frozen_serialization_max_containers),
4122 };
4123
4124 return cmocka_run_group_tests(tests, NULL, NULL);
4125}
4126