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 bc_vec_init(BcVec *restrict v, size_t esize, BcDtorType dtor); 151 152 /** 153 * Expands the vector to have a capacity of @a req items, if it doesn't have 154 * enough already. 155 * @param v The vector to expand. 156 * @param req The requested capacity. 157 */ 158 void bc_vec_expand(BcVec *restrict v, size_t req); 159 160 /** 161 * Grow a vector by at least @a n elements. 162 * @param v The vector to grow. 163 * @param n The number of elements to grow the vector by. 164 */ 165 void 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 bc_vec_npop(BcVec *restrict v, size_t n); 174 175 /** 176 * Pops @a n items, starting at index @a idx, off the vector. The vector must 177 * have at least @a n elements after the @a idx index. Any remaining elements at 178 * the end are moved up to fill the hole. 179 * @param v The vector to pop off of. 180 * @param n The number of elements to pop off. 181 * @param idx The index to start popping at. 182 */ 183 void bc_vec_npopAt(BcVec *restrict v, size_t n, size_t idx); 184 185 /** 186 * Pushes one item on the back of the vector. It does a memcpy(), but it assumes 187 * that the vector takes ownership of the data. 188 * @param v The vector to push onto. 189 * @param data A pointer to the data to push. 190 */ 191 void bc_vec_push(BcVec *restrict v, const void *data); 192 193 /** 194 * Pushes @a n items on the back of the vector. It does a memcpy(), but it 195 * assumes that the vector takes ownership of the data. 196 * @param v The vector to push onto. 197 * @param data A pointer to the elements of data to push. 198 */ 199 void bc_vec_npush(BcVec *restrict v, size_t n, const void *data); 200 201 /** 202 * Push an empty element and return a pointer to it. This is done as an 203 * optimization where initializing an item needs a pointer anyway. It removes an 204 * extra memcpy(). 205 * @param v The vector to push onto. 206 * @return A pointer to the newly-pushed element. 207 */ 208 void* bc_vec_pushEmpty(BcVec *restrict v); 209 210 /** 211 * Pushes a byte onto a bytecode vector. This is a convenience function for the 212 * parsers pushing instructions. The vector must be a bytecode vector. 213 * @param v The vector to push onto. 214 * @param data The byte to push. 215 */ 216 void bc_vec_pushByte(BcVec *restrict v, uchar data); 217 218 /** 219 * Pushes and index onto a bytecode vector. The vector must be a bytecode 220 * vector. For more info about why and how this is done, see the development 221 * manual (manuals/development#bytecode-indices). 222 * @param v The vector to push onto. 223 * @param idx The index to push. 224 */ 225 void bc_vec_pushIndex(BcVec *restrict v, size_t idx); 226 227 /** 228 * Push an item onto the vector at a certain index. The index must be valid 229 * (either exists or is equal to the length of the vector). The elements at that 230 * index and after are moved back one element and kept in the same order. This 231 * is how the map vectors are kept sorted. 232 * @param v The vector to push onto. 233 * @param data A pointer to the data to push. 234 * @param idx The index to push at. 235 */ 236 void bc_vec_pushAt(BcVec *restrict v, const void *data, size_t idx); 237 238 /** 239 * Empties the vector and sets it to the string. The vector must be a valid 240 * vector and must have chars as its elements. 241 * @param v The vector to set to the string. 242 * @param len The length of the string. This can be less than the actual length 243 * of the string, but must never be more. 244 * @param str The string to push. 245 */ 246 void bc_vec_string(BcVec *restrict v, size_t len, const char *restrict str); 247 248 /** 249 * Appends the string to the end of the vector, which must be holding a string 250 * (nul byte-terminated) already. 251 * @param v The vector to append to. 252 * @param str The string to append (by copying). 253 */ 254 void bc_vec_concat(BcVec *restrict v, const char *restrict str); 255 256 /** 257 * Empties a vector and pushes a nul-byte at the first index. The vector must be 258 * a char vector. 259 */ 260 void bc_vec_empty(BcVec *restrict v); 261 262 #if BC_ENABLE_HISTORY 263 264 /** 265 * Replaces an item at a particular index. No elements are moved. The index must 266 * exist. 267 * @param v The vector to replace an item on. 268 * @param idx The index of the item to replace. 269 * @param data The data to replace the item with. 270 */ 271 void bc_vec_replaceAt(BcVec *restrict v, size_t idx, const void *data); 272 273 #endif // BC_ENABLE_HISTORY 274 275 /** 276 * Returns a pointer to the item in the vector at the index. This is the key 277 * function for vectors. The index must exist. 278 * @param v The vector. 279 * @param idx The index to the item to get a pointer to. 280 * @return A pointer to the item at @a idx. 281 */ 282 void* bc_vec_item(const BcVec *restrict v, size_t idx); 283 284 /** 285 * Returns a pointer to the item in the vector at the index, reversed. This is 286 * another key function for vectors. The index must exist. 287 * @param v The vector. 288 * @param idx The index to the item to get a pointer to. 289 * @return A pointer to the item at len - @a idx - 1. 290 */ 291 void* bc_vec_item_rev(const BcVec *restrict v, size_t idx); 292 293 /** 294 * Zeros a vector. The vector must not be allocated. 295 * @param v The vector to clear. 296 */ 297 void bc_vec_clear(BcVec *restrict v); 298 299 /** 300 * Frees a vector and its elements. This is a destructor. 301 * @param vec A vector as a void pointer. 302 */ 303 void bc_vec_free(void *vec); 304 305 /** 306 * Attempts to insert an item into a map and returns true if it succeeded, false 307 * if the item already exists. 308 * @param v The map vector to insert into. 309 * @param name The name of the item to insert. This name is assumed to be owned 310 * by another entity. 311 * @param idx The index of the partner array where the actual item is. 312 * @param i A pointer to an index that will be set to the index of the item 313 * in the map. 314 * @return True if the item was inserted, false if the item already exists. 315 */ 316 bool bc_map_insert(BcVec *restrict v, const char *name, 317 size_t idx, size_t *restrict i); 318 319 /** 320 * Returns the index of the item with @a name in the map, or BC_VEC_INVALID_IDX 321 * if it doesn't exist. 322 * @param v The map vector. 323 * @param name The name of the item to find. 324 * @return The index in the map of the item with @a name, or 325 * BC_VEC_INVALID_IDX if the item does not exist. 326 */ 327 size_t bc_map_index(const BcVec *restrict v, const char *name); 328 329 #if DC_ENABLED 330 331 /** 332 * Returns the name of the item at index @a idx in the map. 333 * @param v The map vector. 334 * @param idx The index. 335 * @return The name of the item at @a idx. 336 */ 337 const char* bc_map_name(const BcVec *restrict v, size_t idx); 338 339 #endif // DC_ENABLED 340 341 /** 342 * Pops one item off of the vector. 343 * @param v The vector to pop one item off of. 344 */ 345 #define bc_vec_pop(v) (bc_vec_npop((v), 1)) 346 347 /** 348 * Pops all items off of the vector. 349 * @param v The vector to pop all items off of. 350 */ 351 #define bc_vec_popAll(v) (bc_vec_npop((v), (v)->len)) 352 353 /** 354 * Return a pointer to the last item in the vector, or first if it's being 355 * treated as a stack. 356 * @param v The vector to get the top of stack of. 357 */ 358 #define bc_vec_top(v) (bc_vec_item_rev((v), 0)) 359 360 /** 361 * Initializes a vector to serve as a map. 362 * @param v The vector to initialize. 363 */ 364 #define bc_map_init(v) (bc_vec_init((v), sizeof(BcId), BC_DTOR_NONE)) 365 366 /// A reference to the array of destructors. 367 extern const BcVecFree bc_vec_dtors[]; 368 369 #if !BC_ENABLE_LIBRARY 370 371 /// The allocated size of slabs. 372 #define BC_SLAB_SIZE (4096) 373 374 /// A slab for allocating strings. 375 typedef struct BcSlab { 376 377 /// The actual allocation. 378 char *s; 379 380 /// How many bytes of the slab are taken. 381 size_t len; 382 383 } BcSlab; 384 385 /** 386 * Frees a slab. This is a destructor. 387 * @param slab The slab as a void pointer. 388 */ 389 void bc_slab_free(void *slab); 390 391 /** 392 * Initializes a slab vector. 393 * @param v The vector to initialize. 394 */ 395 void bc_slabvec_init(BcVec *restrict v); 396 397 /** 398 * Duplicates the string using slabs in the slab vector. 399 * @param v The slab vector. 400 * @param str The string to duplicate. 401 * @return A pointer to the duplicated string, owned by the slab vector. 402 */ 403 char* bc_slabvec_strdup(BcVec *restrict v, const char *str); 404 405 #if BC_ENABLED 406 407 /** 408 * Undoes the last allocation on the slab vector. This allows bc to have a 409 * heap-based stacks for strings. This is used by the bc parser. 410 */ 411 void bc_slabvec_undo(BcVec *restrict v, size_t len); 412 413 #endif // BC_ENABLED 414 415 /** 416 * Clears a slab vector. This deallocates all but the first slab and clears the 417 * first slab. 418 * @param v The slab vector to clear. 419 */ 420 void bc_slabvec_clear(BcVec *restrict v); 421 422 #if BC_DEBUG_CODE 423 424 /** 425 * Prints all of the items in a slab vector, in order. 426 * @param v The vector whose items will be printed. 427 */ 428 void bc_slabvec_print(BcVec *v, const char *func); 429 430 #endif // BC_DEBUG_CODE 431 432 /// A convenience macro for freeing a vector of slabs. 433 #define bc_slabvec_free bc_vec_free 434 435 #ifndef _WIN32 436 437 /** 438 * A macro to get rid of a warning on Windows. 439 * @param d The destination string. 440 * @param l The length of the destination string. This has to be big enough to 441 * contain @a s. 442 * @param s The source string. 443 */ 444 #define bc_strcpy(d, l, s) strcpy(d, s) 445 446 #else // _WIN32 447 448 /** 449 * A macro to get rid of a warning on Windows. 450 * @param d The destination string. 451 * @param l The length of the destination string. This has to be big enough to 452 * contain @a s. 453 * @param s The source string. 454 */ 455 #define bc_strcpy(d, l, s) strcpy_s(d, l, s) 456 457 #endif // _WIN32 458 459 #endif // !BC_ENABLE_LIBRARY 460 461 #endif // BC_VECTOR_H 462