add stable vector

+ Allows references to elements to be stable over insertion

+ Doesn't implement all of the regular vec interface at the moment and
  requires slightly different iteration handling unfortunately, but
  maybe it's not too bad?

5 files changed, 232 insertions, 4 deletions

diff --git a/include/conts/conts.h b/include/conts/conts.h
index fb0094b..7f30873 100644
--- a/include/conts/conts.h
+++ b/include/conts/conts.h
@@ -10,5 +10,5 @@
 #define foreach(name, i, s)\
 	for (CONTS_JOIN(name, iter) i = CONTS_JOIN(name, begin)(s);\
 			!CONTS_JOIN(name, end)(s, i);\
-			i = CONTS_JOIN(name, next)(i))
+			i = CONTS_JOIN(name, next)(s, i))
 #endif /* CONTS_H */
diff --git a/include/conts/map.h b/include/conts/map.h
index 6b62498..d6a6188 100644
--- a/include/conts/map.h
+++ b/include/conts/map.h
@@ -264,8 +264,9 @@ static inline struct MAP_TUPLE *MAP(begin)(struct MAP_ROOT *root)
 	return MAP(find_next)(bucket, &bucket->nodes[0].t);
 }
 
-static inline struct MAP_TUPLE *MAP(next)(struct MAP_TUPLE *t)
+static inline struct MAP_TUPLE *MAP(next)(struct MAP_ROOT *root, struct MAP_TUPLE *t)
 {
+	(void)root;
 	struct MAP_NODE *node = CONTAINER_OF(t, struct MAP_NODE, t);
 	return MAP(find_next)(node->bucket, &(node + 1)->t);
 }
diff --git a/include/conts/sptree.h b/include/conts/sptree.h
index 53c3e73..15c6869 100644
--- a/include/conts/sptree.h
+++ b/include/conts/sptree.h
@@ -97,8 +97,9 @@ static inline SPTREE_TYPE *SPTREE(begin)(struct SPROOT *s)
 	return &SPTREE(first)(s->root)->data;
 }
 
