+#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
+}
+