1252884aeSStefan Eßer /*
2252884aeSStefan Eßer * *****************************************************************************
3252884aeSStefan Eßer *
43aa99676SStefan Eßer * SPDX-License-Identifier: BSD-2-Clause
5252884aeSStefan Eßer *
6d101cdd6SStefan Eßer * Copyright (c) 2018-2023 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
bc_vec_grow(BcVec * restrict v,size_t n)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
bc_vec_init(BcVec * restrict v,size_t esize,BcDtorType dtor)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
bc_vec_expand(BcVec * restrict v,size_t req)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
bc_vec_npop(BcVec * restrict v,size_t n)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
bc_vec_npopAt(BcVec * restrict v,size_t n,size_t idx)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
bc_vec_npush(BcVec * restrict v,size_t n,const void * data)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
bc_vec_push(BcVec * restrict v,const void * data)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*
bc_vec_pushEmpty(BcVec * restrict v)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
bc_vec_pushByte(BcVec * restrict v,uchar data)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
bc_vec_pushIndex(BcVec * restrict v,size_t idx)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
bc_vec_pushAt(BcVec * restrict v,const void * data,size_t idx)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
bc_vec_string(BcVec * restrict v,size_t len,const char * restrict str)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
bc_vec_concat(BcVec * restrict v,const char * restrict str)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
bc_vec_empty(BcVec * restrict v)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
bc_vec_replaceAt(BcVec * restrict v,size_t idx,const void * data)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*
bc_vec_item(const BcVec * restrict v,size_t idx)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*
bc_vec_item_rev(const BcVec * restrict v,size_t idx)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
bc_vec_clear(BcVec * restrict v)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
bc_vec_free(void * vec)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
bc_map_find(const BcVec * restrict v,const char * name)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
bc_map_insert(BcVec * restrict v,const char * name,size_t idx,size_t * restrict i)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
bc_map_index(const BcVec * restrict v,const char * name)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*
bc_map_name(const BcVec * restrict v,size_t idx)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
bc_slab_init(BcSlab * s)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*
bc_slab_add(BcSlab * s,const char * str,size_t len)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
bc_slab_free(void * slab)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
bc_slabvec_init(BcVec * v)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*
bc_slabvec_strdup(BcVec * v,const char * str)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
bc_slabvec_clear(BcVec * v)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
bc_slabvec_print(BcVec * v,const char * func)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