contrib/bc/src/vector.c

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