add map

9 files changed, 659 insertions, 227 deletions

diff --git a/Makefile b/Makefile
index 48e8cb8..ff1eea3 100644
--- a/Makefile
+++ b/Makefile
@@ -1,16 +1,37 @@
-check:
+CFLAGS = -g -std=c23 -Wall -Wextra
+check: check-vec check-sptree check-map
+
+check-vec:
 	mkdir -p build
-	$(CC) -g -Iinclude tests/vec.c -o build/vec
-	$(CC) -g -Iinclude tests/htrie.c -o build/htrie
+	$(CC) $(CFLAGS) -Iinclude tests/vec.c -o build/vec
 	valgrind -q --error-exitcode=1 ./build/vec
-	valgrind -q --error-exitcode=1 ./build/htrie
 
-bench:
+check-sptree:
+	mkdir -p build
+	$(CC) $(CFLAGS) -Iinclude tests/sptree.c -o build/sptree
+	valgrind -q --error-exitcode=1 ./build/sptree
+
+check-map:
+	mkdir -p build
+	$(CC) $(CFLAGS) -Iinclude tests/map.c -o build/map
+	valgrind -q --error-exitcode=1 ./build/map
+
+bench: bench-vec bench-sptree bench-map
+
+bench-vec:
 	mkdir -p build
-	$(CC) -g -O2 -Iinclude tests/vec.c -o build/vec_opt
-	$(CC) -g -O2 -Iinclude tests/htrie.c -o build/htrie_opt
+	$(CC) $(CFLAGS) -O2 -Iinclude tests/vec.c -o build/vec_opt
 	time ./build/vec_opt 2> build/vec_bench.txt
-	time ./build/htrie_opt 2> build/htrie_bench.txt
+
+bench-sptree:
+	mkdir -p build
+	$(CC) $(CFLAGS) -O2 -Iinclude tests/sptree.c -o build/sptree_opt
+	time ./build/sptree_opt 2> build/sptree_bench.txt
+
+bench-map:
+	mkdir -p build
+	$(CC) $(CFLAGS) -O2 -Iinclude tests/map.c -o build/map_opt
+	time ./build/map_opt 2> build/map_bench.txt
 
 clean:
 	rm -rf build
diff --git a/include/conts/conts.h b/include/conts/conts.h
index d965aeb..862bd31 100644
--- a/include/conts/conts.h
+++ b/include/conts/conts.h
@@ -4,25 +4,11 @@
 #define CONTS_JOIN2(a, b) a##_##b
 #define CONTS_JOIN(a, b) CONTS_JOIN2(a, b)
 
-static inline unsigned long conts_strhash(const char *str)
-{
-	/* http://www.cse.yorku.ca/%7Eoz/hash.html, djb2 */
-	unsigned long hash = 5381;
-	int c;
-
-	while (c = *str++)
-		hash = ((hash << 5) + hash) + c;
-
-	return hash;
-}
-
-static inline unsigned long conts_inthash(unsigned long x)
-{
-	/* https://xorshift.di.unimi.it/splitmix64.c */
-	x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
-	x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
-	x = (x ^ (x >> 31));
-	return x;
-}
+#define CONTAINER_OF(ptr, type, member) \
+	(type *)((char *)(ptr) - offsetof(type, member))
 
+#define foreach(name, i, s)\
+	for (auto i = CONTS_JOIN(name, begin)(s);\
+			!CONTS_JOIN(name, end)(s, i);\
+			i = CONTS_JOIN(name, next)(i))
 #endif /* CONTS_H */