-static inline SPTREE_TYPE *SPTREE(next)(SPTREE_TYPE *prev)
+static inline SPTREE_TYPE *SPTREE(next)(struct SPROOT *s, SPTREE_TYPE *prev)
 {
+	(void)s;
 	struct SPNODE *n = CONTAINER_OF(prev, struct SPNODE, data);
 	if (sp_right(n)) {
 		n = sp_right(n);
diff --git a/include/conts/spvec.h b/include/conts/spvec.h
new file mode 100644
index 0000000..8241455
--- /dev/null
+++ b/include/conts/spvec.h
@@ -0,0 +1,225 @@
+#ifndef SPVEC_TYPE
+#error "Need vector type"
+#endif
+
+#ifndef SPVEC_NAME
+#error "Need vector name"
+#endif
+
+#ifndef SPVEC_MALLOC
+#define SPVEC_MALLOC malloc
+#endif
+
+#ifndef SPVEC_CALLOC
+#define SPVEC_CALLOC calloc
+#endif
+
+#ifndef SPVEC_REALLOC
+#define SPVEC_REALLOC realloc
+#endif
+
+#ifndef SPVEC_FREE
+#define SPVEC_FREE free
+#endif
+
+#ifndef SPVEC_H
+#define SPVEC_H
+
+/* common part */
+
+#include <stdbool.h>
+#include <stdint.h>
+#include <string.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include "conts.h"
+
+static inline size_t conts_spvec_bucket(size_t i)
+{
+	if (i < 64)
+		return 0;
+
+	/** @todo fallback for __builtin_clzll, C23 has std_count_leading_zeroes
+	 * but might want to go for a simple loop for maximum compatibility? */
+	return (8 * sizeof(size_t)) - __builtin_clzll(i) - 6;
+}
+
+static inline size_t conts_spvec_size(size_t b)
+{
+	/* all buckets are pow2 in size, skipping the lowest 64 */
+	return 1 << (b + 6);
+}
+
+static inline size_t conts_spvec_elemnt(size_t b, size_t i)
+{
+	if (b == 0)
+		return i;
+
+	/* the adjusted index within a bucket is just the size of all previous
+	 * buckets subtracted away, and since each bucket is twice the size of
+	 * all previous buckets, just check the size of the previous bucket for
+	 * the index */
+	return i - conts_spvec_size(b - 1);
+}
+
+#endif /* SPVEC_H */
+
+#define SPVEC(a) CONTS_JOIN(SPVEC_NAME, a)
+
+#define SPVEC_STRUCT SPVEC_NAME
+struct SPVEC_STRUCT {
+	size_t n;
+	/* smallest bucket is of size 64, so ignore 2^6 */
+	SPVEC_TYPE *(buckets[sizeof(size_t) * 8 - 6]);
+};
+
+/* unfortunately I couldn't really think of a better way to implement foreach,
+ * as it's fairly slow to calculate the index from a pointer to an element and a
+ * the foreach wrapper can't really be modified to use separate element pointer
+ * and iterator, they have to be combined. Sorry :( */
+#define SPVEC_ITER SPVEC(iter)
+
+typedef struct {
+	size_t i;
+	SPVEC_TYPE *v;
+} SPVEC_ITER;
+
+
+static inline struct SPVEC_STRUCT SPVEC(create)()
+{
+	/** @todo a bit of a heavy structure to pass by value */
+	struct SPVEC_STRUCT s;
+	memset(&s, 0, sizeof(s));
+	return s;
+}
+
+static inline SPVEC_TYPE *SPVEC(reserve)(struct SPVEC_STRUCT *v, size_t n)
+{
+	if (v->n >= n) {
+		v->n = n;
+		return &v->buckets[0][0];
+	}
+
+	size_t b = conts_spvec_bucket(n);
+	for (size_t i = 0; i <= b; ++i) {
+		if (v->buckets[i])
+			continue;
+
+		v->buckets[i] = SPVEC_CALLOC(
+				conts_spvec_size(i == 0 ? 0 : b - 1),
+				sizeof(SPVEC_TYPE)
+		);
+
+		if (!v->buckets[i])
+			return NULL;
+	}
+
+	v->n = n;
+	return &v->buckets[0][0];
+}
+
+static inline size_t SPVEC(len)(struct SPVEC_STRUCT *v)
+{
+	return v->n;
+}
+
+static inline SPVEC_TYPE *SPVEC(at)(struct SPVEC_STRUCT *v, size_t i)
+{
+	assert(i < v->n && "out of vector bounds");
+	size_t b = conts_spvec_bucket(i);
+	size_t e = conts_spvec_elemnt(b, i);
+	return &v->buckets[b][e];
+}
+
+static inline SPVEC_TYPE *SPVEC(back)(struct SPVEC_STRUCT *v)
+{
+	assert(v->n);
+	return SPVEC(at)(v, v->n - 1);
+}
+
+static inline SPVEC_TYPE *SPVEC(pop)(struct SPVEC_STRUCT *v)
+{
+	assert(v->n && "attempting to pop empty vector");
+	v->n--;
+	return SPVEC(at)(v, v->n);
+}
+
+static inline SPVEC_TYPE *SPVEC(append)(struct SPVEC_STRUCT *v, SPVEC_TYPE n)
+{
+	/* don't update our size until after we've run reserve */
+	size_t ns = v->n + 1;
+	if (!v->buckets[conts_spvec_bucket(ns)]) {
+		/* try to allocate new bucket */
+		if (!SPVEC(reserve)(v, ns))
+			return NULL;
+	}
+
+	/* reserve might've already written our new size so this is kind of
+	 * duplicate work, but the code is a bit more readable like this */
+	v->n = ns;
+
+	SPVEC_TYPE *p = SPVEC(at)(v, v->n - 1);
+	*p = n;
+	return p;
+}
+
+static inline void SPVEC(remove)(struct SPVEC_STRUCT *v, size_t i)
+{
+	assert(v->n > i);
+
+	/* very slow :( */
+	for (size_t e = i; e < v->n - 1; ++e)
+		*SPVEC(at)(v, e) = *SPVEC(at)(v, e + 1);
+
+	v->n--;
+}
+
+static inline void SPVEC(reset)(struct SPVEC_STRUCT *v)
+{
+	v->n = 0;
+}
+
+static inline void SPVEC(destroy)(struct SPVEC_STRUCT *v) {
+	for (size_t i = 0; i < 8 * sizeof(size_t) - 6; ++i)
+		SPVEC_FREE(v->buckets[i]);
+}
+
+static inline void SPVEC(shrink)(struct SPVEC_STRUCT *v, size_t n)
+{
+	assert(v->n >= n);
+	v->n = n;
+}
+
+static inline SPVEC_ITER SPVEC(begin)(struct SPVEC_STRUCT *v)
+{
+	return (SPVEC_ITER){
+		.i = 0,
+		.v = SPVEC(at)(v, 0)
+	};
+}
+
+static inline bool SPVEC(end)(struct SPVEC_STRUCT *v, SPVEC_ITER i)
+{
+	(void)v;
+	return i.v == NULL;
+}
+
+static inline SPVEC_ITER SPVEC(next)(struct SPVEC_STRUCT *v, SPVEC_ITER i)
+{
+	return (SPVEC_ITER){
+		.i = i.i + 1,
+		.v = i.i + 1 == v->n ? NULL : SPVEC(at)(v, i.i + 1)
+	};
+}
+
+#undef SPVEC
+#undef SPVEC_TYPE
+#undef SPVEC_NAME
+#undef SPVEC_STRUCT
+#undef SPVEC_ITER
+
+#undef SPVEC_MALLOC
+#undef SPVEC_CALLOC
+#undef SPVEC_REALLOC
+#undef SPVEC_FREE
diff --git a/include/conts/vec.h b/include/conts/vec.h
index 6fad1c6..3d0cd66 100644
--- a/include/conts/vec.h
+++ b/include/conts/vec.h
@@ -155,8 +155,9 @@ static inline bool VEC(end)(struct VEC_STRUCT *v, VEC_TYPE *i)
 	return &v->buf[v->n] == i;
 }
 
-static inline VEC_TYPE *VEC(next)(VEC_TYPE *i)
+static inline VEC_TYPE *VEC(next)(struct VEC_STRUCT *v, VEC_TYPE *i)
 {
+	(void)v;
 	return i + 1;
 }