bitvec.h File Reference

Detailed Description

Author

hacatu

Version

0.3.0 A vector of booleans/bits

This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

Definition in file bitvec.h.

Go to the source code of this file.

Data Structures
struct	cr8r_bvec
	A bit vector Take care if manipulating these fields directly, this should only be done if the functions in this file are not sufficient. More...
struct	cr8r_bvec_ft
	Function table for bit vector. More...

Functions
bool	cr8r_bvec_init (cr8r_bvec *, cr8r_bvec_ft *, uint64_t bits)
	Initialize a bit vector with an empty buffer of a given capacity. More...
void	cr8r_bvec_delete (cr8r_bvec *, cr8r_bvec_ft *)
	Free the buffer of a bit vector. More...
bool	cr8r_bvec_copy (cr8r_bvec *dest, const cr8r_bvec *src, cr8r_bvec_ft *)
	Create a copy of a bit vector. More...
bool	cr8r_bvec_sub (cr8r_bvec *dest, const cr8r_bvec *src, cr8r_bvec_ft *, uint64_t a, uint64_t b)
	Create a copy of a slice of a bit vector. More...
bool	cr8r_bvec_resize (cr8r_bvec *, cr8r_bvec_ft *, uint64_t bits)
	Resize a bit vector's reserved buffer. More...
bool	cr8r_bvec_trim (cr8r_bvec *, cr8r_bvec_ft *)
	Resize a bit vector's reserved buffer to its length. More...
void	cr8r_bvec_clear (cr8r_bvec *)
	Sets len to 0.
void	cr8r_bvec_shuffle (cr8r_bvec *, cr8r_prng *)
	Shuffle the bit vector into a random permutation. More...
bool	cr8r_bvec_get (cr8r_bvec *, uint64_t i)
	Get the bit at a given index WITH bounds checking. More...
bool	cr8r_bvec_getu (cr8r_bvec *, uint64_t i)
	Get the bit at a given index WITHOUT bounds checking. More...
bool	cr8r_bvec_getx (cr8r_bvec *, int64_t i)
	Get the element at a given index, with support for negative indices, WITH bounds checking. More...
bool	cr8r_bvec_getux (cr8r_bvec *, int64_t i)
	Get the element at a given index, with support for negative indices, WITHOUT bounds checking. More...
bool	cr8r_bvec_set (cr8r_bvec *, uint64_t i, bool b)
	Set the bit at a given index WITH bounds checking. More...
void	cr8r_bvec_setu (cr8r_bvec *, uint64_t i, bool b)
	Set the bit at a given index WITHOUT bounds checking. More...
bool	cr8r_bvec_setx (cr8r_bvec *, int64_t i, bool b)
	Set the element at a given index, with support for negative indices, WITH bounds checking. More...
void	cr8r_bvec_setux (cr8r_bvec *, int64_t i, bool b)
	Set the element at a given index, with support for negative indices, WITHOUT bounds checking. More...
uint64_t	cr8r_bvec_len (cr8r_bvec *)
	Get the length of a bit vector. More...
bool	cr8r_bvec_pushr (cr8r_bvec *, cr8r_bvec_ft *, bool b)
	Add a bit to the right hand end of a bit vector. More...
bool	cr8r_bvec_popr (cr8r_bvec *, int *status)
	Remove a bit from the right hand end of a bit vector. More...
bool	cr8r_bvec_pushl (cr8r_bvec *, cr8r_bvec_ft *, bool b)
	Add a bit to the left hand end of a bit vector. More...
bool	cr8r_bvec_popl (cr8r_bvec *, int *status)
	Remove a bit from the left hand end of a bit vector. More...
int	cr8r_bvec_forEachPermutation (cr8r_bvec *, void(*f)(const cr8r_bvec *, void *data), void *data)
	Execute a function on every permutation of a bit vector. More...
bool	cr8r_bvec_combine (cr8r_bvec *dest, const cr8r_bvec *src_a, const cr8r_bvec *src_b, cr8r_bvec_ft *)
	Create a new bit vector by concatenating copies of two given bit vectors. More...
bool	cr8r_bvec_augment (cr8r_bvec *self, const cr8r_bvec *other, cr8r_bvec_ft *)
	Add a copy of another bit vector to a given bit vector. More...
