Add vector macros

3 files changed, 156 insertions, 0 deletions

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 750883f..9e757c5 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -36,6 +36,7 @@ add_executable(fastd
   shell.c
   socket.c
   tuntap.c
+  vector.c
   ${BISON_fastd_config_parse_OUTPUTS}
 )
 set_property(TARGET fastd PROPERTY COMPILE_FLAGS "${FASTD_CFLAGS}")
diff --git a/src/vector.c b/src/vector.c
new file mode 100644
index 0000000..153327e
--- /dev/null
+++ b/src/vector.c
@@ -0,0 +1,73 @@
+/*
+  Copyright (c) 2012-2014, Matthias Schiffer <mschiffer@universe-factory.net>
+  All rights reserved.
+
+  Redistribution and use in source and binary forms, with or without
+  modification, are permitted provided that the following conditions are met:
+
+    1. Redistributions of source code must retain the above copyright notice,
+       this list of conditions and the following disclaimer.
+    2. Redistributions in binary form must reproduce the above copyright notice,
+       this list of conditions and the following disclaimer in the documentation
+       and/or other materials provided with the distribution.
+
+  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+  FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+
+#include "vector.h"
+
+#include <string.h>
+
+
+void _fastd_vector_alloc(fastd_vector_desc_t *desc, void **data, size_t n, size_t elemsize) {
+	desc->allocated = 16;
+
+	while (desc->allocated < n*3/2)
+		desc->allocated <<= 1;
+
+	desc->length = n;
+
+	*data = malloc(desc->allocated * elemsize);
+}
+
+void _fastd_vector_resize(fastd_vector_desc_t *desc, void **data, size_t n, size_t elemsize) {
+	desc->length = n;
+
+	size_t alloc = desc->allocated;
+
+	while (alloc < n)
+		alloc <<= 1;
+	while (alloc > n*3 && alloc > 16)
+		alloc >>= 1;
+
+	if (alloc != desc->allocated) {
+		desc->allocated = alloc;
+		*data = realloc(*data, alloc * elemsize);
+	}
+}
+
+void _fastd_vector_insert(fastd_vector_desc_t *desc, void **data, void *element, size_t pos, size_t elemsize) {
+	_fastd_vector_resize(desc, data, desc->length+1, elemsize);
+
+	void *p = *data + pos*elemsize;
+
+	memmove(p+elemsize, p, (desc->length-pos-1)*elemsize);
+	memcpy(p, element, elemsize);
+}
+
+void _fastd_vector_delete(fastd_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);
+
+	_fastd_vector_resize(desc, data, desc->length-1, elemsize);
+}
diff --git a/src/vector.h b/src/vector.h
new file mode 100644
index 0000000..0d9d9be
--- /dev/null
+++ b/src/vector.h
@@ -0,0 +1,82 @@
+/*
+  Copyright (c) 2012-2014, Matthias Schiffer <mschiffer@universe-factory.net>
+  All rights reserved.
+
+  Redistribution and use in source and binary forms, with or without
+  modification, are permitted provided that the following conditions are met:
+
+    1. Redistributions of source code must retain the above copyright notice,
+       this list of conditions and the following disclaimer.
+    2. Redistributions in binary form must reproduce the above copyright notice,
+       this list of conditions and the following disclaimer in the documentation
+       and/or other materials provided with the distribution.
+
+  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+  FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+
+#pragma once
+
+#include <stdlib.h>
+
+
+typedef struct fastd_vector_desc {
+	size_t allocated;
+	size_t length;
+} fastd_vector_desc_t;
+
+
+#define VECTOR(type)				\
+	struct {				\
+		fastd_vector_desc_t desc;	\
+		type *data;			\
+	}
+
+
+
+void _fastd_vector_alloc(fastd_vector_desc_t *desc, void **data, size_t n, size_t elemsize);
+void _fastd_vector_resize(fastd_vector_desc_t *desc, void **data, size_t n, size_t elemsize);
+void _fastd_vector_insert(fastd_vector_desc_t *desc, void **data, void *element, size_t pos, size_t elemsize);
+void _fastd_vector_delete(fastd_vector_desc_t *desc, void **data, size_t pos, size_t elemsize);
+
+
+#define VECTOR_ALLOC(v, n) ({						\
+			__typeof__(v) *_v = &(v);			\
+			_fastd_vector_alloc(&_v->desc, (void**)&_v->data, (n), sizeof(*_v->data)); \
+		})
+
+#define VECTOR_RESIZE(v, n)  ({						\
+			__typeof__(v) *_v = &(v);			\
+			_fastd_vector_resize(&_v->desc, (void**)&_v->data, (n), sizeof(*_v->data)); \
+		})
+
+#define VECTOR_FREE(v) free((v).data)
+
+#define VECTOR_LEN(v) ((v).desc.length)
+#define VECTOR_INDEX(v, i) ((v).data[i])
+#define VECTOR_DATA(v) ((v).data)
+
+#define VECTOR_INSERT(v, elem, pos) ({					\
+			__typeof__(v) *_v = &(v);			\
+			__typeof__(*_v->data) _e = (elem);		\
+			_fastd_vector_insert(&_v->desc, (void**)&_v->data, &_e, (pos), sizeof(_e)); \
+		})
+
+#define VECTOR_ADD(v, elem) ({						\
+			__typeof__(v) *_v = &(v);			\
+			VECTOR_INSERT(*_v, (elem), _v->desc.length);	\
+		})
+
+#define VECTOR_DELETE(v, pos) ({					\
+			__typeof__(v) *_v = &(v);			\
+			_fastd_vector_delete(&_v->desc, (void**)&_v->data, (pos), sizeof(*_v->data)); \
+		})