From 640a3b38b918fee3607530d13b0a7897d8583bc6 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Fri, 18 Oct 2019 16:29:19 +0200 Subject: Fix bug when deleting root node of BTree --- zix/btree.c | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-) (limited to 'zix') diff --git a/zix/btree.c b/zix/btree.c index b5e4b88..de5d777 100644 --- a/zix/btree.c +++ b/zix/btree.c @@ -1,5 +1,5 @@ /* - Copyright 2011-2014 David Robillard + Copyright 2011-2019 David Robillard Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above @@ -557,6 +557,15 @@ zix_btree_remove(ZixBTree* const t, !zix_btree_node_is_minimal(n->children[i + 1])) { // Steal a key from child's right sibling n = zix_btree_rotate_left(n, i); + } else if (n == t->root && n->n_vals == 1) { + // Root has two children, both minimal, delete it + assert(i == 0 || i == 1); + const uint16_t counts[2] = {n->children[0]->n_vals, + n->children[1]->n_vals}; + + n = zix_btree_merge(t, n, 0); + ti->stack[ti->level].node = n; + ti->stack[ti->level].index = counts[i]; } else { // Both child's siblings are minimal, merge them if (i < n->n_vals) { -- cgit v1.2.1