1 /* 2 * ***************************************************************************** 3 * 4 * SPDX-License-Identifier: BSD-2-Clause 5 * 6 * Copyright (c) 2018-2023 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 * Definitions for bc vectors (resizable arrays). 33 * 34 */ 35 36 #ifndef BC_VECTOR_H 37 #define BC_VECTOR_H 38 39 #include <stdbool.h> 40 #include <stddef.h> 41 #include <stdint.h> 42 43 #include <status.h> 44 45 /// An invalid index for a map to mark when an item does not exist. 46 #define BC_VEC_INVALID_IDX (SIZE_MAX) 47 48 /// The starting capacity for vectors. This is based on the minimum allocation 49 /// for 64-bit systems. 50 #define BC_VEC_START_CAP (UINTMAX_C(1) << 5) 51 52 /// An alias. 53 typedef unsigned char uchar; 54 55 /** 56 * A destructor. Frees the object that @a ptr points to. This is used by vectors 57 * to free the memory they own. 58 * @param ptr Pointer to the data to free. 59 */ 60 typedef void (*BcVecFree)(void* ptr); 61 62 #if BC_LONG_BIT >= 64 63 64 /// An integer to shrink the size of a vector by using these instead of size_t. 65 typedef uint32_t BcSize; 66 67 #else // BC_LONG_BIT >= 64 68 69 /// An integer to shrink the size of a vector by using these instead of size_t. 70 typedef uint16_t BcSize; 71 72 #endif // BC_LONG_BIT >= 64 73 74 /// An enum of all of the destructors. We use an enum to save space. 75 typedef enum BcDtorType 76 { 77 /// No destructor needed. 78 BC_DTOR_NONE, 79 80 /// Vector destructor. 81 BC_DTOR_VEC, 82 83 /// BcNum destructor. 84 BC_DTOR_NUM, 85 86 #if !BC_ENABLE_LIBRARY 87 88 #if BC_DEBUG 89 90 /// BcFunc destructor. 91 BC_DTOR_FUNC, 92 93 #endif // BC_DEBUG 94 95 /// BcSlab destructor. 96 BC_DTOR_SLAB, 97 98 /// BcConst destructor. 99 BC_DTOR_CONST, 100 101 /// BcResult destructor. 102 BC_DTOR_RESULT, 103 104 #if BC_ENABLE_HISTORY 105 106 /// String destructor for history, which is *special*. 107 BC_DTOR_HISTORY_STRING, 108 109 #endif // BC_ENABLE_HISTORY 110 #else // !BC_ENABLE_LIBRARY 111 112 /// Destructor for bcl numbers. 113 BC_DTOR_BCL_NUM, 114 115 #endif // !BC_ENABLE_LIBRARY 116 117 } BcDtorType; 118 119 /// The actual vector struct. 120 typedef struct BcVec 121 { 122 /// The vector array itself. This uses a char* because it is compatible with 123 /// pointers of all other types, and I can do pointer arithmetic on it. 124 char* restrict v; 125 126 /// The length of the vector, which is how many items actually exist. 127 size_t len; 128 129 /// The capacity of the vector, which is how many items can fit in the 130 /// current allocation. 131 size_t cap; 132 133 /// The size of the items in the vector, as returned by sizeof(). 134 BcSize size; 135 136 /// The destructor as a BcDtorType enum. 137 BcSize dtor; 138 139 } BcVec; 140 141 /** 142 * Initializes a vector. 143 * @param v The vector to initialize. 144 * @param esize The size of the elements, as returned by sizeof(). 145 * @param dtor The destructor of the elements, as a BcDtorType enum. 146 */ 147 void 148 bc_vec_init(BcVec* restrict v, size_t esize, BcDtorType dtor); 149 150 /** 151 * Expands the vector to have a capacity of @a req items, if it doesn't have 152 * enough already. 153 * @param v The vector to expand. 154 * @param req The requested capacity. 155 */ 156 void 157 bc_vec_expand(BcVec* restrict v, size_t req); 158 159 /** 160 * Grow a vector by at least @a n elements. 161 * @param v The vector to grow. 162 * @param n The number of elements to grow the vector by. 163 */ 164 void 165 bc_vec_grow(BcVec* restrict v, size_t n); 166 167 /** 168 * Pops @a n items off the back of the vector. The vector must have at least 169 * @a n elements. 170 * @param v The vector to pop off of. 171 * @param n The number of elements to pop off. 172 */ 173 void 174 bc_vec_npop(BcVec* restrict v, size_t n); 175 176 /** 177 * Pops @a n items, starting at index @a idx, off the vector. The vector must 178 * have at least @a n elements after the @a idx index. Any remaining elements at 179 * the end are moved up to fill the hole. 180 * @param v The vector to pop off of. 181 * @param n The number of elements to pop off. 182 * @param idx The index to start popping at. 183 */ 184 void 185 bc_vec_npopAt(BcVec* restrict v, size_t n, size_t idx); 186 187 /** 188 * Pushes one item on the back of the vector. It does a memcpy(), but it assumes 189 * that the vector takes ownership of the data. 190 * @param v The vector to push onto. 191 * @param data A pointer to the data to push. 192 */ 193 void 194 bc_vec_push(BcVec* restrict v, const void* data); 195 196 /** 197 * Pushes @a n items on the back of the vector. It does a memcpy(), but it 198 * assumes that the vector takes ownership of the data. 199 * @param v The vector to push onto. 200 * @param data A pointer to the elements of data to push. 201 */ 202 void 203 bc_vec_npush(BcVec* restrict v, size_t n, const void* data); 204 205 /** 206 * Push an empty element and return a pointer to it. This is done as an 207 * optimization where initializing an item needs a pointer anyway. It removes an 208 * extra memcpy(). 209 * @param v The vector to push onto. 210 * @return A pointer to the newly-pushed element. 211 */ 212 void* 213 bc_vec_pushEmpty(BcVec* restrict v); 214 215 /** 216 * Pushes a byte onto a bytecode vector. This is a convenience function for the 217 * parsers pushing instructions. The vector must be a bytecode vector. 218 * @param v The vector to push onto. 219 * @param data The byte to push. 220 */ 221 void 222 bc_vec_pushByte(BcVec* restrict v, uchar data); 223 224 /** 225 * Pushes and index onto a bytecode vector. The vector must be a bytecode 226 * vector. For more info about why and how this is done, see the development 227 * manual (manuals/development#bytecode-indices). 228 * @param v The vector to push onto. 229 * @param idx The index to push. 230 */ 231 void 232 bc_vec_pushIndex(BcVec* restrict v, size_t idx); 233 234 /** 235 * Push an item onto the vector at a certain index. The index must be valid 236 * (either exists or is equal to the length of the vector). The elements at that 237 * index and after are moved back one element and kept in the same order. This 238 * is how the map vectors are kept sorted. 239 * @param v The vector to push onto. 240 * @param data A pointer to the data to push. 241 * @param idx The index to push at. 242 */ 243 void 244 bc_vec_pushAt(BcVec* restrict v, const void* data, size_t idx); 245 246 /** 247 * Empties the vector and sets it to the string. The vector must be a valid 248 * vector and must have chars as its elements. 249 * @param v The vector to set to the string. 250 * @param len The length of the string. This can be less than the actual length 251 * of the string, but must never be more. 252 * @param str The string to push. 253 */ 254 void 255 bc_vec_string(BcVec* restrict v, size_t len, const char* restrict str); 256 257 /** 258 * Appends the string to the end of the vector, which must be holding a string 259 * (nul byte-terminated) already. 260 * @param v The vector to append to. 261 * @param str The string to append (by copying). 262 */ 263 void 264 bc_vec_concat(BcVec* restrict v, const char* restrict str); 265 266 /** 267 * Empties a vector and pushes a nul-byte at the first index. The vector must be 268 * a char vector. 269 */ 270 void 271 bc_vec_empty(BcVec* restrict v); 272 273 #if BC_ENABLE_HISTORY 274 275 /** 276 * Replaces an item at a particular index. No elements are moved. The index must 277 * exist. 278 * @param v The vector to replace an item on. 279 * @param idx The index of the item to replace. 280 * @param data The data to replace the item with. 281 */ 282 void 283 bc_vec_replaceAt(BcVec* restrict v, size_t idx, const void* data); 284 285 #endif // BC_ENABLE_HISTORY 286 287 /** 288 * Returns a pointer to the item in the vector at the index. This is the key 289 * function for vectors. The index must exist. 290 * @param v The vector. 291 * @param idx The index to the item to get a pointer to. 292 * @return A pointer to the item at @a idx. 293 */ 294 void* 295 bc_vec_item(const BcVec* restrict v, size_t idx); 296 297 /** 298 * Returns a pointer to the item in the vector at the index, reversed. This is 299 * another key function for vectors. The index must exist. 300 * @param v The vector. 301 * @param idx The index to the item to get a pointer to. 302 * @return A pointer to the item at len - @a idx - 1. 303 */ 304 void* 305 bc_vec_item_rev(const BcVec* restrict v, size_t idx); 306 307 /** 308 * Zeros a vector. The vector must not be allocated. 309 * @param v The vector to clear. 310 */ 311 void 312 bc_vec_clear(BcVec* restrict v); 313 314 /** 315 * Frees a vector and its elements. This is a destructor. 316 * @param vec A vector as a void pointer. 317 */ 318 void 319 bc_vec_free(void* vec); 320 321 /** 322 * Attempts to insert an ID into a map and returns true if it succeeded, false 323 * if the item already exists. 324 * @param v The map vector to insert into. 325 * @param name The name of the item to insert. This name is assumed to be owned 326 * by another entity. 327 * @param idx The index of the partner array where the actual item is. 328 * @param i A pointer to an index that will be set to the index of the item 329 * in the map. 330 * @return True if the item was inserted, false if the item already exists. 331 */ 332 bool 333 bc_map_insert(BcVec* restrict v, const char* name, size_t idx, 334 size_t* restrict i); 335 336 /** 337 * Returns the index of the item with @a name in the map, or BC_VEC_INVALID_IDX 338 * if it doesn't exist. 339 * @param v The map vector. 340 * @param name The name of the item to find. 341 * @return The index in the map of the item with @a name, or 342 * BC_VEC_INVALID_IDX if the item does not exist. 343 */ 344 size_t 345 bc_map_index(const BcVec* restrict v, const char* name); 346 347 #if DC_ENABLED 348 349 /** 350 * Returns the name of the item at index @a idx in the map. 351 * @param v The map vector. 352 * @param idx The index. 353 * @return The name of the item at @a idx. 354 */ 355 const char* 356 bc_map_name(const BcVec* restrict v, size_t idx); 357 358 #endif // DC_ENABLED 359 360 /** 361 * Pops one item off of the vector. 362 * @param v The vector to pop one item off of. 363 */ 364 #define bc_vec_pop(v) (bc_vec_npop((v), 1)) 365 366 /** 367 * Pops all items off of the vector. 368 * @param v The vector to pop all items off of. 369 */ 370 #define bc_vec_popAll(v) (bc_vec_npop((v), (v)->len)) 371 372 /** 373 * Return a pointer to the last item in the vector, or first if it's being 374 * treated as a stack. 375 * @param v The vector to get the top of stack of. 376 */ 377 #define bc_vec_top(v) (bc_vec_item_rev((v), 0)) 378 379 /** 380 * Initializes a vector to serve as a map. 381 * @param v The vector to initialize. 382 */ 383 #define bc_map_init(v) (bc_vec_init((v), sizeof(BcId), BC_DTOR_NONE)) 384 385 /// A reference to the array of destructors. 386 extern const BcVecFree bc_vec_dtors[]; 387 388 #if !BC_ENABLE_LIBRARY 389 390 /// The allocated size of slabs. 391 #define BC_SLAB_SIZE (4096) 392 393 /// A slab for allocating strings. 394 typedef struct BcSlab 395 { 396 /// The actual allocation. 397 char* s; 398 399 /// How many bytes of the slab are taken. 400 size_t len; 401 402 } BcSlab; 403 404 /** 405 * Frees a slab. This is a destructor. 406 * @param slab The slab as a void pointer. 407 */ 408 void 409 bc_slab_free(void* slab); 410 411 /** 412 * Initializes a slab vector. 413 * @param v The vector to initialize. 414 */ 415 void 416 bc_slabvec_init(BcVec* restrict v); 417 418 /** 419 * Duplicates the string using slabs in the slab vector. 420 * @param v The slab vector. 421 * @param str The string to duplicate. 422 * @return A pointer to the duplicated string, owned by the slab vector. 423 */ 424 char* 425 bc_slabvec_strdup(BcVec* restrict v, const char* str); 426 427 /** 428 * Clears a slab vector. This deallocates all but the first slab and clears the 429 * first slab. 430 * @param v The slab vector to clear. 431 */ 432 void 433 bc_slabvec_clear(BcVec* restrict v); 434 435 #if BC_DEBUG_CODE 436 437 /** 438 * Prints all of the items in a slab vector, in order. 439 * @param v The vector whose items will be printed. 440 */ 441 void 442 bc_slabvec_print(BcVec* v, const char* func); 443 444 #endif // BC_DEBUG_CODE 445 446 /// A convenience macro for freeing a vector of slabs. 447 #define bc_slabvec_free bc_vec_free 448 449 #ifndef _WIN32 450 451 /** 452 * A macro to get rid of a warning on Windows. 453 * @param d The destination string. 454 * @param l The length of the destination string. This has to be big enough to 455 * contain @a s. 456 * @param s The source string. 457 */ 458 #define bc_strcpy(d, l, s) strcpy(d, s) 459 460 #else // _WIN32 461 462 /** 463 * A macro to get rid of a warning on Windows. 464 * @param d The destination string. 465 * @param l The length of the destination string. This has to be big enough to 466 * contain @a s. 467 * @param s The source string. 468 */ 469 #define bc_strcpy(d, l, s) strcpy_s(d, l, s) 470 471 #endif // _WIN32 472 473 #endif // !BC_ENABLE_LIBRARY 474 475 #endif // BC_VECTOR_H 476