bitset.h File Reference

The Bit Set Interface. More...

#include "impl/impl_bitset.h"
#include "types.h"

Include dependency graph for bitset.h:

Go to the source code of this file.

Container Initialization
Initialize and create containers with memory and permissions.
#define	ccc_bs_blocks(bit_cap)   ccc_impl_bs_blocks(bit_cap)
	Get the number of bit blocks needed for the desired bit set capacity.
#define	ccc_bs_init(bitblock_ptr, alloc_fn, aux, cap, optional_size...)    ccc_impl_bs_init(bitblock_ptr, alloc_fn, aux, cap, optional_size)
	Initialize the bit set with memory and allocation permissions.
ccc_result	ccc_bs_copy (ccc_bitset *dst, ccc_bitset const *src, ccc_alloc_fn *fn)
	Copy the bit set at source to destination.

Container Types
Types available in the container interface.
typedef struct ccc_bitset_	ccc_bitset
	The bit set type that may be stored and initialized on the stack, heap, or data segment at compile time or runtime.
typedef ccc_bitblock_	ccc_bitblock
	The type used to efficiently store bits in the bit set.

Bit Membership Interface
Test for the presence of bits.
ccc_tribool	ccc_bs_test (ccc_bitset const *bs, size_t i)
	Test the bit at index i for boolean status (CCC_TRUE or CCC_FALSE).

Bit Modification Interface
Set and flip bits in the set.
ccc_tribool	ccc_bs_set (ccc_bitset *bs, size_t i, ccc_tribool b)
	Set the bit at valid index i to value b (true or false).
ccc_result	ccc_bs_set_all (ccc_bitset *bs, ccc_tribool b)
	Set all the bits to the provided value (CCC_TRUE or CCC_FALSE).
ccc_result	ccc_bs_set_range (ccc_bitset *bs, size_t i, size_t count, ccc_tribool b)
	Set all the bits in the specified range starting at the Least Significant Bit of the range and ending at the Most Significant Bit of the range (CCC_TRUE or CCC_FALSE).
ccc_tribool	ccc_bs_reset (ccc_bitset *bs, size_t i)
	Set the bit at valid index i to boolean value b (true or false).
ccc_result	ccc_bs_reset_all (ccc_bitset *bs)
	Set all the bits to CCC_FALSE.
ccc_result	ccc_bs_reset_range (ccc_bitset *bs, size_t i, size_t count)
	Set all the bits in the specified range starting at the Least Significant Bit of the range and ending at the Most Significant Bit of the range to CCC_FALSE.
ccc_tribool	ccc_bs_flip (ccc_bitset *bs, size_t i)
	Toggle the bit at index i.
ccc_result	ccc_bs_flip_all (ccc_bitset *bs)
	Toggle all of the bits to their opposing boolean value.
ccc_result	ccc_bs_flip_range (ccc_bitset *bs, size_t i, size_t count)
	Flip all the bits in the range, starting at the Least Significant Bit in range and ending at the Most Significant Bit, to their opposite value.

Bit Scan Interface
Find bits with a specific status.
ccc_tribool	ccc_bs_any (ccc_bitset const *bs)
	Return true if any bits in set are 1.
ccc_tribool	ccc_bs_any_range (ccc_bitset const *bs, size_t i, size_t count)
	Return true if any bits are 1 in the specified range.
ccc_tribool	ccc_bs_none (ccc_bitset const *bs)
	Return true if all bits are set to 0.
ccc_tribool	ccc_bs_none_range (ccc_bitset const *bs, size_t i, size_t count)
	Return true if all bits are 0 in the specified range.
ccc_tribool	ccc_bs_all (ccc_bitset const *bs)
	Return true if all bits in set are 1.
ccc_tribool	ccc_bs_all_range (ccc_bitset const *bs, size_t i, size_t count)
	Return true if all bits are set to 1 in the specified range.
ccc_ucount	ccc_bs_first_trailing_one (ccc_bitset const *bs)
	Return the index of the first trailing bit set to 1 in the set.
ccc_ucount	ccc_bs_first_trailing_one_range (ccc_bitset const *bs, size_t i, size_t count)
	Return the index of the first trailing bit set to 1 in the range, starting from the Least Significant Bit at index 0.
ccc_ucount	ccc_bs_first_trailing_ones (ccc_bitset const *bs, size_t num_ones)
	Returns the index of the start of the first trailing num_ones contiguous 1 bits.
ccc_ucount	ccc_bs_first_trailing_ones_range (ccc_bitset const *bs, size_t i, size_t count, size_t num_ones)
	Returns the index of the start of the first trailing num_ones contiguous 1 bits in the specified range.
ccc_ucount	ccc_bs_first_trailing_zero (ccc_bitset const *bs)
	Return the index of the first bit set to 0 in the set.
ccc_ucount	ccc_bs_first_trailing_zero_range (ccc_bitset const *bs, size_t i, size_t count)
	Return the index of the first bit set to 0 in the range.
ccc_ucount	ccc_bs_first_trailing_zeros (ccc_bitset const *bs, size_t num_zeros)
	Returns the index of the start of the first trailing num_zeros contiguous 0 bits.
ccc_ucount	ccc_bs_first_trailing_zeros_range (ccc_bitset const *bs, size_t i, size_t count, size_t num_zeros)
	Returns the index of the start of the first trailing num_zeros contiguous 0 bits in the specified range.
ccc_ucount	ccc_bs_first_leading_one (ccc_bitset const *bs)
	Return the index of the first leading bit set to 1 in the set, starting from the Most Significant Bit at index size - 1.
