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 | |
| parent | 7c80def6c18674804cbbc607de5e1acf459d5d78 (diff) | |
| download | zix-640a3b38b918fee3607530d13b0a7897d8583bc6.tar.gz zix-640a3b38b918fee3607530d13b0a7897d8583bc6.tar.bz2 zix-640a3b38b918fee3607530d13b0a7897d8583bc6.zip | |
Fix bug when deleting root node of BTree
| -rw-r--r-- | test/btree_test.c | 26 | ||||
| -rw-r--r-- | zix/btree.c | 11 |
2 files changed, 34 insertions, 3 deletions
diff --git a/test/btree_test.c b/test/btree_test.c index 93a257f..c45b3e9 100644 --- a/test/btree_test.c +++ b/test/btree_test.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 @@ -324,7 +324,7 @@ stress(int test_num, size_t n_elems) } // Delete some elements in a random order - for (size_t e = 0; e < zix_btree_size(t); e++) { + for (size_t e = 0; e < zix_btree_size(t) / 2; e++) { r = ith_elem(test_num, n_elems, rand() % n_elems); uintptr_t removed; ZixStatus rst = zix_btree_remove(t, (void*)r, (void**)&removed, &next); @@ -335,6 +335,28 @@ stress(int test_num, size_t n_elems) zix_btree_iter_free(next); next = NULL; + // Delete all remaining elements via next iterator + next = zix_btree_begin(t); + uintptr_t last_value = 0; + while (!zix_btree_iter_is_end(next)) { + const uintptr_t value = (uintptr_t)zix_btree_get(next); + uintptr_t removed = 0; + if (zix_btree_remove(t, zix_btree_get(next), (void**)&removed, &next)) { + return test_fail(t, "Error removing next item %lu\n", (uintptr_t)r); + } else if (removed != value) { + return test_fail(t, "Removed wrong next item %lu != %lu\n", + removed, (uintptr_t)value); + } else if (removed < last_value) { + return test_fail(t, "Removed unordered next item %lu < %lu\n", + removed, (uintptr_t)value); + } + + last_value = removed; + } + assert(!next || zix_btree_size(t) == 0); + zix_btree_iter_free(next); + next = NULL; + zix_btree_free(t); // Test lower_bound with wildcard comparator 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) { |