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

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

// For compatibility with MSVC with the use of `restrict`
#if (__STDC_VERSION__ >= 199901L) || \
    (defined(__GNUC__) && defined(__STDC_VERSION__))
#define CBITSET_RESTRICT restrict
#else
#define CBITSET_RESTRICT
#endif  // (__STDC_VERSION__ >= 199901L) || (defined(__GNUC__) &&
        // defined(__STDC_VERSION__ ))

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <roaring/portability.h>

#ifdef __cplusplus
extern "C" { namespace roaring { namespace api {
#endif

struct bitset_s {
    uint64_t *CBITSET_RESTRICT array;
    /* For simplicity and performance, we prefer to have a size and a capacity that is a multiple of 64 bits.
     * Thus we only track the size and the capacity in terms of 64-bit words allocated */
    size_t arraysize;
    size_t capacity;
};

typedef struct bitset_s bitset_t;

/* Create a new bitset. Return NULL in case of failure. */
bitset_t *bitset_create(void);

/* Create a new bitset able to contain size bits. Return NULL in case of
 * failure. */
bitset_t *bitset_create_with_capacity(size_t size);

/* Free memory. */
void bitset_free(bitset_t *bitset);

/* Set all bits to zero. */
void bitset_clear(bitset_t *bitset);

/* Set all bits to one. */
void bitset_fill(bitset_t *bitset);

/* Create a copy */
bitset_t *bitset_copy(const bitset_t *bitset);

/* For advanced users: Resize the bitset so that it can support newarraysize * 64 bits.
 * Return true in case of success, false for failure. Pad
 * with zeroes new buffer areas if requested. */
bool bitset_resize(bitset_t *bitset, size_t newarraysize, bool padwithzeroes);

/* returns how many bytes of memory the backend buffer uses */
inline size_t bitset_size_in_bytes(const bitset_t *bitset) {
    return bitset->arraysize * sizeof(uint64_t);
}

/* returns how many bits can be accessed */
inline size_t bitset_size_in_bits(const bitset_t *bitset) {
    return bitset->arraysize * 64;
}

/* returns how many words (64-bit) of memory the backend buffer uses */
inline size_t bitset_size_in_words(const bitset_t *bitset) {
    return bitset->arraysize;
}

/* For advanced users: Grow the bitset so that it can support newarraysize * 64 bits with padding.
 * Return true in case of success, false for failure. */
bool bitset_grow(bitset_t *bitset, size_t newarraysize);

/* attempts to recover unused memory, return false in case of roaring_reallocation
 * failure */
bool bitset_trim(bitset_t *bitset);

/* shifts all bits by 's' positions so that the bitset representing values
 * 1,2,10 would represent values 1+s, 2+s, 10+s */
void bitset_shift_left(bitset_t *bitset, size_t s);

/* shifts all bits by 's' positions so that the bitset representing values
 * 1,2,10 would represent values 1-s, 2-s, 10-s, negative values are deleted */
void bitset_shift_right(bitset_t *bitset, size_t s);

/* Set the ith bit. Attempts to resize the bitset if needed (may silently fail)
 */
inline void bitset_set(bitset_t *bitset, size_t i) {
    size_t shiftedi = i / 64;
    if (shiftedi >= bitset->arraysize) {
        if (!bitset_grow(bitset, shiftedi + 1)) {
            return;
        }
    }
    bitset->array[shiftedi] |= ((uint64_t)1) << (i % 64);
}

/* Set the ith bit to the specified value. Attempts to resize the bitset if
 * needed (may silently fail) */
inline void bitset_set_to_value(bitset_t *bitset, size_t i, bool flag) {
    size_t shiftedi = i / 64;
    uint64_t mask = ((uint64_t)1) << (i % 64);
    uint64_t dynmask = ((uint64_t)flag) << (i % 64);
    if (shiftedi >= bitset->arraysize) {
        if (!bitset_grow(bitset, shiftedi + 1)) {
            return;
        }
    }
    uint64_t w = bitset->array[shiftedi];
    w &= ~mask;
    w |= dynmask;
    bitset->array[shiftedi] = w;
}

/* Get the value of the ith bit.  */
inline bool bitset_get(const bitset_t *bitset, size_t i) {
    size_t shiftedi = i / 64;
    if (shiftedi >= bitset->arraysize) {
        return false;
    }
    return (bitset->array[shiftedi] & (((uint64_t)1) << (i % 64))) != 0;
}

/* Count number of bits set.  */
size_t bitset_count(const bitset_t *bitset);

/* Find the index of the first bit set. Or zero if the bitset is empty.  */
size_t bitset_minimum(const bitset_t *bitset);

/* Find the index of the last bit set. Or zero if the bitset is empty.  */
size_t bitset_maximum(const bitset_t *bitset);

/* compute the union in-place (to b1), returns true if successful, to generate a
 * new bitset first call bitset_copy */
bool bitset_inplace_union(bitset_t *CBITSET_RESTRICT b1,
                          const bitset_t *CBITSET_RESTRICT b2);

/* report the size of the union (without materializing it) */
size_t bitset_union_count(const bitset_t *CBITSET_RESTRICT b1,
                          const bitset_t *CBITSET_RESTRICT b2);

/* compute the intersection in-place (to b1), to generate a new bitset first
 * call bitset_copy */
void bitset_inplace_intersection(bitset_t *CBITSET_RESTRICT b1,
                                 const bitset_t *CBITSET_RESTRICT b2);

/* report the size of the intersection (without materializing it) */
size_t bitset_intersection_count(const bitset_t *CBITSET_RESTRICT b1,
                                 const bitset_t *CBITSET_RESTRICT b2);

/* returns true if the bitsets contain no common elements */
bool bitsets_disjoint(const bitset_t *CBITSET_RESTRICT b1, const bitset_t *CBITSET_RESTRICT b2);

/* returns true if the bitsets contain any common elements */
bool bitsets_intersect(const bitset_t *CBITSET_RESTRICT b1, const bitset_t *CBITSET_RESTRICT b2);

/* returns true if b1 contains all of the set bits of b2 */
bool bitset_contains_all(const bitset_t *CBITSET_RESTRICT b1, const bitset_t *CBITSET_RESTRICT b2);

/* compute the difference in-place (to b1), to generate a new bitset first call
 * bitset_copy */
void bitset_inplace_difference(bitset_t *CBITSET_RESTRICT b1,
                               const bitset_t *CBITSET_RESTRICT b2);

/* compute the size of the difference */
size_t bitset_difference_count(const bitset_t *CBITSET_RESTRICT b1,
                               const bitset_t *CBITSET_RESTRICT b2);

/* compute the symmetric difference in-place (to b1), return true if successful,
 * to generate a new bitset first call bitset_copy */
bool bitset_inplace_symmetric_difference(bitset_t *CBITSET_RESTRICT b1,
                                         const bitset_t *CBITSET_RESTRICT b2);

/* compute the size of the symmetric difference  */
size_t bitset_symmetric_difference_count(const bitset_t *CBITSET_RESTRICT b1,
                                         const bitset_t *CBITSET_RESTRICT b2);

/* iterate over the set bits
 like so :
  for(size_t i = 0; bitset_next_set_bit(b,&i) ; i++) {
    //.....
  }
  */
inline bool bitset_next_set_bit(const bitset_t *bitset, size_t *i) {
    size_t x = *i / 64;
    if (x >= bitset->arraysize) {
        return false;
    }
    uint64_t w = bitset->array[x];
    w >>= (*i & 63);
    if (w != 0) {
        *i += roaring_trailing_zeroes(w);
        return true;
    }
    x++;
    while (x < bitset->arraysize) {
        w = bitset->array[x];
        if (w != 0) {
            *i = x * 64 + roaring_trailing_zeroes(w);
            return true;
        }
        x++;
    }
    return false;
}

/* iterate over the set bits
 like so :
   size_t buffer[256];
   size_t howmany = 0;
  for(size_t startfrom = 0; (howmany = bitset_next_set_bits(b,buffer,256, &startfrom)) >
 0 ; startfrom++) {
    //.....
  }
  */
inline size_t bitset_next_set_bits(const bitset_t *bitset, size_t *buffer,
                                   size_t capacity, size_t *startfrom) {
    if (capacity == 0) return 0;  // sanity check
    size_t x = *startfrom / 64;
    if (x >= bitset->arraysize) {
        return 0;  // nothing more to iterate over
    }
    uint64_t w = bitset->array[x];
    w >>= (*startfrom & 63);
    size_t howmany = 0;
    size_t base = x << 6;
    while (howmany < capacity) {
        while (w != 0) {
            uint64_t t = w & (~w + 1);
            int r = roaring_trailing_zeroes(w);
            buffer[howmany++] = r + base;
            if (howmany == capacity) goto end;
            w ^= t;
        }
        x += 1;
        if (x == bitset->arraysize) {
            break;
        }
        base += 64;
        w = bitset->array[x];
    }
end:
    if (howmany > 0) {
        *startfrom = buffer[howmany - 1];
    }
    return howmany;
}

typedef bool (*bitset_iterator)(size_t value, void *param);

// return true if uninterrupted
inline bool bitset_for_each(const bitset_t *b, bitset_iterator iterator,
                            void *ptr) {
    size_t base = 0;
    for (size_t i = 0; i < b->arraysize; ++i) {
        uint64_t w = b->array[i];
        while (w != 0) {
            uint64_t t = w & (~w + 1);
            int r = roaring_trailing_zeroes(w);
            if (!iterator(r + base, ptr)) return false;
            w ^= t;
        }
        base += 64;
    }
    return true;
}

inline void bitset_print(const bitset_t *b) {
    printf("{");
    for (size_t i = 0; bitset_next_set_bit(b, &i); i++) {
        printf("%zu, ", i);
    }
    printf("}");
}

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

#endif

Coverage Report

Created: 2024-11-21 23:52

Line	Count	Source (jump to first uncovered line)
1		#ifndef CBITSET_BITSET_H
2		#define CBITSET_BITSET_H
3
4		// For compatibility with MSVC with the use of `restrict`
5		#if (__STDC_VERSION__ >= 199901L) \|\| \
6		(defined(__GNUC__) && defined(__STDC_VERSION__))
7		#define CBITSET_RESTRICT restrict
8		#else
9		#define CBITSET_RESTRICT
10		#endif // (__STDC_VERSION__ >= 199901L) \|\| (defined(__GNUC__) &&
11		// defined(__STDC_VERSION__ ))
12
13		#include <stdbool.h>
14		#include <stdint.h>
15		#include <stdio.h>
16		#include <stdlib.h>
17		#include <string.h>
18		#include <roaring/portability.h>
19
20		#ifdef __cplusplus
21		extern "C" { namespace roaring { namespace api {
22		#endif
23
24		struct bitset_s {
25		uint64_t *CBITSET_RESTRICT array;
26		/* For simplicity and performance, we prefer to have a size and a capacity that is a multiple of 64 bits.
27		* Thus we only track the size and the capacity in terms of 64-bit words allocated */
28		size_t arraysize;
29		size_t capacity;
30		};
31
32		typedef struct bitset_s bitset_t;
33
34		/* Create a new bitset. Return NULL in case of failure. */
35		bitset_t *bitset_create(void);
36
37		/* Create a new bitset able to contain size bits. Return NULL in case of
38		* failure. */
39		bitset_t *bitset_create_with_capacity(size_t size);
40
41		/* Free memory. */
42		void bitset_free(bitset_t *bitset);
43
44		/* Set all bits to zero. */
45		void bitset_clear(bitset_t *bitset);
46
47		/* Set all bits to one. */
48		void bitset_fill(bitset_t *bitset);
49
50		/* Create a copy */
51		bitset_t bitset_copy(const bitset_t bitset);
52
53		/* For advanced users: Resize the bitset so that it can support newarraysize * 64 bits.
54		* Return true in case of success, false for failure. Pad
55		* with zeroes new buffer areas if requested. */
56		bool bitset_resize(bitset_t *bitset, size_t newarraysize, bool padwithzeroes);
57
58		/* returns how many bytes of memory the backend buffer uses */
59	0	inline size_t bitset_size_in_bytes(const bitset_t *bitset) {
60	0	return bitset->arraysize * sizeof(uint64_t);
61	0	}
62
63		/* returns how many bits can be accessed */
64	0	inline size_t bitset_size_in_bits(const bitset_t *bitset) {
65	0	return bitset->arraysize * 64;
66	0	}
67
68		/* returns how many words (64-bit) of memory the backend buffer uses */
69	0	inline size_t bitset_size_in_words(const bitset_t *bitset) {
70	0	return bitset->arraysize;
71	0	}
72
73		/* For advanced users: Grow the bitset so that it can support newarraysize * 64 bits with padding.
74		* Return true in case of success, false for failure. */
75		bool bitset_grow(bitset_t *bitset, size_t newarraysize);
76
77		/* attempts to recover unused memory, return false in case of roaring_reallocation
78		* failure */
79		bool bitset_trim(bitset_t *bitset);
80
81		/* shifts all bits by 's' positions so that the bitset representing values
82		* 1,2,10 would represent values 1+s, 2+s, 10+s */
83		void bitset_shift_left(bitset_t *bitset, size_t s);
84
85		/* shifts all bits by 's' positions so that the bitset representing values
86		* 1,2,10 would represent values 1-s, 2-s, 10-s, negative values are deleted */
87		void bitset_shift_right(bitset_t *bitset, size_t s);
88
89		/* Set the ith bit. Attempts to resize the bitset if needed (may silently fail)
90		*/
91	0	inline void bitset_set(bitset_t *bitset, size_t i) {
92	0	size_t shiftedi = i / 64;
93	0	if (shiftedi >= bitset->arraysize) {
94	0	if (!bitset_grow(bitset, shiftedi + 1)) {
95	0	return;
96	0	}
97	0	}
98	0	bitset->array[shiftedi] \|= ((uint64_t)1) << (i % 64);
99	0	}
100
101		/* Set the ith bit to the specified value. Attempts to resize the bitset if
102		* needed (may silently fail) */
103	0	inline void bitset_set_to_value(bitset_t *bitset, size_t i, bool flag) {
104	0	size_t shiftedi = i / 64;
105	0	uint64_t mask = ((uint64_t)1) << (i % 64);
106	0	uint64_t dynmask = ((uint64_t)flag) << (i % 64);
107	0	if (shiftedi >= bitset->arraysize) {
108	0	if (!bitset_grow(bitset, shiftedi + 1)) {
109	0	return;
110	0	}
111	0	}
112	0	uint64_t w = bitset->array[shiftedi];
113	0	w &= ~mask;
114	0	w \|= dynmask;
115	0	bitset->array[shiftedi] = w;
116	0	}
117
118		/* Get the value of the ith bit. */
119	0	inline bool bitset_get(const bitset_t *bitset, size_t i) {
120	0	size_t shiftedi = i / 64;
121	0	if (shiftedi >= bitset->arraysize) {
122	0	return false;
123	0	}
124	0	return (bitset->array[shiftedi] & (((uint64_t)1) << (i % 64))) != 0;
125	0	}
126
127		/* Count number of bits set. */
128		size_t bitset_count(const bitset_t *bitset);
129
130		/* Find the index of the first bit set. Or zero if the bitset is empty. */
131		size_t bitset_minimum(const bitset_t *bitset);
132
133		/* Find the index of the last bit set. Or zero if the bitset is empty. */
134		size_t bitset_maximum(const bitset_t *bitset);
135
136		/* compute the union in-place (to b1), returns true if successful, to generate a
137		* new bitset first call bitset_copy */
138		bool bitset_inplace_union(bitset_t *CBITSET_RESTRICT b1,
139		const bitset_t *CBITSET_RESTRICT b2);
140
141		/* report the size of the union (without materializing it) */
142		size_t bitset_union_count(const bitset_t *CBITSET_RESTRICT b1,
143		const bitset_t *CBITSET_RESTRICT b2);
144
145		/* compute the intersection in-place (to b1), to generate a new bitset first
146		* call bitset_copy */
147		void bitset_inplace_intersection(bitset_t *CBITSET_RESTRICT b1,
148		const bitset_t *CBITSET_RESTRICT b2);
149
150		/* report the size of the intersection (without materializing it) */
151		size_t bitset_intersection_count(const bitset_t *CBITSET_RESTRICT b1,
152		const bitset_t *CBITSET_RESTRICT b2);
153
154		/* returns true if the bitsets contain no common elements */
155		bool bitsets_disjoint(const bitset_t CBITSET_RESTRICT b1, const bitset_t CBITSET_RESTRICT b2);
156
157		/* returns true if the bitsets contain any common elements */
158		bool bitsets_intersect(const bitset_t CBITSET_RESTRICT b1, const bitset_t CBITSET_RESTRICT b2);
159
160		/* returns true if b1 contains all of the set bits of b2 */
161		bool bitset_contains_all(const bitset_t CBITSET_RESTRICT b1, const bitset_t CBITSET_RESTRICT b2);
162
163		/* compute the difference in-place (to b1), to generate a new bitset first call
164		* bitset_copy */
165		void bitset_inplace_difference(bitset_t *CBITSET_RESTRICT b1,
166		const bitset_t *CBITSET_RESTRICT b2);
167
168		/* compute the size of the difference */
169		size_t bitset_difference_count(const bitset_t *CBITSET_RESTRICT b1,
170		const bitset_t *CBITSET_RESTRICT b2);
171
172		/* compute the symmetric difference in-place (to b1), return true if successful,
173		* to generate a new bitset first call bitset_copy */
174		bool bitset_inplace_symmetric_difference(bitset_t *CBITSET_RESTRICT b1,
175		const bitset_t *CBITSET_RESTRICT b2);
176
177		/* compute the size of the symmetric difference */
178		size_t bitset_symmetric_difference_count(const bitset_t *CBITSET_RESTRICT b1,
179		const bitset_t *CBITSET_RESTRICT b2);
180
181		/* iterate over the set bits
182		like so :
183		for(size_t i = 0; bitset_next_set_bit(b,&i) ; i++) {
184		//.....
185		}
186		*/
187	0	inline bool bitset_next_set_bit(const bitset_t bitset, size_t i) {
188	0	size_t x = *i / 64;
189	0	if (x >= bitset->arraysize) {
190	0	return false;
191	0	}
192	0	uint64_t w = bitset->array[x];
193	0	w >>= (*i & 63);
194	0	if (w != 0) {
195	0	*i += roaring_trailing_zeroes(w);
196	0	return true;
197	0	}
198	0	x++;
199	0	while (x < bitset->arraysize) {
200	0	w = bitset->array[x];
201	0	if (w != 0) {
202	0	i = x 64 + roaring_trailing_zeroes(w);
203	0	return true;
204	0	}
205	0	x++;
206	0	}
207	0	return false;
208	0	}
209
210		/* iterate over the set bits
211		like so :
212		size_t buffer[256];
213		size_t howmany = 0;
214		for(size_t startfrom = 0; (howmany = bitset_next_set_bits(b,buffer,256, &startfrom)) >
215		0 ; startfrom++) {
216		//.....
217		}
218		*/
219		inline size_t bitset_next_set_bits(const bitset_t bitset, size_t buffer,
220	0	size_t capacity, size_t *startfrom) {
221	0	if (capacity == 0) return 0; // sanity check
222	0	size_t x = *startfrom / 64;
223	0	if (x >= bitset->arraysize) {
224	0	return 0; // nothing more to iterate over
225	0	}
226	0	uint64_t w = bitset->array[x];
227	0	w >>= (*startfrom & 63);
228	0	size_t howmany = 0;
229	0	size_t base = x << 6;
230	0	while (howmany < capacity) {
231	0	while (w != 0) {
232	0	uint64_t t = w & (~w + 1);
233	0	int r = roaring_trailing_zeroes(w);
234	0	buffer[howmany++] = r + base;
235	0	if (howmany == capacity) goto end;
236	0	w ^= t;
237	0	}
238	0	x += 1;
239	0	if (x == bitset->arraysize) {
240	0	break;
241	0	}
242	0	base += 64;
243	0	w = bitset->array[x];
244	0	}
245	0	end:
246	0	if (howmany > 0) {
247	0	*startfrom = buffer[howmany - 1];
248	0	}
249	0	return howmany;
250	0	}
251
252		typedef bool (bitset_iterator)(size_t value, void param);
253
254		// return true if uninterrupted
255		inline bool bitset_for_each(const bitset_t *b, bitset_iterator iterator,
256	0	void *ptr) {
257	0	size_t base = 0;
258	0	for (size_t i = 0; i < b->arraysize; ++i) {
259	0	uint64_t w = b->array[i];
260	0	while (w != 0) {
261	0	uint64_t t = w & (~w + 1);
262	0	int r = roaring_trailing_zeroes(w);
263	0	if (!iterator(r + base, ptr)) return false;
264	0	w ^= t;
265	0	}
266	0	base += 64;
267	0	}
268	0	return true;
269	0	}
270
271	0	inline void bitset_print(const bitset_t *b) {
272	0	printf("{");
273	0	for (size_t i = 0; bitset_next_set_bit(b, &i); i++) {
274	0	printf("%zu, ", i);
275	0	}
276	0	printf("}");
277	0	}
278
279		#ifdef __cplusplus
280		} } } // extern "C" { namespace roaring { namespace api {
281		#endif
282
283		#endif