diff --git a/include/conts/htrie.h b/include/conts/htrie.h
deleted file mode 100644
index 26482b2..0000000
--- a/include/conts/htrie.h
+++ /dev/null
@@ -1,199 +0,0 @@
-#ifndef HTRIE_KEY
-#error "Need htrie key"
-#endif
-
-#ifndef HTRIE_CMP
-#error "Need htrie cmp"
-#endif
-
-#ifndef HTRIE_HASH
-#error "Need htrie hash"
-#endif
-
-#ifndef HTRIE_TYPE
-#error "Need htrie type"
-#endif
-
-#ifndef HTRIE_NAME
-#error "Need htrie name"
-#endif
-
-#include <stdlib.h>
-#include <stdbool.h>
-#include "conts.h"
-
-#define HTRIE(a) CONTS_JOIN(HTRIE_NAME, a)
-
-#define HTRIE_STRUCT HTRIE_NAME
-#define HTRIE_NODE CONTS_JOIN(HTRIE_NAME, node)
-
-struct HTRIE_NODE {
-	unsigned long hash;
-	HTRIE_KEY key;
-	struct HTRIE_NODE *left, *right;
-	HTRIE_TYPE data;
-};
-
-struct HTRIE_STRUCT {
-	size_t n;
-	struct HTRIE_NODE *root;
-};
-
-static inline struct HTRIE_STRUCT HTRIE(create)()
-{
-	return (struct HTRIE_STRUCT){.n = 0, .root = NULL};
-}
-
-static inline bool HTRIE(empty)(struct HTRIE_STRUCT *h)
-{
-	return h->n == 0;
-}
-
-static inline size_t HTRIE(len)(struct HTRIE_STRUCT *h)
-{
-	return h->n;
-}
-
-static inline HTRIE_TYPE *HTRIE(insert)(struct HTRIE_STRUCT *h, HTRIE_KEY key, HTRIE_TYPE data)
-{
-	unsigned long hash = HTRIE_HASH(key);
-	if (!h->root) {
-		assert(h->n == 0);
-		struct HTRIE_NODE *new = malloc(sizeof(struct HTRIE_NODE));
-		if (!new)
-			return NULL;
-
-		new->hash = hash;
-		new->key = key;
-		new->data = data;
-		new->left = NULL;
-		new->right = NULL;
-
-		h->root = new;
-		h->n = 1;
-		return &new->data;
-	}
-
-	bool insert_left = true;
-	struct HTRIE_NODE *n = h->root;
-	while (n) {
-		if (n->hash < hash) {
-			if (!n->left) {
-				insert_left = true;
-				break;
-			}
-
-			n = n->left;
-			continue;
-		}
-
-		if (n->hash > hash) {
-			if (!n->right) {
-				insert_left = false;
-				break;
-			}
-
-			n = n->right;
-			continue;
-		}
-
-		/* n->hash == hash */
-		int c = HTRIE_CMP(n->key, key);
-
-		/* already exists */
-		if (c < 0) {
-			if (!n->left) {
-				insert_left = true;
-				break;
-			}
-
-			n = n->left;
-			continue;
-		}
-
-		if (c > 0) {
-			if (!n->right) {
-				insert_left = false;
-				break;
-			}
-
-			n = n->right;
-			continue;
-		}
-
-		/* otherwise, node already exists */
-		return &n->data;
-
-	}
-
-	struct HTRIE_NODE *new = malloc(sizeof(struct HTRIE_NODE));
-	if (!new)
-		return NULL;
-
-	new->hash = hash;
-	new->key = key;
-	new->data = data;
-	new->left = NULL;
-	new->right = NULL;
-
-	if (insert_left)
-		n->left = new;
-	else
-		n->right = new;
-
-	h->n++;
-	return &new->data;
-}
-
-static inline HTRIE_TYPE *HTRIE(at)(struct HTRIE_STRUCT *h, HTRIE_KEY key)
-{
-	unsigned long hash = HTRIE_HASH(key);
-
-	struct HTRIE_NODE *n = h->root;
-	while (n) {
-		if (n->hash < hash) {
-			n = n->left;
-			continue;
-		}
-
-		if (n->hash > hash) {
-			n = n->right;
-			continue;
-		}
-
-		int c = HTRIE_CMP(n->key, key);
-		if (c < 0) {
-			n = n->left;
-			continue;
-		}
-
-		if (c > 0) {
-			n = n->right;
-			continue;
-		}
-
-		/* otherwise, we found our node */
-		break;
-	}
-
-	if (!n)
-		return NULL;
-
-	return &n->data;
-}
-
-static inline void HTRIE(destroy_node)(struct HTRIE_NODE *n)
-{
-	if (n->left)
-		HTRIE(destroy_node)(n->left);
-
-	if (n->right)
-		HTRIE(destroy_node)(n->right);
-
-	free(n);
-}
-
-static inline void HTRIE(destroy)(struct HTRIE_STRUCT *h)
-{
-	HTRIE(destroy_node)(h->root);
-}
diff --git a/include/conts/map.h b/include/conts/map.h
new file mode 100644
index 0000000..d24ab06
--- /dev/null
+++ b/include/conts/map.h
@@ -0,0 +1,104 @@
+#ifndef MAP_KEY
+#error "Need map key"
+#endif
+
+#ifndef MAP_TYPE
+#error "Need map type"
+#endif
+
+#ifndef MAP_CMP
+#error "Need map cmp"
+#endif
+
+#ifndef MAP_NAME
+#error "Need map name"
+#endif
+
+#include "conts.h"
+
+#define MAP(a) CONTS_JOIN(MAP_NAME, a)
+
+#define MAP_NODE MAP(node)
+#define MAP_ROOT MAP_NAME
+
+struct MAP_NODE {
+	MAP_KEY key;
+	MAP_TYPE data;
+};
+
+static inline int MAP(cmp)(struct MAP_NODE a, struct MAP_NODE b)
+{
+	return MAP_CMP(a.key, b.key);
+}
+
+#define BASE(a) CONTS_JOIN(MAP(map_base), a)
+
+#define SPTREE_TYPE struct MAP_NODE
+#define SPTREE_CMP MAP(cmp)
+#define SPTREE_NAME MAP(map_base)
+#include "sptree.h"
+
+struct MAP_ROOT {
+	struct MAP(map_base) root;
+};
+
+static inline struct MAP_ROOT MAP(create)()
+{
+	return (struct MAP_ROOT){.root = BASE(create)()};
+}
+
+static inline void MAP(destroy)(struct MAP_ROOT *root)
+{
+	BASE(destroy)(&root->root);
+}
+
+static inline MAP_TYPE *MAP(insert)(struct MAP_ROOT *root, MAP_KEY key, MAP_TYPE data)
+{
+	struct MAP_NODE node = {.key = key, .data = data};
+	struct MAP_NODE *res = BASE(insert)(&root->root, node);
+	if (!res)
+		return NULL;
+
+	return &res->data;
+}
+
+static inline MAP_TYPE *MAP(find)(struct MAP_ROOT *root, MAP_KEY key)
+{
+	struct MAP_NODE node = {.key = key};
+	struct MAP_NODE *res = BASE(find)(&root->root, node);
+	if (!res)
+		return NULL;
+
+	return &res->data;
+}
+
+static inline void MAP(remove)(struct MAP_ROOT *root, MAP_KEY key)
+{
+	struct MAP_NODE node = {.key = key};
+	BASE(remove)(&root->root, node);
+}
+
+static inline struct MAP_NODE *MAP(begin)(struct MAP_ROOT *root)
+{
+	return BASE(begin)(&root->root);
+}
+
+static inline struct MAP_NODE *MAP(next)(struct MAP_NODE *n)
+{
+	return BASE(next)(n);
+}
+
+static inline bool MAP(end)(struct MAP_ROOT *root, struct MAP_NODE *n)
+{
+	return BASE(end)(&root->root, n);
+}
+
+static inline size_t MAP(len)(struct MAP_ROOT *root)
+{
+	return BASE(len)(&root->root);
+}
+
+#undef MAP_KEY
+#undef MAP_TYPE
+#undef MAP_CMP
+#undef MAP_NAME
diff --git a/include/conts/sptree.h b/include/conts/sptree.h
new file mode 100644
index 0000000..75b88fc
--- /dev/null
+++ b/include/conts/sptree.h
@@ -0,0 +1,413 @@
+#include <stdint.h>
+#include <stdlib.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+#ifndef SPTREE_TYPE
+#error "Need sptree type"
+#endif
+
+#ifndef SPTREE_CMP
+#error "Need sptree cmp"
+#endif
+
+#ifndef SPTREE_NAME
+#error "Need sptree name"
+#endif
+
+#include "conts.h"
+
+#define SPTREE(a) CONTS_JOIN(SPTREE_NAME, a)
+
+#define SPNODE SPTREE(node)
+#define SPROOT SPTREE_NAME
+
+#ifndef SPTREE_H
+#define SPTREE_H
+
+#define sp_left(n) ((n)->left)
+#define sp_right(n) ((n)->right)
+#define sp_paren(n) ((n)->parent)
+#define sp_lparen(n) (sp_left(n)->parent)
+#define sp_rparen(n) (sp_right(n)->parent)
+
+#endif /* SPTREE_H */
+
+struct SPNODE {
+	int_fast16_t hint;
+	struct SPNODE *left, *right, *parent;
+	SPTREE_TYPE data;
+};
+
+struct SPROOT {
+	size_t n;
+	struct SPNODE *root;
+};
+
+static inline struct SPROOT SPTREE(create)()
+{
+	return (struct SPROOT){.n = 0, .root = NULL};
+}
+
+static inline size_t SPTREE(len)(struct SPROOT *s)
+{
+	return s->n;
+}
+
+static inline struct SPNODE *SPTREE(first)(struct SPNODE *n)
+{
+	while (sp_left(n))
+		n = sp_left(n);
+
+	return n;
+}
+
+static inline struct SPNODE *SPTREE(last)(struct SPNODE *n)
+{
+	while (sp_right(n))
+		n = sp_right(n);
+
+	return n;
+}
+
+static inline SPTREE_TYPE *SPTREE(begin)(struct SPROOT *s)
+{
+	return &SPTREE(first)(s->root)->data;
+}
+
+static inline SPTREE_TYPE *SPTREE(next)(SPTREE_TYPE *prev)
+{
+	struct SPNODE *n = CONTAINER_OF(prev, struct SPNODE, data);
+	if (sp_right(n)) {
+		n = sp_right(n);
+		while (sp_left(n))
+			n = sp_left(n);
+
+		return &n->data;
+	}
+
+	while (n) {
+		struct SPNODE *p = sp_paren(n);
+		if (!p)
+			return NULL;
+
+		if (sp_left(p) == n)
+			return &p->data;
+
+		n = p;
+	}
+
+	return NULL;
+}
+
+static inline bool SPTREE(end)(struct SPROOT *s, SPTREE_TYPE *prev)
+{
+	(void)s;
+	return prev == NULL;
+}
+
+static inline void SPTREE(turn_left)(struct SPNODE *n)
+{
+	struct SPNODE *l = sp_left(n);
+	struct SPNODE *p = sp_paren(n);
+
+	assert(l);
+
+	sp_paren(l) = sp_paren(n);
+	sp_left(n) = sp_right(l);
+	sp_paren(n) = l;
+	sp_right(l) = n;
+
+	if (p && sp_left(p) == n)
+		sp_left(p) = l;
+	else if (p)
+		sp_right(p) = l;
+
+	if (sp_left(n))
+		sp_lparen(n) = n;
+}
+
+static inline void SPTREE(turn_right)(struct SPNODE *n)
+{
+	struct SPNODE *r = sp_right(n);
+	struct SPNODE *p = sp_paren(n);
+
+	assert(r);
+
+	sp_paren(r) = sp_paren(n);
+	sp_right(n) = sp_left(r);
+	sp_paren(n) = r;
+	sp_left(r) = n;
+
+	if (p && sp_left(p) == n)
+		sp_left(p) = r;
+	else if (p)
+		sp_right(p) = r;
+
+	if (sp_right(n))
+		sp_rparen(n) = n;
+}
+
+static inline int_fast16_t SPTREE(leaning)(struct SPNODE *n)
+{
+	int_fast16_t l = 0;
+	int_fast16_t r = 0;
+
+	if (sp_left(n))
+		l = sp_left(n)->hint + 1;
+
+	if (sp_right(n))
+		r = sp_right(n)->hint + 1;
+
+	return l - r;
+}
+
+static inline int_fast16_t SPTREE(max_hint)(struct SPNODE *n)
+{
+	int_fast16_t l = 0;
+	int_fast16_t r = 0;
+
+	if (sp_left(n))
+		l = sp_left(n)->hint + 1;
+
+	if (sp_right(n))
+		r = sp_right(n)->hint + 1;
+
+	if (l > r)
+		return l;
+	else
+		return r;
+}
+
+static inline void SPTREE(update)(struct SPROOT *r, struct SPNODE *n)
+{
+	while (n) {
+		int b = SPTREE(leaning)(n);
+		int prev_hint = n->hint;
+		struct SPNODE *p = sp_paren(n);
+
+		if (b < -1) {
+			/* leaning to the right */
+			if (n == r->root)
+				r->root = sp_right(n);
+
+			SPTREE(turn_right)(n);
+		}
+
+		else if (b > 1) {
+			/* leaning to the left */
+			if (n == r->root)
+				r->root = sp_left(n);
+
+			SPTREE(turn_left)(n);
+		}
+
+		n->hint = SPTREE(max_hint)(n);
+		if (n->hint == 0 || n->hint != prev_hint)
+			n = p;
+		else
+			return;
+	}
+}
+
+static inline SPTREE_TYPE *SPTREE(insert)(struct SPROOT *s, SPTREE_TYPE data)
+{
+	if (!s->root) {
+		assert(s->n == 0);
+		struct SPNODE *new = malloc(sizeof(struct SPNODE));
+		if (!new)
+			return NULL;
+
+		new->left = new->right = new->parent = NULL;
+		new->data = data;
+		new->hint = 0;
+
+		s->root = new;
+		s->n = 1;
+		return &new->data;
+	}
+
+	bool insert_left = false;
+
+	struct SPNODE *n = s->root;
+	struct SPNODE *p = NULL;
+	while (n) {
+		p = n;
+		int c = SPTREE_CMP(n->data, data);
+		if (c < 0) {
+			n = sp_left(n);
+			insert_left = true;
+			continue;
+		}
+		if (c > 0) {
+			n = sp_right(n);
+			insert_left = false;
+			continue;
+		}
+
+		/* we already have a node like this */
+		return &n->data;
+	}
+
+	struct SPNODE *new = malloc(sizeof(struct SPNODE));
+	if (!new)
+		return NULL;
+
+	new->left = new->right = NULL;
+	new->parent = p;
+	new->data = data;
+	new->hint = 0;
+
+	if (insert_left)
+		sp_left(p) = new;
+	else
+		sp_right(p) = new;
+
+	SPTREE(update)(s, new);
+	s->n++;
+	return &new->data;
+}
+
+static inline void SPTREE(replace_right)(struct SPNODE *n, struct SPNODE *r)
+{
+	struct SPNODE *p = sp_paren(n);
+	struct SPNODE *rp = sp_paren(r);
+
+	if (sp_left(rp) == r) {
+		sp_left(rp) = sp_right(r);
+		if (sp_right(r))
+			sp_rparen(r) = rp;
+	}
+
+	if (sp_paren(rp) == n)
+		sp_paren(rp) = r;
+
+	sp_paren(r) = p;
+	sp_left(r) = sp_left(n);
+
+	if (sp_right(n) != r) {
+		sp_right(r) = sp_right(n);
+		sp_rparen(n) = r;
+	}
+
+	if (p && sp_left(p) == n)
+		sp_left(p) = r;
+	else if (p)
+		sp_right(p) = r;
+
+	if (sp_left(n))
+		sp_lparen(n) = r;
+}
+
+static inline void SPTREE(replace_left)(struct SPNODE *n, struct SPNODE *l)
+{
+	struct SPNODE *p = sp_paren(n);
+	struct SPNODE *lp = sp_paren(l);
+
+	if (sp_right(lp) == l) {
+		sp_right(lp) = sp_left(l);
+		if (sp_left(l))
+			sp_lparen(l) = lp;
+	}
+
+	if (sp_paren(lp) == n)
+		sp_paren(lp) = l;
+
+	sp_paren(l) = p;
+	sp_right(l) = sp_right(n);
+
+	if (sp_left(n) != l) {
+		sp_left(l) = sp_left(n);
+		sp_lparen(n) = l;
+	}
+
+	if (p && sp_left(p) == n)
+		sp_left(p) = l;
+	else if (p)
+		sp_right(p) = l;
+
+	if (sp_right(n))
+		sp_rparen(n) = l;
+}
+
+static inline SPTREE_TYPE *SPTREE(find)(struct SPROOT *s, SPTREE_TYPE data)
+{
+	struct SPNODE *n = s->root;
+	while (n) {
+		int c = SPTREE_CMP(n->data, data);
+		if (c < 0) {
+			n = n->left;
+			continue;
+		}
+
+		if (c > 0) {
+			n = n->right;
+			continue;
+		}
+
+		return &n->data;
+	}
+
+	return NULL;
+}
+
+static inline void SPTREE(remove_found)(struct SPROOT *s, SPTREE_TYPE *found)
+{
+	s->n--;
+	struct SPNODE *del = CONTAINER_OF(found, struct SPNODE, data);
+	if (sp_right(del)) {
+		struct SPNODE *least = SPTREE(first)(sp_right(del));
+
+		if (del == s->root)
+			s->root = least;
+
+		SPTREE(replace_right)(del, least);
+		SPTREE(update)(s, sp_right(least));
+		return;
+	}
+
+	if (sp_left(del)) {
+		struct SPNODE *most = SPTREE(last)(sp_left(del));
+
+		if (del == s->root)
+			s->root = most;
+
+		SPTREE(replace_left)(del, most);
+		SPTREE(update)(s, sp_left(most));
+		return;
+	}
+
+	if (del == s->root) {
+		s->root = NULL;
+		return;
+	}
+
+	/* empty node */
+	struct SPNODE *paren = sp_paren(del);
+
+	if (sp_left(paren) == del)
+		sp_left(paren) = NULL;
+	else
+		sp_right(paren) = NULL;
+
+	SPTREE(update)(s, paren);
+}
+
+static inline void SPTREE(remove)(struct SPROOT *s, SPTREE_TYPE data)
+{
+	SPTREE_TYPE *found = SPTREE(find)(s, data);
+	if (!found)
+		return;
+
+	SPTREE(remove_found)(s, found);
+}
+
+static inline void SPTREE(destroy)(struct SPROOT *s)
+{
+	while (s->root)
+		SPTREE(remove_found)(s, &s->root->data);
+}
+
+#undef SPTREE
+#undef SPNODE
+#undef SPROOT
diff --git a/include/conts/vec.h b/include/conts/vec.h
index ccdfe81..a11927f 100644
--- a/include/conts/vec.h
+++ b/include/conts/vec.h
@@ -7,6 +7,7 @@
 #endif
 
 #include <stdbool.h>
