A VEC is a typesafe dynamic array, similar to stb's stretchy buffers and C++'s std::vector, whence the name. Insert operations automatically
allocate and grow the internal array using malloc() and realloc(). VECs do not shrink their allocation automatically.
A VEC is declared using the following macro, where Tis the type;
#define VEC(T) \
struct { \
size_t len, alloc; \
T* data; \
}
In this documentation, VEC* will be used to refer to a pointer to a VEC of unspecified type, which is used by all of the functions.
Usually this is the address of the actual variable, not a proper independent pointer to it. T will be used as the declared internal
type of the VEC.
Examples:
VEC(int) numbers;
VEC(char*) names;
VEC_push(&numbers, 56);
VEC_push(&names, "Simon");
Due to C's semantics involving anonymous structs, you have to typedef a VEC of some certain type if you want to declare
pointers to it. I am not aware of a workaround at this time.
typedef VEC(char*) StringList;
// a (string-keyed) hash table containing lists of nicknames for each person
HT(StringList*) nicknames;
char* longest_nickname(StringList* list) {
int longest_len = 0;
char* longest_str = NULL;
VEC_EACH(list, i, nick) {
int len = strlen(nick);
if(len > longest_len) {
longest_len = len;
longest_str = nick;
}
}
return longest_str;
}
VECs must be zero-initialized before use. There is a macro to do this if you value the semantics of it. Subsequent operations automatically
initialize internal variables and allocate memory as needed.
VEC(float) heights = {}; // perfectly fine
VEC_init(&names); // just zeroes out the memory
When you're done, free the internal memory with VEC_free(). Don't forget to also free memory held by the contents if necessary, there
are no cascading frees in C (nor should there be).
VEC(char*) files = {};
for(int a = 0; a < argc; a++) {
if(argv[a][0] == '-' && argv[a][1] == 'f') {
if(argc > a + 1) {
VEC_push(&files, strdup(argv[++a]); // inserted values are not evaluated
// more than once internally.
}
}
}
// do some stuff
VEC_EACH(&files, i, f) {
free(f)
}
VEC_free(&files);
There are magic loop macros for iterating over the contents. They work just like they appear to, including the use of break and continue, and
are a single statement internally, allowing constructs like if(foo) VEC_EACH(&bar, i, b) { printf("%d\n", b); } or nesting loops without
braces on the outer ones.
VEC_EACH(VEC* o, [size_t] iterator, [T] value) { ... }
VEC_EACHP(VEC* o, [size_t] iterator, [T*] elem_ptr) { ... }
iterator and value are both declared as local variables. The contents of VEC_item(o, iterator) are copied into value before each iteration.
A pointer to the actual internal memory at VEC_item(o, iterator) is copied into elem_ptr, allowing direct modification.
And versions that iterate in reverse, especially useful when using VEC_rm().
VEC_R_EACH(VEC* o, [size_t] iterator_name, [T] value_name) { ... }
VEC_R_EACHP(VEC* o, [size_t] iterator_name, [T*] elem_ptr_name) { ... }
Evaluates to the current used length, in elements. Is an L-value and can be assigned to.
Evaluates to the current internal memory allocation size, in elements not bytes. Is an L-value and can be assigned to, not that
you should.
Evaluates to the internal data array pointer. Is an L-value and can be assigned to.
T VEC_item(VEC* o, size_t index)
Evaluates to the internal array element for the given index. Is an L-value and can be assigned to.
Equivalent to
VEC_data(o)[index].
Element addresses are not stable and will change as the internal
memory gets reallocated due to growth. Use
SVEC if you need stable addresses.
There is no bounds checking; passing in an out-of-bounds index is User Error and you deserve the segfault.
Equivalent to VEC_item(o, 0)
T VEC_tail(VEC* o)
T VEC_peek(VEC* o)
Equivalent to VEC_item(o, VEC_len(o) - 1)
ssize_t VEC_find(VEC* o, T* elem_ptr)
Returns the index of the first element that is identical to elem_ptr, or -1 if not found.
Uses a simple linear scan with memcmp() internally.
Equivalent to VEC_len(o) = 0;. Does not cause internal allocation changes.
void VEC_push(VEC* o, T value)
Inserts value at the end of the array, ie, at location VEC_len(o) prior to the insert. Automatically checks allocation
size and grows the internal array if necessary.
Asserts a new value at the end of the array and zero-initializes it. Returns a pointer to the new element.
Remember that the returned pointer is not stable and may change if a later operation causes an internal realloc.
Roughly equivalent to VEC_push(o, (T){}), &VEC_tail(o)
Automatically checks allocation size and grows the internal array if necessary.
void VEC_calloc(VEC* o, size_t num_elems)
Pre-allocates and zero-initializes num_elems internally, and sets the length to num_elems. Existing data will be wiped.
void VEC_crealloc(VEC* o, size_t num_elems)
Pre-allocates and zero-initializes up to num_elems internally, and sets the length to num_elems. Existing data will be preserved..
void VEC_prepend(VEC* o, T value)
Inserts value at the beginning of the array, ie, index 0. Automatically checks allocation
size and grows the internal array if necessary. Existing data is memmove()d to make room.
'
T VEC_pop(VEC* o)
void VEC_pop(VEC* o, T* out_value)
Overloaded function that returns the last (tail) element and decrements the length.
Does not shink the internal allocation. Do not call on an empty VEC. GIGO. You have been warned.
void VEC_rm(VEC* o, size_t index)
Copies the tail element to the specified index, then decrements the length. Fast but does not preserve order.
void VEC_rm_safe(VEC* o, size_t index)
void VEC_rm_ordered(VEC* o, size_t index)
Removes the specified index and memmove()s the rest of the elements dow to fill the space.
Preserves order but slow.
void VEC_rm_val(VEC* o, T* search_elem)
Removes the first element matching *search_elem, using the order destroying algorithm of VEC_rm().
void VEC_copy(VEC* o_dst, VEC* o_src)
Copies data from o_src to o_dst, ensuring sufficient allocation. The lengthof o_dst is set to the length of o_src.
All existing data in o_dst is lost. The arguments must have the same internal type.
Reverses the order of the elements. No heap memory is allocated, no internal allocations change. Calls alloca(sizeof(T))
internally, so dont do anything dumb.
'
void VEC_reserve(VEC* o, size_t len, size_t start_index)
Checks allocations and then memmove()s all elements starting at start_index to make a space of len elements at
start_index. The contents of the reserved space is undefined (whatever used to be there).
void VEC_insert_at(VEC* o, T elem, size_t index)
Checks allocations and inserts elem at index, moving existing data onward.
void VEC_splice(VEC* o_dst, VEC* o_src, size_t index)
Checks allocations and inserts a complete copy of o_src into o_dst at index, moving existing data onward.
void VEC_overwrite(VEC* o_dst, VEC* o_src, size_t index)
Checks allocations and copies the complete contents of o_src into o_dst at index, overwriting existing data in that range.
void VEC_cat(VEC* o_dst, VEC* o_src)
Checks allocations and copies a complete copy of o_src onto the end of o_dst.
void VEC_sort(VEC* o, sort_fn_t* fn)
void VEC_sort_r(VEC* o, sort_fn_t* fn, void* d)
O(n log(n)), probably. Depends on your system's implementation of qsort()
Calls qsort() or qsort_r() respectively on the internal array. The signature of fn is whatever the signature of it is
for qsort/_r() on your system.
void VEC_uniq(VEC* o, int (*cmp)(const void*,const void*))
void VEC_uniq_r(VEC* o, int (*cmp)(const void*,const void*,void*))
Removes consecutive duplicate elements on a pre-sorted VEC.
void VEC_bubble_index(
VEC* o,
size_t start_index,
int (*cmp)(const void*,const void*)
)
Moves the element at start_index in a bubble-sort style fashion to its proper sorted location on an otherwise pre-sorted VEC.
Very niche use, for when a single element's value changes inside a sorted array. Was originally created as the lesser of evils for implementing
a certain mesh simplification algorithm.
