Coverage Report

Created: 2026-08-31 07:17

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/croaring/src/containers/mixed_subset.c
Line
Count
Source
1
#include <roaring/array_util.h>
2
#include <roaring/containers/mixed_subset.h>
3
4
#ifdef __cplusplus
5
extern "C" {
6
namespace roaring {
7
namespace internal {
8
#endif
9
10
bool array_container_is_subset_bitset(const array_container_t* container1,
11
0
                                      const bitset_container_t* container2) {
12
0
    if (container2->cardinality != BITSET_UNKNOWN_CARDINALITY) {
13
0
        if (container2->cardinality < container1->cardinality) {
14
0
            return false;
15
0
        }
16
0
    }
17
0
    for (int i = 0; i < container1->cardinality; ++i) {
18
0
        if (!bitset_container_contains(container2, container1->array[i])) {
19
0
            return false;
20
0
        }
21
0
    }
22
0
    return true;
23
0
}
24
25
bool run_container_is_subset_array(const run_container_t* container1,
26
0
                                   const array_container_t* container2) {
27
0
    if (run_container_cardinality(container1) > container2->cardinality)
28
0
        return false;
29
0
    int32_t start_pos = -1, stop_pos = -1;
30
0
    for (int i = 0; i < container1->n_runs; ++i) {
31
0
        int32_t start = container1->runs[i].value;
32
0
        int32_t stop = start + container1->runs[i].length;
33
0
        start_pos = advanceUntil(container2->array, stop_pos,
34
0
                                 container2->cardinality, start);
35
0
        stop_pos = advanceUntil(container2->array, stop_pos,
36
0
                                container2->cardinality, stop);
37
0
        if (stop_pos == container2->cardinality) {
38
0
            return false;
39
0
        } else if (stop_pos - start_pos != stop - start ||
40
0
                   container2->array[start_pos] != start ||
41
0
                   container2->array[stop_pos] != stop) {
42
0
            return false;
43
0
        }
44
0
    }
45
0
    return true;
46
0
}
47
48
bool array_container_is_subset_run(const array_container_t* container1,
49
0
                                   const run_container_t* container2) {
50
0
    if (container1->cardinality > run_container_cardinality(container2))
51
0
        return false;
52
0
    int i_array = 0, i_run = 0;
53
0
    while (i_array < container1->cardinality && i_run < container2->n_runs) {
54
0
        uint32_t start = container2->runs[i_run].value;
55
0
        uint32_t stop = start + container2->runs[i_run].length;
56
0
        if (container1->array[i_array] < start) {
57
0
            return false;
58
0
        } else if (container1->array[i_array] > stop) {
59
0
            i_run++;
60
0
        } else {  // the value of the array is in the run
61
0
            i_array++;
62
0
        }
63
0
    }
64
0
    if (i_array == container1->cardinality) {
65
0
        return true;
66
0
    } else {
67
0
        return false;
68
0
    }
69
0
}
70
71
bool run_container_is_subset_bitset(const run_container_t* container1,
72
0
                                    const bitset_container_t* container2) {
73
    // todo: this code could be much faster
74
0
    if (container2->cardinality != BITSET_UNKNOWN_CARDINALITY) {
75
0
        if (container2->cardinality < run_container_cardinality(container1)) {
76
0
            return false;
77
0
        }
78
0
    } else {
79
0
        int32_t card = bitset_container_compute_cardinality(
80
0
            container2);  // modify container2?
81
0
        if (card < run_container_cardinality(container1)) {
82
0
            return false;
83
0
        }
84
0
    }
85
0
    for (int i = 0; i < container1->n_runs; ++i) {
86
0
        uint32_t run_start = container1->runs[i].value;
87
0
        uint32_t le = container1->runs[i].length;
88
0
        for (uint32_t j = run_start; j <= run_start + le; ++j) {
89
0
            if (!bitset_container_contains(container2, j)) {
90
0
                return false;
91
0
            }
92
0
        }
93
0
    }
94
0
    return true;
95
0
}
96
97
bool bitset_container_is_subset_run(const bitset_container_t* container1,
98
0
                                    const run_container_t* container2) {
99
    // todo: this code could be much faster
100
0
    if (container1->cardinality != BITSET_UNKNOWN_CARDINALITY) {
101
0
        if (container1->cardinality > run_container_cardinality(container2)) {
102
0
            return false;
103
0
        }
104
0
    }
105
0
    int32_t i_bitset = 0, i_run = 0;
106
0
    while (i_bitset < BITSET_CONTAINER_SIZE_IN_WORDS &&
107
0
           i_run < container2->n_runs) {
108
0
        uint64_t w = container1->words[i_bitset];
109
0
        while (w != 0 && i_run < container2->n_runs) {
110
0
            uint32_t start = container2->runs[i_run].value;
111
0
            uint32_t stop = start + container2->runs[i_run].length;
112
0
            uint64_t t = w & (~w + 1);
113
0
            uint16_t r = i_bitset * 64 + roaring_trailing_zeroes(w);
114
0
            if (r < start) {
115
0
                return false;
116
0
            } else if (r > stop) {
117
0
                i_run++;
118
0
                continue;
119
0
            } else {
120
0
                w ^= t;
121
0
            }
122
0
        }
123
0
        if (w == 0) {
124
0
            i_bitset++;
125
0
        } else {
126
0
            return false;
127
0
        }
128
0
    }
129
0
    if (i_bitset < BITSET_CONTAINER_SIZE_IN_WORDS) {
130
        // terminated iterating on the run containers, check that rest of bitset
131
        // is empty
132
0
        for (; i_bitset < BITSET_CONTAINER_SIZE_IN_WORDS; i_bitset++) {
133
0
            if (container1->words[i_bitset] != 0) {
134
0
                return false;
135
0
            }
136
0
        }
137
0
    }
138
0
    return true;
139
0
}
140
141
#ifdef __cplusplus
142
}
143
}
144
}  // extern "C" { namespace roaring { namespace internal {
145
#endif