As a start to my journey in programming in a more handmade fashion, I decided to test my skills regarding memory management and C in general by attempting to code a C-equivalent of the C++ std::vector. I took inspiration from the stb_stretchy_buffer library.
It's not feature complete yet; just have pop/push, free, and size/cap functions. If you guys have any suggestions or comments, I'd love to hear them!
Here it is:
EDIT: Fixed some issues and implemented a few new features. Thanks for the comments, guys!
EDIT [2]: Threw in a license and uploaded to github
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | #ifndef _DARRAY_H #define _DARRAY_H #include <stdlib.h> #include <stdint.h> #include <memory.h> #define _DARRAY_START_CAP 32 #define da_shrink(a) if(da_size(a) > 0) { _da_shrink((void **)&a, sizeof(a[0])); } #define da_push(a, e) _da_push((void **)&a, &e, sizeof(e)) #define da_insert(a, e, i) _da_insert((void **)&a, &e, sizeof(e), i) #define da_pop(a) if(da_size(a)) { _da_pop((void **)&a, sizeof(a[0])); } #define da_erase(a, i) if(da_size(a)) { _da_erase((void **)&a, sizeof(a[0]), i); } #define da_free(a) _da_free((void **)&a) inline uint32_t *_da_raw(void *array) { return (uint32_t *)array - 2; } inline uint32_t da_size(void *array) { if(array) { return _da_raw(array)[0]; } return 0; } inline uint32_t da_cap(void *array) { if(array) { return _da_raw(array)[1]; } return 0; } inline void _da_free(void **array) { if(*array) { *array = (void *)(_da_raw(*array)); } free(*array); *array = NULL; } inline void _da_grow(void **array, size_t element_size) { uint32_t new_cap = _DARRAY_START_CAP, size = 0; bool need_realloc = true; if(*array) { size = da_size(*array); if(size >= da_cap(*array)) { new_cap = da_cap(*array) + (da_cap(*array) / 2); } else { new_cap = da_cap(*array); need_realloc = false; } } if(need_realloc) { if(*array) { *array = (void *)_da_raw(*array); } *array = realloc(*array, (new_cap * element_size) + (2 * sizeof(uint32_t))); *array = (void *)((uint32_t *)(*array) + 2); _da_raw(*array)[0] = size; _da_raw(*array)[1] = new_cap; } } inline void _da_shrink(void **array, size_t element_size) { if(*array) { if(da_size(*array) > 0) { if(da_size(*array) <= da_cap(*array) - (da_cap(*array) / 3)) { _da_raw(*array)[1] = da_cap(*array) - (da_cap(*array) / 3); *array = realloc(_da_raw(*array), (da_cap(*array) * element_size) + (2 * sizeof(uint32_t))); *array = (uint32_t *)(*array) + 2; } } else { _da_free(array); } } } inline void _da_push(void **array, void *element, size_t element_size) { _da_grow(array, element_size); memcpy(((uint8_t *)(*array)) + (element_size * da_size(*array)), element, element_size); _da_raw(*array)[0]++; } inline void _da_insert(void **array, void *element, size_t element_size, uint32_t pos) { _da_grow(array, element_size); memmove(((uint8_t *)(*array)) + (element_size * (pos + 1)), ((uint8_t *)(*array)) + (element_size * pos), element_size * (da_size(*array) - pos)); memcpy(((uint8_t *)(*array)) + (element_size * pos), element, element_size); _da_raw(*array)[0]++; } inline void _da_pop(void **array, size_t element_size) { if(*array) { _da_raw(*array)[0]--; if(da_size(*array) < 1) { da_free(*array); *array = NULL; } } } inline void _da_erase(void **array, size_t element_size, uint32_t pos) { if(*array) { memmove(((uint8_t *)(*array)) + (element_size * pos), ((uint8_t *)(*array)) + (element_size * (pos + 1)), element_size * (da_size(*array) - pos - 1)); _da_raw(*array)[0]--; if(da_size(*array) < 1) { da_free(*array); *array = NULL; } } } #endif |
Here's an example usage of it:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #include <stdio.h> #include "darray.h" int main() { int *ints = NULL; for(int i = 0; i < 10; i++) { da_push(ints, i); } da_erase(ints, 4); int x = 99; da_insert(ints, x, 4); printf("ints has the following contents:\n\n", da_cap(ints)); for(uint32_t i = 0; i < da_size(ints); i++) { printf("%i", ints[i]); if(i != da_size(ints) - 1) { printf(", "); } } da_free(ints); printf("\n\n"); return 0; } |
The output of the above snippet is the following:
1 2 3 | ints has the following contents: 0, 1, 2, 3, 99, 5, 6, 7, 8, 9 |
-Delix