/var/local/thirdparty/installed/include/roaring/roaring_array.h

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

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>

#include <roaring/containers/containers.h>  // get_writable_copy_if_shared()
#include <roaring/array_util.h>

#ifdef __cplusplus
extern "C" { namespace roaring {

// Note: in pure C++ code, you should avoid putting `using` in header files
using api::roaring_array_t;

namespace internal {
#endif

enum {
    SERIAL_COOKIE_NO_RUNCONTAINER = 12346,
    SERIAL_COOKIE = 12347,
    FROZEN_COOKIE = 13766,
    NO_OFFSET_THRESHOLD = 4
};

/**
 * Create a new roaring array
 */
roaring_array_t *ra_create(void);

/**
 * Initialize an existing roaring array with the specified capacity (in number
 * of containers)
 */
bool ra_init_with_capacity(roaring_array_t *new_ra, uint32_t cap);

/**
 * Initialize with zero capacity
 */
void ra_init(roaring_array_t *t);

/**
 * Copies this roaring array, we assume that dest is not initialized
 */
bool ra_copy(const roaring_array_t *source, roaring_array_t *dest,
             bool copy_on_write);

/*
 * Shrinks the capacity, returns the number of bytes saved.
 */
int ra_shrink_to_fit(roaring_array_t *ra);

/**
 * Copies this roaring array, we assume that dest is initialized
 */
bool ra_overwrite(const roaring_array_t *source, roaring_array_t *dest,
                  bool copy_on_write);

/**
 * Frees the memory used by a roaring array
 */
void ra_clear(roaring_array_t *r);

/**
 * Frees the memory used by a roaring array, but does not free the containers
 */
void ra_clear_without_containers(roaring_array_t *r);

/**
 * Frees just the containers
 */
void ra_clear_containers(roaring_array_t *ra);

/**
 * Get the index corresponding to a 16-bit key
 */
inline int32_t ra_get_index(const roaring_array_t *ra, uint16_t x) {
    if ((ra->size == 0) || ra->keys[ra->size - 1] == x) return ra->size - 1;
    return binarySearch(ra->keys, (int32_t)ra->size, x);
}

/**
 * Retrieves the container at index i, filling in the typecode
 */
inline container_t *ra_get_container_at_index(
    const roaring_array_t *ra, uint16_t i, uint8_t *typecode
){
    *typecode = ra->typecodes[i];
    return ra->containers[i];
}

/**
 * Retrieves the key at index i
 */
inline uint16_t ra_get_key_at_index(const roaring_array_t *ra, uint16_t i) {
    return ra->keys[i];
}

/**
 * Add a new key-value pair at index i
 */
void ra_insert_new_key_value_at(
        roaring_array_t *ra, int32_t i, uint16_t key,
        container_t *c, uint8_t typecode);

/**
 * Append a new key-value pair
 */
void ra_append(
        roaring_array_t *ra, uint16_t key,
        container_t *c, uint8_t typecode);

/**
 * Append a new key-value pair to ra, cloning (in COW sense) a value from sa
 * at index index
 */
void ra_append_copy(roaring_array_t *ra, const roaring_array_t *sa,
                    uint16_t index, bool copy_on_write);

/**
 * Append new key-value pairs to ra, cloning (in COW sense)  values from sa
 * at indexes
 * [start_index, end_index)
 */
void ra_append_copy_range(roaring_array_t *ra, const roaring_array_t *sa,
                          int32_t start_index, int32_t end_index,
                          bool copy_on_write);

/** appends from sa to ra, ending with the greatest key that is
 * is less or equal stopping_key
 */
void ra_append_copies_until(roaring_array_t *ra, const roaring_array_t *sa,
                            uint16_t stopping_key, bool copy_on_write);

/** appends from sa to ra, starting with the smallest key that is
 * is strictly greater than before_start
 */

void ra_append_copies_after(roaring_array_t *ra, const roaring_array_t *sa,
                            uint16_t before_start, bool copy_on_write);

/**
 * Move the key-value pairs to ra from sa at indexes
 * [start_index, end_index), old array should not be freed
 * (use ra_clear_without_containers)
 **/
void ra_append_move_range(roaring_array_t *ra, roaring_array_t *sa,
                          int32_t start_index, int32_t end_index);
/**
 * Append new key-value pairs to ra,  from sa at indexes
 * [start_index, end_index)
 */
void ra_append_range(roaring_array_t *ra, roaring_array_t *sa,
                     int32_t start_index, int32_t end_index,
                     bool copy_on_write);

/**
 * Set the container at the corresponding index using the specified
 * typecode.
 */
inline void ra_set_container_at_index(
    const roaring_array_t *ra, int32_t i,
    container_t *c, uint8_t typecode
){
    assert(i < ra->size);
    ra->containers[i] = c;
    ra->typecodes[i] = typecode;
}

container_t *ra_get_container(roaring_array_t *ra, uint16_t x, uint8_t *typecode);

/**
 * If needed, increase the capacity of the array so that it can fit k values
 * (at
 * least);
 */
bool extend_array(roaring_array_t *ra, int32_t k);

inline int32_t ra_get_size(const roaring_array_t *ra) { return ra->size; }

static inline int32_t ra_advance_until(const roaring_array_t *ra, uint16_t x,
                                       int32_t pos) {
    return advanceUntil(ra->keys, pos, ra->size, x);
}

int32_t ra_advance_until_freeing(roaring_array_t *ra, uint16_t x, int32_t pos);

void ra_downsize(roaring_array_t *ra, int32_t new_length);

inline void ra_replace_key_and_container_at_index(
    roaring_array_t *ra, int32_t i, uint16_t key,
    container_t *c, uint8_t typecode
){
    assert(i < ra->size);

    ra->keys[i] = key;
    ra->containers[i] = c;
    ra->typecodes[i] = typecode;
}

// write set bits to an array
void ra_to_uint32_array(const roaring_array_t *ra, uint32_t *ans);

bool ra_range_uint32_array(const roaring_array_t *ra, size_t offset, size_t limit, uint32_t *ans);

/**
 * write a bitmap to a buffer. This is meant to be compatible with
 * the
 * Java and Go versions. Return the size in bytes of the serialized
 * output (which should be ra_portable_size_in_bytes(ra)).
 */
size_t ra_portable_serialize(const roaring_array_t *ra, char *buf);

/**
 * read a bitmap from a serialized version. This is meant to be compatible
 * with the Java and Go versions.
 * maxbytes  indicates how many bytes available from buf.
 * When the function returns true, roaring_array_t is populated with the data
 * and *readbytes indicates how many bytes were read. In all cases, if the function
 * returns true, then maxbytes >= *readbytes.
 */
bool ra_portable_deserialize(roaring_array_t *ra, const char *buf, const size_t maxbytes, size_t * readbytes);

/**
 * Quickly checks whether there is a serialized bitmap at the pointer,
 * not exceeding size "maxbytes" in bytes. This function does not allocate
 * memory dynamically.
 *
 * This function returns 0 if and only if no valid bitmap is found.
 * Otherwise, it returns how many bytes are occupied by the bitmap data.
 */
size_t ra_portable_deserialize_size(const char *buf, const size_t maxbytes);

/**
 * How many bytes are required to serialize this bitmap (meant to be
 * compatible
 * with Java and Go versions)
 */
size_t ra_portable_size_in_bytes(const roaring_array_t *ra);

/**
 * return true if it contains at least one run container.
 */
bool ra_has_run_container(const roaring_array_t *ra);

/**
 * Size of the header when serializing (meant to be compatible
 * with Java and Go versions)
 */
uint32_t ra_portable_header_size(const roaring_array_t *ra);

/**
 * If the container at the index i is share, unshare it (creating a local
 * copy if needed).
 */
static inline void ra_unshare_container_at_index(roaring_array_t *ra,
                                                 uint16_t i) {
    assert(i < ra->size);
    ra->containers[i] = get_writable_copy_if_shared(ra->containers[i],
                                                    &ra->typecodes[i]);
}

/**
 * remove at index i, sliding over all entries after i
 */
void ra_remove_at_index(roaring_array_t *ra, int32_t i);


/**
* clears all containers, sets the size at 0 and shrinks the memory usage.
*/
void ra_reset(roaring_array_t *ra);

/**
 * remove at index i, sliding over all entries after i. Free removed container.
 */
void ra_remove_at_index_and_free(roaring_array_t *ra, int32_t i);

/**
 * remove a chunk of indices, sliding over entries after it
 */
// void ra_remove_index_range(roaring_array_t *ra, int32_t begin, int32_t end);

// used in inplace andNot only, to slide left the containers from
// the mutated RoaringBitmap that are after the largest container of
// the argument RoaringBitmap.  It is followed by a call to resize.
//
void ra_copy_range(roaring_array_t *ra, uint32_t begin, uint32_t end,
                   uint32_t new_begin);

/**
 * Shifts rightmost $count containers to the left (distance < 0) or
 * to the right (distance > 0).
 * Allocates memory if necessary.
 * This function doesn't free or create new containers.
 * Caller is responsible for that.
 */
void ra_shift_tail(roaring_array_t *ra, int32_t count, int32_t distance);

#ifdef __cplusplus
}  // namespace internal
} }  // extern "C" { namespace roaring {
#endif

#endif

Coverage Report

Created: 2024-11-21 15:53

Line	Count	Source (jump to first uncovered line)
1		#ifndef INCLUDE_ROARING_ARRAY_H
2		#define INCLUDE_ROARING_ARRAY_H
3
4		#include <assert.h>
5		#include <stdbool.h>
6		#include <stdint.h>
7
8		#include <roaring/containers/containers.h> // get_writable_copy_if_shared()
9		#include <roaring/array_util.h>
10
11		#ifdef __cplusplus
12		extern "C" { namespace roaring {
13
14		// Note: in pure C++ code, you should avoid putting `using` in header files
15		using api::roaring_array_t;
16
17		namespace internal {
18		#endif
19
20		enum {
21		SERIAL_COOKIE_NO_RUNCONTAINER = 12346,
22		SERIAL_COOKIE = 12347,
23		FROZEN_COOKIE = 13766,
24		NO_OFFSET_THRESHOLD = 4
25		};
26
27		/**
28		* Create a new roaring array
29		*/
30		roaring_array_t *ra_create(void);
31
32		/**
33		* Initialize an existing roaring array with the specified capacity (in number
34		* of containers)
35		*/
36		bool ra_init_with_capacity(roaring_array_t *new_ra, uint32_t cap);
37
38		/**
39		* Initialize with zero capacity
40		*/
41		void ra_init(roaring_array_t *t);
42
43		/**
44		* Copies this roaring array, we assume that dest is not initialized
45		*/
46		bool ra_copy(const roaring_array_t source, roaring_array_t dest,
47		bool copy_on_write);
48
49		/*
50		* Shrinks the capacity, returns the number of bytes saved.
51		*/
52		int ra_shrink_to_fit(roaring_array_t *ra);
53
54		/**
55		* Copies this roaring array, we assume that dest is initialized
56		*/
57		bool ra_overwrite(const roaring_array_t source, roaring_array_t dest,
58		bool copy_on_write);
59
60		/**
61		* Frees the memory used by a roaring array
62		*/
63		void ra_clear(roaring_array_t *r);
64
65		/**
66		* Frees the memory used by a roaring array, but does not free the containers
67		*/
68		void ra_clear_without_containers(roaring_array_t *r);
69
70		/**
71		* Frees just the containers
72		*/
73		void ra_clear_containers(roaring_array_t *ra);
74
75		/**
76		* Get the index corresponding to a 16-bit key
77		*/
78	0	inline int32_t ra_get_index(const roaring_array_t *ra, uint16_t x) {
79	0	if ((ra->size == 0) \|\| ra->keys[ra->size - 1] == x) return ra->size - 1;
80	0	return binarySearch(ra->keys, (int32_t)ra->size, x);
81	0	}
82
83		/**
84		* Retrieves the container at index i, filling in the typecode
85		*/
86		inline container_t *ra_get_container_at_index(
87		const roaring_array_t ra, uint16_t i, uint8_t typecode
88	0	){
89	0	*typecode = ra->typecodes[i];
90	0	return ra->containers[i];
91	0	}
92
93		/**
94		* Retrieves the key at index i
95		*/
96	0	inline uint16_t ra_get_key_at_index(const roaring_array_t *ra, uint16_t i) {
97	0	return ra->keys[i];
98	0	}
99
100		/**
101		* Add a new key-value pair at index i
102		*/
103		void ra_insert_new_key_value_at(
104		roaring_array_t *ra, int32_t i, uint16_t key,
105		container_t *c, uint8_t typecode);
106
107		/**
108		* Append a new key-value pair
109		*/
110		void ra_append(
111		roaring_array_t *ra, uint16_t key,
112		container_t *c, uint8_t typecode);
113
114		/**
115		* Append a new key-value pair to ra, cloning (in COW sense) a value from sa
116		* at index index
117		*/
118		void ra_append_copy(roaring_array_t ra, const roaring_array_t sa,
119		uint16_t index, bool copy_on_write);
120
121		/**
122		* Append new key-value pairs to ra, cloning (in COW sense) values from sa
123		* at indexes
124		* [start_index, end_index)
125		*/
126		void ra_append_copy_range(roaring_array_t ra, const roaring_array_t sa,
127		int32_t start_index, int32_t end_index,
128		bool copy_on_write);
129
130		/** appends from sa to ra, ending with the greatest key that is
131		* is less or equal stopping_key
132		*/
133		void ra_append_copies_until(roaring_array_t ra, const roaring_array_t sa,
134		uint16_t stopping_key, bool copy_on_write);
135
136		/** appends from sa to ra, starting with the smallest key that is
137		* is strictly greater than before_start
138		*/
139
140		void ra_append_copies_after(roaring_array_t ra, const roaring_array_t sa,
141		uint16_t before_start, bool copy_on_write);
142
143		/**
144		* Move the key-value pairs to ra from sa at indexes
145		* [start_index, end_index), old array should not be freed
146		* (use ra_clear_without_containers)
147		**/
148		void ra_append_move_range(roaring_array_t ra, roaring_array_t sa,
149		int32_t start_index, int32_t end_index);
150		/**
151		* Append new key-value pairs to ra, from sa at indexes
152		* [start_index, end_index)
153		*/
154		void ra_append_range(roaring_array_t ra, roaring_array_t sa,
155		int32_t start_index, int32_t end_index,
156		bool copy_on_write);
157
158		/**
159		* Set the container at the corresponding index using the specified
160		* typecode.
161		*/
162		inline void ra_set_container_at_index(
163		const roaring_array_t *ra, int32_t i,
164		container_t *c, uint8_t typecode
165	0	){
166	0	assert(i < ra->size);
167	0	ra->containers[i] = c;
168	0	ra->typecodes[i] = typecode;
169	0	}
170
171		container_t ra_get_container(roaring_array_t ra, uint16_t x, uint8_t *typecode);
172
173		/**
174		* If needed, increase the capacity of the array so that it can fit k values
175		* (at
176		* least);
177		*/
178		bool extend_array(roaring_array_t *ra, int32_t k);
179
180	0	inline int32_t ra_get_size(const roaring_array_t *ra) { return ra->size; }
181
182		static inline int32_t ra_advance_until(const roaring_array_t *ra, uint16_t x,
183	0	int32_t pos) {
184	0	return advanceUntil(ra->keys, pos, ra->size, x);
185	0	} Unexecuted instantiation: bkd_writer.cpp:_ZN7roaring8internalL16ra_advance_untilEPKNS_3api15roaring_array_sEti Unexecuted instantiation: bkd_reader.cpp:_ZN7roaring8internalL16ra_advance_untilEPKNS_3api15roaring_array_sEti Unexecuted instantiation: packed_index_tree.cpp:_ZN7roaring8internalL16ra_advance_untilEPKNS_3api15roaring_array_sEti Unexecuted instantiation: index_tree.cpp:_ZN7roaring8internalL16ra_advance_untilEPKNS_3api15roaring_array_sEti Unexecuted instantiation: legacy_index_tree.cpp:_ZN7roaring8internalL16ra_advance_untilEPKNS_3api15roaring_array_sEti Unexecuted instantiation: docids_writer.cpp:_ZN7roaring8internalL16ra_advance_untilEPKNS_3api15roaring_array_sEti Unexecuted instantiation: IndexWriter.cpp:_ZN7roaring8internalL16ra_advance_untilEPKNS_3api15roaring_array_sEti
186
187		int32_t ra_advance_until_freeing(roaring_array_t *ra, uint16_t x, int32_t pos);
188
189		void ra_downsize(roaring_array_t *ra, int32_t new_length);
190
191		inline void ra_replace_key_and_container_at_index(
192		roaring_array_t *ra, int32_t i, uint16_t key,
193		container_t *c, uint8_t typecode
194	0	){
195	0	assert(i < ra->size);
196	0
197	0	ra->keys[i] = key;
198	0	ra->containers[i] = c;
199	0	ra->typecodes[i] = typecode;
200	0	}
201
202		// write set bits to an array
203		void ra_to_uint32_array(const roaring_array_t ra, uint32_t ans);
204
205		bool ra_range_uint32_array(const roaring_array_t ra, size_t offset, size_t limit, uint32_t ans);
206
207		/**
208		* write a bitmap to a buffer. This is meant to be compatible with
209		* the
210		* Java and Go versions. Return the size in bytes of the serialized
211		* output (which should be ra_portable_size_in_bytes(ra)).
212		*/
213		size_t ra_portable_serialize(const roaring_array_t ra, char buf);
214
215		/**
216		* read a bitmap from a serialized version. This is meant to be compatible
217		* with the Java and Go versions.
218		* maxbytes indicates how many bytes available from buf.
219		* When the function returns true, roaring_array_t is populated with the data
220		* and *readbytes indicates how many bytes were read. In all cases, if the function
221		* returns true, then maxbytes >= *readbytes.
222		*/
223		bool ra_portable_deserialize(roaring_array_t ra, const char buf, const size_t maxbytes, size_t * readbytes);
224
225		/**
226		* Quickly checks whether there is a serialized bitmap at the pointer,
227		* not exceeding size "maxbytes" in bytes. This function does not allocate
228		* memory dynamically.
229		*
230		* This function returns 0 if and only if no valid bitmap is found.
231		* Otherwise, it returns how many bytes are occupied by the bitmap data.
232		*/
233		size_t ra_portable_deserialize_size(const char *buf, const size_t maxbytes);
234
235		/**
236		* How many bytes are required to serialize this bitmap (meant to be
237		* compatible
238		* with Java and Go versions)
239		*/
240		size_t ra_portable_size_in_bytes(const roaring_array_t *ra);
241
242		/**
243		* return true if it contains at least one run container.
244		*/
245		bool ra_has_run_container(const roaring_array_t *ra);
246
247		/**
248		* Size of the header when serializing (meant to be compatible
249		* with Java and Go versions)
250		*/
251		uint32_t ra_portable_header_size(const roaring_array_t *ra);
252
253		/**
254		* If the container at the index i is share, unshare it (creating a local
255		* copy if needed).
256		*/
257		static inline void ra_unshare_container_at_index(roaring_array_t *ra,
258	0	uint16_t i) {
259	0	assert(i < ra->size);
260	0	ra->containers[i] = get_writable_copy_if_shared(ra->containers[i],
261	0	&ra->typecodes[i]);
262	0	} Unexecuted instantiation: bkd_writer.cpp:_ZN7roaring8internalL29ra_unshare_container_at_indexEPNS_3api15roaring_array_sEt Unexecuted instantiation: bkd_reader.cpp:_ZN7roaring8internalL29ra_unshare_container_at_indexEPNS_3api15roaring_array_sEt Unexecuted instantiation: packed_index_tree.cpp:_ZN7roaring8internalL29ra_unshare_container_at_indexEPNS_3api15roaring_array_sEt Unexecuted instantiation: index_tree.cpp:_ZN7roaring8internalL29ra_unshare_container_at_indexEPNS_3api15roaring_array_sEt Unexecuted instantiation: legacy_index_tree.cpp:_ZN7roaring8internalL29ra_unshare_container_at_indexEPNS_3api15roaring_array_sEt Unexecuted instantiation: docids_writer.cpp:_ZN7roaring8internalL29ra_unshare_container_at_indexEPNS_3api15roaring_array_sEt Unexecuted instantiation: IndexWriter.cpp:_ZN7roaring8internalL29ra_unshare_container_at_indexEPNS_3api15roaring_array_sEt
263
264		/**
265		* remove at index i, sliding over all entries after i
266		*/
267		void ra_remove_at_index(roaring_array_t *ra, int32_t i);
268
269
270		/**
271		* clears all containers, sets the size at 0 and shrinks the memory usage.
272		*/
273		void ra_reset(roaring_array_t *ra);
274
275		/**
276		* remove at index i, sliding over all entries after i. Free removed container.
277		*/
278		void ra_remove_at_index_and_free(roaring_array_t *ra, int32_t i);
279
280		/**
281		* remove a chunk of indices, sliding over entries after it
282		*/
283		// void ra_remove_index_range(roaring_array_t *ra, int32_t begin, int32_t end);
284
285		// used in inplace andNot only, to slide left the containers from
286		// the mutated RoaringBitmap that are after the largest container of
287		// the argument RoaringBitmap. It is followed by a call to resize.
288		//
289		void ra_copy_range(roaring_array_t *ra, uint32_t begin, uint32_t end,
290		uint32_t new_begin);
291
292		/**
293		* Shifts rightmost $count containers to the left (distance < 0) or
294		* to the right (distance > 0).
295		* Allocates memory if necessary.
296		* This function doesn't free or create new containers.
297		* Caller is responsible for that.
298		*/
299		void ra_shift_tail(roaring_array_t *ra, int32_t count, int32_t distance);
300
301		#ifdef __cplusplus
302		} // namespace internal
303		} } // extern "C" { namespace roaring {
304		#endif
305
306		#endif