From 9ac3f4e009fd0d393d2c41449b121498e5b7ad54 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Thu, 18 Aug 2022 16:44:28 -0400 Subject: Reduce zix_tree_insert() complexity --- src/tree.c | 18 ++++++------------ 1 file changed, 6 insertions(+), 12 deletions(-) diff --git a/src/tree.c b/src/tree.c index f745fa6..3355a62 100644 --- a/src/tree.c +++ b/src/tree.c @@ -380,17 +380,11 @@ zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti) if (p && p_height_increased) { int height_change = 0; for (ZixTreeNode* i = p; i && i->parent; i = i->parent) { - if (i == i->parent->left) { - if (--i->parent->balance == -2) { - zix_tree_rebalance(t, i->parent, &height_change); - break; - } - } else { - assert(i == i->parent->right); - if (++i->parent->balance == 2) { - zix_tree_rebalance(t, i->parent, &height_change); - break; - } + i->parent->balance += (i == i->parent->left) ? -1 : 1; + + if (i->parent->balance == -2 || i->parent->balance == 2) { + zix_tree_rebalance(t, i->parent, &height_change); + break; } if (i->parent->balance == 0) { @@ -525,7 +519,7 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti) replace->parent->right == replace); } - // Rebalance starting at to_balance upwards. + // Rebalance starting at to_balance upwards for (ZixTreeNode* i = to_balance; i; i = i->parent) { i->balance += d_balance; if (d_balance == 0 || i->balance == -1 || i->balance == 1) { -- cgit v1.2.1