Have some generic dictionary implementation.

Even comes with testcases, which is nice.

svn path=/trunk/libparserutils/; revision=4138

1 files changed, 87 insertions, 0 deletions

diff --git a/test/rbtree.c b/test/rbtree.c
new file mode 100644
index 0000000..4179561
--- /dev/null
+++ b/test/rbtree.c
@@ -0,0 +1,87 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "utils/rbtree.h"
+
+#include "testutils.h"
+
+static void *myrealloc(void *ptr, size_t len, void *pw)
+{
+	UNUSED(pw);
+
+	return realloc(ptr, len);
+}
+
+static int mycmp(const void *a, const void *b)
+{
+	return ((const uint32_t) a) - ((const uint32_t) b);
+}
+
+int main(int argc, char **argv)
+{
+	parserutils_rbtree *tree;
+
+	UNUSED(argc);
+	UNUSED(argv);
+
+	tree = parserutils_rbtree_create(mycmp, myrealloc, NULL);
+	assert(tree != NULL);
+
+#define N 40000
+#define G 307
+//#define N 400
+//#define G 7
+
+	printf("Inserting %d items\n", N);
+
+	for (int i = G, count = 1; i != 0; i = (i + G) % N, count++) {
+		void *old;
+		assert(parserutils_rbtree_insert(tree, (void *) i, (void *) i, 
+				&old) == PARSERUTILS_OK);
+
+		if ((count % 10000) == 0)
+			printf("%d\n", count);
+	}
+
+	printf("Removing %d items\n", N/2);
+
+	for (int i = 1, count = 1; i < N; i += 2, count++) {
+		void *key, *value;
+		assert(parserutils_rbtree_delete(tree, (void *) i, &key,
+				&value) == PARSERUTILS_OK);
+		if ((count % 10000) == 0)
+			printf("%d\n", count);
+	}
+
+	printf("Finding %d items\n", N/2);
+
+	for (int i = 2, count = 1; i < N; i += 2, count++) {
+		void *value = NULL;
+		assert(parserutils_rbtree_find(tree, (void *) i, &value) == 
+				PARSERUTILS_OK);
+		assert(value != NULL && ((int) value) == i);
+		if ((count % 10000) == 0)
+			printf("%d\n", count);
+	}
+
+	printf("Verifying & removing %d items\n", N/2);
+
+	for (int i = 1, count = 1; i < N; i += 2, count++) {
+		void *key, *value = NULL;
+		assert(parserutils_rbtree_find(tree, (void *) i, &value) == 
+				PARSERUTILS_OK);
+		assert(value == NULL);
+		assert(parserutils_rbtree_delete(tree, (void *) i,
+				&key, &value) == PARSERUTILS_OK);
+		if ((count % 10000) == 0)
+			printf("%d\n", count);
+	}
+
+	parserutils_rbtree_destroy(tree, NULL, NULL);
+
+	printf("PASS\n");
+
+	return 0;
+}
+