Skip to content

Instantly share code, notes, and snippets.

@loyd
Created December 3, 2014 17:43
Show Gist options
  • Save loyd/ac4f4e67d491c642386f to your computer and use it in GitHub Desktop.
Save loyd/ac4f4e67d491c642386f to your computer and use it in GitHub Desktop.
Indexed dynamic vector in C99.
/* Usage:
* int *nums = new_vec(int);
*
* vec_push(&nums, 1);
* vec_push(&nums, 5);
*
* for (int i = 0; i < vec_len(nums); ++i)
* printf("%d", nums[i]);
*
* Advanced usage:
* struct point { int x, y; };
*
* struct point *points = new_vec(struct point, 10);
*
* vec_push(&points, (struct point){20});
* vec_push(&points, ((struct point){20, 30}));
*
* points[0].y = 10;
* --vec_len(points);
*
* API:
* vec[index]
* new_vec(type)
* new_vec(type, init_capacity)
* vec_len(vec)
* vec_push(vec_ptr) → new length
* vec_pop(vec)
* free_vec(vec)
*/
#include <stdlib.h>
#define VEC_DEFAULT_CAPACITY 25
#define VEC_GROWTH_FACTOR 1.5
/////////////////////
// Implementation. //
/////////////////////
#define VEC_GET_CTOR(_1, _2, ctor, ...) ctor
#define new_vec(...) \
VEC_GET_CTOR(__VA_ARGS__, VEC_NEW, VEC_NEW_SHORT)(__VA_ARGS__)
#define VEC_NEW(type, init_capacity) new_vec(sizeof(type), (init_capacity))
#define VEC_NEW_SHORT(type) new_vec(sizeof(type), VEC_DEFAULT_CAPACITY)
#define vec_len(vec) (((size_t *)(void *)(vec))[-1])
#define vec_pop(vec) ((vec)[--vec_len(vec)])
#define vec_push(vec_p, elem) \
(vec_reserve((void **)(vec_p)), \
(*(vec_p))[vec_len(*(vec_p))] = (elem), \
++vec_len(*(vec_p)))
/* ________________________________________________________
* | elem_sz | capacity | length | v[0] | v[1] | v[2] | ...|
* ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
* <---------- header ----------><--------- data ---------->
*/
#define VEC_HEADER_SIZE (sizeof(size_t) * 3)
void *(new_vec)(size_t elem_sz, size_t init_capacity) {
size_t *res = malloc(VEC_HEADER_SIZE + elem_sz * init_capacity);
if (!res) abort();
res[0] = elem_sz;
res[1] = init_capacity;
res[2] = 0;
return res + 3;
}
void vec_reserve(void **vec_ptr) {
size_t *vec = *((size_t **)vec_ptr);
if (vec[-1] != vec[-2])
return;
size_t elem_sz = vec[-3];
size_t capacity = vec[-2] * VEC_GROWTH_FACTOR;
size_t len = vec[-1];
vec = realloc(vec - 3, VEC_HEADER_SIZE + elem_sz * capacity);
if (!vec) abort();
vec[0] = elem_sz;
vec[1] = capacity;
vec[2] = len;
*vec_ptr = vec + 3;
}
void free_vec(void *vec) {
if (vec)
free((char *)vec - VEC_HEADER_SIZE);
}
#include <assert.h>
#include "vector.c"
int main(void) {
// Simple.
int *nums = new_vec(int);
for (int i = 0; i < 10; ++i)
vec_push(&nums, i);
for (int i = 0; i < vec_len(nums); ++i)
assert(nums[i] == i);
// Advanced.
struct a_s { int x, y; };
struct a_s *as = new_vec(struct a_s, 1);
vec_push(&as, (struct a_s){10});
vec_push(&as, ((struct a_s){15, 20}));
assert(as[0].x == 10);
assert(as[1].x == 15);
assert(as[1].y == 20);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment