You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('') and can be up to 35 characters long.
497 lines
14 KiB
497 lines
14 KiB
/* 

* ***************************************************************************** 

* 

* SPDXLicenseIdentifier: BSD2Clause 

* 

* Copyright (c) 20182021 Gavin D. Howard and contributors. 

* 

* Redistribution and use in source and binary forms, with or without 

* modification, are permitted provided that the following conditions are met: 

* 

* * Redistributions of source code must retain the above copyright notice, this 

* list of conditions and the following disclaimer. 

* 

* * Redistributions in binary form must reproduce the above copyright notice, 

* this list of conditions and the following disclaimer in the documentation 

* and/or other materials provided with the distribution. 

* 

* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 

* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 

* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 

* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 

* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 

* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 

* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 

* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 

* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 

* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 

* POSSIBILITY OF SUCH DAMAGE. 

* 

* ***************************************************************************** 

* 

* Definitions for bc vectors (resizable arrays). 

* 

*/ 



#ifndef BC_VECTOR_H 

#define BC_VECTOR_H 



#include <stdbool.h> 

#include <stddef.h> 

#include <stdint.h> 



#include <status.h> 



/// An invalid index for a map to mark when an item does not exist. 

#define BC_VEC_INVALID_IDX (SIZE_MAX) 



/// The starting capacity for vectors. This is based on the minimum allocation 

/// for 64bit systems. 

#define BC_VEC_START_CAP (UINTMAX_C(1) << 5) 



/// An alias. 

typedef unsigned char uchar; 



/** 

* A destructor. Frees the object that @a ptr points to. This is used by vectors 

* to free the memory they own. 

* @param ptr Pointer to the data to free. 

*/ 

typedef void (*BcVecFree)(void* ptr); 



// Forward declaration. 

struct BcId; 



#if BC_LONG_BIT >= 64 



/// An integer to shrink the size of a vector by using these instead of size_t. 

typedef uint32_t BcSize; 



#else // BC_LONG_BIT >= 64 



/// An integer to shrink the size of a vector by using these instead of size_t. 

typedef uint16_t BcSize; 



#endif // BC_LONG_BIT >= 64 



/// An enum of all of the destructors. We use an enum to save space. 

typedef enum BcDtorType 

{ 

/// No destructor needed. 

BC_DTOR_NONE, 



/// Vector destructor. 

BC_DTOR_VEC, 



/// BcNum destructor. 

BC_DTOR_NUM, 



#if !BC_ENABLE_LIBRARY 



#ifndef NDEBUG 



/// BcFunc destructor. 

BC_DTOR_FUNC, 



#endif // NDEBUG 



/// BcSlab destructor. 

BC_DTOR_SLAB, 



/// BcConst destructor. 

BC_DTOR_CONST, 



/// BcResult destructor. 

BC_DTOR_RESULT, 



#if BC_ENABLE_HISTORY 



/// String destructor for history, which is *special*. 

BC_DTOR_HISTORY_STRING, 



#endif // BC_ENABLE_HISTORY 

#else // !BC_ENABLE_LIBRARY 



/// Destructor for bcl numbers. 

BC_DTOR_BCL_NUM, 



#endif // !BC_ENABLE_LIBRARY 



} BcDtorType; 



/// The actual vector struct. 

typedef struct BcVec 

{ 

/// The vector array itself. This uses a char* because it is compatible with 

/// pointers of all other types, and I can do pointer arithmetic on it. 

char* restrict v; 



/// The length of the vector, which is how many items actually exist. 

size_t len; 



/// The capacity of the vector, which is how many items can fit in the 

/// current allocation. 

size_t cap; 



/// The size of the items in the vector, as returned by sizeof(). 

BcSize size; 



/// The destructor as a BcDtorType enum. 

BcSize dtor; 



} BcVec; 



/** 

* Initializes a vector. 

* @param v The vector to initialize. 

* @param esize The size of the elements, as returned by sizeof(). 

* @param dtor The destructor of the elements, as a BcDtorType enum. 

*/ 

void 

bc_vec_init(BcVec* restrict v, size_t esize, BcDtorType dtor); 



/** 

* Expands the vector to have a capacity of @a req items, if it doesn't have 

* enough already. 

* @param v The vector to expand. 

* @param req The requested capacity. 

*/ 

void 

bc_vec_expand(BcVec* restrict v, size_t req); 



/** 

* Grow a vector by at least @a n elements. 

* @param v The vector to grow. 

* @param n The number of elements to grow the vector by. 

*/ 

void 

bc_vec_grow(BcVec* restrict v, size_t n); 



/** 

* Pops @a n items off the back of the vector. The vector must have at least 

* @a n elements. 

* @param v The vector to pop off of. 

* @param n The number of elements to pop off. 

*/ 

void 

bc_vec_npop(BcVec* restrict v, size_t n); 



