1/*
2 * realdata_unit.c
3 */
4#define _GNU_SOURCE
5#include <roaring/roaring.h>
6#include <roaring/roaring_types.h>
7
8#include "../benchmarks/numbersfromtextfiles.h"
9#include "config.h"
10
11/**
12 * Once you have collected all the integers, build the bitmaps.
13 */
14static roaring_bitmap_t **create_all_bitmaps(size_t *howmany,
15 uint32_t **numbers, size_t count,
16 bool copy_on_write) {
17 if (numbers == NULL) return NULL;
18 printf("Constructing %d bitmaps.\n", (int)count);
19 roaring_bitmap_t **answer = malloc(sizeof(roaring_bitmap_t *) * count);
20 for (size_t i = 0; i < count; i++) {
21 printf(".");
22 fflush(stdout);
23 answer[i] = roaring_bitmap_of_ptr(howmany[i], numbers[i]);
24 roaring_bitmap_set_copy_on_write(answer[i], copy_on_write);
25 }
26 printf("\n");
27 return answer;
28}
29
30const char *datadir[] = {
31 "census-income", "census-income_srt", "census1881",
32 "census1881_srt", "uscensus2000", "weather_sept_85",
33 "weather_sept_85_srt", "wikileaks-noquotes", "wikileaks-noquotes_srt"};
34
35bool serialize_correctly(roaring_bitmap_t *r) {
36 uint32_t expectedsize = roaring_bitmap_portable_size_in_bytes(r);
37 char *serialized = malloc(expectedsize);
38 if (serialized == NULL) {
39 printf("failure to allocate memory!\n");
40 return false;
41 }
42 uint32_t serialize_len = roaring_bitmap_portable_serialize(r, serialized);
43 if (serialize_len != expectedsize) {
44 printf("Bad serialized size!\n");
45 free(serialized);
46 return false;
47 }
48 roaring_bitmap_t *r2 = roaring_bitmap_portable_deserialize(serialized);
49 free(serialized);
50 if (!roaring_bitmap_equals(r, r2)) {
51 printf("Won't recover original bitmap!\n");
52 roaring_bitmap_free(r2);
53 return false;
54 }
55 if (!roaring_bitmap_equals(r2, r)) {
56 printf("Won't recover original bitmap!\n");
57 roaring_bitmap_free(r2);
58 return false;
59 }
60 roaring_bitmap_free(r2);
61 return true;
62}
63
64// arrays expected to both be sorted.
65bool array_equals(uint32_t *a1, int32_t size1, uint32_t *a2, int32_t size2) {
66 if (size1 != size2) {
67 printf("they differ since sizes differ %d %d\n", size1, size2);
68 return false;
69 }
70 for (int i = 0; i < size1; ++i)
71 if (a1[i] != a2[i]) {
72 printf("same sizes %d %d but they differ at %d \n", size1, size2,
73 i);
74 return false;
75 }
76 return true;
77}
78
79bool is_union_correct(roaring_bitmap_t *bitmap1, roaring_bitmap_t *bitmap2) {
80 roaring_bitmap_t *temp = roaring_bitmap_or(bitmap1, bitmap2);
81 if (roaring_bitmap_get_cardinality(temp) !=
82 roaring_bitmap_or_cardinality(bitmap1, bitmap2)) {
83 printf("bad union cardinality\n");
84 return false;
85 }
86 uint64_t card1, card2, card;
87 card1 = roaring_bitmap_get_cardinality(bitmap1);
88 card2 = roaring_bitmap_get_cardinality(bitmap2);
89 card = roaring_bitmap_get_cardinality(temp);
90 uint32_t *arr1 = (uint32_t *)malloc(card1 * sizeof(uint32_t));
91 uint32_t *arr2 = (uint32_t *)malloc(card2 * sizeof(uint32_t));
92 uint32_t *arr = (uint32_t *)malloc(card * sizeof(uint32_t));
93
94 if ((arr1 == NULL) || (arr2 == NULL) || (arr == NULL)) {
95 free(arr1);
96 free(arr2);
97 free(arr);
98 return false;
99 }
100
101 roaring_bitmap_to_uint32_array(bitmap1, arr1);
102 roaring_bitmap_to_uint32_array(bitmap2, arr2);
103 roaring_bitmap_to_uint32_array(temp, arr);
104
105 uint32_t *buffer = (uint32_t *)malloc(sizeof(uint32_t) * (card1 + card2));
106 size_t cardtrue = union_uint32(arr1, card1, arr2, card2, buffer);
107 bool answer = array_equals(arr, card, buffer, cardtrue);
108 if (!answer) {
109 printf("\n\nbitmap1:\n");
110 roaring_bitmap_printf_describe(bitmap1); // debug
111 printf("\n\nbitmap2:\n");
112 roaring_bitmap_printf_describe(bitmap2); // debug
113 printf("\n\nresult:\n");
114 roaring_bitmap_printf_describe(temp); // debug
115 roaring_bitmap_t *ca = roaring_bitmap_of_ptr(cardtrue, buffer);
116 printf("\n\ncorrect result:\n");
117 roaring_bitmap_printf_describe(ca); // debug
118 free(ca);
119 }
120 free(buffer);
121 free(arr1);
122 free(arr2);
123 free(arr);
124 roaring_bitmap_free(temp);
125 return answer;
126}
127
128// function copy-pasted from toplevel_unit.c
129static roaring_bitmap_t *synthesized_xor(roaring_bitmap_t *r1,
130 roaring_bitmap_t *r2) {
131 unsigned universe_size = 0;
132 roaring_statistics_t stats;
133 roaring_bitmap_statistics(r1, &stats);
134 universe_size = stats.max_value;
135 roaring_bitmap_statistics(r2, &stats);
136 if (stats.max_value > universe_size) universe_size = stats.max_value;
137
138 roaring_bitmap_t *r1_or_r2 = roaring_bitmap_or(r1, r2);
139 roaring_bitmap_t *r1_and_r2 = roaring_bitmap_and(r1, r2);
140 roaring_bitmap_t *r1_nand_r2 =
141 roaring_bitmap_flip(r1_and_r2, 0U, universe_size + 1U);
142 roaring_bitmap_t *r1_xor_r2 = roaring_bitmap_and(r1_or_r2, r1_nand_r2);
143 roaring_bitmap_free(r1_or_r2);
144 roaring_bitmap_free(r1_and_r2);
145 roaring_bitmap_free(r1_nand_r2);
146 return r1_xor_r2;
147}
148
149static roaring_bitmap_t *synthesized_andnot(roaring_bitmap_t *r1,
150 roaring_bitmap_t *r2) {
151 unsigned universe_size = 0;
152 roaring_statistics_t stats;
153 roaring_bitmap_statistics(r1, &stats);
154 universe_size = stats.max_value;
155 roaring_bitmap_statistics(r2, &stats);
156 if (stats.max_value > universe_size) universe_size = stats.max_value;
157
158 roaring_bitmap_t *not_r2 = roaring_bitmap_flip(r2, 0U, universe_size + 1U);
159 roaring_bitmap_t *r1_andnot_r2 = roaring_bitmap_and(r1, not_r2);
160 roaring_bitmap_free(not_r2);
161 return r1_andnot_r2;
162}
163
164bool is_xor_correct(roaring_bitmap_t *bitmap1, roaring_bitmap_t *bitmap2) {
165 roaring_bitmap_t *temp = roaring_bitmap_xor(bitmap1, bitmap2);
166 if (roaring_bitmap_get_cardinality(temp) !=
167 roaring_bitmap_xor_cardinality(bitmap1, bitmap2)) {
168 printf("bad symmetric difference cardinality\n");
169 return false;
170 }
171
172 roaring_bitmap_t *expected = synthesized_xor(bitmap1, bitmap2);
173 bool answer = roaring_bitmap_equals(temp, expected);
174 if (!answer) {
175 printf("Bad XOR\n\nbitmap1:\n");
176 roaring_bitmap_printf_describe(bitmap1); // debug
177 printf("\n\nbitmap2:\n");
178 roaring_bitmap_printf_describe(bitmap2); // debug
179 printf("\n\nresult:\n");
180 roaring_bitmap_printf_describe(temp); // debug
181 printf("\n\ncorrect result:\n");
182 roaring_bitmap_printf_describe(expected); // debug
183 }
184 roaring_bitmap_free(temp);
185 roaring_bitmap_free(expected);
186 return answer;
187}
188
189bool is_andnot_correct(roaring_bitmap_t *bitmap1, roaring_bitmap_t *bitmap2) {
190 roaring_bitmap_t *temp = roaring_bitmap_andnot(bitmap1, bitmap2);
191 if (roaring_bitmap_get_cardinality(temp) !=
192 roaring_bitmap_andnot_cardinality(bitmap1, bitmap2)) {
193 printf("bad difference cardinality\n");
194 return false;
195 }
196
197 roaring_bitmap_t *expected = synthesized_andnot(bitmap1, bitmap2);
198 bool answer = roaring_bitmap_equals(temp, expected);
199 if (!answer) {
200 printf("Bad ANDNOT\n\nbitmap1:\n");
201 roaring_bitmap_printf_describe(bitmap1); // debug
202 // print_container(3, bitmap1);
203 printf("\n\nbitmap2:\n");
204 roaring_bitmap_printf_describe(bitmap2); // debug
205 printf("\n\nresult:\n");
206 roaring_bitmap_printf_describe(temp); // debug
207 printf("\n\ncorrect result:\n");
208 roaring_bitmap_printf_describe(expected); // debug
209 printf("difference is ");
210 roaring_bitmap_printf(roaring_bitmap_xor(temp, expected));
211 }
212 roaring_bitmap_free(temp);
213 roaring_bitmap_free(expected);
214 return answer;
215}
216
217bool is_negation_correct(roaring_bitmap_t *bitmap) {
218 roaring_statistics_t stats;
219 bool answer = true;
220 roaring_bitmap_statistics(bitmap, &stats);
221 unsigned universe_size = stats.max_value + 1;
222 roaring_bitmap_t *inverted = roaring_bitmap_flip(bitmap, 0U, universe_size);
223
224 roaring_bitmap_t *double_inverted =
225 roaring_bitmap_flip(inverted, 0U, universe_size);
226
227 answer = (roaring_bitmap_get_cardinality(inverted) +
228 roaring_bitmap_get_cardinality(bitmap) ==
229 universe_size);
230 if (answer) answer = roaring_bitmap_equals(bitmap, double_inverted);
231
232 if (!answer) {
233 printf("Bad flip\n\nbitmap1:\n");
234 roaring_bitmap_printf_describe(bitmap); // debug
235 printf("\n\nflipped:\n");
236 roaring_bitmap_printf_describe(inverted); // debug
237 }
238
239 roaring_bitmap_free(double_inverted);
240 roaring_bitmap_free(inverted);
241 return answer;
242}
243
244bool is_intersection_correct(roaring_bitmap_t *bitmap1,
245 roaring_bitmap_t *bitmap2) {
246 roaring_bitmap_t *temp = roaring_bitmap_and(bitmap1, bitmap2);
247 if (roaring_bitmap_get_cardinality(temp) !=
248 roaring_bitmap_and_cardinality(bitmap1, bitmap2)) {
249 printf("bad intersection cardinality\n");
250 return false;
251 }
252
253 uint64_t card1, card2, card;
254 card1 = roaring_bitmap_get_cardinality(bitmap1);
255 card2 = roaring_bitmap_get_cardinality(bitmap2);
256 card = roaring_bitmap_get_cardinality(temp);
257 uint32_t *arr1 = (uint32_t *)malloc(card1 * sizeof(uint32_t));
258 uint32_t *arr2 = (uint32_t *)malloc(card2 * sizeof(uint32_t));
259 uint32_t *arr = (uint32_t *)malloc(card * sizeof(uint32_t));
260
261 if ((arr1 == NULL) || (arr2 == NULL) || (arr == NULL)) {
262 free(arr1);
263 free(arr2);
264 free(arr);
265 return false;
266 }
267
268 roaring_bitmap_to_uint32_array(bitmap1, arr1);
269 roaring_bitmap_to_uint32_array(bitmap2, arr2);
270 roaring_bitmap_to_uint32_array(temp, arr);
271
272 uint32_t *buffer = (uint32_t *)malloc(sizeof(uint32_t) * (card1 + card2));
273 size_t cardtrue = intersection_uint32(arr1, card1, arr2, card2, buffer);
274 bool answer = array_equals(arr, card, buffer, cardtrue);
275 if (!answer) {
276 printf("\n\nbitmap1:\n");
277 roaring_bitmap_printf_describe(bitmap1); // debug
278 printf("\n\nbitmap2:\n");
279 roaring_bitmap_printf_describe(bitmap2); // debug
280 printf("\n\nresult:\n");
281 roaring_bitmap_printf_describe(temp); // debug
282 roaring_bitmap_t *ca = roaring_bitmap_of_ptr(cardtrue, buffer);
283 printf("\n\ncorrect result:\n");
284 roaring_bitmap_printf_describe(ca); // debug
285 free(ca);
286 }
287 free(buffer);
288 free(arr1);
289 free(arr2);
290 free(arr);
291 roaring_bitmap_free(temp);
292 return answer;
293}
294
295
296bool is_intersect_correct(roaring_bitmap_t *bitmap1,
297 roaring_bitmap_t *bitmap2) {
298 uint64_t c = roaring_bitmap_and_cardinality(bitmap1, bitmap2);
299 if(roaring_bitmap_intersect(bitmap1,bitmap2) != (c>0)) return false;
300 roaring_bitmap_t * bitmap1minus2 = roaring_bitmap_andnot(bitmap1, bitmap2);
301 bool answer = true;
302 if(roaring_bitmap_intersect(bitmap1minus2,bitmap2)) {
303 answer = false;
304 }
305 roaring_bitmap_t * bitmap1plus2 = roaring_bitmap_or(bitmap1, bitmap2);
306 if(!roaring_bitmap_intersect(bitmap1plus2,bitmap2)) {
307 answer = false;
308 }
309 roaring_bitmap_free(bitmap1minus2);
310 roaring_bitmap_free(bitmap1plus2);
311 return answer;
312}
313
314
315roaring_bitmap_t *inplace_union(roaring_bitmap_t *bitmap1,
316 roaring_bitmap_t *bitmap2) {
317 roaring_bitmap_t *answer = roaring_bitmap_copy(bitmap1);
318 roaring_bitmap_or_inplace(answer, bitmap2);
319 return answer;
320}
321
322roaring_bitmap_t *inplace_intersection(roaring_bitmap_t *bitmap1,
323 roaring_bitmap_t *bitmap2) {
324 roaring_bitmap_t *answer = roaring_bitmap_copy(bitmap1);
325 roaring_bitmap_and_inplace(answer, bitmap2);
326 return answer;
327}
328
329roaring_bitmap_t *inplace_xor(roaring_bitmap_t *bitmap1,
330 roaring_bitmap_t *bitmap2) {
331 roaring_bitmap_t *answer = roaring_bitmap_copy(bitmap1);
332 roaring_bitmap_xor_inplace(answer, bitmap2);
333 return answer;
334}
335
336roaring_bitmap_t *inplace_andnot(roaring_bitmap_t *bitmap1,
337 roaring_bitmap_t *bitmap2) {
338 roaring_bitmap_t *answer = roaring_bitmap_copy(bitmap1);
339 roaring_bitmap_andnot_inplace(answer, bitmap2);
340 return answer;
341}
342
343bool slow_bitmap_equals(roaring_bitmap_t *bitmap1, roaring_bitmap_t *bitmap2) {
344 uint64_t card1, card2;
345 card1 = roaring_bitmap_get_cardinality(bitmap1);
346 card2 = roaring_bitmap_get_cardinality(bitmap2);
347 uint32_t *arr1 = (uint32_t *)malloc(card1 * sizeof(uint32_t));
348 uint32_t *arr2 = (uint32_t *)malloc(card2 * sizeof(uint32_t));
349 roaring_bitmap_to_uint32_array(bitmap1, arr1);
350 roaring_bitmap_to_uint32_array(bitmap2, arr2);
351 bool answer = array_equals(arr1, card1, arr2, card2);
352 free(arr1);
353 free(arr2);
354 return answer;
355}
356
357bool compare_intersections(roaring_bitmap_t **rnorun, roaring_bitmap_t **rruns,
358 size_t count) {
359 roaring_bitmap_t *tempandnorun;
360 roaring_bitmap_t *tempandruns;
361 for (size_t i = 0; i + 1 < count; ++i) {
362 tempandnorun = roaring_bitmap_and(rnorun[i], rnorun[i + 1]);
363 if (!is_intersection_correct(rnorun[i], rnorun[i + 1])) {
364 printf("no run intersection incorrect\n");
365 return false;
366 }
367 if (!is_intersect_correct(rnorun[i], rnorun[i + 1])) {
368 printf("no run intersect incorrect\n");
369 return false;
370 }
371 tempandruns = roaring_bitmap_and(rruns[i], rruns[i + 1]);
372 if (!is_intersection_correct(rruns[i], rruns[i + 1])) {
373 printf("runs intersection incorrect\n");
374 return false;
375 }
376 if (!is_intersect_correct(rruns[i], rruns[i + 1])) {
377 printf("runs intersect incorrect\n");
378 return false;
379 }
380 if (!slow_bitmap_equals(tempandnorun, tempandruns)) {
381 printf("Intersections don't agree! (slow) \n");
382 return false;
383 }
384
385 if (!roaring_bitmap_equals(tempandnorun, tempandruns)) {
386 printf("Intersections don't agree!\n");
387 printf("\n\nbitmap1:\n");
388 roaring_bitmap_printf_describe(tempandnorun); // debug
389 printf("\n\nbitmap2:\n");
390 roaring_bitmap_printf_describe(tempandruns); // debug
391 return false;
392 }
393 roaring_bitmap_free(tempandnorun);
394 roaring_bitmap_free(tempandruns);
395
396 tempandnorun = inplace_intersection(rnorun[i], rnorun[i + 1]);
397 if (!is_intersection_correct(rnorun[i], rnorun[i + 1])) {
398 printf("[inplace] no run intersection incorrect\n");
399 return false;
400 }
401 if (!is_intersect_correct(rnorun[i], rnorun[i + 1])) {
402 printf("[inplace] no run intersect incorrect\n");
403 return false;
404 }
405 tempandruns = inplace_intersection(rruns[i], rruns[i + 1]);
406 if (!is_intersection_correct(rruns[i], rruns[i + 1])) {
407 printf("[inplace] runs intersection incorrect\n");
408 return false;
409 }
410 if (!is_intersect_correct(rruns[i], rruns[i + 1])) {
411 printf("[inplace] runs intersect incorrect\n");
412 return false;
413 }
414 if (!slow_bitmap_equals(tempandnorun, tempandruns)) {
415 printf("[inplace] Intersections don't agree! (slow) \n");
416 return false;
417 }
418
419 if (!roaring_bitmap_equals(tempandnorun, tempandruns)) {
420 printf("[inplace] Intersections don't agree!\n");
421 printf("\n\nbitmap1:\n");
422 roaring_bitmap_printf_describe(tempandnorun); // debug
423 printf("\n\nbitmap2:\n");
424 roaring_bitmap_printf_describe(tempandruns); // debug
425 return false;
426 }
427 roaring_bitmap_free(tempandnorun);
428 roaring_bitmap_free(tempandruns);
429 }
430 return true;
431}
432
433bool compare_unions(roaring_bitmap_t **rnorun, roaring_bitmap_t **rruns,
434 size_t count) {
435 roaring_bitmap_t *tempornorun;
436 roaring_bitmap_t *temporruns;
437 for (size_t i = 0; i + 1 < count; ++i) {
438 tempornorun = roaring_bitmap_or(rnorun[i], rnorun[i + 1]);
439 if (!is_union_correct(rnorun[i], rnorun[i + 1])) {
440 printf("no-run union incorrect\n");
441 return false;
442 }
443 temporruns = roaring_bitmap_or(rruns[i], rruns[i + 1]);
444 if (!is_union_correct(rruns[i], rruns[i + 1])) {
445 printf("runs unions incorrect\n");
446 return false;
447 }
448 if (!slow_bitmap_equals(tempornorun, temporruns)) {
449 printf("Unions don't agree! (slow) \n");
450 return false;
451 }
452
453 if (!roaring_bitmap_equals(tempornorun, temporruns)) {
454 printf("Unions don't agree!\n");
455 printf("\n\nbitmap1:\n");
456 roaring_bitmap_printf_describe(tempornorun); // debug
457 printf("\n\nbitmap2:\n");
458 roaring_bitmap_printf_describe(temporruns); // debug
459 return false;
460 }
461 roaring_bitmap_free(tempornorun);
462 roaring_bitmap_free(temporruns);
463 tempornorun = inplace_union(rnorun[i], rnorun[i + 1]);
464 if (!is_union_correct(rnorun[i], rnorun[i + 1])) {
465 printf("[inplace] no-run union incorrect\n");
466 return false;
467 }
468 temporruns = inplace_union(rruns[i], rruns[i + 1]);
469 if (!is_union_correct(rruns[i], rruns[i + 1])) {
470 printf("[inplace] runs unions incorrect\n");
471 return false;
472 }
473
474 if (!slow_bitmap_equals(tempornorun, temporruns)) {
475 printf("[inplace] Unions don't agree! (slow) \n");
476 return false;
477 }
478
479 if (!roaring_bitmap_equals(tempornorun, temporruns)) {
480 printf("[inplace] Unions don't agree!\n");
481 printf("\n\nbitmap1:\n");
482 roaring_bitmap_printf_describe(tempornorun); // debug
483 printf("\n\nbitmap2:\n");
484 roaring_bitmap_printf_describe(temporruns); // debug
485 return false;
486 }
487 roaring_bitmap_free(tempornorun);
488 roaring_bitmap_free(temporruns);
489 }
490 return true;
491}
492
493bool compare_xors(roaring_bitmap_t **rnorun, roaring_bitmap_t **rruns,
494 size_t count) {
495 roaring_bitmap_t *tempornorun;
496 roaring_bitmap_t *temporruns;
497 for (size_t i = 0; i + 1 < count; ++i) {
498 tempornorun = roaring_bitmap_xor(rnorun[i], rnorun[i + 1]);
499 if (!is_xor_correct(rnorun[i], rnorun[i + 1])) {
500 printf("no-run xor incorrect\n");
501 return false;
502 }
503 temporruns = roaring_bitmap_xor(rruns[i], rruns[i + 1]);
504 if (!is_xor_correct(rruns[i], rruns[i + 1])) {
505 printf("runs xors incorrect\n");
506 return false;
507 }
508 if (!slow_bitmap_equals(tempornorun, temporruns)) {
509 printf("Xors don't agree! (slow) \n");
510 return false;
511 }
512
513 if (!roaring_bitmap_equals(tempornorun, temporruns)) {
514 printf("Xors don't agree!\n");
515 printf("\n\nbitmap1:\n");
516 roaring_bitmap_printf_describe(tempornorun); // debug
517 printf("\n\nbitmap2:\n");
518 roaring_bitmap_printf_describe(temporruns); // debug
519 return false;
520 }
521 roaring_bitmap_free(tempornorun);
522 roaring_bitmap_free(temporruns);
523 tempornorun = inplace_xor(rnorun[i], rnorun[i + 1]);
524 if (!is_xor_correct(rnorun[i], rnorun[i + 1])) {
525 printf("[inplace] no-run xor incorrect\n");
526 return false;
527 }
528 temporruns = inplace_xor(rruns[i], rruns[i + 1]);
529 if (!is_xor_correct(rruns[i], rruns[i + 1])) {
530 printf("[inplace] runs xors incorrect\n");
531 return false;
532 }
533
534 if (!slow_bitmap_equals(tempornorun, temporruns)) {
535 printf("[inplace] Xors don't agree! (slow) \n");
536 return false;
537 }
538
539 if (!roaring_bitmap_equals(tempornorun, temporruns)) {
540 printf("[inplace] Xors don't agree!\n");
541 printf("\n\nbitmap1:\n");
542 roaring_bitmap_printf_describe(tempornorun); // debug
543 printf("\n\nbitmap2:\n");
544 roaring_bitmap_printf_describe(temporruns); // debug
545 return false;
546 }
547 roaring_bitmap_free(tempornorun);
548 roaring_bitmap_free(temporruns);
549 }
550 return true;
551}
552
553bool compare_andnots(roaring_bitmap_t **rnorun, roaring_bitmap_t **rruns,
554 size_t count) {
555 roaring_bitmap_t *tempornorun;
556 roaring_bitmap_t *temporruns;
557 for (size_t i = 0; i + 1 < count; ++i) {
558 tempornorun = roaring_bitmap_andnot(rnorun[i], rnorun[i + 1]);
559 if (!is_andnot_correct(rnorun[i], rnorun[i + 1])) {
560 printf("no-run andnot incorrect\n");
561 return false;
562 }
563 temporruns = roaring_bitmap_andnot(rruns[i], rruns[i + 1]);
564 if (!is_andnot_correct(rruns[i], rruns[i + 1])) {
565 printf("runs andnots incorrect\n");
566 return false;
567 }
568 if (!slow_bitmap_equals(tempornorun, temporruns)) {
569 printf("Andnots don't agree! (slow) \n");
570 return false;
571 }
572
573 if (!roaring_bitmap_equals(tempornorun, temporruns)) {
574 printf("Andnots don't agree!\n");
575 printf("\n\nbitmap1:\n");
576 roaring_bitmap_printf_describe(tempornorun); // debug
577 printf("\n\nbitmap2:\n");
578 roaring_bitmap_printf_describe(temporruns); // debug
579 return false;
580 }
581 roaring_bitmap_free(tempornorun);
582 roaring_bitmap_free(temporruns);
583 tempornorun = inplace_andnot(rnorun[i], rnorun[i + 1]);
584 if (!is_andnot_correct(rnorun[i], rnorun[i + 1])) {
585 printf("[inplace] no-run andnot incorrect\n");
586 return false;
587 }
588 temporruns = inplace_andnot(rruns[i], rruns[i + 1]);
589 if (!is_andnot_correct(rruns[i], rruns[i + 1])) {
590 printf("[inplace] runs andnots incorrect\n");
591 return false;
592 }
593
594 if (!slow_bitmap_equals(tempornorun, temporruns)) {
595 printf("[inplace] Andnots don't agree! (slow) \n");
596 return false;
597 }
598
599 if (!roaring_bitmap_equals(tempornorun, temporruns)) {
600 printf("[inplace] Andnots don't agree!\n");
601 printf("\n\nbitmap1:\n");
602 roaring_bitmap_printf_describe(tempornorun); // debug
603 printf("\n\nbitmap2:\n");
604 roaring_bitmap_printf_describe(temporruns); // debug
605 return false;
606 }
607 roaring_bitmap_free(tempornorun);
608 roaring_bitmap_free(temporruns);
609 }
610 return true;
611}
612
613bool compare_negations(roaring_bitmap_t **rnorun, roaring_bitmap_t **rruns,
614 size_t count) {
615 for (size_t i = 0; i < count; ++i) {
616 if (!is_negation_correct(rnorun[i])) {
617 printf("no-run negation incorrect\n");
618 return false;
619 }
620 if (!is_negation_correct(rruns[i])) {
621 printf("runs negations incorrect\n");
622 return false;
623 }
624 }
625 return true;
626}
627
628bool compare_wide_unions(roaring_bitmap_t **rnorun, roaring_bitmap_t **rruns,
629 size_t count) {
630 roaring_bitmap_t *tempornorun =
631 roaring_bitmap_or_many(count, (const roaring_bitmap_t **)rnorun);
632 roaring_bitmap_t *temporruns =
633 roaring_bitmap_or_many(count, (const roaring_bitmap_t **)rruns);
634 if (!slow_bitmap_equals(tempornorun, temporruns)) {
635 printf("[compare_wide_unions] Unions don't agree! (fast run-norun) \n");
636 return false;
637 }
638 assert(roaring_bitmap_equals(tempornorun, temporruns));
639
640 roaring_bitmap_t *tempornorunheap =
641 roaring_bitmap_or_many_heap(count, (const roaring_bitmap_t **)rnorun);
642 roaring_bitmap_t *temporrunsheap =
643 roaring_bitmap_or_many_heap(count, (const roaring_bitmap_t **)rruns);
644 // assert(slow_bitmap_equals(tempornorun, tempornorunheap));
645 // assert(slow_bitmap_equals(temporruns,temporrunsheap));
646
647 assert(roaring_bitmap_equals(tempornorun, tempornorunheap));
648 assert(roaring_bitmap_equals(temporruns, temporrunsheap));
649 roaring_bitmap_free(tempornorunheap);
650 roaring_bitmap_free(temporrunsheap);
651
652 roaring_bitmap_t *longtempornorun;
653 roaring_bitmap_t *longtemporruns;
654 if (count == 1) {
655 longtempornorun = rnorun[0];
656 longtemporruns = rruns[0];
657 } else {
658 assert(roaring_bitmap_equals(rnorun[0], rruns[0]));
659 assert(roaring_bitmap_equals(rnorun[1], rruns[1]));
660 longtempornorun = roaring_bitmap_or(rnorun[0], rnorun[1]);
661 longtemporruns = roaring_bitmap_or(rruns[0], rruns[1]);
662 assert(roaring_bitmap_equals(longtempornorun, longtemporruns));
663 for (int i = 2; i < (int)count; ++i) {
664 assert(roaring_bitmap_equals(rnorun[i], rruns[i]));
665 assert(roaring_bitmap_equals(longtempornorun, longtemporruns));
666
667 roaring_bitmap_t *t1 =
668 roaring_bitmap_or(rnorun[i], longtempornorun);
669 roaring_bitmap_t *t2 = roaring_bitmap_or(rruns[i], longtemporruns);
670 assert(roaring_bitmap_equals(t1, t2));
671 roaring_bitmap_free(longtempornorun);
672 longtempornorun = t1;
673 roaring_bitmap_free(longtemporruns);
674 longtemporruns = t2;
675 assert(roaring_bitmap_equals(longtempornorun, longtemporruns));
676 }
677 }
678 if (!slow_bitmap_equals(longtempornorun, tempornorun)) {
679 printf("[compare_wide_unions] Unions don't agree! (regular) \n");
680 return false;
681 }
682 if (!slow_bitmap_equals(temporruns, longtemporruns)) {
683 printf("[compare_wide_unions] Unions don't agree! (runs) \n");
684 return false;
685 }
686 roaring_bitmap_free(tempornorun);
687 roaring_bitmap_free(temporruns);
688
689 roaring_bitmap_free(longtempornorun);
690 roaring_bitmap_free(longtemporruns);
691
692 return true;
693}
694
695bool compare_wide_xors(roaring_bitmap_t **rnorun, roaring_bitmap_t **rruns,
696 size_t count) {
697 roaring_bitmap_t *tempornorun =
698 roaring_bitmap_xor_many(count, (const roaring_bitmap_t **)rnorun);
699 roaring_bitmap_t *temporruns =
700 roaring_bitmap_xor_many(count, (const roaring_bitmap_t **)rruns);
701 if (!slow_bitmap_equals(tempornorun, temporruns)) {
702 printf("[compare_wide_xors] Xors don't agree! (fast run-norun) \n");
703 return false;
704 }
705 assert(roaring_bitmap_equals(tempornorun, temporruns));
706
707 roaring_bitmap_t *longtempornorun;
708 roaring_bitmap_t *longtemporruns;
709 if (count == 1) {
710 longtempornorun = rnorun[0];
711 longtemporruns = rruns[0];
712 } else {
713 assert(roaring_bitmap_equals(rnorun[0], rruns[0]));
714 assert(roaring_bitmap_equals(rnorun[1], rruns[1]));
715 longtempornorun = roaring_bitmap_xor(rnorun[0], rnorun[1]);
716 longtemporruns = roaring_bitmap_xor(rruns[0], rruns[1]);
717 assert(roaring_bitmap_equals(longtempornorun, longtemporruns));
718 for (int i = 2; i < (int)count; ++i) {
719 assert(roaring_bitmap_equals(rnorun[i], rruns[i]));
720 assert(roaring_bitmap_equals(longtempornorun, longtemporruns));
721
722 roaring_bitmap_t *t1 =
723 roaring_bitmap_xor(rnorun[i], longtempornorun);
724 roaring_bitmap_t *t2 = roaring_bitmap_xor(rruns[i], longtemporruns);
725 assert(roaring_bitmap_equals(t1, t2));
726 roaring_bitmap_free(longtempornorun);
727 longtempornorun = t1;
728 roaring_bitmap_free(longtemporruns);
729 longtemporruns = t2;
730 assert(roaring_bitmap_equals(longtempornorun, longtemporruns));
731 }
732 }
733 if (!slow_bitmap_equals(longtempornorun, tempornorun)) {
734 printf("[compare_wide_xors] Xors don't agree! (regular) \n");
735 return false;
736 }
737 if (!slow_bitmap_equals(temporruns, longtemporruns)) {
738 printf("[compare_wide_xors] Xors don't agree! (runs) \n");
739 return false;
740 }
741 roaring_bitmap_free(tempornorun);
742 roaring_bitmap_free(temporruns);
743
744 roaring_bitmap_free(longtempornorun);
745 roaring_bitmap_free(longtemporruns);
746
747 return true;
748}
749
750bool is_bitmap_equal_to_array(roaring_bitmap_t *bitmap, uint32_t *vals,
751 size_t numbers) {
752 uint64_t card;
753 card = roaring_bitmap_get_cardinality(bitmap);
754 uint32_t *arr = (uint32_t *)malloc(card * sizeof(uint32_t));
755 roaring_bitmap_to_uint32_array(bitmap, arr);
756 bool answer = array_equals(arr, card, vals, numbers);
757 free(arr);
758 return answer;
759}
760
761bool loadAndCheckAll(const char *dirname, bool copy_on_write) {
762 printf("[%s] %s datadir=%s %s\n", __FILE__, __func__, dirname,
763 copy_on_write ? "copy-on-write" : "hard-copies");
764
765 const char *extension = ".txt";
766 size_t count;
767
768 size_t *howmany = NULL;
769 uint32_t **numbers =
770 read_all_integer_files(dirname, extension, &howmany, &count);
771 if (numbers == NULL) {
772 printf(
773 "I could not find or load any data file with extension %s in "
774 "directory %s.\n",
775 extension, dirname);
776 return false;
777 }
778
779 roaring_bitmap_t **bitmaps =
780 create_all_bitmaps(howmany, numbers, count, copy_on_write);
781 for (size_t i = 0; i < count; i++) {
782 if (!is_bitmap_equal_to_array(bitmaps[i], numbers[i], howmany[i])) {
783 printf("arrays don't agree with set values\n");
784 return false;
785 }
786 }
787
788 roaring_bitmap_t **bitmapswrun = malloc(sizeof(roaring_bitmap_t *) * count);
789 for (int i = 0; i < (int)count; i++) {
790 bitmapswrun[i] = roaring_bitmap_copy(bitmaps[i]);
791 roaring_bitmap_run_optimize(bitmapswrun[i]);
792 if (roaring_bitmap_get_cardinality(bitmaps[i]) !=
793 roaring_bitmap_get_cardinality(bitmapswrun[i])) {
794 printf("cardinality change due to roaring_bitmap_run_optimize\n");
795 return false;
796 }
797 }
798 for (size_t i = 0; i < count; i++) {
799 if (!is_bitmap_equal_to_array(bitmapswrun[i], numbers[i], howmany[i])) {
800 printf("arrays don't agree with set values\n");
801 return false;
802 }
803 }
804 for (int i = 0; i < (int)count; i++) {
805 if (!serialize_correctly(bitmaps[i])) {
806 return false; // memory leaks
807 }
808 if (!serialize_correctly(bitmapswrun[i])) {
809 return false; // memory leaks
810 }
811 }
812 if (!compare_intersections(bitmaps, bitmapswrun, count)) {
813 return false; // memory leaks
814 }
815 if (!compare_unions(bitmaps, bitmapswrun, count)) {
816 return false; // memory leaks
817 }
818 if (!compare_wide_unions(bitmaps, bitmapswrun, count)) {
819 return false; // memory leaks
820 }
821
822 if (!compare_negations(bitmaps, bitmapswrun, count)) {
823 return false; // memory leaks
824 }
825
826 if (!compare_xors(bitmaps, bitmapswrun, count)) {
827 return false; // memory leaks
828 }
829
830 if (!compare_andnots(bitmaps, bitmapswrun, count)) {
831 return false; // memory leaks
832 }
833
834 if (!compare_wide_xors(bitmaps, bitmapswrun, count)) {
835 return false; // memory leaks
836 }
837
838 for (int i = 0; i < (int)count; ++i) {
839 free(numbers[i]);
840 numbers[i] = NULL; // paranoid
841 roaring_bitmap_free(bitmaps[i]);
842 bitmaps[i] = NULL; // paranoid
843 roaring_bitmap_free(bitmapswrun[i]);
844 bitmapswrun[i] = NULL; // paranoid
845 }
846 free(bitmapswrun);
847 free(bitmaps);
848 free(howmany);
849 free(numbers);
850
851 return true;
852}
853
854int main() {
855 char dirbuffer[1024];
856 size_t bddl = strlen(BENCHMARK_DATA_DIR);
857 strcpy(dirbuffer, BENCHMARK_DATA_DIR);
858 for (size_t i = 0; i < sizeof(datadir) / sizeof(const char *); i++) {
859 strcpy(dirbuffer + bddl, datadir[i]);
860 if (!loadAndCheckAll(dirbuffer, false)) {
861 printf("failure\n");
862 return -1;
863 }
864 if (!loadAndCheckAll(dirbuffer, true)) {
865 printf("failure\n");
866 return -1;
867 }
868 }
869
870 return EXIT_SUCCESS;
871}
872