Skip to content

Instantly share code, notes, and snippets.

@EddieRingle
Created Jan 10, 2014
Embed
What would you like to do?
A dynamic bit array, I guess.
#include <stdlib.h>
#include <string.h>
#ifndef barr_malloc
# define barr_malloc(sz) malloc(sz)
#endif
#ifndef barr_realloc
# define barr_realloc(ptr, sz) realloc(ptr, sz)
#endif
#ifndef barr_free
# define barr_free(ptr) free(ptr)
#endif
#define BIT_SET(i, n) (i |= 1 << (n))
#define BIT_CLR(i, n) (i &= ~(1 << (n)))
#define BIT_TGL(i, n) (i ^= 1 << (n))
#define BIT_CHK(i, n) (i & (1 << (n)))
#define BITS_PER_CHUNK (sizeof(uint64_t) * 8)
#define CHUNK_OF_BIT(i) (i / BITS_PER_CHUNK)
#define BIT_OF_CHUNK(i) (i % BITS_PER_CHUNK)
typedef int barr_bit;
enum {
BARR_OK = 0,
BARR_INVALID_ARGS,
BARR_MEMORY_ERROR
};
typedef struct barr_t * barr_t;
struct barr_t {
size_t size;
size_t capacity;
size_t chunk_count;
uint64_t *chunks;
};
#define barr_check(ptr) \
if ((ptr) == NULL || *(ptr) == NULL || (*(ptr))->chunks == NULL) { \
return BARR_INVALID_ARGS; \
};
/**
* Initialize a new array
*/
int barr_init(barr_t *barr);
/**
* Free a given array
*/
int barr_destroy(barr_t *barr);
/**
* Push a new bit onto the end of the array
*/
int barr_push(barr_t *barr, barr_bit bit);
/**
* Check the value of the bit at the specified index
*/
int barr_get(barr_t *barr, size_t index, barr_bit *bit);
/**
* Set the bit at the specified index
*/
int barr_set(barr_t *barr, size_t index);
/**
* Clear the bit at the specified index
*/
int barr_clear(barr_t *barr, size_t index);
/**
* Toggle the bit at the specified index
*/
int barr_toggle(barr_t *barr, size_t index);
int barr_init(barr_t *barr)
{
if (barr == NULL) {
return BARR_INVALID_ARGS;
}
*barr = barr_malloc(sizeof(barr_t));
if (*barr == NULL) {
return BARR_MEMORY_ERROR;
}
(*barr)->chunks = barr_malloc(sizeof(uint64_t));
if ((*barr)->chunks == NULL) {
return BARR_MEMORY_ERROR;
}
(*barr)->capacity = BITS_PER_CHUNK;
(*barr)->chunk_count = 1;
(*barr)->size = 0;
return BARR_OK;
}
int barr_destroy(barr_t *barr)
{
barr_check(barr);
barr_free((*barr)->chunks);
barr_free(*barr);
*barr = NULL;
return BARR_OK;
}
static int barr_grow(barr_t *barr)
{
(*barr)->chunks = barr_realloc((*barr)->chunks, sizeof(uint64_t) * (*barr)->chunk_count * 2);
if ((*barr)->chunks == NULL) {
return BARR_MEMORY_ERROR;
}
memset((*barr)->chunks + (*barr)->chunk_count, 0, sizeof(uint64_t) * (*barr)->chunk_count);
(*barr)->capacity *= 2;
(*barr)->chunk_count *= 2;
return BARR_OK;
}
static int barr_grow_to_index(barr_t *barr, size_t index)
{
int ret;
while (index >= (*barr)->capacity) {
/*
* TODO:
* barr_grow memset's the newly allocated portion to zero.
* We should try to delay the memset until this while loop completes.
*/
if ((ret = barr_grow(barr)) != BARR_OK) {
return ret;
}
}
return BARR_OK;
}
int barr_push(barr_t *barr, barr_bit bit)
{
size_t index = (*barr)->size;
return (bit) ? barr_set(barr, index) : barr_clear(barr, index);
}
int barr_get(barr_t *barr, size_t index, barr_bit *bit)
{
barr_check(barr);
if (bit == NULL) {
return BARR_INVALID_ARGS;
}
if (index >= (*barr)->capacity) {
*bit = 0;
return BARR_OK;
}
*bit = (unsigned)BIT_CHK((*barr)->chunks[CHUNK_OF_BIT(index)], BIT_OF_CHUNK(index) + 1);
return BARR_OK;
}
int barr_set(barr_t *barr, size_t index)
{
int ret;
barr_check(barr);
if ((ret = barr_grow_to_index(barr, index)) != BARR_OK) {
return ret;
}
BIT_SET((*barr)->chunks[CHUNK_OF_BIT(index)], BIT_OF_CHUNK(index) + 1);
return BARR_OK;
}
int barr_clear(barr_t *barr, size_t index)
{
barr_check(barr);
if (index >= (*barr)->capacity) {
return barr_grow_to_index(barr, index);
}
BIT_CLR((*barr)->chunks[CHUNK_OF_BIT(index)], BIT_OF_CHUNK(index) + 1);
return BARR_OK;
}
int barr_toggle(barr_t *barr, size_t index)
{
int ret;
barr_check(barr);
if ((ret = barr_grow_to_index(barr, index)) != BARR_OK) {
return ret;
}
BIT_TGL((*barr)->chunks[CHUNK_OF_BIT(index)], BIT_OF_CHUNK(index) + 1);
return BARR_OK;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment