1#ifndef CONTAINERS_CONTAINERS_H
2#define CONTAINERS_CONTAINERS_H
3
4#include <assert.h>
5#include <stdbool.h>
6#include <stdio.h>
7
8#include <roaring/containers/array.h>
9#include <roaring/containers/bitset.h>
10#include <roaring/containers/convert.h>
11#include <roaring/containers/mixed_andnot.h>
12#include <roaring/containers/mixed_equal.h>
13#include <roaring/containers/mixed_intersection.h>
14#include <roaring/containers/mixed_negation.h>
15#include <roaring/containers/mixed_subset.h>
16#include <roaring/containers/mixed_union.h>
17#include <roaring/containers/mixed_xor.h>
18#include <roaring/containers/run.h>
19#include <roaring/bitset_util.h>
20
21// would enum be possible or better?
22
23/**
24 * The switch case statements follow
25 * BITSET_CONTAINER_TYPE_CODE -- ARRAY_CONTAINER_TYPE_CODE --
26 * RUN_CONTAINER_TYPE_CODE
27 * so it makes more sense to number them 1, 2, 3 (in the vague hope that the
28 * compiler might exploit this ordering).
29 */
30
31#define BITSET_CONTAINER_TYPE_CODE 1
32#define ARRAY_CONTAINER_TYPE_CODE 2
33#define RUN_CONTAINER_TYPE_CODE 3
34#define SHARED_CONTAINER_TYPE_CODE 4
35
36// macro for pairing container type codes
37#define CONTAINER_PAIR(c1, c2) (4 * (c1) + (c2))
38
39/**
40 * A shared container is a wrapper around a container
41 * with reference counting.
42 */
43
44struct shared_container_s {
45 void *container;
46 uint8_t typecode;
47 uint32_t counter; // to be managed atomically
48};
49
50typedef struct shared_container_s shared_container_t;
51
52/*
53 * With copy_on_write = true
54 * Create a new shared container if the typecode is not SHARED_CONTAINER_TYPE,
55 * otherwise, increase the count
56 * If copy_on_write = false, then clone.
57 * Return NULL in case of failure.
58 **/
59void *get_copy_of_container(void *container, uint8_t *typecode,
60 bool copy_on_write);
61
62/* Frees a shared container (actually decrement its counter and only frees when
63 * the counter falls to zero). */
64void shared_container_free(shared_container_t *container);
65
66/* extract a copy from the shared container, freeing the shared container if
67there is just one instance left,
68clone instances when the counter is higher than one
69*/
70void *shared_container_extract_copy(shared_container_t *container,
71 uint8_t *typecode);
72
73/* access to container underneath */
74inline const void *container_unwrap_shared(
75 const void *candidate_shared_container, uint8_t *type) {
76 if (*type == SHARED_CONTAINER_TYPE_CODE) {
77 *type =
78 ((const shared_container_t *)candidate_shared_container)->typecode;
79 assert(*type != SHARED_CONTAINER_TYPE_CODE);
80 return ((const shared_container_t *)candidate_shared_container)->container;
81 } else {
82 return candidate_shared_container;
83 }
84}
85
86
87/* access to container underneath */
88inline void *container_mutable_unwrap_shared(
89 void *candidate_shared_container, uint8_t *type) {
90 if (*type == SHARED_CONTAINER_TYPE_CODE) {
91 *type =
92 ((shared_container_t *)candidate_shared_container)->typecode;
93 assert(*type != SHARED_CONTAINER_TYPE_CODE);
94 return ((shared_container_t *)candidate_shared_container)->container;
95 } else {
96 return candidate_shared_container;
97 }
98}
99
100/* access to container underneath and queries its type */
101static inline uint8_t get_container_type(const void *container, uint8_t type) {
102 if (type == SHARED_CONTAINER_TYPE_CODE) {
103 return ((const shared_container_t *)container)->typecode;
104 } else {
105 return type;
106 }
107}
108
109/**
110 * Copies a container, requires a typecode. This allocates new memory, caller
111 * is responsible for deallocation. If the container is not shared, then it is
112 * physically cloned. Sharable containers are not cloneable.
113 */
114void *container_clone(const void *container, uint8_t typecode);
115
116/* access to container underneath, cloning it if needed */
117static inline void *get_writable_copy_if_shared(
118 void *candidate_shared_container, uint8_t *type) {
119 if (*type == SHARED_CONTAINER_TYPE_CODE) {
120 return shared_container_extract_copy(
121 (shared_container_t *)candidate_shared_container, type);
122 } else {
123 return candidate_shared_container;
124 }
125}
126
127/**
128 * End of shared container code
129 */
130
131static const char *container_names[] = {"bitset", "array", "run", "shared"};
132static const char *shared_container_names[] = {
133 "bitset (shared)", "array (shared)", "run (shared)"};
134
135// no matter what the initial container was, convert it to a bitset
136// if a new container is produced, caller responsible for freeing the previous
137// one
138// container should not be a shared container
139static inline void *container_to_bitset(void *container, uint8_t typecode) {
140 bitset_container_t *result = NULL;
141 switch (typecode) {
142 case BITSET_CONTAINER_TYPE_CODE:
143 return container; // nothing to do
144 case ARRAY_CONTAINER_TYPE_CODE:
145 result =
146 bitset_container_from_array((array_container_t *)container);
147 return result;
148 case RUN_CONTAINER_TYPE_CODE:
149 result = bitset_container_from_run((run_container_t *)container);
150 return result;
151 case SHARED_CONTAINER_TYPE_CODE:
152 assert(false);
153 }
154 assert(false);
155 __builtin_unreachable();
156 return 0; // unreached
157}
158
159/**
160 * Get the container name from the typecode
161 */
162static inline const char *get_container_name(uint8_t typecode) {
163 switch (typecode) {
164 case BITSET_CONTAINER_TYPE_CODE:
165 return container_names[0];
166 case ARRAY_CONTAINER_TYPE_CODE:
167 return container_names[1];
168 case RUN_CONTAINER_TYPE_CODE:
169 return container_names[2];
170 case SHARED_CONTAINER_TYPE_CODE:
171 return container_names[3];
172 default:
173 assert(false);
174 __builtin_unreachable();
175 return "unknown";
176 }
177}
178
179static inline const char *get_full_container_name(const void *container,
180 uint8_t typecode) {
181 switch (typecode) {
182 case BITSET_CONTAINER_TYPE_CODE:
183 return container_names[0];
184 case ARRAY_CONTAINER_TYPE_CODE:
185 return container_names[1];
186 case RUN_CONTAINER_TYPE_CODE:
187 return container_names[2];
188 case SHARED_CONTAINER_TYPE_CODE:
189 switch (((const shared_container_t *)container)->typecode) {
190 case BITSET_CONTAINER_TYPE_CODE:
191 return shared_container_names[0];
192 case ARRAY_CONTAINER_TYPE_CODE:
193 return shared_container_names[1];
194 case RUN_CONTAINER_TYPE_CODE:
195 return shared_container_names[2];
196 default:
197 assert(false);
198 __builtin_unreachable();
199 return "unknown";
200 }
201 break;
202 default:
203 assert(false);
204 __builtin_unreachable();
205 return "unknown";
206 }
207 __builtin_unreachable();
208 return NULL;
209}
210
211/**
212 * Get the container cardinality (number of elements), requires a typecode
213 */
214static inline int container_get_cardinality(const void *container,
215 uint8_t typecode) {
216 container = container_unwrap_shared(container, &typecode);
217 switch (typecode) {
218 case BITSET_CONTAINER_TYPE_CODE:
219 return bitset_container_cardinality(
220 (const bitset_container_t *)container);
221 case ARRAY_CONTAINER_TYPE_CODE:
222 return array_container_cardinality(
223 (const array_container_t *)container);
224 case RUN_CONTAINER_TYPE_CODE:
225 return run_container_cardinality(
226 (const run_container_t *)container);
227 }
228 assert(false);
229 __builtin_unreachable();
230 return 0; // unreached
231}
232
233
234
235// returns true if a container is known to be full. Note that a lazy bitset
236// container
237// might be full without us knowing
238static inline bool container_is_full(const void *container, uint8_t typecode) {
239 container = container_unwrap_shared(container, &typecode);
240 switch (typecode) {
241 case BITSET_CONTAINER_TYPE_CODE:
242 return bitset_container_cardinality(
243 (const bitset_container_t *)container) == (1 << 16);
244 case ARRAY_CONTAINER_TYPE_CODE:
245 return array_container_cardinality(
246 (const array_container_t *)container) == (1 << 16);
247 case RUN_CONTAINER_TYPE_CODE:
248 return run_container_is_full((const run_container_t *)container);
249 }
250 assert(false);
251 __builtin_unreachable();
252 return 0; // unreached
253}
254
255static inline int container_shrink_to_fit(void *container, uint8_t typecode) {
256 container = container_mutable_unwrap_shared(container, &typecode);
257 switch (typecode) {
258 case BITSET_CONTAINER_TYPE_CODE:
259 return 0; // no shrinking possible
260 case ARRAY_CONTAINER_TYPE_CODE:
261 return array_container_shrink_to_fit(
262 (array_container_t *)container);
263 case RUN_CONTAINER_TYPE_CODE:
264 return run_container_shrink_to_fit((run_container_t *)container);
265 }
266 assert(false);
267 __builtin_unreachable();
268 return 0; // unreached
269}
270
271
272/**
273 * make a container with a run of ones
274 */
275/* initially always use a run container, even if an array might be
276 * marginally
277 * smaller */
278static inline void *container_range_of_ones(uint32_t range_start,
279 uint32_t range_end,
280 uint8_t *result_type) {
281 assert(range_end >= range_start);
282 uint64_t cardinality = range_end - range_start + 1;
283 if(cardinality <= 2) {
284 *result_type = ARRAY_CONTAINER_TYPE_CODE;
285 return array_container_create_range(range_start, range_end);
286 } else {
287 *result_type = RUN_CONTAINER_TYPE_CODE;
288 return run_container_create_range(range_start, range_end);
289 }
290}
291
292
293/* Create a container with all the values between in [min,max) at a
294 distance k*step from min. */
295static inline void *container_from_range(uint8_t *type, uint32_t min,
296 uint32_t max, uint16_t step) {
297 if (step == 0) return NULL; // being paranoid
298 if (step == 1) {
299 return container_range_of_ones(min,max,type);
300 // Note: the result is not always a run (need to check the cardinality)
301 //*type = RUN_CONTAINER_TYPE_CODE;
302 //return run_container_create_range(min, max);
303 }
304 int size = (max - min + step - 1) / step;
305 if (size <= DEFAULT_MAX_SIZE) { // array container
306 *type = ARRAY_CONTAINER_TYPE_CODE;
307 array_container_t *array = array_container_create_given_capacity(size);
308 array_container_add_from_range(array, min, max, step);
309 assert(array->cardinality == size);
310 return array;
311 } else { // bitset container
312 *type = BITSET_CONTAINER_TYPE_CODE;
313 bitset_container_t *bitset = bitset_container_create();
314 bitset_container_add_from_range(bitset, min, max, step);
315 assert(bitset->cardinality == size);
316 return bitset;
317 }
318}
319
320/**
321 * "repair" the container after lazy operations.
322 */
323static inline void *container_repair_after_lazy(void *container,
324 uint8_t *typecode) {
325 container = get_writable_copy_if_shared(
326 container, typecode); // TODO: this introduces unnecessary cloning
327 void *result = NULL;
328 switch (*typecode) {
329 case BITSET_CONTAINER_TYPE_CODE:
330 ((bitset_container_t *)container)->cardinality =
331 bitset_container_compute_cardinality(
332 (bitset_container_t *)container);
333 if (((bitset_container_t *)container)->cardinality <=
334 DEFAULT_MAX_SIZE) {
335 result = array_container_from_bitset(
336 (const bitset_container_t *)container);
337 bitset_container_free((bitset_container_t *)container);
338 *typecode = ARRAY_CONTAINER_TYPE_CODE;
339 return result;
340 }
341 return container;
342 case ARRAY_CONTAINER_TYPE_CODE:
343 return container; // nothing to do
344 case RUN_CONTAINER_TYPE_CODE:
345 return convert_run_to_efficient_container_and_free(
346 (run_container_t *)container, typecode);
347 case SHARED_CONTAINER_TYPE_CODE:
348 assert(false);
349 }
350 assert(false);
351 __builtin_unreachable();
352 return 0; // unreached
353}
354
355/**
356 * Writes the underlying array to buf, outputs how many bytes were written.
357 * This is meant to be byte-by-byte compatible with the Java and Go versions of
358 * Roaring.
359 * The number of bytes written should be
360 * container_write(container, buf).
361 *
362 */
363static inline int32_t container_write(const void *container, uint8_t typecode,
364 char *buf) {
365 container = container_unwrap_shared(container, &typecode);
366 switch (typecode) {
367 case BITSET_CONTAINER_TYPE_CODE:
368 return bitset_container_write((const bitset_container_t *)container, buf);
369 case ARRAY_CONTAINER_TYPE_CODE:
370 return array_container_write((const array_container_t *)container, buf);
371 case RUN_CONTAINER_TYPE_CODE:
372 return run_container_write((const run_container_t *)container, buf);
373 }
374 assert(false);
375 __builtin_unreachable();
376 return 0; // unreached
377}
378
379/**
380 * Get the container size in bytes under portable serialization (see
381 * container_write), requires a
382 * typecode
383 */
384static inline int32_t container_size_in_bytes(const void *container,
385 uint8_t typecode) {
386 container = container_unwrap_shared(container, &typecode);
387 switch (typecode) {
388 case BITSET_CONTAINER_TYPE_CODE:
389 return bitset_container_size_in_bytes(
390 (const bitset_container_t *)container);
391 case ARRAY_CONTAINER_TYPE_CODE:
392 return array_container_size_in_bytes(
393 (const array_container_t *)container);
394 case RUN_CONTAINER_TYPE_CODE:
395 return run_container_size_in_bytes((const run_container_t *)container);
396 }
397 assert(false);
398 __builtin_unreachable();
399 return 0; // unreached
400}
401
402/**
403 * print the container (useful for debugging), requires a typecode
404 */
405void container_printf(const void *container, uint8_t typecode);
406
407/**
408 * print the content of the container as a comma-separated list of 32-bit values
409 * starting at base, requires a typecode
410 */
411void container_printf_as_uint32_array(const void *container, uint8_t typecode,
412 uint32_t base);
413
414/**
415 * Checks whether a container is not empty, requires a typecode
416 */
417static inline bool container_nonzero_cardinality(const void *container,
418 uint8_t typecode) {
419 container = container_unwrap_shared(container, &typecode);
420 switch (typecode) {
421 case BITSET_CONTAINER_TYPE_CODE:
422 return bitset_container_const_nonzero_cardinality(
423 (const bitset_container_t *)container);
424 case ARRAY_CONTAINER_TYPE_CODE:
425 return array_container_nonzero_cardinality(
426 (const array_container_t *)container);
427 case RUN_CONTAINER_TYPE_CODE:
428 return run_container_nonzero_cardinality(
429 (const run_container_t *)container);
430 }
431 assert(false);
432 __builtin_unreachable();
433 return 0; // unreached
434}
435
436/**
437 * Recover memory from a container, requires a typecode
438 */
439void container_free(void *container, uint8_t typecode);
440
441/**
442 * Convert a container to an array of values, requires a typecode as well as a
443 * "base" (most significant values)
444 * Returns number of ints added.
445 */
446static inline int container_to_uint32_array(uint32_t *output,
447 const void *container,
448 uint8_t typecode, uint32_t base) {
449 container = container_unwrap_shared(container, &typecode);
450 switch (typecode) {
451 case BITSET_CONTAINER_TYPE_CODE:
452 return bitset_container_to_uint32_array(
453 output, (const bitset_container_t *)container, base);
454 case ARRAY_CONTAINER_TYPE_CODE:
455 return array_container_to_uint32_array(
456 output, (const array_container_t *)container, base);
457 case RUN_CONTAINER_TYPE_CODE:
458 return run_container_to_uint32_array(
459 output, (const run_container_t *)container, base);
460 }
461 assert(false);
462 __builtin_unreachable();
463 return 0; // unreached
464}
465
466/**
467 * Add a value to a container, requires a typecode, fills in new_typecode and
468 * return (possibly different) container.
469 * This function may allocate a new container, and caller is responsible for
470 * memory deallocation
471 */
472static inline void *container_add(void *container, uint16_t val,
473 uint8_t typecode, uint8_t *new_typecode) {
474 container = get_writable_copy_if_shared(container, &typecode);
475 switch (typecode) {
476 case BITSET_CONTAINER_TYPE_CODE:
477 bitset_container_set((bitset_container_t *)container, val);
478 *new_typecode = BITSET_CONTAINER_TYPE_CODE;
479 return container;
480 case ARRAY_CONTAINER_TYPE_CODE: {
481 array_container_t *ac = (array_container_t *)container;
482 if (array_container_try_add(ac, val, DEFAULT_MAX_SIZE) != -1) {
483 *new_typecode = ARRAY_CONTAINER_TYPE_CODE;
484 return ac;
485 } else {
486 bitset_container_t* bitset = bitset_container_from_array(ac);
487 bitset_container_add(bitset, val);
488 *new_typecode = BITSET_CONTAINER_TYPE_CODE;
489 return bitset;
490 }
491 } break;
492 case RUN_CONTAINER_TYPE_CODE:
493 // per Java, no container type adjustments are done (revisit?)
494 run_container_add((run_container_t *)container, val);
495 *new_typecode = RUN_CONTAINER_TYPE_CODE;
496 return container;
497 default:
498 assert(false);
499 __builtin_unreachable();
500 return NULL;
501 }
502}
503
504/**
505 * Remove a value from a container, requires a typecode, fills in new_typecode
506 * and
507 * return (possibly different) container.
508 * This function may allocate a new container, and caller is responsible for
509 * memory deallocation
510 */
511static inline void *container_remove(void *container, uint16_t val,
512 uint8_t typecode, uint8_t *new_typecode) {
513 container = get_writable_copy_if_shared(container, &typecode);
514 switch (typecode) {
515 case BITSET_CONTAINER_TYPE_CODE:
516 if (bitset_container_remove((bitset_container_t *)container, val)) {
517 if (bitset_container_cardinality(
518 (bitset_container_t *)container) <= DEFAULT_MAX_SIZE) {
519 *new_typecode = ARRAY_CONTAINER_TYPE_CODE;
520 return array_container_from_bitset(
521 (bitset_container_t *)container);
522 }
523 }
524 *new_typecode = typecode;
525 return container;
526 case ARRAY_CONTAINER_TYPE_CODE:
527 *new_typecode = typecode;
528 array_container_remove((array_container_t *)container, val);
529 return container;
530 case RUN_CONTAINER_TYPE_CODE:
531 // per Java, no container type adjustments are done (revisit?)
532 run_container_remove((run_container_t *)container, val);
533 *new_typecode = RUN_CONTAINER_TYPE_CODE;
534 return container;
535 default:
536 assert(false);
537 __builtin_unreachable();
538 return NULL;
539 }
540}
541
542/**
543 * Check whether a value is in a container, requires a typecode
544 */
545inline bool container_contains(const void *container, uint16_t val,
546 uint8_t typecode) {
547 container = container_unwrap_shared(container, &typecode);
548 switch (typecode) {
549 case BITSET_CONTAINER_TYPE_CODE:
550 return bitset_container_get((const bitset_container_t *)container,
551 val);
552 case ARRAY_CONTAINER_TYPE_CODE:
553 return array_container_contains(
554 (const array_container_t *)container, val);
555 case RUN_CONTAINER_TYPE_CODE:
556 return run_container_contains((const run_container_t *)container,
557 val);
558 default:
559 assert(false);
560 __builtin_unreachable();
561 return false;
562 }
563}
564
565/**
566 * Check whether a range of values from range_start (included) to range_end (excluded)
567 * is in a container, requires a typecode
568 */
569static inline bool container_contains_range(const void *container, uint32_t range_start,
570 uint32_t range_end, uint8_t typecode) {
571 container = container_unwrap_shared(container, &typecode);
572 switch (typecode) {
573 case BITSET_CONTAINER_TYPE_CODE:
574 return bitset_container_get_range((const bitset_container_t *)container,
575 range_start, range_end);
576 case ARRAY_CONTAINER_TYPE_CODE:
577 return array_container_contains_range((const array_container_t *)container,
578 range_start, range_end);
579 case RUN_CONTAINER_TYPE_CODE:
580 return run_container_contains_range((const run_container_t *)container,
581 range_start, range_end);
582 default:
583 assert(false);
584 __builtin_unreachable();
585 return false;
586 }
587}
588
589int32_t container_serialize(const void *container, uint8_t typecode,
590 char *buf) WARN_UNUSED;
591
592uint32_t container_serialization_len(const void *container, uint8_t typecode);
593
594void *container_deserialize(uint8_t typecode, const char *buf, size_t buf_len);
595
596/**
597 * Returns true if the two containers have the same content. Note that
598 * two containers having different types can be "equal" in this sense.
599 */
600static inline bool container_equals(const void *c1, uint8_t type1,
601 const void *c2, uint8_t type2) {
602 c1 = container_unwrap_shared(c1, &type1);
603 c2 = container_unwrap_shared(c2, &type2);
604 switch (CONTAINER_PAIR(type1, type2)) {
605 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
606 BITSET_CONTAINER_TYPE_CODE):
607 return bitset_container_equals((const bitset_container_t *)c1,
608 (const bitset_container_t *)c2);
609 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
610 RUN_CONTAINER_TYPE_CODE):
611 return run_container_equals_bitset((const run_container_t *)c2,
612 (const bitset_container_t *)c1);
613 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE,
614 BITSET_CONTAINER_TYPE_CODE):
615 return run_container_equals_bitset((const run_container_t *)c1,
616 (const bitset_container_t *)c2);
617 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
618 ARRAY_CONTAINER_TYPE_CODE):
619 // java would always return false?
620 return array_container_equal_bitset((const array_container_t *)c2,
621 (const bitset_container_t *)c1);
622 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
623 BITSET_CONTAINER_TYPE_CODE):
624 // java would always return false?
625 return array_container_equal_bitset((const array_container_t *)c1,
626 (const bitset_container_t *)c2);
627 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
628 return run_container_equals_array((const run_container_t *)c2,
629 (const array_container_t *)c1);
630 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, ARRAY_CONTAINER_TYPE_CODE):
631 return run_container_equals_array((const run_container_t *)c1,
632 (const array_container_t *)c2);
633 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
634 ARRAY_CONTAINER_TYPE_CODE):
635 return array_container_equals((const array_container_t *)c1,
636 (const array_container_t *)c2);
637 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
638 return run_container_equals((const run_container_t *)c1,
639 (const run_container_t *)c2);
640 default:
641 assert(false);
642 __builtin_unreachable();
643 return false;
644 }
645}
646
647/**
648 * Returns true if the container c1 is a subset of the container c2. Note that
649 * c1 can be a subset of c2 even if they have a different type.
650 */
651static inline bool container_is_subset(const void *c1, uint8_t type1,
652 const void *c2, uint8_t type2) {
653 c1 = container_unwrap_shared(c1, &type1);
654 c2 = container_unwrap_shared(c2, &type2);
655 switch (CONTAINER_PAIR(type1, type2)) {
656 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
657 BITSET_CONTAINER_TYPE_CODE):
658 return bitset_container_is_subset((const bitset_container_t *)c1,
659 (const bitset_container_t *)c2);
660 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
661 RUN_CONTAINER_TYPE_CODE):
662 return bitset_container_is_subset_run((const bitset_container_t *)c1,
663 (const run_container_t *)c2);
664 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE,
665 BITSET_CONTAINER_TYPE_CODE):
666 return run_container_is_subset_bitset((const run_container_t *)c1,
667 (const bitset_container_t *)c2);
668 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
669 ARRAY_CONTAINER_TYPE_CODE):
670 return false; // by construction, size(c1) > size(c2)
671 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
672 BITSET_CONTAINER_TYPE_CODE):
673 return array_container_is_subset_bitset((const array_container_t *)c1,
674 (const bitset_container_t *)c2);
675 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
676 return array_container_is_subset_run((const array_container_t *)c1,
677 (const run_container_t *)c2);
678 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, ARRAY_CONTAINER_TYPE_CODE):
679 return run_container_is_subset_array((const run_container_t *)c1,
680 (const array_container_t *)c2);
681 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
682 ARRAY_CONTAINER_TYPE_CODE):
683 return array_container_is_subset((const array_container_t *)c1,
684 (const array_container_t *)c2);
685 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
686 return run_container_is_subset((const run_container_t *)c1,
687 (const run_container_t *)c2);
688 default:
689 assert(false);
690 __builtin_unreachable();
691 return false;
692 }
693}
694
695// macro-izations possibilities for generic non-inplace binary-op dispatch
696
697/**
698 * Compute intersection between two containers, generate a new container (having
699 * type result_type), requires a typecode. This allocates new memory, caller
700 * is responsible for deallocation.
701 */
702static inline void *container_and(const void *c1, uint8_t type1, const void *c2,
703 uint8_t type2, uint8_t *result_type) {
704 c1 = container_unwrap_shared(c1, &type1);
705 c2 = container_unwrap_shared(c2, &type2);
706 void *result = NULL;
707 switch (CONTAINER_PAIR(type1, type2)) {
708 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
709 BITSET_CONTAINER_TYPE_CODE):
710 *result_type = bitset_bitset_container_intersection(
711 (const bitset_container_t *)c1,
712 (const bitset_container_t *)c2, &result)
713 ? BITSET_CONTAINER_TYPE_CODE
714 : ARRAY_CONTAINER_TYPE_CODE;
715 return result;
716 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
717 ARRAY_CONTAINER_TYPE_CODE):
718 result = array_container_create();
719 array_container_intersection((const array_container_t *)c1,
720 (const array_container_t *)c2,
721 (array_container_t *)result);
722 *result_type = ARRAY_CONTAINER_TYPE_CODE; // never bitset
723 return result;
724 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
725 result = run_container_create();
726 run_container_intersection((const run_container_t *)c1,
727 (const run_container_t *)c2,
728 (run_container_t *)result);
729 return convert_run_to_efficient_container_and_free(
730 (run_container_t *)result, result_type);
731 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
732 ARRAY_CONTAINER_TYPE_CODE):
733 result = array_container_create();
734 array_bitset_container_intersection((const array_container_t *)c2,
735 (const bitset_container_t *)c1,
736 (array_container_t *)result);
737 *result_type = ARRAY_CONTAINER_TYPE_CODE; // never bitset
738 return result;
739 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
740 BITSET_CONTAINER_TYPE_CODE):
741 result = array_container_create();
742 *result_type = ARRAY_CONTAINER_TYPE_CODE; // never bitset
743 array_bitset_container_intersection((const array_container_t *)c1,
744 (const bitset_container_t *)c2,
745 (array_container_t *)result);
746 return result;
747
748 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
749 RUN_CONTAINER_TYPE_CODE):
750 *result_type = run_bitset_container_intersection(
751 (const run_container_t *)c2,
752 (const bitset_container_t *)c1, &result)
753 ? BITSET_CONTAINER_TYPE_CODE
754 : ARRAY_CONTAINER_TYPE_CODE;
755 return result;
756 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE,
757 BITSET_CONTAINER_TYPE_CODE):
758 *result_type = run_bitset_container_intersection(
759 (const run_container_t *)c1,
760 (const bitset_container_t *)c2, &result)
761 ? BITSET_CONTAINER_TYPE_CODE
762 : ARRAY_CONTAINER_TYPE_CODE;
763 return result;
764 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
765 result = array_container_create();
766 *result_type = ARRAY_CONTAINER_TYPE_CODE; // never bitset
767 array_run_container_intersection((const array_container_t *)c1,
768 (const run_container_t *)c2,
769 (array_container_t *)result);
770 return result;
771
772 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, ARRAY_CONTAINER_TYPE_CODE):
773 result = array_container_create();
774 *result_type = ARRAY_CONTAINER_TYPE_CODE; // never bitset
775 array_run_container_intersection((const array_container_t *)c2,
776 (const run_container_t *)c1,
777 (array_container_t *)result);
778 return result;
779 default:
780 assert(false);
781 __builtin_unreachable();
782 return NULL;
783 }
784}
785
786/**
787 * Compute the size of the intersection between two containers.
788 */
789static inline int container_and_cardinality(const void *c1, uint8_t type1,
790 const void *c2, uint8_t type2) {
791 c1 = container_unwrap_shared(c1, &type1);
792 c2 = container_unwrap_shared(c2, &type2);
793 switch (CONTAINER_PAIR(type1, type2)) {
794 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
795 BITSET_CONTAINER_TYPE_CODE):
796 return bitset_container_and_justcard(
797 (const bitset_container_t *)c1, (const bitset_container_t *)c2);
798 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
799 ARRAY_CONTAINER_TYPE_CODE):
800 return array_container_intersection_cardinality(
801 (const array_container_t *)c1, (const array_container_t *)c2);
802 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
803 return run_container_intersection_cardinality(
804 (const run_container_t *)c1, (const run_container_t *)c2);
805 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
806 ARRAY_CONTAINER_TYPE_CODE):
807 return array_bitset_container_intersection_cardinality(
808 (const array_container_t *)c2, (const bitset_container_t *)c1);
809 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
810 BITSET_CONTAINER_TYPE_CODE):
811 return array_bitset_container_intersection_cardinality(
812 (const array_container_t *)c1, (const bitset_container_t *)c2);
813 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
814 RUN_CONTAINER_TYPE_CODE):
815 return run_bitset_container_intersection_cardinality(
816 (const run_container_t *)c2, (const bitset_container_t *)c1);
817 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE,
818 BITSET_CONTAINER_TYPE_CODE):
819 return run_bitset_container_intersection_cardinality(
820 (const run_container_t *)c1, (const bitset_container_t *)c2);
821 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
822 return array_run_container_intersection_cardinality(
823 (const array_container_t *)c1, (const run_container_t *)c2);
824 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, ARRAY_CONTAINER_TYPE_CODE):
825 return array_run_container_intersection_cardinality(
826 (const array_container_t *)c2, (const run_container_t *)c1);
827 default:
828 assert(false);
829 __builtin_unreachable();
830 return 0;
831 }
832}
833
834/**
835 * Check whether two containers intersect.
836 */
837static inline bool container_intersect(const void *c1, uint8_t type1, const void *c2,
838 uint8_t type2) {
839 c1 = container_unwrap_shared(c1, &type1);
840 c2 = container_unwrap_shared(c2, &type2);
841 switch (CONTAINER_PAIR(type1, type2)) {
842 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
843 BITSET_CONTAINER_TYPE_CODE):
844 return bitset_container_intersect(
845 (const bitset_container_t *)c1,
846 (const bitset_container_t *)c2);
847 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
848 ARRAY_CONTAINER_TYPE_CODE):
849 return array_container_intersect((const array_container_t *)c1,
850 (const array_container_t *)c2);
851 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
852 return run_container_intersect((const run_container_t *)c1,
853 (const run_container_t *)c2);
854 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
855 ARRAY_CONTAINER_TYPE_CODE):
856 return array_bitset_container_intersect((const array_container_t *)c2,
857 (const bitset_container_t *)c1);
858 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
859 BITSET_CONTAINER_TYPE_CODE):
860 return array_bitset_container_intersect((const array_container_t *)c1,
861 (const bitset_container_t *)c2);
862 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
863 RUN_CONTAINER_TYPE_CODE):
864 return run_bitset_container_intersect(
865 (const run_container_t *)c2,
866 (const bitset_container_t *)c1);
867 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE,
868 BITSET_CONTAINER_TYPE_CODE):
869 return run_bitset_container_intersect(
870 (const run_container_t *)c1,
871 (const bitset_container_t *)c2);
872 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
873 return array_run_container_intersect((const array_container_t *)c1,
874 (const run_container_t *)c2);
875 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, ARRAY_CONTAINER_TYPE_CODE):
876 return array_run_container_intersect((const array_container_t *)c2,
877 (const run_container_t *)c1);
878 default:
879 assert(false);
880 __builtin_unreachable();
881 return 0;
882 }
883}
884
885/**
886 * Compute intersection between two containers, with result in the first
887 container if possible. If the returned pointer is identical to c1,
888 then the container has been modified. If the returned pointer is different
889 from c1, then a new container has been created and the caller is responsible
890 for freeing it.
891 The type of the first container may change. Returns the modified
892 (and possibly new) container.
893*/
894static inline void *container_iand(void *c1, uint8_t type1, const void *c2,
895 uint8_t type2, uint8_t *result_type) {
896 c1 = get_writable_copy_if_shared(c1, &type1);
897 c2 = container_unwrap_shared(c2, &type2);
898 void *result = NULL;
899 switch (CONTAINER_PAIR(type1, type2)) {
900 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
901 BITSET_CONTAINER_TYPE_CODE):
902 *result_type =
903 bitset_bitset_container_intersection_inplace(
904 (bitset_container_t *)c1, (const bitset_container_t *)c2, &result)
905 ? BITSET_CONTAINER_TYPE_CODE
906 : ARRAY_CONTAINER_TYPE_CODE;
907 return result;
908 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
909 ARRAY_CONTAINER_TYPE_CODE):
910 array_container_intersection_inplace((array_container_t *)c1,
911 (const array_container_t *)c2);
912 *result_type = ARRAY_CONTAINER_TYPE_CODE;
913 return c1;
914 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
915 result = run_container_create();
916 run_container_intersection((const run_container_t *)c1,
917 (const run_container_t *)c2,
918 (run_container_t *)result);
919 // as of January 2016, Java code used non-in-place intersection for
920 // two runcontainers
921 return convert_run_to_efficient_container_and_free(
922 (run_container_t *)result, result_type);
923 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
924 ARRAY_CONTAINER_TYPE_CODE):
925 // c1 is a bitmap so no inplace possible
926 result = array_container_create();
927 array_bitset_container_intersection((const array_container_t *)c2,
928 (const bitset_container_t *)c1,
929 (array_container_t *)result);
930 *result_type = ARRAY_CONTAINER_TYPE_CODE; // never bitset
931 return result;
932 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
933 BITSET_CONTAINER_TYPE_CODE):
934 *result_type = ARRAY_CONTAINER_TYPE_CODE; // never bitset
935 array_bitset_container_intersection(
936 (const array_container_t *)c1, (const bitset_container_t *)c2,
937 (array_container_t *)c1); // allowed
938 return c1;
939
940 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
941 RUN_CONTAINER_TYPE_CODE):
942 // will attempt in-place computation
943 *result_type = run_bitset_container_intersection(
944 (const run_container_t *)c2,
945 (const bitset_container_t *)c1, &c1)
946 ? BITSET_CONTAINER_TYPE_CODE
947 : ARRAY_CONTAINER_TYPE_CODE;
948 return c1;
949 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE,
950 BITSET_CONTAINER_TYPE_CODE):
951 *result_type = run_bitset_container_intersection(
952 (const run_container_t *)c1,
953 (const bitset_container_t *)c2, &result)
954 ? BITSET_CONTAINER_TYPE_CODE
955 : ARRAY_CONTAINER_TYPE_CODE;
956 return result;
957 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
958 result = array_container_create();
959 *result_type = ARRAY_CONTAINER_TYPE_CODE; // never bitset
960 array_run_container_intersection((const array_container_t *)c1,
961 (const run_container_t *)c2,
962 (array_container_t *)result);
963 return result;
964
965 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, ARRAY_CONTAINER_TYPE_CODE):
966 result = array_container_create();
967 *result_type = ARRAY_CONTAINER_TYPE_CODE; // never bitset
968 array_run_container_intersection((const array_container_t *)c2,
969 (const run_container_t *)c1,
970 (array_container_t *)result);
971 return result;
972 default:
973 assert(false);
974 __builtin_unreachable();
975 return NULL;
976 }
977}
978
979/**
980 * Compute union between two containers, generate a new container (having type
981 * result_type), requires a typecode. This allocates new memory, caller
982 * is responsible for deallocation.
983 */
984static inline void *container_or(const void *c1, uint8_t type1, const void *c2,
985 uint8_t type2, uint8_t *result_type) {
986 c1 = container_unwrap_shared(c1, &type1);
987 c2 = container_unwrap_shared(c2, &type2);
988 void *result = NULL;
989 switch (CONTAINER_PAIR(type1, type2)) {
990 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
991 BITSET_CONTAINER_TYPE_CODE):
992 result = bitset_container_create();
993 bitset_container_or((const bitset_container_t *)c1,
994 (const bitset_container_t *)c2,
995 (bitset_container_t *)result);
996 *result_type = BITSET_CONTAINER_TYPE_CODE;
997 return result;
998 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
999 ARRAY_CONTAINER_TYPE_CODE):
1000 *result_type = array_array_container_union(
1001 (const array_container_t *)c1,
1002 (const array_container_t *)c2, &result)
1003 ? BITSET_CONTAINER_TYPE_CODE
1004 : ARRAY_CONTAINER_TYPE_CODE;
1005 return result;
1006 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1007 result = run_container_create();
1008 run_container_union((const run_container_t *)c1,
1009 (const run_container_t *)c2,
1010 (run_container_t *)result);
1011 *result_type = RUN_CONTAINER_TYPE_CODE;
1012 // todo: could be optimized since will never convert to array
1013 result = convert_run_to_efficient_container_and_free(
1014 (run_container_t *)result, (uint8_t *)result_type);
1015 return result;
1016 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1017 ARRAY_CONTAINER_TYPE_CODE):
1018 result = bitset_container_create();
1019 array_bitset_container_union((const array_container_t *)c2,
1020 (const bitset_container_t *)c1,
1021 (bitset_container_t *)result);
1022 *result_type = BITSET_CONTAINER_TYPE_CODE;
1023 return result;
1024 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1025 BITSET_CONTAINER_TYPE_CODE):
1026 result = bitset_container_create();
1027 array_bitset_container_union((const array_container_t *)c1,
1028 (const bitset_container_t *)c2,
1029 (bitset_container_t *)result);
1030 *result_type = BITSET_CONTAINER_TYPE_CODE;
1031 return result;
1032 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1033 RUN_CONTAINER_TYPE_CODE):
1034 if (run_container_is_full((const run_container_t *)c2)) {
1035 result = run_container_create();
1036 *result_type = RUN_CONTAINER_TYPE_CODE;
1037 run_container_copy((const run_container_t *)c2,
1038 (run_container_t *)result);
1039 return result;
1040 }
1041 result = bitset_container_create();
1042 run_bitset_container_union((const run_container_t *)c2,
1043 (const bitset_container_t *)c1,
1044 (bitset_container_t *)result);
1045 *result_type = BITSET_CONTAINER_TYPE_CODE;
1046 return result;
1047 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE,
1048 BITSET_CONTAINER_TYPE_CODE):
1049 if (run_container_is_full((const run_container_t *)c1)) {
1050 result = run_container_create();
1051 *result_type = RUN_CONTAINER_TYPE_CODE;
1052 run_container_copy((const run_container_t *)c1,
1053 (run_container_t *)result);
1054 return result;
1055 }
1056 result = bitset_container_create();
1057 run_bitset_container_union((const run_container_t *)c1,
1058 (const bitset_container_t *)c2,
1059 (bitset_container_t *)result);
1060 *result_type = BITSET_CONTAINER_TYPE_CODE;
1061 return result;
1062 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1063 result = run_container_create();
1064 array_run_container_union((const array_container_t *)c1,
1065 (const run_container_t *)c2,
1066 (run_container_t *)result);
1067 result = convert_run_to_efficient_container_and_free(
1068 (run_container_t *)result, (uint8_t *)result_type);
1069 return result;
1070 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, ARRAY_CONTAINER_TYPE_CODE):
1071 result = run_container_create();
1072 array_run_container_union((const array_container_t *)c2,
1073 (const run_container_t *)c1,
1074 (run_container_t *)result);
1075 result = convert_run_to_efficient_container_and_free(
1076 (run_container_t *)result, (uint8_t *)result_type);
1077 return result;
1078 default:
1079 assert(false);
1080 __builtin_unreachable();
1081 return NULL; // unreached
1082 }
1083}
1084
1085/**
1086 * Compute union between two containers, generate a new container (having type
1087 * result_type), requires a typecode. This allocates new memory, caller
1088 * is responsible for deallocation.
1089 *
1090 * This lazy version delays some operations such as the maintenance of the
1091 * cardinality. It requires repair later on the generated containers.
1092 */
1093static inline void *container_lazy_or(const void *c1, uint8_t type1,
1094 const void *c2, uint8_t type2,
1095 uint8_t *result_type) {
1096 c1 = container_unwrap_shared(c1, &type1);
1097 c2 = container_unwrap_shared(c2, &type2);
1098 void *result = NULL;
1099 switch (CONTAINER_PAIR(type1, type2)) {
1100 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1101 BITSET_CONTAINER_TYPE_CODE):
1102 result = bitset_container_create();
1103 bitset_container_or_nocard(
1104 (const bitset_container_t *)c1, (const bitset_container_t *)c2,
1105 (bitset_container_t *)result); // is lazy
1106 *result_type = BITSET_CONTAINER_TYPE_CODE;
1107 return result;
1108 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1109 ARRAY_CONTAINER_TYPE_CODE):
1110 *result_type = array_array_container_lazy_union(
1111 (const array_container_t *)c1,
1112 (const array_container_t *)c2, &result)
1113 ? BITSET_CONTAINER_TYPE_CODE
1114 : ARRAY_CONTAINER_TYPE_CODE;
1115 return result;
1116 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1117 result = run_container_create();
1118 run_container_union((const run_container_t *)c1,
1119 (const run_container_t *)c2,
1120 (run_container_t *)result);
1121 *result_type = RUN_CONTAINER_TYPE_CODE;
1122 // we are being lazy
1123 result = convert_run_to_efficient_container(
1124 (run_container_t *)result, result_type);
1125 return result;
1126 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1127 ARRAY_CONTAINER_TYPE_CODE):
1128 result = bitset_container_create();
1129 array_bitset_container_lazy_union(
1130 (const array_container_t *)c2, (const bitset_container_t *)c1,
1131 (bitset_container_t *)result); // is lazy
1132 *result_type = BITSET_CONTAINER_TYPE_CODE;
1133 return result;
1134 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1135 BITSET_CONTAINER_TYPE_CODE):
1136 result = bitset_container_create();
1137 array_bitset_container_lazy_union(
1138 (const array_container_t *)c1, (const bitset_container_t *)c2,
1139 (bitset_container_t *)result); // is lazy
1140 *result_type = BITSET_CONTAINER_TYPE_CODE;
1141 return result;
1142 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1143 RUN_CONTAINER_TYPE_CODE):
1144 if (run_container_is_full((const run_container_t *)c2)) {
1145 result = run_container_create();
1146 *result_type = RUN_CONTAINER_TYPE_CODE;
1147 run_container_copy((const run_container_t *)c2,
1148 (run_container_t *)result);
1149 return result;
1150 }
1151 result = bitset_container_create();
1152 run_bitset_container_lazy_union(
1153 (const run_container_t *)c2, (const bitset_container_t *)c1,
1154 (bitset_container_t *)result); // is lazy
1155 *result_type = BITSET_CONTAINER_TYPE_CODE;
1156 return result;
1157 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE,
1158 BITSET_CONTAINER_TYPE_CODE):
1159 if (run_container_is_full((const run_container_t *)c1)) {
1160 result = run_container_create();
1161 *result_type = RUN_CONTAINER_TYPE_CODE;
1162 run_container_copy((const run_container_t *)c1,
1163 (run_container_t *)result);
1164 return result;
1165 }
1166 result = bitset_container_create();
1167 run_bitset_container_lazy_union(
1168 (const run_container_t *)c1, (const bitset_container_t *)c2,
1169 (bitset_container_t *)result); // is lazy
1170 *result_type = BITSET_CONTAINER_TYPE_CODE;
1171 return result;
1172 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1173 result = run_container_create();
1174 array_run_container_union((const array_container_t *)c1,
1175 (const run_container_t *)c2,
1176 (run_container_t *)result);
1177 *result_type = RUN_CONTAINER_TYPE_CODE;
1178 // next line skipped since we are lazy
1179 // result = convert_run_to_efficient_container(result, result_type);
1180 return result;
1181 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, ARRAY_CONTAINER_TYPE_CODE):
1182 result = run_container_create();
1183 array_run_container_union(
1184 (const array_container_t *)c2, (const run_container_t *)c1,
1185 (run_container_t *)result); // TODO make lazy
1186 *result_type = RUN_CONTAINER_TYPE_CODE;
1187 // next line skipped since we are lazy
1188 // result = convert_run_to_efficient_container(result, result_type);
1189 return result;
1190 default:
1191 assert(false);
1192 __builtin_unreachable();
1193 return NULL; // unreached
1194 }
1195}
1196
1197/**
1198 * Compute the union between two containers, with result in the first container.
1199 * If the returned pointer is identical to c1, then the container has been
1200 * modified.
1201 * If the returned pointer is different from c1, then a new container has been
1202 * created and the caller is responsible for freeing it.
1203 * The type of the first container may change. Returns the modified
1204 * (and possibly new) container
1205*/
1206static inline void *container_ior(void *c1, uint8_t type1, const void *c2,
1207 uint8_t type2, uint8_t *result_type) {
1208 c1 = get_writable_copy_if_shared(c1, &type1);
1209 c2 = container_unwrap_shared(c2, &type2);
1210 void *result = NULL;
1211 switch (CONTAINER_PAIR(type1, type2)) {
1212 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1213 BITSET_CONTAINER_TYPE_CODE):
1214 bitset_container_or((const bitset_container_t *)c1,
1215 (const bitset_container_t *)c2,
1216 (bitset_container_t *)c1);
1217#ifdef OR_BITSET_CONVERSION_TO_FULL
1218 if (((bitset_container_t *)c1)->cardinality ==
1219 (1 << 16)) { // we convert
1220 result = run_container_create_range(0, (1 << 16));
1221 *result_type = RUN_CONTAINER_TYPE_CODE;
1222 return result;
1223 }
1224#endif
1225 *result_type = BITSET_CONTAINER_TYPE_CODE;
1226 return c1;
1227 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1228 ARRAY_CONTAINER_TYPE_CODE):
1229 *result_type = array_array_container_inplace_union(
1230 (array_container_t *)c1,
1231 (const array_container_t *)c2, &result)
1232 ? BITSET_CONTAINER_TYPE_CODE
1233 : ARRAY_CONTAINER_TYPE_CODE;
1234 if((result == NULL)
1235 && (*result_type == ARRAY_CONTAINER_TYPE_CODE)) {
1236 return c1; // the computation was done in-place!
1237 }
1238 return result;
1239 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1240 run_container_union_inplace((run_container_t *)c1,
1241 (const run_container_t *)c2);
1242 return convert_run_to_efficient_container((run_container_t *)c1,
1243 result_type);
1244 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1245 ARRAY_CONTAINER_TYPE_CODE):
1246 array_bitset_container_union((const array_container_t *)c2,
1247 (const bitset_container_t *)c1,
1248 (bitset_container_t *)c1);
1249 *result_type = BITSET_CONTAINER_TYPE_CODE; // never array
1250 return c1;
1251 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1252 BITSET_CONTAINER_TYPE_CODE):
1253 // c1 is an array, so no in-place possible
1254 result = bitset_container_create();
1255 *result_type = BITSET_CONTAINER_TYPE_CODE;
1256 array_bitset_container_union((const array_container_t *)c1,
1257 (const bitset_container_t *)c2,
1258 (bitset_container_t *)result);
1259 return result;
1260 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1261 RUN_CONTAINER_TYPE_CODE):
1262 if (run_container_is_full((const run_container_t *)c2)) {
1263 result = run_container_create();
1264 *result_type = RUN_CONTAINER_TYPE_CODE;
1265 run_container_copy((const run_container_t *)c2,
1266 (run_container_t *)result);
1267 return result;
1268 }
1269 run_bitset_container_union((const run_container_t *)c2,
1270 (const bitset_container_t *)c1,
1271 (bitset_container_t *)c1); // allowed
1272 *result_type = BITSET_CONTAINER_TYPE_CODE;
1273 return c1;
1274 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE,
1275 BITSET_CONTAINER_TYPE_CODE):
1276 if (run_container_is_full((const run_container_t *)c1)) {
1277 *result_type = RUN_CONTAINER_TYPE_CODE;
1278
1279 return c1;
1280 }
1281 result = bitset_container_create();
1282 run_bitset_container_union((const run_container_t *)c1,
1283 (const bitset_container_t *)c2,
1284 (bitset_container_t *)result);
1285 *result_type = BITSET_CONTAINER_TYPE_CODE;
1286 return result;
1287 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1288 result = run_container_create();
1289 array_run_container_union((const array_container_t *)c1,
1290 (const run_container_t *)c2,
1291 (run_container_t *)result);
1292 result = convert_run_to_efficient_container_and_free(
1293 (run_container_t *)result, result_type);
1294 return result;
1295 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, ARRAY_CONTAINER_TYPE_CODE):
1296 array_run_container_inplace_union((const array_container_t *)c2,
1297 (run_container_t *)c1);
1298 c1 = convert_run_to_efficient_container((run_container_t *)c1,
1299 result_type);
1300 return c1;
1301 default:
1302 assert(false);
1303 __builtin_unreachable();
1304 return NULL;
1305 }
1306}
1307
1308/**
1309 * Compute the union between two containers, with result in the first container.
1310 * If the returned pointer is identical to c1, then the container has been
1311 * modified.
1312 * If the returned pointer is different from c1, then a new container has been
1313 * created and the caller is responsible for freeing it.
1314 * The type of the first container may change. Returns the modified
1315 * (and possibly new) container
1316 *
1317 * This lazy version delays some operations such as the maintenance of the
1318 * cardinality. It requires repair later on the generated containers.
1319*/
1320static inline void *container_lazy_ior(void *c1, uint8_t type1, const void *c2,
1321 uint8_t type2, uint8_t *result_type) {
1322 assert(type1 != SHARED_CONTAINER_TYPE_CODE);
1323 // c1 = get_writable_copy_if_shared(c1,&type1);
1324 c2 = container_unwrap_shared(c2, &type2);
1325 void *result = NULL;
1326 switch (CONTAINER_PAIR(type1, type2)) {
1327 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1328 BITSET_CONTAINER_TYPE_CODE):
1329#ifdef LAZY_OR_BITSET_CONVERSION_TO_FULL
1330 // if we have two bitsets, we might as well compute the cardinality
1331 bitset_container_or((const bitset_container_t *)c1,
1332 (const bitset_container_t *)c2,
1333 (bitset_container_t *)c1);
1334 // it is possible that two bitsets can lead to a full container
1335 if (((bitset_container_t *)c1)->cardinality ==
1336 (1 << 16)) { // we convert
1337 result = run_container_create_range(0, (1 << 16));
1338 *result_type = RUN_CONTAINER_TYPE_CODE;
1339 return result;
1340 }
1341#else
1342 bitset_container_or_nocard((const bitset_container_t *)c1,
1343 (const bitset_container_t *)c2,
1344 (bitset_container_t *)c1);
1345
1346#endif
1347 *result_type = BITSET_CONTAINER_TYPE_CODE;
1348 return c1;
1349 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1350 ARRAY_CONTAINER_TYPE_CODE):
1351 *result_type = array_array_container_lazy_inplace_union(
1352 (array_container_t *)c1,
1353 (const array_container_t *)c2, &result)
1354 ? BITSET_CONTAINER_TYPE_CODE
1355 : ARRAY_CONTAINER_TYPE_CODE;
1356 if((result == NULL)
1357 && (*result_type == ARRAY_CONTAINER_TYPE_CODE)) {
1358 return c1; // the computation was done in-place!
1359 }
1360 return result;
1361 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1362 run_container_union_inplace((run_container_t *)c1,
1363 (const run_container_t *)c2);
1364 *result_type = RUN_CONTAINER_TYPE_CODE;
1365 return convert_run_to_efficient_container((run_container_t *)c1,
1366 result_type);
1367 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1368 ARRAY_CONTAINER_TYPE_CODE):
1369 array_bitset_container_lazy_union(
1370 (const array_container_t *)c2, (const bitset_container_t *)c1,
1371 (bitset_container_t *)c1); // is lazy
1372 *result_type = BITSET_CONTAINER_TYPE_CODE; // never array
1373 return c1;
1374 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1375 BITSET_CONTAINER_TYPE_CODE):
1376 // c1 is an array, so no in-place possible
1377 result = bitset_container_create();
1378 *result_type = BITSET_CONTAINER_TYPE_CODE;
1379 array_bitset_container_lazy_union(
1380 (const array_container_t *)c1, (const bitset_container_t *)c2,
1381 (bitset_container_t *)result); // is lazy
1382 return result;
1383 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1384 RUN_CONTAINER_TYPE_CODE):
1385 if (run_container_is_full((const run_container_t *)c2)) {
1386 result = run_container_create();
1387 *result_type = RUN_CONTAINER_TYPE_CODE;
1388 run_container_copy((const run_container_t *)c2,
1389 (run_container_t *)result);
1390 return result;
1391 }
1392 run_bitset_container_lazy_union(
1393 (const run_container_t *)c2, (const bitset_container_t *)c1,
1394 (bitset_container_t *)c1); // allowed // lazy
1395 *result_type = BITSET_CONTAINER_TYPE_CODE;
1396 return c1;
1397 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE,
1398 BITSET_CONTAINER_TYPE_CODE):
1399 if (run_container_is_full((const run_container_t *)c1)) {
1400 *result_type = RUN_CONTAINER_TYPE_CODE;
1401 return c1;
1402 }
1403 result = bitset_container_create();
1404 run_bitset_container_lazy_union(
1405 (const run_container_t *)c1, (const bitset_container_t *)c2,
1406 (bitset_container_t *)result); // lazy
1407 *result_type = BITSET_CONTAINER_TYPE_CODE;
1408 return result;
1409 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1410 result = run_container_create();
1411 array_run_container_union((const array_container_t *)c1,
1412 (const run_container_t *)c2,
1413 (run_container_t *)result);
1414 *result_type = RUN_CONTAINER_TYPE_CODE;
1415 // next line skipped since we are lazy
1416 // result = convert_run_to_efficient_container_and_free(result,
1417 // result_type);
1418 return result;
1419 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, ARRAY_CONTAINER_TYPE_CODE):
1420 array_run_container_inplace_union((const array_container_t *)c2,
1421 (run_container_t *)c1);
1422 *result_type = RUN_CONTAINER_TYPE_CODE;
1423 // next line skipped since we are lazy
1424 // result = convert_run_to_efficient_container_and_free(result,
1425 // result_type);
1426 return c1;
1427 default:
1428 assert(false);
1429 __builtin_unreachable();
1430 return NULL;
1431 }
1432}
1433
1434/**
1435 * Compute symmetric difference (xor) between two containers, generate a new
1436 * container (having type result_type), requires a typecode. This allocates new
1437 * memory, caller is responsible for deallocation.
1438 */
1439static inline void *container_xor(const void *c1, uint8_t type1, const void *c2,
1440 uint8_t type2, uint8_t *result_type) {
1441 c1 = container_unwrap_shared(c1, &type1);
1442 c2 = container_unwrap_shared(c2, &type2);
1443 void *result = NULL;
1444 switch (CONTAINER_PAIR(type1, type2)) {
1445 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1446 BITSET_CONTAINER_TYPE_CODE):
1447 *result_type = bitset_bitset_container_xor(
1448 (const bitset_container_t *)c1,
1449 (const bitset_container_t *)c2, &result)
1450 ? BITSET_CONTAINER_TYPE_CODE
1451 : ARRAY_CONTAINER_TYPE_CODE;
1452 return result;
1453 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1454 ARRAY_CONTAINER_TYPE_CODE):
1455 *result_type = array_array_container_xor(
1456 (const array_container_t *)c1,
1457 (const array_container_t *)c2, &result)
1458 ? BITSET_CONTAINER_TYPE_CODE
1459 : ARRAY_CONTAINER_TYPE_CODE;
1460 return result;
1461 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1462 *result_type =
1463 run_run_container_xor((const run_container_t *)c1,
1464 (const run_container_t *)c2, &result);
1465 return result;
1466
1467 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1468 ARRAY_CONTAINER_TYPE_CODE):
1469 *result_type = array_bitset_container_xor(
1470 (const array_container_t *)c2,
1471 (const bitset_container_t *)c1, &result)
1472 ? BITSET_CONTAINER_TYPE_CODE
1473 : ARRAY_CONTAINER_TYPE_CODE;
1474 return result;
1475 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1476 BITSET_CONTAINER_TYPE_CODE):
1477 *result_type = array_bitset_container_xor(
1478 (const array_container_t *)c1,
1479 (const bitset_container_t *)c2, &result)
1480 ? BITSET_CONTAINER_TYPE_CODE
1481 : ARRAY_CONTAINER_TYPE_CODE;
1482 return result;
1483 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1484 RUN_CONTAINER_TYPE_CODE):
1485 *result_type = run_bitset_container_xor(
1486 (const run_container_t *)c2,
1487 (const bitset_container_t *)c1, &result)
1488 ? BITSET_CONTAINER_TYPE_CODE
1489 : ARRAY_CONTAINER_TYPE_CODE;
1490 return result;
1491
1492 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE,
1493 BITSET_CONTAINER_TYPE_CODE):
1494
1495 *result_type = run_bitset_container_xor(
1496 (const run_container_t *)c1,
1497 (const bitset_container_t *)c2, &result)
1498 ? BITSET_CONTAINER_TYPE_CODE
1499 : ARRAY_CONTAINER_TYPE_CODE;
1500 return result;
1501
1502 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1503 *result_type =
1504 array_run_container_xor((const array_container_t *)c1,
1505 (const run_container_t *)c2, &result);
1506 return result;
1507
1508 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, ARRAY_CONTAINER_TYPE_CODE):
1509 *result_type =
1510 array_run_container_xor((const array_container_t *)c2,
1511 (const run_container_t *)c1, &result);
1512 return result;
1513
1514 default:
1515 assert(false);
1516 __builtin_unreachable();
1517 return NULL; // unreached
1518 }
1519}
1520
1521/**
1522 * Compute xor between two containers, generate a new container (having type
1523 * result_type), requires a typecode. This allocates new memory, caller
1524 * is responsible for deallocation.
1525 *
1526 * This lazy version delays some operations such as the maintenance of the
1527 * cardinality. It requires repair later on the generated containers.
1528 */
1529static inline void *container_lazy_xor(const void *c1, uint8_t type1,
1530 const void *c2, uint8_t type2,
1531 uint8_t *result_type) {
1532 c1 = container_unwrap_shared(c1, &type1);
1533 c2 = container_unwrap_shared(c2, &type2);
1534 void *result = NULL;
1535 switch (CONTAINER_PAIR(type1, type2)) {
1536 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1537 BITSET_CONTAINER_TYPE_CODE):
1538 result = bitset_container_create();
1539 bitset_container_xor_nocard(
1540 (const bitset_container_t *)c1, (const bitset_container_t *)c2,
1541 (bitset_container_t *)result); // is lazy
1542 *result_type = BITSET_CONTAINER_TYPE_CODE;
1543 return result;
1544 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1545 ARRAY_CONTAINER_TYPE_CODE):
1546 *result_type = array_array_container_lazy_xor(
1547 (const array_container_t *)c1,
1548 (const array_container_t *)c2, &result)
1549 ? BITSET_CONTAINER_TYPE_CODE
1550 : ARRAY_CONTAINER_TYPE_CODE;
1551 return result;
1552 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1553 // nothing special done yet.
1554 *result_type =
1555 run_run_container_xor((const run_container_t *)c1,
1556 (const run_container_t *)c2, &result);
1557 return result;
1558 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1559 ARRAY_CONTAINER_TYPE_CODE):
1560 result = bitset_container_create();
1561 *result_type = BITSET_CONTAINER_TYPE_CODE;
1562 array_bitset_container_lazy_xor((const array_container_t *)c2,
1563 (const bitset_container_t *)c1,
1564 (bitset_container_t *)result);
1565 return result;
1566 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1567 BITSET_CONTAINER_TYPE_CODE):
1568 result = bitset_container_create();
1569 *result_type = BITSET_CONTAINER_TYPE_CODE;
1570 array_bitset_container_lazy_xor((const array_container_t *)c1,
1571 (const bitset_container_t *)c2,
1572 (bitset_container_t *)result);
1573 return result;
1574 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1575 RUN_CONTAINER_TYPE_CODE):
1576 result = bitset_container_create();
1577 run_bitset_container_lazy_xor((const run_container_t *)c2,
1578 (const bitset_container_t *)c1,
1579 (bitset_container_t *)result);
1580 *result_type = BITSET_CONTAINER_TYPE_CODE;
1581 return result;
1582 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE,
1583 BITSET_CONTAINER_TYPE_CODE):
1584 result = bitset_container_create();
1585 run_bitset_container_lazy_xor((const run_container_t *)c1,
1586 (const bitset_container_t *)c2,
1587 (bitset_container_t *)result);
1588 *result_type = BITSET_CONTAINER_TYPE_CODE;
1589 return result;
1590
1591 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1592 result = run_container_create();
1593 array_run_container_lazy_xor((const array_container_t *)c1,
1594 (const run_container_t *)c2,
1595 (run_container_t *)result);
1596 *result_type = RUN_CONTAINER_TYPE_CODE;
1597 // next line skipped since we are lazy
1598 // result = convert_run_to_efficient_container(result, result_type);
1599 return result;
1600 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, ARRAY_CONTAINER_TYPE_CODE):
1601 result = run_container_create();
1602 array_run_container_lazy_xor((const array_container_t *)c2,
1603 (const run_container_t *)c1,
1604 (run_container_t *)result);
1605 *result_type = RUN_CONTAINER_TYPE_CODE;
1606 // next line skipped since we are lazy
1607 // result = convert_run_to_efficient_container(result, result_type);
1608 return result;
1609 default:
1610 assert(false);
1611 __builtin_unreachable();
1612 return NULL; // unreached
1613 }
1614}
1615
1616/**
1617 * Compute the xor between two containers, with result in the first container.
1618 * If the returned pointer is identical to c1, then the container has been
1619 * modified.
1620 * If the returned pointer is different from c1, then a new container has been
1621 * created and the caller is responsible for freeing it.
1622 * The type of the first container may change. Returns the modified
1623 * (and possibly new) container
1624*/
1625static inline void *container_ixor(void *c1, uint8_t type1, const void *c2,
1626 uint8_t type2, uint8_t *result_type) {
1627 c1 = get_writable_copy_if_shared(c1, &type1);
1628 c2 = container_unwrap_shared(c2, &type2);
1629 void *result = NULL;
1630 switch (CONTAINER_PAIR(type1, type2)) {
1631 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1632 BITSET_CONTAINER_TYPE_CODE):
1633 *result_type = bitset_bitset_container_ixor(
1634 (bitset_container_t *)c1,
1635 (const bitset_container_t *)c2, &result)
1636 ? BITSET_CONTAINER_TYPE_CODE
1637 : ARRAY_CONTAINER_TYPE_CODE;
1638 return result;
1639 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1640 ARRAY_CONTAINER_TYPE_CODE):
1641 *result_type = array_array_container_ixor(
1642 (array_container_t *)c1,
1643 (const array_container_t *)c2, &result)
1644 ? BITSET_CONTAINER_TYPE_CODE
1645 : ARRAY_CONTAINER_TYPE_CODE;
1646 return result;
1647
1648 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1649 *result_type = run_run_container_ixor(
1650 (run_container_t *)c1, (const run_container_t *)c2, &result);
1651 return result;
1652
1653 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1654 ARRAY_CONTAINER_TYPE_CODE):
1655 *result_type = bitset_array_container_ixor(
1656 (bitset_container_t *)c1,
1657 (const array_container_t *)c2, &result)
1658 ? BITSET_CONTAINER_TYPE_CODE
1659 : ARRAY_CONTAINER_TYPE_CODE;
1660 return result;
1661 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1662 BITSET_CONTAINER_TYPE_CODE):
1663 *result_type = array_bitset_container_ixor(
1664 (array_container_t *)c1,
1665 (const bitset_container_t *)c2, &result)
1666 ? BITSET_CONTAINER_TYPE_CODE
1667 : ARRAY_CONTAINER_TYPE_CODE;
1668
1669 return result;
1670
1671 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1672 RUN_CONTAINER_TYPE_CODE):
1673 *result_type =
1674 bitset_run_container_ixor((bitset_container_t *)c1,
1675 (const run_container_t *)c2, &result)
1676 ? BITSET_CONTAINER_TYPE_CODE
1677 : ARRAY_CONTAINER_TYPE_CODE;
1678
1679 return result;
1680
1681 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE,
1682 BITSET_CONTAINER_TYPE_CODE):
1683 *result_type = run_bitset_container_ixor(
1684 (run_container_t *)c1,
1685 (const bitset_container_t *)c2, &result)
1686 ? BITSET_CONTAINER_TYPE_CODE
1687 : ARRAY_CONTAINER_TYPE_CODE;
1688
1689 return result;
1690
1691 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1692 *result_type = array_run_container_ixor(
1693 (array_container_t *)c1, (const run_container_t *)c2, &result);
1694 return result;
1695 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, ARRAY_CONTAINER_TYPE_CODE):
1696 *result_type = run_array_container_ixor(
1697 (run_container_t *)c1, (const array_container_t *)c2, &result);
1698 return result;
1699 default:
1700 assert(false);
1701 __builtin_unreachable();
1702 return NULL;
1703 }
1704}
1705
1706/**
1707 * Compute the xor between two containers, with result in the first container.
1708 * If the returned pointer is identical to c1, then the container has been
1709 * modified.
1710 * If the returned pointer is different from c1, then a new container has been
1711 * created and the caller is responsible for freeing it.
1712 * The type of the first container may change. Returns the modified
1713 * (and possibly new) container
1714 *
1715 * This lazy version delays some operations such as the maintenance of the
1716 * cardinality. It requires repair later on the generated containers.
1717*/
1718static inline void *container_lazy_ixor(void *c1, uint8_t type1, const void *c2,
1719 uint8_t type2, uint8_t *result_type) {
1720 assert(type1 != SHARED_CONTAINER_TYPE_CODE);
1721 // c1 = get_writable_copy_if_shared(c1,&type1);
1722 c2 = container_unwrap_shared(c2, &type2);
1723 switch (CONTAINER_PAIR(type1, type2)) {
1724 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1725 BITSET_CONTAINER_TYPE_CODE):
1726 bitset_container_xor_nocard((bitset_container_t *)c1,
1727 (const bitset_container_t *)c2,
1728 (bitset_container_t *)c1); // is lazy
1729 *result_type = BITSET_CONTAINER_TYPE_CODE;
1730 return c1;
1731 // TODO: other cases being lazy, esp. when we know inplace not likely
1732 // could see the corresponding code for union
1733 default:
1734 // we may have a dirty bitset (without a precomputed cardinality) and
1735 // calling container_ixor on it might be unsafe.
1736 if( (type1 == BITSET_CONTAINER_TYPE_CODE)
1737 && (((const bitset_container_t *)c1)->cardinality == BITSET_UNKNOWN_CARDINALITY)) {
1738 ((bitset_container_t *)c1)->cardinality = bitset_container_compute_cardinality((bitset_container_t *)c1);
1739 }
1740 return container_ixor(c1, type1, c2, type2, result_type);
1741 }
1742}
1743
1744/**
1745 * Compute difference (andnot) between two containers, generate a new
1746 * container (having type result_type), requires a typecode. This allocates new
1747 * memory, caller is responsible for deallocation.
1748 */
1749static inline void *container_andnot(const void *c1, uint8_t type1,
1750 const void *c2, uint8_t type2,
1751 uint8_t *result_type) {
1752 c1 = container_unwrap_shared(c1, &type1);
1753 c2 = container_unwrap_shared(c2, &type2);
1754 void *result = NULL;
1755 switch (CONTAINER_PAIR(type1, type2)) {
1756 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1757 BITSET_CONTAINER_TYPE_CODE):
1758 *result_type = bitset_bitset_container_andnot(
1759 (const bitset_container_t *)c1,
1760 (const bitset_container_t *)c2, &result)
1761 ? BITSET_CONTAINER_TYPE_CODE
1762 : ARRAY_CONTAINER_TYPE_CODE;
1763 return result;
1764 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1765 ARRAY_CONTAINER_TYPE_CODE):
1766 result = array_container_create();
1767 array_array_container_andnot((const array_container_t *)c1,
1768 (const array_container_t *)c2,
1769 (array_container_t *)result);
1770 *result_type = ARRAY_CONTAINER_TYPE_CODE;
1771 return result;
1772 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1773 if (run_container_is_full((const run_container_t *)c2)) {
1774 result = array_container_create();
1775 *result_type = ARRAY_CONTAINER_TYPE_CODE;
1776 return result;
1777 }
1778 *result_type =
1779 run_run_container_andnot((const run_container_t *)c1,
1780 (const run_container_t *)c2, &result);
1781 return result;
1782
1783 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1784 ARRAY_CONTAINER_TYPE_CODE):
1785 *result_type = bitset_array_container_andnot(
1786 (const bitset_container_t *)c1,
1787 (const array_container_t *)c2, &result)
1788 ? BITSET_CONTAINER_TYPE_CODE
1789 : ARRAY_CONTAINER_TYPE_CODE;
1790 return result;
1791 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1792 BITSET_CONTAINER_TYPE_CODE):
1793 result = array_container_create();
1794 array_bitset_container_andnot((const array_container_t *)c1,
1795 (const bitset_container_t *)c2,
1796 (array_container_t *)result);
1797 *result_type = ARRAY_CONTAINER_TYPE_CODE;
1798 return result;
1799 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1800 RUN_CONTAINER_TYPE_CODE):
1801 if (run_container_is_full((const run_container_t *)c2)) {
1802 result = array_container_create();
1803 *result_type = ARRAY_CONTAINER_TYPE_CODE;
1804 return result;
1805 }
1806 *result_type = bitset_run_container_andnot(
1807 (const bitset_container_t *)c1,
1808 (const run_container_t *)c2, &result)
1809 ? BITSET_CONTAINER_TYPE_CODE
1810 : ARRAY_CONTAINER_TYPE_CODE;
1811 return result;
1812 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE,
1813 BITSET_CONTAINER_TYPE_CODE):
1814
1815 *result_type = run_bitset_container_andnot(
1816 (const run_container_t *)c1,
1817 (const bitset_container_t *)c2, &result)
1818 ? BITSET_CONTAINER_TYPE_CODE
1819 : ARRAY_CONTAINER_TYPE_CODE;
1820 return result;
1821
1822 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1823 if (run_container_is_full((const run_container_t *)c2)) {
1824 result = array_container_create();
1825 *result_type = ARRAY_CONTAINER_TYPE_CODE;
1826 return result;
1827 }
1828 result = array_container_create();
1829 array_run_container_andnot((const array_container_t *)c1,
1830 (const run_container_t *)c2,
1831 (array_container_t *)result);
1832 *result_type = ARRAY_CONTAINER_TYPE_CODE;
1833 return result;
1834
1835 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, ARRAY_CONTAINER_TYPE_CODE):
1836 *result_type = run_array_container_andnot(
1837 (const run_container_t *)c1, (const array_container_t *)c2,
1838 &result);
1839 return result;
1840
1841 default:
1842 assert(false);
1843 __builtin_unreachable();
1844 return NULL; // unreached
1845 }
1846}
1847
1848/**
1849 * Compute the andnot between two containers, with result in the first
1850 * container.
1851 * If the returned pointer is identical to c1, then the container has been
1852 * modified.
1853 * If the returned pointer is different from c1, then a new container has been
1854 * created and the caller is responsible for freeing it.
1855 * The type of the first container may change. Returns the modified
1856 * (and possibly new) container
1857*/
1858static inline void *container_iandnot(void *c1, uint8_t type1, const void *c2,
1859 uint8_t type2, uint8_t *result_type) {
1860 c1 = get_writable_copy_if_shared(c1, &type1);
1861 c2 = container_unwrap_shared(c2, &type2);
1862 void *result = NULL;
1863 switch (CONTAINER_PAIR(type1, type2)) {
1864 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1865 BITSET_CONTAINER_TYPE_CODE):
1866 *result_type = bitset_bitset_container_iandnot(
1867 (bitset_container_t *)c1,
1868 (const bitset_container_t *)c2, &result)
1869 ? BITSET_CONTAINER_TYPE_CODE
1870 : ARRAY_CONTAINER_TYPE_CODE;
1871 return result;
1872 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1873 ARRAY_CONTAINER_TYPE_CODE):
1874 array_array_container_iandnot((array_container_t *)c1,
1875 (const array_container_t *)c2);
1876 *result_type = ARRAY_CONTAINER_TYPE_CODE;
1877 return c1;
1878
1879 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1880 *result_type = run_run_container_iandnot(
1881 (run_container_t *)c1, (const run_container_t *)c2, &result);
1882 return result;
1883
1884 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1885 ARRAY_CONTAINER_TYPE_CODE):
1886 *result_type = bitset_array_container_iandnot(
1887 (bitset_container_t *)c1,
1888 (const array_container_t *)c2, &result)
1889 ? BITSET_CONTAINER_TYPE_CODE
1890 : ARRAY_CONTAINER_TYPE_CODE;
1891 return result;
1892 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE,
1893 BITSET_CONTAINER_TYPE_CODE):
1894 *result_type = ARRAY_CONTAINER_TYPE_CODE;
1895
1896 array_bitset_container_iandnot((array_container_t *)c1,
1897 (const bitset_container_t *)c2);
1898 return c1;
1899
1900 case CONTAINER_PAIR(BITSET_CONTAINER_TYPE_CODE,
1901 RUN_CONTAINER_TYPE_CODE):
1902 *result_type = bitset_run_container_iandnot(
1903 (bitset_container_t *)c1,
1904 (const run_container_t *)c2, &result)
1905 ? BITSET_CONTAINER_TYPE_CODE
1906 : ARRAY_CONTAINER_TYPE_CODE;
1907
1908 return result;
1909
1910 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE,
1911 BITSET_CONTAINER_TYPE_CODE):
1912 *result_type = run_bitset_container_iandnot(
1913 (run_container_t *)c1,
1914 (const bitset_container_t *)c2, &result)
1915 ? BITSET_CONTAINER_TYPE_CODE
1916 : ARRAY_CONTAINER_TYPE_CODE;
1917
1918 return result;
1919
1920 case CONTAINER_PAIR(ARRAY_CONTAINER_TYPE_CODE, RUN_CONTAINER_TYPE_CODE):
1921 *result_type = ARRAY_CONTAINER_TYPE_CODE;
1922 array_run_container_iandnot((array_container_t *)c1,
1923 (const run_container_t *)c2);
1924 return c1;
1925 case CONTAINER_PAIR(RUN_CONTAINER_TYPE_CODE, ARRAY_CONTAINER_TYPE_CODE):
1926 *result_type = run_array_container_iandnot(
1927 (run_container_t *)c1, (const array_container_t *)c2, &result);
1928 return result;
1929 default:
1930 assert(false);
1931 __builtin_unreachable();
1932 return NULL;
1933 }
1934}
1935
1936/**
1937 * Visit all values x of the container once, passing (base+x,ptr)
1938 * to iterator. You need to specify a container and its type.
1939 * Returns true if the iteration should continue.
1940 */
1941static inline bool container_iterate(const void *container, uint8_t typecode,
1942 uint32_t base, roaring_iterator iterator,
1943 void *ptr) {
1944 container = container_unwrap_shared(container, &typecode);
1945 switch (typecode) {
1946 case BITSET_CONTAINER_TYPE_CODE:
1947 return bitset_container_iterate(
1948 (const bitset_container_t *)container, base, iterator, ptr);
1949 case ARRAY_CONTAINER_TYPE_CODE:
1950 return array_container_iterate((const array_container_t *)container,
1951 base, iterator, ptr);
1952 case RUN_CONTAINER_TYPE_CODE:
1953 return run_container_iterate((const run_container_t *)container,
1954 base, iterator, ptr);
1955 default:
1956 assert(false);
1957 __builtin_unreachable();
1958 }
1959 assert(false);
1960 __builtin_unreachable();
1961 return false;
1962}
1963
1964static inline bool container_iterate64(const void *container, uint8_t typecode,
1965 uint32_t base,
1966 roaring_iterator64 iterator,
1967 uint64_t high_bits, void *ptr) {
1968 container = container_unwrap_shared(container, &typecode);
1969 switch (typecode) {
1970 case BITSET_CONTAINER_TYPE_CODE:
1971 return bitset_container_iterate64(
1972 (const bitset_container_t *)container, base, iterator,
1973 high_bits, ptr);
1974 case ARRAY_CONTAINER_TYPE_CODE:
1975 return array_container_iterate64(
1976 (const array_container_t *)container, base, iterator, high_bits,
1977 ptr);
1978 case RUN_CONTAINER_TYPE_CODE:
1979 return run_container_iterate64((const run_container_t *)container,
1980 base, iterator, high_bits, ptr);
1981 default:
1982 assert(false);
1983 __builtin_unreachable();
1984 }
1985 assert(false);
1986 __builtin_unreachable();
1987 return false;
1988}
1989
1990static inline void *container_not(const void *c, uint8_t typ,
1991 uint8_t *result_type) {
1992 c = container_unwrap_shared(c, &typ);
1993 void *result = NULL;
1994 switch (typ) {
1995 case BITSET_CONTAINER_TYPE_CODE:
1996 *result_type = bitset_container_negation(
1997 (const bitset_container_t *)c, &result)
1998 ? BITSET_CONTAINER_TYPE_CODE
1999 : ARRAY_CONTAINER_TYPE_CODE;
2000 return result;
2001 case ARRAY_CONTAINER_TYPE_CODE:
2002 result = bitset_container_create();
2003 *result_type = BITSET_CONTAINER_TYPE_CODE;
2004 array_container_negation((const array_container_t *)c,
2005 (bitset_container_t *)result);
2006 return result;
2007 case RUN_CONTAINER_TYPE_CODE:
2008 *result_type =
2009 run_container_negation((const run_container_t *)c, &result);
2010 return result;
2011
2012 default:
2013 assert(false);
2014 __builtin_unreachable();
2015 }
2016 assert(false);
2017 __builtin_unreachable();
2018 return NULL;
2019}
2020
2021static inline void *container_not_range(const void *c, uint8_t typ,
2022 uint32_t range_start,
2023 uint32_t range_end,
2024 uint8_t *result_type) {
2025 c = container_unwrap_shared(c, &typ);
2026 void *result = NULL;
2027 switch (typ) {
2028 case BITSET_CONTAINER_TYPE_CODE:
2029 *result_type =
2030 bitset_container_negation_range((const bitset_container_t *)c,
2031 range_start, range_end, &result)
2032 ? BITSET_CONTAINER_TYPE_CODE
2033 : ARRAY_CONTAINER_TYPE_CODE;
2034 return result;
2035 case ARRAY_CONTAINER_TYPE_CODE:
2036 *result_type =
2037 array_container_negation_range((const array_container_t *)c,
2038 range_start, range_end, &result)
2039 ? BITSET_CONTAINER_TYPE_CODE
2040 : ARRAY_CONTAINER_TYPE_CODE;
2041 return result;
2042 case RUN_CONTAINER_TYPE_CODE:
2043 *result_type = run_container_negation_range(
2044 (const run_container_t *)c, range_start, range_end, &result);
2045 return result;
2046
2047 default:
2048 assert(false);
2049 __builtin_unreachable();
2050 }
2051 assert(false);
2052 __builtin_unreachable();
2053 return NULL;
2054}
2055
2056static inline void *container_inot(void *c, uint8_t typ, uint8_t *result_type) {
2057 c = get_writable_copy_if_shared(c, &typ);
2058 void *result = NULL;
2059 switch (typ) {
2060 case BITSET_CONTAINER_TYPE_CODE:
2061 *result_type = bitset_container_negation_inplace(
2062 (bitset_container_t *)c, &result)
2063 ? BITSET_CONTAINER_TYPE_CODE
2064 : ARRAY_CONTAINER_TYPE_CODE;
2065 return result;
2066 case ARRAY_CONTAINER_TYPE_CODE:
2067 // will never be inplace
2068 result = bitset_container_create();
2069 *result_type = BITSET_CONTAINER_TYPE_CODE;
2070 array_container_negation((array_container_t *)c,
2071 (bitset_container_t *)result);
2072 array_container_free((array_container_t *)c);
2073 return result;
2074 case RUN_CONTAINER_TYPE_CODE:
2075 *result_type =
2076 run_container_negation_inplace((run_container_t *)c, &result);
2077 return result;
2078
2079 default:
2080 assert(false);
2081 __builtin_unreachable();
2082 }
2083 assert(false);
2084 __builtin_unreachable();
2085 return NULL;
2086}
2087
2088static inline void *container_inot_range(void *c, uint8_t typ,
2089 uint32_t range_start,
2090 uint32_t range_end,
2091 uint8_t *result_type) {
2092 c = get_writable_copy_if_shared(c, &typ);
2093 void *result = NULL;
2094 switch (typ) {
2095 case BITSET_CONTAINER_TYPE_CODE:
2096 *result_type =
2097 bitset_container_negation_range_inplace(
2098 (bitset_container_t *)c, range_start, range_end, &result)
2099 ? BITSET_CONTAINER_TYPE_CODE
2100 : ARRAY_CONTAINER_TYPE_CODE;
2101 return result;
2102 case ARRAY_CONTAINER_TYPE_CODE:
2103 *result_type =
2104 array_container_negation_range_inplace(
2105 (array_container_t *)c, range_start, range_end, &result)
2106 ? BITSET_CONTAINER_TYPE_CODE
2107 : ARRAY_CONTAINER_TYPE_CODE;
2108 return result;
2109 case RUN_CONTAINER_TYPE_CODE:
2110 *result_type = run_container_negation_range_inplace(
2111 (run_container_t *)c, range_start, range_end, &result);
2112 return result;
2113
2114 default:
2115 assert(false);
2116 __builtin_unreachable();
2117 }
2118 assert(false);
2119 __builtin_unreachable();
2120 return NULL;
2121}
2122
2123/**
2124 * If the element of given rank is in this container, supposing that
2125 * the first
2126 * element has rank start_rank, then the function returns true and
2127 * sets element
2128 * accordingly.
2129 * Otherwise, it returns false and update start_rank.
2130 */
2131static inline bool container_select(const void *container, uint8_t typecode,
2132 uint32_t *start_rank, uint32_t rank,
2133 uint32_t *element) {
2134 container = container_unwrap_shared(container, &typecode);
2135 switch (typecode) {
2136 case BITSET_CONTAINER_TYPE_CODE:
2137 return bitset_container_select((const bitset_container_t *)container,
2138 start_rank, rank, element);
2139 case ARRAY_CONTAINER_TYPE_CODE:
2140 return array_container_select((const array_container_t *)container,
2141 start_rank, rank, element);
2142 case RUN_CONTAINER_TYPE_CODE:
2143 return run_container_select((const run_container_t *)container,
2144 start_rank, rank, element);
2145 default:
2146 assert(false);
2147 __builtin_unreachable();
2148 }
2149 assert(false);
2150 __builtin_unreachable();
2151 return false;
2152}
2153
2154static inline uint16_t container_maximum(const void *container,
2155 uint8_t typecode) {
2156 container = container_unwrap_shared(container, &typecode);
2157 switch (typecode) {
2158 case BITSET_CONTAINER_TYPE_CODE:
2159 return bitset_container_maximum((const bitset_container_t *)container);
2160 case ARRAY_CONTAINER_TYPE_CODE:
2161 return array_container_maximum((const array_container_t *)container);
2162 case RUN_CONTAINER_TYPE_CODE:
2163 return run_container_maximum((const run_container_t *)container);
2164 default:
2165 assert(false);
2166 __builtin_unreachable();
2167 }
2168 assert(false);
2169 __builtin_unreachable();
2170 return false;
2171}
2172
2173static inline uint16_t container_minimum(const void *container,
2174 uint8_t typecode) {
2175 container = container_unwrap_shared(container, &typecode);
2176 switch (typecode) {
2177 case BITSET_CONTAINER_TYPE_CODE:
2178 return bitset_container_minimum((const bitset_container_t *)container);
2179 case ARRAY_CONTAINER_TYPE_CODE:
2180 return array_container_minimum((const array_container_t *)container);
2181 case RUN_CONTAINER_TYPE_CODE:
2182 return run_container_minimum((const run_container_t *)container);
2183 default:
2184 assert(false);
2185 __builtin_unreachable();
2186 }
2187 assert(false);
2188 __builtin_unreachable();
2189 return false;
2190}
2191
2192// number of values smaller or equal to x
2193static inline int container_rank(const void *container, uint8_t typecode,
2194 uint16_t x) {
2195 container = container_unwrap_shared(container, &typecode);
2196 switch (typecode) {
2197 case BITSET_CONTAINER_TYPE_CODE:
2198 return bitset_container_rank((const bitset_container_t *)container, x);
2199 case ARRAY_CONTAINER_TYPE_CODE:
2200 return array_container_rank((const array_container_t *)container, x);
2201 case RUN_CONTAINER_TYPE_CODE:
2202 return run_container_rank((const run_container_t *)container, x);
2203 default:
2204 assert(false);
2205 __builtin_unreachable();
2206 }
2207 assert(false);
2208 __builtin_unreachable();
2209 return false;
2210}
2211
2212/**
2213 * Add all values in range [min, max] to a given container.
2214 *
2215 * If the returned pointer is different from $container, then a new container
2216 * has been created and the caller is responsible for freeing it.
2217 * The type of the first container may change. Returns the modified
2218 * (and possibly new) container.
2219 */
2220static inline void *container_add_range(void *container, uint8_t type,
2221 uint32_t min, uint32_t max,
2222 uint8_t *result_type) {
2223 // NB: when selecting new container type, we perform only inexpensive checks
2224 switch (type) {
2225 case BITSET_CONTAINER_TYPE_CODE: {
2226 bitset_container_t *bitset = (bitset_container_t *) container;
2227
2228 int32_t union_cardinality = 0;
2229 union_cardinality += bitset->cardinality;
2230 union_cardinality += max - min + 1;
2231 union_cardinality -= bitset_lenrange_cardinality(bitset->array, min, max-min);
2232
2233 if (union_cardinality == INT32_C(0x10000)) {
2234 *result_type = RUN_CONTAINER_TYPE_CODE;
2235 return run_container_create_range(0, INT32_C(0x10000));
2236 } else {
2237 *result_type = BITSET_CONTAINER_TYPE_CODE;
2238 bitset_set_lenrange(bitset->array, min, max - min);
2239 bitset->cardinality = union_cardinality;
2240 return bitset;
2241 }
2242 }
2243 case ARRAY_CONTAINER_TYPE_CODE: {
2244 array_container_t *array = (array_container_t *) container;
2245
2246 int32_t nvals_greater = count_greater(array->array, array->cardinality, max);
2247 int32_t nvals_less = count_less(array->array, array->cardinality - nvals_greater, min);
2248 int32_t union_cardinality = nvals_less + (max - min + 1) + nvals_greater;
2249
2250 if (union_cardinality == INT32_C(0x10000)) {
2251 *result_type = RUN_CONTAINER_TYPE_CODE;
2252 return run_container_create_range(0, INT32_C(0x10000));
2253 } else if (union_cardinality <= DEFAULT_MAX_SIZE) {
2254 *result_type = ARRAY_CONTAINER_TYPE_CODE;
2255 array_container_add_range_nvals(array, min, max, nvals_less, nvals_greater);
2256 return array;
2257 } else {
2258 *result_type = BITSET_CONTAINER_TYPE_CODE;
2259 bitset_container_t *bitset = bitset_container_from_array(array);
2260 bitset_set_lenrange(bitset->array, min, max - min);
2261 bitset->cardinality = union_cardinality;
2262 return bitset;
2263 }
2264 }
2265 case RUN_CONTAINER_TYPE_CODE: {
2266 run_container_t *run = (run_container_t *) container;
2267
2268 int32_t nruns_greater = rle16_count_greater(run->runs, run->n_runs, max);
2269 int32_t nruns_less = rle16_count_less(run->runs, run->n_runs - nruns_greater, min);
2270
2271 int32_t run_size_bytes = (nruns_less + 1 + nruns_greater) * sizeof(rle16_t);
2272 int32_t bitset_size_bytes = BITSET_CONTAINER_SIZE_IN_WORDS * sizeof(uint64_t);
2273
2274 if (run_size_bytes <= bitset_size_bytes) {
2275 run_container_add_range_nruns(run, min, max, nruns_less, nruns_greater);
2276 *result_type = RUN_CONTAINER_TYPE_CODE;
2277 return run;
2278 } else {
2279 *result_type = BITSET_CONTAINER_TYPE_CODE;
2280 return bitset_container_from_run_range(run, min, max);
2281 }
2282 }
2283 default:
2284 __builtin_unreachable();
2285 }
2286}
2287
2288/*
2289 * Removes all elements in range [min, max].
2290 * Returns one of:
2291 * - NULL if no elements left
2292 * - pointer to the original container
2293 * - pointer to a newly-allocated container (if it is more efficient)
2294 *
2295 * If the returned pointer is different from $container, then a new container
2296 * has been created and the caller is responsible for freeing the original container.
2297 */
2298static inline void *container_remove_range(void *container, uint8_t type,
2299 uint32_t min, uint32_t max,
2300 uint8_t *result_type) {
2301 switch (type) {
2302 case BITSET_CONTAINER_TYPE_CODE: {
2303 bitset_container_t *bitset = (bitset_container_t *) container;
2304
2305 int32_t result_cardinality = bitset->cardinality -
2306 bitset_lenrange_cardinality(bitset->array, min, max-min);
2307
2308 if (result_cardinality == 0) {
2309 return NULL;
2310 } else if (result_cardinality < DEFAULT_MAX_SIZE) {
2311 *result_type = ARRAY_CONTAINER_TYPE_CODE;
2312 bitset_reset_range(bitset->array, min, max+1);
2313 bitset->cardinality = result_cardinality;
2314 return array_container_from_bitset(bitset);
2315 } else {
2316 *result_type = BITSET_CONTAINER_TYPE_CODE;
2317 bitset_reset_range(bitset->array, min, max+1);
2318 bitset->cardinality = result_cardinality;
2319 return bitset;
2320 }
2321 }
2322 case ARRAY_CONTAINER_TYPE_CODE: {
2323 array_container_t *array = (array_container_t *) container;
2324
2325 int32_t nvals_greater = count_greater(array->array, array->cardinality, max);
2326 int32_t nvals_less = count_less(array->array, array->cardinality - nvals_greater, min);
2327 int32_t result_cardinality = nvals_less + nvals_greater;
2328
2329 if (result_cardinality == 0) {
2330 return NULL;
2331 } else {
2332 *result_type = ARRAY_CONTAINER_TYPE_CODE;
2333 array_container_remove_range(array, nvals_less,
2334 array->cardinality - result_cardinality);
2335 return array;
2336 }
2337 }
2338 case RUN_CONTAINER_TYPE_CODE: {
2339 run_container_t *run = (run_container_t *) container;
2340
2341 if (run->n_runs == 0) {
2342 return NULL;
2343 }
2344 if (min <= run_container_minimum(run) && max >= run_container_maximum(run)) {
2345 return NULL;
2346 }
2347
2348 run_container_remove_range(run, min, max);
2349
2350 if (run_container_serialized_size_in_bytes(run->n_runs) <=
2351 bitset_container_serialized_size_in_bytes()) {
2352 *result_type = RUN_CONTAINER_TYPE_CODE;
2353 return run;
2354 } else {
2355 *result_type = BITSET_CONTAINER_TYPE_CODE;
2356 return bitset_container_from_run(run);
2357 }
2358 }
2359 default:
2360 __builtin_unreachable();
2361 }
2362}
2363
2364#endif
2365