bitset.h File Reference

A bitset for operating on flags. More...

#include <stdbool.h>
#include <stdint.h>

Go to the source code of this file.

Data Structures
struct	Bitset
	A bitset spread across multiple uint32_t words. More...
struct	BitsetItr
	An iterator into a Bitset. More...

Macros
#define	BITSET_BITS_PER_WORD   32
	Number of bits in a word for a bitset.
#define	BITSET_ARRAY_SIZE   8
	Number of words in a bitset.
#define	BITSET_MAX_BITS   (BITSET_BITS_PER_WORD * BITSET_ARRAY_SIZE)
	Maximum number of bits in a bitset.
#define	BITSET_DEFINE(name, capacity)
	Make a standard bitset.

Typedefs
typedef struct Bitset	Bitset
	A bitset spread across multiple uint32_t words.

Functions
void	bitset_set_idx (Bitset *bitset, int idx, bool on)
	Set a flag in a bitset to a value.
bool	bitset_get_idx (Bitset *bitset, int idx)
	Get the value of a flag.
int	bitset_set_next_free_idx (Bitset *bitset)
	Set the next free index in the bitset and return the index value.
void	bitset_clear (Bitset *bitset)
	Clear the bitset, all to 0.
bool	bitset_is_empty (Bitset *bitset)
	Check if a bitset is empty (all 0's)
int	bitset_num_set_bits (Bitset *bitset)
	Count how many bits are set to 1 in a bitset.
int	bitset_find_idx_of_nth_set (const Bitset *bitset, int n)
	Find the index of the nth set bit.
BitsetItr	bitset_itr_create (const Bitset *bitset)
	Declare a BitsetItr.
int	bitset_itr_next (BitsetItr *itr)
	Get the index of the next set bit in the bitset from a BitsetItr.

Detailed Description

A bitset for operating on flags.

Definition in file bitset.h.

Macro Definition Documentation

BITSET_ARRAY_SIZE

#define BITSET_ARRAY_SIZE   8

Number of words in a bitset.

Number of words in every bitset. This represents the maximum number and each bitset will always use this number of words, though it's capacity can be any length from 1 to BITSET_BITS_PER_WORD * BITSET_ARRAY_SIZE

Definition at line 28 of file bitset.h.

BITSET_BITS_PER_WORD

#define BITSET_BITS_PER_WORD   32

Number of bits in a word for a bitset.

Number of bits in a word for a bitset. Will always be 32 here.

Definition at line 18 of file bitset.h.

BITSET_DEFINE

#define BITSET_DEFINE	(		name,
			capacity
	)

Value:

    static uint32_t name##_w[BITSET_ARRAY_SIZE] = {0}; \
    static Bitset name = {                             \
        .w = name##_w,                                 \
        .nbits = BITSET_BITS_PER_WORD,                 \
        .nwords = BITSET_ARRAY_SIZE,                   \
        .cap = capacity,                               \
    };

Make a standard bitset.

Make a bitset with a valid static array to store it's array of words.

Use this to define bitsets in the code, specifically as a static scoped variable. The passed name will be the same name as the bitset.

Usage example:

BITSET_DEFINE(_my_bitset, 128);
// normal operation...
bitset_clear(&_my_bitset);

Parameters

name	the name of the bitset
capacity	the capacity of the bitset

Definition at line 198 of file bitset.h.

BITSET_MAX_BITS

#define BITSET_MAX_BITS   (BITSET_BITS_PER_WORD * BITSET_ARRAY_SIZE)

Maximum number of bits in a bitset.

Definition at line 34 of file bitset.h.

Function Documentation

bitset_clear()

void bitset_clear

(

Bitset *

bitset

)

Clear the bitset, all to 0.

Parameters

bitset

A Bitset to operate on

Definition at line 54 of file bitset.c.

bitset_find_idx_of_nth_set()

int bitset_find_idx_of_nth_set	(	const Bitset *	bitset,
		int	n
	)

Find the index of the nth set bit.

Find the index of the nth flag set to 1. This function is useful to get one value quickly, but does not operate iteratively well. Use a @BitsetItr for iterative access to a bitset.

Parameters

bitset

A Bitset to operate on

Returns

The index of the nth flag set to 1 in the bitset

Definition at line 92 of file bitset.c.

bitset_get_idx()

bool bitset_get_idx	(	Bitset *	bitset,
		int	idx
	)

Get the value of a flag.

Parameters

bitset	A Bitset to operate on
idx	the index of the flag to get

Returns

the value of the flag as true or false

Definition at line 72 of file bitset.c.

bitset_is_empty()

bool bitset_is_empty

(

Bitset *

bitset

)

Check if a bitset is empty (all 0's)

Parameters

bitset

A Bitset to operate on

Returns

true if empty, false otherwise

Definition at line 62 of file bitset.c.

bitset_itr_create()

BitsetItr bitset_itr_create

(

const Bitset *

bitset

)

Declare a BitsetItr.

Parameters

bitset

A Bitset to operate on

Returns

A newly constructed BitsetItr

Definition at line 128 of file bitset.c.

bitset_itr_next()

int bitset_itr_next

(

BitsetItr *

itr

)

Get the index of the next set bit in the bitset from a BitsetItr.

Parameters

itr	A BitsetItr to operate on

Returns

a positive number if successful, UNDEFINED otherwise (out-of-bounds)

Definition at line 140 of file bitset.c.

bitset_num_set_bits()

int bitset_num_set_bits

(

Bitset *

bitset

)

Count how many bits are set to 1 in a bitset.

Parameters

bitset

A Bitset to operate on

Returns

The number of flags set to 1 in a bitset

Definition at line 80 of file bitset.c.

bitset_set_idx()

void bitset_set_idx	(	Bitset *	bitset,
		int	idx,
		bool	on
	)

Set a flag in a bitset to a value.

Parameters

bitset	A Bitset to operate on
idx	the index of the flag to set
on	the value to set the flag to

Definition at line 5 of file bitset.c.

bitset_set_next_free_idx()

int bitset_set_next_free_idx

(

Bitset *

bitset

)

Set the next free index in the bitset and return the index value.

Parameters

bitset

A Bitset to operate on

Returns

The index of the bit that was set

Definition at line 27 of file bitset.c.