bitarray.h

Go to the documentation of this file.

 
 
#pragma once
 
#include <assert.h>
#include <inttypes.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <util/alloc.h>
 
typedef struct {
  union {
    uint8_t block[sizeof(uint8_t *)]; 
    uint8_t *base; 
  };
  size_t size_bits; 
} bitarray_t;
 
static inline bitarray_t bitarray_new(size_t size_bits) {
 
  bitarray_t ba = {.size_bits = size_bits};
 
  // if the array is small enough, we can use inline storage
  if (size_bits <= sizeof(ba.block) * 8) {
    // nothing to be done
 
    // otherwise we need to heap-allocate
  } else {
    size_t capacity = size_bits / 8 + (size_bits % 8 == 0 ? 0 : 1);
    ba.base = gv_calloc(capacity, sizeof(uint8_t));
  }
 
  return ba;
}
 
static inline bool bitarray_get(bitarray_t self, size_t index) {
  assert(index < self.size_bits && "out of bounds access");
 
  // determine if this array is stored inline or not
  const uint8_t *base;
  if (self.size_bits <= sizeof(self.block) * 8) {
    base = self.block;
  } else {
    base = self.base;
  }
 
  return (base[index / 8] >> (index % 8)) & 1;
}
 
static inline void bitarray_set(bitarray_t *self, size_t index, bool value) {
  assert(index < self->size_bits && "out of bounds access");
 
  // determine if this array is stored inline or not
  uint8_t *base;
  if (self->size_bits <= sizeof(self->block) * 8) {
    base = self->block;
  } else {
    base = self->base;
  }
 
  if (value) {
    base[index / 8] |= (uint8_t)(UINT8_C(1) << (index % 8));
  } else {
    base[index / 8] &= (uint8_t)~(UINT8_C(1) << (index % 8));
  }
}
 
static inline void bitarray_clear(bitarray_t *self) {
  assert(self != NULL);
 
  // determine if this array is stored inline or not
  uint8_t *const base =
      self->size_bits <= sizeof(self->block) * 8 ? self->block : self->base;
 
  // calculate byte extent covering the array
  const size_t size = self->size_bits / 8 + (self->size_bits % 8 == 0 ? 0 : 1);
 
  // zero all bits
  memset(base, 0, size);
}
 
static inline void bitarray_reset(bitarray_t *self) {
  assert(self != NULL);
 
  // is this array stored out of line?
  if (self->size_bits > sizeof(self->block) * 8)
    free(self->base);
 
  *self = (bitarray_t){0};
}