Coverage Report

Created: 2023-01-15 06:02

/src/croaring/include/roaring/array_util.h
Line
Count
Source (jump to first uncovered line)
1
#ifndef ARRAY_UTIL_H
2
#define ARRAY_UTIL_H
3
4
#include <stddef.h>  // for size_t
5
#include <stdint.h>
6
7
#include <roaring/portability.h>
8
9
#ifdef __cplusplus
10
extern "C" { namespace roaring { namespace internal {
11
#endif
12
13
/*
14
 *  Good old binary search.
15
 *  Assumes that array is sorted, has logarithmic complexity.
16
 *  if the result is x, then:
17
 *     if ( x>0 )  you have array[x] = ikey
18
 *     if ( x<0 ) then inserting ikey at position -x-1 in array (insuring that array[-x-1]=ikey)
19
 *                   keys the array sorted.
20
 */
21
inline int32_t binarySearch(const uint16_t *array, int32_t lenarray,
22
0
                            uint16_t ikey) {
23
0
    int32_t low = 0;
24
0
    int32_t high = lenarray - 1;
25
0
    while (low <= high) {
26
0
        int32_t middleIndex = (low + high) >> 1;
27
0
        uint16_t middleValue = array[middleIndex];
28
0
        if (middleValue < ikey) {
29
0
            low = middleIndex + 1;
30
0
        } else if (middleValue > ikey) {
31
0
            high = middleIndex - 1;
32
0
        } else {
33
0
            return middleIndex;
34
0
        }
35
0
    }
36
0
    return -(low + 1);
37
0
}
38
39
/**
40
 * Galloping search
41
 * Assumes that array is sorted, has logarithmic complexity.
42
 * if the result is x, then if x = length, you have that all values in array between pos and length
43
 *    are smaller than min.
44
 * otherwise returns the first index x such that array[x] >= min.
45
 */
46
static inline int32_t advanceUntil(const uint16_t *array, int32_t pos,
47
0
                                   int32_t length, uint16_t min) {
48
0
    int32_t lower = pos + 1;
49
50
0
    if ((lower >= length) || (array[lower] >= min)) {
51
0
        return lower;
52
0
    }
53
54
0
    int32_t spansize = 1;
55
56
0
    while ((lower + spansize < length) && (array[lower + spansize] < min)) {
57
0
        spansize <<= 1;
58
0
    }
59
0
    int32_t upper = (lower + spansize < length) ? lower + spansize : length - 1;
60
61
0
    if (array[upper] == min) {
62
0
        return upper;
63
0
    }
64
0
    if (array[upper] < min) {
65
        // means
66
        // array
67
        // has no
68
        // item
69
        // >= min
70
        // pos = array.length;
71
0
        return length;
72
0
    }
73
74
    // we know that the next-smallest span was too small
75
0
    lower += (spansize >> 1);
76
77
0
    int32_t mid = 0;
78
0
    while (lower + 1 != upper) {
79
0
        mid = (lower + upper) >> 1;
80
0
        if (array[mid] == min) {
81
0
            return mid;
82
0
        } else if (array[mid] < min) {
83
0
            lower = mid;
84
0
        } else {
85
0
            upper = mid;
86
0
        }
87
0
    }
88
0
    return upper;
89
0
}
Unexecuted instantiation: roaring.c:advanceUntil
Unexecuted instantiation: roaring_array.c:advanceUntil
Unexecuted instantiation: array_util.c:advanceUntil
Unexecuted instantiation: array.c:advanceUntil
Unexecuted instantiation: containers.c:advanceUntil
Unexecuted instantiation: convert.c:advanceUntil
Unexecuted instantiation: mixed_intersection.c:advanceUntil
Unexecuted instantiation: mixed_union.c:advanceUntil
Unexecuted instantiation: mixed_equal.c:advanceUntil
Unexecuted instantiation: mixed_subset.c:advanceUntil
Unexecuted instantiation: mixed_negation.c:advanceUntil
Unexecuted instantiation: mixed_xor.c:advanceUntil
Unexecuted instantiation: mixed_andnot.c:advanceUntil
Unexecuted instantiation: run.c:advanceUntil
90
91
/**
92
 * Returns number of elements which are less then $ikey.
93
 * Array elements must be unique and sorted.
94
 */
95
static inline int32_t count_less(const uint16_t *array, int32_t lenarray,
96
0
                                 uint16_t ikey) {
97
0
    if (lenarray == 0) return 0;
98
0
    int32_t pos = binarySearch(array, lenarray, ikey);
99
0
    return pos >= 0 ? pos : -(pos+1);
100
0
}
Unexecuted instantiation: roaring.c:count_less
Unexecuted instantiation: roaring_array.c:count_less
Unexecuted instantiation: array_util.c:count_less
Unexecuted instantiation: array.c:count_less
Unexecuted instantiation: containers.c:count_less
Unexecuted instantiation: convert.c:count_less
Unexecuted instantiation: mixed_intersection.c:count_less
Unexecuted instantiation: mixed_union.c:count_less
Unexecuted instantiation: mixed_equal.c:count_less
Unexecuted instantiation: mixed_subset.c:count_less
Unexecuted instantiation: mixed_negation.c:count_less
Unexecuted instantiation: mixed_xor.c:count_less
Unexecuted instantiation: mixed_andnot.c:count_less
Unexecuted instantiation: run.c:count_less
101
102
/**
103
 * Returns number of elements which are greater then $ikey.
104
 * Array elements must be unique and sorted.
105
 */
106
static inline int32_t count_greater(const uint16_t *array, int32_t lenarray,
107
0
                                    uint16_t ikey) {
108
0
    if (lenarray == 0) return 0;
109
0
    int32_t pos = binarySearch(array, lenarray, ikey);
110
0
    if (pos >= 0) {
111
0
        return lenarray - (pos+1);
112
0
    } else {
113
0
        return lenarray - (-pos-1);
114
0
    }
115
0
}
Unexecuted instantiation: roaring.c:count_greater
Unexecuted instantiation: roaring_array.c:count_greater
Unexecuted instantiation: array_util.c:count_greater
Unexecuted instantiation: array.c:count_greater
Unexecuted instantiation: containers.c:count_greater
Unexecuted instantiation: convert.c:count_greater
Unexecuted instantiation: mixed_intersection.c:count_greater
Unexecuted instantiation: mixed_union.c:count_greater
Unexecuted instantiation: mixed_equal.c:count_greater
Unexecuted instantiation: mixed_subset.c:count_greater
Unexecuted instantiation: mixed_negation.c:count_greater
Unexecuted instantiation: mixed_xor.c:count_greater
Unexecuted instantiation: mixed_andnot.c:count_greater
Unexecuted instantiation: run.c:count_greater
116
117
/**
118
 * From Schlegel et al., Fast Sorted-Set Intersection using SIMD Instructions
119
 * Optimized by D. Lemire on May 3rd 2013
120
 *
121
 * C should have capacity greater than the minimum of s_1 and s_b + 8
122
 * where 8 is sizeof(__m128i)/sizeof(uint16_t).
123
 */
124
int32_t intersect_vector16(const uint16_t *__restrict__ A, size_t s_a,
125
                           const uint16_t *__restrict__ B, size_t s_b,
126
                           uint16_t *C);
127
128
/**
129
 * Compute the cardinality of the intersection using SSE4 instructions
130
 */
131
int32_t intersect_vector16_cardinality(const uint16_t *__restrict__ A,
132
                                       size_t s_a,
133
                                       const uint16_t *__restrict__ B,
134
                                       size_t s_b);
135
136
/* Computes the intersection between one small and one large set of uint16_t.
137
 * Stores the result into buffer and return the number of elements. */
138
int32_t intersect_skewed_uint16(const uint16_t *smallarray, size_t size_s,
139
                                const uint16_t *largearray, size_t size_l,
140
                                uint16_t *buffer);
141
142
/* Computes the size of the intersection between one small and one large set of
143
 * uint16_t. */
144
int32_t intersect_skewed_uint16_cardinality(const uint16_t *smallarray,
145
                                            size_t size_s,
146
                                            const uint16_t *largearray,
147
                                            size_t size_l);
148
149
150
/* Check whether the size of the intersection between one small and one large set of uint16_t is non-zero. */
151
bool intersect_skewed_uint16_nonempty(const uint16_t *smallarray, size_t size_s,
152
                                const uint16_t *largearray, size_t size_l);
153
/**
154
 * Generic intersection function.
155
 */
156
int32_t intersect_uint16(const uint16_t *A, const size_t lenA,
157
                         const uint16_t *B, const size_t lenB, uint16_t *out);
158
/**
159
 * Compute the size of the intersection (generic).
160
 */
161
int32_t intersect_uint16_cardinality(const uint16_t *A, const size_t lenA,
162
                                     const uint16_t *B, const size_t lenB);
163
164
/**
165
 * Checking whether the size of the intersection  is non-zero.
166
 */
167
bool intersect_uint16_nonempty(const uint16_t *A, const size_t lenA,
168
                         const uint16_t *B, const size_t lenB);
169
/**
170
 * Generic union function.
171
 */
172
size_t union_uint16(const uint16_t *set_1, size_t size_1, const uint16_t *set_2,
173
                    size_t size_2, uint16_t *buffer);
174
175
/**
176
 * Generic XOR function.
177
 */
178
int32_t xor_uint16(const uint16_t *array_1, int32_t card_1,
179
                   const uint16_t *array_2, int32_t card_2, uint16_t *out);
180
181
/**
182
 * Generic difference function (ANDNOT).
183
 */
184
int difference_uint16(const uint16_t *a1, int length1, const uint16_t *a2,
185
                      int length2, uint16_t *a_out);
186
187
/**
188
 * Generic intersection function.
189
 */
190
size_t intersection_uint32(const uint32_t *A, const size_t lenA,
191
                           const uint32_t *B, const size_t lenB, uint32_t *out);
192
193
/**
194
 * Generic intersection function, returns just the cardinality.
195
 */
196
size_t intersection_uint32_card(const uint32_t *A, const size_t lenA,
197
                                const uint32_t *B, const size_t lenB);
198
199
/**
200
 * Generic union function.
201
 */
202
size_t union_uint32(const uint32_t *set_1, size_t size_1, const uint32_t *set_2,
203
                    size_t size_2, uint32_t *buffer);
204
205
/**
206
 * A fast SSE-based union function.
207
 */
208
uint32_t union_vector16(const uint16_t *__restrict__ set_1, uint32_t size_1,
209
                        const uint16_t *__restrict__ set_2, uint32_t size_2,
210
                        uint16_t *__restrict__ buffer);
211
/**
212
 * A fast SSE-based XOR function.
213
 */
214
uint32_t xor_vector16(const uint16_t *__restrict__ array1, uint32_t length1,
215
                      const uint16_t *__restrict__ array2, uint32_t length2,
216
                      uint16_t *__restrict__ output);
217
218
/**
219
 * A fast SSE-based difference function.
220
 */
221
int32_t difference_vector16(const uint16_t *__restrict__ A, size_t s_a,
222
                            const uint16_t *__restrict__ B, size_t s_b,
223
                            uint16_t *C);
224
225
/**
226
 * Generic union function, returns just the cardinality.
227
 */
228
size_t union_uint32_card(const uint32_t *set_1, size_t size_1,
229
                         const uint32_t *set_2, size_t size_2);
230
231
/**
232
* combines union_uint16 and  union_vector16 optimally
233
*/
234
size_t fast_union_uint16(const uint16_t *set_1, size_t size_1, const uint16_t *set_2,
235
                    size_t size_2, uint16_t *buffer);
236
237
238
bool memequals(const void *s1, const void *s2, size_t n);
239
240
#ifdef __cplusplus
241
} } }  // extern "C" { namespace roaring { namespace internal {
242
#endif
243
244
#endif