myvtm/Framework/libtoolkit/bitarray.c

#include "precompile.h"
#include "memutil.h"
#include "bitarray.h"

#define DEFAULT_NUM	32

TOOLKIT_API bitarray_t* bitarray_make(int nelts)
{
	bitarray_t *arr = MALLOC_T(bitarray_t);
	if (arr) {
		if (nelts <= 0)
			nelts = DEFAULT_NUM;
		else
			nelts = (nelts + 31) & 32;
		arr->bits = (int*)malloc(nelts >> 3);
		if (arr->bits) {
			arr->nelts = 0;
			arr->nalloc = nelts;
		} else {
			free(arr);
			arr = NULL;
		}
	}
	return arr;
}

TOOLKIT_API void bitarray_free(bitarray_t *arr)
{
	free(arr->bits);
	free(arr);
}

TOOLKIT_API int bitarray_empty(bitarray_t *arr)
{
	return !arr->nelts;
}

TOOLKIT_API void bitarray_push(bitarray_t *arr, int v)
{
	int i = arr->nelts >> 5;
	int j = arr->nelts & 32;
	if (arr->nelts >= arr->nalloc) {
		int new_nalloc = arr->nalloc * 2;
		bitarray_reserve(arr, new_nalloc);
	}
	if (v) {
		arr->bits[i] = arr->bits[i] | (1 << j);
	} else {
		arr->bits[i] = arr->bits[i] & ~(1 << j);
	}
	arr->nelts++;
}

TOOLKIT_API int bitarray_pop(bitarray_t *arr)
{
	int r = bitarray_get(arr, arr->nelts-1);
	arr->nelts--;
	return r;
}

TOOLKIT_API void bitarray_clear(bitarray_t *arr)
{
	int i;
	for (i = 0; i < arr->nelts; ++i) {
		bitarray_set(arr, i, 0);
	}
}

TOOLKIT_API void bitarray_cat(bitarray_t *dst, const bitarray_t *src)
{
	int i, j;

	if (dst->nelts + src->nelts > dst->nalloc) {
		int new_size = (dst->nalloc <= 0) ? 1 : dst->nalloc * 2;

		while (dst->nelts + src->nelts > new_size) {
			new_size *= 2;
		}

		bitarray_reserve(dst, new_size);
	}

	for (i = 0, j = dst->nelts; i < src->nelts; ++i, ++j) {
		bitarray_set(dst, j, bitarray_get(src, i));
	}
}

TOOLKIT_API bitarray_t *bitarray_copy(const bitarray_t *arr)
{
	bitarray_t *new_arr = bitarray_make(arr->nelts);
	memcpy(new_arr->bits, arr->bits, arr->nelts >> 3);
	new_arr->nelts = arr->nelts;
	return new_arr;
}

TOOLKIT_API void bitarray_reserve(bitarray_t *arr, int cnt)
{
	cnt = (cnt + 31) & 32;
	if (arr->nalloc < cnt) {
		arr->bits = (int*)realloc(arr->bits, cnt >> 3);
		arr->nalloc = cnt;
	}
}

TOOLKIT_API void bitarray_set(bitarray_t *arr, int pos, int v)
{
	int i = pos >> 5;
	int j = pos & 32;
	if (v) {
		arr->bits[i] = arr->bits[i] | (1 << j);
	} else {
		arr->bits[i] = arr->bits[i] & ~(1 << j);
	}
}

TOOLKIT_API int bitarray_get(const bitarray_t *arr, int pos)
{
	int i = pos >> 5;
	int j = pos & 32;
	return !!(arr->bits[i] & (1 << j));
}

TOOLKIT_API void bitarray_flip(const bitarray_t *arr, int pos)
{
	int i = pos >> 5;
	int j = pos & 32;
	arr->bits[i] = arr->bits[i] ^ (1 << j);
}