/** 

* Pops @a n items, starting at index @a idx, off the vector. The vector must 

* have at least @a n elements after the @a idx index. Any remaining elements at 

* the end are moved up to fill the hole. 

* @param v The vector to pop off of. 

* @param n The number of elements to pop off. 

* @param idx The index to start popping at. 

*/ 

void 

bc_vec_npopAt(BcVec* restrict v, size_t n, size_t idx); 



/** 

* Pushes one item on the back of the vector. It does a memcpy(), but it assumes 

* that the vector takes ownership of the data. 

* @param v The vector to push onto. 

* @param data A pointer to the data to push. 

*/ 

void 

bc_vec_push(BcVec* restrict v, const void* data); 



/** 

* Pushes @a n items on the back of the vector. It does a memcpy(), but it 

* assumes that the vector takes ownership of the data. 

* @param v The vector to push onto. 

* @param data A pointer to the elements of data to push. 

*/ 

void 

bc_vec_npush(BcVec* restrict v, size_t n, const void* data); 



/** 

* Push an empty element and return a pointer to it. This is done as an 

* optimization where initializing an item needs a pointer anyway. It removes an 

* extra memcpy(). 

* @param v The vector to push onto. 

* @return A pointer to the newlypushed element. 

*/ 

void* 

bc_vec_pushEmpty(BcVec* restrict v); 



/** 

* Pushes a byte onto a bytecode vector. This is a convenience function for the 

* parsers pushing instructions. The vector must be a bytecode vector. 

* @param v The vector to push onto. 

* @param data The byte to push. 

*/ 

void 

bc_vec_pushByte(BcVec* restrict v, uchar data); 



/** 

* Pushes and index onto a bytecode vector. The vector must be a bytecode 

* vector. For more info about why and how this is done, see the development 

* manual (manuals/development#bytecodeindices). 

* @param v The vector to push onto. 

* @param idx The index to push. 

*/ 

void 

bc_vec_pushIndex(BcVec* restrict v, size_t idx); 



/** 

* Push an item onto the vector at a certain index. The index must be valid 

* (either exists or is equal to the length of the vector). The elements at that 

* index and after are moved back one element and kept in the same order. This 

* is how the map vectors are kept sorted. 

* @param v The vector to push onto. 

* @param data A pointer to the data to push. 

* @param idx The index to push at. 

*/ 

void 

bc_vec_pushAt(BcVec* restrict v, const void* data, size_t idx); 



/** 

* Empties the vector and sets it to the string. The vector must be a valid 

* vector and must have chars as its elements. 

* @param v The vector to set to the string. 

* @param len The length of the string. This can be less than the actual length 

* of the string, but must never be more. 

* @param str The string to push. 

*/ 

void 

bc_vec_string(BcVec* restrict v, size_t len, const char* restrict str); 



/** 

* Appends the string to the end of the vector, which must be holding a string 

* (nul byteterminated) already. 

* @param v The vector to append to. 

* @param str The string to append (by copying). 

*/ 

void 

bc_vec_concat(BcVec* restrict v, const char* restrict str); 



/** 

* Empties a vector and pushes a nulbyte at the first index. The vector must be 

* a char vector. 

*/ 

void 

bc_vec_empty(BcVec* restrict v); 



#if BC_ENABLE_HISTORY 



/** 

* Replaces an item at a particular index. No elements are moved. The index must 

* exist. 

* @param v The vector to replace an item on. 

* @param idx The index of the item to replace. 

* @param data The data to replace the item with. 

*/ 

void 

bc_vec_replaceAt(BcVec* restrict v, size_t idx, const void* data); 



#endif // BC_ENABLE_HISTORY 



/** 

* Returns a pointer to the item in the vector at the index. This is the key 

* function for vectors. The index must exist. 

* @param v The vector. 

* @param idx The index to the item to get a pointer to. 

* @return A pointer to the item at @a idx. 

*/ 

void* 

bc_vec_item(const BcVec* restrict v, size_t idx); 



/** 

* Returns a pointer to the item in the vector at the index, reversed. This is 

* another key function for vectors. The index must exist. 

* @param v The vector. 

* @param idx The index to the item to get a pointer to. 

* @return A pointer to the item at len  @a idx  1. 

*/ 

void* 

bc_vec_item_rev(const BcVec* restrict v, size_t idx); 



/** 

* Zeros a vector. The vector must not be allocated. 

* @param v The vector to clear. 

*/ 

void 

bc_vec_clear(BcVec* restrict v); 



/** 

* Frees a vector and its elements. This is a destructor. 

* @param vec A vector as a void pointer. 

*/ 

void 

bc_vec_free(void* vec); 



