ref: 6a03fb24de2ceb5b093e3771351c71adc4f4db49
parent: b73fa273322688000ae7c71d7582b019c0265671
author: glenda <[email protected]>
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;