bitvector.h

Go to the documentation of this file.

 
#ifndef CBITS_BITVECTOR_H
#define CBITS_BITVECTOR_H
 
#include "compat.h"
#include <stdbool.h>
 
#define BV_ALIGN 64
#define BV_WORDS_SUPER_SHIFT 3
#define BV_WORDS_SUPER (1u << BV_WORDS_SUPER_SHIFT)
 
static inline size_t
bv_word(const size_t pos)
{
    return pos >> 6;
}
static inline size_t
bv_bit(const size_t pos)
{
    return pos & 63;
}
 
typedef struct {
    uint64_t *data; 
    size_t n_bits;  
    size_t n_words; 
    size_t
        *super_rank; 
    uint16_t *block_rank; 
    bool rank_dirty; 
} BitVector;
 
static inline void
bv_apply_tail_mask(BitVector *bv)
{
    if (!bv->n_words) {
        return;
    }
    unsigned tail = (unsigned) (bv->n_bits & 63);
    if (tail) {
        uint64_t mask = (UINT64_C(1) << tail) - 1;
        bv->data[bv->n_words - 1] &= mask;
    }
}
 
BitVector *
bv_new(size_t n_bits);
BitVector *
bv_copy(const BitVector *src);
void
bv_free(BitVector *bv);
static inline int
bv_get(const BitVector *bv, const size_t pos)
{
    return (bv->data[bv_word(pos)] >> bv_bit(pos)) & 1;
}
static inline void
bv_set(BitVector *bv, const size_t pos)
{
    uint64_t mask = 1ULL << bv_bit(pos);
    bv->data[bv_word(pos)] |= mask;
    bv->rank_dirty = true;
}
static inline void
bv_clear(BitVector *bv, const size_t pos)
{
    uint64_t mask = ~(1ULL << bv_bit(pos));
    bv->data[bv_word(pos)] &= mask;
    bv->rank_dirty = true;
}
static inline void
bv_flip(BitVector *bv, const size_t pos)
{
    uint64_t mask = 1ULL << bv_bit(pos);
    bv->data[bv_word(pos)] ^= mask;
    bv->rank_dirty = true;
}
void
bv_set_range(BitVector *bv, size_t start, size_t len);
void
bv_clear_range(BitVector *bv, size_t start, size_t len);
void
bv_flip_range(BitVector *bv, size_t start, size_t len);
void
bv_build_rank(BitVector *bv);
size_t
bv_rank(BitVector *bv, const size_t pos);
bool
bv_equal(const BitVector *a, const BitVector *b);
bool
bv_contains_subvector(const BitVector *a, const BitVector *b);
 
#endif /* CBITS_BITVECTOR_H */