X-Git-Url: https://git.distorted.org.uk/u/mdw/putty/blobdiff_plain/2d56b16ff20a3ca254f6058222e15595c5094652..a094ae434ec1d6a0f69af9b3ef6fbeb40fa96d92:/tree234.c

diff --git a/tree234.c b/tree234.c
index 8101c78b..fafb3706 100644
--- 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.
@@ -631,15 +642,17 @@ void *next234(enum234 *e) {
  * Test code for the 2-3-4 tree. This code maintains an alternative
  * representation of the data in the tree, in an array (using the
  * obvious and slow insert and delete functions). After each tree
- * operation, the tree_valid() function is called, which ensures
- * all the tree properties are preserved (node->child->parent
- * always equals node; number of kids == number of elements + 1;
- * all tree nodes are distinct; ordering property between elements
- * of a node and elements of its children is preserved) and also
- * ensures the list represented by the tree is the same list it
- * should be. (This last check also verifies the ordering
- * properties, because the `same list it should be' is by
- * definition correctly ordered.)
+ * operation, the verify() function is called, which ensures all
+ * the tree properties are preserved (node->child->parent always
+ * equals node; number of kids == 0 or number of elements + 1;
+ * ordering property between elements of a node and elements of its
+ * children is preserved; tree has the same depth everywhere; every
+ * node has at least one element) and also ensures the list
+ * represented by the tree is the same list it should be. (This
+ * last check also verifies the ordering properties, because the
+ * `same list it should be' is by definition correctly ordered. It
+ * also ensures all nodes are distinct, because the enum functions
+ * would get caught in a loop if not.)
  */
 
 #include <stdarg.h>