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 #include <stdbool.h>
40
41 #include <vector.h>
42 #include <lang.h>
43 #include <vm.h>
44
bc_vec_grow(BcVec * restrict v,size_t n)45 void bc_vec_grow(BcVec *restrict v, size_t n) {
46
47 size_t cap, len;
48 sig_atomic_t lock;
49
50 cap = v->cap;
51 len = v->len + n;
52
53 // If this is true, we might overflow.
54 if (len > SIZE_MAX / 2) cap = len;
55 else {
56 // Keep doubling until larger.
57 while (cap < len) cap += cap;
58 }
59
60 BC_SIG_TRYLOCK(lock);
61
62 v->v = bc_vm_realloc(v->v, bc_vm_arraySize(cap, v->size));
63 v->cap = cap;
64
65 BC_SIG_TRYUNLOCK(lock);
66 }
67
bc_vec_init(BcVec * restrict v,size_t esize,BcDtorType dtor)68 void bc_vec_init(BcVec *restrict v, size_t esize, BcDtorType dtor) {
69
70 BC_SIG_ASSERT_LOCKED;
71
72 assert(v != NULL && esize);
73
74 v->v = bc_vm_malloc(bc_vm_arraySize(BC_VEC_START_CAP, esize));
75
76 v->size = (BcSize) esize;
77 v->cap = BC_VEC_START_CAP;
78 v->len = 0;
79 v->dtor = (BcSize) dtor;
80 }
81
bc_vec_expand(BcVec * restrict v,size_t req)82 void bc_vec_expand(BcVec *restrict v, size_t req) {
83
84 assert(v != NULL);
85
86 // Only expand if necessary.
87 if (v->cap < req) {
88
89 sig_atomic_t lock;
90
91 BC_SIG_TRYLOCK(lock);
92
93 v->v = bc_vm_realloc(v->v, bc_vm_arraySize(req, v->size));
94 v->cap = req;
95
96 BC_SIG_TRYUNLOCK(lock);
97 }
98 }
99
bc_vec_npop(BcVec * restrict v,size_t n)100 void bc_vec_npop(BcVec *restrict v, size_t n) {
101
102 sig_atomic_t lock;
103
104 assert(v != NULL && n <= v->len);
105
106 BC_SIG_TRYLOCK(lock);
107
108 if (!v->dtor) v->len -= n;
109 else {
110
111 const BcVecFree d = bc_vec_dtors[v->dtor];
112 size_t esize = v->size;
113 size_t len = v->len - n;
114
115 // Loop through and manually destruct every element.
116 while (v->len > len) d(v->v + (esize * --v->len));
117 }
118
119 BC_SIG_TRYUNLOCK(lock);
120 }
121
bc_vec_npopAt(BcVec * restrict v,size_t n,size_t idx)122 void bc_vec_npopAt(BcVec *restrict v, size_t n, size_t idx) {
123
124 char* ptr, *data;
125 sig_atomic_t lock;
126
127 assert(v != NULL);
128 assert(idx + n < v->len);
129
130 // Grab start and end pointers.
131 ptr = bc_vec_item(v, idx);
132 data = bc_vec_item(v, idx + n);
133
134 BC_SIG_TRYLOCK(lock);
135
136 if (v->dtor) {
137
138 size_t i;
139 const BcVecFree d = bc_vec_dtors[v->dtor];
140
141 // Destroy every popped item.
142 for (i = 0; i < n; ++i) d(bc_vec_item(v, idx + i));
143 }
144
145 v->len -= n;
146 memmove(ptr, data, (v->len - idx) * v->size);
147
148 BC_SIG_TRYUNLOCK(lock);
149 }
150
bc_vec_npush(BcVec * restrict v,size_t n,const void * data)151 void bc_vec_npush(BcVec *restrict v, size_t n, const void *data) {
152
153 sig_atomic_t lock;
154 size_t esize;
155
156 assert(v != NULL && data != NULL);
157
158 BC_SIG_TRYLOCK(lock);
159
160 // Grow if necessary.
161 if (v->len + n > v->cap) bc_vec_grow(v, n);
162
163 esize = v->size;
164
165 // Copy the elements in.
166 memcpy(v->v + (esize * v->len), data, esize * n);
167 v->len += n;
168
169 BC_SIG_TRYUNLOCK(lock);
170 }
171
bc_vec_push(BcVec * restrict v,const void * data)172 inline void bc_vec_push(BcVec *restrict v, const void *data) {
173 bc_vec_npush(v, 1, data);
174 }
175
bc_vec_pushEmpty(BcVec * restrict v)176 void* bc_vec_pushEmpty(BcVec *restrict v) {
177
178 sig_atomic_t lock;
179 void *ptr;
180
181 assert(v != NULL);
182
183 BC_SIG_TRYLOCK(lock);
184
185 // Grow if necessary.
186 if (v->len + 1 > v->cap) bc_vec_grow(v, 1);
187
188 ptr = v->v + v->size * v->len;
189 v->len += 1;
190
191 BC_SIG_TRYUNLOCK(lock);
192
193 return ptr;
194 }
195
bc_vec_pushByte(BcVec * restrict v,uchar data)196 inline void bc_vec_pushByte(BcVec *restrict v, uchar data) {
197 assert(v != NULL && v->size == sizeof(uchar));
198 bc_vec_npush(v, 1, &data);
199 }
200
bc_vec_pushIndex(BcVec * restrict v,size_t idx)201 void bc_vec_pushIndex(BcVec *restrict v, size_t idx) {
202
203 uchar amt, nums[sizeof(size_t) + 1];
204
205 assert(v != NULL);
206 assert(v->size == sizeof(uchar));
207
208 // Encode the index.
209 for (amt = 0; idx; ++amt) {
210 nums[amt + 1] = (uchar) idx;
211 idx &= ((size_t) ~(UCHAR_MAX));
212 idx >>= sizeof(uchar) * CHAR_BIT;
213 }
214
215 nums[0] = amt;
216
217 // Push the index onto the vector.
218 bc_vec_npush(v, amt + 1, nums);
219 }
220
bc_vec_pushAt(BcVec * restrict v,const void * data,size_t idx)221 void bc_vec_pushAt(BcVec *restrict v, const void *data, size_t idx) {
222
223 assert(v != NULL && data != NULL && idx <= v->len);
224
225 BC_SIG_ASSERT_LOCKED;
226
227 // Do the easy case.
228 if (idx == v->len) bc_vec_push(v, data);
229 else {
230
231 char *ptr;
232 size_t esize;
233
234 // Grow if necessary.
235 if (v->len == v->cap) bc_vec_grow(v, 1);
236
237 esize = v->size;
238
239 ptr = v->v + esize * idx;
240
241 memmove(ptr + esize, ptr, esize * (v->len++ - idx));
242 memcpy(ptr, data, esize);
243 }
244 }
245
bc_vec_string(BcVec * restrict v,size_t len,const char * restrict str)246 void bc_vec_string(BcVec *restrict v, size_t len, const char *restrict str) {
247
248 sig_atomic_t lock;
249
250 assert(v != NULL && v->size == sizeof(char));
251 assert(!v->dtor);
252 assert(!v->len || !v->v[v->len - 1]);
253 assert(v->v != str);
254
255 BC_SIG_TRYLOCK(lock);
256
257 bc_vec_popAll(v);
258 bc_vec_expand(v, bc_vm_growSize(len, 1));
259 memcpy(v->v, str, len);
260 v->len = len;
261
262 bc_vec_pushByte(v, '\0');
263
264 BC_SIG_TRYUNLOCK(lock);
265 }
266
bc_vec_concat(BcVec * restrict v,const char * restrict str)267 void bc_vec_concat(BcVec *restrict v, const char *restrict str) {
268
269 sig_atomic_t lock;
270
271 assert(v != NULL && v->size == sizeof(char));
272 assert(!v->dtor);
273 assert(!v->len || !v->v[v->len - 1]);
274 assert(v->v != str);
275
276 BC_SIG_TRYLOCK(lock);
277
278 // If there is already a string, erase its nul byte.
279 if (v->len) v->len -= 1;
280
281 bc_vec_npush(v, strlen(str) + 1, str);
282
283 BC_SIG_TRYUNLOCK(lock);
284 }
285
bc_vec_empty(BcVec * restrict v)286 void bc_vec_empty(BcVec *restrict v) {
287
288 sig_atomic_t lock;
289
290 assert(v != NULL && v->size == sizeof(char));
291 assert(!v->dtor);
292
293 BC_SIG_TRYLOCK(lock);
294
295 bc_vec_popAll(v);
296 bc_vec_pushByte(v, '\0');
297
298 BC_SIG_TRYUNLOCK(lock);
299 }
300
301 #if BC_ENABLE_HISTORY
bc_vec_replaceAt(BcVec * restrict v,size_t idx,const void * data)302 void bc_vec_replaceAt(BcVec *restrict v, size_t idx, const void *data) {
303
304 char *ptr;
305
306 BC_SIG_ASSERT_LOCKED;
307
308 assert(v != NULL);
309
310 ptr = bc_vec_item(v, idx);
311
312 if (v->dtor) bc_vec_dtors[v->dtor](ptr);
313
314 memcpy(ptr, data, v->size);
315 }
316 #endif // BC_ENABLE_HISTORY
317
bc_vec_item(const BcVec * restrict v,size_t idx)318 inline void* bc_vec_item(const BcVec *restrict v, size_t idx) {
319 assert(v != NULL && v->len && idx < v->len);
320 return v->v + v->size * idx;
321 }
322
bc_vec_item_rev(const BcVec * restrict v,size_t idx)323 inline void* bc_vec_item_rev(const BcVec *restrict v, size_t idx) {
324 assert(v != NULL && v->len && idx < v->len);
325 return v->v + v->size * (v->len - idx - 1);
326 }
327
bc_vec_clear(BcVec * restrict v)328 inline void bc_vec_clear(BcVec *restrict v) {
329 BC_SIG_ASSERT_LOCKED;
330 v->v = NULL;
331 v->len = 0;
332 v->dtor = BC_DTOR_NONE;
333 }
334
bc_vec_free(void * vec)335 void bc_vec_free(void *vec) {
336 BcVec *v = (BcVec*) vec;
337 BC_SIG_ASSERT_LOCKED;
338 bc_vec_popAll(v);
339 free(v->v);
340 }
341
342 #if !BC_ENABLE_LIBRARY
343
344 /**
345 * Finds a name in a map by binary search. Returns the index where the item
346 * *would* be if it doesn't exist. Callers are responsible for checking that the
347 * item exists at the index.
348 * @param v The map.
349 * @param name The name to find.
350 * @return The index of the item with @a name, or where the item would be
351 * if it does not exist.
352 */
bc_map_find(const BcVec * restrict v,const char * name)353 static size_t bc_map_find(const BcVec *restrict v, const char *name) {
354
355 size_t low = 0, high = v->len;
356
357 while (low < high) {
358
359 size_t mid = (low + high) / 2;
360 const BcId *id = bc_vec_item(v, mid);
361 int result = strcmp(name, id->name);
362
363 if (!result) return mid;
364 else if (result < 0) high = mid;
365 else low = mid + 1;
366 }
367
368 return low;
369 }
370
bc_map_insert(BcVec * restrict v,const char * name,size_t idx,size_t * restrict i)371 bool bc_map_insert(BcVec *restrict v, const char *name,
372 size_t idx, size_t *restrict i)
373 {
374 BcId id;
375 BcVec *slabs;
376
377 BC_SIG_ASSERT_LOCKED;
378
379 assert(v != NULL && name != NULL && i != NULL);
380
381 *i = bc_map_find(v, name);
382
383 assert(*i <= v->len);
384
385 if (*i != v->len && !strcmp(name, ((BcId*) bc_vec_item(v, *i))->name))
386 return false;
387
388 #if BC_ENABLED
389 slabs = BC_IS_DC ? &vm.main_slabs : &vm.other_slabs;
390 #else // BC_ENABLED
391 slabs = &vm.main_slabs;
392 #endif // BC_ENABLED
393
394 id.name = bc_slabvec_strdup(slabs, name);
395 id.idx = idx;
396
397 bc_vec_pushAt(v, &id, *i);
398
399 return true;
400 }
401
bc_map_index(const BcVec * restrict v,const char * name)402 size_t bc_map_index(const BcVec *restrict v, const char *name) {
403
404 size_t i;
405
406 assert(v != NULL && name != NULL);
407
408 i = bc_map_find(v, name);
409
410 // If out of range, return invalid.
411 if (i >= v->len) return BC_VEC_INVALID_IDX;
412
413 // Make sure the item exists.
414 return strcmp(name, ((BcId*) bc_vec_item(v, i))->name) ?
415 BC_VEC_INVALID_IDX : i;
416 }
417
418 #if DC_ENABLED
bc_map_name(const BcVec * restrict v,size_t idx)419 const char* bc_map_name(const BcVec *restrict v, size_t idx) {
420
421 size_t i, len = v->len;
422
423 for (i = 0; i < len; ++i) {
424 BcId* id = (BcId*) bc_vec_item(v, i);
425 if (id->idx == idx) return id->name;
426 }
427
428 BC_UNREACHABLE
429
430 return "";
431 }
432 #endif // DC_ENABLED
433
434 /**
435 * Initializes a single slab.
436 * @param s The slab to initialize.
437 */
bc_slab_init(BcSlab * s)438 static void bc_slab_init(BcSlab *s) {
439 s->s = bc_vm_malloc(BC_SLAB_SIZE);
440 s->len = 0;
441 }
442
443 /**
444 * Adds a string to a slab and returns a pointer to it, or NULL if it could not
445 * be added.
446 * @param s The slab to add to.
447 * @param str The string to add.
448 * @param len The length of the string, including its nul byte.
449 * @return A pointer to the new string in the slab, or NULL if it could not
450 * be added.
451 */
bc_slab_add(BcSlab * s,const char * str,size_t len)452 static char* bc_slab_add(BcSlab *s, const char *str, size_t len) {
453
454 char *ptr;
455
456 assert(s != NULL);
457 assert(str != NULL);
458 assert(len == strlen(str) + 1);
459
460 if (s->len + len > BC_SLAB_SIZE) return NULL;
461
462 ptr = (char*) (s->s + s->len);
463
464 bc_strcpy(ptr, len, str);
465
466 s->len += len;
467
468 return ptr;
469 }
470
bc_slab_free(void * slab)471 void bc_slab_free(void *slab) {
472 free(((BcSlab*) slab)->s);
473 }
474
bc_slabvec_init(BcVec * v)475 void bc_slabvec_init(BcVec* v) {
476
477 BcSlab *slab;
478
479 assert(v != NULL);
480
481 bc_vec_init(v, sizeof(BcSlab), BC_DTOR_SLAB);
482
483 // We always want to have at least one slab.
484 slab = bc_vec_pushEmpty(v);
485 bc_slab_init(slab);
486 }
487
bc_slabvec_strdup(BcVec * v,const char * str)488 char* bc_slabvec_strdup(BcVec *v, const char *str) {
489
490 char *s;
491 size_t len;
492 BcSlab slab;
493 BcSlab *slab_ptr;
494
495 BC_SIG_ASSERT_LOCKED;
496
497 assert(v != NULL && v->len);
498
499 assert(str != NULL);
500
501 len = strlen(str) + 1;
502
503 // If the len is greater than 128, then just allocate it with malloc.
504 if (BC_UNLIKELY(len >= BC_SLAB_SIZE)) {
505
506 // SIZE_MAX is a marker for these standalone allocations.
507 slab.len = SIZE_MAX;
508 slab.s = bc_vm_strdup(str);
509
510 // Push the standalone slab.
511 bc_vec_pushAt(v, &slab, v->len - 1);
512
513 return slab.s;
514 }
515
516 // Add to a slab.
517 slab_ptr = bc_vec_top(v);
518 s = bc_slab_add(slab_ptr, str, len);
519
520 // If it couldn't be added, add a slab and try again.
521 if (BC_UNLIKELY(s == NULL)) {
522
523 slab_ptr = bc_vec_pushEmpty(v);
524 bc_slab_init(slab_ptr);
525
526 s = bc_slab_add(slab_ptr, str, len);
527
528 assert(s != NULL);
529 }
530
531 return s;
532 }
533
bc_slabvec_clear(BcVec * v)534 void bc_slabvec_clear(BcVec *v) {
535
536 BcSlab *s;
537 bool again;
538
539 // This complicated loop exists because of standalone allocations over 128
540 // bytes.
541 do {
542
543 // Get the first slab.
544 s = bc_vec_item(v, 0);
545
546 // Either the slab must be valid (not standalone), or there must be
547 // another slab.
548 assert(s->len != SIZE_MAX || v->len > 1);
549
550 // Do we have to loop again? We do if it's a standalone allocation.
551 again = (s->len == SIZE_MAX);
552
553 // Pop the standalone allocation, not the one after it.
554 if (again) bc_vec_npopAt(v, 1, 0);
555
556 } while(again);
557
558 // If we get here, we know that the first slab is a valid slab. We want to
559 // pop all of the other slabs.
560 if (v->len > 1) bc_vec_npop(v, v->len - 1);
561
562 // Empty the first slab.
563 s->len = 0;
564 }
565 #endif // !BC_ENABLE_LIBRARY
566
567 #if BC_DEBUG_CODE
568
bc_slabvec_print(BcVec * v,const char * func)569 void bc_slabvec_print(BcVec *v, const char *func) {
570
571 size_t i;
572 BcSlab *s;
573
574 bc_file_printf(&vm.ferr, "%s\n", func);
575
576 for (i = 0; i < v->len; ++i) {
577 s = bc_vec_item(v, i);
578 bc_file_printf(&vm.ferr, "%zu { s = %zu, len = %zu }\n",
579 i, (uintptr_t) s->s, s->len);
580 }
581
582 bc_file_puts(&vm.ferr, bc_flush_none, "\n");
583 bc_file_flush(&vm.ferr, bc_flush_none);
584 }
585
586 #endif // BC_DEBUG_CODE
587