-
Notifications
You must be signed in to change notification settings - Fork 0
/
bitarr.h
283 lines (234 loc) · 6.54 KB
/
bitarr.h
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
/* Implements an expandable int->bool bit array. */
#pragma once
#include <stdbool.h>
#include <limits.h>
#include <stdint.h>
#include <stdlib.h>
#ifndef WORD
typedef uint64_t word;
#define WORD 64
#define WORD_MAX UINT64_MAX
#ifdef PRIu64
#define PRIW PRIu64
#else
#define PRIW "ul"
#endif
#endif
#pragma region Types
typedef word *bitarr_t;
#pragma endregion
#pragma region Internal Functions
static inline size_t _bitarr_size(size_t len)
{
return (len / WORD) + ((len % WORD) ? 1 : 0);
}
#pragma endregion
#pragma region Interface
/* Resizes the given array from the old to the new size.
New bits are initialized to 0. */
bitarr_t bitarr_resize(bitarr_t arr, size_t oldLen, size_t newLen);
/* Initializes a new bitarray with the given length.
Every bit is set to 0. */
bitarr_t bitarr_new(size_t len);
/* Reads the bit at the given index. */
bool bitarr_get(bitarr_t arr, size_t index);
/* Sets the bit at the given index to the given value. */
void bitarr_set(bitarr_t arr, size_t index, bool value);
/* Deallocates the given bit array */
void bitarr_destroy(bitarr_t arr);
/* Counts the total number of bits in the bitarray of the given length with the givne value. */
size_t bitarr_count(bitarr_t arr, size_t len, bool val);
/* Finds the lowest bit index >= start in the array with the given value.
The given length is absolute.
Returns -1 if the value doesn't exist */
size_t bitarr_next(const bitarr_t arr, size_t start, size_t len, bool val);
/* Determines if any bit in the array is of the given value. */
bool bitarr_any(const bitarr_t arr, size_t len, bool val);
/* Determines if every bit in the array is of the given value. */
bool bitarr_all(const bitarr_t arr, size_t len, bool val);
/* Determines if, for every 1 in pos, arr is 1 at that position and, for every 1 in neg, arr is 0 at that position.
pos or neg may be NULL, in which case they are ignored. */
bool bitarr_match(const bitarr_t arr, size_t len, const bitarr_t pos, const bitarr_t neg);
/* Sets arr to the bitwise or of arr and r. */
void bitarr_eqor(bitarr_t arr, size_t len, const bitarr_t r);
/* Determines if, at any index, l and r are both 1. */
bool bitarr_anyAnd(bitarr_t l, size_t len, bitarr_t r);
/* Copies src to dest */
void bitarr_copy(bitarr_t dest, size_t len, const bitarr_t src);
/* Sets the first length bits in the array, starting at startIndex, to value. */
void bitarr_fill(bitarr_t arr, size_t startIndex, size_t length, bool value);
#pragma endregion
#pragma region Macros
/* Iterates over all indexes in arr for which arr[i] == val. i cannot be a full declaration, only an identifier. */
#define bitarr_forall(arr, len, i, val) for (size_t i = bitarr_next(arr, 0, len, val); i != (size_t)-1; i = bitarr_next(arr, i + 1, len, val))
#pragma endregion
#pragma region Implementation
bitarr_t bitarr_resize(bitarr_t arr, size_t oldLen, size_t newLen)
{
size_t newSiz = _bitarr_size(newLen);
size_t oldSiz = _bitarr_size(oldLen);
if(oldSiz != newSiz && !(arr = realloc(arr, newSiz * 8)))
return NULL;
if(newLen > oldLen)
bitarr_fill(arr, oldLen, newLen - oldLen, false);
return arr;
}
bitarr_t bitarr_new(size_t len)
{
return calloc(_bitarr_size(len), sizeof(word));
}
bool bitarr_get(bitarr_t arr, size_t index)
{
return (bool)(arr[index / WORD] & (1 << (index % WORD)));
}
void bitarr_set(bitarr_t arr, size_t index, bool value)
{
if(value)
arr[index / WORD] |= (1 << (index % WORD));
else
arr[index / WORD] &= ~(1 << (index % WORD));
}
void bitarr_destroy(bitarr_t arr)
{
free(arr);
}
size_t bitarr_count(bitarr_t arr, size_t len, bool val)
{
const word skip = val ? 0 : WORD_MAX;
const word all = val ? WORD_MAX : 0;
size_t siz = _bitarr_size(len);
size_t c = 0;
for (size_t i = 0; i < siz; i++)
{
word cur = arr[i];
// Avoid bitwise iteration if possible
if(cur == skip)
continue;
if(i < (len / WORD) && cur == all)
{
c += WORD;
continue;
}
size_t wl = ((i + 1 == siz) && (len % WORD)) ? (len % WORD) : WORD;
for (size_t j = 0; j < wl; j++)
{
if(cur & 1)
c++;
cur >>= 1;
}
}
return c;
}
size_t bitarr_next(const bitarr_t arr, size_t start, size_t len, bool val)
{
size_t z = _bitarr_size(len);
word skip = val ? 0 : WORD_MAX;
size_t p = start;
for (size_t w = start / WORD; w < z; w++)
{
if(arr[w] == skip)
continue;
word cur = arr[w];
if(start % WORD)
{
cur >>= start % WORD;
start = 0;
}
for (; p < len; cur >>= 1, p++)
{
if((cur & 1) == val)
return p;
}
}
return -1;
}
bool bitarr_any(const bitarr_t arr, size_t len, bool val)
{
return bitarr_next(arr, 0, len, val) != (size_t)-1;
}
bool bitarr_all(const bitarr_t arr, size_t len, bool val)
{
word want = val ? WORD_MAX : 0;
for (size_t w = 0; w < len / WORD; w++)
{
if(arr[w] != want)
return false;
}
size_t rest = len % WORD;
if(!rest)
return true;
word mask = WORD_MAX >> (WORD - rest);
return (arr[len / WORD] & mask) == (want & mask);
}
bool bitarr_match(const bitarr_t arr, size_t len, const bitarr_t pos, const bitarr_t neg)
{
if(pos)
{
bitarr_forall(pos, len, i, true)
{
if(!bitarr_get(arr, i))
return false;
}
}
if(neg)
{
bitarr_forall(neg, len, i, true)
{
if(bitarr_get(arr, i))
return false;
}
}
return true;
}
void bitarr_eqor(bitarr_t arr, size_t len, const bitarr_t r)
{
for (size_t w = 0; w < len / WORD; w++)
arr[w] |= r[w];
// Handles last word
if(len % WORD)
arr[len/WORD] |= r[len/WORD] & (WORD_MAX >> (WORD - (len % WORD)));
}
bool bitarr_anyAnd(bitarr_t l, size_t len, bitarr_t r)
{
for (size_t w = 0; w < len / WORD; w++)
{
if(l[w] & r[w])
return true;
}
// Handles last word
if(len % WORD && (l[len/WORD] & r[len/WORD] & (WORD_MAX >> (WORD - (len % WORD)))))
return true;
return false;
}
void bitarr_copy(bitarr_t dest, size_t len, const bitarr_t src)
{
size_t z = _bitarr_size(len);
for (size_t w = 0; w < z; w++)
dest[w] = src[w];
}
/* Sets every bit in arr to 1 is pos is 1, 0 if neg is 1 and to the value of arr otherwise */
void bitarr_merge(bitarr_t arr, size_t len, const bitarr_t pos, const bitarr_t neg)
{
size_t z = _bitarr_size(len);
for (size_t w = 0; w < z; w++)
{
arr[w] |= pos[w];
arr[w] &= ~neg[w];
}
}
void bitarr_fill(bitarr_t arr, size_t startIndex, size_t length, bool value)
{
// first partial word
if(startIndex % WORD)
{
if(value)
arr[startIndex / WORD] |= WORD_MAX << (startIndex % WORD);
else
arr[startIndex / WORD] &= WORD_MAX >> (WORD - (startIndex % WORD));
}
word fill = value ? WORD_MAX : 0;
size_t l = _bitarr_size(startIndex + length);
for (size_t i = _bitarr_size(startIndex); i < l; i++)
arr[i] = fill;
}
#pragma endregion