1/*
2 * mixed_intersection.c
3 *
4 */
5
6#include <roaring/array_util.h>
7#include <roaring/bitset_util.h>
8#include <roaring/containers/convert.h>
9#include <roaring/containers/mixed_intersection.h>
10
11/* Compute the intersection of src_1 and src_2 and write the result to
12 * dst. */
13void array_bitset_container_intersection(const array_container_t *src_1,
14 const bitset_container_t *src_2,
15 array_container_t *dst) {
16 if (dst->capacity < src_1->cardinality) {
17 array_container_grow(dst, src_1->cardinality, false);
18 }
19 int32_t newcard = 0; // dst could be src_1
20 const int32_t origcard = src_1->cardinality;
21 for (int i = 0; i < origcard; ++i) {
22 uint16_t key = src_1->array[i];
23 // this branchless approach is much faster...
24 dst->array[newcard] = key;
25 newcard += bitset_container_contains(src_2, key);
26 /**
27 * we could do it this way instead...
28 * if (bitset_container_contains(src_2, key)) {
29 * dst->array[newcard++] = key;
30 * }
31 * but if the result is unpredictible, the processor generates
32 * many mispredicted branches.
33 * Difference can be huge (from 3 cycles when predictible all the way
34 * to 16 cycles when unpredictible.
35 * See
36 * https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/extra/bitset/c/arraybitsetintersection.c
37 */
38 }
39 dst->cardinality = newcard;
40}
41
42/* Compute the size of the intersection of src_1 and src_2. */
43int array_bitset_container_intersection_cardinality(
44 const array_container_t *src_1, const bitset_container_t *src_2) {
45 int32_t newcard = 0;
46 const int32_t origcard = src_1->cardinality;
47 for (int i = 0; i < origcard; ++i) {
48 uint16_t key = src_1->array[i];
49 newcard += bitset_container_contains(src_2, key);
50 }
51 return newcard;
52}
53
54
55bool array_bitset_container_intersect(const array_container_t *src_1,
56 const bitset_container_t *src_2) {
57 const int32_t origcard = src_1->cardinality;
58 for (int i = 0; i < origcard; ++i) {
59 uint16_t key = src_1->array[i];
60 if(bitset_container_contains(src_2, key)) return true;
61 }
62 return false;
63}
64
65/* Compute the intersection of src_1 and src_2 and write the result to
66 * dst. It is allowed for dst to be equal to src_1. We assume that dst is a
67 * valid container. */
68void array_run_container_intersection(const array_container_t *src_1,
69 const run_container_t *src_2,
70 array_container_t *dst) {
71 if (run_container_is_full(src_2)) {
72 if (dst != src_1) array_container_copy(src_1, dst);
73 return;
74 }
75 if (dst->capacity < src_1->cardinality) {
76 array_container_grow(dst, src_1->cardinality, false);
77 }
78 if (src_2->n_runs == 0) {
79 return;
80 }
81 int32_t rlepos = 0;
82 int32_t arraypos = 0;
83 rle16_t rle = src_2->runs[rlepos];
84 int32_t newcard = 0;
85 while (arraypos < src_1->cardinality) {
86 const uint16_t arrayval = src_1->array[arraypos];
87 while (rle.value + rle.length <
88 arrayval) { // this will frequently be false
89 ++rlepos;
90 if (rlepos == src_2->n_runs) {
91 dst->cardinality = newcard;
92 return; // we are done
93 }
94 rle = src_2->runs[rlepos];
95 }
96 if (rle.value > arrayval) {
97 arraypos = advanceUntil(src_1->array, arraypos, src_1->cardinality,
98 rle.value);
99 } else {
100 dst->array[newcard] = arrayval;
101 newcard++;
102 arraypos++;
103 }
104 }
105 dst->cardinality = newcard;
106}
107
108/* Compute the intersection of src_1 and src_2 and write the result to
109 * *dst. If the result is true then the result is a bitset_container_t
110 * otherwise is a array_container_t. If *dst == src_2, an in-place processing
111 * is attempted.*/
112bool run_bitset_container_intersection(const run_container_t *src_1,
113 const bitset_container_t *src_2,
114 void **dst) {
115 if (run_container_is_full(src_1)) {
116 if (*dst != src_2) *dst = bitset_container_clone(src_2);
117 return true;
118 }
119 int32_t card = run_container_cardinality(src_1);
120 if (card <= DEFAULT_MAX_SIZE) {
121 // result can only be an array (assuming that we never make a
122 // RunContainer)
123 if (card > src_2->cardinality) {
124 card = src_2->cardinality;
125 }
126 array_container_t *answer = array_container_create_given_capacity(card);
127 *dst = answer;
128 if (*dst == NULL) {
129 return false;
130 }
131 for (int32_t rlepos = 0; rlepos < src_1->n_runs; ++rlepos) {
132 rle16_t rle = src_1->runs[rlepos];
133 uint32_t endofrun = (uint32_t)rle.value + rle.length;
134 for (uint32_t runValue = rle.value; runValue <= endofrun;
135 ++runValue) {
136 answer->array[answer->cardinality] = (uint16_t)runValue;
137 answer->cardinality +=
138 bitset_container_contains(src_2, runValue);
139 }
140 }
141 return false;
142 }
143 if (*dst == src_2) { // we attempt in-place
144 bitset_container_t *answer = (bitset_container_t *)*dst;
145 uint32_t start = 0;
146 for (int32_t rlepos = 0; rlepos < src_1->n_runs; ++rlepos) {
147 const rle16_t rle = src_1->runs[rlepos];
148 uint32_t end = rle.value;
149 bitset_reset_range(src_2->array, start, end);
150
151 start = end + rle.length + 1;
152 }
153 bitset_reset_range(src_2->array, start, UINT32_C(1) << 16);
154 answer->cardinality = bitset_container_compute_cardinality(answer);
155 if (src_2->cardinality > DEFAULT_MAX_SIZE) {
156 return true;
157 } else {
158 array_container_t *newanswer = array_container_from_bitset(src_2);
159 if (newanswer == NULL) {
160 *dst = NULL;
161 return false;
162 }
163 *dst = newanswer;
164 return false;
165 }
166 } else { // no inplace
167 // we expect the answer to be a bitmap (if we are lucky)
168 bitset_container_t *answer = bitset_container_clone(src_2);
169
170 *dst = answer;
171 if (answer == NULL) {
172 return true;
173 }
174 uint32_t start = 0;
175 for (int32_t rlepos = 0; rlepos < src_1->n_runs; ++rlepos) {
176 const rle16_t rle = src_1->runs[rlepos];
177 uint32_t end = rle.value;
178 bitset_reset_range(answer->array, start, end);
179 start = end + rle.length + 1;
180 }
181 bitset_reset_range(answer->array, start, UINT32_C(1) << 16);
182 answer->cardinality = bitset_container_compute_cardinality(answer);
183
184 if (answer->cardinality > DEFAULT_MAX_SIZE) {
185 return true;
186 } else {
187 array_container_t *newanswer = array_container_from_bitset(answer);
188 bitset_container_free((bitset_container_t *)*dst);
189 if (newanswer == NULL) {
190 *dst = NULL;
191 return false;
192 }
193 *dst = newanswer;
194 return false;
195 }
196 }
197}
198
199/* Compute the size of the intersection between src_1 and src_2 . */
200int array_run_container_intersection_cardinality(const array_container_t *src_1,
201 const run_container_t *src_2) {
202 if (run_container_is_full(src_2)) {
203 return src_1->cardinality;
204 }
205 if (src_2->n_runs == 0) {
206 return 0;
207 }
208 int32_t rlepos = 0;
209 int32_t arraypos = 0;
210 rle16_t rle = src_2->runs[rlepos];
211 int32_t newcard = 0;
212 while (arraypos < src_1->cardinality) {
213 const uint16_t arrayval = src_1->array[arraypos];
214 while (rle.value + rle.length <
215 arrayval) { // this will frequently be false
216 ++rlepos;
217 if (rlepos == src_2->n_runs) {
218 return newcard; // we are done
219 }
220 rle = src_2->runs[rlepos];
221 }
222 if (rle.value > arrayval) {
223 arraypos = advanceUntil(src_1->array, arraypos, src_1->cardinality,
224 rle.value);
225 } else {
226 newcard++;
227 arraypos++;
228 }
229 }
230 return newcard;
231}
232
233/* Compute the intersection between src_1 and src_2
234 **/
235int run_bitset_container_intersection_cardinality(
236 const run_container_t *src_1, const bitset_container_t *src_2) {
237 if (run_container_is_full(src_1)) {
238 return bitset_container_cardinality(src_2);
239 }
240 int answer = 0;
241 for (int32_t rlepos = 0; rlepos < src_1->n_runs; ++rlepos) {
242 rle16_t rle = src_1->runs[rlepos];
243 answer +=
244 bitset_lenrange_cardinality(src_2->array, rle.value, rle.length);
245 }
246 return answer;
247}
248
249
250bool array_run_container_intersect(const array_container_t *src_1,
251 const run_container_t *src_2) {
252 if( run_container_is_full(src_2) ) {
253 return !array_container_empty(src_1);
254 }
255 if (src_2->n_runs == 0) {
256 return false;
257 }
258 int32_t rlepos = 0;
259 int32_t arraypos = 0;
260 rle16_t rle = src_2->runs[rlepos];
261 while (arraypos < src_1->cardinality) {
262 const uint16_t arrayval = src_1->array[arraypos];
263 while (rle.value + rle.length <
264 arrayval) { // this will frequently be false
265 ++rlepos;
266 if (rlepos == src_2->n_runs) {
267 return false; // we are done
268 }
269 rle = src_2->runs[rlepos];
270 }
271 if (rle.value > arrayval) {
272 arraypos = advanceUntil(src_1->array, arraypos, src_1->cardinality,
273 rle.value);
274 } else {
275 return true;
276 }
277 }
278 return false;
279}
280
281/* Compute the intersection between src_1 and src_2
282 **/
283bool run_bitset_container_intersect(const run_container_t *src_1,
284 const bitset_container_t *src_2) {
285 if( run_container_is_full(src_1) ) {
286 return !bitset_container_empty(src_2);
287 }
288 for (int32_t rlepos = 0; rlepos < src_1->n_runs; ++rlepos) {
289 rle16_t rle = src_1->runs[rlepos];
290 if(!bitset_lenrange_empty(src_2->array, rle.value,rle.length)) return true;
291 }
292 return false;
293}
294
295/*
296 * Compute the intersection between src_1 and src_2 and write the result
297 * to *dst. If the return function is true, the result is a bitset_container_t
298 * otherwise is a array_container_t.
299 */
300bool bitset_bitset_container_intersection(const bitset_container_t *src_1,
301 const bitset_container_t *src_2,
302 void **dst) {
303 const int newCardinality = bitset_container_and_justcard(src_1, src_2);
304 if (newCardinality > DEFAULT_MAX_SIZE) {
305 *dst = bitset_container_create();
306 if (*dst != NULL) {
307 bitset_container_and_nocard(src_1, src_2,
308 (bitset_container_t *)*dst);
309 ((bitset_container_t *)*dst)->cardinality = newCardinality;
310 }
311 return true; // it is a bitset
312 }
313 *dst = array_container_create_given_capacity(newCardinality);
314 if (*dst != NULL) {
315 ((array_container_t *)*dst)->cardinality = newCardinality;
316 bitset_extract_intersection_setbits_uint16(
317 ((const bitset_container_t *)src_1)->array,
318 ((const bitset_container_t *)src_2)->array,
319 BITSET_CONTAINER_SIZE_IN_WORDS, ((array_container_t *)*dst)->array,
320 0);
321 }
322 return false; // not a bitset
323}
324
325bool bitset_bitset_container_intersection_inplace(
326 bitset_container_t *src_1, const bitset_container_t *src_2, void **dst) {
327 const int newCardinality = bitset_container_and_justcard(src_1, src_2);
328 if (newCardinality > DEFAULT_MAX_SIZE) {
329 *dst = src_1;
330 bitset_container_and_nocard(src_1, src_2, src_1);
331 ((bitset_container_t *)*dst)->cardinality = newCardinality;
332 return true; // it is a bitset
333 }
334 *dst = array_container_create_given_capacity(newCardinality);
335 if (*dst != NULL) {
336 ((array_container_t *)*dst)->cardinality = newCardinality;
337 bitset_extract_intersection_setbits_uint16(
338 ((const bitset_container_t *)src_1)->array,
339 ((const bitset_container_t *)src_2)->array,
340 BITSET_CONTAINER_SIZE_IN_WORDS, ((array_container_t *)*dst)->array,
341 0);
342 }
343 return false; // not a bitset
344}
345