1 /* 2 * ***************************************************************************** 3 * 4 * SPDX-License-Identifier: BSD-2-Clause 5 * 6 * Copyright (c) 2018-2020 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 40 #include <vector.h> 41 #include <lang.h> 42 #include <vm.h> 43 44 void bc_vec_grow(BcVec *restrict v, size_t n) { 45 46 size_t len, cap = v->cap; 47 sig_atomic_t lock; 48 49 len = bc_vm_growSize(v->len, n); 50 51 while (cap < len) cap = bc_vm_growSize(cap, cap); 52 53 BC_SIG_TRYLOCK(lock); 54 v->v = bc_vm_realloc(v->v, bc_vm_arraySize(cap, v->size)); 55 v->cap = cap; 56 BC_SIG_TRYUNLOCK(lock); 57 } 58 59 void bc_vec_init(BcVec *restrict v, size_t esize, BcVecFree dtor) { 60 BC_SIG_ASSERT_LOCKED; 61 assert(v != NULL && esize); 62 v->size = esize; 63 v->cap = BC_VEC_START_CAP; 64 v->len = 0; 65 v->dtor = dtor; 66 v->v = bc_vm_malloc(bc_vm_arraySize(BC_VEC_START_CAP, esize)); 67 } 68 69 void bc_vec_expand(BcVec *restrict v, size_t req) { 70 71 assert(v != NULL); 72 73 if (v->cap < req) { 74 75 sig_atomic_t lock; 76 77 BC_SIG_TRYLOCK(lock); 78 79 v->v = bc_vm_realloc(v->v, bc_vm_arraySize(req, v->size)); 80 v->cap = req; 81 82 BC_SIG_TRYUNLOCK(lock); 83 } 84 } 85 86 void bc_vec_npop(BcVec *restrict v, size_t n) { 87 88 sig_atomic_t lock; 89 90 assert(v != NULL && n <= v->len); 91 92 BC_SIG_TRYLOCK(lock); 93 94 if (v->dtor == NULL) v->len -= n; 95 else { 96 size_t len = v->len - n; 97 while (v->len > len) v->dtor(v->v + (v->size * --v->len)); 98 } 99 100 BC_SIG_TRYUNLOCK(lock); 101 } 102 103 void bc_vec_npopAt(BcVec *restrict v, size_t n, size_t idx) { 104 105 char* ptr, *data; 106 107 assert(v != NULL); 108 assert(idx + n < v->len); 109 110 ptr = bc_vec_item(v, idx); 111 data = bc_vec_item(v, idx + n); 112 113 BC_SIG_LOCK; 114 115 if (v->dtor != NULL) { 116 117 size_t i; 118 119 for (i = 0; i < n; ++i) v->dtor(bc_vec_item(v, idx + i)); 120 } 121 122 v->len -= n; 123 memmove(ptr, data, (v->len - idx) * v->size); 124 125 BC_SIG_UNLOCK; 126 } 127 128 void bc_vec_npush(BcVec *restrict v, size_t n, const void *data) { 129 130 sig_atomic_t lock; 131 132 assert(v != NULL && data != NULL); 133 134 BC_SIG_TRYLOCK(lock); 135 136 if (v->len + n > v->cap) bc_vec_grow(v, n); 137 138 memcpy(v->v + (v->size * v->len), data, v->size * n); 139 v->len += n; 140 141 BC_SIG_TRYUNLOCK(lock); 142 } 143 144 inline void bc_vec_push(BcVec *restrict v, const void *data) { 145 bc_vec_npush(v, 1, data); 146 } 147 148 void bc_vec_pushByte(BcVec *restrict v, uchar data) { 149 assert(v != NULL && v->size == sizeof(uchar)); 150 bc_vec_npush(v, 1, &data); 151 } 152 153 void bc_vec_pushIndex(BcVec *restrict v, size_t idx) { 154 155 uchar amt, nums[sizeof(size_t) + 1]; 156 157 assert(v != NULL); 158 assert(v->size == sizeof(uchar)); 159 160 for (amt = 0; idx; ++amt) { 161 nums[amt + 1] = (uchar) idx; 162 idx &= ((size_t) ~(UCHAR_MAX)); 163 idx >>= sizeof(uchar) * CHAR_BIT; 164 } 165 166 nums[0] = amt; 167 168 bc_vec_npush(v, amt + 1, nums); 169 } 170 171 static void bc_vec_pushAt(BcVec *restrict v, const void *data, size_t idx) { 172 173 sig_atomic_t lock; 174 175 assert(v != NULL && data != NULL && idx <= v->len); 176 177 BC_SIG_TRYLOCK(lock); 178 179 if (idx == v->len) bc_vec_push(v, data); 180 else { 181 182 char *ptr; 183 184 if (v->len == v->cap) bc_vec_grow(v, 1); 185 186 ptr = v->v + v->size * idx; 187 188 memmove(ptr + v->size, ptr, v->size * (v->len++ - idx)); 189 memmove(ptr, data, v->size); 190 } 191 192 BC_SIG_TRYUNLOCK(lock); 193 } 194 195 void bc_vec_string(BcVec *restrict v, size_t len, const char *restrict str) { 196 197 sig_atomic_t lock; 198 199 assert(v != NULL && v->size == sizeof(char)); 200 assert(v->dtor == NULL); 201 assert(!v->len || !v->v[v->len - 1]); 202 assert(v->v != str); 203 204 BC_SIG_TRYLOCK(lock); 205 206 bc_vec_npop(v, v->len); 207 bc_vec_expand(v, bc_vm_growSize(len, 1)); 208 memcpy(v->v, str, len); 209 v->len = len; 210 211 bc_vec_pushByte(v, '\0'); 212 213 BC_SIG_TRYUNLOCK(lock); 214 } 215 216 void bc_vec_concat(BcVec *restrict v, const char *restrict str) { 217 218 sig_atomic_t lock; 219 220 assert(v != NULL && v->size == sizeof(char)); 221 assert(v->dtor == NULL); 222 assert(!v->len || !v->v[v->len - 1]); 223 assert(v->v != str); 224 225 BC_SIG_TRYLOCK(lock); 226 227 if (v->len) v->len -= 1; 228 229 bc_vec_npush(v, strlen(str) + 1, str); 230 231 BC_SIG_TRYUNLOCK(lock); 232 } 233 234 void bc_vec_empty(BcVec *restrict v) { 235 236 sig_atomic_t lock; 237 238 assert(v != NULL && v->size == sizeof(char)); 239 assert(v->dtor == NULL); 240 241 BC_SIG_TRYLOCK(lock); 242 243 bc_vec_npop(v, v->len); 244 bc_vec_pushByte(v, '\0'); 245 246 BC_SIG_TRYUNLOCK(lock); 247 } 248 249 #if BC_ENABLE_HISTORY 250 void bc_vec_replaceAt(BcVec *restrict v, size_t idx, const void *data) { 251 252 char *ptr; 253 254 BC_SIG_ASSERT_LOCKED; 255 256 assert(v != NULL); 257 258 ptr = bc_vec_item(v, idx); 259 260 if (v->dtor != NULL) v->dtor(ptr); 261 262 memcpy(ptr, data, v->size); 263 } 264 #endif // BC_ENABLE_HISTORY 265 266 inline void* bc_vec_item(const BcVec *restrict v, size_t idx) { 267 assert(v != NULL && v->len && idx < v->len); 268 return v->v + v->size * idx; 269 } 270 271 inline void* bc_vec_item_rev(const BcVec *restrict v, size_t idx) { 272 assert(v != NULL && v->len && idx < v->len); 273 return v->v + v->size * (v->len - idx - 1); 274 } 275 276 inline void bc_vec_clear(BcVec *restrict v) { 277 BC_SIG_ASSERT_LOCKED; 278 v->v = NULL; 279 v->len = 0; 280 v->dtor = NULL; 281 } 282 283 void bc_vec_free(void *vec) { 284 BcVec *v = (BcVec*) vec; 285 BC_SIG_ASSERT_LOCKED; 286 bc_vec_npop(v, v->len); 287 free(v->v); 288 } 289 290 static size_t bc_map_find(const BcVec *restrict v, const char *name) { 291 292 size_t low = 0, high = v->len; 293 294 while (low < high) { 295 296 size_t mid = (low + high) / 2; 297 const BcId *id = bc_vec_item(v, mid); 298 int result = strcmp(name, id->name); 299 300 if (!result) return mid; 301 else if (result < 0) high = mid; 302 else low = mid + 1; 303 } 304 305 return low; 306 } 307 308 bool bc_map_insert(BcVec *restrict v, const char *name, 309 size_t idx, size_t *restrict i) 310 { 311 BcId id; 312 313 BC_SIG_ASSERT_LOCKED; 314 315 assert(v != NULL && name != NULL && i != NULL); 316 317 *i = bc_map_find(v, name); 318 319 assert(*i <= v->len); 320 321 if (*i != v->len && !strcmp(name, ((BcId*) bc_vec_item(v, *i))->name)) 322 return false; 323 324 id.name = bc_vm_strdup(name); 325 id.idx = idx; 326 327 bc_vec_pushAt(v, &id, *i); 328 329 return true; 330 } 331 332 size_t bc_map_index(const BcVec *restrict v, const char *name) { 333 334 size_t i; 335 336 assert(v != NULL && name != NULL); 337 338 i = bc_map_find(v, name); 339 340 if (i >= v->len) return BC_VEC_INVALID_IDX; 341 342 return strcmp(name, ((BcId*) bc_vec_item(v, i))->name) ? 343 BC_VEC_INVALID_IDX : i; 344 } 345