Skip to content

Instantly share code, notes, and snippets.

@sixthgear sixthgear/vect.h
Created Dec 21, 2011

Embed
What would you like to do?
Generic Vector Type in C
#ifndef VECT_H
#define VECT_H
/*
* vect.h -- type-safe generic dynamic array
* made by sixthgear. BSD Licenced.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VECT_CAPACITY 256
/* vector type for use in type-unsafe functions */
/* macros will generate type-safe functions for each type called in */
/* VECT_GENERATE_TYPE */
typedef struct {
int size;
int capacity;
size_t data_size;
void *data;
} vect;
void
vect_err(const char *error)
{
fprintf(stderr, "%s\n", error);
exit(1);
}
vect *
vect_init(size_t data_size, unsigned int capacity)
{
vect *v = malloc(sizeof(vect));
if (v == NULL)
vect_err("vect_init: allocation of vect failed.");
if (capacity == 0)
capacity = VECT_CAPACITY;
v->data = malloc(data_size * capacity);
if (v->data == NULL)
vect_err("vect_init: allocation of vect data failed.");
v->data_size = data_size;
v->size = 0;
v->capacity = capacity;
return v;
}
void
vect_free(void *v)
{
free(((vect *)v)->data);
free(((vect *)v));
}
void
vect_resize(vect *v)
{
v->capacity *= 2; /* double capacity */
v->data = realloc(v->data, v->data_size * v->capacity);
if (v->data == NULL)
vect_err("vect_resize: resize failed.");
}
unsigned int
vect_chk_bounds(vect *v, unsigned int pos) {
return (pos < v->size);
}
unsigned int
vect_at(vect *v, unsigned int pos)
{
if (!vect_chk_bounds((vect*)v, pos))
vect_err("vect_at: out of bounds.");
return pos;
}
unsigned int
vect_set(vect *v, unsigned int pos)
{
if (!vect_chk_bounds((vect*)v, pos))
vect_err("vect_set: out of bounds.");
return pos;
}
unsigned int
vect_push(vect *v)
{
if (v->size == v->capacity)
vect_resize(v);
return v->size++;
}
unsigned int
vect_pop(vect *v)
{
if (v->size == 0)
vect_err("vect_pop: underflow.");
return --v->size;
}
unsigned int
vect_rem(vect *v, unsigned int pos)
{
if (!vect_chk_bounds((vect*)v, pos))
vect_err("vect_rem: out of bounds.");
char *dest = (char *) v->data + (v->data_size * pos);
char *src = dest + v->data_size;
size_t num_bytes = v->data_size * (v->size - pos - 1);
memmove(dest, src, num_bytes);
v->size--;
return pos;
}
unsigned int
vect_ins(vect *v, unsigned int pos)
{
if (!vect_chk_bounds((vect*)v, pos))
vect_err("vect_rem: out of bounds.");
char *src = (char *) v->data + (v->data_size * pos);
char *dest = src + v->data_size;
size_t num_bytes = v->data_size * (v->size - pos);
memmove(dest, src, num_bytes);
v->size++;
return pos;
}
/* vector type for use in type-safe functions */
/* functions for each type must be generated by VECT_GENERATE_TYPE(type) */
/* or VECT_GENERATE_NAME(type, name) for pointer types or multiple qualifiers */
#define VECT_GENERATE_TYPE(TYPE) VECT_GENERATE_NAME(TYPE, TYPE)
#define VECT_GENERATE_NAME(TYPE, NAME) \
typedef struct { \
int size; \
int capacity; \
size_t data_size; \
TYPE *data; \
} vect_##NAME; \
vect_##NAME * \
vect_init_##NAME(unsigned int capacity) \
{ \
return (vect_##NAME *) vect_init(sizeof(TYPE), capacity); \
} \
TYPE * \
vect_ptr_##NAME(vect_##NAME *v, unsigned int pos) \
{ \
return v->data + vect_at((vect *)v, pos); \
} \
TYPE \
vect_at_##NAME(vect_##NAME *v, unsigned int pos) \
{ \
return v->data[vect_at((vect *)v, pos)]; \
} \
void \
vect_push_##NAME(vect_##NAME *v, TYPE value) \
{ \
v->data[vect_push((vect *)v)] = value; \
} \
void \
vect_set_##NAME(vect_##NAME *v, unsigned int pos, TYPE value) \
{ \
v->data[vect_set((vect *)v, pos)] = value; \
} \
TYPE \
vect_pop_##NAME(vect_##NAME *v) \
{ \
return v->data[vect_pop((vect *) v)]; \
} \
void \
vect_rem_##NAME(vect_##NAME *v, unsigned int pos) \
{ \
vect_rem((vect *) v, pos); \
} \
void \
vect_ins_##NAME(vect_##NAME *v, unsigned int pos, TYPE value) \
{ \
v->data[vect_ins((vect *) v, pos)] = value; \
} \
void \
vect_cat_##NAME(vect_##NAME *v1, vect_##NAME *v2) \
{ \
return; \
}
#endif
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include "vect.h"
#include "minunit.h"
int tests_run = 0;
VECT_GENERATE_TYPE(int)
VECT_GENERATE_NAME(uint64_t, ui64)
static char * test_resize() {
int result;
vect_int *vi = vect_init_int(1);
vect_push_int(vi, 1);
vect_push_int(vi, 2);
vect_push_int(vi, 3);
vect_push_int(vi, 4);
vect_push_int(vi, 5);
result = vi->capacity;
vect_free(vi);
mu_assert("error: vi->capacity != 8", result == 8);
return 0;
}
static char * test_fibs_build() {
/* build fibs sequence */
uint64_t result;
vect_ui64 *vl = vect_init_ui64(8);
uint64_t a = 0;
uint64_t b = 1;
vect_push_ui64(vl, 0);
for(int i=1; i<94; i++) {
uint64_t tmp = a;
a = a + b;
b = tmp;
vect_push_ui64(vl, a);
}
result = vect_at_ui64(vl, vl->size-1);
vect_free(vl);
mu_assert("error: result != 12200160415121876738", result == 12200160415121876738ULL);
return 0;
}
static char * all_tests() {
mu_run_test(test_resize);
mu_run_test(test_fibs_build);
return 0;
}
int
main()
{
char *result = all_tests();
if (result != 0)
printf("%s\n", result);
else
printf("ALL TESTS PASSED\n");
printf("Tests run: %d\n", tests_run);
return result != 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.