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