ccc_ucount	ccc_bs_first_leading_one_range (ccc_bitset const *bs, size_t i, size_t count)
	Return the index of the first leading bit set to 1 in the set, starting from the Most Significant Bit at index size - 1.
ccc_ucount	ccc_bs_first_leading_ones (ccc_bitset const *bs, size_t num_ones)
	Returns the index of the start of the first leading num_ones contiguous 1 bits.
ccc_ucount	ccc_bs_first_leading_ones_range (ccc_bitset const *bs, size_t i, size_t count, size_t num_ones)
	Returns the index of the start of the first leading num_ones contiguous 1 bits in the specified range.
ccc_ucount	ccc_bs_first_leading_zero (ccc_bitset const *bs)
	Return the index of the first leading bit set to 0 in the set, starting from the Most Significant Bit at index size - 1.
ccc_ucount	ccc_bs_first_leading_zero_range (ccc_bitset const *bs, size_t i, size_t count)
	Return the index of the first leading bit set to 0 in the set, starting from the Most Significant Bit at index size - 1.
ccc_ucount	ccc_bs_first_leading_zeros (ccc_bitset const *bs, size_t num_zeros)
	Returns the index of the start of the first leading num_zeros contiguous 0 bits.
ccc_ucount	ccc_bs_first_leading_zeros_range (ccc_bitset const *bs, size_t i, size_t count, size_t num_zeros)
	Returns the index of the start of the first leading num_zeros contiguous 0 bits in the specified range.

Bit Operations Interface
Use standard integer width bit operations on the entire set.
ccc_result	ccc_bs_or (ccc_bitset *dst, ccc_bitset const *src)
	Bitwise OR dst set with src set.
ccc_result	ccc_bs_and (ccc_bitset *dst, ccc_bitset const *src)
	Bitwise AND dst set with src set.
ccc_result	ccc_bs_xor (ccc_bitset *dst, ccc_bitset const *src)
	Bitwise XOR dst set with src set.
ccc_result	ccc_bs_shiftl (ccc_bitset *bs, size_t left_shifts)
	Shift the bit set left by left_shifts amount.
ccc_result	ccc_bs_shiftr (ccc_bitset *bs, size_t right_shifts)
	Shift the bit set right by right_shifts amount.
ccc_tribool	ccc_bs_eq (ccc_bitset const *a, ccc_bitset const *b)
	Checks two bit sets of the same size (not capacity) for equality.

Set Operations Interface
Perform basic mathematical set operations on the bit set.
ccc_tribool	ccc_bs_is_proper_subset (ccc_bitset const *set, ccc_bitset const *subset)
	Return CCC_TRUE if subset is a proper subset of set (subset ⊂ set).
ccc_tribool	ccc_bs_is_subset (ccc_bitset const *set, ccc_bitset const *subset)
	Return CCC_TRUE if subset is a subset of set (subset ⊆ set).

State Interface
Obtain state from the container.
ccc_bitblock *	ccc_bs_data (ccc_bitset const *bs)
	Return a reference to the base of the underlying block array.
ccc_ucount	ccc_bs_capacity (ccc_bitset const *bs)
	Return total number of bits the capacity of the set can hold.
ccc_ucount	ccc_bs_size (ccc_bitset const *bs)
	Return total number of bits actively tracked by the user and set.
ccc_ucount	ccc_bs_blocks_capacity (ccc_bitset const *bs)
	Return number of ccc_bitblocks used by bit set for capacity bits.
ccc_ucount	ccc_bs_blocks_size (ccc_bitset const *bs)
	Return number of ccc_bitblocks used by the bit set for size bits.
ccc_tribool	ccc_bs_empty (ccc_bitset const *bs)
	Return true if no bits are actively tracked by the user and set.
ccc_ucount	ccc_bs_popcount (ccc_bitset const *bs)
	Return the number of bits set to CCC_TRUE. O(n).
ccc_ucount	ccc_bs_popcount_range (ccc_bitset const *bs, size_t i, size_t count)
	Return the number of bits set to CCC_TRUE in the range. O(n).

Destructor Interface
Clear the set and manage its memory.
ccc_result	ccc_bs_clear (ccc_bitset *bs)
	Clears the bit set by setting the size to 0 and all bits to 0. The underlying memory capacity remains unchanged.
ccc_result	ccc_bs_clear_and_free (ccc_bitset *bs)
	Clears the bit set by setting the size to 0 and freeing the underlying memory. Capacity becomes 0 as well.

Dynamic Interface
Allows adding to and removing from the set.
ccc_result	ccc_bs_push_back (ccc_bitset *bs, ccc_tribool b)
	Append a bit value to the set as the new Most Significant Bit.
ccc_tribool	ccc_bs_pop_back (ccc_bitset *bs)
	Remove the Most Significant Bit from the set.

Detailed Description

The Bit Set Interface.

A bit set offers efficient set membership operations when the range of values can be tracked via an index. Both a fixed size and dynamic variant are possible depending on initialization options.

Conceptually, the bit set can be thought of as an arbitrary length integer with index 0 being the Least Significant Bit and index N - 1 being the Most Significant Bit of the integer. Internally, this is implemented by populating each block of the bit set from Least Significant Bit to Most Significant Bit. Therefore, "trailing" means starting from the Least Significant Bit and "leading" means starting from the Most Significant Bit; this is done to stay consistent with upcoming bit operations introduced to the C23 standard.

A bit set can be used for modeling integer operations on integers that exceed the widths available on one's platform. The provided bitwise operation functions are helpful for these types of manipulations.

