diff options
Diffstat (limited to 'src/tree.c')
| -rw-r--r-- | src/tree.c | 42 |
1 files changed, 12 insertions, 30 deletions
@@ -1,9 +1,11 @@ // Copyright 2011-2020 David Robillard <d@drobilla.net> // SPDX-License-Identifier: ISC -#include "zix/tree.h" +#include <zix/tree.h> -#include "zix/status.h" +#include <zix/allocator.h> +#include <zix/attributes.h> +#include <zix/status.h> #include <assert.h> @@ -31,13 +33,12 @@ struct ZixTreeNodeImpl { #define MIN(a, b) (((a) < (b)) ? (a) : (b)) #define MAX(a, b) (((a) > (b)) ? (a) : (b)) -// Uncomment these for debugging features -// #define ZIX_TREE_VERIFY 1 -// #define ZIX_TREE_HYPER_VERIFY 1 - -#if defined(ZIX_TREE_VERIFY) || defined(ZIX_TREE_HYPER_VERIFY) -# include "tree_debug.h" -# define ASSERT_BALANCE(n) assert(verify_balance(n)) +#ifndef NDEBUG +# define ASSERT_BALANCE(n) \ + assert(!(((n)->balance < -2 || (n)->balance > 2) || \ + ((n)->balance < 0 && !(n)->left) || \ + ((n)->balance > 0 && !(n)->right) || \ + ((n)->balance != 0 && !(n)->left && !(n)->right))) #else # define ASSERT_BALANCE(n) #endif @@ -282,10 +283,6 @@ rotate_right_left(ZixTreeNode* p, int* height_change) static ZixTreeNode* zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) { -#ifdef ZIX_TREE_HYPER_VERIFY - const size_t old_height = height(node); -#endif - *height_change = 0; const bool is_root = !node->parent; @@ -294,6 +291,7 @@ zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) ZixTreeNode* replacement = node; if (node->balance == -2) { assert(node->left); + // NOLINTNEXTLINE(clang-analyzer-core.NullDereference) if (node->left->balance == 1) { replacement = rotate_left_right(node, height_change); } else { @@ -301,6 +299,7 @@ zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) } } else if (node->balance == 2) { assert(node->right); + // NOLINTNEXTLINE(clang-analyzer-core.NullDereference) if (node->right->balance == -1) { replacement = rotate_right_left(node, height_change); } else { @@ -312,10 +311,6 @@ zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) t->root = replacement; } -#ifdef ZIX_TREE_HYPER_VERIFY - assert(old_height + *height_change == height(replacement)); -#endif - return replacement; } @@ -395,12 +390,6 @@ zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti) ++t->size; -#ifdef ZIX_TREE_VERIFY - if (!verify(t, t->root)) { - return ZIX_STATUS_ERROR; - } -#endif - return ZIX_STATUS_SUCCESS; } @@ -548,13 +537,6 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti) zix_free(t->allocator, n); --t->size; - -#ifdef ZIX_TREE_VERIFY - if (!verify(t, t->root)) { - return ZIX_STATUS_ERROR; - } -#endif - return ZIX_STATUS_SUCCESS; } |