bitvector.h File Reference

Packed BitVector C-API declarations. More...

#include "compat.h"
#include <stdbool.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 array of bits with support for rank/select operations. More...

Macros
#define	BV_ALIGN   64
	Alignment in bytes for all BitVector allocations.
#define	BV_WORDS_SUPER_SHIFT   3
	Number of bits to shift a word index to compute a superblock index.
#define	BV_WORDS_SUPER   (1u << BV_WORDS_SUPER_SHIFT)
	Number of 64-bit worde per superblock.

Functions
static size_t	bv_word (const size_t pos)
	Compute the word index for a given bit position.
static size_t	bv_bit (const size_t pos)
	Compute the bit offset within its 64-bit word.
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_build_rank (BitVector *bv)
	Build or rebuild the rank tables for a BitVector.
static int	bv_get (const BitVector *bv, const size_t pos)
	Get the bit value at a given position.
static void	bv_set (BitVector *bv, const size_t pos)
	Set the bit at a given position (set to 1)
static void	bv_clear (BitVector *bv, const size_t pos)
	Clear the bit at a given position (set to 0)
static void	bv_flip (BitVector *bv, const size_t pos)
	Toggle (flip) the bit at a given position.
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.

Detailed Description

Packed BitVector C-API declarations.

This header decleares the BitVector C-API:

• creation, copy, free
• bit get/set/clear/flip operations
• rank and subvector-containment queries

Author

lambdaphoenix

Version

0.1.1

Copyright

Copyright (c) 2025 lambdaphoenix

Macro Definition Documentation

BV_ALIGN

#define BV_ALIGN   64

Alignment in bytes for all BitVector allocations.

BV_WORDS_SUPER

#define BV_WORDS_SUPER   (1u << BV_WORDS_SUPER_SHIFT)

Number of 64-bit worde per superblock.

BV_WORDS_SUPER_SHIFT

#define BV_WORDS_SUPER_SHIFT   3

Number of bits to shift a word index to compute a superblock index.

Function Documentation

bv_bit()

static size_t bv_bit ( const size_t  pos )

inlinestatic

Compute the bit offset within its 64-bit word.

Parameters

pos

bit index

Returns

Offset in [0...63] inside the 64-bit word.

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()

static void bv_clear ( BitVector *  bv, const size_t  pos  )

inlinestatic

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_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

Returns

Newly allocated BitVector copy, or NULL on 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()

static void bv_flip ( BitVector *  bv, const size_t  pos  )

inlinestatic

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_free()

void bv_free

(

BitVector *

bv

)

Free all memory associated with a BitVector.

Parameters

bv	Pointer to the BitVector to free

bv_get()

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

inlinestatic

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

Returns

Pointer to the new BitVector

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_set()

static void bv_set ( BitVector *  bv, const size_t  pos  )

inlinestatic

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_word()

static size_t bv_word ( const size_t  pos )

inlinestatic

Compute the word index for a given bit position.

Parameters

pos

bit index

Returns

Index of the 64-bit word containing that bit.