A bit set can also be used for modeling data that can be abstracted to a position and binary value. For example, disk blocks in a file system, free blocks in a memory allocator, and many other resource abstractions can benefit from a bit set. For these use cases the bit set offers efficient functions to find the first bits set to zero or one from either the trailing or leading direction. A bit set can also efficiently report if contiguous ranges of zeros or ones are available.

To shorten names in the interface, define the following preprocessor directive at the top of your file.

#define BITSET_USING_NAMESPACE_CCC

All types and functions can then be written without the ccc_ prefix.

Macro Definition Documentation

ccc_bs_blocks

#define ccc_bs_blocks

(

bit_cap

)

ccc_impl_bs_blocks(bit_cap)

Get the number of bit blocks needed for the desired bit set capacity.

Parameters

[in]

bit_cap

the number of bits representing this bit set.

Returns

the number of blocks needed for the desired bit set.

Warning

bit_cap must be >= 1.

Note

this macro is not needed if capacity is 0 to start.

This method can be used for compile time initialization of bit sets so the user need to worry about the underlying bit set representation. For example:

static ccc_bitset b
    = ccc_bs_init((static ccc_bitblock[ccc_bs_blocks(256)]){}, NULL, NULL, 256);

The above example also illustrates the benefits of a static compound literal to encapsulate the bits within the bit set array to prevent dangling references. If your compiler has not implemented storage duration of compound literals the more traditional example would look like this.

static ccc_bitblock blocks[ccc_bs_blocks(256)];
static ccc_bitset b = ccc_bs_init(blocks, NULL, NULL, 256);

This macro is required for any initialization where the bit block memory comes from the stack or data segment as determined by the user.

ccc_bs_init

#define ccc_bs_init	(		bitblock_ptr,
			alloc_fn,
			aux,
			cap,
			optional_size...
	)		ccc_impl_bs_init(bitblock_ptr, alloc_fn, aux, cap, optional_size)

Initialize the bit set with memory and allocation permissions.

Parameters

[in]	bitblock_ptr	the pointer to existing blocks or NULL.
[in]	alloc_fn	the allocation function for a dynamic bit set or NULL.
[in]	aux	auxiliary data needed for allocation of the bit set.
[in]	cap	the number of bits that will be stored in this bit set.
[in]	optional_size	an optional starting size <= capacity. If the bitset is of fixed size with no allocation permission, and dynamic push and pop are not needed, the optional size parameter should be set equivalent to capacity.

Returns

the initialized bit set on the right hand side of an equality operator

Warning

the user must use the ccc_bs_blocks macro to help determine the size of the bitblock array if a fixed size bitblock array is provided at compile time; the necessary conversion from bits requested to number of blocks required to store those bits must occur before use. If capacity is zero the helper macro is not needed.

#define BITSET_USING_NAMESPACE_CCC
bitset bs = bs_init((bitblock[bs_blocks(9)]){}, 9, NULL, NULL, 9);

Or, initialize with zero capacity for a dynamic bit set.

#define BITSET_USING_NAMESPACE_CCC
bitset bs = bs_init(NULL, std_alloc, NULL, 0);

See types.h for more on allocation functions.

Typedef Documentation

ccc_bitblock

typedef ccc_bitblock_ ccc_bitblock

The type used to efficiently store bits in the bit set.

A block is a pre-determined integer width that allows for efficient block sized bit operations for various scanning and setting tasks. The user must participate in the storage of the bit set by using the provided ccc_bs_blocks macro to determine how many blocks are needed for the desired bits in the bit set.

ccc_bitset

typedef struct ccc_bitset_ ccc_bitset

The bit set type that may be stored and initialized on the stack, heap, or data segment at compile time or runtime.

A bit set offers fast membership testing and bit range manipulations when the data can be modeled as a 0-indexed key value data set. In the case of a bit set the key is the index in the bit set and the value is 1 or 0 depending on how the bit has been set. Operations on single bits occur in O(1) time. All scanning operations operate in O(N) time.

Function Documentation

ccc_bs_all()

ccc_tribool ccc_bs_all

(

ccc_bitset const *

bs

)

Return true if all bits in set are 1.

Parameters

[in]

bs

a pointer to the bit set.

Returns

CCC_TRUE if all bits are 1, CCC_FALSE if any bits are 0, CCC_TRIBOOL_ERROR if bs is NULL.

ccc_bs_all_range()

ccc_tribool ccc_bs_all_range	(	ccc_bitset const *	bs,
		size_t	i,
		size_t	count
	)

Return true if all bits are set to 1 in the specified range.

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the starting position.
[in]	count	the size of the range to check.

Returns

CCC_TRUE if all bits are 1, CCC_FALSE if any bits are 0, CCC_TRIBOOL_ERROR if bs is NULL, i is invalid, count is invalid, or both i and count are invalid.

ccc_bs_and()

ccc_result ccc_bs_and	(	ccc_bitset *	dst,
		ccc_bitset const *	src
	)

Bitwise AND dst set with src set.

Parameters

[in]	dst	the set to modified with the AND operation.
[in]	src	the set to be read as the source bits for the AND operation.

Returns

an OK result if the operation is successful or an input error if dst or src are NULL.

Warning

sets behave identically to integers for the AND operation when widening occurs. If dst is larger than src, src is padded with zeros in its Most Significant Bits. This means a bitwise AND operations will occur with the higher order bits in dst and 0's in this padded range (this results in all bits in dst being set to 0 in that range).