+#include <string.h>
 #include <stdlib.h>
 #include <assert.h>
 
@@ -111,6 +112,29 @@ static inline void VEC(shrink)(struct VEC_STRUCT *v, size_t n)
 	v->n = n;
 }
 
+static inline void VEC(remove)(struct VEC_STRUCT *v, size_t i)
+{
+	assert(v->n > i);
+	size_t c = sizeof(VEC_TYPE) * (v->n - i);
+	memcpy(&v->buf[i], &v->buf[i + 1], c);
+	v->n--;
+}
+
+static inline VEC_TYPE *VEC(begin)(struct VEC_STRUCT *v)
+{
+	return &v->buf[0];
+}
+
+static inline bool VEC(end)(struct VEC_STRUCT *v, VEC_TYPE *i)
+{
+	return &v->buf[v->n - 1] == i;
+}
+
+static inline VEC_TYPE *VEC(next)(VEC_TYPE *i)
+{
+	return i + 1;
+}
+
 #undef VEC
 #undef VEC_TYPE
 #undef VEC_NAME
diff --git a/tests/map.c b/tests/map.c
new file mode 100644
index 0000000..e9362ab
--- /dev/null
+++ b/tests/map.c
@@ -0,0 +1,33 @@
+#include <assert.h>
+#include <stdio.h>
+
+#define MAP_KEY int
+#define MAP_TYPE int
+#define MAP_CMP(a, b) ((a) - (b))
+#define MAP_NAME ints
+#include <conts/map.h>
+
+int main()
+{
+	struct ints ints = ints_create();
+	for (int i = 0; i < 1000000; ++i) {
+		ints_insert(&ints, i, i);
+	}
+	assert(ints_len(&ints) == 1000000);
+
+	for (int i = 0; i < 1000000; ++i) {
+		int *v = ints_find(&ints, i);
+		assert(v && *v == i);
+	}
+
+	foreach(ints, iter, &ints) {
+		assert(iter->key == iter->data);
+	}
+
+	for (int i = 0; i < 1000000; ++i) {
+		ints_remove(&ints, i);
+	}
+
+	assert(ints_len(&ints) == 0);
+	ints_destroy(&ints);
+}
diff --git a/tests/sptree.c b/tests/sptree.c
new file mode 100644
index 0000000..b8d1e5a
--- /dev/null
+++ b/tests/sptree.c
@@ -0,0 +1,37 @@
+#include <assert.h>
+#include <stdio.h>
+
+#define SPTREE_TYPE int
+#define SPTREE_CMP(a, b) ((b) - (a))
+#define SPTREE_NAME ints
+#include <conts/sptree.h>
+
+int main()
+{
+	struct ints ints = ints_create();
+	for (int i = 0; i < 1000000; ++i) {
+		ints_insert(&ints, i);
+	}
+	assert(ints_len(&ints) == 1000000);
+
+	for (int i = 0; i < 1000000; ++i) {
+		int *v = ints_find(&ints, i);
+		assert(v && *v == i);
+	}
+
+	int i = 0;
+	foreach(ints, iter, &ints) {
+		/* since my trees are ordered, this must hold, although you
+		 * might consider it an implementation detail that shouldn't be
+		 * relied on */
+		assert(iter && *iter == i);
+		i++;
+	}
+
+	for (int i = 0; i < 1000000; ++i) {
+		ints_remove(&ints, i);
+	}
+
+	assert(ints_len(&ints) == 0);
+	ints_destroy(&ints);
+}
diff --git a/tests/vec.c b/tests/vec.c
index 4bc06e7..a84096c 100644
--- a/tests/vec.c
+++ b/tests/vec.c
@@ -10,10 +10,23 @@ int main()
 	for (int i = 0; i < 1000000; ++i) {
 		ints_append(&ints, i);
 	}
+	assert(ints_len(&ints) == 1000000);
 
 	for (int i = 0; i < 1000000; ++i) {
 		int *v = ints_at(&ints, i);
 		assert(v && *v == i);
 	}
+
+	int i = 0;
+	foreach(ints, iter, &ints) {
+		assert(iter && *iter == i);
+		i++;
+	}
+
+	for (int i = 1000000 - 1; i >= 0; --i) {
+		ints_remove(&ints, i);
+	}
+	assert(ints_len(&ints) == 0);
+
 	ints_destroy(&ints);
 }