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 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
  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
  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
 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
 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
 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
 172 inline void bc_vec_push(BcVec *restrict v, const void *data) {
 173         bc_vec_npush(v, 1, data);
 174 }
 175
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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  */
 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
 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
 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
 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  */
 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  */
 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
 471 void bc_slab_free(void *slab) {
 472         free(((BcSlab*) slab)->s);
 473 }
 474
 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
 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
 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
 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