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