+
+static int consistency_check_subtree(struct stringmap_node *n) {
+ uint32_t bitno = n->bitno;
+ int success = 1;
+
+ //make sure bitnos ascend (must ascend unless left ends)
+ if (!n->left_is_leaf && bitno >= n->lr[0]->bitno) {
+ printf("Left leaf has bitno >= than parent\n");
+ success = 0;
+ }
+ if (!n->right_is_leaf && bitno >= n->lr[1]->bitno) {
+ if (left_ends(n) && bitno == n->lr[1]->bitno) {
+ //fine, there's a shelf here
+ } else {
+ printf("Right leaf has bitno >= than parent\n");
+ success = 0;
+ }
+ }
+
+ //make sure eponymous bits are set properly
+ if (n->left_is_leaf) {
+ struct T *lf = leaf(n, 0);
+ size_t len = lf->len << 3;
+ if (len == n->bitno) {
+ //this is a shelf
+ } else if (len <= n->bitno) {
+ printf("Left leaf is too short\n");
+ success = 0;
+ } else if (PEEK_BIT(lf->str, n->bitno) == 1) {
+ printf("Left leaf has incorrect bit\n");
+ success = 0;
+ }
+ }
+ if (n->right_is_leaf) {
+ struct T *lf = leaf(n, 1);
+ size_t len = lf->len << 3;
+ if (len <= n->bitno) {
+ printf("Right leaf is too short\n");
+ success = 0;
+ } else if (PEEK_BIT(lf->str, n->bitno) == 0 && !left_ends(n)) {
+ printf("Right leaf has incorrect bit\n");
+ success = 0;
+ }
+ }
+
+ if (!success) {
+ //emit_subtree(n, 0);
+ abort();
+ }
+
+ //recursively check
+ return (!n->left_is_leaf ? consistency_check_subtree(n->lr[0]) : 1) &&
+ (!n->right_is_leaf ? consistency_check_subtree(n->lr[1]) : 1);
+}
+
+static int consistency_check(struct stringmap *t) {
+ if (t->count < 2)
+ return 1;
+ return consistency_check_subtree(t->root);
+}
+
+//The following can be used to create Graphviz "dot" files to visualize the tree
+
+static void leaf_to_dot(void *lp, FILE *f) {
+ struct T *leaf = lp;
+ size_t bit_count = leaf->len << 3;
+ size_t i;
+
+ fputs("\"", f);
+ #if 1
+ for (i=0; i<bit_count; i++) {
+ putc(PEEK_BIT(leaf->str, i) ? '1' : '0', f);
+ if (((i+1) & 7) == 0)
+ fputs("\\n", f); //add newlines between bytes
+ }
+ putc(' ', f);
+ #endif
+ fprintf(f, "(%s)\"\n", leaf->str);
+}
+
+static void node_to_dot(struct stringmap_node *n, FILE *f, size_t level) {
+ //don't draw ridiculously huge trees
+ if (level > 4)
+ return;
+
+ fprintf(f, "%zu [label=\"[%zu] %u\"]\n", (size_t)n, level, n->bitno);
+
+ if (n->left_is_leaf) {
+ fprintf(f, "%zu -> ", (size_t)n);
+ leaf_to_dot(n->lr[0], f);
+ } else {
+ fprintf(f, "%zu -> %zu \n", (size_t)n, (size_t)n->lr[0]);
+ node_to_dot(n->lr[0], f, level+1);
+ }
+
+ if (n->right_is_leaf) {
+ fprintf(f, "%zu -> ", (size_t)n);
+ leaf_to_dot(n->lr[1], f);
+ } else {
+ fprintf(f, "%zu -> %zu \n", (size_t)n, (size_t)n->lr[1]);
+ node_to_dot(n->lr[1], f, level+1);
+ }
+}
+
+static void stringmap_subtree_to_dot(struct stringmap_node *n, int is_leaf, const char *filename_out) {
+ FILE *f = fopen(filename_out, "w");
+
+ fputs("digraph G {\n", f);
+
+ if (is_leaf)
+ leaf_to_dot(n, f);
+ else
+ node_to_dot(n, f, 0);
+
+ fputs("}\n", f);
+ fclose(f);
+}
+
+static size_t dot_file_number = 0;
+
+static void emit_subtree(struct stringmap_node *n, int is_leaf) {
+ char buf[64];
+ sprintf(buf, "dot/%04zu.dot", dot_file_number++);
+ stringmap_subtree_to_dot(n, is_leaf, buf);
+}
+
+static void emit_dot(struct stringmap *t) {
+ if (t->count)
+ emit_subtree(t->root, t->count==1);
+}