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. 53typedef 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 */ 60typedef 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. 65typedef 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. 70typedef 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. 75typedef 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. 120typedef 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 */ 147void 148bc_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 */ 156void 157bc_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 */ 164void 165bc_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 */ 173void 174bc_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 */ 184void 185bc_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 */ 193void 194bc_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 */ 202void 203bc_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 */ 212void* 213bc_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 */ 221void 222bc_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 */ 231void 232bc_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 */ 243void 244bc_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 */ 254void 255bc_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 */ 263void 264bc_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 */ 270void 271bc_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 */ 282void 283bc_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 */ 294void* 295bc_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 */ 304void* 305bc_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 */ 311void 312bc_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 */ 318void 319bc_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 */ 332bool 333bc_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 */ 344size_t 345bc_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 */ 355const char* 356bc_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. 386extern 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. 394typedef 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 */ 408void 409bc_slab_free(void* slab); 410 411/** 412 * Initializes a slab vector. 413 * @param v The vector to initialize. 414 */ 415void 416bc_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 */ 424char* 425bc_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 */ 432void 433bc_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 */ 441void 442bc_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