1 /* 2 * ***************************************************************************** 3 * 4 * Copyright (c) 2018-2020 Gavin D. Howard and contributors. 5 * 6 * All rights reserved. 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 assert(v != NULL && n <= v->len); 90 91 if (v->dtor == NULL) v->len -= n; 92 else { 93 94 sig_atomic_t lock; 95 size_t len = v->len - n; 96 97 BC_SIG_TRYLOCK(lock); 98 99 while (v->len > len) v->dtor(v->v + (v->size * --v->len)); 100 101 BC_SIG_TRYUNLOCK(lock); 102 } 103 } 104 105 void bc_vec_npopAt(BcVec *restrict v, size_t n, size_t idx) { 106 107 char* ptr, *data; 108 109 assert(v != NULL); 110 assert(idx + n < v->len); 111 112 ptr = bc_vec_item(v, idx); 113 data = bc_vec_item(v, idx + n); 114 115 if (v->dtor != NULL) { 116 117 size_t i; 118 119 BC_SIG_LOCK; 120 121 for (i = 0; i < n; ++i) v->dtor(bc_vec_item(v, idx + i)); 122 123 BC_SIG_UNLOCK; 124 } 125 126 v->len -= n; 127 memmove(ptr, data, (v->len - idx) * v->size); 128 } 129 130 void bc_vec_npush(BcVec *restrict v, size_t n, const void *data) { 131 assert(v != NULL && data != NULL); 132 if (v->len + n > v->cap) bc_vec_grow(v, n); 133 memcpy(v->v + (v->size * v->len), data, v->size * n); 134 v->len += n; 135 } 136 137 inline void bc_vec_push(BcVec *restrict v, const void *data) { 138 bc_vec_npush(v, 1, data); 139 } 140 141 void bc_vec_pushByte(BcVec *restrict v, uchar data) { 142 assert(v != NULL && v->size == sizeof(uchar)); 143 if (v->len == v->cap) bc_vec_grow(v, 1); 144 v->v[v->len] = (char) data; 145 v->len += 1; 146 } 147 148 void bc_vec_pushIndex(BcVec *restrict v, size_t idx) { 149 150 uchar amt, nums[sizeof(size_t)]; 151 152 assert(v != NULL); 153 assert(v->size == sizeof(uchar)); 154 155 for (amt = 0; idx; ++amt) { 156 nums[amt] = (uchar) idx; 157 idx &= ((size_t) ~(UCHAR_MAX)); 158 idx >>= sizeof(uchar) * CHAR_BIT; 159 } 160 161 bc_vec_push(v, &amt); 162 bc_vec_npush(v, amt, nums); 163 } 164 165 static void bc_vec_pushAt(BcVec *restrict v, const void *data, size_t idx) { 166 167 assert(v != NULL && data != NULL && idx <= v->len); 168 169 if (idx == v->len) bc_vec_push(v, data); 170 else { 171 172 char *ptr; 173 174 if (v->len == v->cap) bc_vec_grow(v, 1); 175 176 ptr = v->v + v->size * idx; 177 178 memmove(ptr + v->size, ptr, v->size * (v->len++ - idx)); 179 memmove(ptr, data, v->size); 180 } 181 } 182 183 void bc_vec_string(BcVec *restrict v, size_t len, const char *restrict str) { 184 185 assert(v != NULL && v->size == sizeof(char)); 186 assert(v->dtor == NULL); 187 assert(!v->len || !v->v[v->len - 1]); 188 assert(v->v != str); 189 190 bc_vec_npop(v, v->len); 191 bc_vec_expand(v, bc_vm_growSize(len, 1)); 192 memcpy(v->v, str, len); 193 v->len = len; 194 195 bc_vec_pushByte(v, '\0'); 196 } 197 198 void bc_vec_concat(BcVec *restrict v, const char *restrict str) { 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 if (v->len) v->len -= 1; 206 207 bc_vec_npush(v, strlen(str) + 1, str); 208 } 209 210 void bc_vec_empty(BcVec *restrict v) { 211 assert(v != NULL && v->size == sizeof(char)); 212 assert(v->dtor == NULL); 213 bc_vec_npop(v, v->len); 214 bc_vec_pushByte(v, '\0'); 215 } 216 217 #if BC_ENABLE_HISTORY 218 void bc_vec_replaceAt(BcVec *restrict v, size_t idx, const void *data) { 219 220 char *ptr; 221 222 BC_SIG_ASSERT_LOCKED; 223 224 assert(v != NULL); 225 226 ptr = bc_vec_item(v, idx); 227 228 if (v->dtor != NULL) v->dtor(ptr); 229 230 memcpy(ptr, data, v->size); 231 } 232 #endif // BC_ENABLE_HISTORY 233 234 inline void* bc_vec_item(const BcVec *restrict v, size_t idx) { 235 assert(v != NULL && v->len && idx < v->len); 236 return v->v + v->size * idx; 237 } 238 239 inline void* bc_vec_item_rev(const BcVec *restrict v, size_t idx) { 240 assert(v != NULL && v->len && idx < v->len); 241 return v->v + v->size * (v->len - idx - 1); 242 } 243 244 inline void bc_vec_clear(BcVec *restrict v) { 245 v->v = NULL; 246 v->len = 0; 247 v->dtor = NULL; 248 } 249 250 void bc_vec_free(void *vec) { 251 BcVec *v = (BcVec*) vec; 252 BC_SIG_ASSERT_LOCKED; 253 bc_vec_npop(v, v->len); 254 free(v->v); 255 } 256 257 static size_t bc_map_find(const BcVec *restrict v, const char *name) { 258 259 size_t low = 0, high = v->len; 260 261 while (low < high) { 262 263 size_t mid = (low + high) / 2; 264 const BcId *id = bc_vec_item(v, mid); 265 int result = strcmp(name, id->name); 266 267 if (!result) return mid; 268 else if (result < 0) high = mid; 269 else low = mid + 1; 270 } 271 272 return low; 273 } 274 275 bool bc_map_insert(BcVec *restrict v, const char *name, 276 size_t idx, size_t *restrict i) 277 { 278 BcId id; 279 280 BC_SIG_ASSERT_LOCKED; 281 282 assert(v != NULL && name != NULL && i != NULL); 283 284 *i = bc_map_find(v, name); 285 286 assert(*i <= v->len); 287 288 if (*i != v->len && !strcmp(name, ((BcId*) bc_vec_item(v, *i))->name)) 289 return false; 290 291 id.name = bc_vm_strdup(name); 292 id.idx = idx; 293 294 bc_vec_pushAt(v, &id, *i); 295 296 return true; 297 } 298 299 size_t bc_map_index(const BcVec *restrict v, const char *name) { 300 301 size_t i; 302 303 assert(v != NULL && name != NULL); 304 305 i = bc_map_find(v, name); 306 307 if (i >= v->len) return BC_VEC_INVALID_IDX; 308 309 return strcmp(name, ((BcId*) bc_vec_item(v, i))->name) ? 310 BC_VEC_INVALID_IDX : i; 311 } 312