bool	cr8r_bvec_all (const cr8r_bvec *)
	Test if all bits are set.
bool	cr8r_bvec_any (const cr8r_bvec *)
	Test if any bits.
uint64_t	cr8r_bvec_popcount (const cr8r_bvec *)
	Count the number of bits set.
uint64_t	cr8r_bvec_clz (const cr8r_bvec *)
	Count leading zeros (starting from the largest index self->len - 1)
uint64_t	cr8r_bvec_ctz (const cr8r_bvec *)
	Count trailing zeros (starting from the smallest index 0)
uint64_t	cr8r_bvec_clo (const cr8r_bvec *)
	Count leading ones (starting from the largest index self->len - 1)
uint64_t	cr8r_bvec_cto (const cr8r_bvec *)
	Count trailing ones (starting from the smallest index 0)
void	cr8r_bvec_icompl (cr8r_bvec *)
	Bitwise negate (~) a bit vector in place.
void	cr8r_bvec_iand (cr8r_bvec *self, const cr8r_bvec *other)
	Bitwise and (&=) a bit vector with another in place If the other vector is shorter, missing bits are treated as zero.
void	cr8r_bvec_ior (cr8r_bvec *self, const cr8r_bvec *other)
	Bitwise or (|=) a bit vector with another in place If the other vector is shorter, missing bits are treated as zero.
void	cr8r_bvec_ixor (cr8r_bvec *self, const cr8r_bvec *other)
	Bitwise xor (^=) a bit vector with another in place If the other vector is shorter, missing bits are treated as zero.
bool	cr8r_bvec_any_range (const cr8r_bvec *, uint64_t a, uint64_t b)
	Test if any bit in the range [a, b) is set If the range is invalid, 0 is returned.
bool	cr8r_bvec_all_range (const cr8r_bvec *, uint64_t a, uint64_t b)
	Test if all bits in the range [a, b) are set If the range is invalid, 0 is returned.
bool	cr8r_bvec_set_range (cr8r_bvec *, uint64_t a, uint64_t b, bool v)
	Set all bits in a range WITH bounds checking. More...
int	cr8r_bvec_cmp (const cr8r_bvec *a, const cr8r_bvec *b)
	Lexicographically compare two bit vectors. More...

Variables
cr8r_bvec_ft	cr8r_bvecft
	Function table for bit vectors. More...

Function Documentation

cr8r_bvec_init()

bool cr8r_bvec_init	(	cr8r_bvec *	,
		cr8r_bvec_ft *	,
		uint64_t	bits
	)

Initialize a bit vector with an empty buffer of a given capacity.

Parameters

[in]

bits

how many bits to reserve space for initially (will be rounded up to a multiple of 64)

Returns

1 on success, 0 on failure (memory allocation failure)

cr8r_bvec_delete()

void cr8r_bvec_delete	(	cr8r_bvec *	,
		cr8r_bvec_ft *
	)

Free the buffer of a bit vector.

ft->resize is called to "resize" to 0. the fields of the vector are all zeroed out

cr8r_bvec_copy()

bool cr8r_bvec_copy	(	cr8r_bvec *	dest,
		const cr8r_bvec *	src,
		cr8r_bvec_ft *
	)

Create a copy of a bit vector.

dest should NOT be initialized or its buffer will be leaked! The copy's capacity is only its length.

Parameters

[out]	dest	the bit vector to copy TO
[in]	src	the bit vector to copy FROM

Returns

1 on success, 0 on failure (memory allocation failure)

cr8r_bvec_sub()

bool cr8r_bvec_sub	(	cr8r_bvec *	dest,
		const cr8r_bvec *	src,
		cr8r_bvec_ft *	,
		uint64_t	a,
		uint64_t	b
	)

Create a copy of a slice of a bit vector.

dest should NOT be initialized or its buffer will be leaked! Copies the range [ a : b ) from src to dest. The copy's capacity is only its length (b - a).

Parameters

[out]	dest	the bit vector to copy TO
[in]	src	the bit vector to copy FROM
[in]	a,b	inclusive start index and exclusive end index

Returns

1 on success, 0 on failure (memory allocation failure or invalid bounds)

