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