X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fstringmap%2Ftest%2Frun.c;h=2ffcb1242493b79ffabb2008729b17fa7dbc3b7f;hp=68c5538a3977d1799e7a78bfa4391b7e0d8da872;hb=6fa62e5ae1e29646aa718e99020fdf2efee74373;hpb=3c81225fc0a4fb99d10282ebf11b7ec6ae1eabdd

diff --git a/ccan/stringmap/test/run.c b/ccan/stringmap/test/run.c
index 68c5538a..2ffcb124 100644
--- a/ccan/stringmap/test/run.c
+++ b/ccan/stringmap/test/run.c
@@ -1,11 +1,17 @@
-#include "stringmap/stringmap.h"
-#include "stringmap/stringmap.c"
+#include <ccan/stringmap/stringmap.h>
+#include <ccan/stringmap/stringmap.c>
 
-#include "tap/tap.h"
+#include <ccan/tap/tap.h>
 
 static void test_trivial(void) {
 	stringmap(int) map = stringmap_new(NULL);
 	
+	ok1(stringmap_lookup(map, "") == NULL);
+	*stringmap_enter(map, "") = -1;
+	
+	ok1(stringmap_lookup(map, "0") == NULL);
+	*stringmap_enter(map, "0") = 0;
+	
 	ok1(stringmap_lookup(map, "one") == NULL);
 	*stringmap_enter(map, "one") = 1;
 	
@@ -22,8 +28,10 @@ static void test_trivial(void) {
 	ok1(*stringmap_lookup(map, "one") == 1);
 	ok1(*stringmap_lookup(map, "four") == 4);
 	ok1(*stringmap_lookup(map, "two") == 2);
+	ok1(*stringmap_lookup(map, "") == -1);
+	ok1(*stringmap_lookup(map, "0") == 0);
 	
-	ok1(map.t.count == 4);
+	ok1(map.t.count == 6);
 	
 	stringmap_free(map);
 }
@@ -45,35 +53,60 @@ static void scramble(void *base, size_t nmemb, size_t size) {
 
 //#define RANDOM_STRING_READABLE
 
-static char *random_string(struct block_pool *bp) {
-	size_t len = random() % 100;
-	char *str = block_pool_alloc(bp, len+1);
+static char *random_string(struct block_pool *bp, size_t *len_out) {
+	#ifndef RANDOM_STRING_READABLE
+	size_t len = random()%5 ? random()%10 : random()%1000;
+	#else
+	size_t len = random() % 10;
+	#endif
+	char *str = block_pool_alloc(bp, len);
 	char *i;
 	
+	*len_out = len;
+	
 	for (i=str; len--; i++) {
 		#ifndef RANDOM_STRING_READABLE
 		char c = random();
-		*i = c ? c : ' ';
+		*i = c;
 		#else
-		//only generate characters [32,126]
-		char c = random()%95 + 32;
+		//only generate characters a-z
+		char c = random()%26 + 'a';
 		*i = c;
 		#endif
 	}
-	*i = 0;
 	
 	return str;
 }
 
 struct test_entry {
+	//note: struct layout needs to match *stringmap(char*).last
 	const char *str;
+	size_t len;
+	
 	char *value;
 		/* value is not a string, but a pointer to char marking that
 		   this key has been entered already. */
 };
 
-static int by_str(const void *ap, const void *bp) {
-	return strcmp(((struct test_entry*)ap)->str, ((struct test_entry*)bp)->str);
+static int tecmp(const struct test_entry *ap, const struct test_entry *bp) {
+	const unsigned char *a = (unsigned char*)ap->str, *ae = a+ap->len;
+	const unsigned char *b = (unsigned char*)bp->str, *be = b+bp->len;
+	
+	for (;;a++, b++) {
+		if (a >= ae) {
+			if (b >= be)
+				return 0; //strings are the same
+			return -1; //a is shorter than b
+		}
+		if (b >= be)
+			return 1; //b is shorter than a
+		if (*a != *b) //there is a differing character
+			return (unsigned int)*a - (unsigned int)*b;
+	}
+}
+
+static int by_str(const void *a, const void *b) {
+	return tecmp(a, b);
 }
 
 static void cull_duplicates(struct test_entry *entries, size_t *count) {
@@ -83,10 +116,10 @@ static void cull_duplicates(struct test_entry *entries, size_t *count) {
 	
 	for (i=entries, o=entries; i<e;) {
 		//skip repeated strings
-		if (i>entries) {
-			const char *last = i[-1].str;
-			if (!strcmp(last, i->str)) {
-				do i++; while(i<e && !strcmp(last, i->str));
+		if (o>entries) {
+			struct test_entry *last = &o[-1];
+			if (!tecmp(last, i)) {
+				do i++; while(i<e && !tecmp(last, i));
 				continue;
 			}
 		}
@@ -101,23 +134,114 @@ static void cull_duplicates(struct test_entry *entries, size_t *count) {
 	*count = o-entries;
 }
 
+#define print(tag, fmt, ...) do { \
+		if (out) \
+			fprintf(out, tag fmt "\n", ##__VA_ARGS__); \
+	} while(0)
+#define err(...) do { \
+		print("error: ", __VA_ARGS__); \
+		goto fail; \
+	} while(0)
+//#define debug(...) print("debug: ", __VA_ARGS__)
+#define debug(...) do {} while(0)
+#define msg(...) print("info: ", __VA_ARGS__)
+
+static int test_traverse(struct stringmap *map, struct test_entry *strings, size_t size, FILE *out) {
+	size_t sp = 0;
+	size_t stack_alloc = 16;
+	struct stringmap_node **stack = NULL;
+	struct stringmap_node *n;
+	void *leaf;
+	#define check(lri) do { \
+			leaf = n->lr[lri]; \
+			if (!size--) \
+				err("Fewer items in tree than counted"); \
+			if (tecmp(leaf, strings++)) \
+				err("%s leaf has incorrect string", lri ? "Left" : "Right"); \
+		} while(0)
+	#define check_left() check(0)
+	#define check_right() check(1)
+	
+	if (map->count != size)
+		err("map->count != size");
+	
+	if (map->count == 0)
+		return 1;
+	
+	if (map->count == 1) {
+		leaf = (struct test_entry*)map->root;
+		if (!tecmp(leaf, &strings[0]))
+			return 1;
+		else
+			err("Only leaf in tree has incorrect value");
+	}
+	
+	stack = malloc(sizeof(*stack) * stack_alloc);
+	n = map->root;
+	
+	for (;;) {
+		//descend left
+		while (!n->left_is_leaf) {
+			stack[sp++] = n;
+			n = n->lr[0];
+			
+			if (sp >= stack_alloc) {
+				stack_alloc += stack_alloc;
+				stack = realloc(stack, sizeof(*stack) * stack_alloc);
+			}
+		}
+		
+		check_left();
+		
+	ascend_right:
+		while (n->right_is_leaf) {
+			check_right();
+			
+			if (!sp)
+				goto done; //we finished up the last entry
+			n = stack[--sp];
+		}
+		
+		//descend right
+		n = n->lr[1];
+		while (n->left_is_leaf) {
+			check_left();
+			
+			if (n->right_is_leaf) {
+				check_right();
+				
+				if (!sp)
+					goto done;
+				n = stack[--sp];
+				goto ascend_right; //sorry
+			}
+			n = n->lr[1];
+		}
+	}
+	
+done:
+	if (size != 0)
+		err("More items in tree than counted");
+	
+	free(stack);
+	return 1;
+	
+fail:
+	if (stack)
+		free(stack);
+	return 0;
+	
+	#undef check
+	#undef check_left
+	#undef check_right
+}
+
 static int test_stringmap(size_t count, FILE *out) {
 	stringmap(char*) map = stringmap_new(NULL);
 	
-	#define print(tag, fmt, ...) do { \
-			if (out) \
-				fprintf(out, tag fmt "\n", ##__VA_ARGS__); \
-		} while(0)
-	#define err(...) do { \
-			print("error: ", __VA_ARGS__); \
-			goto fail; \
-		} while(0)
-	#define debug(...) print("debug: ", __VA_ARGS__)
-	#define msg(...) print("info: ", __VA_ARGS__)
-	
 	struct block_pool *bp = block_pool_new(NULL);
 	struct test_entry *entries = block_pool_alloc(bp, sizeof(*entries) * count);
-	struct test_entry *i, *e = entries+count;
+	struct test_entry *i, *e = entries+count, *o;
 	char *value_base = block_pool_alloc(bp, count), *value = value_base;
 	size_t unique_count = 0;
 	
@@ -127,11 +251,13 @@ static int test_stringmap(size_t count, FILE *out) {
 	msg("Generating %zu test entries...", count);
 	
 	for (i=entries; i<e; value++) {
-		char *str = random_string(bp);
+		size_t len;
+		char *str = random_string(bp, &len);
 		size_t same_count = (random()%5 ? random()%3 : random()%10) + 1;
 		
 		for (;same_count-- && i<e; i++) {
 			i->str = str;
+			i->len = len;
 			i->value = value;
 		}
 	}
@@ -142,29 +268,34 @@ static int test_stringmap(size_t count, FILE *out) {
 	
 	msg("Inserting/looking up %zu entries...", count);
 	
-	for (i=entries; i<e; i++) {
+	for (i=entries, o=entries; i<e; i++) {
 		char **node;
 		
 		debug("Looking up %s", i->str);
 		
-		node = stringmap_lookup(map, i->str);
+		node = stringmap_lookup_n(map, i->str, i->len);
 		
 		if (!node) {
 			if (*i->value)
 				err("Previously inserted entry not found");
 			
-			debug("Not found; entering");
+			debug("Not found; entering %s", i->str);
 			
-			node = stringmap_enter(map, i->str);
-			if (!node || strcmp(i->str, map.last->str))
+			node = stringmap_enter_n(map, i->str, i->len);
+			if (!node || tecmp(i, (void*)map.last))
 				err("Node not properly entered");
+			if (map.last->str[map.last->len])
+				err("Entered string not zero-terminated");
 			*node = i->value;
 			*i->value = 1; //mark that the entry is entered
 			
-			unique_count++;
+			//write this unique entry to the entry list to traverse later
+			*o++ = *i;
 		} else {
-			if (strcmp(i->str, map.last->str))
+			if (tecmp(i, (void*)map.last))
 				err("lookup returned incorrect string");
+			if (map.last->str[map.last->len])
+				err("Looked-up string not zero-terminated");
 			if (i->value != *node)
 				err("lookup returned incorrect value");
 			if (!*i->value)
@@ -172,34 +303,44 @@ static int test_stringmap(size_t count, FILE *out) {
 		}
 	}
 	
+	unique_count = o-entries;
+	
 	if (map.t.count != unique_count)
 		err("Map has incorrect count");
 	
-	printf("stringmap test passed after %zu inserts, %zu lookups (%zu total operations)\n", unique_count, (i-entries)-unique_count, i-entries);
+	qsort(entries, unique_count, sizeof(*entries), by_str);
+	
+	msg("Traversing forward through %zu items", unique_count);	
+	if (!test_traverse(&map.t, entries, unique_count, out))
+		err("Traversal does not produce the strings in order");
+	
+	printf("stringmap test passed after %zu inserts, %zu lookups (%zu total operations)\n",
+		unique_count, (i-entries)-unique_count, i-entries);
 	
 	block_pool_free(bp);
 	stringmap_free(map);
 	return 1;
 
 fail:
-	printf("stringmap test failed after %zu inserts, %zu lookups (%zu total operations)\n", unique_count, (i-entries)-unique_count, i-entries);
+	printf("stringmap test failed after %zu inserts, %zu lookups (%zu total operations)\n",
+		unique_count, (i-entries)-unique_count, i-entries);
 	
 	block_pool_free(bp);
 	stringmap_free(map);
 	return 0;
-	
-	#undef print
-	#undef err
-	#undef debug
-	#undef msg
 }
 
+#undef print
+#undef err
+#undef debug
+#undef msg
+
 int main(void)
 {
-	plan_tests(10);
+	plan_tests(14);
 	
 	test_trivial();
-	ok1(test_stringmap(10000, NULL));
+	ok1(test_stringmap(10000, stdout));
 	
 	return exit_status();
 }