shithub: gefs

Download patch

ref: 6a03fb24de2ceb5b093e3771351c71adc4f4db49
parent: b73fa273322688000ae7c71d7582b019c0265671
author: glenda <glenda@9front.local>
date: Sun Nov 28 15:42:18 EST 2021 

lookup: collect all the way up the tree.


--- a/fns.h
+++ b/fns.h
@@ -40,7 +40,7 @@
 
 int	btupsert(Tree*, Msg*, int);
 char	*btlookup(Tree*, Key*, Kvp*, char*, int);
-char	*btlookupat(Blk*, Key*, Kvp*, char*, int);
+char	*btlookupat(Blk*, int, Key*, Kvp*, char*, int);
 char	*btscan(Tree*, Scan*, char*, int);
 char	*btnext(Scan*, Kvp*, int*);
 void	btdone(Scan*);
--- a/fs.c
+++ b/fs.c
@@ -41,17 +41,15 @@
 {
 	char *e;
 	Blk *b;
+	int h;
 
-	if(f->root.bp.addr == -1)
-		b = getroot(&fs->root, nil);
-	else
-		b = getblk(f->root.bp, 0);
-	if(b == nil)
+	assert(f->root.bp.addr == -1);
+	if((b = getroot(&fs->root, &h)) == nil)
 		return Efs;
 
 	if(lk)
 		rlock(f->dent);
-	e = btlookupat(b, k, kv, buf, nbuf);
+	e = btlookupat(b, h, k, kv, buf, nbuf);
 	if(lk)
 		runlock(f->dent);
 	putblk(b);
--- a/tree.c
+++ b/tree.c
@@ -1198,75 +1198,45 @@
 	return getblk(bp, 0);
 }
 
-static char*
-collect(Blk *b, Key *k, Kvp *r, char *buf, int nbuf, int *done)
+char*
+btlookupat(Blk *b, int h, Key *k, Kvp *r, char *buf, int nbuf)
 {
-	int i, idx, same;
+	int i, j, ok, same;
 	char *err;
+	Blk **p;
 	Msg m;
 
-	*done = 0;
-	idx = bufsearch(b, k, &m, &same);
-	if(!same)
-		return nil;
+	assert(k != r);
+	if((p = calloc(h, sizeof(Blk*))) == nil)
+		return Emem;
 	err = Eexist;
-	for(i = idx; i < b->nbuf; i++){
-		getmsg(b, i, &m);
-		if(keycmp(&m, k) != 0)
-			break;
-		switch(m.op){
-		case Oinsert:
-			cpkvp(r, &m, buf, nbuf);
-			*done = 1;
-			err = nil;
-			break;
-		case Odelete:
-			*done = 1;
-			err = Eexist;
-			break;
-		case Owstat:
-//			statupdate(r, &m);
-			break;
-		default:
+	p[0] = refblk(b);
+	for(i = 1; i < h; i++){
+		if(blksearch(p[i-1], k, r, nil) == -1)
+			goto Out;
+		if((p[i] = getblk(r->bp, 0)) == nil)
 			return Efs;
-		}
 	}
-	return err;
-}
-
-char*
-btlookupat(Blk *b0, Key *k, Kvp *r, char *buf, int nbuf)
-{
-	int idx, same, done, r0;
-	char *ret, *err;
-	Blk *b, *c;
-
-	r0 = b0->ref;
-	b = refblk(b0);
-	assert(k != r);
-	while(b->type == Tpivot){
-		ret = collect(b, k, r, buf, nbuf, &done);
-		if(done)
-			return ret;
-		idx = blksearch(b, k, r, nil);
-		if(idx == -1){
-			assert(b0->ref == r0 + (b == b0) ? 1 : 0);
-			putblk(b);
-			return Eexist;
+	blksearch(p[h-1], k, r, &ok);
+	if(ok)
+		cpkvp(r, r, buf, nbuf);
+	for(i = h - 2; i >= 0; i--){
+		j = bufsearch(p[i], k, &m, &same);
+		if(!same)
+			continue;
+		for(; j < p[i]->nbuf; j++){
+			getmsg(p[i], j, &m);
+			if(keycmp(k, &m) != 0)
+				break;
+			ok = apply(r, &m, buf, nbuf);
 		}
-		if((c = getblk(r->bp, 0)) == nil)
-			return Efs;
-		putblk(b);
-		b = c;
 	}
-	assert(b->type == Tleaf);
-	err = Eexist;
-	blksearch(b, k, r, &same);
-	if(same){
-		cpkvp(r, r, buf, nbuf);
+	if(ok)
 		err = nil;
-	}
-	putblk(b);
+Out:
+	for(i = 0; i < h; i++)
+		if(p[i] != nil)
+			putblk(p[i]);
 	return err;
 }
 
@@ -1275,10 +1245,11 @@
 {
 	char *ret;
 	Blk *b;
+	int h;
 
-	if((b = getroot(t, nil)) == nil)
+	if((b = getroot(t, &h)) == nil)
 		return Efs;
-	ret = btlookupat(b, k, r, buf, nbuf);
+	ret = btlookupat(b, h, k, r, buf, nbuf);
 	putblk(b);
 
 	return ret;