contrib/bc/src/vector.c

   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
  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