/src/croaring/include/roaring/array_util.h

Source (jump to first uncovered line)
#ifndef CROARING_ARRAY_UTIL_H
#define CROARING_ARRAY_UTIL_H

#include <stddef.h>  // for size_t
#include <stdint.h>

#include <roaring/portability.h>

#if CROARING_IS_X64
#ifndef CROARING_COMPILER_SUPPORTS_AVX512
#error "CROARING_COMPILER_SUPPORTS_AVX512 needs to be defined."
#endif  // CROARING_COMPILER_SUPPORTS_AVX512
#endif
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wuninitialized"
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
#endif
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace internal {
#endif

/*
 *  Good old binary search.
 *  Assumes that array is sorted, has logarithmic complexity.
 *  if the result is x, then:
 *     if ( x>0 )  you have array[x] = ikey
 *     if ( x<0 ) then inserting ikey at position -x-1 in array (insuring that
 * array[-x-1]=ikey) keys the array sorted.
 */
inline int32_t binarySearch(const uint16_t *array, int32_t lenarray,
                            uint16_t ikey) {
    int32_t low = 0;
    int32_t high = lenarray - 1;
    while (low <= high) {
        int32_t middleIndex = (low + high) >> 1;
        uint16_t middleValue = array[middleIndex];
        if (middleValue < ikey) {
            low = middleIndex + 1;
        } else if (middleValue > ikey) {
            high = middleIndex - 1;
        } else {
            return middleIndex;
        }
    }
    return -(low + 1);
}

/**
 * Galloping search
 * Assumes that array is sorted, has logarithmic complexity.
 * if the result is x, then if x = length, you have that all values in array
 * between pos and length are smaller than min. otherwise returns the first
 * index x such that array[x] >= min.
 */
static inline int32_t advanceUntil(const uint16_t *array, int32_t pos,
                                   int32_t length, uint16_t min) {
    int32_t lower = pos + 1;

    if ((lower >= length) || (array[lower] >= min)) {
        return lower;
    }

    int32_t spansize = 1;

    while ((lower + spansize < length) && (array[lower + spansize] < min)) {
        spansize <<= 1;
    }
    int32_t upper = (lower + spansize < length) ? lower + spansize : length - 1;

    if (array[upper] == min) {
        return upper;
    }
    if (array[upper] < min) {
        // means
        // array
        // has no
        // item
        // >= min
        // pos = array.length;
        return length;
    }

    // we know that the next-smallest span was too small
    lower += (spansize >> 1);

    int32_t mid = 0;
    while (lower + 1 != upper) {
        mid = (lower + upper) >> 1;
        if (array[mid] == min) {
            return mid;
        } else if (array[mid] < min) {
            lower = mid;
        } else {
            upper = mid;
        }
    }
    return upper;
}

/**
 * Returns number of elements which are less than ikey.
 * Array elements must be unique and sorted.
 */
static inline int32_t count_less(const uint16_t *array, int32_t lenarray,
                                 uint16_t ikey) {
    if (lenarray == 0) return 0;
    int32_t pos = binarySearch(array, lenarray, ikey);
    return pos >= 0 ? pos : -(pos + 1);
}

/**
 * Returns number of elements which are greater than ikey.
 * Array elements must be unique and sorted.
 */
static inline int32_t count_greater(const uint16_t *array, int32_t lenarray,
                                    uint16_t ikey) {
    if (lenarray == 0) return 0;
    int32_t pos = binarySearch(array, lenarray, ikey);
    if (pos >= 0) {
        return lenarray - (pos + 1);
    } else {
        return lenarray - (-pos - 1);
    }
}

/**
 * From Schlegel et al., Fast Sorted-Set Intersection using SIMD Instructions
 * Optimized by D. Lemire on May 3rd 2013
 *
 * C should have capacity greater than the minimum of s_1 and s_b + 8
 * where 8 is sizeof(__m128i)/sizeof(uint16_t).
 */
int32_t intersect_vector16(const uint16_t *__restrict__ A, size_t s_a,
                           const uint16_t *__restrict__ B, size_t s_b,
                           uint16_t *C);

int32_t intersect_vector16_inplace(uint16_t *__restrict__ A, size_t s_a,
                                   const uint16_t *__restrict__ B, size_t s_b);

/**
 * Take an array container and write it out to a 32-bit array, using base
 * as the offset.
 */
int array_container_to_uint32_array_vector16(void *vout, const uint16_t *array,
                                             size_t cardinality, uint32_t base);
#if CROARING_COMPILER_SUPPORTS_AVX512
int avx512_array_container_to_uint32_array(void *vout, const uint16_t *array,
                                           size_t cardinality, uint32_t base);
#endif
/**
 * Compute the cardinality of the intersection using SSE4 instructions
 */
int32_t intersect_vector16_cardinality(const uint16_t *__restrict__ A,
                                       size_t s_a,
                                       const uint16_t *__restrict__ B,
                                       size_t s_b);

/* Computes the intersection between one small and one large set of uint16_t.
 * Stores the result into buffer and return the number of elements. */
int32_t intersect_skewed_uint16(const uint16_t *smallarray, size_t size_s,
                                const uint16_t *largearray, size_t size_l,
                                uint16_t *buffer);

/* Computes the size of the intersection between one small and one large set of
 * uint16_t. */
int32_t intersect_skewed_uint16_cardinality(const uint16_t *smallarray,
                                            size_t size_s,
                                            const uint16_t *largearray,
                                            size_t size_l);

/* Check whether the size of the intersection between one small and one large
 * set of uint16_t is non-zero. */
bool intersect_skewed_uint16_nonempty(const uint16_t *smallarray, size_t size_s,
                                      const uint16_t *largearray,
                                      size_t size_l);
/**
 * Generic intersection function.
 */
int32_t intersect_uint16(const uint16_t *A, const size_t lenA,
                         const uint16_t *B, const size_t lenB, uint16_t *out);
/**
 * Compute the size of the intersection (generic).
 */
int32_t intersect_uint16_cardinality(const uint16_t *A, const size_t lenA,
                                     const uint16_t *B, const size_t lenB);

/**
 * Checking whether the size of the intersection  is non-zero.
 */
bool intersect_uint16_nonempty(const uint16_t *A, const size_t lenA,
                               const uint16_t *B, const size_t lenB);
/**
 * Generic union function.
 */
size_t union_uint16(const uint16_t *set_1, size_t size_1, const uint16_t *set_2,
                    size_t size_2, uint16_t *buffer);

/**
 * Generic XOR function.
 */
int32_t xor_uint16(const uint16_t *array_1, int32_t card_1,
                   const uint16_t *array_2, int32_t card_2, uint16_t *out);

/**
 * Generic difference function (ANDNOT).
 */
int difference_uint16(const uint16_t *a1, int length1, const uint16_t *a2,
                      int length2, uint16_t *a_out);

/**
 * Generic intersection function.
 */
size_t intersection_uint32(const uint32_t *A, const size_t lenA,
                           const uint32_t *B, const size_t lenB, uint32_t *out);

/**
 * Generic intersection function, returns just the cardinality.
 */
size_t intersection_uint32_card(const uint32_t *A, const size_t lenA,
                                const uint32_t *B, const size_t lenB);

/**
 * Generic union function.
 */
size_t union_uint32(const uint32_t *set_1, size_t size_1, const uint32_t *set_2,
                    size_t size_2, uint32_t *buffer);

/**
 * A fast SSE-based union function.
 */
uint32_t union_vector16(const uint16_t *__restrict__ set_1, uint32_t size_1,
                        const uint16_t *__restrict__ set_2, uint32_t size_2,
                        uint16_t *__restrict__ buffer);
/**
 * A fast SSE-based XOR function.
 */
uint32_t xor_vector16(const uint16_t *__restrict__ array1, uint32_t length1,
                      const uint16_t *__restrict__ array2, uint32_t length2,
                      uint16_t *__restrict__ output);

/**
 * A fast SSE-based difference function.
 */
int32_t difference_vector16(const uint16_t *__restrict__ A, size_t s_a,
                            const uint16_t *__restrict__ B, size_t s_b,
                            uint16_t *C);

/**
 * Generic union function, returns just the cardinality.
 */
size_t union_uint32_card(const uint32_t *set_1, size_t size_1,
                         const uint32_t *set_2, size_t size_2);

/**
 * combines union_uint16 and  union_vector16 optimally
 */
size_t fast_union_uint16(const uint16_t *set_1, size_t size_1,
                         const uint16_t *set_2, size_t size_2,
                         uint16_t *buffer);

bool memequals(const void *s1, const void *s2, size_t n);

#ifdef __cplusplus
}
}
}  // extern "C" { namespace roaring { namespace internal {
#endif
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic pop
#endif
#endif

Coverage Report

Created: 2025-02-22 06:30

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