diff options
| author | David Robillard <d@drobilla.net> | 2019-10-18 16:29:19 +0200 |
|---|---|---|
| committer | David Robillard <d@drobilla.net> | 2019-10-18 16:31:23 +0200 |
| commit | 640a3b38b918fee3607530d13b0a7897d8583bc6 (patch) | |
| tree | d9cddf30576082c6b526eb0c63f566344656226a /zix | |
| parent | 7c80def6c18674804cbbc607de5e1acf459d5d78 (diff) | |
| download | zix-640a3b38b918fee3607530d13b0a7897d8583bc6.tar.gz zix-640a3b38b918fee3607530d13b0a7897d8583bc6.tar.bz2 zix-640a3b38b918fee3607530d13b0a7897d8583bc6.zip | |
Fix bug when deleting root node of BTree
Diffstat (limited to 'zix')
| -rw-r--r-- | zix/btree.c | 11 |
1 files changed, 10 insertions, 1 deletions
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 <http://drobilla.net> + Copyright 2011-2019 David Robillard <http://drobilla.net> 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) { |