sbitset.h: bit set (bit array)

Functions allowing bit random access storage and bit counting. Bit counting is optimized so, instead of per-call 'poppulation count', it takes O(1) for the computation, as a record of bit set/clear is kept.

sb_alloc	sb_capacity	sb_dup	sb_popcount	sb_reset	sb_test
sb_alloca	sb_clear	sb_free	sb_reserve	sb_set

srt_bitset *sb_alloc(size_t initial_num_elems_reserve)

Allocate bitset (heap)
size_t initial_num_elems_reserve: space preallocated to store n elements
Return (srt_bitset *): bitset
Time complexity: O(n)
Space complexity: no extra space
Coverage: [1/2] test covered (test + Valgrind)
Quality: [2/4] reviewed, clean (-Wall, style, speed)

srt_bitset *sb_alloca(size_t initial_num_elems_reserve)

Allocate bitset (stack)
size_t initial_num_elems_reserve: space preallocated to store n elements
Return (srt_bitset *): bitset
Time complexity: O(n)
Space complexity: no extra space
Coverage: [1/2] test covered (test + Valgrind)
Quality: [2/4] reviewed, clean (-Wall, style, speed)

size_t sb_capacity(const srt_bitset *b)

Preallocated space left (number of 1 bit elements)
const srt_bitset *b: bitset
Return (size_t): allocated space left (unit: bits)
Time complexity: O(1)
Space complexity: no extra space
Coverage: [1/2] test covered (test + Valgrind)
Quality: [2/4] reviewed, clean (-Wall, style, speed)

void sb_clear(srt_bitset *b)

Reset bitset
srt_bitset *b: bitset
Return (void): -
Time complexity: O(1)
Space complexity: no extra space
Coverage: [1/2] test covered (test + Valgrind)
Quality: [2/4] reviewed, clean (-Wall, style, speed)

srt_bitset *sb_dup(const srt_bitset *src)

Duplicate bitset
const srt_bitset *src: bitset
Return (srt_bitset *): output bitset
Time complexity: O(n)
Space complexity: no extra space
Coverage: [1/2] test covered (test + Valgrind)
Quality: [2/4] reviewed, clean (-Wall, style, speed)

srt_bitset *sb_free(srt_bitset **b, ...)

Free one or more bitsets (heap)
srt_bitset **b: bitset
...: more bitsets (optional)
Return (srt_bitset *): bitset
Time complexity: O(1)
Space complexity: no extra space
Coverage: [1/2] test covered (test + Valgrind)
Quality: [2/4] reviewed, clean (-Wall, style, speed)

size_t sb_popcount(const srt_bitset *b)

Number of bits set to 1
const srt_bitset *b: bitset
Return (size_t): Map number of elements
Time complexity: O(1)
Space complexity: no extra space
Coverage: [1/2] test covered (test + Valgrind)
Quality: [2/4] reviewed, clean (-Wall, style, speed)

size_t sb_reserve(srt_bitset **b, size_t max_elems)

Ensure space for N 1-bit elements
srt_bitset **b: bitset
size_t max_elems: absolute element reserve (unit: bits)
Return (size_t): reserved elements
Time complexity: O(1)
Space complexity: no extra space
Coverage: [1/2] test covered (test + Valgrind)
Quality: [2/4] reviewed, clean (-Wall, style, speed)

void sb_reset(srt_bitset **b, size_t nth)

Set nth bit to 0
srt_bitset **b: bitset
size_t nth: bit offset
Time complexity: O(1)
Space complexity: no extra space
Coverage: [1/2] test covered (test + Valgrind)
Quality: [2/4] reviewed, clean (-Wall, style, speed)

void sb_set(srt_bitset **b, size_t nth)

Set nth bit to 1
srt_bitset **b: bitset
size_t nth: bit offset
Time complexity: O(1)
Space complexity: no extra space
Coverage: [1/2] test covered (test + Valgrind)
Quality: [2/4] reviewed, clean (-Wall, style, speed)

int sb_test(const srt_bitset *b, size_t nth)

Access to nth bit
const srt_bitset *b: bitset
size_t nth: bit offset
Return (int): 1 or 0
Time complexity: O(1)
Space complexity: no extra space
Coverage: [1/2] test covered (test + Valgrind)
Quality: [2/4] reviewed, clean (-Wall, style, speed)