Note that sets are aligned from their Least Significant Bit and a smaller src set is conceptually padded with 0's in its higher order bits to align with the larger dst set (no modifications to the smaller set are performed to achieve this). This is done to stay consistent with integer promotion and widening rules in C.

ccc_bs_any()

ccc_tribool ccc_bs_any

(

ccc_bitset const *

bs

)

Return true if any bits in set are 1.

Parameters

[in]

bs

a pointer to the bit set.

Returns

CCC_TRUE if any bits are 1, CCC_FALSE if no bits are 1, CCC_TRIBOOL_ERROR if bs is NULL.

ccc_bs_any_range()

ccc_tribool ccc_bs_any_range	(	ccc_bitset const *	bs,
		size_t	i,
		size_t	count
	)

Return true if any bits are 1 in the specified range.

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the starting position.
[in]	count	the size of the range to check.

Returns

CCC_TRUE if any bits are 1, CCC_FALSE if no bits are 1, CCC_TRIBOOL_ERROR if bs is NULL, i is invalid, count is invalid, or both i and count are invalid.

ccc_bs_blocks_capacity()

ccc_ucount ccc_bs_blocks_capacity

(

ccc_bitset const *

bs

)

Return number of ccc_bitblocks used by bit set for capacity bits.

Parameters

[in]

bs

a pointer to the bit set.

Returns

an OK(0) status and the capacity in number of bit blocks used to hold the entire capacity of bits in the set. If bs is NULL an argument error is set.

Capacity may be greater than or equal to size.

ccc_bs_blocks_size()

ccc_ucount ccc_bs_blocks_size

(

ccc_bitset const *

bs

)

Return number of ccc_bitblocks used by the bit set for size bits.

Parameters

[in]

bs

a pointer to the bit set.

Returns

size in number of bit blocks used to hold the current size of bits in the set. An argument error is set if bs is NULL.

Size may be less than or equal to capacity.

ccc_bs_capacity()

ccc_ucount ccc_bs_capacity

(

ccc_bitset const *

bs

)

Return total number of bits the capacity of the set can hold.

Parameters

[in]

bs

a pointer to the bit set.

Returns

an OK(0) status and the capacity of bits capable of being stored in the current set. If bs is NULL an argument error is set.

ccc_bs_clear()

ccc_result ccc_bs_clear

(

ccc_bitset *

bs

)

Clears the bit set by setting the size to 0 and all bits to 0. The underlying memory capacity remains unchanged.

Parameters

[in]

bs

a pointer to the bit set.

Returns

the result of the clear operation, error is returned if bs is NULL .

ccc_bs_clear_and_free()

ccc_result ccc_bs_clear_and_free

(

ccc_bitset *

bs

)

Clears the bit set by setting the size to 0 and freeing the underlying memory. Capacity becomes 0 as well.

Parameters

[in]

bs

a pointer to the bit set.

Returns

the result of the clear operation, error is returned if bs is NULL or the set cannot be freed because no allocation function was provided upon initialization.

ccc_bs_copy()

ccc_result ccc_bs_copy	(	ccc_bitset *	dst,
		ccc_bitset const *	src,
		ccc_alloc_fn *	fn
	)

Copy the bit set at source to destination.

Parameters

[in]	dst	the initialized destination for the copy of the src set.
[in]	src	the initialized source of the set.
[in]	fn	the optional allocation function if resizing is needed.

Returns

the result of the copy operation. If the destination capacity is less than the source capacity and no allocation function is provided an input error is returned. If resizing is required and resizing of dst fails a memory error is returned.

Note

dst must have capacity greater than or equal to src. If dst capacity is less than src, an allocation function must be provided with the fn argument.

Note that there are two ways to copy data from source to destination: provide sufficient memory and pass NULL as fn, or allow the copy function to take care of allocation for the copy.

Manual memory management with no allocation function provided.

#define BITSET_USING_NAMESPACE_CCC
static bitset src
    = bs_init((static bitblock[bs_blocks(11)]){}, NULL, NULL, 11);
set_rand_bits(&src);
static bitset src
    = bs_init((static bitblock[bs_blocks(13)]){}, NULL, NULL, 13);
ccc_result res = bs_copy(&dst, &src, NULL);

The above requires dst capacity be greater than or equal to src capacity. Here is memory management handed over to the copy function.

#define BITSET_USING_NAMESPACE_CCC
static bitset src = bs_init((bitblock *)NULL, std_alloc, NULL, 0);
push_rand_bits(&src);
static bitset src = bs_init((bitblock *)NULL, std_alloc, NULL, 0);
ccc_result res = bs_copy(&dst, &src, std_alloc);

The above allows dst to have a capacity less than that of the src as long as copy has been provided an allocation function to resize dst. Note that this would still work if copying to a destination that the user wants as a fixed size map.

#define BITSET_USING_NAMESPACE_CCC
static bitset src = bs_init((bitblock *)NULL, std_alloc, NULL, 0);
push_rand_bits(&src);
static bitset src = bs_init((bitblock *)NULL, NULL, NULL, 0);
ccc_result res = bs_copy(&dst, &src, std_alloc);

The above sets up dst with fixed size while src is a dynamic map. Because an allocation function is provided, the dst is resized once for the copy and retains its fixed size after the copy is complete. This would require the user to manually free the underlying buffer at dst eventually if this method is used. Usually it is better to allocate the memory explicitly before the copy if copying between maps without allocation permission.

These options allow users to stay consistent across containers with their memory management strategies.

ccc_bs_data()