/** 

* Attempts to insert an item into a map and returns true if it succeeded, false 

* if the item already exists. 

* @param v The map vector to insert into. 

* @param name The name of the item to insert. This name is assumed to be owned 

* by another entity. 

* @param idx The index of the partner array where the actual item is. 

* @param i A pointer to an index that will be set to the index of the item 

* in the map. 

* @return True if the item was inserted, false if the item already exists. 

*/ 

bool 

bc_map_insert(BcVec* restrict v, const char* name, size_t idx, 

size_t* restrict i); 



/** 

* Returns the index of the item with @a name in the map, or BC_VEC_INVALID_IDX 

* if it doesn't exist. 

* @param v The map vector. 

* @param name The name of the item to find. 

* @return The index in the map of the item with @a name, or 

* BC_VEC_INVALID_IDX if the item does not exist. 

*/ 

size_t 

bc_map_index(const BcVec* restrict v, const char* name); 



#if DC_ENABLED 



/** 

* Returns the name of the item at index @a idx in the map. 

* @param v The map vector. 

* @param idx The index. 

* @return The name of the item at @a idx. 

*/ 

const char* 

bc_map_name(const BcVec* restrict v, size_t idx); 



#endif // DC_ENABLED 



/** 

* Pops one item off of the vector. 

* @param v The vector to pop one item off of. 

*/ 

#define bc_vec_pop(v) (bc_vec_npop((v), 1)) 



/** 

* Pops all items off of the vector. 

* @param v The vector to pop all items off of. 

*/ 

#define bc_vec_popAll(v) (bc_vec_npop((v), (v)>len)) 



/** 

* Return a pointer to the last item in the vector, or first if it's being 

* treated as a stack. 

* @param v The vector to get the top of stack of. 

*/ 

#define bc_vec_top(v) (bc_vec_item_rev((v), 0)) 



/** 

* Initializes a vector to serve as a map. 

* @param v The vector to initialize. 

*/ 

#define bc_map_init(v) (bc_vec_init((v), sizeof(BcId), BC_DTOR_NONE)) 



/// A reference to the array of destructors. 

extern const BcVecFree bc_vec_dtors[]; 



#if !BC_ENABLE_LIBRARY 



/// The allocated size of slabs. 

#define BC_SLAB_SIZE (4096) 



/// A slab for allocating strings. 

typedef struct BcSlab 

{ 

/// The actual allocation. 

char* s; 



/// How many bytes of the slab are taken. 

size_t len; 



} BcSlab; 



/** 

* Frees a slab. This is a destructor. 

* @param slab The slab as a void pointer. 

*/ 

void 

bc_slab_free(void* slab); 



/** 

* Initializes a slab vector. 

* @param v The vector to initialize. 

*/ 

void 

bc_slabvec_init(BcVec* restrict v); 



/** 

* Duplicates the string using slabs in the slab vector. 

* @param v The slab vector. 

* @param str The string to duplicate. 

* @return A pointer to the duplicated string, owned by the slab vector. 

*/ 

char* 

bc_slabvec_strdup(BcVec* restrict v, const char* str); 



/** 

* Clears a slab vector. This deallocates all but the first slab and clears the 

* first slab. 

* @param v The slab vector to clear. 

*/ 

void 

bc_slabvec_clear(BcVec* restrict v); 



#if BC_DEBUG_CODE 



/** 

* Prints all of the items in a slab vector, in order. 

* @param v The vector whose items will be printed. 

*/ 

void 

bc_slabvec_print(BcVec* v, const char* func); 



#endif // BC_DEBUG_CODE 



/// A convenience macro for freeing a vector of slabs. 

#define bc_slabvec_free bc_vec_free 



#if BC_ENABLED 

#if DC_ENABLED 



/// Returns the set of slabs for the maps and the current calculator. 

#define BC_VEC_MAP_SLABS (BC_IS_DC ? &vm>main_slabs : &vm>other_slabs) 



#else // DC_ENABLED 



/// Returns the set of slabs for the maps and the current calculator. 

#define BC_VEC_MAP_SLABS (&vm>other_slabs) 



#endif // DC_ENABLED 

#else // BC_ENABLED 



/// Returns the set of slabs for the maps and the current calculator. 

#define BC_VEC_MAP_SLABS (&vm>main_slabs) 



#endif // BC_ENABLED 



#ifndef _WIN32 



/** 

* A macro to get rid of a warning on Windows. 

* @param d The destination string. 

* @param l The length of the destination string. This has to be big enough to 

* contain @a s. 

* @param s The source string. 

*/ 

#define bc_strcpy(d, l, s) strcpy(d, s) 



#else // _WIN32 



/** 

* A macro to get rid of a warning on Windows. 

* @param d The destination string. 

* @param l The length of the destination string. This has to be big enough to 

* contain @a s. 

* @param s The source string. 

*/ 

#define bc_strcpy(d, l, s) strcpy_s(d, l, s) 



#endif // _WIN32 



#endif // !BC_ENABLE_LIBRARY 



#endif // BC_VECTOR_H


