1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#ifndef BITSET_H
#define BITSET_H
#include <stdint.h>
#include <stdbit.h>
#include "arena.h"
#define BITSET_BYTES sizeof(uintmax_t)
#define BITSET_BITS (8 * BITSET_BYTES)
#define BITSET_CAP(n) (((n)/BITSET_BITS)+1)
#define BITSET_HAS(s, i) (1 & ((s)[(i)/BITSET_BITS] >> ((i)&(BITSET_BITS-1))))
#define BITSET_MASK(i) ((uintmax_t)1 << ((i)&(BITSET_BITS-1)))
#define BITSET_SET(s, i) ((s)[(i)/BITSET_BITS] |= BITSET_MASK(i))
#define BITSET_CLR(s, i) ((s)[(i)/BITSET_BITS] &= ~BITSET_MASK(i))
#define BITSET_ALLOC(a, n) new_arr(a, uintmax_t, BITSET_CAP(n))
#define BITSET_SET_ALL(s, n) memset(s, 0xff, BITSET_CAP(n) * BITSET_BYTES)
#define BITSET_CLR_ALL(s, n) memset(s, 0x00, BITSET_CAP(n) * BITSET_BYTES)
typedef struct {
size_t cap;
uintmax_t *data;
} BitSet;
static inline void bitset_fit(BitSet *s, size_t sz, Arena *a) {
if (s->cap >= sz) return;
size_t c = stdc_bit_ceil(sz);
s->data = resize(a, s->data, BITSET_CAP(s->cap), BITSET_CAP(c));
s->cap = c;
for (uint32_t i = BITSET_CAP(s->cap); i < c; i++)
s->data[i] = 0;
}
static inline void bitset_clr(BitSet *s) {
if (s->data) BITSET_CLR_ALL(s->data, s->cap);
}
static inline void bitset_fill(BitSet *s, size_t n, Arena *a) {
bitset_fit(s, n - 1, a);
if (s->data) BITSET_SET_ALL(s->data, s->cap);
}
static inline void bitset_add(BitSet *s, uint32_t n, Arena *a) {
bitset_fit(s, n, a);
BITSET_SET(s->data, n);
}
static inline int bitset_has(BitSet *s, uint32_t n) {
return (n / BITSET_BITS < s->cap) && BITSET_HAS(s->data, n);
}
static inline void bitset_del(BitSet *s, uint32_t n) {
if (BITSET_HAS(s->data, n)) {
BITSET_CLR(s->data, n);
}
}
#endif
|