ccc_bitblock * ccc_bs_data

(

ccc_bitset const *

bs

)

Return a reference to the base of the underlying block array.

Parameters

[in]

bs

a pointer to the bit set.

Returns

a reference to the base of the first block of the bit set block array or NULL if bs is NULL or has no capacity.

Every block populates bits from Least Significant Bit (LSB) to Most Significant Bit (MSB) so this reference is to the base or LSB of the entire set.

ccc_bs_empty()

ccc_tribool ccc_bs_empty

(

ccc_bitset const *

bs

)

Return true if no bits are actively tracked by the user and set.

Parameters

[in]

bs

a pointer to the bit set.

Returns

CCC_TRUE if the size of the set is 0 meaning no bits, regardless of 0 or 1 status, are tracked by the set. CCC_TRIBOOL_ERROR is returned if bs is NULL.

Warning

if the number of bits set to 1 is desired see ccc_bs_popcount.

ccc_bs_eq()

ccc_tribool ccc_bs_eq	(	ccc_bitset const *	a,
		ccc_bitset const *	b
	)

Checks two bit sets of the same size (not capacity) for equality.

Parameters

[in]	a	pointer to a bit set.
[in]	b	pointer to another bit set of equal size.

Returns

true if the bit sets are of equal size with identical bit values at every position, false if the sets are different sizes or have mismatched bits. A bool error is returned if either pointer is NULL.

ccc_bs_first_leading_one()

ccc_ucount ccc_bs_first_leading_one

(

ccc_bitset const *

bs

)

Return the index of the first leading bit set to 1 in the set, starting from the Most Significant Bit at index size - 1.

Parameters

[in]

bs

a pointer to the bit set.

Returns

the index of the first leading bit set to 1 or CCC_RESULT_FAIL if no 1 bit is found or bs in NULL.

ccc_bs_first_leading_one_range()

ccc_ucount ccc_bs_first_leading_one_range	(	ccc_bitset const *	bs,
		size_t	i,
		size_t	count
	)

Return the index of the first leading bit set to 1 in the set, starting from the Most Significant Bit at index size - 1.

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the starting index to search.
[in]	count	the size of the range to check from i towards index 0.

Returns

the index of the first leading bit set to 1 or CCC_RESULT_FAIL if no 1 bit is found, bs is NULL, or the range is invalid.

Warning

the user must validate their own range. A bit does not exist in an invalid range therefore CCC_RESULT_FAIL is returned. To distinguish a valid negative result signifying not found and a negative result indicating a range error the user must check their input.

ccc_bs_first_leading_ones()

ccc_ucount ccc_bs_first_leading_ones	(	ccc_bitset const *	bs,
		size_t	num_ones
	)

Returns the index of the start of the first leading num_ones contiguous 1 bits.

Parameters

[in]	bs	a pointer to the bit set.
[in]	num_ones	the number of leading contiguous 1 bits to find.

Returns

the index in a search starting from the Least Significant Bit of the set of the first 1 in a sequence of num_ones 1 bits. If the input is invalid or such a sequence cannot be found CCC_RESULT_FAIL is returned.

Warning

the user must validate that bs is non-NULL and num_ones is less than the size of the set in order to distinguish CCC_RESULT_FAIL returned as a result of a failed search or bad input.

ccc_bs_first_leading_ones_range()

ccc_ucount ccc_bs_first_leading_ones_range	(	ccc_bitset const *	bs,
		size_t	i,
		size_t	count,
		size_t	num_ones
	)

Returns the index of the start of the first leading num_ones contiguous 1 bits in the specified range.

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the starting index to search.
[in]	count	the size of the range to check.
[in]	num_ones	the number of leading contiguous 1 bits to find.

Returns

an OK(0) status and the index in a search starting from the Least Significant Bit of the range of the first 1 in a sequence of num_ones 1 bits. If such a sequence cannot be found CCC_RESULT_FAIL is set. If bs is NULL or any argument is out of range an argument error is set.

ccc_bs_first_leading_zero()

ccc_ucount ccc_bs_first_leading_zero

(

ccc_bitset const *

bs

)

Return the index of the first leading bit set to 0 in the set, starting from the Most Significant Bit at index size - 1.

Parameters

[in]

bs

a pointer to the bit set.

Returns

an OK(0) status and the index of the first bit set to 0 or CCC_RESULT_FAIL if no 1 bit is found. If bs in NULL an argument error is set.

ccc_bs_first_leading_zero_range()

ccc_ucount ccc_bs_first_leading_zero_range	(	ccc_bitset const *	bs,
		size_t	i,
		size_t	count
	)

Return the index of the first leading bit set to 0 in the set, starting from the Most Significant Bit at index size - 1.

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the starting index to search for a 0 bit.
[in]	count	size to search from Most Significant Bit to Least in range.

Returns

an OK(0) status the index of the first bit set to 0 or CCC_RESULT_FAIL if no 0 bit is found. If bs in NULL an argument error is set.

ccc_bs_first_leading_zeros()

ccc_ucount ccc_bs_first_leading_zeros	(	ccc_bitset const *	bs,
		size_t	num_zeros
	)

Returns the index of the start of the first leading num_zeros contiguous 0 bits.

Parameters

[in]	bs	a pointer to the bit set.
[in]	num_zeros	the number of leading contiguous 0 bits to find.

Returns

an OK(0) status and the index in a search, starting from the Most Significant Bit of the set, of the first 0 in a sequence of num_zeros 0 bits. If such a sequence cannot be found CCC_RESULT_FAIL is set. If bs is NULL or num_zeros is too large an argument error is set.

