X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/putty/blobdiff_plain/2d56b16ff20a3ca254f6058222e15595c5094652..a8cc197c711b4381e8050e0ecfc3458873f24468:/tree234.c

diff --git a/tree234.c b/tree234.c
index 8101c78b..7830aebb 100644
--- a/tree234.c
+++ b/tree234.c
@@ -6,10 +6,12 @@
 #include <stdio.h>
 #include <stdlib.h>
 
+#include "puttymem.h"
+
 #include "tree234.h"
 
-#define mknew(typ) ( (typ *) malloc (sizeof (typ)) )
-#define sfree free
+#define mknew(typ) ( (typ *) smalloc (sizeof (typ)) )
+/* #define sfree free */
 
 #ifdef TEST
 #define LOG(x) (printf x)
@@ -569,6 +571,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 +644,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>
@@ -806,8 +821,8 @@ void addtest(void *elem) {
 
     if (arraysize < arraylen+1) {
         arraysize = arraylen+1+256;
-        array = (array == NULL ? malloc(arraysize*sizeof(*array)) :
-                 realloc(array, arraysize*sizeof(*array)));
+        array = (array == NULL ? smalloc(arraysize*sizeof(*array)) :
+                 srealloc(array, arraysize*sizeof(*array)));
     }
 
     i = 0;