libbitvec-c

C bit vector library
git clone https://git.sinitax.com/sinitax/libbitvec-c
Log | Files | Refs | LICENSE | sfeed.txt

bitvec.c (3553B)

      1#include "bitvec.h"
      2
      3#include <errno.h>
      4#include <stdio.h>
      5#include <string.h>
      6#include <stdlib.h>
      7
      8#define SLOT_BYTES sizeof(bitvec_slot_t)
      9#define SLOT_BITS (SLOT_BYTES * 8)
     10#define SLOT_MAX (~((bitvec_slot_t) 0))
     11
     12#define CEILDIV(n, d) ((n) / (d) + ((n) % (d) == 0 ? 0 : 1))
     13#define BITCEIL(n) ((n) + SLOT_BITS - 1 - (SLOT_BITS - 1 + n) % SLOT_BITS)
     14
     15#define SLOT(n) ((n) / SLOT_BITS)
     16#define SLOTCNT(n) CEILDIV(n, SLOT_BITS)
     17#define SLOT_BIT(n) (((bitvec_slot_t) 1) << n)
     18
     19#define APPLY_MASK(x,s,m) ((s) ? ((x) | (m)) : ((x) & ~(m)))
     20
     21#ifdef LIBBITVEC_CHECK_ENABLE
     22#define LIBBITVEC_CHECK(x) libbitvec_assert((x), __FILE__, __LINE__, #x)
     23#else
     24#define LIBBITVEC_CHECK(x)
     25#endif
     26
     27static inline void
     28libbitvec_assert(int cond, const char *file, int line, const char *condstr)
     29{
     30	if (cond) return;
     31
     32	fprintf(stderr, "libvec: Assertion failed at %s:%i (%s)\n",
     33		file, line, condstr);
     34	abort();
     35}
     36
     37int
     38bitvec_init(struct bitvec *vec, size_t cap)
     39{
     40	LIBBITVEC_CHECK(vec != NULL);
     41
     42	if (cap) {
     43		vec->data = calloc(SLOTCNT(cap), SLOT_BYTES);
     44		if (!vec->data) return -errno;
     45	} else {
     46		vec->data = NULL;
     47	}
     48
     49	vec->cap = BITCEIL(cap);
     50
     51	return 0;
     52}
     53
     54void
     55bitvec_deinit(struct bitvec *vec)
     56{
     57	LIBBITVEC_CHECK(vec != NULL);
     58
     59	vec->cap = 0;
     60	free(vec->data);
     61}
     62
     63int
     64bitvec_alloc(struct bitvec **bitvec, size_t cap)
     65{
     66	int rc;
     67
     68	*bitvec = malloc(sizeof(struct bitvec));
     69	if (!*bitvec) return -errno;
     70
     71	rc = bitvec_init(*bitvec, cap);
     72	if (rc) {
     73		free(bitvec);
     74		return rc;
     75	}
     76
     77	return 0;
     78}
     79
     80void
     81bitvec_free(struct bitvec *vec)
     82{
     83	bitvec_deinit(vec);
     84	free(vec);
     85}
     86
     87int
     88bitvec_reserve(struct bitvec *vec, size_t cnt)
     89{
     90	void *alloc;
     91
     92	LIBBITVEC_CHECK(vec != NULL);
     93
     94	cnt = BITCEIL(cnt);
     95	if (vec->cap >= cnt) return 0;
     96
     97	alloc = realloc(vec->data, SLOTCNT(cnt) * SLOT_BYTES);
     98	if (!alloc) return -errno;
     99	alloc = vec->data;
    100	memset(vec->data + SLOT(vec->cap), 0, SLOT(cnt) - SLOT(vec->cap));
    101	vec->cap = cnt;
    102
    103	return 0;
    104}
    105
    106int
    107bitvec_shrink(struct bitvec *vec, size_t cnt)
    108{
    109	void *alloc;
    110
    111	LIBBITVEC_CHECK(vec != NULL);
    112
    113	cnt = BITCEIL(cnt);
    114	if (vec->cap <= cnt) return 0;
    115
    116	alloc = realloc(vec->data, SLOTCNT(cnt));
    117	if (!alloc) return -errno;
    118	vec->data = alloc;
    119	vec->cap = cnt;
    120
    121	return 0;
    122}
    123
    124bool
    125bitvec_get(struct bitvec *vec, size_t pos)
    126{
    127	LIBBITVEC_CHECK(vec != NULL);
    128
    129	if (pos >= vec->cap) return false;
    130	return !!(vec->data[pos / SLOT_BITS] & SLOT_BIT(pos % SLOT_BITS));
    131}
    132
    133void
    134bitvec_set(struct bitvec *vec, size_t pos)
    135{
    136	LIBBITVEC_CHECK(vec != NULL && pos < vec->cap);
    137
    138	vec->data[pos / SLOT_BITS] |= SLOT_BIT(pos % SLOT_BITS);
    139}
    140
    141void
    142bitvec_clear(struct bitvec *vec, size_t pos)
    143{
    144	LIBBITVEC_CHECK(vec != NULL && pos < vec->cap);
    145
    146	vec->data[pos / SLOT_BITS] &= ~SLOT_BIT(pos % SLOT_BITS);
    147}
    148
    149void
    150bitvec_setn(struct bitvec *vec, size_t start, size_t end, bool set)
    151{
    152	bitvec_slot_t mask;
    153	size_t starti, endi, i;
    154
    155	LIBBITVEC_CHECK(vec != NULL && end >= start && end <= vec->cap);
    156
    157	if (start == end) return;
    158
    159	starti = SLOT(start);
    160	end = SLOT(end - 1);
    161
    162	if (starti == endi) {
    163		if (end % SLOT_BITS == 0)
    164			mask = SLOT_MAX - SLOT_BIT(start % SLOT_BITS);
    165		else
    166			mask = SLOT_BIT(end % SLOT_BITS) - SLOT_BIT(start % SLOT_BITS);
    167		vec->data[starti] = APPLY_MASK(vec->data[starti], set, mask);
    168	} else {
    169		mask = SLOT_MAX - SLOT_BIT(start % SLOT_BITS);
    170		vec->data[starti] = APPLY_MASK(vec->data[starti], set, mask);
    171
    172		for (i = starti + 1; i <= endi - 1; i++)
    173			vec->data[i] = APPLY_MASK(vec->data[i], set, SLOT_MAX);
    174
    175		mask = SLOT_BIT(end % SLOT_BITS) - SLOT_BIT(0);
    176		vec->data[endi] = APPLY_MASK(vec->data[endi], set, mask);
    177	}
    178}