diff options
Diffstat (limited to 'zix/tree_debug.h')
| -rw-r--r-- | zix/tree_debug.h | 234 |
1 files changed, 126 insertions, 108 deletions
diff --git a/zix/tree_debug.h b/zix/tree_debug.h index ff9311e..68e37b6 100644 --- a/zix/tree_debug.h +++ b/zix/tree_debug.h @@ -23,20 +23,22 @@ static void zix_tree_print(ZixTreeNode* node, int level) { - if (node) { - if (!node->parent) { - printf("{{{\n"); - } - zix_tree_print(node->right, level + 1); - for (int i = 0; i < level; i++) { - printf(" "); - } - printf("%ld.%d\n", (intptr_t)node->data, node->balance); - zix_tree_print(node->left, level + 1); - if (!node->parent) { - printf("}}}\n"); - } - } + if (node) { + if (!node->parent) { + printf("{{{\n"); + } + + zix_tree_print(node->right, level + 1); + for (int i = 0; i < level; i++) { + printf(" "); + } + + printf("%ld.%d\n", (intptr_t)node->data, node->balance); + zix_tree_print(node->left, level + 1); + if (!node->parent) { + printf("}}}\n"); + } + } } #endif @@ -44,11 +46,11 @@ zix_tree_print(ZixTreeNode* node, int level) static size_t height(ZixTreeNode* n) { - if (!n) { - return 0; - } else { - return 1 + MAX(height(n->left), height(n->right)); - } + if (!n) { + return 0; + } else { + return 1 + MAX(height(n->left), height(n->right)); + } } #endif @@ -56,47 +58,59 @@ height(ZixTreeNode* n) static bool verify_balance(ZixTreeNode* n) { - if (!n) { - return true; - } - - if (n->balance < -2 || n->balance > 2) { - fprintf(stderr, "Balance out of range : %ld (balance %d)\n", - (intptr_t)n->data, n->balance); - return false; - } - - if (n->balance < 0 && !n->left) { - fprintf(stderr, "Bad balance : %ld (balance %d) has no left child\n", - (intptr_t)n->data, n->balance); - return false; - } - - if (n->balance > 0 && !n->right) { - fprintf(stderr, "Bad balance : %ld (balance %d) has no right child\n", - (intptr_t)n->data, n->balance); - return false; - } - - if (n->balance != 0 && !n->left && !n->right) { - fprintf(stderr, "Bad balance : %ld (balance %d) has no children\n", - (intptr_t)n->data, n->balance); - return false; - } - -#ifdef ZIX_TREE_HYPER_VERIFY - const intptr_t left_height = (intptr_t)height(n->left); - const intptr_t right_height = (intptr_t)height(n->right); - if (n->balance != right_height - left_height) { - fprintf(stderr, "Bad balance at %ld: h_r (%" PRIdPTR ")" - "- l_h (%" PRIdPTR ") != %d\n", - (intptr_t)n->data, right_height, left_height, n->balance); - assert(false); - return false; - } -#endif - - return true; + if (!n) { + return true; + } + + if (n->balance < -2 || n->balance > 2) { + fprintf(stderr, + "Balance out of range : %ld (balance %d)\n", + (intptr_t)n->data, + n->balance); + return false; + } + + if (n->balance < 0 && !n->left) { + fprintf(stderr, + "Bad balance : %ld (balance %d) has no left child\n", + (intptr_t)n->data, + n->balance); + return false; + } + + if (n->balance > 0 && !n->right) { + fprintf(stderr, + "Bad balance : %ld (balance %d) has no right child\n", + (intptr_t)n->data, + n->balance); + return false; + } + + if (n->balance != 0 && !n->left && !n->right) { + fprintf(stderr, + "Bad balance : %ld (balance %d) has no children\n", + (intptr_t)n->data, + n->balance); + return false; + } + +# ifdef ZIX_TREE_HYPER_VERIFY + const intptr_t left_height = (intptr_t)height(n->left); + const intptr_t right_height = (intptr_t)height(n->right); + if (n->balance != right_height - left_height) { + fprintf(stderr, + "Bad balance at %ld: h_r (%" PRIdPTR ")" + "- l_h (%" PRIdPTR ") != %d\n", + (intptr_t)n->data, + right_height, + left_height, + n->balance); + assert(false); + return false; + } +# endif + + return true; } #endif @@ -104,54 +118,58 @@ verify_balance(ZixTreeNode* n) static bool verify(ZixTree* t, ZixTreeNode* n) { - if (!n) { - return true; - } - - if (n->parent) { - if ((n->parent->left != n) && (n->parent->right != n)) { - fprintf(stderr, "Corrupt child/parent pointers\n"); - return false; - } - } - - if (n->left) { - if (t->cmp(n->left->data, n->data, t->cmp_data) > 0) { - fprintf(stderr, "Bad order: %" PRIdPTR " with left child\n", - (intptr_t)n->data); - fprintf(stderr, "%p ? %p\n", (void*)n, (void*)n->left); - fprintf(stderr, "%" PRIdPTR " ? %" PRIdPTR "\n", (intptr_t)n->data, - (intptr_t)n->left->data); - return false; - } - if (!verify(t, n->left)) { - return false; - } - } - - if (n->right) { - if (t->cmp(n->right->data, n->data, t->cmp_data) < 0) { - fprintf(stderr, "Bad order: %" PRIdPTR " with right child\n", - (intptr_t)n->data); - return false; - } - if (!verify(t, n->right)) { - return false; - } - } - - if (!verify_balance(n)) { - return false; - } - - if (n->balance <= -2 || n->balance >= 2) { - fprintf(stderr, "Imbalance: %p (balance %d)\n", - (void*)n, n->balance); - return false; - } - - return true; + if (!n) { + return true; + } + + if (n->parent) { + if ((n->parent->left != n) && (n->parent->right != n)) { + fprintf(stderr, "Corrupt child/parent pointers\n"); + return false; + } + } + + if (n->left) { + if (t->cmp(n->left->data, n->data, t->cmp_data) > 0) { + fprintf( + stderr, "Bad order: %" PRIdPTR " with left child\n", (intptr_t)n->data); + fprintf(stderr, "%p ? %p\n", (void*)n, (void*)n->left); + fprintf(stderr, + "%" PRIdPTR " ? %" PRIdPTR "\n", + (intptr_t)n->data, + (intptr_t)n->left->data); + return false; + } + + if (!verify(t, n->left)) { + return false; + } + } + + if (n->right) { + if (t->cmp(n->right->data, n->data, t->cmp_data) < 0) { + fprintf(stderr, + "Bad order: %" PRIdPTR " with right child\n", + (intptr_t)n->data); + return false; + } + + if (!verify(t, n->right)) { + return false; + } + } + + if (!verify_balance(n)) { + return false; + } + + if (n->balance <= -2 || n->balance >= 2) { + fprintf(stderr, "Imbalance: %p (balance %d)\n", (void*)n, n->balance); + return false; + } + + return true; } #endif -#endif // ZIX_TREE_DEBUG_H +#endif // ZIX_TREE_DEBUG_H |