xref: /freebsd/contrib/bc/include/vector.h (revision 9bc300465e48e19d794d88d0c158a2adb92c7197)
1 /*
2  * *****************************************************************************
3  *
4  * SPDX-License-Identifier: BSD-2-Clause
5  *
6  * Copyright (c) 2018-2024 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 #if BC_LONG_BIT >= 64
63 
64 /// An integer to shrink the size of a vector by using these instead of size_t.
65 typedef 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.
70 typedef 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.
75 typedef 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.
120 typedef 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  */
147 void
148 bc_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  */
156 void
157 bc_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  */
164 void
165 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
174 bc_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  */
184 void
185 bc_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  */
193 void
194 bc_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  */
202 void
203 bc_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  */
212 void*
213 bc_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  */
221 void
222 bc_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  */
231 void
232 bc_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  */
243 void
244 bc_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  */
254 void
255 bc_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  */
263 void
264 bc_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  */
270 void
271 bc_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  */
282 void
283 bc_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  */
294 void*
295 bc_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  */
304 void*
305 bc_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  */
311 void
312 bc_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  */
318 void
319 bc_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  */
332 bool
333 bc_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  */
344 size_t
345 bc_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  */
355 const char*
356 bc_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.
386 extern 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.
394 typedef 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  */
408 void
409 bc_slab_free(void* slab);
410 
411 /**
412  * Initializes a slab vector.
413  * @param v  The vector to initialize.
414  */
415 void
416 bc_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  */
424 char*
425 bc_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  */
432 void
433 bc_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  */
441 void
442 bc_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