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