Deletion case 2c can shift the root; case 3b is not the only case that

can do that. The bad case happens when you have a root node containing
only one actual element, and its two child nodes have only one element
each, and you try to delete the element in the root.

git-svn-id: svn://svn.tartarus.org/sgt/putty@660 cda61777-01e9-0310-a592-d414129be87e

diff --git a/tree234.c b/tree234.c
index 8101c78..f97837a 100644 (file)
--- a/tree234.c
+++ b/tree234.c
@@ -569,6 +569,17 @@ void del234(tree234 *t, void *e) {
            }
            n->elems[j] = NULL;
            n->kids[j+1] = NULL;
+            /*
+             * It's possible, in this case, that we've just removed
+             * the only element in the root of the tree. If so,
+             * shift the root.
+             */
+            if (n->elems[0] == NULL) {
+                LOG(("  shifting root!\n"));
+                t->root = a;
+                a->parent = NULL;
+                sfree(n);
+            }
            /*
             * Now go round the deletion process again, with n
             * pointing at the new big node and e still the same.