Coverage Report

Created: 2023-01-15 06:02

/src/croaring/src/roaring.c
Line
Count
Source (jump to first uncovered line)
1
#include <assert.h>
2
#include <stdarg.h>
3
#include <stdint.h>
4
#include <stdio.h>
5
#include <string.h>
6
#include <inttypes.h>
7
8
#include <roaring/roaring.h>
9
#include <roaring/roaring_array.h>
10
11
#include <roaring/containers/containers.h>
12
#include <roaring/bitset_util.h>
13
#include <roaring/array_util.h>
14
15
#ifdef __cplusplus
16
using namespace ::roaring::internal;
17
18
extern "C" { namespace roaring { namespace api {
19
#endif
20
21
0
#define CROARING_SERIALIZATION_ARRAY_UINT32 1
22
0
#define CROARING_SERIALIZATION_CONTAINER 2
23
24
extern inline bool roaring_bitmap_get_copy_on_write(const roaring_bitmap_t* r);
25
extern inline void roaring_bitmap_set_copy_on_write(roaring_bitmap_t* r, bool cow);
26
27
0
static inline bool is_cow(const roaring_bitmap_t *r) {
28
0
    return r->high_low_container.flags & ROARING_FLAG_COW;
29
0
}
30
122
static inline bool is_frozen(const roaring_bitmap_t *r) {
31
122
    return r->high_low_container.flags & ROARING_FLAG_FROZEN;
32
122
}
33
34
// this is like roaring_bitmap_add, but it populates pointer arguments in such a
35
// way
36
// that we can recover the container touched, which, in turn can be used to
37
// accelerate some functions (when you repeatedly need to add to the same
38
// container)
39
static inline container_t *containerptr_roaring_bitmap_add(
40
    roaring_bitmap_t *r, uint32_t val,
41
    uint8_t *type, int *index
42
0
){
43
0
    roaring_array_t *ra = &r->high_low_container;
44
45
0
    uint16_t hb = val >> 16;
46
0
    const int i = ra_get_index(ra, hb);
47
0
    if (i >= 0) {
48
0
        ra_unshare_container_at_index(ra, i);
49
0
        container_t *c = ra_get_container_at_index(ra, i, type);
50
0
        uint8_t new_type = *type;
51
0
        container_t *c2 = container_add(c, val & 0xFFFF, *type, &new_type);
52
0
        *index = i;
53
0
        if (c2 != c) {
54
0
            container_free(c, *type);
55
0
            ra_set_container_at_index(ra, i, c2, new_type);
56
0
            *type = new_type;
57
0
            return c2;
58
0
        } else {
59
0
            return c;
60
0
        }
61
0
    } else {
62
0
        array_container_t *new_ac = array_container_create();
63
0
        container_t *c = container_add(new_ac, val & 0xFFFF,
64
0
                                       ARRAY_CONTAINER_TYPE, type);
65
        // we could just assume that it stays an array container
66
0
        ra_insert_new_key_value_at(ra, -i - 1, hb, c, *type);
67
0
        *index = -i - 1;
68
0
        return c;
69
0
    }
70
0
}
71
72
0
roaring_bitmap_t *roaring_bitmap_create_with_capacity(uint32_t cap) {
73
0
    roaring_bitmap_t *ans =
74
0
        (roaring_bitmap_t *)roaring_malloc(sizeof(roaring_bitmap_t));
75
0
    if (!ans) {
76
0
        return NULL;
77
0
    }
78
0
    bool is_ok = ra_init_with_capacity(&ans->high_low_container, cap);
79
0
    if (!is_ok) {
80
0
        roaring_free(ans);
81
0
        return NULL;
82
0
    }
83
0
    return ans;
84
0
}
85
86
0
bool roaring_bitmap_init_with_capacity(roaring_bitmap_t *r, uint32_t cap) {
87
0
    return ra_init_with_capacity(&r->high_low_container, cap);
88
0
}
89
90
static inline void add_bulk_impl(roaring_bitmap_t *r,
91
                                 roaring_bulk_context_t *context,
92
0
                                 uint32_t val) {
93
0
    uint16_t key = val >> 16;
94
0
    if (context->container == NULL || context->key != key) {
95
0
        uint8_t typecode;
96
0
        int idx;
97
0
        context->container = containerptr_roaring_bitmap_add(
98
0
            r, val, &typecode, &idx);
99
0
        context->typecode = typecode;
100
0
        context->idx = idx;
101
0
        context->key = key;
102
0
    } else {
103
        // no need to seek the container, it is at hand
104
        // because we already have the container at hand, we can do the
105
        // insertion directly, bypassing the roaring_bitmap_add call
106
0
        uint8_t new_typecode;
107
0
        container_t *container2 = container_add(
108
0
            context->container, val & 0xFFFF, context->typecode, &new_typecode);
109
0
        if (container2 != context->container) {
110
            // rare instance when we need to change the container type
111
0
            container_free(context->container, context->typecode);
112
0
            ra_set_container_at_index(&r->high_low_container, context->idx,
113
0
                                      container2, new_typecode);
114
0
            context->typecode = new_typecode;
115
0
            context->container = container2;
116
0
        }
117
0
    }
118
0
}
119
120
void roaring_bitmap_add_many(roaring_bitmap_t *r, size_t n_args,
121
0
                             const uint32_t *vals) {
122
0
    uint32_t val;
123
0
    const uint32_t *start = vals;
124
0
    const uint32_t *end = vals + n_args;
125
0
    const uint32_t *current_val = start;
126
127
0
    if (n_args == 0) {
128
0
        return;
129
0
    }
130
131
0
    uint8_t typecode;
132
0
    int idx;
133
0
    container_t *container;
134
0
    val = *current_val;
135
0
    container = containerptr_roaring_bitmap_add(r, val, &typecode, &idx);
136
0
    roaring_bulk_context_t context = {container, idx, (uint16_t)(val >> 16), typecode};
137
138
0
    for (; current_val != end; current_val++) {
139
0
        memcpy(&val, current_val, sizeof(val));
140
0
        add_bulk_impl(r, &context, val);
141
0
    }
142
0
}
143
144
void roaring_bitmap_add_bulk(roaring_bitmap_t *r,
145
0
                             roaring_bulk_context_t *context, uint32_t val) {
146
0
    add_bulk_impl(r, context, val);
147
0
}
148
149
bool roaring_bitmap_contains_bulk(const roaring_bitmap_t *r,
150
                                  roaring_bulk_context_t *context,
151
                                  uint32_t val)
152
0
{
153
0
    uint16_t key = val >> 16;
154
0
    if (context->container == NULL || context->key != key) {
155
0
        int32_t start_idx = -1;
156
0
        if (context->container != NULL && context->key < key) {
157
0
            start_idx = context->idx;
158
0
        }
159
0
        int idx = ra_advance_until(&r->high_low_container, key, start_idx);
160
0
        if (idx == ra_get_size(&r->high_low_container)) {
161
0
            return false;
162
0
        }
163
0
        uint8_t typecode;
164
0
        context->container = ra_get_container_at_index(&r->high_low_container, idx, &typecode);
165
0
        context->typecode = typecode;
166
0
        context->idx = idx;
167
0
        context->key = ra_get_key_at_index(&r->high_low_container, idx);
168
        // ra_advance_until finds the next key >= the target, we found a later container.
169
0
        if (context->key != key) {
170
0
            return false;
171
0
        }
172
0
    }
173
    // context is now set up
174
0
    return container_contains(context->container, val & 0xFFFF, context->typecode);
175
0
}
176
177
0
roaring_bitmap_t *roaring_bitmap_of_ptr(size_t n_args, const uint32_t *vals) {
178
0
    roaring_bitmap_t *answer = roaring_bitmap_create();
179
0
    roaring_bitmap_add_many(answer, n_args, vals);
180
0
    return answer;
181
0
}
182
183
0
roaring_bitmap_t *roaring_bitmap_of(size_t n_args, ...) {
184
    // todo: could be greatly optimized but we do not expect this call to ever
185
    // include long lists
186
0
    roaring_bitmap_t *answer = roaring_bitmap_create();
187
0
    roaring_bulk_context_t context = {0};
188
0
    va_list ap;
189
0
    va_start(ap, n_args);
190
0
    for (size_t i = 0; i < n_args; i++) {
191
0
        uint32_t val = va_arg(ap, uint32_t);
192
0
        roaring_bitmap_add_bulk(answer, &context, val);
193
0
    }
194
0
    va_end(ap);
195
0
    return answer;
196
0
}
197
198
0
static inline uint32_t minimum_uint32(uint32_t a, uint32_t b) {
199
0
    return (a < b) ? a : b;
200
0
}
201
202
0
static inline uint64_t minimum_uint64(uint64_t a, uint64_t b) {
203
0
    return (a < b) ? a : b;
204
0
}
205
206
roaring_bitmap_t *roaring_bitmap_from_range(uint64_t min, uint64_t max,
207
0
                                            uint32_t step) {
208
0
    if(max >= UINT64_C(0x100000000)) {
209
0
        max = UINT64_C(0x100000000);
210
0
    }
211
0
    if (step == 0) return NULL;
212
0
    if (max <= min) return NULL;
213
0
    roaring_bitmap_t *answer = roaring_bitmap_create();
214
0
    if (step >= (1 << 16)) {
215
0
        for (uint32_t value = (uint32_t)min; value < max; value += step) {
216
0
            roaring_bitmap_add(answer, value);
217
0
        }
218
0
        return answer;
219
0
    }
220
0
    uint64_t min_tmp = min;
221
0
    do {
222
0
        uint32_t key = (uint32_t)min_tmp >> 16;
223
0
        uint32_t container_min = min_tmp & 0xFFFF;
224
0
        uint32_t container_max = (uint32_t)minimum_uint64(max - (key << 16), 1 << 16);
225
0
        uint8_t type;
226
0
        container_t *container = container_from_range(&type, container_min,
227
0
                                               container_max, (uint16_t)step);
228
0
        ra_append(&answer->high_low_container, key, container, type);
229
0
        uint32_t gap = container_max - container_min + step - 1;
230
0
        min_tmp += gap - (gap % step);
231
0
    } while (min_tmp < max);
232
    // cardinality of bitmap will be ((uint64_t) max - min + step - 1 ) / step
233
0
    return answer;
234
0
}
235
236
0
void roaring_bitmap_add_range_closed(roaring_bitmap_t *r, uint32_t min, uint32_t max) {
237
0
    if (min > max) {
238
0
        return;
239
0
    }
240
241
0
    roaring_array_t *ra = &r->high_low_container;
242
243
0
    uint32_t min_key = min >> 16;
244
0
    uint32_t max_key = max >> 16;
245
246
0
    int32_t num_required_containers = max_key - min_key + 1;
247
0
    int32_t suffix_length = count_greater(ra->keys, ra->size, max_key);
248
0
    int32_t prefix_length = count_less(ra->keys, ra->size - suffix_length,
249
0
                                       min_key);
250
0
    int32_t common_length = ra->size - prefix_length - suffix_length;
251
252
0
    if (num_required_containers > common_length) {
253
0
        ra_shift_tail(ra, suffix_length,
254
0
                      num_required_containers - common_length);
255
0
    }
256
257
0
    int32_t src = prefix_length + common_length - 1;
258
0
    int32_t dst = ra->size - suffix_length - 1;
259
0
    for (uint32_t key = max_key; key != min_key-1; key--) { // beware of min_key==0
260
0
        uint32_t container_min = (min_key == key) ? (min & 0xffff) : 0;
261
0
        uint32_t container_max = (max_key == key) ? (max & 0xffff) : 0xffff;
262
0
        container_t* new_container;
263
0
        uint8_t new_type;
264
265
0
        if (src >= 0 && ra->keys[src] == key) {
266
0
            ra_unshare_container_at_index(ra, src);
267
0
            new_container = container_add_range(ra->containers[src],
268
0
                                                ra->typecodes[src],
269
0
                                                container_min, container_max,
270
0
                                                &new_type);
271
0
            if (new_container != ra->containers[src]) {
272
0
                container_free(ra->containers[src],
273
0
                               ra->typecodes[src]);
274
0
            }
275
0
            src--;
276
0
        } else {
277
0
            new_container = container_from_range(&new_type, container_min,
278
0
                                                 container_max+1, 1);
279
0
        }
280
0
        ra_replace_key_and_container_at_index(ra, dst, key, new_container,
281
0
                                              new_type);
282
0
        dst--;
283
0
    }
284
0
}
285
286
0
void roaring_bitmap_remove_range_closed(roaring_bitmap_t *r, uint32_t min, uint32_t max) {
287
0
    if (min > max) {
288
0
        return;
289
0
    }
290
291
0
    roaring_array_t *ra = &r->high_low_container;
292
293
0
    uint32_t min_key = min >> 16;
294
0
    uint32_t max_key = max >> 16;
295
296
0
    int32_t src = count_less(ra->keys, ra->size, min_key);
297
0
    int32_t dst = src;
298
0
    while (src < ra->size && ra->keys[src] <= max_key) {
299
0
        uint32_t container_min = (min_key == ra->keys[src]) ? (min & 0xffff) : 0;
300
0
        uint32_t container_max = (max_key == ra->keys[src]) ? (max & 0xffff) : 0xffff;
301
0
        ra_unshare_container_at_index(ra, src);
302
0
        container_t *new_container;
303
0
        uint8_t new_type;
304
0
        new_container = container_remove_range(ra->containers[src],
305
0
                                               ra->typecodes[src],
306
0
                                               container_min, container_max,
307
0
                                               &new_type);
308
0
        if (new_container != ra->containers[src]) {
309
0
            container_free(ra->containers[src],
310
0
                           ra->typecodes[src]);
311
0
        }
312
0
        if (new_container) {
313
0
            ra_replace_key_and_container_at_index(ra, dst, ra->keys[src],
314
0
                                                  new_container, new_type);
315
0
            dst++;
316
0
        }
317
0
        src++;
318
0
    }
319
0
    if (src > dst) {
320
0
        ra_shift_tail(ra, ra->size - src, dst - src);
321
0
    }
322
0
}
323
324
extern inline void roaring_bitmap_add_range(roaring_bitmap_t *r, uint64_t min, uint64_t max);
325
extern inline void roaring_bitmap_remove_range(roaring_bitmap_t *r, uint64_t min, uint64_t max);
326
327
0
void roaring_bitmap_printf(const roaring_bitmap_t *r) {
328
0
    const roaring_array_t *ra = &r->high_low_container;
329
330
0
    printf("{");
331
0
    for (int i = 0; i < ra->size; ++i) {
332
0
        container_printf_as_uint32_array(ra->containers[i], ra->typecodes[i],
333
0
                                         ((uint32_t)ra->keys[i]) << 16);
334
335
0
        if (i + 1 < ra->size) {
336
0
            printf(",");
337
0
        }
338
0
    }
339
0
    printf("}");
340
0
}
341
342
0
void roaring_bitmap_printf_describe(const roaring_bitmap_t *r) {
343
0
    const roaring_array_t *ra = &r->high_low_container;
344
345
0
    printf("{");
346
0
    for (int i = 0; i < ra->size; ++i) {
347
0
        printf("%d: %s (%d)", ra->keys[i],
348
0
               get_full_container_name(ra->containers[i], ra->typecodes[i]),
349
0
               container_get_cardinality(ra->containers[i], ra->typecodes[i]));
350
0
        if (ra->typecodes[i] == SHARED_CONTAINER_TYPE) {
351
0
            printf(
352
0
                "(shared count = %" PRIu32 " )",
353
0
                    CAST_shared(ra->containers[i])->counter);
354
0
        }
355
356
0
        if (i + 1 < ra->size) {
357
0
            printf(", ");
358
0
        }
359
0
    }
360
0
    printf("}");
361
0
}
362
363
typedef struct min_max_sum_s {
364
    uint32_t min;
365
    uint32_t max;
366
    uint64_t sum;
367
} min_max_sum_t;
368
369
0
static bool min_max_sum_fnc(uint32_t value, void *param) {
370
0
    min_max_sum_t *mms = (min_max_sum_t *)param;
371
0
    if (value > mms->max) mms->max = value;
372
0
    if (value < mms->min) mms->min = value;
373
0
    mms->sum += value;
374
0
    return true;  // we always process all data points
375
0
}
376
377
/**
378
*  (For advanced users.)
379
* Collect statistics about the bitmap
380
*/
381
void roaring_bitmap_statistics(const roaring_bitmap_t *r,
382
0
                               roaring_statistics_t *stat) {
383
0
    const roaring_array_t *ra = &r->high_low_container;
384
385
0
    memset(stat, 0, sizeof(*stat));
386
0
    stat->n_containers = ra->size;
387
0
    stat->cardinality = roaring_bitmap_get_cardinality(r);
388
0
    min_max_sum_t mms;
389
0
    mms.min = UINT32_C(0xFFFFFFFF);
390
0
    mms.max = UINT32_C(0);
391
0
    mms.sum = 0;
392
0
    roaring_iterate(r, &min_max_sum_fnc, &mms);
393
0
    stat->min_value = mms.min;
394
0
    stat->max_value = mms.max;
395
0
    stat->sum_value = mms.sum;
396
397
0
    for (int i = 0; i < ra->size; ++i) {
398
0
        uint8_t truetype =
399
0
            get_container_type(ra->containers[i], ra->typecodes[i]);
400
0
        uint32_t card =
401
0
            container_get_cardinality(ra->containers[i], ra->typecodes[i]);
402
0
        uint32_t sbytes =
403
0
            container_size_in_bytes(ra->containers[i], ra->typecodes[i]);
404
0
        switch (truetype) {
405
0
            case BITSET_CONTAINER_TYPE:
406
0
                stat->n_bitset_containers++;
407
0
                stat->n_values_bitset_containers += card;
408
0
                stat->n_bytes_bitset_containers += sbytes;
409
0
                break;
410
0
            case ARRAY_CONTAINER_TYPE:
411
0
                stat->n_array_containers++;
412
0
                stat->n_values_array_containers += card;
413
0
                stat->n_bytes_array_containers += sbytes;
414
0
                break;
415
0
            case RUN_CONTAINER_TYPE:
416
0
                stat->n_run_containers++;
417
0
                stat->n_values_run_containers += card;
418
0
                stat->n_bytes_run_containers += sbytes;
419
0
                break;
420
0
            default:
421
0
                assert(false);
422
0
                __builtin_unreachable();
423
0
        }
424
0
    }
425
0
}
426
427
0
roaring_bitmap_t *roaring_bitmap_copy(const roaring_bitmap_t *r) {
428
0
    roaring_bitmap_t *ans =
429
0
        (roaring_bitmap_t *)roaring_malloc(sizeof(roaring_bitmap_t));
430
0
    if (!ans) {
431
0
        return NULL;
432
0
    }
433
0
    if (!ra_init_with_capacity(  // allocation of list of containers can fail
434
0
                &ans->high_low_container, r->high_low_container.size)
435
0
    ){
436
0
        roaring_free(ans);
437
0
        return NULL;
438
0
    }
439
0
    if (!ra_overwrite(  // memory allocation of individual containers may fail
440
0
                &r->high_low_container, &ans->high_low_container, is_cow(r))
441
0
    ){
442
0
        roaring_bitmap_free(ans);  // overwrite should leave in freeable state
443
0
        return NULL;
444
0
    }
445
0
    roaring_bitmap_set_copy_on_write(ans, is_cow(r));
446
0
    return ans;
447
0
}
448
449
bool roaring_bitmap_overwrite(roaring_bitmap_t *dest,
450
0
                                     const roaring_bitmap_t *src) {
451
0
    roaring_bitmap_set_copy_on_write(dest, is_cow(src));
452
0
    return ra_overwrite(&src->high_low_container, &dest->high_low_container,
453
0
                        is_cow(src));
454
0
}
455
456
122
void roaring_bitmap_free(const roaring_bitmap_t *r) {
457
122
    if (!is_frozen(r)) {
458
122
      ra_clear((roaring_array_t*)&r->high_low_container);
459
122
    }
460
122
    roaring_free((roaring_bitmap_t*)r);
461
122
}
462
463
0
void roaring_bitmap_clear(roaring_bitmap_t *r) {
464
0
  ra_reset(&r->high_low_container);
465
0
}
466
467
0
void roaring_bitmap_add(roaring_bitmap_t *r, uint32_t val) {
468
0
    roaring_array_t *ra = &r->high_low_container;
469
470
0
    const uint16_t hb = val >> 16;
471
0
    const int i = ra_get_index(ra, hb);
472
0
    uint8_t typecode;
473
0
    if (i >= 0) {
474
0
        ra_unshare_container_at_index(ra, i);
475
0
        container_t *container =
476
0
            ra_get_container_at_index(ra, i, &typecode);
477
0
        uint8_t newtypecode = typecode;
478
0
        container_t *container2 =
479
0
            container_add(container, val & 0xFFFF, typecode, &newtypecode);
480
0
        if (container2 != container) {
481
0
            container_free(container, typecode);
482
0
            ra_set_container_at_index(&r->high_low_container, i, container2,
483
0
                                      newtypecode);
484
0
        }
485
0
    } else {
486
0
        array_container_t *newac = array_container_create();
487
0
        container_t *container = container_add(newac, val & 0xFFFF,
488
0
                                        ARRAY_CONTAINER_TYPE, &typecode);
489
        // we could just assume that it stays an array container
490
0
        ra_insert_new_key_value_at(&r->high_low_container, -i - 1, hb,
491
0
                                   container, typecode);
492
0
    }
493
0
}
494
495
0
bool roaring_bitmap_add_checked(roaring_bitmap_t *r, uint32_t val) {
496
0
    const uint16_t hb = val >> 16;
497
0
    const int i = ra_get_index(&r->high_low_container, hb);
498
0
    uint8_t typecode;
499
0
    bool result = false;
500
0
    if (i >= 0) {
501
0
        ra_unshare_container_at_index(&r->high_low_container, i);
502
0
        container_t *container =
503
0
            ra_get_container_at_index(&r->high_low_container, i, &typecode);
504
505
0
        const int oldCardinality =
506
0
            container_get_cardinality(container, typecode);
507
508
0
        uint8_t newtypecode = typecode;
509
0
        container_t *container2 =
510
0
            container_add(container, val & 0xFFFF, typecode, &newtypecode);
511
0
        if (container2 != container) {
512
0
            container_free(container, typecode);
513
0
            ra_set_container_at_index(&r->high_low_container, i, container2,
514
0
                                      newtypecode);
515
0
            result = true;
516
0
        } else {
517
0
            const int newCardinality =
518
0
                container_get_cardinality(container, newtypecode);
519
520
0
            result = oldCardinality != newCardinality;
521
0
        }
522
0
    } else {
523
0
        array_container_t *newac = array_container_create();
524
0
        container_t *container = container_add(newac, val & 0xFFFF,
525
0
                                        ARRAY_CONTAINER_TYPE, &typecode);
526
        // we could just assume that it stays an array container
527
0
        ra_insert_new_key_value_at(&r->high_low_container, -i - 1, hb,
528
0
                                   container, typecode);
529
0
        result = true;
530
0
    }
531
532
0
    return result;
533
0
}
534
535
0
void roaring_bitmap_remove(roaring_bitmap_t *r, uint32_t val) {
536
0
    const uint16_t hb = val >> 16;
537
0
    const int i = ra_get_index(&r->high_low_container, hb);
538
0
    uint8_t typecode;
539
0
    if (i >= 0) {
540
0
        ra_unshare_container_at_index(&r->high_low_container, i);
541
0
        container_t *container =
542
0
            ra_get_container_at_index(&r->high_low_container, i, &typecode);
543
0
        uint8_t newtypecode = typecode;
544
0
        container_t *container2 =
545
0
            container_remove(container, val & 0xFFFF, typecode, &newtypecode);
546
0
        if (container2 != container) {
547
0
            container_free(container, typecode);
548
0
            ra_set_container_at_index(&r->high_low_container, i, container2,
549
0
                                      newtypecode);
550
0
        }
551
0
        if (container_get_cardinality(container2, newtypecode) != 0) {
552
0
            ra_set_container_at_index(&r->high_low_container, i, container2,
553
0
                                      newtypecode);
554
0
        } else {
555
0
            ra_remove_at_index_and_free(&r->high_low_container, i);
556
0
        }
557
0
    }
558
0
}
559
560
0
bool roaring_bitmap_remove_checked(roaring_bitmap_t *r, uint32_t val) {
561
0
    const uint16_t hb = val >> 16;
562
0
    const int i = ra_get_index(&r->high_low_container, hb);
563
0
    uint8_t typecode;
564
0
    bool result = false;
565
0
    if (i >= 0) {
566
0
        ra_unshare_container_at_index(&r->high_low_container, i);
567
0
        container_t *container =
568
0
            ra_get_container_at_index(&r->high_low_container, i, &typecode);
569
570
0
        const int oldCardinality =
571
0
            container_get_cardinality(container, typecode);
572
573
0
        uint8_t newtypecode = typecode;
574
0
        container_t *container2 =
575
0
            container_remove(container, val & 0xFFFF, typecode, &newtypecode);
576
0
        if (container2 != container) {
577
0
            container_free(container, typecode);
578
0
            ra_set_container_at_index(&r->high_low_container, i, container2,
579
0
                                      newtypecode);
580
0
        }
581
582
0
        const int newCardinality =
583
0
            container_get_cardinality(container2, newtypecode);
584
585
0
        if (newCardinality != 0) {
586
0
            ra_set_container_at_index(&r->high_low_container, i, container2,
587
0
                                      newtypecode);
588
0
        } else {
589
0
            ra_remove_at_index_and_free(&r->high_low_container, i);
590
0
        }
591
592
0
        result = oldCardinality != newCardinality;
593
0
    }
594
0
    return result;
595
0
}
596
597
void roaring_bitmap_remove_many(roaring_bitmap_t *r, size_t n_args,
598
0
                                const uint32_t *vals) {
599
0
    if (n_args == 0 || r->high_low_container.size == 0) {
600
0
        return;
601
0
    }
602
0
    int32_t pos = -1; // position of the container used in the previous iteration
603
0
    for (size_t i = 0; i < n_args; i++) {
604
0
        uint16_t key = (uint16_t)(vals[i] >> 16);
605
0
        if (pos < 0 || key != r->high_low_container.keys[pos]) {
606
0
            pos = ra_get_index(&r->high_low_container, key);
607
0
        }
608
0
        if (pos >= 0) {
609
0
            uint8_t new_typecode;
610
0
            container_t *new_container;
611
0
            new_container = container_remove(r->high_low_container.containers[pos],
612
0
                                             vals[i] & 0xffff,
613
0
                                             r->high_low_container.typecodes[pos],
614
0
                                             &new_typecode);
615
0
            if (new_container != r->high_low_container.containers[pos]) {
616
0
                container_free(r->high_low_container.containers[pos],
617
0
                               r->high_low_container.typecodes[pos]);
618
0
                ra_replace_key_and_container_at_index(&r->high_low_container,
619
0
                                                      pos, key, new_container,
620
0
                                                      new_typecode);
621
0
            }
622
0
            if (!container_nonzero_cardinality(new_container, new_typecode)) {
623
0
                container_free(new_container, new_typecode);
624
0
                ra_remove_at_index(&r->high_low_container, pos);
625
0
                pos = -1;
626
0
            }
627
0
        }
628
0
    }
629
0
}
630
631
// there should be some SIMD optimizations possible here
632
roaring_bitmap_t *roaring_bitmap_and(const roaring_bitmap_t *x1,
633
0
                                     const roaring_bitmap_t *x2) {
634
0
    uint8_t result_type = 0;
635
0
    const int length1 = x1->high_low_container.size,
636
0
              length2 = x2->high_low_container.size;
637
0
    uint32_t neededcap = length1 > length2 ? length2 : length1;
638
0
    roaring_bitmap_t *answer = roaring_bitmap_create_with_capacity(neededcap);
639
0
    roaring_bitmap_set_copy_on_write(answer, is_cow(x1) || is_cow(x2));
640
641
0
    int pos1 = 0, pos2 = 0;
642
643
0
    while (pos1 < length1 && pos2 < length2) {
644
0
        const uint16_t s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
645
0
        const uint16_t s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
646
647
0
        if (s1 == s2) {
648
0
            uint8_t type1, type2;
649
0
            container_t *c1 = ra_get_container_at_index(
650
0
                                    &x1->high_low_container, pos1, &type1);
651
0
            container_t *c2 = ra_get_container_at_index(
652
0
                                    &x2->high_low_container, pos2, &type2);
653
0
            container_t *c = container_and(c1, type1, c2, type2, &result_type);
654
655
0
            if (container_nonzero_cardinality(c, result_type)) {
656
0
                ra_append(&answer->high_low_container, s1, c, result_type);
657
0
            } else {
658
0
                container_free(c, result_type);  // otherwise: memory leak!
659
0
            }
660
0
            ++pos1;
661
0
            ++pos2;
662
0
        } else if (s1 < s2) {  // s1 < s2
663
0
            pos1 = ra_advance_until(&x1->high_low_container, s2, pos1);
664
0
        } else {  // s1 > s2
665
0
            pos2 = ra_advance_until(&x2->high_low_container, s1, pos2);
666
0
        }
667
0
    }
668
0
    return answer;
669
0
}
670
671
/**
672
 * Compute the union of 'number' bitmaps.
673
 */
674
roaring_bitmap_t *roaring_bitmap_or_many(size_t number,
675
0
                                         const roaring_bitmap_t **x) {
676
0
    if (number == 0) {
677
0
        return roaring_bitmap_create();
678
0
    }
679
0
    if (number == 1) {
680
0
        return roaring_bitmap_copy(x[0]);
681
0
    }
682
0
    roaring_bitmap_t *answer =
683
0
        roaring_bitmap_lazy_or(x[0], x[1], LAZY_OR_BITSET_CONVERSION);
684
0
    for (size_t i = 2; i < number; i++) {
685
0
        roaring_bitmap_lazy_or_inplace(answer, x[i], LAZY_OR_BITSET_CONVERSION);
686
0
    }
687
0
    roaring_bitmap_repair_after_lazy(answer);
688
0
    return answer;
689
0
}
690
691
/**
692
 * Compute the xor of 'number' bitmaps.
693
 */
694
roaring_bitmap_t *roaring_bitmap_xor_many(size_t number,
695
0
                                          const roaring_bitmap_t **x) {
696
0
    if (number == 0) {
697
0
        return roaring_bitmap_create();
698
0
    }
699
0
    if (number == 1) {
700
0
        return roaring_bitmap_copy(x[0]);
701
0
    }
702
0
    roaring_bitmap_t *answer = roaring_bitmap_lazy_xor(x[0], x[1]);
703
0
    for (size_t i = 2; i < number; i++) {
704
0
        roaring_bitmap_lazy_xor_inplace(answer, x[i]);
705
0
    }
706
0
    roaring_bitmap_repair_after_lazy(answer);
707
0
    return answer;
708
0
}
709
710
// inplace and (modifies its first argument).
711
void roaring_bitmap_and_inplace(roaring_bitmap_t *x1,
712
0
                                const roaring_bitmap_t *x2) {
713
0
    if (x1 == x2) return;
714
0
    int pos1 = 0, pos2 = 0, intersection_size = 0;
715
0
    const int length1 = ra_get_size(&x1->high_low_container);
716
0
    const int length2 = ra_get_size(&x2->high_low_container);
717
718
    // any skipped-over or newly emptied containers in x1
719
    // have to be freed.
720
0
    while (pos1 < length1 && pos2 < length2) {
721
0
        const uint16_t s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
722
0
        const uint16_t s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
723
724
0
        if (s1 == s2) {
725
0
            uint8_t type1, type2, result_type;
726
0
            container_t *c1 = ra_get_container_at_index(
727
0
                                    &x1->high_low_container, pos1, &type1);
728
0
            container_t *c2 = ra_get_container_at_index(
729
0
                                    &x2->high_low_container, pos2, &type2);
730
731
            // We do the computation "in place" only when c1 is not a shared container.
732
            // Rationale: using a shared container safely with in place computation would
733
            // require making a copy and then doing the computation in place which is likely
734
            // less efficient than avoiding in place entirely and always generating a new
735
            // container.
736
0
            container_t *c =
737
0
                (type1 == SHARED_CONTAINER_TYPE)
738
0
                    ? container_and(c1, type1, c2, type2, &result_type)
739
0
                    : container_iand(c1, type1, c2, type2, &result_type);
740
741
0
            if (c != c1) {  // in this instance a new container was created, and
742
                            // we need to free the old one
743
0
                container_free(c1, type1);
744
0
            }
745
0
            if (container_nonzero_cardinality(c, result_type)) {
746
0
                ra_replace_key_and_container_at_index(&x1->high_low_container,
747
0
                                                      intersection_size, s1, c,
748
0
                                                      result_type);
749
0
                intersection_size++;
750
0
            } else {
751
0
                container_free(c, result_type);
752
0
            }
753
0
            ++pos1;
754
0
            ++pos2;
755
0
        } else if (s1 < s2) {
756
0
            pos1 = ra_advance_until_freeing(&x1->high_low_container, s2, pos1);
757
0
        } else {  // s1 > s2
758
0
            pos2 = ra_advance_until(&x2->high_low_container, s1, pos2);
759
0
        }
760
0
    }
761
762
    // if we ended early because x2 ran out, then all remaining in x1 should be
763
    // freed
764
0
    while (pos1 < length1) {
765
0
        container_free(x1->high_low_container.containers[pos1],
766
0
                       x1->high_low_container.typecodes[pos1]);
767
0
        ++pos1;
768
0
    }
769
770
    // all containers after this have either been copied or freed
771
0
    ra_downsize(&x1->high_low_container, intersection_size);
772
0
}
773
774
roaring_bitmap_t *roaring_bitmap_or(const roaring_bitmap_t *x1,
775
0
                                    const roaring_bitmap_t *x2) {
776
0
    uint8_t result_type = 0;
777
0
    const int length1 = x1->high_low_container.size,
778
0
              length2 = x2->high_low_container.size;
779
0
    if (0 == length1) {
780
0
        return roaring_bitmap_copy(x2);
781
0
    }
782
0
    if (0 == length2) {
783
0
        return roaring_bitmap_copy(x1);
784
0
    }
785
0
    roaring_bitmap_t *answer =
786
0
        roaring_bitmap_create_with_capacity(length1 + length2);
787
0
    roaring_bitmap_set_copy_on_write(answer, is_cow(x1) || is_cow(x2));
788
0
    int pos1 = 0, pos2 = 0;
789
0
    uint8_t type1, type2;
790
0
    uint16_t s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
791
0
    uint16_t s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
792
0
    while (true) {
793
0
        if (s1 == s2) {
794
0
            container_t *c1 = ra_get_container_at_index(
795
0
                                    &x1->high_low_container, pos1, &type1);
796
0
            container_t *c2 = ra_get_container_at_index(
797
0
                                    &x2->high_low_container, pos2, &type2);
798
0
            container_t *c = container_or(c1, type1, c2, type2, &result_type);
799
800
            // since we assume that the initial containers are non-empty, the
801
            // result here
802
            // can only be non-empty
803
0
            ra_append(&answer->high_low_container, s1, c, result_type);
804
0
            ++pos1;
805
0
            ++pos2;
806
0
            if (pos1 == length1) break;
807
0
            if (pos2 == length2) break;
808
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
809
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
810
811
0
        } else if (s1 < s2) {  // s1 < s2
812
0
            container_t *c1 = ra_get_container_at_index(
813
0
                                    &x1->high_low_container, pos1, &type1);
814
            // c1 = container_clone(c1, type1);
815
0
            c1 = get_copy_of_container(c1, &type1, is_cow(x1));
816
0
            if (is_cow(x1)) {
817
0
                ra_set_container_at_index(&x1->high_low_container, pos1, c1,
818
0
                                          type1);
819
0
            }
820
0
            ra_append(&answer->high_low_container, s1, c1, type1);
821
0
            pos1++;
822
0
            if (pos1 == length1) break;
823
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
824
825
0
        } else {  // s1 > s2
826
0
            container_t *c2 = ra_get_container_at_index(
827
0
                                    &x2->high_low_container, pos2, &type2);
828
            // c2 = container_clone(c2, type2);
829
0
            c2 = get_copy_of_container(c2, &type2, is_cow(x2));
830
0
            if (is_cow(x2)) {
831
0
                ra_set_container_at_index(&x2->high_low_container, pos2, c2,
832
0
                                          type2);
833
0
            }
834
0
            ra_append(&answer->high_low_container, s2, c2, type2);
835
0
            pos2++;
836
0
            if (pos2 == length2) break;
837
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
838
0
        }
839
0
    }
840
0
    if (pos1 == length1) {
841
0
        ra_append_copy_range(&answer->high_low_container,
842
0
                             &x2->high_low_container, pos2, length2,
843
0
                             is_cow(x2));
844
0
    } else if (pos2 == length2) {
845
0
        ra_append_copy_range(&answer->high_low_container,
846
0
                             &x1->high_low_container, pos1, length1,
847
0
                             is_cow(x1));
848
0
    }
849
0
    return answer;
850
0
}
851
852
// inplace or (modifies its first argument).
853
void roaring_bitmap_or_inplace(roaring_bitmap_t *x1,
854
0
                               const roaring_bitmap_t *x2) {
855
0
    uint8_t result_type = 0;
856
0
    int length1 = x1->high_low_container.size;
857
0
    const int length2 = x2->high_low_container.size;
858
859
0
    if (0 == length2) return;
860
861
0
    if (0 == length1) {
862
0
        roaring_bitmap_overwrite(x1, x2);
863
0
        return;
864
0
    }
865
0
    int pos1 = 0, pos2 = 0;
866
0
    uint8_t type1, type2;
867
0
    uint16_t s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
868
0
    uint16_t s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
869
0
    while (true) {
870
0
        if (s1 == s2) {
871
0
            container_t *c1 = ra_get_container_at_index(
872
0
                                    &x1->high_low_container, pos1, &type1);
873
0
            if (!container_is_full(c1, type1)) {
874
0
                container_t *c2 = ra_get_container_at_index(
875
0
                                        &x2->high_low_container, pos2, &type2);
876
0
                container_t *c =
877
0
                    (type1 == SHARED_CONTAINER_TYPE)
878
0
                        ? container_or(c1, type1, c2, type2, &result_type)
879
0
                        : container_ior(c1, type1, c2, type2, &result_type);
880
881
0
                if (c != c1) {  // in this instance a new container was created,
882
                                // and we need to free the old one
883
0
                    container_free(c1, type1);
884
0
                }
885
0
                ra_set_container_at_index(&x1->high_low_container, pos1, c,
886
0
                                          result_type);
887
0
            }
888
0
            ++pos1;
889
0
            ++pos2;
890
0
            if (pos1 == length1) break;
891
0
            if (pos2 == length2) break;
892
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
893
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
894
895
0
        } else if (s1 < s2) {  // s1 < s2
896
0
            pos1++;
897
0
            if (pos1 == length1) break;
898
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
899
900
0
        } else {  // s1 > s2
901
0
            container_t *c2 = ra_get_container_at_index(&x2->high_low_container,
902
0
                                                        pos2, &type2);
903
0
            c2 = get_copy_of_container(c2, &type2, is_cow(x2));
904
0
            if (is_cow(x2)) {
905
0
                ra_set_container_at_index(&x2->high_low_container, pos2, c2,
906
0
                                          type2);
907
0
            }
908
909
            // container_t *c2_clone = container_clone(c2, type2);
910
0
            ra_insert_new_key_value_at(&x1->high_low_container, pos1, s2, c2,
911
0
                                       type2);
912
0
            pos1++;
913
0
            length1++;
914
0
            pos2++;
915
0
            if (pos2 == length2) break;
916
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
917
0
        }
918
0
    }
919
0
    if (pos1 == length1) {
920
0
        ra_append_copy_range(&x1->high_low_container, &x2->high_low_container,
921
0
                             pos2, length2, is_cow(x2));
922
0
    }
923
0
}
924
925
roaring_bitmap_t *roaring_bitmap_xor(const roaring_bitmap_t *x1,
926
0
                                     const roaring_bitmap_t *x2) {
927
0
    uint8_t result_type = 0;
928
0
    const int length1 = x1->high_low_container.size,
929
0
              length2 = x2->high_low_container.size;
930
0
    if (0 == length1) {
931
0
        return roaring_bitmap_copy(x2);
932
0
    }
933
0
    if (0 == length2) {
934
0
        return roaring_bitmap_copy(x1);
935
0
    }
936
0
    roaring_bitmap_t *answer =
937
0
        roaring_bitmap_create_with_capacity(length1 + length2);
938
0
    roaring_bitmap_set_copy_on_write(answer, is_cow(x1) || is_cow(x2));
939
0
    int pos1 = 0, pos2 = 0;
940
0
    uint8_t type1, type2;
941
0
    uint16_t s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
942
0
    uint16_t s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
943
0
    while (true) {
944
0
        if (s1 == s2) {
945
0
            container_t *c1 = ra_get_container_at_index(
946
0
                                    &x1->high_low_container, pos1, &type1);
947
0
            container_t *c2 = ra_get_container_at_index(
948
0
                                    &x2->high_low_container, pos2, &type2);
949
0
            container_t *c = container_xor(c1, type1, c2, type2, &result_type);
950
951
0
            if (container_nonzero_cardinality(c, result_type)) {
952
0
                ra_append(&answer->high_low_container, s1, c, result_type);
953
0
            } else {
954
0
                container_free(c, result_type);
955
0
            }
956
0
            ++pos1;
957
0
            ++pos2;
958
0
            if (pos1 == length1) break;
959
0
            if (pos2 == length2) break;
960
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
961
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
962
963
0
        } else if (s1 < s2) {  // s1 < s2
964
0
            container_t *c1 = ra_get_container_at_index(
965
0
                                &x1->high_low_container, pos1, &type1);
966
0
            c1 = get_copy_of_container(c1, &type1, is_cow(x1));
967
0
            if (is_cow(x1)) {
968
0
                ra_set_container_at_index(&x1->high_low_container, pos1, c1,
969
0
                                          type1);
970
0
            }
971
0
            ra_append(&answer->high_low_container, s1, c1, type1);
972
0
            pos1++;
973
0
            if (pos1 == length1) break;
974
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
975
976
0
        } else {  // s1 > s2
977
0
            container_t *c2 = ra_get_container_at_index(
978
0
                                &x2->high_low_container, pos2, &type2);
979
0
            c2 = get_copy_of_container(c2, &type2, is_cow(x2));
980
0
            if (is_cow(x2)) {
981
0
                ra_set_container_at_index(&x2->high_low_container, pos2, c2,
982
0
                                          type2);
983
0
            }
984
0
            ra_append(&answer->high_low_container, s2, c2, type2);
985
0
            pos2++;
986
0
            if (pos2 == length2) break;
987
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
988
0
        }
989
0
    }
990
0
    if (pos1 == length1) {
991
0
        ra_append_copy_range(&answer->high_low_container,
992
0
                             &x2->high_low_container, pos2, length2,
993
0
                             is_cow(x2));
994
0
    } else if (pos2 == length2) {
995
0
        ra_append_copy_range(&answer->high_low_container,
996
0
                             &x1->high_low_container, pos1, length1,
997
0
                             is_cow(x1));
998
0
    }
999
0
    return answer;
1000
0
}
1001
1002
// inplace xor (modifies its first argument).
1003
1004
void roaring_bitmap_xor_inplace(roaring_bitmap_t *x1,
1005
0
                                const roaring_bitmap_t *x2) {
1006
0
    assert(x1 != x2);
1007
0
    uint8_t result_type = 0;
1008
0
    int length1 = x1->high_low_container.size;
1009
0
    const int length2 = x2->high_low_container.size;
1010
1011
0
    if (0 == length2) return;
1012
1013
0
    if (0 == length1) {
1014
0
        roaring_bitmap_overwrite(x1, x2);
1015
0
        return;
1016
0
    }
1017
1018
    // XOR can have new containers inserted from x2, but can also
1019
    // lose containers when x1 and x2 are nonempty and identical.
1020
1021
0
    int pos1 = 0, pos2 = 0;
1022
0
    uint8_t type1, type2;
1023
0
    uint16_t s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
1024
0
    uint16_t s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
1025
0
    while (true) {
1026
0
        if (s1 == s2) {
1027
0
            container_t *c1 = ra_get_container_at_index(
1028
0
                                    &x1->high_low_container, pos1, &type1);
1029
0
            container_t *c2 = ra_get_container_at_index(
1030
0
                                    &x2->high_low_container, pos2, &type2);
1031
1032
            // We do the computation "in place" only when c1 is not a shared container.
1033
            // Rationale: using a shared container safely with in place computation would
1034
            // require making a copy and then doing the computation in place which is likely
1035
            // less efficient than avoiding in place entirely and always generating a new
1036
            // container.
1037
1038
0
            container_t *c;
1039
0
            if (type1 == SHARED_CONTAINER_TYPE) {
1040
0
                c = container_xor(c1, type1, c2, type2, &result_type);
1041
0
                shared_container_free(CAST_shared(c1));  // so release
1042
0
            }
1043
0
            else {
1044
0
                c = container_ixor(c1, type1, c2, type2, &result_type);
1045
0
            }
1046
1047
0
            if (container_nonzero_cardinality(c, result_type)) {
1048
0
                ra_set_container_at_index(&x1->high_low_container, pos1, c,
1049
0
                                          result_type);
1050
0
                ++pos1;
1051
0
            } else {
1052
0
                container_free(c, result_type);
1053
0
                ra_remove_at_index(&x1->high_low_container, pos1);
1054
0
                --length1;
1055
0
            }
1056
1057
0
            ++pos2;
1058
0
            if (pos1 == length1) break;
1059
0
            if (pos2 == length2) break;
1060
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
1061
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
1062
1063
0
        } else if (s1 < s2) {  // s1 < s2
1064
0
            pos1++;
1065
0
            if (pos1 == length1) break;
1066
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
1067
1068
0
        } else {  // s1 > s2
1069
0
            container_t *c2 = ra_get_container_at_index(
1070
0
                                    &x2->high_low_container, pos2, &type2);
1071
0
            c2 = get_copy_of_container(c2, &type2, is_cow(x2));
1072
0
            if (is_cow(x2)) {
1073
0
                ra_set_container_at_index(&x2->high_low_container, pos2, c2,
1074
0
                                          type2);
1075
0
            }
1076
1077
0
            ra_insert_new_key_value_at(&x1->high_low_container, pos1, s2, c2,
1078
0
                                       type2);
1079
0
            pos1++;
1080
0
            length1++;
1081
0
            pos2++;
1082
0
            if (pos2 == length2) break;
1083
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
1084
0
        }
1085
0
    }
1086
0
    if (pos1 == length1) {
1087
0
        ra_append_copy_range(&x1->high_low_container, &x2->high_low_container,
1088
0
                             pos2, length2, is_cow(x2));
1089
0
    }
1090
0
}
1091
1092
roaring_bitmap_t *roaring_bitmap_andnot(const roaring_bitmap_t *x1,
1093
0
                                        const roaring_bitmap_t *x2) {
1094
0
    uint8_t result_type = 0;
1095
0
    const int length1 = x1->high_low_container.size,
1096
0
              length2 = x2->high_low_container.size;
1097
0
    if (0 == length1) {
1098
0
        roaring_bitmap_t *empty_bitmap = roaring_bitmap_create();
1099
0
        roaring_bitmap_set_copy_on_write(empty_bitmap, is_cow(x1) || is_cow(x2));
1100
0
        return empty_bitmap;
1101
0
    }
1102
0
    if (0 == length2) {
1103
0
        return roaring_bitmap_copy(x1);
1104
0
    }
1105
0
    roaring_bitmap_t *answer = roaring_bitmap_create_with_capacity(length1);
1106
0
    roaring_bitmap_set_copy_on_write(answer, is_cow(x1) || is_cow(x2));
1107
1108
0
    int pos1 = 0, pos2 = 0;
1109
0
    uint8_t type1, type2;
1110
0
    uint16_t s1 = 0;
1111
0
    uint16_t s2 = 0;
1112
0
    while (true) {
1113
0
        s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
1114
0
        s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
1115
1116
0
        if (s1 == s2) {
1117
0
            container_t *c1 = ra_get_container_at_index(
1118
0
                                    &x1->high_low_container, pos1, &type1);
1119
0
            container_t *c2 = ra_get_container_at_index(
1120
0
                                    &x2->high_low_container, pos2, &type2);
1121
0
            container_t *c = container_andnot(c1, type1, c2, type2,
1122
0
                                              &result_type);
1123
1124
0
            if (container_nonzero_cardinality(c, result_type)) {
1125
0
                ra_append(&answer->high_low_container, s1, c, result_type);
1126
0
            } else {
1127
0
                container_free(c, result_type);
1128
0
            }
1129
0
            ++pos1;
1130
0
            ++pos2;
1131
0
            if (pos1 == length1) break;
1132
0
            if (pos2 == length2) break;
1133
0
        } else if (s1 < s2) {  // s1 < s2
1134
0
            const int next_pos1 =
1135
0
                ra_advance_until(&x1->high_low_container, s2, pos1);
1136
0
            ra_append_copy_range(&answer->high_low_container,
1137
0
                                 &x1->high_low_container, pos1, next_pos1,
1138
0
                                 is_cow(x1));
1139
            // TODO : perhaps some of the copy_on_write should be based on
1140
            // answer rather than x1 (more stringent?).  Many similar cases
1141
0
            pos1 = next_pos1;
1142
0
            if (pos1 == length1) break;
1143
0
        } else {  // s1 > s2
1144
0
            pos2 = ra_advance_until(&x2->high_low_container, s1, pos2);
1145
0
            if (pos2 == length2) break;
1146
0
        }
1147
0
    }
1148
0
    if (pos2 == length2) {
1149
0
        ra_append_copy_range(&answer->high_low_container,
1150
0
                             &x1->high_low_container, pos1, length1,
1151
0
                             is_cow(x1));
1152
0
    }
1153
0
    return answer;
1154
0
}
1155
1156
// inplace andnot (modifies its first argument).
1157
1158
void roaring_bitmap_andnot_inplace(roaring_bitmap_t *x1,
1159
0
                                   const roaring_bitmap_t *x2) {
1160
0
    assert(x1 != x2);
1161
1162
0
    uint8_t result_type = 0;
1163
0
    int length1 = x1->high_low_container.size;
1164
0
    const int length2 = x2->high_low_container.size;
1165
0
    int intersection_size = 0;
1166
1167
0
    if (0 == length2) return;
1168
1169
0
    if (0 == length1) {
1170
0
        roaring_bitmap_clear(x1);
1171
0
        return;
1172
0
    }
1173
1174
0
    int pos1 = 0, pos2 = 0;
1175
0
    uint8_t type1, type2;
1176
0
    uint16_t s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
1177
0
    uint16_t s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
1178
0
    while (true) {
1179
0
        if (s1 == s2) {
1180
0
            container_t *c1 = ra_get_container_at_index(
1181
0
                                    &x1->high_low_container, pos1, &type1);
1182
0
            container_t *c2 = ra_get_container_at_index(
1183
0
                                    &x2->high_low_container, pos2, &type2);
1184
1185
            // We do the computation "in place" only when c1 is not a shared container.
1186
            // Rationale: using a shared container safely with in place computation would
1187
            // require making a copy and then doing the computation in place which is likely
1188
            // less efficient than avoiding in place entirely and always generating a new
1189
            // container.
1190
1191
0
            container_t *c;
1192
0
            if (type1 == SHARED_CONTAINER_TYPE) {
1193
0
                c = container_andnot(c1, type1, c2, type2, &result_type);
1194
0
                shared_container_free(CAST_shared(c1));  // release
1195
0
            }
1196
0
            else {
1197
0
                c = container_iandnot(c1, type1, c2, type2, &result_type);
1198
0
            }
1199
1200
0
            if (container_nonzero_cardinality(c, result_type)) {
1201
0
                ra_replace_key_and_container_at_index(&x1->high_low_container,
1202
0
                                                      intersection_size++, s1,
1203
0
                                                      c, result_type);
1204
0
            } else {
1205
0
                container_free(c, result_type);
1206
0
            }
1207
1208
0
            ++pos1;
1209
0
            ++pos2;
1210
0
            if (pos1 == length1) break;
1211
0
            if (pos2 == length2) break;
1212
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
1213
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
1214
1215
0
        } else if (s1 < s2) {  // s1 < s2
1216
0
            if (pos1 != intersection_size) {
1217
0
                container_t *c1 = ra_get_container_at_index(
1218
0
                                        &x1->high_low_container, pos1, &type1);
1219
1220
0
                ra_replace_key_and_container_at_index(&x1->high_low_container,
1221
0
                                                      intersection_size, s1, c1,
1222
0
                                                      type1);
1223
0
            }
1224
0
            intersection_size++;
1225
0
            pos1++;
1226
0
            if (pos1 == length1) break;
1227
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
1228
1229
0
        } else {  // s1 > s2
1230
0
            pos2 = ra_advance_until(&x2->high_low_container, s1, pos2);
1231
0
            if (pos2 == length2) break;
1232
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
1233
0
        }
1234
0
    }
1235
1236
0
    if (pos1 < length1) {
1237
        // all containers between intersection_size and
1238
        // pos1 are junk.  However, they have either been moved
1239
        // (thus still referenced) or involved in an iandnot
1240
        // that will clean up all containers that could not be reused.
1241
        // Thus we should not free the junk containers between
1242
        // intersection_size and pos1.
1243
0
        if (pos1 > intersection_size) {
1244
            // left slide of remaining items
1245
0
            ra_copy_range(&x1->high_low_container, pos1, length1,
1246
0
                          intersection_size);
1247
0
        }
1248
        // else current placement is fine
1249
0
        intersection_size += (length1 - pos1);
1250
0
    }
1251
0
    ra_downsize(&x1->high_low_container, intersection_size);
1252
0
}
1253
1254
0
uint64_t roaring_bitmap_get_cardinality(const roaring_bitmap_t *r) {
1255
0
    const roaring_array_t *ra = &r->high_low_container;
1256
1257
0
    uint64_t card = 0;
1258
0
    for (int i = 0; i < ra->size; ++i)
1259
0
        card += container_get_cardinality(ra->containers[i], ra->typecodes[i]);
1260
0
    return card;
1261
0
}
1262
1263
uint64_t roaring_bitmap_range_cardinality(const roaring_bitmap_t *r,
1264
                                          uint64_t range_start,
1265
0
                                          uint64_t range_end) {
1266
0
    const roaring_array_t *ra = &r->high_low_container;
1267
1268
0
    if (range_end > UINT32_MAX) {
1269
0
        range_end = UINT32_MAX + UINT64_C(1);
1270
0
    }
1271
0
    if (range_start >= range_end) {
1272
0
        return 0;
1273
0
    }
1274
0
    range_end--; // make range_end inclusive
1275
    // now we have: 0 <= range_start <= range_end <= UINT32_MAX
1276
1277
0
    uint16_t minhb = range_start >> 16;
1278
0
    uint16_t maxhb = range_end >> 16;
1279
1280
0
    uint64_t card = 0;
1281
1282
0
    int i = ra_get_index(ra, minhb);
1283
0
    if (i >= 0) {
1284
0
        if (minhb == maxhb) {
1285
0
            card += container_rank(ra->containers[i], ra->typecodes[i],
1286
0
                                   range_end & 0xffff);
1287
0
        } else {
1288
0
            card += container_get_cardinality(ra->containers[i],
1289
0
                                              ra->typecodes[i]);
1290
0
        }
1291
0
        if ((range_start & 0xffff) != 0) {
1292
0
            card -= container_rank(ra->containers[i], ra->typecodes[i],
1293
0
                                   (range_start & 0xffff) - 1);
1294
0
        }
1295
0
        i++;
1296
0
    } else {
1297
0
        i = -i - 1;
1298
0
    }
1299
1300
0
    for (; i < ra->size; i++) {
1301
0
        uint16_t key = ra->keys[i];
1302
0
        if (key < maxhb) {
1303
0
            card += container_get_cardinality(ra->containers[i],
1304
0
                                              ra->typecodes[i]);
1305
0
        } else if (key == maxhb) {
1306
0
            card += container_rank(ra->containers[i], ra->typecodes[i],
1307
0
                                   range_end & 0xffff);
1308
0
            break;
1309
0
        } else {
1310
0
            break;
1311
0
        }
1312
0
    }
1313
1314
0
    return card;
1315
0
}
1316
1317
1318
0
bool roaring_bitmap_is_empty(const roaring_bitmap_t *r) {
1319
0
    return r->high_low_container.size == 0;
1320
0
}
1321
1322
0
void roaring_bitmap_to_uint32_array(const roaring_bitmap_t *r, uint32_t *ans) {
1323
0
    ra_to_uint32_array(&r->high_low_container, ans);
1324
0
}
1325
1326
bool roaring_bitmap_range_uint32_array(const roaring_bitmap_t *r,
1327
                                       size_t offset, size_t limit,
1328
0
                                       uint32_t *ans) {
1329
0
    return ra_range_uint32_array(&r->high_low_container, offset, limit, ans);
1330
0
}
1331
1332
/** convert array and bitmap containers to run containers when it is more
1333
 * efficient;
1334
 * also convert from run containers when more space efficient.  Returns
1335
 * true if the result has at least one run container.
1336
*/
1337
0
bool roaring_bitmap_run_optimize(roaring_bitmap_t *r) {
1338
0
    bool answer = false;
1339
0
    for (int i = 0; i < r->high_low_container.size; i++) {
1340
0
        uint8_t type_original, type_after;
1341
0
        ra_unshare_container_at_index(
1342
0
            &r->high_low_container, i);  // TODO: this introduces extra cloning!
1343
0
        container_t *c = ra_get_container_at_index(&r->high_low_container, i,
1344
0
                                                   &type_original);
1345
0
        container_t *c1 = convert_run_optimize(c, type_original, &type_after);
1346
0
        if (type_after == RUN_CONTAINER_TYPE) {
1347
0
            answer = true;
1348
0
        }
1349
0
        ra_set_container_at_index(&r->high_low_container, i, c1, type_after);
1350
0
    }
1351
0
    return answer;
1352
0
}
1353
1354
0
size_t roaring_bitmap_shrink_to_fit(roaring_bitmap_t *r) {
1355
0
    size_t answer = 0;
1356
0
    for (int i = 0; i < r->high_low_container.size; i++) {
1357
0
        uint8_t type_original;
1358
0
        container_t *c = ra_get_container_at_index(&r->high_low_container, i,
1359
0
                                                   &type_original);
1360
0
        answer += container_shrink_to_fit(c, type_original);
1361
0
    }
1362
0
    answer += ra_shrink_to_fit(&r->high_low_container);
1363
0
    return answer;
1364
0
}
1365
1366
/**
1367
 *  Remove run-length encoding even when it is more space efficient
1368
 *  return whether a change was applied
1369
 */
1370
0
bool roaring_bitmap_remove_run_compression(roaring_bitmap_t *r) {
1371
0
    bool answer = false;
1372
0
    for (int i = 0; i < r->high_low_container.size; i++) {
1373
0
        uint8_t type_original, type_after;
1374
0
        container_t *c = ra_get_container_at_index(&r->high_low_container, i,
1375
0
                                                   &type_original);
1376
0
        if (get_container_type(c, type_original) == RUN_CONTAINER_TYPE) {
1377
0
            answer = true;
1378
0
            if (type_original == SHARED_CONTAINER_TYPE) {
1379
0
                run_container_t *truec = CAST_run(CAST_shared(c)->container);
1380
0
                int32_t card = run_container_cardinality(truec);
1381
0
                container_t *c1 = convert_to_bitset_or_array_container(
1382
0
                                        truec, card, &type_after);
1383
0
                shared_container_free(CAST_shared(c));  // frees run as needed
1384
0
                ra_set_container_at_index(&r->high_low_container, i, c1,
1385
0
                                          type_after);
1386
1387
0
            } else {
1388
0
                int32_t card = run_container_cardinality(CAST_run(c));
1389
0
                container_t *c1 = convert_to_bitset_or_array_container(
1390
0
                                    CAST_run(c), card, &type_after);
1391
0
                run_container_free(CAST_run(c));
1392
0
                ra_set_container_at_index(&r->high_low_container, i, c1,
1393
0
                                          type_after);
1394
0
            }
1395
0
        }
1396
0
    }
1397
0
    return answer;
1398
0
}
1399
1400
0
size_t roaring_bitmap_serialize(const roaring_bitmap_t *r, char *buf) {
1401
0
    size_t portablesize = roaring_bitmap_portable_size_in_bytes(r);
1402
0
    uint64_t cardinality = roaring_bitmap_get_cardinality(r);
1403
0
    uint64_t sizeasarray = cardinality * sizeof(uint32_t) + sizeof(uint32_t);
1404
0
    if (portablesize < sizeasarray) {
1405
0
        buf[0] = CROARING_SERIALIZATION_CONTAINER;
1406
0
        return roaring_bitmap_portable_serialize(r, buf + 1) + 1;
1407
0
    } else {
1408
0
        buf[0] = CROARING_SERIALIZATION_ARRAY_UINT32;
1409
0
        memcpy(buf + 1, &cardinality, sizeof(uint32_t));
1410
0
        roaring_bitmap_to_uint32_array(
1411
0
            r, (uint32_t *)(buf + 1 + sizeof(uint32_t)));
1412
0
        return 1 + (size_t)sizeasarray;
1413
0
    }
1414
0
}
1415
1416
0
size_t roaring_bitmap_size_in_bytes(const roaring_bitmap_t *r) {
1417
0
    size_t portablesize = roaring_bitmap_portable_size_in_bytes(r);
1418
0
    uint64_t sizeasarray = roaring_bitmap_get_cardinality(r) * sizeof(uint32_t) +
1419
0
                         sizeof(uint32_t);
1420
0
    return portablesize < sizeasarray ? portablesize + 1 : (size_t)sizeasarray + 1;
1421
0
}
1422
1423
0
size_t roaring_bitmap_portable_size_in_bytes(const roaring_bitmap_t *r) {
1424
0
    return ra_portable_size_in_bytes(&r->high_low_container);
1425
0
}
1426
1427
1428
647
roaring_bitmap_t *roaring_bitmap_portable_deserialize_safe(const char *buf, size_t maxbytes) {
1429
647
    roaring_bitmap_t *ans =
1430
647
        (roaring_bitmap_t *)roaring_malloc(sizeof(roaring_bitmap_t));
1431
647
    if (ans == NULL) {
1432
0
        return NULL;
1433
0
    }
1434
647
    size_t bytesread;
1435
647
    bool is_ok = ra_portable_deserialize(&ans->high_low_container, buf, maxbytes, &bytesread);
1436
647
    if(is_ok) assert(bytesread <= maxbytes);
1437
647
    roaring_bitmap_set_copy_on_write(ans, false);
1438
647
    if (!is_ok) {
1439
525
        roaring_free(ans);
1440
525
        return NULL;
1441
525
    }
1442
122
    return ans;
1443
647
}
1444
1445
0
roaring_bitmap_t *roaring_bitmap_portable_deserialize(const char *buf) {
1446
0
    return roaring_bitmap_portable_deserialize_safe(buf, SIZE_MAX);
1447
0
}
1448
1449
1450
0
size_t roaring_bitmap_portable_deserialize_size(const char *buf, size_t maxbytes) {
1451
0
  return ra_portable_deserialize_size(buf, maxbytes);
1452
0
}
1453
1454
1455
size_t roaring_bitmap_portable_serialize(const roaring_bitmap_t *r,
1456
0
                                         char *buf) {
1457
0
    return ra_portable_serialize(&r->high_low_container, buf);
1458
0
}
1459
1460
0
roaring_bitmap_t *roaring_bitmap_deserialize(const void *buf) {
1461
0
    const char *bufaschar = (const char *)buf;
1462
0
    if (bufaschar[0] == CROARING_SERIALIZATION_ARRAY_UINT32) {
1463
        /* This looks like a compressed set of uint32_t elements */
1464
0
        uint32_t card;
1465
0
        memcpy(&card, bufaschar + 1, sizeof(uint32_t));
1466
0
        const uint32_t *elems =
1467
0
            (const uint32_t *)(bufaschar + 1 + sizeof(uint32_t));
1468
0
        roaring_bitmap_t *bitmap = roaring_bitmap_create();
1469
0
        if (bitmap == NULL) {
1470
0
            return NULL;
1471
0
        }
1472
0
        roaring_bulk_context_t context = {0};
1473
0
        for (uint32_t i = 0; i < card; i++) {
1474
            // elems may not be aligned, read with memcpy
1475
0
            uint32_t elem;
1476
0
            memcpy(&elem, elems + i, sizeof(elem));
1477
0
            roaring_bitmap_add_bulk(bitmap, &context, elem);
1478
0
        }
1479
0
        return bitmap;
1480
0
    } else if (bufaschar[0] == CROARING_SERIALIZATION_CONTAINER) {
1481
0
        return roaring_bitmap_portable_deserialize(bufaschar + 1);
1482
0
    } else
1483
0
        return (NULL);
1484
0
}
1485
1486
bool roaring_iterate(const roaring_bitmap_t *r, roaring_iterator iterator,
1487
0
                     void *ptr) {
1488
0
    const roaring_array_t *ra = &r->high_low_container;
1489
1490
0
    for (int i = 0; i < ra->size; ++i)
1491
0
        if (!container_iterate(ra->containers[i], ra->typecodes[i],
1492
0
                               ((uint32_t)ra->keys[i]) << 16,
1493
0
                               iterator, ptr)) {
1494
0
            return false;
1495
0
        }
1496
0
    return true;
1497
0
}
1498
1499
bool roaring_iterate64(const roaring_bitmap_t *r, roaring_iterator64 iterator,
1500
0
                       uint64_t high_bits, void *ptr) {
1501
0
    const roaring_array_t *ra = &r->high_low_container;
1502
1503
0
    for (int i = 0; i < ra->size; ++i)
1504
0
        if (!container_iterate64(
1505
0
                ra->containers[i], ra->typecodes[i],
1506
0
                ((uint32_t)ra->keys[i]) << 16, iterator,
1507
0
                high_bits, ptr)) {
1508
0
            return false;
1509
0
        }
1510
0
    return true;
1511
0
}
1512
1513
/****
1514
* begin roaring_uint32_iterator_t
1515
*****/
1516
1517
// Partially initializes the roaring iterator when it begins looking at
1518
// a new container.
1519
0
static bool iter_new_container_partial_init(roaring_uint32_iterator_t *newit) {
1520
0
    newit->in_container_index = 0;
1521
0
    newit->run_index = 0;
1522
0
    newit->current_value = 0;
1523
0
    if (newit->container_index >= newit->parent->high_low_container.size ||
1524
0
        newit->container_index < 0) {
1525
0
        newit->current_value = UINT32_MAX;
1526
0
        return (newit->has_value = false);
1527
0
    }
1528
    // assume not empty
1529
0
    newit->has_value = true;
1530
    // we precompute container, typecode and highbits so that successive
1531
    // iterators do not have to grab them from odd memory locations
1532
    // and have to worry about the (easily predicted) container_unwrap_shared
1533
    // call.
1534
0
    newit->container =
1535
0
            newit->parent->high_low_container.containers[newit->container_index];
1536
0
    newit->typecode =
1537
0
            newit->parent->high_low_container.typecodes[newit->container_index];
1538
0
    newit->highbits =
1539
0
            ((uint32_t)
1540
0
                    newit->parent->high_low_container.keys[newit->container_index])
1541
0
                    << 16;
1542
0
    newit->container =
1543
0
            container_unwrap_shared(newit->container, &(newit->typecode));
1544
0
    return newit->has_value;
1545
0
}
1546
1547
0
static bool loadfirstvalue(roaring_uint32_iterator_t *newit) {
1548
0
    if (!iter_new_container_partial_init(newit))
1549
0
        return newit->has_value;
1550
1551
0
    switch (newit->typecode) {
1552
0
        case BITSET_CONTAINER_TYPE: {
1553
0
            const bitset_container_t *bc = const_CAST_bitset(newit->container);
1554
1555
0
            uint32_t wordindex = 0;
1556
0
            uint64_t word;
1557
0
            while ((word = bc->words[wordindex]) == 0) {
1558
0
                wordindex++;  // advance
1559
0
            }
1560
            // here "word" is non-zero
1561
0
            newit->in_container_index = wordindex * 64 + __builtin_ctzll(word);
1562
0
            newit->current_value = newit->highbits | newit->in_container_index;
1563
0
            break; }
1564
1565
0
        case ARRAY_CONTAINER_TYPE: {
1566
0
            const array_container_t *ac = const_CAST_array(newit->container);
1567
0
            newit->current_value = newit->highbits | ac->array[0];
1568
0
            break; }
1569
1570
0
        case RUN_CONTAINER_TYPE: {
1571
0
            const run_container_t *rc = const_CAST_run(newit->container);
1572
0
            newit->current_value = newit->highbits | rc->runs[0].value;
1573
0
            break; }
1574
1575
0
        default:
1576
            // if this ever happens, bug!
1577
0
            assert(false);
1578
0
    }  // switch (typecode)
1579
0
    return true;
1580
0
}
1581
1582
0
static bool loadlastvalue(roaring_uint32_iterator_t* newit) {
1583
0
    if (!iter_new_container_partial_init(newit))
1584
0
        return newit->has_value;
1585
1586
0
    switch(newit->typecode) {
1587
0
        case BITSET_CONTAINER_TYPE: {
1588
0
            uint32_t wordindex = BITSET_CONTAINER_SIZE_IN_WORDS - 1;
1589
0
            uint64_t word;
1590
0
            const bitset_container_t* bitset_container = (const bitset_container_t*)newit->container;
1591
0
            while ((word = bitset_container->words[wordindex]) == 0)
1592
0
                --wordindex;
1593
1594
0
            int num_leading_zeros = __builtin_clzll(word);
1595
0
            newit->in_container_index = (wordindex * 64) + (63 - num_leading_zeros);
1596
0
            newit->current_value = newit->highbits | newit->in_container_index;
1597
0
            break;
1598
0
        }
1599
0
        case ARRAY_CONTAINER_TYPE: {
1600
0
            const array_container_t* array_container = (const array_container_t*)newit->container;
1601
0
            newit->in_container_index = array_container->cardinality - 1;
1602
0
            newit->current_value = newit->highbits | array_container->array[newit->in_container_index];
1603
0
            break;
1604
0
        }
1605
0
        case RUN_CONTAINER_TYPE: {
1606
0
            const run_container_t* run_container = (const run_container_t*)newit->container;
1607
0
            newit->run_index = run_container->n_runs - 1;
1608
0
            const rle16_t* last_run = &run_container->runs[newit->run_index];
1609
0
            newit->current_value = newit->highbits | (last_run->value + last_run->length);
1610
0
            break;
1611
0
        }
1612
0
        default:
1613
            // if this ever happens, bug!
1614
0
            assert(false);
1615
0
    }
1616
0
    return true;
1617
0
}
1618
1619
// prerequesite: the value should be in range of the container
1620
0
static bool loadfirstvalue_largeorequal(roaring_uint32_iterator_t *newit, uint32_t val) {
1621
    // Don't have to check return value because of prerequisite
1622
0
    iter_new_container_partial_init(newit);
1623
0
    uint16_t lb = val & 0xFFFF;
1624
1625
0
    switch (newit->typecode) {
1626
0
        case BITSET_CONTAINER_TYPE: {
1627
0
            const bitset_container_t *bc = const_CAST_bitset(newit->container);
1628
0
            newit->in_container_index =
1629
0
                        bitset_container_index_equalorlarger(bc, lb);
1630
0
            newit->current_value = newit->highbits | newit->in_container_index;
1631
0
            break; }
1632
1633
0
        case ARRAY_CONTAINER_TYPE: {
1634
0
            const array_container_t *ac = const_CAST_array(newit->container);
1635
0
            newit->in_container_index =
1636
0
                        array_container_index_equalorlarger(ac, lb);
1637
0
            newit->current_value =
1638
0
                        newit->highbits | ac->array[newit->in_container_index];
1639
0
            break; }
1640
1641
0
        case RUN_CONTAINER_TYPE: {
1642
0
            const run_container_t *rc = const_CAST_run(newit->container);
1643
0
            newit->run_index = run_container_index_equalorlarger(rc, lb);
1644
0
            if (rc->runs[newit->run_index].value <= lb) {
1645
0
                newit->current_value = val;
1646
0
            } else {
1647
0
                newit->current_value =
1648
0
                        newit->highbits | rc->runs[newit->run_index].value;
1649
0
            }
1650
0
            break; }
1651
1652
0
        default:
1653
0
            __builtin_unreachable();
1654
0
    }
1655
1656
0
    return true;
1657
0
}
1658
1659
void roaring_init_iterator(const roaring_bitmap_t *r,
1660
0
                           roaring_uint32_iterator_t *newit) {
1661
0
    newit->parent = r;
1662
0
    newit->container_index = 0;
1663
0
    newit->has_value = loadfirstvalue(newit);
1664
0
}
1665
1666
void roaring_init_iterator_last(const roaring_bitmap_t *r,
1667
0
                                roaring_uint32_iterator_t *newit) {
1668
0
    newit->parent = r;
1669
0
    newit->container_index = newit->parent->high_low_container.size - 1;
1670
0
    newit->has_value = loadlastvalue(newit);
1671
0
}
1672
1673
0
roaring_uint32_iterator_t *roaring_create_iterator(const roaring_bitmap_t *r) {
1674
0
    roaring_uint32_iterator_t *newit =
1675
0
        (roaring_uint32_iterator_t *)roaring_malloc(sizeof(roaring_uint32_iterator_t));
1676
0
    if (newit == NULL) return NULL;
1677
0
    roaring_init_iterator(r, newit);
1678
0
    return newit;
1679
0
}
1680
1681
roaring_uint32_iterator_t *roaring_copy_uint32_iterator(
1682
0
    const roaring_uint32_iterator_t *it) {
1683
0
    roaring_uint32_iterator_t *newit =
1684
0
        (roaring_uint32_iterator_t *)roaring_malloc(sizeof(roaring_uint32_iterator_t));
1685
0
    memcpy(newit, it, sizeof(roaring_uint32_iterator_t));
1686
0
    return newit;
1687
0
}
1688
1689
0
bool roaring_move_uint32_iterator_equalorlarger(roaring_uint32_iterator_t *it, uint32_t val) {
1690
0
    uint16_t hb = val >> 16;
1691
0
    const int i = ra_get_index(& it->parent->high_low_container, hb);
1692
0
    if (i >= 0) {
1693
0
      uint32_t lowvalue = container_maximum(it->parent->high_low_container.containers[i], it->parent->high_low_container.typecodes[i]);
1694
0
      uint16_t lb = val & 0xFFFF;
1695
0
      if(lowvalue < lb ) {
1696
0
        it->container_index = i+1; // will have to load first value of next container
1697
0
      } else {// the value is necessarily within the range of the container
1698
0
        it->container_index = i;
1699
0
        it->has_value = loadfirstvalue_largeorequal(it, val);
1700
0
        return it->has_value;
1701
0
      }
1702
0
    } else {
1703
      // there is no matching, so we are going for the next container
1704
0
      it->container_index = -i-1;
1705
0
    }
1706
0
    it->has_value = loadfirstvalue(it);
1707
0
    return it->has_value;
1708
0
}
1709
1710
1711
0
bool roaring_advance_uint32_iterator(roaring_uint32_iterator_t *it) {
1712
0
    if (it->container_index >= it->parent->high_low_container.size) {
1713
0
        return (it->has_value = false);
1714
0
    }
1715
0
    if (it->container_index < 0) {
1716
0
        it->container_index = 0;
1717
0
        return (it->has_value = loadfirstvalue(it));
1718
0
    }
1719
1720
0
    switch (it->typecode) {
1721
0
        case BITSET_CONTAINER_TYPE: {
1722
0
            const bitset_container_t *bc = const_CAST_bitset(it->container);
1723
0
            it->in_container_index++;
1724
1725
0
            uint32_t wordindex = it->in_container_index / 64;
1726
0
            if (wordindex >= BITSET_CONTAINER_SIZE_IN_WORDS) break;
1727
1728
0
            uint64_t word = bc->words[wordindex] &
1729
0
                   (UINT64_MAX << (it->in_container_index % 64));
1730
            // next part could be optimized/simplified
1731
0
            while ((word == 0) &&
1732
0
                   (wordindex + 1 < BITSET_CONTAINER_SIZE_IN_WORDS)) {
1733
0
                wordindex++;
1734
0
                word = bc->words[wordindex];
1735
0
            }
1736
0
            if (word != 0) {
1737
0
                it->in_container_index = wordindex * 64 + __builtin_ctzll(word);
1738
0
                it->current_value = it->highbits | it->in_container_index;
1739
0
                return (it->has_value = true);
1740
0
            }
1741
0
            break; }
1742
1743
0
        case ARRAY_CONTAINER_TYPE: {
1744
0
            const array_container_t *ac = const_CAST_array(it->container);
1745
0
            it->in_container_index++;
1746
0
            if (it->in_container_index < ac->cardinality) {
1747
0
                it->current_value =
1748
0
                        it->highbits | ac->array[it->in_container_index];
1749
0
                return (it->has_value = true);
1750
0
            }
1751
0
            break; }
1752
1753
0
        case RUN_CONTAINER_TYPE: {
1754
0
            if(it->current_value == UINT32_MAX) {  // avoid overflow to zero
1755
0
                return (it->has_value = false);
1756
0
            }
1757
1758
0
            const run_container_t* rc = const_CAST_run(it->container);
1759
0
            uint32_t limit = (it->highbits | (rc->runs[it->run_index].value +
1760
0
                                              rc->runs[it->run_index].length));
1761
0
            if (++it->current_value <= limit) {
1762
0
                return (it->has_value = true);
1763
0
            }
1764
1765
0
            if (++it->run_index < rc->n_runs) {  // Assume the run has a value
1766
0
                it->current_value =
1767
0
                        it->highbits | rc->runs[it->run_index].value;
1768
0
                return (it->has_value = true);
1769
0
            }
1770
0
            break;
1771
0
        }
1772
1773
0
        default:
1774
0
            __builtin_unreachable();
1775
0
    }
1776
1777
    // moving to next container
1778
0
    it->container_index++;
1779
0
    return (it->has_value = loadfirstvalue(it));
1780
0
}
1781
1782
0
bool roaring_previous_uint32_iterator(roaring_uint32_iterator_t *it) {
1783
0
    if (it->container_index < 0) {
1784
0
        return (it->has_value = false);
1785
0
    }
1786
0
    if (it->container_index >= it->parent->high_low_container.size) {
1787
0
        it->container_index = it->parent->high_low_container.size - 1;
1788
0
        return (it->has_value = loadlastvalue(it));
1789
0
    }
1790
1791
0
    switch (it->typecode) {
1792
0
        case BITSET_CONTAINER_TYPE: {
1793
0
            if (--it->in_container_index < 0)
1794
0
                break;
1795
1796
0
            const bitset_container_t* bitset_container = (const bitset_container_t*)it->container;
1797
0
            int32_t wordindex = it->in_container_index / 64;
1798
0
            uint64_t word = bitset_container->words[wordindex] & (UINT64_MAX >> (63 - (it->in_container_index % 64)));
1799
1800
0
            while (word == 0 && --wordindex >= 0) {
1801
0
                word = bitset_container->words[wordindex];
1802
0
            }
1803
0
            if (word == 0)
1804
0
                break;
1805
1806
0
            int num_leading_zeros = __builtin_clzll(word);
1807
0
            it->in_container_index = (wordindex * 64) + (63 - num_leading_zeros);
1808
0
            it->current_value = it->highbits | it->in_container_index;
1809
0
            return (it->has_value = true);
1810
0
        }
1811
0
        case ARRAY_CONTAINER_TYPE: {
1812
0
            if (--it->in_container_index < 0)
1813
0
                break;
1814
1815
0
            const array_container_t* array_container = (const array_container_t*)it->container;
1816
0
            it->current_value = it->highbits | array_container->array[it->in_container_index];
1817
0
            return (it->has_value = true);
1818
0
        }
1819
0
        case RUN_CONTAINER_TYPE: {
1820
0
            if(it->current_value == 0)
1821
0
                return (it->has_value = false);
1822
1823
0
            const run_container_t* run_container = (const run_container_t*)it->container;
1824
0
            if (--it->current_value >= (it->highbits | run_container->runs[it->run_index].value)) {
1825
0
                return (it->has_value = true);
1826
0
            }
1827
1828
0
            if (--it->run_index < 0)
1829
0
                break;
1830
1831
0
            it->current_value = it->highbits | (run_container->runs[it->run_index].value +
1832
0
                                                run_container->runs[it->run_index].length);
1833
0
            return (it->has_value = true);
1834
0
        }
1835
0
        default:
1836
            // if this ever happens, bug!
1837
0
            assert(false);
1838
0
    }  // switch (typecode)
1839
1840
    // moving to previous container
1841
0
    it->container_index--;
1842
0
    return (it->has_value = loadlastvalue(it));
1843
0
}
1844
1845
0
uint32_t roaring_read_uint32_iterator(roaring_uint32_iterator_t *it, uint32_t* buf, uint32_t count) {
1846
0
  uint32_t ret = 0;
1847
0
  uint32_t num_values;
1848
0
  uint32_t wordindex;  // used for bitsets
1849
0
  uint64_t word;       // used for bitsets
1850
0
  const array_container_t* acont; //TODO remove
1851
0
  const run_container_t* rcont; //TODO remove
1852
0
  const bitset_container_t* bcont; //TODO remove
1853
1854
0
  while (it->has_value && ret < count) {
1855
0
    switch (it->typecode) {
1856
0
      case BITSET_CONTAINER_TYPE:
1857
0
        bcont = const_CAST_bitset(it->container);
1858
0
        wordindex = it->in_container_index / 64;
1859
0
        word = bcont->words[wordindex] & (UINT64_MAX << (it->in_container_index % 64));
1860
0
        do {
1861
0
          while (word != 0 && ret < count) {
1862
0
            buf[0] = it->highbits | (wordindex * 64 + __builtin_ctzll(word));
1863
0
            word = word & (word - 1);
1864
0
            buf++;
1865
0
            ret++;
1866
0
          }
1867
0
          while (word == 0 && wordindex+1 < BITSET_CONTAINER_SIZE_IN_WORDS) {
1868
0
            wordindex++;
1869
0
            word = bcont->words[wordindex];
1870
0
          }
1871
0
        } while (word != 0 && ret < count);
1872
0
        it->has_value = (word != 0);
1873
0
        if (it->has_value) {
1874
0
          it->in_container_index = wordindex * 64 + __builtin_ctzll(word);
1875
0
          it->current_value = it->highbits | it->in_container_index;
1876
0
        }
1877
0
        break;
1878
0
      case ARRAY_CONTAINER_TYPE:
1879
0
        acont = const_CAST_array(it->container);
1880
0
        num_values = minimum_uint32(acont->cardinality - it->in_container_index, count - ret);
1881
0
        for (uint32_t i = 0; i < num_values; i++) {
1882
0
          buf[i] = it->highbits | acont->array[it->in_container_index + i];
1883
0
        }
1884
0
        buf += num_values;
1885
0
        ret += num_values;
1886
0
        it->in_container_index += num_values;
1887
0
        it->has_value = (it->in_container_index < acont->cardinality);
1888
0
        if (it->has_value) {
1889
0
          it->current_value = it->highbits | acont->array[it->in_container_index];
1890
0
        }
1891
0
        break;
1892
0
      case RUN_CONTAINER_TYPE:
1893
0
        rcont = const_CAST_run(it->container);
1894
        //"in_run_index" name is misleading, read it as "max_value_in_current_run"
1895
0
        do {
1896
0
          uint32_t largest_run_value = it->highbits | (rcont->runs[it->run_index].value + rcont->runs[it->run_index].length);
1897
0
          num_values = minimum_uint32(largest_run_value - it->current_value + 1, count - ret);
1898
0
          for (uint32_t i = 0; i < num_values; i++) {
1899
0
            buf[i] = it->current_value + i;
1900
0
          }
1901
0
          it->current_value += num_values; // this can overflow to zero: UINT32_MAX+1=0
1902
0
          buf += num_values;
1903
0
          ret += num_values;
1904
1905
0
          if (it->current_value > largest_run_value || it->current_value == 0) {
1906
0
            it->run_index++;
1907
0
            if (it->run_index < rcont->n_runs) {
1908
0
              it->current_value = it->highbits | rcont->runs[it->run_index].value;
1909
0
            } else {
1910
0
              it->has_value = false;
1911
0
            }
1912
0
          }
1913
0
        } while ((ret < count) && it->has_value);
1914
0
        break;
1915
0
      default:
1916
0
        assert(false);
1917
0
    }
1918
0
    if (it->has_value) {
1919
0
      assert(ret == count);
1920
0
      return ret;
1921
0
    }
1922
0
    it->container_index++;
1923
0
    it->has_value = loadfirstvalue(it);
1924
0
  }
1925
0
  return ret;
1926
0
}
1927
1928
1929
1930
0
void roaring_free_uint32_iterator(roaring_uint32_iterator_t *it) { roaring_free(it); }
1931
1932
/****
1933
* end of roaring_uint32_iterator_t
1934
*****/
1935
1936
bool roaring_bitmap_equals(const roaring_bitmap_t *r1,
1937
0
                           const roaring_bitmap_t *r2) {
1938
0
    const roaring_array_t *ra1 = &r1->high_low_container;
1939
0
    const roaring_array_t *ra2 = &r2->high_low_container;
1940
1941
0
    if (ra1->size != ra2->size) {
1942
0
        return false;
1943
0
    }
1944
0
    for (int i = 0; i < ra1->size; ++i) {
1945
0
        if (ra1->keys[i] != ra2->keys[i]) {
1946
0
            return false;
1947
0
        }
1948
0
    }
1949
0
    for (int i = 0; i < ra1->size; ++i) {
1950
0
        bool areequal = container_equals(ra1->containers[i],
1951
0
                                         ra1->typecodes[i],
1952
0
                                         ra2->containers[i],
1953
0
                                         ra2->typecodes[i]);
1954
0
        if (!areequal) {
1955
0
            return false;
1956
0
        }
1957
0
    }
1958
0
    return true;
1959
0
}
1960
1961
bool roaring_bitmap_is_subset(const roaring_bitmap_t *r1,
1962
0
                              const roaring_bitmap_t *r2) {
1963
0
    const roaring_array_t *ra1 = &r1->high_low_container;
1964
0
    const roaring_array_t *ra2 = &r2->high_low_container;
1965
1966
0
    const int length1 = ra1->size,
1967
0
              length2 = ra2->size;
1968
1969
0
    int pos1 = 0, pos2 = 0;
1970
1971
0
    while (pos1 < length1 && pos2 < length2) {
1972
0
        const uint16_t s1 = ra_get_key_at_index(ra1, pos1);
1973
0
        const uint16_t s2 = ra_get_key_at_index(ra2, pos2);
1974
1975
0
        if (s1 == s2) {
1976
0
            uint8_t type1, type2;
1977
0
            container_t *c1 = ra_get_container_at_index(ra1, pos1, &type1);
1978
0
            container_t *c2 = ra_get_container_at_index(ra2, pos2, &type2);
1979
0
            if (!container_is_subset(c1, type1, c2, type2))
1980
0
                return false;
1981
0
            ++pos1;
1982
0
            ++pos2;
1983
0
        } else if (s1 < s2) {  // s1 < s2
1984
0
            return false;
1985
0
        } else {  // s1 > s2
1986
0
            pos2 = ra_advance_until(ra2, s1, pos2);
1987
0
        }
1988
0
    }
1989
0
    if (pos1 == length1)
1990
0
        return true;
1991
0
    else
1992
0
        return false;
1993
0
}
1994
1995
static void insert_flipped_container(roaring_array_t *ans_arr,
1996
                                     const roaring_array_t *x1_arr, uint16_t hb,
1997
0
                                     uint16_t lb_start, uint16_t lb_end) {
1998
0
    const int i = ra_get_index(x1_arr, hb);
1999
0
    const int j = ra_get_index(ans_arr, hb);
2000
0
    uint8_t ctype_in, ctype_out;
2001
0
    container_t *flipped_container = NULL;
2002
0
    if (i >= 0) {
2003
0
        container_t *container_to_flip =
2004
0
            ra_get_container_at_index(x1_arr, i, &ctype_in);
2005
0
        flipped_container =
2006
0
            container_not_range(container_to_flip, ctype_in, (uint32_t)lb_start,
2007
0
                                (uint32_t)(lb_end + 1), &ctype_out);
2008
2009
0
        if (container_get_cardinality(flipped_container, ctype_out))
2010
0
            ra_insert_new_key_value_at(ans_arr, -j - 1, hb, flipped_container,
2011
0
                                       ctype_out);
2012
0
        else {
2013
0
            container_free(flipped_container, ctype_out);
2014
0
        }
2015
0
    } else {
2016
0
        flipped_container = container_range_of_ones(
2017
0
            (uint32_t)lb_start, (uint32_t)(lb_end + 1), &ctype_out);
2018
0
        ra_insert_new_key_value_at(ans_arr, -j - 1, hb, flipped_container,
2019
0
                                   ctype_out);
2020
0
    }
2021
0
}
2022
2023
static void inplace_flip_container(roaring_array_t *x1_arr, uint16_t hb,
2024
0
                                   uint16_t lb_start, uint16_t lb_end) {
2025
0
    const int i = ra_get_index(x1_arr, hb);
2026
0
    uint8_t ctype_in, ctype_out;
2027
0
    container_t *flipped_container = NULL;
2028
0
    if (i >= 0) {
2029
0
        container_t *container_to_flip =
2030
0
            ra_get_container_at_index(x1_arr, i, &ctype_in);
2031
0
        flipped_container = container_inot_range(
2032
0
            container_to_flip, ctype_in, (uint32_t)lb_start,
2033
0
            (uint32_t)(lb_end + 1), &ctype_out);
2034
        // if a new container was created, the old one was already freed
2035
0
        if (container_get_cardinality(flipped_container, ctype_out)) {
2036
0
            ra_set_container_at_index(x1_arr, i, flipped_container, ctype_out);
2037
0
        } else {
2038
0
            container_free(flipped_container, ctype_out);
2039
0
            ra_remove_at_index(x1_arr, i);
2040
0
        }
2041
2042
0
    } else {
2043
0
        flipped_container = container_range_of_ones(
2044
0
            (uint32_t)lb_start, (uint32_t)(lb_end + 1), &ctype_out);
2045
0
        ra_insert_new_key_value_at(x1_arr, -i - 1, hb, flipped_container,
2046
0
                                   ctype_out);
2047
0
    }
2048
0
}
2049
2050
static void insert_fully_flipped_container(roaring_array_t *ans_arr,
2051
                                           const roaring_array_t *x1_arr,
2052
0
                                           uint16_t hb) {
2053
0
    const int i = ra_get_index(x1_arr, hb);
2054
0
    const int j = ra_get_index(ans_arr, hb);
2055
0
    uint8_t ctype_in, ctype_out;
2056
0
    container_t *flipped_container = NULL;
2057
0
    if (i >= 0) {
2058
0
        container_t *container_to_flip =
2059
0
            ra_get_container_at_index(x1_arr, i, &ctype_in);
2060
0
        flipped_container =
2061
0
            container_not(container_to_flip, ctype_in, &ctype_out);
2062
0
        if (container_get_cardinality(flipped_container, ctype_out))
2063
0
            ra_insert_new_key_value_at(ans_arr, -j - 1, hb, flipped_container,
2064
0
                                       ctype_out);
2065
0
        else {
2066
0
            container_free(flipped_container, ctype_out);
2067
0
        }
2068
0
    } else {
2069
0
        flipped_container = container_range_of_ones(0U, 0x10000U, &ctype_out);
2070
0
        ra_insert_new_key_value_at(ans_arr, -j - 1, hb, flipped_container,
2071
0
                                   ctype_out);
2072
0
    }
2073
0
}
2074
2075
0
static void inplace_fully_flip_container(roaring_array_t *x1_arr, uint16_t hb) {
2076
0
    const int i = ra_get_index(x1_arr, hb);
2077
0
    uint8_t ctype_in, ctype_out;
2078
0
    container_t *flipped_container = NULL;
2079
0
    if (i >= 0) {
2080
0
        container_t *container_to_flip =
2081
0
            ra_get_container_at_index(x1_arr, i, &ctype_in);
2082
0
        flipped_container =
2083
0
            container_inot(container_to_flip, ctype_in, &ctype_out);
2084
2085
0
        if (container_get_cardinality(flipped_container, ctype_out)) {
2086
0
            ra_set_container_at_index(x1_arr, i, flipped_container, ctype_out);
2087
0
        } else {
2088
0
            container_free(flipped_container, ctype_out);
2089
0
            ra_remove_at_index(x1_arr, i);
2090
0
        }
2091
2092
0
    } else {
2093
0
        flipped_container = container_range_of_ones(0U, 0x10000U, &ctype_out);
2094
0
        ra_insert_new_key_value_at(x1_arr, -i - 1, hb, flipped_container,
2095
0
                                   ctype_out);
2096
0
    }
2097
0
}
2098
2099
roaring_bitmap_t *roaring_bitmap_flip(const roaring_bitmap_t *x1,
2100
                                      uint64_t range_start,
2101
0
                                      uint64_t range_end) {
2102
0
    if (range_start >= range_end) {
2103
0
        return roaring_bitmap_copy(x1);
2104
0
    }
2105
0
    if(range_end >= UINT64_C(0x100000000)) {
2106
0
        range_end = UINT64_C(0x100000000);
2107
0
    }
2108
2109
0
    roaring_bitmap_t *ans = roaring_bitmap_create();
2110
0
    roaring_bitmap_set_copy_on_write(ans, is_cow(x1));
2111
2112
0
    uint16_t hb_start = (uint16_t)(range_start >> 16);
2113
0
    const uint16_t lb_start = (uint16_t)range_start;  // & 0xFFFF;
2114
0
    uint16_t hb_end = (uint16_t)((range_end - 1) >> 16);
2115
0
    const uint16_t lb_end = (uint16_t)(range_end - 1);  // & 0xFFFF;
2116
2117
0
    ra_append_copies_until(&ans->high_low_container, &x1->high_low_container,
2118
0
                           hb_start, is_cow(x1));
2119
0
    if (hb_start == hb_end) {
2120
0
        insert_flipped_container(&ans->high_low_container,
2121
0
                                 &x1->high_low_container, hb_start, lb_start,
2122
0
                                 lb_end);
2123
0
    } else {
2124
        // start and end containers are distinct
2125
0
        if (lb_start > 0) {
2126
            // handle first (partial) container
2127
0
            insert_flipped_container(&ans->high_low_container,
2128
0
                                     &x1->high_low_container, hb_start,
2129
0
                                     lb_start, 0xFFFF);
2130
0
            ++hb_start;  // for the full containers.  Can't wrap.
2131
0
        }
2132
2133
0
        if (lb_end != 0xFFFF) --hb_end;  // later we'll handle the partial block
2134
2135
0
        for (uint32_t hb = hb_start; hb <= hb_end; ++hb) {
2136
0
            insert_fully_flipped_container(&ans->high_low_container,
2137
0
                                           &x1->high_low_container, hb);
2138
0
        }
2139
2140
        // handle a partial final container
2141
0
        if (lb_end != 0xFFFF) {
2142
0
            insert_flipped_container(&ans->high_low_container,
2143
0
                                     &x1->high_low_container, hb_end + 1, 0,
2144
0
                                     lb_end);
2145
0
            ++hb_end;
2146
0
        }
2147
0
    }
2148
0
    ra_append_copies_after(&ans->high_low_container, &x1->high_low_container,
2149
0
                           hb_end, is_cow(x1));
2150
0
    return ans;
2151
0
}
2152
2153
void roaring_bitmap_flip_inplace(roaring_bitmap_t *x1, uint64_t range_start,
2154
0
                                 uint64_t range_end) {
2155
0
    if (range_start >= range_end) {
2156
0
        return;  // empty range
2157
0
    }
2158
0
    if(range_end >= UINT64_C(0x100000000)) {
2159
0
        range_end = UINT64_C(0x100000000);
2160
0
    }
2161
2162
0
    uint16_t hb_start = (uint16_t)(range_start >> 16);
2163
0
    const uint16_t lb_start = (uint16_t)range_start;
2164
0
    uint16_t hb_end = (uint16_t)((range_end - 1) >> 16);
2165
0
    const uint16_t lb_end = (uint16_t)(range_end - 1);
2166
2167
0
    if (hb_start == hb_end) {
2168
0
        inplace_flip_container(&x1->high_low_container, hb_start, lb_start,
2169
0
                               lb_end);
2170
0
    } else {
2171
        // start and end containers are distinct
2172
0
        if (lb_start > 0) {
2173
            // handle first (partial) container
2174
0
            inplace_flip_container(&x1->high_low_container, hb_start, lb_start,
2175
0
                                   0xFFFF);
2176
0
            ++hb_start;  // for the full containers.  Can't wrap.
2177
0
        }
2178
2179
0
        if (lb_end != 0xFFFF) --hb_end;
2180
2181
0
        for (uint32_t hb = hb_start; hb <= hb_end; ++hb) {
2182
0
            inplace_fully_flip_container(&x1->high_low_container, hb);
2183
0
        }
2184
        // handle a partial final container
2185
0
        if (lb_end != 0xFFFF) {
2186
0
            inplace_flip_container(&x1->high_low_container, hb_end + 1, 0,
2187
0
                                   lb_end);
2188
0
            ++hb_end;
2189
0
        }
2190
0
    }
2191
0
}
2192
2193
0
static void offset_append_with_merge(roaring_array_t *ra, int k, container_t *c, uint8_t t) {
2194
0
    int size = ra_get_size(ra);
2195
0
    if (size == 0 || ra_get_key_at_index(ra, size-1) != k) {
2196
        // No merge.
2197
0
        ra_append(ra, k, c, t);
2198
0
        return;
2199
0
    }
2200
2201
0
    uint8_t last_t, new_t;
2202
0
    container_t *last_c, *new_c;
2203
2204
    // NOTE: we don't need to unwrap here, since we added last_c ourselves
2205
    // we have the certainty it's not a shared container.
2206
    // The same applies to c, as it's the result of calling container_offset.
2207
0
    last_c = ra_get_container_at_index(ra, size-1, &last_t);
2208
0
    new_c = container_ior(last_c, last_t, c, t, &new_t);
2209
2210
0
    ra_set_container_at_index(ra, size-1, new_c, new_t);
2211
2212
    // Comparison of pointers of different origin is UB (or so claim some compiler
2213
    // makers), so we compare their bit representation only.
2214
0
    if ((uintptr_t)last_c != (uintptr_t)new_c) {
2215
0
        container_free(last_c, last_t);
2216
0
    }
2217
0
    container_free(c, t);
2218
0
}
2219
2220
// roaring_bitmap_add_offset adds the value 'offset' to each and every value in
2221
// a bitmap, generating a new bitmap in the process. If offset + element is
2222
// outside of the range [0,2^32), that the element will be dropped.
2223
// We need "offset" to be 64 bits because we want to support values
2224
// between -0xFFFFFFFF up to +0xFFFFFFFF.
2225
roaring_bitmap_t *roaring_bitmap_add_offset(const roaring_bitmap_t *bm,
2226
0
                                            int64_t offset) {
2227
0
    roaring_bitmap_t *answer;
2228
0
    roaring_array_t *ans_ra;
2229
0
    int64_t container_offset;
2230
0
    uint16_t in_offset;
2231
2232
0
    const roaring_array_t *bm_ra = &bm->high_low_container;
2233
0
    int length = bm_ra->size;
2234
2235
0
    if (offset == 0) {
2236
0
        return roaring_bitmap_copy(bm);
2237
0
    }
2238
2239
0
    container_offset = offset >> 16;
2240
0
    in_offset = (uint16_t)(offset - container_offset * (1 << 16));
2241
2242
0
    answer = roaring_bitmap_create();
2243
0
    roaring_bitmap_set_copy_on_write(answer, is_cow(bm));
2244
2245
0
    ans_ra = &answer->high_low_container;
2246
2247
0
    if (in_offset == 0) {
2248
0
        ans_ra = &answer->high_low_container;
2249
2250
0
        for (int i = 0, j = 0; i < length; ++i) {
2251
0
            int64_t key = ra_get_key_at_index(bm_ra, i);
2252
0
            key += container_offset;
2253
2254
0
            if (key < 0 || key >= (1 << 16)) {
2255
0
                continue;
2256
0
            }
2257
2258
0
            ra_append_copy(ans_ra, bm_ra, i, false);
2259
0
            ans_ra->keys[j++] = key;
2260
0
        }
2261
2262
0
        return answer;
2263
0
    }
2264
2265
0
    uint8_t t;
2266
0
    const container_t *c;
2267
0
    container_t *lo, *hi, **lo_ptr, **hi_ptr;
2268
0
    int64_t k;
2269
2270
0
    for (int i = 0; i < length; ++i) {
2271
0
        lo = hi = NULL;
2272
0
        lo_ptr = hi_ptr = NULL;
2273
2274
0
        k = ra_get_key_at_index(bm_ra, i)+container_offset;
2275
0
        if (k >= 0 && k < (1 << 16)) {
2276
0
            lo_ptr = &lo;
2277
0
        }
2278
0
        if (k+1 >= 0 && k+1 < (1 << 16)) {
2279
0
            hi_ptr = &hi;
2280
0
        }
2281
0
        if (lo_ptr == NULL && hi_ptr == NULL) {
2282
0
            continue;
2283
0
        }
2284
2285
0
        c = ra_get_container_at_index(bm_ra, i, &t);
2286
0
        c = container_unwrap_shared(c, &t);
2287
2288
0
        container_add_offset(c, t, lo_ptr, hi_ptr, in_offset);
2289
0
        if (lo != NULL) {
2290
0
            offset_append_with_merge(ans_ra, k, lo, t);
2291
0
        }
2292
0
        if (hi != NULL) {
2293
0
            ra_append(ans_ra, k+1, hi, t);
2294
0
        }
2295
0
    }
2296
2297
0
    return answer;
2298
0
}
2299
2300
roaring_bitmap_t *roaring_bitmap_lazy_or(const roaring_bitmap_t *x1,
2301
                                         const roaring_bitmap_t *x2,
2302
0
                                         const bool bitsetconversion) {
2303
0
    uint8_t result_type = 0;
2304
0
    const int length1 = x1->high_low_container.size,
2305
0
              length2 = x2->high_low_container.size;
2306
0
    if (0 == length1) {
2307
0
        return roaring_bitmap_copy(x2);
2308
0
    }
2309
0
    if (0 == length2) {
2310
0
        return roaring_bitmap_copy(x1);
2311
0
    }
2312
0
    roaring_bitmap_t *answer =
2313
0
        roaring_bitmap_create_with_capacity(length1 + length2);
2314
0
    roaring_bitmap_set_copy_on_write(answer, is_cow(x1) || is_cow(x2));
2315
0
    int pos1 = 0, pos2 = 0;
2316
0
    uint8_t type1, type2;
2317
0
    uint16_t s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
2318
0
    uint16_t s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
2319
0
    while (true) {
2320
0
        if (s1 == s2) {
2321
0
            container_t *c1 = ra_get_container_at_index(
2322
0
                                    &x1->high_low_container, pos1, &type1);
2323
0
            container_t *c2 = ra_get_container_at_index(
2324
0
                                    &x2->high_low_container, pos2, &type2);
2325
0
            container_t *c;
2326
0
            if (bitsetconversion &&
2327
0
                (get_container_type(c1, type1) != BITSET_CONTAINER_TYPE) &&
2328
0
                (get_container_type(c2, type2) != BITSET_CONTAINER_TYPE)
2329
0
            ){
2330
0
                container_t *newc1 =
2331
0
                    container_mutable_unwrap_shared(c1, &type1);
2332
0
                newc1 = container_to_bitset(newc1, type1);
2333
0
                type1 = BITSET_CONTAINER_TYPE;
2334
0
                c = container_lazy_ior(newc1, type1, c2, type2,
2335
0
                                       &result_type);
2336
0
                if (c != newc1) {  // should not happen
2337
0
                    container_free(newc1, type1);
2338
0
                }
2339
0
            } else {
2340
0
                c = container_lazy_or(c1, type1, c2, type2, &result_type);
2341
0
            }
2342
            // since we assume that the initial containers are non-empty,
2343
            // the
2344
            // result here
2345
            // can only be non-empty
2346
0
            ra_append(&answer->high_low_container, s1, c, result_type);
2347
0
            ++pos1;
2348
0
            ++pos2;
2349
0
            if (pos1 == length1) break;
2350
0
            if (pos2 == length2) break;
2351
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
2352
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
2353
2354
0
        } else if (s1 < s2) {  // s1 < s2
2355
0
            container_t *c1 = ra_get_container_at_index(
2356
0
                                    &x1->high_low_container, pos1, &type1);
2357
0
            c1 = get_copy_of_container(c1, &type1, is_cow(x1));
2358
0
            if (is_cow(x1)) {
2359
0
                ra_set_container_at_index(&x1->high_low_container, pos1, c1,
2360
0
                                          type1);
2361
0
            }
2362
0
            ra_append(&answer->high_low_container, s1, c1, type1);
2363
0
            pos1++;
2364
0
            if (pos1 == length1) break;
2365
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
2366
2367
0
        } else {  // s1 > s2
2368
0
            container_t *c2 = ra_get_container_at_index(
2369
0
                                    &x2->high_low_container, pos2, &type2);
2370
0
            c2 = get_copy_of_container(c2, &type2, is_cow(x2));
2371
0
            if (is_cow(x2)) {
2372
0
                ra_set_container_at_index(&x2->high_low_container, pos2, c2,
2373
0
                                          type2);
2374
0
            }
2375
0
            ra_append(&answer->high_low_container, s2, c2, type2);
2376
0
            pos2++;
2377
0
            if (pos2 == length2) break;
2378
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
2379
0
        }
2380
0
    }
2381
0
    if (pos1 == length1) {
2382
0
        ra_append_copy_range(&answer->high_low_container,
2383
0
                             &x2->high_low_container, pos2, length2,
2384
0
                             is_cow(x2));
2385
0
    } else if (pos2 == length2) {
2386
0
        ra_append_copy_range(&answer->high_low_container,
2387
0
                             &x1->high_low_container, pos1, length1,
2388
0
                             is_cow(x1));
2389
0
    }
2390
0
    return answer;
2391
0
}
2392
2393
void roaring_bitmap_lazy_or_inplace(roaring_bitmap_t *x1,
2394
                                    const roaring_bitmap_t *x2,
2395
0
                                    const bool bitsetconversion) {
2396
0
    uint8_t result_type = 0;
2397
0
    int length1 = x1->high_low_container.size;
2398
0
    const int length2 = x2->high_low_container.size;
2399
2400
0
    if (0 == length2) return;
2401
2402
0
    if (0 == length1) {
2403
0
        roaring_bitmap_overwrite(x1, x2);
2404
0
        return;
2405
0
    }
2406
0
    int pos1 = 0, pos2 = 0;
2407
0
    uint8_t type1, type2;
2408
0
    uint16_t s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
2409
0
    uint16_t s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
2410
0
    while (true) {
2411
0
        if (s1 == s2) {
2412
0
            container_t *c1 = ra_get_container_at_index(
2413
0
                                    &x1->high_low_container, pos1, &type1);
2414
0
            if (!container_is_full(c1, type1)) {
2415
0
                if ((bitsetconversion == false) ||
2416
0
                    (get_container_type(c1, type1) == BITSET_CONTAINER_TYPE)
2417
0
                ){
2418
0
                    c1 = get_writable_copy_if_shared(c1, &type1);
2419
0
                } else {
2420
                    // convert to bitset
2421
0
                    container_t *old_c1 = c1;
2422
0
                    uint8_t old_type1 = type1;
2423
0
                    c1 = container_mutable_unwrap_shared(c1, &type1);
2424
0
                    c1 = container_to_bitset(c1, type1);
2425
0
                    container_free(old_c1, old_type1);
2426
0
                    type1 = BITSET_CONTAINER_TYPE;
2427
0
                }
2428
2429
0
                container_t *c2 = ra_get_container_at_index(
2430
0
                                        &x2->high_low_container, pos2, &type2);
2431
0
                container_t *c = container_lazy_ior(c1, type1, c2, type2,
2432
0
                                                    &result_type);
2433
2434
0
                if (c != c1) {  // in this instance a new container was created,
2435
                                // and we need to free the old one
2436
0
                    container_free(c1, type1);
2437
0
                }
2438
2439
0
                ra_set_container_at_index(&x1->high_low_container, pos1, c,
2440
0
                                          result_type);
2441
0
            }
2442
0
            ++pos1;
2443
0
            ++pos2;
2444
0
            if (pos1 == length1) break;
2445
0
            if (pos2 == length2) break;
2446
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
2447
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
2448
2449
0
        } else if (s1 < s2) {  // s1 < s2
2450
0
            pos1++;
2451
0
            if (pos1 == length1) break;
2452
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
2453
2454
0
        } else {  // s1 > s2
2455
0
            container_t *c2 = ra_get_container_at_index(
2456
0
                                    &x2->high_low_container, pos2, &type2);
2457
            // container_t *c2_clone = container_clone(c2, type2);
2458
0
            c2 = get_copy_of_container(c2, &type2, is_cow(x2));
2459
0
            if (is_cow(x2)) {
2460
0
                ra_set_container_at_index(&x2->high_low_container, pos2, c2,
2461
0
                                          type2);
2462
0
            }
2463
0
            ra_insert_new_key_value_at(&x1->high_low_container, pos1, s2, c2,
2464
0
                                       type2);
2465
0
            pos1++;
2466
0
            length1++;
2467
0
            pos2++;
2468
0
            if (pos2 == length2) break;
2469
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
2470
0
        }
2471
0
    }
2472
0
    if (pos1 == length1) {
2473
0
        ra_append_copy_range(&x1->high_low_container, &x2->high_low_container,
2474
0
                             pos2, length2, is_cow(x2));
2475
0
    }
2476
0
}
2477
2478
roaring_bitmap_t *roaring_bitmap_lazy_xor(const roaring_bitmap_t *x1,
2479
0
                                          const roaring_bitmap_t *x2) {
2480
0
    uint8_t result_type = 0;
2481
0
    const int length1 = x1->high_low_container.size,
2482
0
              length2 = x2->high_low_container.size;
2483
0
    if (0 == length1) {
2484
0
        return roaring_bitmap_copy(x2);
2485
0
    }
2486
0
    if (0 == length2) {
2487
0
        return roaring_bitmap_copy(x1);
2488
0
    }
2489
0
    roaring_bitmap_t *answer =
2490
0
        roaring_bitmap_create_with_capacity(length1 + length2);
2491
0
    roaring_bitmap_set_copy_on_write(answer, is_cow(x1) || is_cow(x2));
2492
0
    int pos1 = 0, pos2 = 0;
2493
0
    uint8_t type1, type2;
2494
0
    uint16_t s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
2495
0
    uint16_t s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
2496
0
    while (true) {
2497
0
        if (s1 == s2) {
2498
0
            container_t *c1 = ra_get_container_at_index(
2499
0
                                    &x1->high_low_container, pos1, &type1);
2500
0
            container_t *c2 = ra_get_container_at_index(
2501
0
                                    &x2->high_low_container, pos2, &type2);
2502
0
            container_t *c = container_lazy_xor(
2503
0
                                    c1, type1, c2, type2, &result_type);
2504
2505
0
            if (container_nonzero_cardinality(c, result_type)) {
2506
0
                ra_append(&answer->high_low_container, s1, c, result_type);
2507
0
            } else {
2508
0
                container_free(c, result_type);
2509
0
            }
2510
2511
0
            ++pos1;
2512
0
            ++pos2;
2513
0
            if (pos1 == length1) break;
2514
0
            if (pos2 == length2) break;
2515
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
2516
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
2517
2518
0
        } else if (s1 < s2) {  // s1 < s2
2519
0
            container_t *c1 = ra_get_container_at_index(
2520
0
                                    &x1->high_low_container, pos1, &type1);
2521
0
            c1 = get_copy_of_container(c1, &type1, is_cow(x1));
2522
0
            if (is_cow(x1)) {
2523
0
                ra_set_container_at_index(&x1->high_low_container, pos1, c1,
2524
0
                                          type1);
2525
0
            }
2526
0
            ra_append(&answer->high_low_container, s1, c1, type1);
2527
0
            pos1++;
2528
0
            if (pos1 == length1) break;
2529
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
2530
2531
0
        } else {  // s1 > s2
2532
0
            container_t *c2 = ra_get_container_at_index(
2533
0
                                    &x2->high_low_container, pos2, &type2);
2534
0
            c2 = get_copy_of_container(c2, &type2, is_cow(x2));
2535
0
            if (is_cow(x2)) {
2536
0
                ra_set_container_at_index(&x2->high_low_container, pos2, c2,
2537
0
                                          type2);
2538
0
            }
2539
0
            ra_append(&answer->high_low_container, s2, c2, type2);
2540
0
            pos2++;
2541
0
            if (pos2 == length2) break;
2542
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
2543
0
        }
2544
0
    }
2545
0
    if (pos1 == length1) {
2546
0
        ra_append_copy_range(&answer->high_low_container,
2547
0
                             &x2->high_low_container, pos2, length2,
2548
0
                             is_cow(x2));
2549
0
    } else if (pos2 == length2) {
2550
0
        ra_append_copy_range(&answer->high_low_container,
2551
0
                             &x1->high_low_container, pos1, length1,
2552
0
                             is_cow(x1));
2553
0
    }
2554
0
    return answer;
2555
0
}
2556
2557
void roaring_bitmap_lazy_xor_inplace(roaring_bitmap_t *x1,
2558
0
                                     const roaring_bitmap_t *x2) {
2559
0
    assert(x1 != x2);
2560
0
    uint8_t result_type = 0;
2561
0
    int length1 = x1->high_low_container.size;
2562
0
    const int length2 = x2->high_low_container.size;
2563
2564
0
    if (0 == length2) return;
2565
2566
0
    if (0 == length1) {
2567
0
        roaring_bitmap_overwrite(x1, x2);
2568
0
        return;
2569
0
    }
2570
0
    int pos1 = 0, pos2 = 0;
2571
0
    uint8_t type1, type2;
2572
0
    uint16_t s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
2573
0
    uint16_t s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
2574
0
    while (true) {
2575
0
        if (s1 == s2) {
2576
0
            container_t *c1 = ra_get_container_at_index(
2577
0
                                    &x1->high_low_container, pos1, &type1);
2578
0
            container_t *c2 = ra_get_container_at_index(
2579
0
                                    &x2->high_low_container, pos2, &type2);
2580
2581
            // We do the computation "in place" only when c1 is not a shared container.
2582
            // Rationale: using a shared container safely with in place computation would
2583
            // require making a copy and then doing the computation in place which is likely
2584
            // less efficient than avoiding in place entirely and always generating a new
2585
            // container.
2586
2587
0
            container_t *c;
2588
0
            if (type1 == SHARED_CONTAINER_TYPE) {
2589
0
                c = container_lazy_xor(c1, type1, c2, type2, &result_type);
2590
0
                shared_container_free(CAST_shared(c1));  // release
2591
0
            }
2592
0
            else {
2593
0
                c = container_lazy_ixor(c1, type1, c2, type2, &result_type);
2594
0
            }
2595
2596
0
            if (container_nonzero_cardinality(c, result_type)) {
2597
0
                ra_set_container_at_index(&x1->high_low_container, pos1, c,
2598
0
                                          result_type);
2599
0
                ++pos1;
2600
0
            } else {
2601
0
                container_free(c, result_type);
2602
0
                ra_remove_at_index(&x1->high_low_container, pos1);
2603
0
                --length1;
2604
0
            }
2605
0
            ++pos2;
2606
0
            if (pos1 == length1) break;
2607
0
            if (pos2 == length2) break;
2608
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
2609
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
2610
2611
0
        } else if (s1 < s2) {  // s1 < s2
2612
0
            pos1++;
2613
0
            if (pos1 == length1) break;
2614
0
            s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
2615
2616
0
        } else {  // s1 > s2
2617
0
            container_t *c2 = ra_get_container_at_index(
2618
0
                                    &x2->high_low_container, pos2, &type2);
2619
            // container_t *c2_clone = container_clone(c2, type2);
2620
0
            c2 = get_copy_of_container(c2, &type2, is_cow(x2));
2621
0
            if (is_cow(x2)) {
2622
0
                ra_set_container_at_index(&x2->high_low_container, pos2, c2,
2623
0
                                          type2);
2624
0
            }
2625
0
            ra_insert_new_key_value_at(&x1->high_low_container, pos1, s2, c2,
2626
0
                                       type2);
2627
0
            pos1++;
2628
0
            length1++;
2629
0
            pos2++;
2630
0
            if (pos2 == length2) break;
2631
0
            s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
2632
0
        }
2633
0
    }
2634
0
    if (pos1 == length1) {
2635
0
        ra_append_copy_range(&x1->high_low_container, &x2->high_low_container,
2636
0
                             pos2, length2, is_cow(x2));
2637
0
    }
2638
0
}
2639
2640
0
void roaring_bitmap_repair_after_lazy(roaring_bitmap_t *r) {
2641
0
    roaring_array_t *ra = &r->high_low_container;
2642
2643
0
    for (int i = 0; i < ra->size; ++i) {
2644
0
        const uint8_t old_type = ra->typecodes[i];
2645
0
        container_t *old_c = ra->containers[i];
2646
0
        uint8_t new_type = old_type;
2647
0
        container_t *new_c = container_repair_after_lazy(old_c, &new_type);
2648
0
        ra->containers[i] = new_c;
2649
0
        ra->typecodes[i] = new_type;
2650
0
    }
2651
0
}
2652
2653
2654
2655
/**
2656
* roaring_bitmap_rank returns the number of integers that are smaller or equal
2657
* to x.
2658
*/
2659
0
uint64_t roaring_bitmap_rank(const roaring_bitmap_t *bm, uint32_t x) {
2660
0
    uint64_t size = 0;
2661
0
    uint32_t xhigh = x >> 16;
2662
0
    for (int i = 0; i < bm->high_low_container.size; i++) {
2663
0
        uint32_t key = bm->high_low_container.keys[i];
2664
0
        if (xhigh > key) {
2665
0
            size +=
2666
0
                container_get_cardinality(bm->high_low_container.containers[i],
2667
0
                                          bm->high_low_container.typecodes[i]);
2668
0
        } else if (xhigh == key) {
2669
0
            return size + container_rank(bm->high_low_container.containers[i],
2670
0
                                         bm->high_low_container.typecodes[i],
2671
0
                                         x & 0xFFFF);
2672
0
        } else {
2673
0
            return size;
2674
0
        }
2675
0
    }
2676
0
    return size;
2677
0
}
2678
2679
/**
2680
* roaring_bitmap_smallest returns the smallest value in the set.
2681
* Returns UINT32_MAX if the set is empty.
2682
*/
2683
0
uint32_t roaring_bitmap_minimum(const roaring_bitmap_t *bm) {
2684
0
    if (bm->high_low_container.size > 0) {
2685
0
        container_t *c = bm->high_low_container.containers[0];
2686
0
        uint8_t type = bm->high_low_container.typecodes[0];
2687
0
        uint32_t key = bm->high_low_container.keys[0];
2688
0
        uint32_t lowvalue = container_minimum(c, type);
2689
0
        return lowvalue | (key << 16);
2690
0
    }
2691
0
    return UINT32_MAX;
2692
0
}
2693
2694
/**
2695
* roaring_bitmap_smallest returns the greatest value in the set.
2696
* Returns 0 if the set is empty.
2697
*/
2698
0
uint32_t roaring_bitmap_maximum(const roaring_bitmap_t *bm) {
2699
0
    if (bm->high_low_container.size > 0) {
2700
0
        container_t *container =
2701
0
            bm->high_low_container.containers[bm->high_low_container.size - 1];
2702
0
        uint8_t typecode =
2703
0
            bm->high_low_container.typecodes[bm->high_low_container.size - 1];
2704
0
        uint32_t key =
2705
0
            bm->high_low_container.keys[bm->high_low_container.size - 1];
2706
0
        uint32_t lowvalue = container_maximum(container, typecode);
2707
0
        return lowvalue | (key << 16);
2708
0
    }
2709
0
    return 0;
2710
0
}
2711
2712
bool roaring_bitmap_select(const roaring_bitmap_t *bm, uint32_t rank,
2713
0
                           uint32_t *element) {
2714
0
    container_t *container;
2715
0
    uint8_t typecode;
2716
0
    uint16_t key;
2717
0
    uint32_t start_rank = 0;
2718
0
    int i = 0;
2719
0
    bool valid = false;
2720
0
    while (!valid && i < bm->high_low_container.size) {
2721
0
        container = bm->high_low_container.containers[i];
2722
0
        typecode = bm->high_low_container.typecodes[i];
2723
0
        valid =
2724
0
            container_select(container, typecode, &start_rank, rank, element);
2725
0
        i++;
2726
0
    }
2727
2728
0
    if (valid) {
2729
0
        key = bm->high_low_container.keys[i - 1];
2730
0
        *element |= (((uint32_t)key) << 16);  // w/o cast, key promotes signed
2731
0
        return true;
2732
0
    } else
2733
0
        return false;
2734
0
}
2735
2736
bool roaring_bitmap_intersect(const roaring_bitmap_t *x1,
2737
0
                                     const roaring_bitmap_t *x2) {
2738
0
    const int length1 = x1->high_low_container.size,
2739
0
              length2 = x2->high_low_container.size;
2740
0
    uint64_t answer = 0;
2741
0
    int pos1 = 0, pos2 = 0;
2742
2743
0
    while (pos1 < length1 && pos2 < length2) {
2744
0
        const uint16_t s1 = ra_get_key_at_index(& x1->high_low_container, pos1);
2745
0
        const uint16_t s2 = ra_get_key_at_index(& x2->high_low_container, pos2);
2746
2747
0
        if (s1 == s2) {
2748
0
            uint8_t type1, type2;
2749
0
            container_t *c1 = ra_get_container_at_index(
2750
0
                                    &x1->high_low_container, pos1, &type1);
2751
0
            container_t *c2 = ra_get_container_at_index(
2752
0
                                    &x2->high_low_container, pos2, &type2);
2753
0
            if (container_intersect(c1, type1, c2, type2))
2754
0
                return true;
2755
0
            ++pos1;
2756
0
            ++pos2;
2757
0
        } else if (s1 < s2) {  // s1 < s2
2758
0
            pos1 = ra_advance_until(& x1->high_low_container, s2, pos1);
2759
0
        } else {  // s1 > s2
2760
0
            pos2 = ra_advance_until(& x2->high_low_container, s1, pos2);
2761
0
        }
2762
0
    }
2763
0
    return answer != 0;
2764
0
}
2765
2766
bool roaring_bitmap_intersect_with_range(const roaring_bitmap_t *bm,
2767
0
                                         uint64_t x, uint64_t y) {
2768
0
    if (x >= y) {
2769
        // Empty range.
2770
0
        return false;
2771
0
    }
2772
0
    roaring_uint32_iterator_t it;
2773
0
    roaring_init_iterator(bm, &it);
2774
0
    if (!roaring_move_uint32_iterator_equalorlarger(&it, x)) {
2775
        // No values above x.
2776
0
        return false;
2777
0
    }
2778
0
    if (it.current_value >= y) {
2779
        // No values below y.
2780
0
        return false;
2781
0
    }
2782
0
    return true;
2783
0
}
2784
2785
2786
uint64_t roaring_bitmap_and_cardinality(const roaring_bitmap_t *x1,
2787
0
                                        const roaring_bitmap_t *x2) {
2788
0
    const int length1 = x1->high_low_container.size,
2789
0
              length2 = x2->high_low_container.size;
2790
0
    uint64_t answer = 0;
2791
0
    int pos1 = 0, pos2 = 0;
2792
2793
0
    while (pos1 < length1 && pos2 < length2) {
2794
0
        const uint16_t s1 = ra_get_key_at_index(&x1->high_low_container, pos1);
2795
0
        const uint16_t s2 = ra_get_key_at_index(&x2->high_low_container, pos2);
2796
2797
0
        if (s1 == s2) {
2798
0
            uint8_t type1, type2;
2799
0
            container_t *c1 = ra_get_container_at_index(
2800
0
                                    &x1->high_low_container, pos1, &type1);
2801
0
            container_t *c2 = ra_get_container_at_index(
2802
0
                                    &x2->high_low_container, pos2, &type2);
2803
0
            answer += container_and_cardinality(c1, type1, c2, type2);
2804
0
            ++pos1;
2805
0
            ++pos2;
2806
0
        } else if (s1 < s2) {  // s1 < s2
2807
0
            pos1 = ra_advance_until(&x1->high_low_container, s2, pos1);
2808
0
        } else {  // s1 > s2
2809
0
            pos2 = ra_advance_until(&x2->high_low_container, s1, pos2);
2810
0
        }
2811
0
    }
2812
0
    return answer;
2813
0
}
2814
2815
double roaring_bitmap_jaccard_index(const roaring_bitmap_t *x1,
2816
0
                                    const roaring_bitmap_t *x2) {
2817
0
    const uint64_t c1 = roaring_bitmap_get_cardinality(x1);
2818
0
    const uint64_t c2 = roaring_bitmap_get_cardinality(x2);
2819
0
    const uint64_t inter = roaring_bitmap_and_cardinality(x1, x2);
2820
0
    return (double)inter / (double)(c1 + c2 - inter);
2821
0
}
2822
2823
uint64_t roaring_bitmap_or_cardinality(const roaring_bitmap_t *x1,
2824
0
                                       const roaring_bitmap_t *x2) {
2825
0
    const uint64_t c1 = roaring_bitmap_get_cardinality(x1);
2826
0
    const uint64_t c2 = roaring_bitmap_get_cardinality(x2);
2827
0
    const uint64_t inter = roaring_bitmap_and_cardinality(x1, x2);
2828
0
    return c1 + c2 - inter;
2829
0
}
2830
2831
uint64_t roaring_bitmap_andnot_cardinality(const roaring_bitmap_t *x1,
2832
0
                                           const roaring_bitmap_t *x2) {
2833
0
    const uint64_t c1 = roaring_bitmap_get_cardinality(x1);
2834
0
    const uint64_t inter = roaring_bitmap_and_cardinality(x1, x2);
2835
0
    return c1 - inter;
2836
0
}
2837
2838
uint64_t roaring_bitmap_xor_cardinality(const roaring_bitmap_t *x1,
2839
0
                                        const roaring_bitmap_t *x2) {
2840
0
    const uint64_t c1 = roaring_bitmap_get_cardinality(x1);
2841
0
    const uint64_t c2 = roaring_bitmap_get_cardinality(x2);
2842
0
    const uint64_t inter = roaring_bitmap_and_cardinality(x1, x2);
2843
0
    return c1 + c2 - 2 * inter;
2844
0
}
2845
2846
2847
0
bool roaring_bitmap_contains(const roaring_bitmap_t *r, uint32_t val) {
2848
0
    const uint16_t hb = val >> 16;
2849
    /*
2850
     * the next function call involves a binary search and lots of branching.
2851
     */
2852
0
    int32_t i = ra_get_index(&r->high_low_container, hb);
2853
0
    if (i < 0) return false;
2854
2855
0
    uint8_t typecode;
2856
    // next call ought to be cheap
2857
0
    container_t *container =
2858
0
        ra_get_container_at_index(&r->high_low_container, i, &typecode);
2859
    // rest might be a tad expensive, possibly involving another round of binary search
2860
0
    return container_contains(container, val & 0xFFFF, typecode);
2861
0
}
2862
2863
2864
/**
2865
 * Check whether a range of values from range_start (included) to range_end (excluded) is present
2866
 */
2867
0
bool roaring_bitmap_contains_range(const roaring_bitmap_t *r, uint64_t range_start, uint64_t range_end) {
2868
0
    if(range_end >= UINT64_C(0x100000000)) {
2869
0
        range_end = UINT64_C(0x100000000);
2870
0
    }
2871
0
    if (range_start >= range_end) return true;  // empty range are always contained!
2872
0
    if (range_end - range_start == 1) return roaring_bitmap_contains(r, (uint32_t)range_start);
2873
0
    uint16_t hb_rs = (uint16_t)(range_start >> 16);
2874
0
    uint16_t hb_re = (uint16_t)((range_end - 1) >> 16);
2875
0
    const int32_t span = hb_re - hb_rs;
2876
0
    const int32_t hlc_sz = ra_get_size(&r->high_low_container);
2877
0
    if (hlc_sz < span + 1) {
2878
0
      return false;
2879
0
    }
2880
0
    int32_t is = ra_get_index(&r->high_low_container, hb_rs);
2881
0
    int32_t ie = ra_get_index(&r->high_low_container, hb_re);
2882
0
    ie = (ie < 0 ? -ie - 1 : ie);
2883
0
    if ((is < 0) || ((ie - is) != span) || ie >= hlc_sz) {
2884
0
       return false;
2885
0
    }
2886
0
    const uint32_t lb_rs = range_start & 0xFFFF;
2887
0
    const uint32_t lb_re = ((range_end - 1) & 0xFFFF) + 1;
2888
0
    uint8_t type;
2889
0
    container_t *c = ra_get_container_at_index(&r->high_low_container, is,
2890
0
                                               &type);
2891
0
    if (hb_rs == hb_re) {
2892
0
      return container_contains_range(c, lb_rs, lb_re, type);
2893
0
    }
2894
0
    if (!container_contains_range(c, lb_rs, 1 << 16, type)) {
2895
0
      return false;
2896
0
    }
2897
0
    c = ra_get_container_at_index(&r->high_low_container, ie, &type);
2898
0
    if (!container_contains_range(c, 0, lb_re, type)) {
2899
0
        return false;
2900
0
    }
2901
0
    for (int32_t i = is + 1; i < ie; ++i) {
2902
0
        c = ra_get_container_at_index(&r->high_low_container, i, &type);
2903
0
        if (!container_is_full(c, type) ) {
2904
0
          return false;
2905
0
        }
2906
0
    }
2907
0
    return true;
2908
0
}
2909
2910
2911
bool roaring_bitmap_is_strict_subset(const roaring_bitmap_t *r1,
2912
0
                                     const roaring_bitmap_t *r2) {
2913
0
    return (roaring_bitmap_get_cardinality(r2) >
2914
0
                roaring_bitmap_get_cardinality(r1) &&
2915
0
            roaring_bitmap_is_subset(r1, r2));
2916
0
}
2917
2918
2919
/*
2920
 * FROZEN SERIALIZATION FORMAT DESCRIPTION
2921
 *
2922
 * -- (beginning must be aligned by 32 bytes) --
2923
 * <bitset_data> uint64_t[BITSET_CONTAINER_SIZE_IN_WORDS * num_bitset_containers]
2924
 * <run_data>    rle16_t[total number of rle elements in all run containers]
2925
 * <array_data>  uint16_t[total number of array elements in all array containers]
2926
 * <keys>        uint16_t[num_containers]
2927
 * <counts>      uint16_t[num_containers]
2928
 * <typecodes>   uint8_t[num_containers]
2929
 * <header>      uint32_t
2930
 *
2931
 * <header> is a 4-byte value which is a bit union of FROZEN_COOKIE (15 bits)
2932
 * and the number of containers (17 bits).
2933
 *
2934
 * <counts> stores number of elements for every container.
2935
 * Its meaning depends on container type.
2936
 * For array and bitset containers, this value is the container cardinality minus one.
2937
 * For run container, it is the number of rle_t elements (n_runs).
2938
 *
2939
 * <bitset_data>,<array_data>,<run_data> are flat arrays of elements of
2940
 * all containers of respective type.
2941
 *
2942
 * <*_data> and <keys> are kept close together because they are not accessed
2943
 * during deserilization. This may reduce IO in case of large mmaped bitmaps.
2944
 * All members have their native alignments during deserilization except <header>,
2945
 * which is not guaranteed to be aligned by 4 bytes.
2946
 */
2947
2948
0
size_t roaring_bitmap_frozen_size_in_bytes(const roaring_bitmap_t *rb) {
2949
0
    const roaring_array_t *ra = &rb->high_low_container;
2950
0
    size_t num_bytes = 0;
2951
0
    for (int32_t i = 0; i < ra->size; i++) {
2952
0
        switch (ra->typecodes[i]) {
2953
0
            case BITSET_CONTAINER_TYPE: {
2954
0
                num_bytes += BITSET_CONTAINER_SIZE_IN_WORDS * sizeof(uint64_t);
2955
0
                break;
2956
0
            }
2957
0
            case RUN_CONTAINER_TYPE: {
2958
0
                const run_container_t *rc = const_CAST_run(ra->containers[i]);
2959
0
                num_bytes += rc->n_runs * sizeof(rle16_t);
2960
0
                break;
2961
0
            }
2962
0
            case ARRAY_CONTAINER_TYPE: {
2963
0
                const array_container_t *ac =
2964
0
                        const_CAST_array(ra->containers[i]);
2965
0
                num_bytes += ac->cardinality * sizeof(uint16_t);
2966
0
                break;
2967
0
            }
2968
0
            default:
2969
0
                __builtin_unreachable();
2970
0
        }
2971
0
    }
2972
0
    num_bytes += (2 + 2 + 1) * ra->size; // keys, counts, typecodes
2973
0
    num_bytes += 4; // header
2974
0
    return num_bytes;
2975
0
}
2976
2977
0
inline static void *arena_alloc(char **arena, size_t num_bytes) {
2978
0
    char *res = *arena;
2979
0
    *arena += num_bytes;
2980
0
    return res;
2981
0
}
2982
2983
0
void roaring_bitmap_frozen_serialize(const roaring_bitmap_t *rb, char *buf) {
2984
    /*
2985
     * Note: we do not require user to supply a specifically aligned buffer.
2986
     * Thus we have to use memcpy() everywhere.
2987
     */
2988
2989
0
    const roaring_array_t *ra = &rb->high_low_container;
2990
2991
0
    size_t bitset_zone_size = 0;
2992
0
    size_t run_zone_size = 0;
2993
0
    size_t array_zone_size = 0;
2994
0
    for (int32_t i = 0; i < ra->size; i++) {
2995
0
        switch (ra->typecodes[i]) {
2996
0
            case BITSET_CONTAINER_TYPE: {
2997
0
                bitset_zone_size +=
2998
0
                        BITSET_CONTAINER_SIZE_IN_WORDS * sizeof(uint64_t);
2999
0
                break;
3000
0
            }
3001
0
            case RUN_CONTAINER_TYPE: {
3002
0
                const run_container_t *rc = const_CAST_run(ra->containers[i]);
3003
0
                run_zone_size += rc->n_runs * sizeof(rle16_t);
3004
0
                break;
3005
0
            }
3006
0
            case ARRAY_CONTAINER_TYPE: {
3007
0
                const array_container_t *ac =
3008
0
                        const_CAST_array(ra->containers[i]);
3009
0
                array_zone_size += ac->cardinality * sizeof(uint16_t);
3010
0
                break;
3011
0
            }
3012
0
            default:
3013
0
                __builtin_unreachable();
3014
0
        }
3015
0
    }
3016
3017
0
    uint64_t *bitset_zone = (uint64_t *)arena_alloc(&buf, bitset_zone_size);
3018
0
    rle16_t *run_zone = (rle16_t *)arena_alloc(&buf, run_zone_size);
3019
0
    uint16_t *array_zone = (uint16_t *)arena_alloc(&buf, array_zone_size);
3020
0
    uint16_t *key_zone = (uint16_t *)arena_alloc(&buf, 2*ra->size);
3021
0
    uint16_t *count_zone = (uint16_t *)arena_alloc(&buf, 2*ra->size);
3022
0
    uint8_t *typecode_zone = (uint8_t *)arena_alloc(&buf, ra->size);
3023
0
    uint32_t *header_zone = (uint32_t *)arena_alloc(&buf, 4);
3024
3025
0
    for (int32_t i = 0; i < ra->size; i++) {
3026
0
        uint16_t count;
3027
0
        switch (ra->typecodes[i]) {
3028
0
            case BITSET_CONTAINER_TYPE: {
3029
0
                const bitset_container_t *bc =
3030
0
                            const_CAST_bitset(ra->containers[i]);
3031
0
                memcpy(bitset_zone, bc->words,
3032
0
                       BITSET_CONTAINER_SIZE_IN_WORDS * sizeof(uint64_t));
3033
0
                bitset_zone += BITSET_CONTAINER_SIZE_IN_WORDS;
3034
0
                if (bc->cardinality != BITSET_UNKNOWN_CARDINALITY) {
3035
0
                    count = bc->cardinality - 1;
3036
0
                } else {
3037
0
                    count = bitset_container_compute_cardinality(bc) - 1;
3038
0
                }
3039
0
                break;
3040
0
            }
3041
0
            case RUN_CONTAINER_TYPE: {
3042
0
                const run_container_t *rc = const_CAST_run(ra->containers[i]);
3043
0
                size_t num_bytes = rc->n_runs * sizeof(rle16_t);
3044
0
                memcpy(run_zone, rc->runs, num_bytes);
3045
0
                run_zone += rc->n_runs;
3046
0
                count = rc->n_runs;
3047
0
                break;
3048
0
            }
3049
0
            case ARRAY_CONTAINER_TYPE: {
3050
0
                const array_container_t *ac =
3051
0
                            const_CAST_array(ra->containers[i]);
3052
0
                size_t num_bytes = ac->cardinality * sizeof(uint16_t);
3053
0
                memcpy(array_zone, ac->array, num_bytes);
3054
0
                array_zone += ac->cardinality;
3055
0
                count = ac->cardinality - 1;
3056
0
                break;
3057
0
            }
3058
0
            default:
3059
0
                __builtin_unreachable();
3060
0
        }
3061
0
        memcpy(&count_zone[i], &count, 2);
3062
0
    }
3063
0
    memcpy(key_zone, ra->keys, ra->size * sizeof(uint16_t));
3064
0
    memcpy(typecode_zone, ra->typecodes, ra->size * sizeof(uint8_t));
3065
0
    uint32_t header = ((uint32_t)ra->size << 15) | FROZEN_COOKIE;
3066
0
    memcpy(header_zone, &header, 4);
3067
0
}
3068
3069
const roaring_bitmap_t *
3070
0
roaring_bitmap_frozen_view(const char *buf, size_t length) {
3071
0
    if ((uintptr_t)buf % 32 != 0) {
3072
0
        return NULL;
3073
0
    }
3074
3075
    // cookie and num_containers
3076
0
    if (length < 4) {
3077
0
        return NULL;
3078
0
    }
3079
0
    uint32_t header;
3080
0
    memcpy(&header, buf + length - 4, 4); // header may be misaligned
3081
0
    if ((header & 0x7FFF) != FROZEN_COOKIE) {
3082
0
        return NULL;
3083
0
    }
3084
0
    int32_t num_containers = (header >> 15);
3085
3086
    // typecodes, counts and keys
3087
0
    if (length < 4 + (size_t)num_containers * (1 + 2 + 2)) {
3088
0
        return NULL;
3089
0
    }
3090
0
    uint16_t *keys = (uint16_t *)(buf + length - 4 - num_containers * 5);
3091
0
    uint16_t *counts = (uint16_t *)(buf + length - 4 - num_containers * 3);
3092
0
    uint8_t *typecodes = (uint8_t *)(buf + length - 4 - num_containers * 1);
3093
3094
    // {bitset,array,run}_zone
3095
0
    int32_t num_bitset_containers = 0;
3096
0
    int32_t num_run_containers = 0;
3097
0
    int32_t num_array_containers = 0;
3098
0
    size_t bitset_zone_size = 0;
3099
0
    size_t run_zone_size = 0;
3100
0
    size_t array_zone_size = 0;
3101
0
    for (int32_t i = 0; i < num_containers; i++) {
3102
0
        switch (typecodes[i]) {
3103
0
            case BITSET_CONTAINER_TYPE:
3104
0
                num_bitset_containers++;
3105
0
                bitset_zone_size += BITSET_CONTAINER_SIZE_IN_WORDS * sizeof(uint64_t);
3106
0
                break;
3107
0
            case RUN_CONTAINER_TYPE:
3108
0
                num_run_containers++;
3109
0
                run_zone_size += counts[i] * sizeof(rle16_t);
3110
0
                break;
3111
0
            case ARRAY_CONTAINER_TYPE:
3112
0
                num_array_containers++;
3113
0
                array_zone_size += (counts[i] + UINT32_C(1)) * sizeof(uint16_t);
3114
0
                break;
3115
0
            default:
3116
0
                return NULL;
3117
0
        }
3118
0
    }
3119
0
    if (length != bitset_zone_size + run_zone_size + array_zone_size +
3120
0
                  5 * num_containers + 4) {
3121
0
        return NULL;
3122
0
    }
3123
0
    uint64_t *bitset_zone = (uint64_t*) (buf);
3124
0
    rle16_t *run_zone = (rle16_t*) (buf + bitset_zone_size);
3125
0
    uint16_t *array_zone = (uint16_t*) (buf + bitset_zone_size + run_zone_size);
3126
3127
0
    size_t alloc_size = 0;
3128
0
    alloc_size += sizeof(roaring_bitmap_t);
3129
0
    alloc_size += num_containers * sizeof(container_t*);
3130
0
    alloc_size += num_bitset_containers * sizeof(bitset_container_t);
3131
0
    alloc_size += num_run_containers * sizeof(run_container_t);
3132
0
    alloc_size += num_array_containers * sizeof(array_container_t);
3133
3134
0
    char *arena = (char *)roaring_malloc(alloc_size);
3135
0
    if (arena == NULL) {
3136
0
        return NULL;
3137
0
    }
3138
3139
0
    roaring_bitmap_t *rb = (roaring_bitmap_t *)
3140
0
            arena_alloc(&arena, sizeof(roaring_bitmap_t));
3141
0
    rb->high_low_container.flags = ROARING_FLAG_FROZEN;
3142
0
    rb->high_low_container.allocation_size = num_containers;
3143
0
    rb->high_low_container.size = num_containers;
3144
0
    rb->high_low_container.keys = (uint16_t *)keys;
3145
0
    rb->high_low_container.typecodes = (uint8_t *)typecodes;
3146
0
    rb->high_low_container.containers =
3147
0
        (container_t **)arena_alloc(&arena,
3148
0
                                    sizeof(container_t*) * num_containers);
3149
    // Ensure offset of high_low_container.containers is known distance used in
3150
    // C++ wrapper. sizeof(roaring_bitmap_t) is used as it is the size of the
3151
    // only allocation that precedes high_low_container.containers. If this is
3152
    // changed (new allocation or changed order), this offset will also need to
3153
    // be changed in the C++ wrapper.
3154
0
    assert(rb ==
3155
0
           (roaring_bitmap_t *)((char *)rb->high_low_container.containers -
3156
0
                                sizeof(roaring_bitmap_t)));
3157
0
    for (int32_t i = 0; i < num_containers; i++) {
3158
0
        switch (typecodes[i]) {
3159
0
            case BITSET_CONTAINER_TYPE: {
3160
0
                bitset_container_t *bitset = (bitset_container_t *)
3161
0
                        arena_alloc(&arena, sizeof(bitset_container_t));
3162
0
                bitset->words = bitset_zone;
3163
0
                bitset->cardinality = counts[i] + UINT32_C(1);
3164
0
                rb->high_low_container.containers[i] = bitset;
3165
0
                bitset_zone += BITSET_CONTAINER_SIZE_IN_WORDS;
3166
0
                break;
3167
0
            }
3168
0
            case RUN_CONTAINER_TYPE: {
3169
0
                run_container_t *run = (run_container_t *)
3170
0
                        arena_alloc(&arena, sizeof(run_container_t));
3171
0
                run->capacity = counts[i];
3172
0
                run->n_runs = counts[i];
3173
0
                run->runs = run_zone;
3174
0
                rb->high_low_container.containers[i] = run;
3175
0
                run_zone += run->n_runs;
3176
0
                break;
3177
0
            }
3178
0
            case ARRAY_CONTAINER_TYPE: {
3179
0
                array_container_t *array = (array_container_t *)
3180
0
                        arena_alloc(&arena, sizeof(array_container_t));
3181
0
                array->capacity = counts[i] + UINT32_C(1);
3182
0
                array->cardinality = counts[i] + UINT32_C(1);
3183
0
                array->array = array_zone;
3184
0
                rb->high_low_container.containers[i] = array;
3185
0
                array_zone += counts[i] + UINT32_C(1);
3186
0
                break;
3187
0
            }
3188
0
            default:
3189
0
                roaring_free(arena);
3190
0
                return NULL;
3191
0
        }
3192
0
    }
3193
3194
0
    return rb;
3195
0
}
3196
3197
#ifdef __cplusplus
3198
} } }  // extern "C" { namespace roaring {
3199
#endif