Add first parts of interface config handling

19 files changed, 741 insertions, 104 deletions

diff --git a/meson.build b/meson.build
index f8089e4..81cf8ee 100644
--- a/meson.build
+++ b/meson.build
@@ -1,5 +1,4 @@
-project('pnc', 'c', default_options : ['c_std=c11'])
-add_project_arguments('-D_DEFAULT_SOURCE', language : 'c')
+project('neco', 'c', default_options : ['c_std=gnu11'])
 
 cc = meson.get_compiler('c')
 ubox_dep = cc.find_library('ubox')
diff --git a/src/config-ini.c b/src/config-ini.c
index 30275fa..0461e13 100644
--- a/src/config-ini.c
+++ b/src/config-ini.c
@@ -1,5 +1,4 @@
 #include "config-ini.h"
-#include "types.h"
 
 #include <ctype.h>
 #include <errno.h>
diff --git a/src/config-ini.h b/src/config-ini.h
index 58f6608..48400fd 100644
--- a/src/config-ini.h
+++ b/src/config-ini.h
@@ -4,19 +4,19 @@
 
 #include <stdio.h>
 
-typedef struct {
+typedef struct _ini_field {
 	struct list_head node;
 	char *key;
 	char *value;
 } ini_field_t;
 
-typedef struct {
+typedef struct _ini_section {
 	struct list_head node;
 	struct list_head fields;
 	char *name;
 } ini_section_t;
 
-typedef struct {
+typedef struct _ini_file {
 	struct list_head sections;
 } ini_file_t;
 
diff --git a/src/config-load.c b/src/config-load.c
index 28b5953..92abca0 100644
--- a/src/config-load.c
+++ b/src/config-load.c
@@ -1,10 +1,11 @@
 #include "config-load.h"
-#include "config-ini.h"
-#include "types.h"
+#include "config-process.h"
+#include "device.h"
+#include "util.h"
 
-#include <libubox/avl.h>
 #include <libubox/avl-cmp.h>
 
+#include <sys/stat.h>
 #include <sys/types.h>
 #include <dirent.h>
 #include <errno.h>
@@ -13,22 +14,9 @@
 #include <string.h>
 #include <unistd.h>
 
-typedef enum {
-	LOAD_TYPE_INTERFACE,
-	LOAD_TYPE_SUBCONFIG,
-	LOAD_TYPE_GENERATOR,
-	LOAD_TYPE_DEVICE,
-	N_LOAD_TYPES,
-} load_type_t;
-
-typedef struct {
-	struct avl_node node;
-	char *type;
-	ini_file_t *data;
-} load_object_t;
-
-typedef struct {
-	struct avl_tree objects[N_LOAD_TYPES];
+typedef struct _load_ctx {
+	struct avl_tree subtypes;
+	struct avl_tree devices;
 } load_ctx_t;
 
 static const char * extname(const char *filename) {
@@ -36,29 +24,24 @@ static const char * extname(const char *filename) {
 	return dot ? (dot+1) : NULL;
 }
 
-static void free_object(load_object_t *obj) {
-	free_ini_file(obj->data);
-	free(obj->type);
-	free(NODE_NAME(obj));
-	free(obj);
+static bool isfile(int fd) {
+	struct stat buf;
+	if (fstat(fd, &buf) < 0)
+		return false;
+
+	return (buf.st_mode & S_IFMT) == S_IFREG;
 }
 
 static bool read_config_file(load_ctx_t *ctx, int dirfd, const char *filename) {
 	const char *ext = extname(filename);
-	if (!ext) {
-		errno = EINVAL;
-		return false;
-	}
+	if (!ext)
+		return true;
 
-	load_type_t type;
-	if (strcmp(ext, "interface") == 0)
-		type = LOAD_TYPE_INTERFACE;
-	else if (strcmp(ext, "sub") == 0)
-		type = LOAD_TYPE_SUBCONFIG;
-	else if (strcmp(ext, "gen") == 0)
-		type = LOAD_TYPE_GENERATOR;
-	else if (strcmp(ext, "bridge") == 0)
-		type = LOAD_TYPE_DEVICE;
+	struct avl_tree *target_tree;
+	if (strcmp(ext, "sub") == 0 || strcmp(ext, "gen") == 0)
+		target_tree = &ctx->subtypes;
+	else if (get_device_type(ext))
+		target_tree = &ctx->devices;
 	else
 		return true;
 	
@@ -66,6 +49,11 @@ static bool read_config_file(load_ctx_t *ctx, int dirfd, const char *filename) {
 	if (fd < 0)
 		return false;
 	
+	if (!isfile(fd)) {
+		close(fd);
+		return true;
+	}
+
 	FILE *f = fdopen(fd, "r");
 	if (!f) {
 		close(fd);
@@ -78,7 +66,7 @@ static bool read_config_file(load_ctx_t *ctx, int dirfd, const char *filename) {
 	if (!data)
 		return false;
 	
-	load_object_t *obj = calloc(1, sizeof(*obj));
+	config_object_t *obj = calloc(1, sizeof(*obj));
 	if (!obj) {
 		free_ini_file(data);
 		return false;
@@ -87,18 +75,18 @@ static bool read_config_file(load_ctx_t *ctx, int dirfd, const char *filename) {
 
 	char *name = strndup(filename, (ext - filename) - 1);
 	if (!name) {
-		free_object(obj);
+		config_object_free(obj);
 		return false;
 	}
 	NODE_NAME(obj) = name;
 
 	obj->type = strdup(ext);
 	if (!obj->type) {
-		free_object(obj);
+		config_object_free(obj);
 		return false;
 	}
 
-	avl_insert(&ctx->objects[type], &obj->node);
+	avl_insert(target_tree, &obj->node);
 
 	return true;
 }
@@ -111,10 +99,8 @@ static bool read_config_dir(load_ctx_t *ctx, const char *path) {
 	int fd = dirfd(dir);
 
 	struct dirent *ent;
-	while ((ent = readdir(dir)) != NULL) {
-		if (ent->d_type == DT_REG)
-			read_config_file(ctx, fd, ent->d_name);
-	}
+	while ((ent = readdir(dir)) != NULL)
+		read_config_file(ctx, fd, ent->d_name);
 
 	closedir(dir);
 
@@ -123,23 +109,21 @@ static bool read_config_dir(load_ctx_t *ctx, const char *path) {
 
 bool read_config(const char *path) {
 	load_ctx_t ctx;
-	for (size_t i = 0; i < N_LOAD_TYPES; i++)
-		avl_init(&ctx.objects[i], avl_strcmp, true, NULL);
+	avl_init(&ctx.subtypes, avl_strcmp, true, NULL);
+	avl_init(&ctx.devices, avl_strcmp, true, NULL);
 	
 	bool ret = read_config_dir(&ctx, path);
 
-	for (size_t i = 0; i < N_LOAD_TYPES; i++) {
-		load_object_t *obj;
-		avl_for_each_element(&ctx.objects[i], obj, node) {
-			printf("%s(%u): %s\n", obj->type, (unsigned)i, NODE_NAME(obj));
-		}
-	}
+	struct avl_tree *subtypes = config_process_subtypes(&ctx.subtypes);
+	struct avl_tree *devices = config_process_devices(&ctx.devices);
 
-	for (size_t i = 0; i < N_LOAD_TYPES; i++) {
-		load_object_t *obj, *tmp;
-		avl_for_each_element_safe(&ctx.objects[i], obj, node, tmp)
-			free_object(obj);
-	}
+	free(subtypes);
+
+	device_t *dev, *tmp;
+	avl_remove_all_elements(devices, dev, node, tmp)
+		dev->type->free_device(dev);
+
+	free(devices);
 
 	return ret;
 }
diff --git a/src/config-process.c b/src/config-process.c
new file mode 100644
index 0000000..e71b228
--- /dev/null
+++ b/src/config-process.c
@@ -0,0 +1,135 @@
+#include "config-process.h"
+#include "device.h"
+#include "keywords.h"
+#include "util.h"
+
+#include <libubox/avl-cmp.h>
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+typedef struct _process_ctx {
+	struct avl_tree *ret;
+} process_ctx_t;
+
+typedef struct _config_subtype {
+	struct avl_node node;
+} config_subtype_t;
+
+void config_object_free(config_object_t *obj) {
+	free_ini_file(obj->data);
+	free(obj->type);
+	free(NODE_NAME(obj));
+	free(obj);
+}
+
+static bool subtype_supported(const process_ctx_t *ctx, const char *type) {
+	switch (lookup_keyword(type)) {
+	case KW_Properties:
+	case KW_Generate:
+	case KW_Static:
+	case KW_DHCP:
+	case KW_DHCPv6:
+		return true;
+
+	default:
+		return avl_find(ctx->ret, type);
+	}
+}
+
+static config_subtype_t * config_process_subtype(const process_ctx_t *ctx, config_object_t *obj) {
+	ini_section_t *section;
+	list_for_each_entry(section, &obj->data->sections, node) {
+		printf("%s %s %i\n", NODE_NAME(obj), section->name, subtype_supported(ctx, section->name));
+
+		if (!subtype_supported(ctx, section->name))
+			return NULL;
+	}
+
+	config_subtype_t *ret = calloc(1, sizeof(*ret));
+	if (!ret)
+		return NULL;
+
+	char *name = strdup(NODE_NAME(obj));
+	if (!name) {
+		free(ret);
+		return NULL;
+	}
+
+	NODE_NAME(ret) = name;
+
+	return ret;
+}
+
+struct avl_tree * config_process_subtypes(struct avl_tree *sub) {
+	process_ctx_t ctx;
+	ctx.ret = calloc(1, sizeof(*ctx.ret));
+	if (!ctx.ret)
+		return NULL;
+
+	avl_init(ctx.ret, avl_strcmp, false, NULL);
+
+	while (true) {
+		size_t processed = 0;
+
+		config_object_t *obj, *tmp;
+		avl_for_each_element_safe(sub, obj, node, tmp) {
+			config_subtype_t *t = config_process_subtype(&ctx, obj);
+			if (!t)
+				continue;
+
+			avl_delete(sub, &obj->node);
+			config_object_free(obj);
+
+			avl_insert(ctx.ret, &t->node);
+
+			processed++;
+		}
+
+		if (!processed)
+			break;
+	}
+
+	return ctx.ret;
+}
+
+static device_t * config_process_device(config_object_t *obj) {
+	const device_type_t *type = get_device_type(obj->type);
+
+	assert(type != NULL);
+
+	return type->process_config(NODE_NAME(obj), obj->data);
+}
+
+struct avl_tree * config_process_devices(struct avl_tree *devices) {
+	process_ctx_t ctx;
+	ctx.ret = calloc(1, sizeof(*ctx.ret));
+	if (!ctx.ret)
+		return NULL;
+
+	avl_init(ctx.ret, avl_strcmp, false, NULL);
+
+	while (true) {
+		size_t processed = 0;
+
+		config_object_t *obj, *tmp;
+		avl_for_each_element_safe(devices, obj, node, tmp) {
+			device_t *device = config_process_device(obj);
+			if (!device)
+				continue;
+
+			avl_delete(devices, &obj->node);
+			config_object_free(obj);
+
+			avl_insert(ctx.ret, &device->node);
+
+			processed++;
+		}
+
+		if (!processed)
+			break;
+	}
+
+	return ctx.ret;
+}
diff --git a/src/config-process.h b/src/config-process.h
new file mode 100644
index 0000000..501e765
--- /dev/null
+++ b/src/config-process.h
@@ -0,0 +1,15 @@
+#pragma once
+
+#include "config-ini.h"
+
+#include <libubox/avl.h>
+
+typedef struct _config_object {
+	struct avl_node node;
+	char *type;
+	ini_file_t *data;
+} config_object_t;
+
+void config_object_free(config_object_t *obj);
+struct avl_tree * config_process_subtypes(struct avl_tree *sub);
+struct avl_tree * config_process_devices(struct avl_tree *devices);
diff --git a/src/device-bridge.c b/src/device-bridge.c
new file mode 100644
index 0000000..f973dbf
--- /dev/null
+++ b/src/device-bridge.c
@@ -0,0 +1,15 @@
+#include "device.h"
+
+static device_t * bridge_process_config(const char *name, const ini_file_t *config) {
+	printf("Bridge: %s\n", name);
+	return NULL;
+}
+
+device_type_t device_type_bridge = {
+	.process_config = bridge_process_config,
+};
+
+__attribute__((constructor))
+static void bridge_constructor(void) {
+	register_device_type("bridge", &device_type_bridge);
+}
diff --git a/src/device-interface.c b/src/device-interface.c
new file mode 100644
index 0000000..5ac7cee
--- /dev/null
+++ b/src/device-interface.c
@@ -0,0 +1,202 @@
+#include "device.h"
+#include "keywords.h"
+#include "util.h"
+#include "vector.h"
+
+#include <arpa/inet.h>
+#include <netinet/ether.h>
+#include <netinet/in.h>
+
+#include <assert.h>
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+
+static device_type_t device_type_interface;
+
+typedef struct _ipaddr {
+	int af;
+	union {
+		struct in_addr addr4;
+		struct in6_addr addr6;
+	};
+} ipaddr_t;
+
+typedef struct _ipprefix {
+	ipaddr_t addr;
+	uint8_t plen;
+} ipaddr_prefix_t;
+
+typedef VECTOR(ipaddr_prefix_t) ipaddr_prefix_vector_t;
+
+typedef struct _device_interface {
+	device_t device;
+
+	struct ether_addr macaddr;
+	uint16_t mtu;
+
+	ipaddr_prefix_vector_t addrs;
+} device_interface_t;
+
+static unsigned long strtoul_safe(const char *str) {
+	char *endptr;
+
+	errno = 0;
+	unsigned long val = strtoul(str, &endptr, 10);
+	if (endptr == str || *endptr)
+		errno = EINVAL;
+
+	return val;
+}
+
+static bool parse_address(ipaddr_t *addr, const char *str) {
+	if (inet_pton(AF_INET, str, &addr->addr4)) {
+		addr->af = AF_INET;
+		return true;
+	}
+
+	if (inet_pton(AF_INET6, str, &addr->addr6)) {
+		addr->af = AF_INET6;
+		return true;
+	}
+
+	return false;
+}
+
+static bool parse_prefix(ipaddr_prefix_t *prefix, const char *str, bool allow_host) {
+	const char *slash = strrchr(str, '/');
+	if (!slash)
+		return false;
+
+	size_t len = slash - str;
+	char buf[len+1];
+	memcpy(buf, str, len);
+	buf[len] = 0;
+
+	if (!parse_address(&prefix->addr, buf))
+		return false;
+
+	long plen = strtoul_safe(slash + 1);
+	if (errno)
+		return false;
+
+	switch (prefix->addr.af) {
+	case AF_INET:
+		if (plen > 32)
+			return false;
+		break;
+
+	case AF_INET6:
+		if (plen > 128)
+			return false;
+		break;
+
+	default:
+		assert(false);
+		__builtin_unreachable();
+	}
+
+	prefix->plen = plen;
+
+	// TODO: Implement allow_host
+
+	return true;
+}
+
+static bool process_section_device(device_interface_t *iface, const ini_section_t *section) {
+	ini_field_t *field;
+
+	list_for_each_entry(field, &section->fields, node) {
+		switch (lookup_keyword(field->key)) {
+		default:
+			fprintf(stderr, "interface: [Device]: unknown field %s\n", field->key);
+		}
+	}
+
+	return true;
+}
+
+static bool process_section_static(device_interface_t *iface, const ini_section_t *section) {
+	ini_field_t *field;
+
+	list_for_each_entry(field, &section->fields, node) {
+		switch (lookup_keyword(field->key)) {
+		case KW_Address: {
+			ipaddr_prefix_t p;
+			if (!parse_prefix(&p, field->value, true)) {
+				fprintf(stderr, "interface: [Static]: unable to parse Address %s\n", field->value);
+				break;
+			}
+
+			if (!VECTOR_ADD(iface->addrs, p)) {
+				fprintf(stderr, "interface: [Static]: adding address failed\n");
+				return false;
+			}
+
+			break;
+		}
+
+		default:
+			fprintf(stderr, "interface: [Static]: unknown field %s\n", field->key);
+		}
+	}
+
+	return true;
+}
+
+static void interface_free_device(device_t *dev) {
+	device_interface_t *iface = container_of(dev, device_interface_t, device);
+
+	VECTOR_FREE(iface->addrs);
+	free(NODE_NAME(dev));
+	free(iface);
+}
+
+static device_t * interface_process_config(const char *name, const ini_file_t *config) {
+	device_interface_t *iface = calloc(1, sizeof(*iface));
+	if (!iface)
+		return NULL;
+
+	device_t *dev = &iface->device;
+	dev->type = &device_type_interface;
+
+	NODE_NAME(dev) = strdup(name);
+	if (!NODE_NAME(dev)) {
+		free(iface);
+		return NULL;
+	}
+
+	const ini_section_t *section;
+	list_for_each_entry(section, &config->sections, node) {
+		switch (lookup_keyword(section->name)) {
+		case KW_Device:
+			if (!process_section_device(iface, section))
+				goto err;
+			break;
+
+		case KW_Static:
+			if (!process_section_static(iface, section))
+				goto err;
+			break;
+
+		default:
+			fprintf(stderr, "interface: unknown section %s\n", section->name);
+		}
+	}
+
+	return dev;
+
+err:
+	interface_free_device(dev);
+	return NULL;
+}
+
+static device_type_t device_type_interface = {
+	.process_config = interface_process_config,
+	.free_device = interface_free_device,
+};
+
+__attribute__((constructor))
+static void interface_constructor(void) {
+	register_device_type("interface", &device_type_interface);
+}
diff --git a/src/device.c b/src/device.c
new file mode 100644
index 0000000..a773036
--- /dev/null
+++ b/src/device.c
@@ -0,0 +1,15 @@
+#include "device.h"
+#include "util.h"
+
+#include <libubox/avl-cmp.h>
+
+AVL_TREE(device_types, avl_strcmp, false, NULL);
+
+void register_device_type(const char *name, device_type_t *device_type) {
+	NODE_NAME(device_type) = (char *)name;
+	avl_insert(&device_types, &device_type->node);
+}
+
+const device_type_t * get_device_type(const char *name) {
+	return avl_find_element(&device_types, name, (device_type_t *)NULL, node);
+}
diff --git a/src/device.h b/src/device.h
new file mode 100644
index 0000000..f437021
--- /dev/null
+++ b/src/device.h
@@ -0,0 +1,23 @@
+#pragma once
+
+#include "config-ini.h"
+
+#include <libubox/avl.h>
+
+extern struct avl_tree device_types;
+
+typedef struct _device_type device_type_t;
+
+typedef struct _device {
+	struct avl_node node;
+	const device_type_t *type;
+} device_t;
+
+struct _device_type {
+	struct avl_node node;
+	device_t * (*process_config)(const char *name, const ini_file_t *config);
+	void (*free_device)(device_t *device);
+};
+
+void register_device_type(const char *name, device_type_t *device_type);
+const device_type_t * get_device_type(const char *name);
diff --git a/src/keywords.c b/src/keywords.c
new file mode 100644
index 0000000..12393bd
--- /dev/null
+++ b/src/keywords.c
@@ -0,0 +1,31 @@
+#include "keywords.h"
+
+#include <libubox/utils.h>
+
+#include <stdlib.h>
+#include <string.h>
+
+static const char *const keywords[] = {
+
+#define KW(kw) #kw,
+#include "keywords.def"
+#undef KW
+
+};
+
+static int compare_keywords(const void *a, const void *b) {
+	const char *const *ea = a, *const *eb = b;
+	return strcmp(*ea, *eb);
+}
+
+keyword_t lookup_keyword(const char *keyword) {
+	const char *const *entry = bsearch(
+		&keyword, keywords, ARRAY_SIZE(keywords), sizeof(const char *),
+		compare_keywords
+	);
+
+	if (!entry)
+		return UNKNOWN_KEYWORD;
+
+	return (keyword_t) (entry - keywords + 1);
+}
diff --git a/src/keywords.def b/src/keywords.def
new file mode 100644
index 0000000..0dbd866
--- /dev/null
+++ b/src/keywords.def
@@ -0,0 +1,9 @@
+/* Config section and field names; keep sorted! */
+
+KW(Address)
+KW(DHCP)
+KW(DHCPv6)
+KW(Device)
+KW(Generate)
+KW(Properties)
+KW(Static)
diff --git a/src/keywords.h b/src/keywords.h
new file mode 100644
index 0000000..05d809e
--- /dev/null
+++ b/src/keywords.h
@@ -0,0 +1,12 @@
+#pragma once
+
+typedef enum _keyword {
+	UNKNOWN_KEYWORD = 0,
+
+#define KW(kw) KW_##kw,
+#include "keywords.def"
+#undef KW
+
+} keyword_t;
+
+keyword_t lookup_keyword(const char *keyword);
diff --git a/src/meson.build b/src/meson.build
index c24ca21..b088e39 100644
--- a/src/meson.build
+++ b/src/meson.build
@@ -1,7 +1,13 @@
 src = [
-	'pnc.c',
+	'neco.c',
 	'config-ini.c',
 	'config-load.c',
+	'config-process.c',
+	'device.c',
+	'device-bridge.c',
+	'device-interface.c',
+	'keywords.c',
+	'vector.c',
 ]
 
-executable('pnc', sources: src, dependencies: [ubox_dep])
+executable('neco', sources: src, dependencies: [ubox_dep])
diff --git a/src/pnc.c b/src/neco.c
index 942ba2f..942ba2f 100644
--- a/src/pnc.c
+++ b/src/neco.c
diff --git a/src/types.h b/src/types.h
deleted file mode 100644
index cabaac6..0000000
--- a/src/types.h
+++ /dev/null
@@ -1,38 +0,0 @@
-#pragma once
-
-#include <libubox/avl.h>
-
-#include <net/if.h>
-#include <stdint.h>
-
-typedef struct {
-	uint8_t addr[6];
-} macaddr_t;
-
-#define NODE_NAME(c) (*(char **)&(c)->node.key)
-
-typedef struct {
-	struct avl_tree subtypes;
-	struct avl_tree interfaces;
-} config_t;
-
-typedef struct {
-	struct avl_node node;
-} subconfig_type_t;
-
-typedef struct {
-	struct avl_node node;
-	struct avl_tree subconfigs;
-
-	macaddr_t macaddr;
-	uint16_t mtu;
-} interface_config_t;
-
-typedef struct {
-	struct avl_node node;
-	const char *type;
-} interface_subconfig_t;
-
-
-typedef struct {
-} interface_generator_t;
diff --git a/src/util.h b/src/util.h
new file mode 100644
index 0000000..31b13b6
--- /dev/null
+++ b/src/util.h
@@ -0,0 +1,3 @@
+#pragma once
+
+#define NODE_NAME(c) (*(char **)&(c)->node.key)
diff --git a/src/vector.c b/src/vector.c
new file mode 100644
index 0000000..41cd0cc
--- /dev/null
+++ b/src/vector.c
@@ -0,0 +1,114 @@
+/**
+   \file
+
+   Typesafe dynamically sized arrays
+*/
+
+
+#include "vector.h"
+
+#include <errno.h>
+#include <stdint.h>
+#include <string.h>
+
+/** The minimum number of elements to allocate even when fewer elements are used */
+#define MIN_VECTOR_ALLOC 4
+
+/**
+   Multiplies two size_t values, checking for overflows
+
+   Both arguments are limited to the size of a uint32_t (to keep the check simple)
+
+   Returns SIZE_MAX and sets errno on failure.
+*/
+static inline size_t mul_check(size_t members, size_t size) {
+	uint64_t v = (uint64_t)members * size;
+
+	if (members > UINT32_MAX || size > UINT32_MAX || v > SIZE_MAX) {
+		errno = EOVERFLOW;
+		return SIZE_MAX;
+	}
+
+	return v;
+}
+
+/**
+   Reallocates a block of memory for an array on the heap
+
+   May fail with EOVERFLOW (when members or size does not fit into a uint32_t,
+   or their product does not fit into a size_t) or ENOMEM.
+*/
+static inline void * realloc_array(void *ptr, size_t members, size_t size) {
+	errno = 0;
+	size_t array_size = mul_check(members, size);
+	if (errno)
+		return NULL;
+
+	return realloc(ptr, array_size);
+}
+
+/**
+   Resizes a vector
+
+   Vector allocations are always powers of 2.
+
+   Internal function, use VECTOR_RESIZE() instead.
+*/
+bool _vector_resize(vector_desc_t *desc, void **data, size_t n, size_t elemsize) {
+	desc->length = n;
+
+	size_t alloc = desc->allocated;
+
+	if (!alloc) {
+		alloc = MIN_VECTOR_ALLOC;
+		n = n*3/2;
+	}
+
+	while (alloc < n) {
+		alloc <<= 1;
+		if (!alloc) {
+			errno = ENOMEM;
+			return false;
+		}
+	}
+
+	if (alloc != desc->allocated) {
+		desc->allocated = alloc;
+		void *tmp = realloc_array(*data, alloc, elemsize);
+		if (!tmp)
+			return false;
+
+		*data = tmp;
+	}
+
+	return true;
+}
+
+/**
+   Inserts an element into a vector
+
+   Internal function, use VECTOR_INSERT() and VECTOR_ADD() instead.
+*/
+bool _vector_insert(vector_desc_t *desc, void **data, void *element, size_t pos, size_t elemsize) {
+	if (!_vector_resize(desc, data, desc->length+1, elemsize))
+		return false;
+
+	void *p = *data + pos*elemsize;
+
+	memmove(p+elemsize, p, (desc->length-pos-1)*elemsize);
+	memcpy(p, element, elemsize);
+
+	return true;
+}
+
+/**
+   Deletes an element from a vector
+
+   Internal function, use VECTOR_DELETE() instead.
+*/
+void _vector_delete(vector_desc_t *desc, void **data, size_t pos, size_t elemsize) {
+	void *p = *data + pos*elemsize;
+	memmove(p, p+elemsize, (desc->length-pos-1)*elemsize);
+
+	desc->length--;
+}
diff --git a/src/vector.h b/src/vector.h
new file mode 100644
index 0000000..02ea804
--- /dev/null
+++ b/src/vector.h
@@ -0,0 +1,113 @@
+/**
+   \file
+
+   Typesafe dynamically sized arrays
+*/
+
+
+#pragma once
+
+#include <stdbool.h>
+#include <stdlib.h>
+
+/** A vector descriptor */
+typedef struct _vector_desc {
+	size_t allocated;		/**< The number of elements currently allocated */
+	size_t length;			/**< The actual number of elements in the vector */
+} vector_desc_t;
+
+/**
+   A type for a vector of \e type elements
+
+   \hideinitializer
+*/
+#define VECTOR(type) struct {	\
+	vector_desc_t desc;	\
+	type *data;		\
+}
+
+bool _vector_resize(vector_desc_t *desc, void **data, size_t n, size_t elemsize);
+bool _vector_insert(vector_desc_t *desc, void **data, void *element, size_t pos, size_t elemsize);
+void _vector_delete(vector_desc_t *desc, void **data, size_t pos, size_t elemsize);
+
+/**
+   Resizes the vector \e a to \e n elements
+
+   \hideinitializer
+*/
+#define VECTOR_RESIZE(v, n)  ({				\
+	__typeof__(v) *_v = &(v);			\
+	_vector_resize(&_v->desc, (void **)&_v->data, (n), sizeof(*_v->data)); \
+})
+
+/**
+   Frees all resources used by the vector \e v
+
+   \hideinitializer
+*/
+#define VECTOR_FREE(v) free((v).data)
+
+/**
+   Returns the number of elements in the vector \e v
+
+   \hideinitializer
+*/
+#define VECTOR_LEN(v) ((v).desc.length)
+
+/**
+   Returns the element with index \e i in the vector \e v
+
+   \hideinitializer
+*/
+#define VECTOR_INDEX(v, i) ((v).data[i])
+
+/**
+   Returns a pointer to the vector elements of \e v
+
+   \hideinitializer
+*/
+#define VECTOR_DATA(v) ((v).data)
+
+/**
+   Inserts the element \e elem at index \e pos of vector \e v
+
+   \hideinitializer
+*/
+#define VECTOR_INSERT(v, elem, pos) ({			\
+	__typeof__(v) *_v = &(v);			\
+	__typeof__(*_v->data) _e = (elem);		\
+	_vector_insert(&_v->desc, (void **)&_v->data, &_e, (pos), sizeof(_e)); \
+})
+
+/**
+   Adds the element \e elem at the end of vector \e v
+
+   \hideinitializer
+*/
+#define VECTOR_ADD(v, elem) ({				\
+	__typeof__(v) *_v = &(v);			\
+	__typeof__(*_v->data) _e = (elem);		\
+	_vector_insert(&_v->desc, (void **)&_v->data, &_e, _v->desc.length, sizeof(_e)); \
+})
+
+/**
+   Deletes the element at index \e pos of vector \e v
+
+   \hideinitializer
+*/
+#define VECTOR_DELETE(v, pos) ({			\
+	__typeof__(v) *_v = &(v);			\
+	_vector_delete(&_v->desc, (void **)&_v->data, (pos), sizeof(*_v->data)); \
+})
+
+/**
+   Performs a binary search on the vector \e v, returning a pointer to a matching vector element
+
+   \hideinitializer
+*/
+#define VECTOR_BSEARCH(key, v, cmp) ({			\
+	__typeof__(v) *_v = &(v);			\
+	const __typeof__(*_v->data) *_key = (key);	\
+	int (*_cmp)(__typeof__(_key), __typeof__(_key)) = (cmp); \
+	(__typeof__(_v->data))bsearch(_key, _v->data, _v->desc.length, sizeof(*_v->data), (int (*)(const void *, const void *))_cmp); \
+})