cr8r_bvec_resize()

bool cr8r_bvec_resize	(	cr8r_bvec *	,
		cr8r_bvec_ft *	,
		uint64_t	bits
	)

Resize a bit vector's reserved buffer.

Can extend or shrink the buffer, but cannot make it smaller than its length.

Parameters

[in]

cap

the target capacity, should not be less than the current length

Returns

1 on success, 0 on failure (memory allocation or invalid bounds)

cr8r_bvec_trim()

bool cr8r_bvec_trim	(	cr8r_bvec *	,
		cr8r_bvec_ft *
	)

Resize a bit vector's reserved buffer to its length.

Exactly like cr8r_bvec_resize with self->len as the cap parameter

Returns

1 on success, 0 on failure (memory allocation, shouldn't happen unless ft->resize can fail to shrink)

cr8r_bvec_shuffle()

void cr8r_bvec_shuffle	(	cr8r_bvec *	,
		cr8r_prng *
	)

Shuffle the bit vector into a random permutation.

Actually works by counting the number of bits set and redistributing them.

cr8r_bvec_get()

bool cr8r_bvec_get	(	cr8r_bvec *	,
		uint64_t	i
	)

Get the bit at a given index WITH bounds checking.

Parameters

[in]

i

the index to get, should be from 0 inclusive to self->len exclusive

Returns

the bit at index i, or 0 if i is out of bounds

cr8r_bvec_getu()

bool cr8r_bvec_getu	(	cr8r_bvec *	,
		uint64_t	i
	)

Get the bit at a given index WITHOUT bounds checking.

Parameters

[in]

i

the index to get, should be from 0 inclusive to self->len exclusive

Returns

the bit at index i, or 0 if i is out of bounds

cr8r_bvec_getx()

bool cr8r_bvec_getx	(	cr8r_bvec *	,
		int64_t	i
	)

Get the element at a given index, with support for negative indices, WITH bounds checking.

Negative indicies work backwards, with -1 referring to the last element and so on.

Parameters

[in]

i

the index to get, should be from 0 inclusive to self->len exclusive

Returns

the bit at index i, or 0 if i is out of bounds

cr8r_bvec_getux()

bool cr8r_bvec_getux	(	cr8r_bvec *	,
		int64_t	i
	)

Get the element at a given index, with support for negative indices, WITHOUT bounds checking.

Negative indicies work backwards, with -1 referring to the last element and so on.

Parameters

[in]

i

the index to get, should be from 0 inclusive to self->len exclusive

Returns

the bit at index i, or 0 if i is out of bounds

cr8r_bvec_set()

bool cr8r_bvec_set	(	cr8r_bvec *	,
		uint64_t	i,
		bool	b
	)

Set the bit at a given index WITH bounds checking.

Parameters

[in]

i

the index to get, should be from 0 inclusive to self->len exclusive

Returns

1 on success, or 0 if i is out of bounds

cr8r_bvec_setu()

void cr8r_bvec_setu	(	cr8r_bvec *	,
		uint64_t	i,
		bool	b
	)

Set the bit at a given index WITHOUT bounds checking.

Parameters

[in]

i

the index to get, should be from 0 inclusive to self->len exclusive

cr8r_bvec_setx()

bool cr8r_bvec_setx	(	cr8r_bvec *	,
		int64_t	i,
		bool	b
	)

Set the element at a given index, with support for negative indices, WITH bounds checking.

Negative indicies work backwards, with -1 referring to the last element and so on.

Parameters

[in]

i

the index to get, should be from 0 inclusive to self->len exclusive

Returns

the bit at index i, or 0 if i is out of bounds

cr8r_bvec_setux()

void cr8r_bvec_setux	(	cr8r_bvec *	,
		int64_t	i,
		bool	b
	)

Set the element at a given index, with support for negative indices, WITHOUT bounds checking.

Negative indicies work backwards, with -1 referring to the last element and so on.

Parameters

[in]

i

the index to get, should be from 0 inclusive to self->len exclusive

cr8r_bvec_len()

uint64_t cr8r_bvec_len

(

cr8r_bvec *

)

Get the length of a bit vector.

Simply returns self->len

Returns

the length of the vector

cr8r_bvec_pushr()

bool cr8r_bvec_pushr	(	cr8r_bvec *	,
		cr8r_bvec_ft *	,
		bool	b
	)

Add a bit to the right hand end of a bit vector.

This is an O(1) operation

Parameters

[in]

b

the bit to add

Returns

1 on success, 0 on failure (allocation failure)

cr8r_bvec_popr()

bool cr8r_bvec_popr	(	cr8r_bvec *	,
		int *	status
	)

Remove a bit from the right hand end of a bit vector.

Vectors are arranged with increasing indicies at increasing memory addresses, so this is an O(1) operation

Parameters

[out]

status

if not NULL, *status will be set to 1 on success or 0 on failure (if the bit vector was empty)

Returns

the bit that was removed

cr8r_bvec_pushl()

bool cr8r_bvec_pushl	(	cr8r_bvec *	,
		cr8r_bvec_ft *	,
		bool	b
	)

Add a bit to the left hand end of a bit vector.

Avoid if possible.

Don't do this. This is an O(n) operation because bit vectors are arranged with increasing indicies at increasing memory addresses.

Parameters

[in]

b

the bit to add

Returns

1 on success, 0 on failure

cr8r_bvec_popl()

bool cr8r_bvec_popl	(	cr8r_bvec *	,
		int *	status
	)

Remove a bit from the left hand end of a bit vector.

Avoid if possible.

Don't do this. This is an O(n) operation because bit vectors are arranged with increasing indicies at increasing memory addresses.

Parameters

[out]

status

if not NULL, *status will be set to 1 on success or 0 on failure (if the bit vector was empty)

Returns

the bit that was removed

cr8r_bvec_forEachPermutation()

int cr8r_bvec_forEachPermutation	(	cr8r_bvec *	,
		void(*)(const cr8r_bvec *, void *data)	f,
		void *	data
	)

Execute a function on every permutation of a bit vector.

The bit vector is actually permuted in place using Heap's algorithm, and ends at the "last" permutation without being restored.

Parameters

[in]	f	callback function
[in,out]	data	reentrant data to pass to the callback, can provide input, output, and persistant state without needing to hijack ft->base.data or similar

Returns

1 on success, 0 on failure (if an array of self->len uint64_t's cannot be allocated)

cr8r_bvec_combine()

bool cr8r_bvec_combine	(	cr8r_bvec *	dest,
		const cr8r_bvec *	src_a,
		const cr8r_bvec *	src_b,
		cr8r_bvec_ft *
	)

Create a new bit vector by concatenating copies of two given bit vectors.

dest should NOT be initialized or its buffer will be leaked! First, ensures the dest buffer has enough capacity for both src bit vectors, extending if necessary, then copy the bit vectors one after the other.

Parameters

[out]	dest	bit vector in which to store result
[in]	src_a,src_b	bit vectors to copy elements from

Returns

1 on success, 0 on failure (allocation failure)

cr8r_bvec_augment()

bool cr8r_bvec_augment	(	cr8r_bvec *	self,
		const cr8r_bvec *	other,
		cr8r_bvec_ft *
	)

Add a copy of another bit vector to a given bit vector.

First, extends self->buf if needed, then copy the other bit vector right after the current end.

Parameters

[in,out]	self	bit vector to extend with a copy of the other bit vector
[in]	other	bit vector to copy from

Returns

1 on success, 0 on failure (allocation failure)

cr8r_bvec_set_range()

bool cr8r_bvec_set_range	(	cr8r_bvec *	,
		uint64_t	a,
		uint64_t	b,
		bool	v
	)

Set all bits in a range WITH bounds checking.

The bounds are [a, b)

Returns

1 on success, 0 on failure (out of bounds)

cr8r_bvec_cmp()

int cr8r_bvec_cmp	(	const cr8r_bvec *	a,
		const cr8r_bvec *	b
	)

Lexicographically compare two bit vectors.

Parameters

[in]

a,b

vectors to compare

Returns

-1 if a is lexicographically before b, +1 visa versa, or 0 if they are equal

Variable Documentation

cr8r_bvecft

cr8r_bvec_ft cr8r_bvecft

extern

Function table for bit vectors.

The default allocation scheme cr8r_default_new_size and cr8r_default_resize is used.