Last active
September 11, 2026 10:51
-
-
Save ClarkeRemy/3be5800a0deda6b92ba4d3b83d89f69c to your computer and use it in GitHub Desktop.
Basic (untested) C vector
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdint.h> | |
| #include <string.h> | |
| #define VECTOR_ALIGN_CHECK 0 | |
| struct vector_t { | |
| uint64_t size; | |
| uint64_t align; | |
| uint64_t stride; | |
| uint64_t len; | |
| uint64_t capacity; | |
| char* data; | |
| int aliased_allocation; | |
| }; | |
| /** the maximum between an elements size and it's alignment. | |
| * | |
| */ | |
| static inline uint64_t vector_stride(struct vector_t* v) { | |
| return ((v->size + v->align - 1) / v->align) * v->align; | |
| } | |
| struct vector_t vector_new(size_t size, size_t align) { | |
| struct vector_t v = {0}; | |
| v.size = size; | |
| v.align = align; | |
| v.stride = vector_stride(&v); | |
| return v; | |
| } | |
| static inline uint64_t uint64_t_min(uint64_t l, uint64_t r) { | |
| return (l < r)? l : r; | |
| } | |
| static inline uint64_t uint64_t_max(uint64_t l, uint64_t r) { | |
| return (l > r)? l : r; | |
| } | |
| /** returns the vector's length __before__ the operation was completed | |
| * | |
| * decrements the vectors length | |
| * returns 0 if input vector was empty | |
| */ | |
| static uint64_t vector_pop_last_len(struct vector_t* v) { | |
| uint64_t out = v->len; | |
| if (v->len != 0) v->len--; | |
| return out; | |
| } | |
| /** the last min(len, n) elements are forgotten | |
| * | |
| * returns the minimum between the number of elements requested to be forgotten, | |
| * and how many were actually forgotten. | |
| * | |
| * a discrepancy is between n and the result may be a signal for an error. | |
| */ | |
| uint64_t vector_forget_n(struct vector_t* v, uint64_t n) { | |
| uint64_t min = uint64_t_min(v->len, n); | |
| v->len -= min; | |
| return min; | |
| } | |
| /** the last min(capacity-len, n) elements are recovered | |
| * | |
| * Assumes the values that are "recovered" are correctly initialized. | |
| * One can only recover as many elements as remain in the difference between | |
| * the length and capacity | |
| * | |
| * a discrepancy is between n and the result may be a signal for an error. | |
| */ | |
| uint64_t vector_recover_n(struct vector_t* v, uint64_t n) { | |
| uint64_t min = uint64_t_min(v->capacity - v->len, n); | |
| v->len += min; | |
| return min; | |
| } | |
| static inline void* vector_nth_unchecked(struct vector_t* v, uint64_t n) { | |
| return (void*)(v->data + v->stride * n); | |
| } | |
| /** returns the number of elements in the vector at the end of the operation | |
| * | |
| * An element may not be popped and written if the output is improperly aligned | |
| * This is observable if the vector keeps returning the same non-zero value | |
| */ | |
| uint64_t vector_pop_element(struct vector_t* v, void* out) { | |
| if ( VECTOR_ALIGN_CHECK | |
| && ((uint64_t)out % v->align)!=0) | |
| return v->len; | |
| if (vector_pop_last_len(v)) { | |
| memcpy(out, vector_nth_unchecked(v, v->len), v->stride); | |
| } | |
| return v->len; | |
| } | |
| /** returns a pointer to the element of interest in the vector | |
| * | |
| * returns a null pointer when the index is out of bounds | |
| */ | |
| void* vector_nth(struct vector_t* v, uint64_t n) { | |
| if (n >= (v->len)) return (void*)0; | |
| v->aliased_allocation = 1; | |
| return vector_nth_unchecked(v, n); | |
| } | |
| /** this signals that the vector is being aliased and cannot reallocate | |
| * | |
| */ | |
| void vector_set_allocation_alias(struct vector_t* v) { | |
| v->aliased_allocation = 1; | |
| } | |
| /** use of this function asserts that a previously aliased vector is clear of aliasing | |
| * | |
| */ | |
| void vector_clear_allocation_alias(struct vector_t* v) { | |
| v->aliased_allocation = 0; | |
| } | |
| /** returns the number of elements remaining availible slots in the vector | |
| * | |
| * An element may not be pushed if either the vector is full, or the input is unaligned | |
| * This is observable if the vector keeps returning the same value | |
| */ | |
| uint64_t vector_push(struct vector_t* v, void* in) { | |
| if ( VECTOR_ALIGN_CHECK | |
| && ((uint64_t)in % v->align)!=0) | |
| return v->capacity - v->len; | |
| if (v->len == v->capacity) return 0; | |
| void* nth = vector_nth_unchecked(v,v->len); | |
| memcpy(nth, in, v->size); | |
| v->len++; | |
| return v->capacity - v->len; | |
| } | |
| static inline int vector_advise_realloc(struct vector_t* v, uint64_t n) { | |
| return (v->len+n >= v->capacity); | |
| } | |
| static inline void* vector_realloc_unchecked( | |
| struct vector_t* v, | |
| uint64_t new_capacity, | |
| void* allocator, | |
| void*(*alloc)(void* allocator, size_t size, size_t align) | |
| ){ | |
| void* old = (void*)(v->data); | |
| new_capacity = uint64_t_max(1, new_capacity); | |
| void* new_ = alloc(allocator, v->stride * new_capacity, v->align); | |
| if (new_ == (void*)0) return new_; | |
| if (old != (void*)0) memcpy(new_, old, v->stride * v->len); | |
| v->data = (char*)new_; | |
| v->capacity = new_capacity; | |
| return old; | |
| } | |
| /** grows the vector to a larger allocation if n elements cannot be pushed in. | |
| * | |
| * | |
| * returns null if did not grow | |
| * retruns the original allocation otherwise | |
| * | |
| * failure to grow can be because of aliasing detection. | |
| * to assert no aliasing, call vector_clear_allocation_alias. | |
| * | |
| * the alloc parameter should return a null pointer if allocation failed | |
| */ | |
| void* vector_grow( | |
| struct vector_t* v, | |
| uint64_t n, | |
| void* allocator, | |
| void*(*alloc)(void* allocator, size_t size, size_t align) | |
| ){ | |
| if (v->aliased_allocation) return (void*)0; | |
| if (!vector_advise_realloc(v, n)) return (void*)0; | |
| return vector_realloc_unchecked(v, v->capacity + uint64_t_max(n,v->capacity),allocator,alloc); | |
| } | |
| /** shrinks the vector to a smaller allocation if n is a sufficient capacity. | |
| * | |
| * returns null if did not shrink | |
| * retruns the original allocation otherwise | |
| * | |
| * failure to grow can be because of aliasing detection. | |
| * to assert no aliasing, call vector_clear_allocation_alias. | |
| * | |
| * the alloc parameter should return a null pointer if allocation failed | |
| */ | |
| void* vector_shrink( | |
| struct vector_t* v, | |
| uint64_t n, | |
| void* allocator, | |
| void*(*alloc)(void* allocator, size_t size, size_t align) | |
| ) { | |
| if (v->aliased_allocation) return (void*)0; | |
| if (n < v->len || n >= v->capacity ) return (void*)0; | |
| if (n == 0) { | |
| void* old = (void*) v->data; | |
| v->data = (char*)0; | |
| v->capacity = 0; | |
| return old; | |
| } | |
| return vector_realloc_unchecked(v, n, allocator,alloc); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment