An implementation of Unix dc and POSIX bc with GNU and BSD extensions. Finished, but well-maintained.
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

/*
* *****************************************************************************
*
* SPDX-License-Identifier: BSD-2-Clause
*
* Copyright (c) 2018-2021 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 64-bit 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 newly-pushed 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#bytecode-indices).
* @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 byte-terminated) 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 nul-byte 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