From 6613c6d53cc47ead36729a82dc5a718f5213a2df Mon Sep 17 00:00:00 2001 From: 0scar Date: Tue, 16 Nov 2021 12:17:01 +0100 Subject: Fix child_merge and delete OOB index Child merge didn't copy children properly, since it incremented number of children in `y` as it copied children from `z`. Also, deletion could index into a free'd node after merging. --- src/btree_naive.c | 15 ++++++++++++--- 1 file changed, 12 insertions(+), 3 deletions(-) (limited to 'src/btree_naive.c') diff --git a/src/btree_naive.c b/src/btree_naive.c index 8232a7f..01b57f3 100644 --- a/src/btree_naive.c +++ b/src/btree_naive.c @@ -214,8 +214,9 @@ void node_child_merge( /* Move children from z to y */ for (j = 0; j < z->c; j++) { - y->children[j+y->c++] = z->children[j]; + y->children[j+y->c] = z->children[j]; } + y->c += z->c; /* Remove z from x */ for (j = i+1; j < x->c; j++) { @@ -531,8 +532,16 @@ int node_delete(struct node *x, } else { /* We need to determine wether we merge left or right, if possible */ - if (ii > 0) node_child_merge(x, ii - 1, degree, elem_size); - else node_child_merge(x, ii, degree, elem_size); + if (ii > 0) { + node_child_merge(x, ii - 1, degree, elem_size); + y = x->children[ii - 1]; + } + else if (ii < x->c - 1) { + node_child_merge(x, ii, degree, elem_size); + } + else { + perror("Cannot merge!"); + } } } -- cgit v1.3