bitvector.h File Reference

Public C API for the BitVector data structure. More...

#include <stdbool.h>
#include "compat.h"

Include dependency graph for bitvector.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	BitVector
	Packed bit array with rank-support structures. More...

Macros
#define	BV_ALIGN   64
	Alignment (in bytes) for all BitVector allocations.
#define	BV_WORDS_SUPER_SHIFT   3
	Log2 of the number of 64‑bit words per superblock.
#define	BV_WORDS_SUPER   (1u << BV_WORDS_SUPER_SHIFT)
	Number of 64-bit worde in a superblock.

Functions
BitVector *	bv_new (size_t n_bits)
	Allocate a new BitVector with all bits cleared.
BitVector *	bv_copy (const BitVector *src)
	Make a copy of an existing BitVector.
void	bv_free (BitVector *bv)
	Free all memory associated with a BitVector.
void	bv_set_range (BitVector *bv, size_t start, size_t len)
	Set all bits in the half-open range [start, start+len).
void	bv_clear_range (BitVector *bv, size_t start, size_t len)
	Clear all bits in the half-open range [start, start+len).
void	bv_flip_range (BitVector *bv, size_t start, size_t len)
	Toggle (flip) all bits in the half-open range [start, start+len).
void	bv_build_rank (BitVector *bv)
	Build or rebuild the rank tables for a BitVector.
size_t	bv_rank (BitVector *bv, const size_t pos)
	Compute the rank (number of set bits) up to a position.
bool	bv_equal (const BitVector *a, const BitVector *b)
	Test equality of two BitVectors.
bool	bv_contains_subvector (const BitVector *a, const BitVector *b)
	Check weather B appears as a contiguous sub-bitvector of A.
int	bv_get (const BitVector *bv, const size_t pos)
	Get the bit value at a given position.
void	bv_set (BitVector *bv, const size_t pos)
	Set the bit at a given position (set to 1)
void	bv_clear (BitVector *bv, const size_t pos)
	Clear the bit at a given position (set to 0)
void	bv_flip (BitVector *bv, const size_t pos)
	Toggle (flip) the bit at a given position.
BitVector *	bv_concat (const BitVector *a, const BitVector *b)
	Concatenate two BitVectors into a new BitVector.
BitVector *	bv_repeat (const BitVector *bv, const size_t count)
	Repeat a BitVector n times.

Detailed Description

Public C API for the BitVector data structure.

Declares the stable, external-facing API for working with BitVectors:

• construction and destruction (bv_new, bv_copy, bv_free)
• single-bit operations (bv_get, bv_set, bv_clear, bv_flip)
• range operations (bv_set_range, bv_clear_range, bv_flip_range)
• rank queries (bv_build_rank, bv_rank)
• comparison and subvector search (bv_equal, bv_contains_subvector)

The public API is intentionally minimal. Internal helpers, inline fast‑paths, and low‑level utilities are defined separately in bitvector_internal.h.

BitVector provides a compact, cache‑friendly bit array with optional auxiliary rank tables enabling O(1) prefix‑popcount queries.

Author

lambdaphoenix

Version

0.3.0

Copyright

Copyright (c) 2026 lambdaphoenix

Macro Definition Documentation

BV_ALIGN

#define BV_ALIGN   64

Alignment (in bytes) for all BitVector allocations.

Ensures that the underlying word array is aligned for efficient SIMD and cache‑line access.

BV_WORDS_SUPER_SHIFT

#define BV_WORDS_SUPER_SHIFT   3

Log2 of the number of 64‑bit words per superblock.

Used to compute superblock indices via bit‑shifts rather than division.

Function Documentation

bv_build_rank()

void bv_build_rank

(

BitVector *

bv

)

Build or rebuild the rank tables for a BitVector.

This populates super_rank[] and block_rank[] to support O(1) rank queries. After this call, bv->rank_dirty is cleared.

Parameters

bv	Pointer to the BitVector whose tables to build

bv_clear()

void bv_clear	(	BitVector *	bv,
		const size_t	pos
	)

Clear the bit at a given position (set to 0)

Marks the rank table dirty so it will be rebuilt on next rank query.

Parameters

bv	Pointer to the BitVector
pos	Bit index

bv_clear_range()

