contrib/bc/include/vector.h

   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