git: 9front

Download patch

ref: 64f48417193fd2c6f95e439199889791b2717aac
parent: f60a431a31aa3fa69b866600e675e44f872b6115
author: Ori Bernstein <ori@eigenstate.org>
date: Sat Nov 22 13:25:43 EST 2025 

gefs: no need for mid out parameter

we already should be pulling the right value when
we use the tree node, no need to actually collect
the thing at all. For splitting a pivot, make the
same change to move getting the midpoint to after
we did the full split and pull.


--- a/sys/src/cmd/gefs/tree.c
+++ b/sys/src/cmd/gefs/tree.c
@@ -677,7 +677,7 @@
  * grow the total height of the tree by more than 1.
  */
 static void
-splitleaf(Tree *t, Path *up, Path *p, Kvp *mid)
+splitleaf(Tree *t, Path *up, Path *p)
 {
 	char buf[Msgmax];
 	Blk *b, *d, *l, *r;
@@ -782,7 +782,6 @@
 	}
 	p->npull = (j - up->lo);
 	p->op = POsplit;
-	getval(r, 0, mid);
 	setb(&p->nl, t, l);
 	setb(&p->nr, t, r);
 	poperror();
@@ -795,11 +794,11 @@
  * than one.
  */
 static void
-splitpiv(Tree *t, Path *, Path *p, Path *pp, Kvp *mid)
+splitpiv(Tree *t, Path *, Path *p, Path *pp)
 {
 	int i, copied, halfsz;
 	Blk *b, *d, *l, *r;
-	Kvp tk;
+	Kvp tk, mid;
 	Msg m;
 
 	/*
@@ -823,16 +822,11 @@
 	bassert(b, b->nval >= 4);
 	for(i = 0; i < b->nval; i++){
 		/*
-		 * We're trying to balance size,
-		 * but we need at least 2 nodes
-		 * in each half of the split if
-		 * we want a valid tree.
+		 * Balance size, but ensure we have at least 2 nodes
+		 * in each half of the split so we have a valid tree.
 		 */
-		if(d == l)
-		if((i == b->nval-2) || (i >= 2 && copied >= halfsz)){
+		if(d == l && (i == b->nval-2 || (i >= 2 && copied >= halfsz)))
 			d = r;
-			getval(b, i, mid);
-		}
 		if(i == p->idx){
 			copyup(d, pp, &copied);
 			continue;
@@ -842,6 +836,7 @@
 		copied += valsz(&tk);
 	}
 	d = l;
+	getval(r, 0, &mid);
 	for(i = 0; i < b->nbuf; i++){
 		if(i == p->lo)
 			i += pp->npull;
@@ -848,7 +843,7 @@
 		if(i == b->nbuf)
 			break;
 		getmsg(b, i, &m);
-		if(d == l && keycmp(&m, mid) >= 0)
+		if(d == l && keycmp(&m, &mid) >= 0)
 			d = r;
 		setmsg(d, &m);
 	}
@@ -1079,7 +1074,6 @@
 {
 
 	Path *up, *p, *pp, *rp;
-	Kvp mid;
 
 	/*
 	 * The path must contain at minimum two elements:
@@ -1097,7 +1091,7 @@
 			updateleaf(t, p-1, p);
 			rp = p;
 		}else{
-			splitleaf(t, up, p, &mid);
+			splitleaf(t, up, p);
 		}
 		p->midx = -1;
 		pp = p;
@@ -1123,7 +1117,7 @@
 			updatepiv(t, up, p, pp);
 			rp = p;
 		}else{
-			splitpiv(t, up, p, pp, &mid);
+			splitpiv(t, up, p, pp);
 		}
 		pp = p;
 		up--;
-- 
⑨