cbits 0.1.1
High-performance BitVector C-API & Python binding
Loading...
Searching...
No Matches
bitvector.h
Go to the documentation of this file.
1
13#ifndef CBITS_BITVECTOR_H
14#define CBITS_BITVECTOR_H
15
16#include "compat.h"
17#include <stdbool.h>
18
23#define BV_ALIGN 64
29#define BV_WORDS_SUPER_SHIFT 3
34#define BV_WORDS_SUPER (1u << BV_WORDS_SUPER_SHIFT)
35
41static inline size_t
42bv_word(const size_t pos)
43{
44 return pos >> 6;
45}
51static inline size_t
52bv_bit(const size_t pos)
53{
54 return pos & 63;
55}
56
64typedef struct {
65 uint64_t *data;
66 size_t n_bits;
67 size_t n_words;
68 size_t
70 uint16_t *block_rank;
72} BitVector;
73
80bv_new(size_t n_bits);
90bv_copy(const BitVector *src);
95void
104void
112static inline int
113bv_get(const BitVector *bv, const size_t pos)
114{
115 return (bv->data[bv_word(pos)] >> bv_bit(pos)) & 1;
116}
124static inline void
125bv_set(BitVector *bv, const size_t pos)
126{
127 uint64_t mask = 1ULL << bv_bit(pos);
128 bv->data[bv_word(pos)] |= mask;
129 bv->rank_dirty = true;
130}
138static inline void
139bv_clear(BitVector *bv, const size_t pos)
140{
141 uint64_t mask = ~(1ULL << bv_bit(pos));
142 bv->data[bv_word(pos)] &= mask;
143 bv->rank_dirty = true;
144}
152static inline void
153bv_flip(BitVector *bv, const size_t pos)
154{
155 uint64_t mask = 1ULL << bv_bit(pos);
156 bv->data[bv_word(pos)] ^= mask;
157 bv->rank_dirty = true;
158}
167size_t
168bv_rank(BitVector *bv, const size_t pos);
177bool
178bv_equal(const BitVector *a, const BitVector *b);
188bool
189bv_contains_subvector(const BitVector *a, const BitVector *b);
190
191#endif /* CBITS_BITVECTOR_H */
void bv_free(BitVector *bv)
Free all memory associated with a BitVector.
Definition bitvector.c:84
static void bv_flip(BitVector *bv, const size_t pos)
Toggle (flip) the bit at a given position.
Definition bitvector.h:153
bool bv_contains_subvector(const BitVector *a, const BitVector *b)
Check weather B appears as a contiguous sub-bitvector of A.
Definition bitvector.c:155
void bv_build_rank(BitVector *bv)
Build or rebuild the rank tables for a BitVector.
Definition bitvector.c:93
BitVector * bv_new(size_t n_bits)
Allocate a new BitVector with all bits cleared.
Definition bitvector.c:35
static void bv_set(BitVector *bv, const size_t pos)
Set the bit at a given position (set to 1)
Definition bitvector.h:125
static void bv_clear(BitVector *bv, const size_t pos)
Clear the bit at a given position (set to 0)
Definition bitvector.h:139
static size_t bv_word(const size_t pos)
Compute the word index for a given bit position.
Definition bitvector.h:42
BitVector * bv_copy(const BitVector *src)
Make a copy of an existing BitVector.
Definition bitvector.c:72
static size_t bv_bit(const size_t pos)
Compute the bit offset within its 64-bit word.
Definition bitvector.h:52
bool bv_equal(const BitVector *a, const BitVector *b)
Test equality of two BitVectors.
Definition bitvector.c:140
static int bv_get(const BitVector *bv, const size_t pos)
Get the bit value at a given position.
Definition bitvector.h:113
size_t bv_rank(BitVector *bv, const size_t pos)
Compute the rank (number of set bits) up to a position.
Definition bitvector.c:125
Cross-platform aligned allocators, popcount, prefetch.
Packed array of bits with support for rank/select operations.
Definition bitvector.h:64
uint64_t * data
Definition bitvector.h:65
size_t n_bits
Definition bitvector.h:66
uint16_t * block_rank
Definition bitvector.h:70
size_t * super_rank
Definition bitvector.h:69
size_t n_words
Definition bitvector.h:67
bool rank_dirty
Definition bitvector.h:71