1 /* 2 * ***************************************************************************** 3 * 4 * SPDX-License-Identifier: BSD-2-Clause 5 * 6 * Copyright (c) 2018-2024 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 45 void 46 bc_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 75 void 76 bc_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 90 void 91 bc_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 111 void 112 bc_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 139 void 140 bc_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 176 void 177 bc_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 201 inline void 202 bc_vec_push(BcVec* restrict v, const void* data) 203 { 204 bc_vec_npush(v, 1, data); 205 } 206 207 void* 208 bc_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 230 inline void 231 bc_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 237 void 238 bc_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 259 void 260 bc_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 287 void 288 bc_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 312 void 313 bc_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 334 void 335 bc_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 353 void 354 bc_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 371 inline void* 372 bc_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 378 inline void* 379 bc_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 385 inline void 386 bc_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 394 void 395 bc_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 */ 414 static size_t 415 bc_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 433 bool 434 bc_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 460 size_t 461 bc_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 480 const char* 481 bc_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 */ 503 static void 504 bc_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 */ 519 static char* 520 bc_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 540 void 541 bc_slab_free(void* slab) 542 { 543 free(((BcSlab*) slab)->s); 544 } 545 546 void 547 bc_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 560 char* 561 bc_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 607 void 608 bc_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 643 void 644 bc_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