void bv_clear_range	(	BitVector *	bv,
		size_t	start,
		size_t	len
	)

Clear all bits in the half-open range [start, start+len).

Marks the rank table dirty so it will be rebuilt on next rank query.

Parameters

bv	Pointer to the BitVector
start	Start bit index
len	Number of bits to clear

Since

0.2.0

bv_concat()

BitVector * bv_concat	(	const BitVector *	a,
		const BitVector *	b
	)

Concatenate two BitVectors into a new BitVector.

Produces a new BitVector whose bits are A followed by B. Returns NULL on allocation failure.

Parameters

a	Left operand.
b	Right operand.

Return values

object	New BitVector on success.
NULL	on failure.

Since

0.3.0

bv_contains_subvector()

bool bv_contains_subvector	(	const BitVector *	a,
		const BitVector *	b
	)

Check weather B appears as a contiguous sub-bitvector of A.

That is, whether there exists an offset i in A such that A[i..i+|B|-1] == B[0..|B|-1] .

Parameters

a	Haystack BitVector
b	Needle BitVector

Returns

true if b is contained in a, false otherwise

bv_copy()

BitVector * bv_copy

(

const BitVector *

src

)

Make a copy of an existing BitVector.

The copy shares no memory with the source; all bits and rank tables are reinitialized.

Parameters

src	Pointer to the source BitVector

Return values

BitVector*	Newly allocated BitVector copy.
NULL	Failure.

bv_equal()

bool bv_equal	(	const BitVector *	a,
		const BitVector *	b
	)

Test equality of two BitVectors.

Only vectors with the same length can compare equal.

Parameters

a	First BitVector
b	Second BitVector

Returns

true if length and all words are identical, false otherwise

bv_flip()

void bv_flip	(	BitVector *	bv,
		const size_t	pos
	)

Toggle (flip) the bit at a given position.

Marks the rank table dirty so it will be rebuilt on next rank query.

Parameters

bv	Pointer to the BitVector
pos	Bit index

bv_flip_range()

void bv_flip_range	(	BitVector *	bv,
		size_t	start,
		size_t	len
	)

Toggle (flip) all bits in the half-open range [start, start+len).

Marks the rank table dirty so it will be rebuilt on next rank query.

Parameters

bv	Pointer to the BitVector
start	Start bit index
len	Number of bits to flip

Since

0.2.0

bv_free()

void bv_free

(

BitVector *

bv

)

Free all memory associated with a BitVector.

Parameters

bv	Pointer to the BitVector to free

bv_get()

int bv_get	(	const BitVector *	bv,
		const size_t	pos
	)

Get the bit value at a given position.

Parameters

bv	Pointer to the BitVector
pos	Bit index

Returns

0 or 1 depending on the bit value

bv_new()

BitVector * bv_new

(

size_t

n_bits

)

Allocate a new BitVector with all bits cleared.

Parameters

n_bits

Number of bits to allocate.

Return values

BitVector*	Newly allocated BitVector.
NULL	Allocation failure.

bv_rank()

size_t bv_rank	(	BitVector *	bv,
		const size_t	pos
	)

Compute the rank (number of set bits) up to a position.

If the internal rank tables are dirty, they will be rebuilt.

Parameters

bv	Pointer to the BitVector
pos	Bit index

Returns

Number of bits set in range [0...pos)

bv_repeat()

BitVector * bv_repeat	(	const BitVector *	bv,
		const size_t	count
	)

Repeat a BitVector n times.

Produces a new BitVector whose bit pattern is the original repeated count times. Returns NULL on allocation failure.

Parameters

bv	BitVector instance.
count	Repeat count.

Return values

object	New BitVector on success.
NULL	on error (exception set).

Since

0.3.0

bv_set()

void bv_set	(	BitVector *	bv,
		const size_t	pos
	)

Set the bit at a given position (set to 1)

Marks the rank table dirty so it will be rebuilt on next rank query.

Parameters

bv	Pointer to the BitVector
pos	Bit index

bv_set_range()

void bv_set_range	(	BitVector *	bv,
		size_t	start,
		size_t	len
	)

Set all bits in the half-open range [start, start+len).

Marks the rank table dirty so it will be rebuilt on next rank query.

Parameters

bv	Pointer to the BitVector
start	Start bit index
len	Number of bits to set

Since

0.2.0