ccc_bs_first_leading_zeros_range()

ccc_ucount ccc_bs_first_leading_zeros_range	(	ccc_bitset const *	bs,
		size_t	i,
		size_t	count,
		size_t	num_zeros
	)

Returns the index of the start of the first leading num_zeros contiguous 0 bits in the specified range.

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the starting index to search.
[in]	count	the size of the range to check.
[in]	num_zeros	the number of leading contiguous 0 bits to find.

Returns

an OK(0) status and the index in a search, starting from the Most Significant Bit of the range, of the first 0 in a sequence of num_zeros 0 bits. If such a sequence cannot be found CCC_RESULT_FAIL is returned. If bs is NULL or the arguments are out of range an argument error is set.

ccc_bs_first_trailing_one()

ccc_ucount ccc_bs_first_trailing_one

(

ccc_bitset const *

bs

)

Return the index of the first trailing bit set to 1 in the set.

Parameters

[in]

bs

a pointer to the bit set.

Returns

an OK(0) status and index of the first trailing bit set to 1 or an error set to CCC_RESULT_FAIL if no 1 bit is found. Argument error is set if bs is NULL.

ccc_bs_first_trailing_one_range()

ccc_ucount ccc_bs_first_trailing_one_range	(	ccc_bitset const *	bs,
		size_t	i,
		size_t	count
	)

Return the index of the first trailing bit set to 1 in the range, starting from the Least Significant Bit at index 0.

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the starting index to search.
[in]	count	the size of the range to check.

Returns

an OK(0) status and the index of the first trailing bit set to 1 or CCC_RESULT_FAIL if no 1 bit is found. Argument error is returned bs is NULL, or the range is invalid.

ccc_bs_first_trailing_ones()

ccc_ucount ccc_bs_first_trailing_ones	(	ccc_bitset const *	bs,
		size_t	num_ones
	)

Returns the index of the start of the first trailing num_ones contiguous 1 bits.

Parameters

[in]	bs	a pointer to the bit set.
[in]	num_ones	the number of trailing contiguous 1 bits to find.

Returns

an OK(0) status and the index in a search starting from the Least Significant Bit of the set of the first 1 in a sequence of num_ones 1 bits. If such a sequence cannot be found CCC_RESULT_FAIL result error is set. If bs is NULL or num_ones is too large an argument error is set.

ccc_bs_first_trailing_ones_range()

ccc_ucount ccc_bs_first_trailing_ones_range	(	ccc_bitset const *	bs,
		size_t	i,
		size_t	count,
		size_t	num_ones
	)

Returns the index of the start of the first trailing num_ones contiguous 1 bits in the specified range.

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the starting index to search.
[in]	count	the size of the range to check.
[in]	num_ones	the number of trailing contiguous 1 bits to find.

Returns

an OK(0) status and the index in a search starting from the Least Significant Bit of the range of the first 1 in a sequence of num_ones 1 bits. If no range is found CCC_RESULT_FAIL error is set. If bs is NULL or arguments are out of range an argument error is set.

ccc_bs_first_trailing_zero()

ccc_ucount ccc_bs_first_trailing_zero

(

ccc_bitset const *

bs

)

Return the index of the first bit set to 0 in the set.

Parameters

[in]

bs

a pointer to the bit set.

Returns

an OK(0) status and the index of the first bit set to 0 or CCC_RESULT_FAIL if no 0 bit is found. If bs is NULL an argument error is set.

ccc_bs_first_trailing_zero_range()

ccc_ucount ccc_bs_first_trailing_zero_range	(	ccc_bitset const *	bs,
		size_t	i,
		size_t	count
	)

Return the index of the first bit set to 0 in the range.

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the starting index to search.
[in]	count	the size of the range to check.

Returns

an OK(0) status and the index of the first bit set to 0 or CCC_RESULT_FAIL if no 0 bit is found. If bs is NULL, or the range is invalid, an argument error is set.

ccc_bs_first_trailing_zeros()

ccc_ucount ccc_bs_first_trailing_zeros	(	ccc_bitset const *	bs,
		size_t	num_zeros
	)

Returns the index of the start of the first trailing num_zeros contiguous 0 bits.

Parameters

[in]	bs	a pointer to the bit set.
[in]	num_zeros	the number of trailing contiguous 0 bits to find.

Returns

an OK(0) status and the index in a search, starting from the Least Significant Bit of the set, of the first 0 in a sequence of num_zeros 0 bits. If such a sequence cannot be found CCC_RESULT_FAIL is returned. If bs is NULL or num zeros is too large an argument error is set.

ccc_bs_first_trailing_zeros_range()

ccc_ucount ccc_bs_first_trailing_zeros_range	(	ccc_bitset const *	bs,
		size_t	i,
		size_t	count,
		size_t	num_zeros
	)

Returns the index of the start of the first trailing num_zeros contiguous 0 bits in the specified range.

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the starting index to search.
[in]	count	the size of the range to check.
[in]	num_zeros	the number of trailing contiguous 0 bits to find.

Returns

the index in a search, starting from the Least Significant Bit of the range, of the first 0 in a sequence of num_zeros 0 bits. If the input is invalid or such a sequence cannot be found CCC_RESULT_FAIL is returned.

ccc_bs_flip()

ccc_tribool ccc_bs_flip	(	ccc_bitset *	bs,
		size_t	i
	)

Toggle the bit at index i.

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the index identifying the bit to toggle

Returns

