bitmask.h#

#include <sif/structures/bitmask.h>
SIF_STRUCTURES_BITMASK_H#

Dense array of bits, packed 64 to a word.

Used where one boolean per grid cell would otherwise cost a byte or more: the finders mark every cell swallowed by an accepted void, and at 1024^3 cells the difference between a bit and a byte is 128 MiB against 1 GiB.

The accessors are static inline because they sit in the innermost loop of the finders, where a call would cost more than the shift and mask it wraps.

struct sif_bitmask_t#

A bitmask for tracking boolean states densely.

Note

The plain set/unset accessors are NOT thread-safe: distinct bits share a 64-bit word, so concurrent read-modify-write silently loses updates. Code that mutates the mask from inside a parallel region must use the _atomic variants.

uint64_t *words#

Packed storage, 64 bits per word. Bits past #n_bits are always zero.

uint64_t n_bits#

Bits the caller asked for.

uint64_t n_words#

Words actually allocated: ceil(n_bits / 64).

sif_bitmask_t *sif_bitmask_alloc(uint64_t n_bits)#

Allocate a bitmask with every bit clear.

Parameters:

  • n_bits – Number of bits. Must be non-zero.

Returns:

The mask, owned by the caller and released with sif_bitmask_free(). NULL if n_bits is 0 or on allocation failure.

void sif_bitmask_free(sif_bitmask_t *mask)#

Release a bitmask and its storage.

Parameters:

  • mask – Mask to free. NULL is accepted and ignored.

void sif_bitmask_clear_all(sif_bitmask_t *mask)#

Clear every bit.

Parameters:

  • mask – Mask to clear.

uint64_t sif_bitmask_count_set(const sif_bitmask_t *mask)#

Count the set bits.

Parallelized across words with a population count per word, so it costs a pass over the storage rather than over the bits.

Parameters:

  • mask – Mask to count.

Returns:

The number of set bits, or 0 for a NULL or empty mask.

static inline uint8_t sif_bitmask_get(const sif_bitmask_t *mask, uint64_t ind)#

Test one bit.

Parameters:

  • mask – The mask.

  • ind – Bit index; must be below sif_bitmask_t::n_bits.

Returns:

1 if the bit is set, 0 otherwise.

static inline void sif_bitmask_set(sif_bitmask_t *mask, uint64_t ind)#

Set one bit. Fast, and NOT thread-safe.

Parameters:

  • mask – The mask.

  • ind – Bit index; must be below sif_bitmask_t::n_bits.

static inline void sif_bitmask_unset(sif_bitmask_t *mask, uint64_t ind)#

Clear one bit. Fast, and NOT thread-safe.

Parameters:

  • mask – The mask.

  • ind – Bit index; must be below sif_bitmask_t::n_bits.

static inline void sif_bitmask_set_atomic(sif_bitmask_t *mask, uint64_t ind)#

Set one bit. Safe to call concurrently.

Parameters:

  • mask – The mask.

  • ind – Bit index; must be below sif_bitmask_t::n_bits.

Note

The test-before-write is an atomic relaxed load, not a plain read: it skips the expensive RMW when the bit is already set without introducing a data race. Two threads racing to set the same bit is harmless, OR is idempotent.

static inline void sif_bitmask_unset_atomic(sif_bitmask_t *mask, uint64_t ind)#

Clear one bit. Safe to call concurrently.

Parameters:

  • mask – The mask.

  • ind – Bit index; must be below sif_bitmask_t::n_bits.

Note

Same relaxed test-before-write as sif_bitmask_set_atomic().