/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 |