the state of the bit before the toggle operation, true if it was previously true, false if it was previously false, or error if bs is NULL or i is out of range.

Note

this function performs bounds checking in the release target.

ccc_bs_flip_all()

ccc_result ccc_bs_flip_all

(

ccc_bitset *

bs

)

Toggle all of the bits to their opposing boolean value.

Parameters

[in]

bs

a pointer to the bit set.

Returns

the result of the operation. OK if successful, or an input error if bs is NULL.

ccc_bs_flip_range()

ccc_result ccc_bs_flip_range	(	ccc_bitset *	bs,
		size_t	i,
		size_t	count
	)

Flip all the bits in the range, starting at the Least Significant Bit in range and ending at the Most Significant Bit, to their opposite value.

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the starting index to reset.
[in]	count	the count of bits starting at i to reset.

Returns

the result of the operation. OK if successful, or an input error if bs is NULL or the range is invalid by position, count, or both.

Note that a range is defined from i to i + count, where i + count is the exclusive end of the range. This is equivalent to moving from Least to Most Significant Bit in an integer.

ccc_bs_is_proper_subset()

ccc_tribool ccc_bs_is_proper_subset	(	ccc_bitset const *	set,
		ccc_bitset const *	subset
	)

Return CCC_TRUE if subset is a proper subset of set (subset ⊂ set).

Parameters

[set]	the set to check subset against.
[subset]	the subset to confirm as a proper subset of set.

Returns

CCC_TRUE if all bit positions in subset share the same value–0 or 1–as the bit positions in set and set is of greater size than subset. A CCC_TRIBOOL_ERROR is returned if set or subset is NULL.

If set is of size 0 the function returns CCC_FALSE regardless of the size of subset. If set is not of size 0 and subset is of size 0 the function returns CCC_TRUE.

ccc_bs_is_subset()

ccc_tribool ccc_bs_is_subset	(	ccc_bitset const *	set,
		ccc_bitset const *	subset
	)

Return CCC_TRUE if subset is a subset of set (subset ⊆ set).

Parameters

[set]	the set to check subset against.
[subset]	the subset to confirm as a subset of set.

Returns

CCC_TRUE if all bit positions in subset share the same value–0 or 1–as the bit positions in set. A CCC_TRIBOOL_ERROR is returned if set or subset is NULL.

If set is size zero subset must also be of size 0 to return CCC_TRUE. If subset is size 0 the function returns CCC_TRUE regardless of the size of set.

ccc_bs_none()

ccc_tribool ccc_bs_none

(

ccc_bitset const *

bs

)

Return true if all bits are set to 0.

Parameters

[in]

bs

a pointer to the bit set.

Returns

CCC_TRUE if all bits are 0, CCC_FALSE if any bits are 1, CCC_TRIBOOL_ERROR if bs is NULL.

ccc_bs_none_range()

ccc_tribool ccc_bs_none_range	(	ccc_bitset const *	bs,
		size_t	i,
		size_t	count
	)

Return true if all bits are 0 in the specified range.

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the starting position.
[in]	count	the size of the range to check.

Returns

CCC_TRUE if all bits are 0, CCC_FALSE if any bits are 1, CCC_TRIBOOL_ERROR if bs is NULL, i is invalid, count is invalid, or both i and count are invalid.

ccc_bs_or()

ccc_result ccc_bs_or	(	ccc_bitset *	dst,
		ccc_bitset const *	src
	)

Bitwise OR dst set with src set.

Parameters

[in]	dst	the set to modified with the OR operation.
[in]	src	the set to be read as the source bits for the OR operation.

Returns

an OK result if the operation is successful or an input error if dst or src are NULL.

Note that sets are aligned from their Least Significant Bit and a smaller src set is conceptually padded with 0's in its higher order bits to align with the larger dst set (no modifications to the smaller set are performed to achieve this). This is done to stay consistent with how the operation would work on a smaller integer being stored in a larger integer to align with the larger.

ccc_bs_pop_back()

ccc_tribool ccc_bs_pop_back

(

ccc_bitset *

bs

)

Remove the Most Significant Bit from the set.

Parameters

[in]

bs

a pointer to the bit set.

Returns

the previous value of the Most Significant Bit (CCC_TRUE or CCC_FALSE) or a bool error if bs is NULL or bs is empty.

ccc_bs_popcount()

ccc_ucount ccc_bs_popcount

(

ccc_bitset const *

bs

)

Return the number of bits set to CCC_TRUE. O(n).

Parameters

[in]

bs

a pointer to the bit set.

Returns

the total number of bits currently set to CCC_TRUE. CCC_RESULT_FAIL is returned if bs is NULL.

ccc_bs_popcount_range()

ccc_ucount ccc_bs_popcount_range	(	ccc_bitset const *	bs,
		size_t	i,
		size_t	count
	)

Return the number of bits set to CCC_TRUE in the range. O(n).

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the starting position.
[in]	count	the size of the range to check.

Returns

the total number of bits currently set in the range to CCC_TRUE. An argument error is set if bs is NULL, i is invalid, count is invalid, or both i and count are invalid.

ccc_bs_push_back()

ccc_result ccc_bs_push_back	(	ccc_bitset *	bs,
		ccc_tribool	b
	)

Append a bit value to the set as the new Most Significant Bit.

Parameters

[in]	bs	a pointer to the bit set.
[in]	b	the value to push at the Most Significant Bit CCC_TRUE/CCC_FALSE.

Returns

the result of the operation, ok if successful or an error if bad parameters are provided or resizing is required to accommodate a new bit but resizing fails.

