1252884aeSStefan Eßer /* 2252884aeSStefan Eßer * ***************************************************************************** 3252884aeSStefan Eßer * 43aa99676SStefan Eßer * SPDX-License-Identifier: BSD-2-Clause 5252884aeSStefan Eßer * 6*a970610aSStefan Eßer * Copyright (c) 2018-2024 Gavin D. Howard and contributors. 7252884aeSStefan Eßer * 8252884aeSStefan Eßer * Redistribution and use in source and binary forms, with or without 9252884aeSStefan Eßer * modification, are permitted provided that the following conditions are met: 10252884aeSStefan Eßer * 11252884aeSStefan Eßer * * Redistributions of source code must retain the above copyright notice, this 12252884aeSStefan Eßer * list of conditions and the following disclaimer. 13252884aeSStefan Eßer * 14252884aeSStefan Eßer * * Redistributions in binary form must reproduce the above copyright notice, 15252884aeSStefan Eßer * this list of conditions and the following disclaimer in the documentation 16252884aeSStefan Eßer * and/or other materials provided with the distribution. 17252884aeSStefan Eßer * 18252884aeSStefan Eßer * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 19252884aeSStefan Eßer * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20252884aeSStefan Eßer * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21252884aeSStefan Eßer * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 22252884aeSStefan Eßer * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23252884aeSStefan Eßer * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 24252884aeSStefan Eßer * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 25252884aeSStefan Eßer * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 26252884aeSStefan Eßer * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 27252884aeSStefan Eßer * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 28252884aeSStefan Eßer * POSSIBILITY OF SUCH DAMAGE. 29252884aeSStefan Eßer * 30252884aeSStefan Eßer * ***************************************************************************** 31252884aeSStefan Eßer * 32252884aeSStefan Eßer * Code to manipulate vectors (resizable arrays). 33252884aeSStefan Eßer * 34252884aeSStefan Eßer */ 35252884aeSStefan Eßer 36252884aeSStefan Eßer #include <assert.h> 37252884aeSStefan Eßer #include <stdlib.h> 38252884aeSStefan Eßer #include <string.h> 3944d4804dSStefan Eßer #include <stdbool.h> 40252884aeSStefan Eßer 41252884aeSStefan Eßer #include <vector.h> 42252884aeSStefan Eßer #include <lang.h> 43252884aeSStefan Eßer #include <vm.h> 44252884aeSStefan Eßer 4578bc019dSStefan Eßer void 4678bc019dSStefan Eßer bc_vec_grow(BcVec* restrict v, size_t n) 4778bc019dSStefan Eßer { 4844d4804dSStefan Eßer size_t cap, len; 49d101cdd6SStefan Eßer #if !BC_ENABLE_LIBRARY 50252884aeSStefan Eßer sig_atomic_t lock; 51d101cdd6SStefan Eßer #endif // !BC_ENABLE_LIBRARY 52252884aeSStefan Eßer 5344d4804dSStefan Eßer cap = v->cap; 5444d4804dSStefan Eßer len = v->len + n; 55252884aeSStefan Eßer 5644d4804dSStefan Eßer // If this is true, we might overflow. 5744d4804dSStefan Eßer if (len > SIZE_MAX / 2) cap = len; 5878bc019dSStefan Eßer else 5978bc019dSStefan Eßer { 6044d4804dSStefan Eßer // Keep doubling until larger. 6178bc019dSStefan Eßer while (cap < len) 6278bc019dSStefan Eßer { 6378bc019dSStefan Eßer cap += cap; 6478bc019dSStefan Eßer } 6544d4804dSStefan Eßer } 66252884aeSStefan Eßer 67252884aeSStefan Eßer BC_SIG_TRYLOCK(lock); 6844d4804dSStefan Eßer 69252884aeSStefan Eßer v->v = bc_vm_realloc(v->v, bc_vm_arraySize(cap, v->size)); 70252884aeSStefan Eßer v->cap = cap; 7144d4804dSStefan Eßer 72252884aeSStefan Eßer BC_SIG_TRYUNLOCK(lock); 73252884aeSStefan Eßer } 74252884aeSStefan Eßer 7578bc019dSStefan Eßer void 7678bc019dSStefan Eßer bc_vec_init(BcVec* restrict v, size_t esize, BcDtorType dtor) 7778bc019dSStefan Eßer { 78252884aeSStefan Eßer BC_SIG_ASSERT_LOCKED; 7944d4804dSStefan Eßer 80252884aeSStefan Eßer assert(v != NULL && esize); 8144d4804dSStefan Eßer 8244d4804dSStefan Eßer v->v = bc_vm_malloc(bc_vm_arraySize(BC_VEC_START_CAP, esize)); 8344d4804dSStefan Eßer 8444d4804dSStefan Eßer v->size = (BcSize) esize; 85252884aeSStefan Eßer v->cap = BC_VEC_START_CAP; 86252884aeSStefan Eßer v->len = 0; 8744d4804dSStefan Eßer v->dtor = (BcSize) dtor; 88252884aeSStefan Eßer } 89252884aeSStefan Eßer 9078bc019dSStefan Eßer void 9178bc019dSStefan Eßer bc_vec_expand(BcVec* restrict v, size_t req) 9278bc019dSStefan Eßer { 93252884aeSStefan Eßer assert(v != NULL); 94252884aeSStefan Eßer 9544d4804dSStefan Eßer // Only expand if necessary. 9678bc019dSStefan Eßer if (v->cap < req) 9778bc019dSStefan Eßer { 98d101cdd6SStefan Eßer #if !BC_ENABLE_LIBRARY 99252884aeSStefan Eßer sig_atomic_t lock; 100d101cdd6SStefan Eßer #endif // !BC_ENABLE_LIBRARY 101252884aeSStefan Eßer 102252884aeSStefan Eßer BC_SIG_TRYLOCK(lock); 103252884aeSStefan Eßer 104252884aeSStefan Eßer v->v = bc_vm_realloc(v->v, bc_vm_arraySize(req, v->size)); 105252884aeSStefan Eßer v->cap = req; 106252884aeSStefan Eßer 107252884aeSStefan Eßer BC_SIG_TRYUNLOCK(lock); 108252884aeSStefan Eßer } 109252884aeSStefan Eßer } 110252884aeSStefan Eßer 11178bc019dSStefan Eßer void 11278bc019dSStefan Eßer bc_vec_npop(BcVec* restrict v, size_t n) 11378bc019dSStefan Eßer { 114d101cdd6SStefan Eßer #if !BC_ENABLE_LIBRARY 115252884aeSStefan Eßer sig_atomic_t lock; 116d101cdd6SStefan Eßer #endif // !BC_ENABLE_LIBRARY 1173aa99676SStefan Eßer 1183aa99676SStefan Eßer assert(v != NULL && n <= v->len); 119252884aeSStefan Eßer 120252884aeSStefan Eßer BC_SIG_TRYLOCK(lock); 121252884aeSStefan Eßer 12244d4804dSStefan Eßer if (!v->dtor) v->len -= n; 12378bc019dSStefan Eßer else 12478bc019dSStefan Eßer { 12544d4804dSStefan Eßer const BcVecFree d = bc_vec_dtors[v->dtor]; 12644d4804dSStefan Eßer size_t esize = v->size; 1273aa99676SStefan Eßer size_t len = v->len - n; 12844d4804dSStefan Eßer 12944d4804dSStefan Eßer // Loop through and manually destruct every element. 13078bc019dSStefan Eßer while (v->len > len) 13178bc019dSStefan Eßer { 13278bc019dSStefan Eßer d(v->v + (esize * --v->len)); 13378bc019dSStefan Eßer } 1343aa99676SStefan Eßer } 135252884aeSStefan Eßer 136252884aeSStefan Eßer BC_SIG_TRYUNLOCK(lock); 137252884aeSStefan Eßer } 138252884aeSStefan Eßer 13978bc019dSStefan Eßer void 14078bc019dSStefan Eßer bc_vec_npopAt(BcVec* restrict v, size_t n, size_t idx) 14178bc019dSStefan Eßer { 14278bc019dSStefan Eßer char* ptr; 14378bc019dSStefan Eßer char* data; 144d101cdd6SStefan Eßer #if !BC_ENABLE_LIBRARY 14544d4804dSStefan Eßer sig_atomic_t lock; 146d101cdd6SStefan Eßer #endif // !BC_ENABLE_LIBRARY 147252884aeSStefan Eßer 148252884aeSStefan Eßer assert(v != NULL); 149252884aeSStefan Eßer assert(idx + n < v->len); 150252884aeSStefan Eßer 15144d4804dSStefan Eßer // Grab start and end pointers. 152252884aeSStefan Eßer ptr = bc_vec_item(v, idx); 153252884aeSStefan Eßer data = bc_vec_item(v, idx + n); 154252884aeSStefan Eßer 15544d4804dSStefan Eßer BC_SIG_TRYLOCK(lock); 1563aa99676SStefan Eßer 15778bc019dSStefan Eßer if (v->dtor) 15878bc019dSStefan Eßer { 159252884aeSStefan Eßer size_t i; 16044d4804dSStefan Eßer const BcVecFree d = bc_vec_dtors[v->dtor]; 161252884aeSStefan Eßer 16244d4804dSStefan Eßer // Destroy every popped item. 16378bc019dSStefan Eßer for (i = 0; i < n; ++i) 16478bc019dSStefan Eßer { 16578bc019dSStefan Eßer d(bc_vec_item(v, idx + i)); 16678bc019dSStefan Eßer } 167252884aeSStefan Eßer } 168252884aeSStefan Eßer 169252884aeSStefan Eßer v->len -= n; 17078bc019dSStefan Eßer // NOLINTNEXTLINE 171252884aeSStefan Eßer memmove(ptr, data, (v->len - idx) * v->size); 1723aa99676SStefan Eßer 17344d4804dSStefan Eßer BC_SIG_TRYUNLOCK(lock); 174252884aeSStefan Eßer } 175252884aeSStefan Eßer 17678bc019dSStefan Eßer void 17778bc019dSStefan Eßer bc_vec_npush(BcVec* restrict v, size_t n, const void* data) 17878bc019dSStefan Eßer { 179d101cdd6SStefan Eßer #if !BC_ENABLE_LIBRARY 1803aa99676SStefan Eßer sig_atomic_t lock; 181d101cdd6SStefan Eßer #endif // !BC_ENABLE_LIBRARY 18244d4804dSStefan Eßer size_t esize; 1833aa99676SStefan Eßer 184252884aeSStefan Eßer assert(v != NULL && data != NULL); 1853aa99676SStefan Eßer 1863aa99676SStefan Eßer BC_SIG_TRYLOCK(lock); 1873aa99676SStefan Eßer 18844d4804dSStefan Eßer // Grow if necessary. 189252884aeSStefan Eßer if (v->len + n > v->cap) bc_vec_grow(v, n); 1903aa99676SStefan Eßer 19144d4804dSStefan Eßer esize = v->size; 19244d4804dSStefan Eßer 19344d4804dSStefan Eßer // Copy the elements in. 19478bc019dSStefan Eßer // NOLINTNEXTLINE 19544d4804dSStefan Eßer memcpy(v->v + (esize * v->len), data, esize * n); 196252884aeSStefan Eßer v->len += n; 1973aa99676SStefan Eßer 1983aa99676SStefan Eßer BC_SIG_TRYUNLOCK(lock); 199252884aeSStefan Eßer } 200252884aeSStefan Eßer 20178bc019dSStefan Eßer inline void 20278bc019dSStefan Eßer bc_vec_push(BcVec* restrict v, const void* data) 20378bc019dSStefan Eßer { 204252884aeSStefan Eßer bc_vec_npush(v, 1, data); 205252884aeSStefan Eßer } 206252884aeSStefan Eßer 20778bc019dSStefan Eßer void* 20878bc019dSStefan Eßer bc_vec_pushEmpty(BcVec* restrict v) 20978bc019dSStefan Eßer { 210d101cdd6SStefan Eßer #if !BC_ENABLE_LIBRARY 21144d4804dSStefan Eßer sig_atomic_t lock; 212d101cdd6SStefan Eßer #endif // !BC_ENABLE_LIBRARY 21344d4804dSStefan Eßer void* ptr; 21444d4804dSStefan Eßer 21544d4804dSStefan Eßer assert(v != NULL); 21644d4804dSStefan Eßer 21744d4804dSStefan Eßer BC_SIG_TRYLOCK(lock); 21844d4804dSStefan Eßer 21944d4804dSStefan Eßer // Grow if necessary. 22044d4804dSStefan Eßer if (v->len + 1 > v->cap) bc_vec_grow(v, 1); 22144d4804dSStefan Eßer 22244d4804dSStefan Eßer ptr = v->v + v->size * v->len; 22344d4804dSStefan Eßer v->len += 1; 22444d4804dSStefan Eßer 22544d4804dSStefan Eßer BC_SIG_TRYUNLOCK(lock); 22644d4804dSStefan Eßer 22744d4804dSStefan Eßer return ptr; 22844d4804dSStefan Eßer } 22944d4804dSStefan Eßer 23078bc019dSStefan Eßer inline void 23178bc019dSStefan Eßer bc_vec_pushByte(BcVec* restrict v, uchar data) 23278bc019dSStefan Eßer { 233252884aeSStefan Eßer assert(v != NULL && v->size == sizeof(uchar)); 2343aa99676SStefan Eßer bc_vec_npush(v, 1, &data); 235252884aeSStefan Eßer } 236252884aeSStefan Eßer 23778bc019dSStefan Eßer void 23878bc019dSStefan Eßer bc_vec_pushIndex(BcVec* restrict v, size_t idx) 23978bc019dSStefan Eßer { 2403aa99676SStefan Eßer uchar amt, nums[sizeof(size_t) + 1]; 241252884aeSStefan Eßer 242252884aeSStefan Eßer assert(v != NULL); 243252884aeSStefan Eßer assert(v->size == sizeof(uchar)); 244252884aeSStefan Eßer 24544d4804dSStefan Eßer // Encode the index. 24678bc019dSStefan Eßer for (amt = 0; idx; ++amt) 24778bc019dSStefan Eßer { 2483aa99676SStefan Eßer nums[amt + 1] = (uchar) idx; 249252884aeSStefan Eßer idx &= ((size_t) ~(UCHAR_MAX)); 250252884aeSStefan Eßer idx >>= sizeof(uchar) * CHAR_BIT; 251252884aeSStefan Eßer } 252252884aeSStefan Eßer 2533aa99676SStefan Eßer nums[0] = amt; 2543aa99676SStefan Eßer 25544d4804dSStefan Eßer // Push the index onto the vector. 2563aa99676SStefan Eßer bc_vec_npush(v, amt + 1, nums); 257252884aeSStefan Eßer } 258252884aeSStefan Eßer 25978bc019dSStefan Eßer void 26078bc019dSStefan Eßer bc_vec_pushAt(BcVec* restrict v, const void* data, size_t idx) 26178bc019dSStefan Eßer { 262252884aeSStefan Eßer assert(v != NULL && data != NULL && idx <= v->len); 263252884aeSStefan Eßer 26444d4804dSStefan Eßer BC_SIG_ASSERT_LOCKED; 2653aa99676SStefan Eßer 26644d4804dSStefan Eßer // Do the easy case. 267252884aeSStefan Eßer if (idx == v->len) bc_vec_push(v, data); 26878bc019dSStefan Eßer else 26978bc019dSStefan Eßer { 270252884aeSStefan Eßer char* ptr; 27144d4804dSStefan Eßer size_t esize; 272252884aeSStefan Eßer 27344d4804dSStefan Eßer // Grow if necessary. 274252884aeSStefan Eßer if (v->len == v->cap) bc_vec_grow(v, 1); 275252884aeSStefan Eßer 27644d4804dSStefan Eßer esize = v->size; 277252884aeSStefan Eßer 27844d4804dSStefan Eßer ptr = v->v + esize * idx; 27944d4804dSStefan Eßer 28078bc019dSStefan Eßer // NOLINTNEXTLINE 28144d4804dSStefan Eßer memmove(ptr + esize, ptr, esize * (v->len++ - idx)); 28278bc019dSStefan Eßer // NOLINTNEXTLINE 28344d4804dSStefan Eßer memcpy(ptr, data, esize); 284252884aeSStefan Eßer } 285252884aeSStefan Eßer } 286252884aeSStefan Eßer 28778bc019dSStefan Eßer void 28878bc019dSStefan Eßer bc_vec_string(BcVec* restrict v, size_t len, const char* restrict str) 28978bc019dSStefan Eßer { 290d101cdd6SStefan Eßer #if !BC_ENABLE_LIBRARY 2913aa99676SStefan Eßer sig_atomic_t lock; 292d101cdd6SStefan Eßer #endif // !BC_ENABLE_LIBRARY 2933aa99676SStefan Eßer 294252884aeSStefan Eßer assert(v != NULL && v->size == sizeof(char)); 29544d4804dSStefan Eßer assert(!v->dtor); 296252884aeSStefan Eßer assert(!v->len || !v->v[v->len - 1]); 297252884aeSStefan Eßer assert(v->v != str); 298252884aeSStefan Eßer 2993aa99676SStefan Eßer BC_SIG_TRYLOCK(lock); 3003aa99676SStefan Eßer 30110328f8bSStefan Eßer bc_vec_popAll(v); 302252884aeSStefan Eßer bc_vec_expand(v, bc_vm_growSize(len, 1)); 30378bc019dSStefan Eßer // NOLINTNEXTLINE 304252884aeSStefan Eßer memcpy(v->v, str, len); 305252884aeSStefan Eßer v->len = len; 306252884aeSStefan Eßer 307252884aeSStefan Eßer bc_vec_pushByte(v, '\0'); 3083aa99676SStefan Eßer 3093aa99676SStefan Eßer BC_SIG_TRYUNLOCK(lock); 310252884aeSStefan Eßer } 311252884aeSStefan Eßer 31278bc019dSStefan Eßer void 31378bc019dSStefan Eßer bc_vec_concat(BcVec* restrict v, const char* restrict str) 31478bc019dSStefan Eßer { 315d101cdd6SStefan Eßer #if !BC_ENABLE_LIBRARY 3163aa99676SStefan Eßer sig_atomic_t lock; 317d101cdd6SStefan Eßer #endif // !BC_ENABLE_LIBRARY 3183aa99676SStefan Eßer 319252884aeSStefan Eßer assert(v != NULL && v->size == sizeof(char)); 32044d4804dSStefan Eßer assert(!v->dtor); 321252884aeSStefan Eßer assert(!v->len || !v->v[v->len - 1]); 322252884aeSStefan Eßer assert(v->v != str); 323252884aeSStefan Eßer 3243aa99676SStefan Eßer BC_SIG_TRYLOCK(lock); 3253aa99676SStefan Eßer 32644d4804dSStefan Eßer // If there is already a string, erase its nul byte. 327252884aeSStefan Eßer if (v->len) v->len -= 1; 328252884aeSStefan Eßer 329252884aeSStefan Eßer bc_vec_npush(v, strlen(str) + 1, str); 3303aa99676SStefan Eßer 3313aa99676SStefan Eßer BC_SIG_TRYUNLOCK(lock); 332252884aeSStefan Eßer } 333252884aeSStefan Eßer 33478bc019dSStefan Eßer void 33578bc019dSStefan Eßer bc_vec_empty(BcVec* restrict v) 33678bc019dSStefan Eßer { 337d101cdd6SStefan Eßer #if !BC_ENABLE_LIBRARY 3383aa99676SStefan Eßer sig_atomic_t lock; 339d101cdd6SStefan Eßer #endif // !BC_ENABLE_LIBRARY 3403aa99676SStefan Eßer 341252884aeSStefan Eßer assert(v != NULL && v->size == sizeof(char)); 34244d4804dSStefan Eßer assert(!v->dtor); 3433aa99676SStefan Eßer 3443aa99676SStefan Eßer BC_SIG_TRYLOCK(lock); 3453aa99676SStefan Eßer 34610328f8bSStefan Eßer bc_vec_popAll(v); 347252884aeSStefan Eßer bc_vec_pushByte(v, '\0'); 3483aa99676SStefan Eßer 3493aa99676SStefan Eßer BC_SIG_TRYUNLOCK(lock); 350252884aeSStefan Eßer } 351252884aeSStefan Eßer 352252884aeSStefan Eßer #if BC_ENABLE_HISTORY 35378bc019dSStefan Eßer void 35478bc019dSStefan Eßer bc_vec_replaceAt(BcVec* restrict v, size_t idx, const void* data) 35578bc019dSStefan Eßer { 356252884aeSStefan Eßer char* ptr; 357252884aeSStefan Eßer 358252884aeSStefan Eßer BC_SIG_ASSERT_LOCKED; 359252884aeSStefan Eßer 360252884aeSStefan Eßer assert(v != NULL); 361252884aeSStefan Eßer 362252884aeSStefan Eßer ptr = bc_vec_item(v, idx); 363252884aeSStefan Eßer 36444d4804dSStefan Eßer if (v->dtor) bc_vec_dtors[v->dtor](ptr); 365252884aeSStefan Eßer 36678bc019dSStefan Eßer // NOLINTNEXTLINE 367252884aeSStefan Eßer memcpy(ptr, data, v->size); 368252884aeSStefan Eßer } 369252884aeSStefan Eßer #endif // BC_ENABLE_HISTORY 370252884aeSStefan Eßer 37178bc019dSStefan Eßer inline void* 37278bc019dSStefan Eßer bc_vec_item(const BcVec* restrict v, size_t idx) 37378bc019dSStefan Eßer { 374252884aeSStefan Eßer assert(v != NULL && v->len && idx < v->len); 375252884aeSStefan Eßer return v->v + v->size * idx; 376252884aeSStefan Eßer } 377252884aeSStefan Eßer 37878bc019dSStefan Eßer inline void* 37978bc019dSStefan Eßer bc_vec_item_rev(const BcVec* restrict v, size_t idx) 38078bc019dSStefan Eßer { 381252884aeSStefan Eßer assert(v != NULL && v->len && idx < v->len); 382252884aeSStefan Eßer return v->v + v->size * (v->len - idx - 1); 383252884aeSStefan Eßer } 384252884aeSStefan Eßer 38578bc019dSStefan Eßer inline void 38678bc019dSStefan Eßer bc_vec_clear(BcVec* restrict v) 38778bc019dSStefan Eßer { 3883aa99676SStefan Eßer BC_SIG_ASSERT_LOCKED; 389252884aeSStefan Eßer v->v = NULL; 390252884aeSStefan Eßer v->len = 0; 39144d4804dSStefan Eßer v->dtor = BC_DTOR_NONE; 392252884aeSStefan Eßer } 393252884aeSStefan Eßer 39478bc019dSStefan Eßer void 39578bc019dSStefan Eßer bc_vec_free(void* vec) 39678bc019dSStefan Eßer { 397252884aeSStefan Eßer BcVec* v = (BcVec*) vec; 398252884aeSStefan Eßer BC_SIG_ASSERT_LOCKED; 39910328f8bSStefan Eßer bc_vec_popAll(v); 400252884aeSStefan Eßer free(v->v); 401252884aeSStefan Eßer } 402252884aeSStefan Eßer 40344d4804dSStefan Eßer #if !BC_ENABLE_LIBRARY 40444d4804dSStefan Eßer 40544d4804dSStefan Eßer /** 40644d4804dSStefan Eßer * Finds a name in a map by binary search. Returns the index where the item 40744d4804dSStefan Eßer * *would* be if it doesn't exist. Callers are responsible for checking that the 40844d4804dSStefan Eßer * item exists at the index. 40944d4804dSStefan Eßer * @param v The map. 41044d4804dSStefan Eßer * @param name The name to find. 41144d4804dSStefan Eßer * @return The index of the item with @a name, or where the item would be 41244d4804dSStefan Eßer * if it does not exist. 41344d4804dSStefan Eßer */ 41478bc019dSStefan Eßer static size_t 41578bc019dSStefan Eßer bc_map_find(const BcVec* restrict v, const char* name) 41678bc019dSStefan Eßer { 417252884aeSStefan Eßer size_t low = 0, high = v->len; 418252884aeSStefan Eßer 41978bc019dSStefan Eßer while (low < high) 42078bc019dSStefan Eßer { 421d101cdd6SStefan Eßer size_t mid = low + (high - low) / 2; 422252884aeSStefan Eßer const BcId* id = bc_vec_item(v, mid); 423252884aeSStefan Eßer int result = strcmp(name, id->name); 424252884aeSStefan Eßer 425252884aeSStefan Eßer if (!result) return mid; 426252884aeSStefan Eßer else if (result < 0) high = mid; 427252884aeSStefan Eßer else low = mid + 1; 428252884aeSStefan Eßer } 429252884aeSStefan Eßer 430252884aeSStefan Eßer return low; 431252884aeSStefan Eßer } 432252884aeSStefan Eßer 43378bc019dSStefan Eßer bool 43478bc019dSStefan Eßer bc_map_insert(BcVec* restrict v, const char* name, size_t idx, 43578bc019dSStefan Eßer size_t* restrict i) 436252884aeSStefan Eßer { 437252884aeSStefan Eßer BcId id; 438252884aeSStefan Eßer 439252884aeSStefan Eßer BC_SIG_ASSERT_LOCKED; 440252884aeSStefan Eßer 441252884aeSStefan Eßer assert(v != NULL && name != NULL && i != NULL); 442252884aeSStefan Eßer 443252884aeSStefan Eßer *i = bc_map_find(v, name); 444252884aeSStefan Eßer 445252884aeSStefan Eßer assert(*i <= v->len); 446252884aeSStefan Eßer 447252884aeSStefan Eßer if (*i != v->len && !strcmp(name, ((BcId*) bc_vec_item(v, *i))->name)) 44878bc019dSStefan Eßer { 449252884aeSStefan Eßer return false; 45078bc019dSStefan Eßer } 451252884aeSStefan Eßer 452d101cdd6SStefan Eßer id.name = bc_slabvec_strdup(&vm->slabs, name); 453252884aeSStefan Eßer id.idx = idx; 454252884aeSStefan Eßer 455252884aeSStefan Eßer bc_vec_pushAt(v, &id, *i); 456252884aeSStefan Eßer 457252884aeSStefan Eßer return true; 458252884aeSStefan Eßer } 459252884aeSStefan Eßer 46078bc019dSStefan Eßer size_t 46178bc019dSStefan Eßer bc_map_index(const BcVec* restrict v, const char* name) 46278bc019dSStefan Eßer { 463252884aeSStefan Eßer size_t i; 464d101cdd6SStefan Eßer BcId* id; 465252884aeSStefan Eßer 466252884aeSStefan Eßer assert(v != NULL && name != NULL); 467252884aeSStefan Eßer 468252884aeSStefan Eßer i = bc_map_find(v, name); 469252884aeSStefan Eßer 47044d4804dSStefan Eßer // If out of range, return invalid. 471252884aeSStefan Eßer if (i >= v->len) return BC_VEC_INVALID_IDX; 472252884aeSStefan Eßer 473d101cdd6SStefan Eßer id = (BcId*) bc_vec_item(v, i); 474d101cdd6SStefan Eßer 475d101cdd6SStefan Eßer // Make sure the item exists and return appropriately. 476d101cdd6SStefan Eßer return strcmp(name, id->name) ? BC_VEC_INVALID_IDX : i; 477252884aeSStefan Eßer } 47844d4804dSStefan Eßer 47944d4804dSStefan Eßer #if DC_ENABLED 48078bc019dSStefan Eßer const char* 48178bc019dSStefan Eßer bc_map_name(const BcVec* restrict v, size_t idx) 48278bc019dSStefan Eßer { 48344d4804dSStefan Eßer size_t i, len = v->len; 48444d4804dSStefan Eßer 48578bc019dSStefan Eßer for (i = 0; i < len; ++i) 48678bc019dSStefan Eßer { 48744d4804dSStefan Eßer BcId* id = (BcId*) bc_vec_item(v, i); 48844d4804dSStefan Eßer if (id->idx == idx) return id->name; 48944d4804dSStefan Eßer } 49044d4804dSStefan Eßer 49144d4804dSStefan Eßer BC_UNREACHABLE 49244d4804dSStefan Eßer 493d101cdd6SStefan Eßer #if !BC_CLANG 49444d4804dSStefan Eßer return ""; 495d101cdd6SStefan Eßer #endif // !BC_CLANG 49644d4804dSStefan Eßer } 49744d4804dSStefan Eßer #endif // DC_ENABLED 49844d4804dSStefan Eßer 49944d4804dSStefan Eßer /** 50044d4804dSStefan Eßer * Initializes a single slab. 50144d4804dSStefan Eßer * @param s The slab to initialize. 50244d4804dSStefan Eßer */ 50378bc019dSStefan Eßer static void 50478bc019dSStefan Eßer bc_slab_init(BcSlab* s) 50578bc019dSStefan Eßer { 50644d4804dSStefan Eßer s->s = bc_vm_malloc(BC_SLAB_SIZE); 50744d4804dSStefan Eßer s->len = 0; 50844d4804dSStefan Eßer } 50944d4804dSStefan Eßer 51044d4804dSStefan Eßer /** 51144d4804dSStefan Eßer * Adds a string to a slab and returns a pointer to it, or NULL if it could not 51244d4804dSStefan Eßer * be added. 51344d4804dSStefan Eßer * @param s The slab to add to. 51444d4804dSStefan Eßer * @param str The string to add. 51544d4804dSStefan Eßer * @param len The length of the string, including its nul byte. 51644d4804dSStefan Eßer * @return A pointer to the new string in the slab, or NULL if it could not 51744d4804dSStefan Eßer * be added. 51844d4804dSStefan Eßer */ 51978bc019dSStefan Eßer static char* 52078bc019dSStefan Eßer bc_slab_add(BcSlab* s, const char* str, size_t len) 52178bc019dSStefan Eßer { 52244d4804dSStefan Eßer char* ptr; 52344d4804dSStefan Eßer 52444d4804dSStefan Eßer assert(s != NULL); 52544d4804dSStefan Eßer assert(str != NULL); 52644d4804dSStefan Eßer assert(len == strlen(str) + 1); 52744d4804dSStefan Eßer 52844d4804dSStefan Eßer if (s->len + len > BC_SLAB_SIZE) return NULL; 52944d4804dSStefan Eßer 53044d4804dSStefan Eßer ptr = (char*) (s->s + s->len); 53144d4804dSStefan Eßer 53278bc019dSStefan Eßer // NOLINTNEXTLINE 533662087dfSStefan Eßer bc_strcpy(ptr, len, str); 53444d4804dSStefan Eßer 53544d4804dSStefan Eßer s->len += len; 53644d4804dSStefan Eßer 53744d4804dSStefan Eßer return ptr; 53844d4804dSStefan Eßer } 53944d4804dSStefan Eßer 54078bc019dSStefan Eßer void 54178bc019dSStefan Eßer bc_slab_free(void* slab) 54278bc019dSStefan Eßer { 54344d4804dSStefan Eßer free(((BcSlab*) slab)->s); 54444d4804dSStefan Eßer } 54544d4804dSStefan Eßer 54678bc019dSStefan Eßer void 54778bc019dSStefan Eßer bc_slabvec_init(BcVec* v) 54878bc019dSStefan Eßer { 54944d4804dSStefan Eßer BcSlab* slab; 55044d4804dSStefan Eßer 55144d4804dSStefan Eßer assert(v != NULL); 55244d4804dSStefan Eßer 55344d4804dSStefan Eßer bc_vec_init(v, sizeof(BcSlab), BC_DTOR_SLAB); 55444d4804dSStefan Eßer 55544d4804dSStefan Eßer // We always want to have at least one slab. 55644d4804dSStefan Eßer slab = bc_vec_pushEmpty(v); 55744d4804dSStefan Eßer bc_slab_init(slab); 55844d4804dSStefan Eßer } 55944d4804dSStefan Eßer 56078bc019dSStefan Eßer char* 56178bc019dSStefan Eßer bc_slabvec_strdup(BcVec* v, const char* str) 56278bc019dSStefan Eßer { 56344d4804dSStefan Eßer char* s; 56444d4804dSStefan Eßer size_t len; 56544d4804dSStefan Eßer BcSlab slab; 56644d4804dSStefan Eßer BcSlab* slab_ptr; 56744d4804dSStefan Eßer 56844d4804dSStefan Eßer BC_SIG_ASSERT_LOCKED; 56944d4804dSStefan Eßer 57044d4804dSStefan Eßer assert(v != NULL && v->len); 57144d4804dSStefan Eßer 57244d4804dSStefan Eßer assert(str != NULL); 57344d4804dSStefan Eßer 57444d4804dSStefan Eßer len = strlen(str) + 1; 57544d4804dSStefan Eßer 57644d4804dSStefan Eßer // If the len is greater than 128, then just allocate it with malloc. 57778bc019dSStefan Eßer if (BC_UNLIKELY(len >= BC_SLAB_SIZE)) 57878bc019dSStefan Eßer { 57944d4804dSStefan Eßer // SIZE_MAX is a marker for these standalone allocations. 58044d4804dSStefan Eßer slab.len = SIZE_MAX; 58144d4804dSStefan Eßer slab.s = bc_vm_strdup(str); 58244d4804dSStefan Eßer 58344d4804dSStefan Eßer // Push the standalone slab. 58444d4804dSStefan Eßer bc_vec_pushAt(v, &slab, v->len - 1); 58544d4804dSStefan Eßer 58644d4804dSStefan Eßer return slab.s; 58744d4804dSStefan Eßer } 58844d4804dSStefan Eßer 58944d4804dSStefan Eßer // Add to a slab. 59044d4804dSStefan Eßer slab_ptr = bc_vec_top(v); 59144d4804dSStefan Eßer s = bc_slab_add(slab_ptr, str, len); 59244d4804dSStefan Eßer 59344d4804dSStefan Eßer // If it couldn't be added, add a slab and try again. 59478bc019dSStefan Eßer if (BC_UNLIKELY(s == NULL)) 59578bc019dSStefan Eßer { 59644d4804dSStefan Eßer slab_ptr = bc_vec_pushEmpty(v); 59744d4804dSStefan Eßer bc_slab_init(slab_ptr); 59844d4804dSStefan Eßer 59944d4804dSStefan Eßer s = bc_slab_add(slab_ptr, str, len); 60044d4804dSStefan Eßer 60144d4804dSStefan Eßer assert(s != NULL); 60244d4804dSStefan Eßer } 60344d4804dSStefan Eßer 60444d4804dSStefan Eßer return s; 60544d4804dSStefan Eßer } 60644d4804dSStefan Eßer 60778bc019dSStefan Eßer void 60878bc019dSStefan Eßer bc_slabvec_clear(BcVec* v) 60978bc019dSStefan Eßer { 61044d4804dSStefan Eßer BcSlab* s; 61144d4804dSStefan Eßer bool again; 61244d4804dSStefan Eßer 61344d4804dSStefan Eßer // This complicated loop exists because of standalone allocations over 128 61444d4804dSStefan Eßer // bytes. 61578bc019dSStefan Eßer do 61678bc019dSStefan Eßer { 61744d4804dSStefan Eßer // Get the first slab. 61844d4804dSStefan Eßer s = bc_vec_item(v, 0); 61944d4804dSStefan Eßer 62044d4804dSStefan Eßer // Either the slab must be valid (not standalone), or there must be 62144d4804dSStefan Eßer // another slab. 62244d4804dSStefan Eßer assert(s->len != SIZE_MAX || v->len > 1); 62344d4804dSStefan Eßer 62444d4804dSStefan Eßer // Do we have to loop again? We do if it's a standalone allocation. 62544d4804dSStefan Eßer again = (s->len == SIZE_MAX); 62644d4804dSStefan Eßer 62744d4804dSStefan Eßer // Pop the standalone allocation, not the one after it. 62844d4804dSStefan Eßer if (again) bc_vec_npopAt(v, 1, 0); 62978bc019dSStefan Eßer } 63078bc019dSStefan Eßer while (again); 63144d4804dSStefan Eßer 63244d4804dSStefan Eßer // If we get here, we know that the first slab is a valid slab. We want to 63344d4804dSStefan Eßer // pop all of the other slabs. 63444d4804dSStefan Eßer if (v->len > 1) bc_vec_npop(v, v->len - 1); 63544d4804dSStefan Eßer 63644d4804dSStefan Eßer // Empty the first slab. 63744d4804dSStefan Eßer s->len = 0; 63844d4804dSStefan Eßer } 63944d4804dSStefan Eßer #endif // !BC_ENABLE_LIBRARY 64044d4804dSStefan Eßer 64144d4804dSStefan Eßer #if BC_DEBUG_CODE 64244d4804dSStefan Eßer 64378bc019dSStefan Eßer void 64478bc019dSStefan Eßer bc_slabvec_print(BcVec* v, const char* func) 64578bc019dSStefan Eßer { 64644d4804dSStefan Eßer size_t i; 64744d4804dSStefan Eßer BcSlab* s; 64844d4804dSStefan Eßer 649d101cdd6SStefan Eßer bc_file_printf(&vm->ferr, "%s\n", func); 65044d4804dSStefan Eßer 65178bc019dSStefan Eßer for (i = 0; i < v->len; ++i) 65278bc019dSStefan Eßer { 65344d4804dSStefan Eßer s = bc_vec_item(v, i); 654d101cdd6SStefan Eßer bc_file_printf(&vm->ferr, "%zu { s = %zu, len = %zu }\n", i, 65578bc019dSStefan Eßer (uintptr_t) s->s, s->len); 65644d4804dSStefan Eßer } 65744d4804dSStefan Eßer 658d101cdd6SStefan Eßer bc_file_puts(&vm->ferr, bc_flush_none, "\n"); 659d101cdd6SStefan Eßer bc_file_flush(&vm->ferr, bc_flush_none); 66044d4804dSStefan Eßer } 66144d4804dSStefan Eßer 66244d4804dSStefan Eßer #endif // BC_DEBUG_CODE 663