1 /*
2 * *****************************************************************************
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 *
6 * Copyright (c) 2018-2021 Gavin D. Howard and contributors.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are met:
10 *
11 * * Redistributions of source code must retain the above copyright notice, this
12 * list of conditions and the following disclaimer.
13 *
14 * * Redistributions in binary form must reproduce the above copyright notice,
15 * this list of conditions and the following disclaimer in the documentation
16 * and/or other materials provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 * POSSIBILITY OF SUCH DAMAGE.
29 *
30 * *****************************************************************************
31 *
32 * Code to manipulate vectors (resizable arrays).
33 *
34 */
35
36 #include <assert.h>
37 #include <stdlib.h>
38 #include <string.h>
39
40 #include <vector.h>
41 #include <lang.h>
42 #include <vm.h>
43
bc_vec_grow(BcVec * restrict v,size_t n)44 void bc_vec_grow(BcVec *restrict v, size_t n) {
45
46 size_t len, cap = v->cap;
47 sig_atomic_t lock;
48
49 len = bc_vm_growSize(v->len, n);
50
51 while (cap < len) cap = bc_vm_growSize(cap, cap);
52
53 BC_SIG_TRYLOCK(lock);
54 v->v = bc_vm_realloc(v->v, bc_vm_arraySize(cap, v->size));
55 v->cap = cap;
56 BC_SIG_TRYUNLOCK(lock);
57 }
58
bc_vec_init(BcVec * restrict v,size_t esize,BcVecFree dtor)59 void bc_vec_init(BcVec *restrict v, size_t esize, BcVecFree dtor) {
60 BC_SIG_ASSERT_LOCKED;
61 assert(v != NULL && esize);
62 v->size = esize;
63 v->cap = BC_VEC_START_CAP;
64 v->len = 0;
65 v->dtor = dtor;
66 v->v = bc_vm_malloc(bc_vm_arraySize(BC_VEC_START_CAP, esize));
67 }
68
bc_vec_expand(BcVec * restrict v,size_t req)69 void bc_vec_expand(BcVec *restrict v, size_t req) {
70
71 assert(v != NULL);
72
73 if (v->cap < req) {
74
75 sig_atomic_t lock;
76
77 BC_SIG_TRYLOCK(lock);
78
79 v->v = bc_vm_realloc(v->v, bc_vm_arraySize(req, v->size));
80 v->cap = req;
81
82 BC_SIG_TRYUNLOCK(lock);
83 }
84 }
85
bc_vec_npop(BcVec * restrict v,size_t n)86 void bc_vec_npop(BcVec *restrict v, size_t n) {
87
88 sig_atomic_t lock;
89
90 assert(v != NULL && n <= v->len);
91
92 BC_SIG_TRYLOCK(lock);
93
94 if (v->dtor == NULL) v->len -= n;
95 else {
96 size_t len = v->len - n;
97 while (v->len > len) v->dtor(v->v + (v->size * --v->len));
98 }
99
100 BC_SIG_TRYUNLOCK(lock);
101 }
102
bc_vec_npopAt(BcVec * restrict v,size_t n,size_t idx)103 void bc_vec_npopAt(BcVec *restrict v, size_t n, size_t idx) {
104
105 char* ptr, *data;
106
107 assert(v != NULL);
108 assert(idx + n < v->len);
109
110 ptr = bc_vec_item(v, idx);
111 data = bc_vec_item(v, idx + n);
112
113 BC_SIG_LOCK;
114
115 if (v->dtor != NULL) {
116
117 size_t i;
118
119 for (i = 0; i < n; ++i) v->dtor(bc_vec_item(v, idx + i));
120 }
121
122 v->len -= n;
123 memmove(ptr, data, (v->len - idx) * v->size);
124
125 BC_SIG_UNLOCK;
126 }
127
bc_vec_npush(BcVec * restrict v,size_t n,const void * data)128 void bc_vec_npush(BcVec *restrict v, size_t n, const void *data) {
129
130 sig_atomic_t lock;
131
132 assert(v != NULL && data != NULL);
133
134 BC_SIG_TRYLOCK(lock);
135
136 if (v->len + n > v->cap) bc_vec_grow(v, n);
137
138 memcpy(v->v + (v->size * v->len), data, v->size * n);
139 v->len += n;
140
141 BC_SIG_TRYUNLOCK(lock);
142 }
143
bc_vec_push(BcVec * restrict v,const void * data)144 inline void bc_vec_push(BcVec *restrict v, const void *data) {
145 bc_vec_npush(v, 1, data);
146 }
147
bc_vec_pushByte(BcVec * restrict v,uchar data)148 void bc_vec_pushByte(BcVec *restrict v, uchar data) {
149 assert(v != NULL && v->size == sizeof(uchar));
150 bc_vec_npush(v, 1, &data);
151 }
152
bc_vec_pushIndex(BcVec * restrict v,size_t idx)153 void bc_vec_pushIndex(BcVec *restrict v, size_t idx) {
154
155 uchar amt, nums[sizeof(size_t) + 1];
156
157 assert(v != NULL);
158 assert(v->size == sizeof(uchar));
159
160 for (amt = 0; idx; ++amt) {
161 nums[amt + 1] = (uchar) idx;
162 idx &= ((size_t) ~(UCHAR_MAX));
163 idx >>= sizeof(uchar) * CHAR_BIT;
164 }
165
166 nums[0] = amt;
167
168 bc_vec_npush(v, amt + 1, nums);
169 }
170
bc_vec_pushAt(BcVec * restrict v,const void * data,size_t idx)171 static void bc_vec_pushAt(BcVec *restrict v, const void *data, size_t idx) {
172
173 sig_atomic_t lock;
174
175 assert(v != NULL && data != NULL && idx <= v->len);
176
177 BC_SIG_TRYLOCK(lock);
178
179 if (idx == v->len) bc_vec_push(v, data);
180 else {
181
182 char *ptr;
183
184 if (v->len == v->cap) bc_vec_grow(v, 1);
185
186 ptr = v->v + v->size * idx;
187
188 memmove(ptr + v->size, ptr, v->size * (v->len++ - idx));
189 memmove(ptr, data, v->size);
190 }
191
192 BC_SIG_TRYUNLOCK(lock);
193 }
194
bc_vec_string(BcVec * restrict v,size_t len,const char * restrict str)195 void bc_vec_string(BcVec *restrict v, size_t len, const char *restrict str) {
196
197 sig_atomic_t lock;
198
199 assert(v != NULL && v->size == sizeof(char));
200 assert(v->dtor == NULL);
201 assert(!v->len || !v->v[v->len - 1]);
202 assert(v->v != str);
203
204 BC_SIG_TRYLOCK(lock);
205
206 bc_vec_popAll(v);
207 bc_vec_expand(v, bc_vm_growSize(len, 1));
208 memcpy(v->v, str, len);
209 v->len = len;
210
211 bc_vec_pushByte(v, '\0');
212
213 BC_SIG_TRYUNLOCK(lock);
214 }
215
bc_vec_concat(BcVec * restrict v,const char * restrict str)216 void bc_vec_concat(BcVec *restrict v, const char *restrict str) {
217
218 sig_atomic_t lock;
219
220 assert(v != NULL && v->size == sizeof(char));
221 assert(v->dtor == NULL);
222 assert(!v->len || !v->v[v->len - 1]);
223 assert(v->v != str);
224
225 BC_SIG_TRYLOCK(lock);
226
227 if (v->len) v->len -= 1;
228
229 bc_vec_npush(v, strlen(str) + 1, str);
230
231 BC_SIG_TRYUNLOCK(lock);
232 }
233
bc_vec_empty(BcVec * restrict v)234 void bc_vec_empty(BcVec *restrict v) {
235
236 sig_atomic_t lock;
237
238 assert(v != NULL && v->size == sizeof(char));
239 assert(v->dtor == NULL);
240
241 BC_SIG_TRYLOCK(lock);
242
243 bc_vec_popAll(v);
244 bc_vec_pushByte(v, '\0');
245
246 BC_SIG_TRYUNLOCK(lock);
247 }
248
249 #if BC_ENABLE_HISTORY
bc_vec_replaceAt(BcVec * restrict v,size_t idx,const void * data)250 void bc_vec_replaceAt(BcVec *restrict v, size_t idx, const void *data) {
251
252 char *ptr;
253
254 BC_SIG_ASSERT_LOCKED;
255
256 assert(v != NULL);
257
258 ptr = bc_vec_item(v, idx);
259
260 if (v->dtor != NULL) v->dtor(ptr);
261
262 memcpy(ptr, data, v->size);
263 }
264 #endif // BC_ENABLE_HISTORY
265
bc_vec_item(const BcVec * restrict v,size_t idx)266 inline void* bc_vec_item(const BcVec *restrict v, size_t idx) {
267 assert(v != NULL && v->len && idx < v->len);
268 return v->v + v->size * idx;
269 }
270
bc_vec_item_rev(const BcVec * restrict v,size_t idx)271 inline void* bc_vec_item_rev(const BcVec *restrict v, size_t idx) {
272 assert(v != NULL && v->len && idx < v->len);
273 return v->v + v->size * (v->len - idx - 1);
274 }
275
bc_vec_clear(BcVec * restrict v)276 inline void bc_vec_clear(BcVec *restrict v) {
277 BC_SIG_ASSERT_LOCKED;
278 v->v = NULL;
279 v->len = 0;
280 v->dtor = NULL;
281 }
282
bc_vec_free(void * vec)283 void bc_vec_free(void *vec) {
284 BcVec *v = (BcVec*) vec;
285 BC_SIG_ASSERT_LOCKED;
286 bc_vec_popAll(v);
287 free(v->v);
288 }
289
bc_map_find(const BcVec * restrict v,const char * name)290 static size_t bc_map_find(const BcVec *restrict v, const char *name) {
291
292 size_t low = 0, high = v->len;
293
294 while (low < high) {
295
296 size_t mid = (low + high) / 2;
297 const BcId *id = bc_vec_item(v, mid);
298 int result = strcmp(name, id->name);
299
300 if (!result) return mid;
301 else if (result < 0) high = mid;
302 else low = mid + 1;
303 }
304
305 return low;
306 }
307
bc_map_insert(BcVec * restrict v,const char * name,size_t idx,size_t * restrict i)308 bool bc_map_insert(BcVec *restrict v, const char *name,
309 size_t idx, size_t *restrict i)
310 {
311 BcId id;
312
313 BC_SIG_ASSERT_LOCKED;
314
315 assert(v != NULL && name != NULL && i != NULL);
316
317 *i = bc_map_find(v, name);
318
319 assert(*i <= v->len);
320
321 if (*i != v->len && !strcmp(name, ((BcId*) bc_vec_item(v, *i))->name))
322 return false;
323
324 id.name = bc_vm_strdup(name);
325 id.idx = idx;
326
327 bc_vec_pushAt(v, &id, *i);
328
329 return true;
330 }
331
bc_map_index(const BcVec * restrict v,const char * name)332 size_t bc_map_index(const BcVec *restrict v, const char *name) {
333
334 size_t i;
335
336 assert(v != NULL && name != NULL);
337
338 i = bc_map_find(v, name);
339
340 if (i >= v->len) return BC_VEC_INVALID_IDX;
341
342 return strcmp(name, ((BcId*) bc_vec_item(v, i))->name) ?
343 BC_VEC_INVALID_IDX : i;
344 }
345