ccc_bs_reset()

ccc_tribool ccc_bs_reset	(	ccc_bitset *	bs,
		size_t	i
	)

Set the bit at valid index i to boolean value b (true or false).

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the valid index identifying the bit to set.

Returns

the state of the bit before the set operation, true if it was previously true, false if it was previously false, or error if bs is NULL or i is out of range.

Note

this function performs bounds checking in the release target.

ccc_bs_reset_all()

ccc_result ccc_bs_reset_all

(

ccc_bitset *

bs

)

Set all the bits to CCC_FALSE.

Parameters

[in]

bs

a pointer to the bit set.

Returns

the result of the operation. OK if successful, or an input error if bs is NULL.

ccc_bs_reset_range()

ccc_result ccc_bs_reset_range	(	ccc_bitset *	bs,
		size_t	i,
		size_t	count
	)

Set all the bits in the specified range starting at the Least Significant Bit of the range and ending at the Most Significant Bit of the range to CCC_FALSE.

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the starting index to reset.
[in]	count	the count of bits starting at i to reset.

Returns

the result of the operation. OK if successful, or an input error if bs is NULL or the range is invalid by position, count, or both.

Note that a range is defined from i to i + count, where i + count is the exclusive end of the range. This is equivalent to moving from Least to Most Significant bit in an integer.

ccc_bs_set()

ccc_tribool ccc_bs_set	(	ccc_bitset *	bs,
		size_t	i,
		ccc_tribool	b
	)

Set the bit at valid index i to value b (true or false).

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the valid index identifying the bit to set.
[in]	b	the value to set at position i (CCC_TRUE or CCC_FALSE).

Returns

the state of the bit before the set operation, true if it was previously true, false if it was previously false, or error if bs is NULL or i is out of range.

Note

this function performs bounds checking in the release target.

ccc_bs_set_all()

ccc_result ccc_bs_set_all	(	ccc_bitset *	bs,
		ccc_tribool	b
	)

Set all the bits to the provided value (CCC_TRUE or CCC_FALSE).

Parameters

[in]	bs	a pointer to the bit set.
[in]	b	the value to set (CCC_TRUE or CCC_FALSE).

Returns

the result of the operation. OK if successful, or an input error if bs is NULL.

ccc_bs_set_range()

ccc_result ccc_bs_set_range	(	ccc_bitset *	bs,
		size_t	i,
		size_t	count,
		ccc_tribool	b
	)

Set all the bits in the specified range starting at the Least Significant Bit of the range and ending at the Most Significant Bit of the range (CCC_TRUE or CCC_FALSE).

Parameters

[in]	bs	a pointer to the bit set.
[in]	b	the value to set (CCC_TRUE or CCC_FALSE).
[in]	i	the starting index to set.
[in]	count	the count of bits starting at i to set.

Returns

the result of the operation. OK if successful, or an input error if bs is NULL or the range is invalid by position, count, or both.

Note that a range is defined from i to i + count, where i + count is the exclusive end of the range. This is equivalent to moving from Least to Most Significant bit in an integer.

ccc_bs_shiftl()

ccc_result ccc_bs_shiftl	(	ccc_bitset *	bs,
		size_t	left_shifts
	)

Shift the bit set left by left_shifts amount.

Parameters

[in]	bs	a pointer to the bit set.
[in]	left_shifts	the number of left shifts to perform.

Returns

an ok result if the operation was successful or an error if the bitset is NULL.

Note that if the number of shifts is greater than the bit set size the bit set is zeroed out rather than exhibiting undefined behavior as in the equivalent integer operation.

ccc_bs_shiftr()

ccc_result ccc_bs_shiftr	(	ccc_bitset *	bs,
		size_t	right_shifts
	)

Shift the bit set right by right_shifts amount.

Parameters

[in]	bs	a pointer to the bit set.
[in]	right_shifts	the number of right shifts to perform.

Returns

an ok result if the operation was successful or an error if the bitset is NULL.

Note that if the number of shifts is greater than the bit set size the bit set is zeroed out rather than exhibiting undefined behavior as in the equivalent integer operation.

ccc_bs_size()

ccc_ucount ccc_bs_size

(

ccc_bitset const *

bs

)

Return total number of bits actively tracked by the user and set.

Parameters

[in]

bs

a pointer to the bit set.

Returns

an OK(0) status and the total number of bits currently tracked by the set regardless of true or false state of each. If bs is NULL an argument error is set.

ccc_bs_test()

ccc_tribool ccc_bs_test	(	ccc_bitset const *	bs,
		size_t	i
	)

Test the bit at index i for boolean status (CCC_TRUE or CCC_FALSE).

Parameters

[in]	bs	a pointer to the bit set.
[in]	i	the index identifying the bit to set.

Returns

the state of the bit, or CCC_TRIBOOL_ERROR if bs is NULL.

Note

this function performs bounds checking in the release target.

ccc_bs_xor()

ccc_result ccc_bs_xor	(	ccc_bitset *	dst,
		ccc_bitset const *	src
	)

Bitwise XOR dst set with src set.

Parameters

[in]	dst	the set to modified with the XOR operation.
[in]	src	the set to be read as the source bits for the XOR operation.

Returns

an OK result if the operation is successful or an input error if dst or src are NULL.

Note that sets are aligned from their Least Significant Bit and a smaller src set is conceptually padded with 0's in its higher order bits to align with the larger dst set (no modifications to the smaller set are performed to achieve this). This is done to stay consistent with how the operation would work on a smaller integer being stored in a larger integer to align with the larger.