1/*
2 * run_container_unit.c
3 *
4 */
5
6#include <stdint.h>
7#include <stdio.h>
8#include <stdlib.h>
9
10#include <roaring/containers/run.h>
11
12#include "test.h"
13
14void printf_test() {
15 run_container_t* B = run_container_create();
16
17 assert_non_null(B);
18
19 run_container_add(B, 1);
20 run_container_add(B, 2);
21 run_container_add(B, 3);
22 run_container_add(B, 10);
23 run_container_add(B, 10000);
24
25 run_container_printf(B);
26 printf("\n");
27
28 run_container_free(B);
29}
30
31void add_contains_test() {
32 run_container_t* B = run_container_create();
33 assert_non_null(B);
34
35 int expected_card = 0;
36 for (size_t x = 0; x < 1 << 16; x += 3) {
37 assert_true(run_container_add(B, x));
38 assert_true(run_container_contains(B, x));
39 assert_int_equal(run_container_cardinality(B), ++expected_card);
40 assert_true(run_container_cardinality(B) <= B->capacity);
41 }
42
43 for (size_t x = 0; x < 1 << 16; x++) {
44 assert_int_equal(run_container_contains(B, x), (x / 3 * 3 == x));
45 }
46
47 assert_int_equal(run_container_cardinality(B), (1 << 16) / 3 + 1);
48
49 for (size_t x = 0; x < 1 << 16; x += 3) {
50 assert_true(run_container_contains(B, x));
51 assert_true(run_container_remove(B, x));
52 assert_int_equal(run_container_cardinality(B), --expected_card);
53 assert_false(run_container_contains(B, x));
54 }
55
56 assert_int_equal(run_container_cardinality(B), 0);
57
58 for (int x = 65535; x >= 0; x -= 3) {
59 assert_true(run_container_add(B, x));
60 assert_true(run_container_contains(B, x));
61 assert_int_equal(run_container_cardinality(B), ++expected_card);
62 assert_true(run_container_cardinality(B) <= B->capacity);
63 }
64
65 assert_int_equal(run_container_cardinality(B), (1 << 16) / 3 + 1);
66
67 for (size_t x = 0; x < 1 << 16; x++) {
68 assert_int_equal(run_container_contains(B, x), (x / 3 * 3 == x));
69 }
70
71 for (size_t x = 0; x < 1 << 16; x += 3) {
72 assert_true(run_container_contains(B, x));
73 assert_true(run_container_remove(B, x));
74 assert_int_equal(run_container_cardinality(B), --expected_card);
75 assert_false(run_container_contains(B, x));
76 }
77
78 run_container_free(B);
79}
80
81void and_or_test() {
82 run_container_t* B1 = run_container_create();
83 run_container_t* B2 = run_container_create();
84 run_container_t* BI = run_container_create();
85 run_container_t* BO = run_container_create();
86 run_container_t* TMP = run_container_create();
87
88 assert_non_null(B1);
89 assert_non_null(B2);
90 assert_non_null(BI);
91 assert_non_null(BO);
92 assert_non_null(TMP);
93
94 for (size_t x = 0; x < (1 << 16); x += 3) {
95 run_container_add(B1, x);
96 run_container_add(BI, x);
97 }
98
99 // important: 62 is not divisible by 3
100 for (size_t x = 0; x < (1 << 16); x += 62) {
101 run_container_add(B2, x);
102 run_container_add(BI, x);
103 }
104
105 for (size_t x = 0; x < (1 << 16); x += 62 * 3) {
106 run_container_add(BO, x);
107 }
108
109 run_container_intersection(B1, B2, TMP);
110 assert_true(run_container_equals(BO, TMP));
111
112 run_container_union(B1, B2, TMP);
113 assert_true(run_container_equals(BI, TMP));
114
115 run_container_free(B1);
116 run_container_free(B2);
117 run_container_free(BO);
118 run_container_free(BI);
119 run_container_free(TMP);
120}
121
122// returns 0 on error, 1 if ok.
123void to_uint32_array_test() {
124 for (size_t offset = 1; offset < 128; offset *= 2) {
125 run_container_t* B = run_container_create();
126 assert_non_null(B);
127
128 for (int k = 0; k < (1 << 16); k += offset) {
129 run_container_add(B, k);
130 }
131
132 int card = run_container_cardinality(B);
133 uint32_t* out = malloc(sizeof(uint32_t) * card);
134 int nc = run_container_to_uint32_array(out, B, 0);
135 assert_int_equal(nc, card);
136
137 for (int k = 1; k < nc; ++k) {
138 assert_int_equal(out[k], offset + out[k - 1]);
139 }
140
141 free(out);
142 run_container_free(B);
143 }
144}
145
146void select_test() {
147 run_container_t* B = run_container_create();
148 assert_non_null(B);
149 uint16_t base = 27;
150 for (uint16_t value = base; value < base + 200; value += 5) {
151 run_container_add(B, value);
152 }
153 uint32_t i = 0;
154 uint32_t element = 0;
155 uint32_t start_rank;
156 for (uint16_t value = base; value < base + 200; value += 5) {
157 start_rank = 12;
158 assert_true(run_container_select(B, &start_rank, i + 12, &element));
159 assert_int_equal(element, value);
160 i++;
161 }
162 start_rank = 12;
163 assert_false(run_container_select(B, &start_rank, i + 12, &element));
164 assert_int_equal(start_rank, i + 12);
165 run_container_free(B);
166}
167
168void remove_range_test() {
169 run_container_t* run = run_container_create();
170 run_container_add_range(run, 100, 150);
171 run_container_add_range(run, 200, 250);
172 run_container_add_range(run, 300, 350);
173
174 // act on left-most run
175 run_container_remove_range(run, 100, 110);
176 run_container_remove_range(run, 140, 150);
177 run_container_remove_range(run, 120, 130);
178
179 // act on right-most run
180 run_container_remove_range(run, 300, 310);
181 run_container_remove_range(run, 340, 350);
182 run_container_remove_range(run, 320, 330);
183
184 // act on inner run
185 run_container_remove_range(run, 200, 210);
186 run_container_remove_range(run, 240, 250);
187 run_container_remove_range(run, 220, 230);
188
189 // [111..119], [131..139], [211..219], [231..239], [311..319], [331..339]
190
191 // remove entire runs
192 run_container_remove_range(run, 111, 119);
193 run_container_remove_range(run, 331, 339);
194 run_container_remove_range(run, 231, 239);
195
196 // [131..139], [211..219], [311..319]
197
198 assert_true(run_container_contains_range(run, 131, 139+1));
199 assert_true(run_container_contains_range(run, 211, 219+1));
200 assert_true(run_container_contains_range(run, 311, 319+1));
201 assert_true(run_container_cardinality(run) == 27);
202
203 run_container_free(run);
204}
205
206int main() {
207 const struct CMUnitTest tests[] = {
208 cmocka_unit_test(printf_test), cmocka_unit_test(add_contains_test),
209 cmocka_unit_test(and_or_test), cmocka_unit_test(to_uint32_array_test),
210 cmocka_unit_test(select_test),
211 cmocka_unit_test(remove_range_test),
212 };
213
214 return cmocka_run_group_tests(tests, NULL, NULL);
215}
216