Bitmap

include/structures/bitmap.h View source View on GitHub

Type Aliases

typedef uint64_t bitmap_word_t;

void bitmap_set(bitmap_word_t *map, size_t bit);

void bitmap_clear(bitmap_word_t *map, size_t bit);

void bitmap_toggle(bitmap_word_t *map, size_t bit);

bool bitmap_test(const bitmap_word_t *map, size_t bit);

bool bitmap_test_and_set(bitmap_word_t *map, size_t bit);

bool bitmap_test_and_clear(bitmap_word_t *map, size_t bit);

void bitmap_atomic_set(bitmap_word_t *map, size_t bit);

void bitmap_atomic_clear(bitmap_word_t *map, size_t bit);

void bitmap_atomic_toggle(bitmap_word_t *map, size_t bit);

bool bitmap_atomic_test(const bitmap_word_t *map, size_t bit);

bool bitmap_atomic_test_and_set(bitmap_word_t *map, size_t bit);

bool bitmap_atomic_test_and_clear(bitmap_word_t *map, size_t bit);

void bitmap_zero(bitmap_word_t *map, size_t nbits);

void bitmap_copy(bitmap_word_t *dst, const bitmap_word_t *src, size_t nbits);

void bitmap_fill(bitmap_word_t *map, size_t nbits);

void bitmap_set_range(bitmap_word_t *map, size_t start, size_t len);

void bitmap_clear_range(bitmap_word_t *map, size_t start, size_t len);

void bitmap_and(bitmap_word_t *dst, const bitmap_word_t *src1, const bitmap_word_t *src2, size_t nbits);

void bitmap_or(bitmap_word_t *dst, const bitmap_word_t *src1, const bitmap_word_t *src2, size_t nbits);

void bitmap_xor(bitmap_word_t *dst, const bitmap_word_t *src1, const bitmap_word_t *src2, size_t nbits);

void bitmap_andnot(bitmap_word_t *dst, const bitmap_word_t *src1, const bitmap_word_t *src2, size_t nbits);

bool bitmap_equal(const bitmap_word_t *src1, const bitmap_word_t *src2, size_t nbits);

bool bitmap_intersects(const bitmap_word_t *src1, const bitmap_word_t *src2, size_t nbits);

bool bitmap_subset(const bitmap_word_t *subset, const bitmap_word_t *superset, size_t nbits);

bool bitmap_empty(const bitmap_word_t *map, size_t nbits);

bool bitmap_full(const bitmap_word_t *map, size_t nbits);

size_t bitmap_weight(const bitmap_word_t *map, size_t nbits);

size_t bitmap_find_first_set(const bitmap_word_t *map, size_t nbits);

size_t bitmap_find_first_zero(const bitmap_word_t *map, size_t nbits);

size_t bitmap_find_next_bit(const bitmap_word_t *map, size_t nbits, size_t start);

size_t bitmap_find_next_zero_bit(const bitmap_word_t *map, size_t nbits, size_t start);

#define BITMAP_BITS_PER_WORD 64

#define BITMAP_WORDS(nbits) DIV_ROUND_UP(nbits, BITMAP_BITS_PER_WORD)

#define BITMAP_DECLARE(name, nbits) bitmap_word_t name[BITMAP_WORDS(nbits)]

#define BITMAP_WORD_INDEX(bit) ((bit) / BITMAP_BITS_PER_WORD)

#define BITMAP_BIT_OFFSET(bit) ((bit) % BITMAP_BITS_PER_WORD)

#define BITMAP_BIT_MASK(bit) ((bitmap_word_t) 1 << BITMAP_BIT_OFFSET(bit))

#define bitmap_for_each_bit_set(bit, map, nbits) \
    for (size_t bit = 0; bit < (nbits); bit++) \
        if (bitmap_test((map), (bit)))

#define bitmap_for_each_bit_unset(bit, map, nbits) \
    for (size_t bit = 0; bit < (nbits); bit++) \
        if (!bitmap_test((map), (bit)))