8 #define min(a, b) (((b) < (a))?(b):(a))
9 #define ISDELOP(op) (((op).buf == NULL) && ((op).fillfn == NULL))
11 ssize_t btget(struct store *st, struct btnode *tree, block_t bl, void *buf, size_t len, size_t blsize)
15 struct btnode indir[1 << blsize];
24 /* This check should really only be necessary on the first
25 * iteration, but I felt it was easier to put it in the
27 if((bl >> (d * blsize)) > 0) {
33 return(storeget(st, buf, len, &tree->a));
35 /* Luckily, this is tail recursive */
36 if((sz = storeget(st, indir, sizeof(indir), &tree->a)) < 0)
38 c = sz / sizeof(struct btnode);
39 sel = bl >> ((d - 1) * blsize);
45 bl &= (1LL << ((d - 1) * blsize)) - 1;
50 static int btputleaf(struct store *st, struct btnode *leaf, struct btop *op, block_t bloff)
62 buf = op->buf = malloc(op->len);
63 if(op->fillfn(buf, op->len, op->pdata))
66 ret = storeput(st, op->buf, op->len, &na);
76 static int countops(struct btop *ops, int numops, block_t bloff, block_t maxbl)
80 for(i = 0; i < numops; i++) {
81 if(ops[i].blk - bloff >= maxbl)
88 * blputmany() in many ways makes the code uglier, but it saves a
89 * *lot* of space, since it doesn't need to store intermediary blocks.
91 static int btputmany2(struct store *st, struct btnode *tree, struct btop *ops, int numops, size_t blsize, block_t bloff)
93 int i, subops, d, f, hasid;
94 block_t c, sel, bl, nextsz;
96 struct btnode indir[1 << blsize];
104 for(i = 0; i < numops; ) {
105 if(ops[i].blk < bloff) {
109 bl = ops[i].blk - bloff;
111 if((d == 0) && (bl == 0)) {
112 if(btputleaf(st, tree, ops, bloff))
118 if(f && (bl == (1LL << (d * blsize)))) {
119 /* New level of indirection */
121 if(storeput(st, indir, c * sizeof(struct btnode), &na))
136 /* Assume that numops == largest block number + 1 -- gaps
137 * will be detected as errors later */
138 for(bl = numops - 1; bl > 0; d++, bl <<= blsize);
143 /* Get indirect block */
145 if((sz = storeget(st, indir, sizeof(indir), &tree->a)) < 0)
147 c = sz / sizeof(struct btnode);
152 sel = bl >> ((d - 1) * blsize);
160 if((c > 0) && (!(indir[c - 1].d & 0x80) || ((indir[c - 1].d & 0x7f) < (d - 1)))) {
167 nextsz = 1LL << ((d - 1) * blsize);
168 subops = countops(ops + i, numops - i, bloff + (sel * nextsz), nextsz);
169 if(btputmany2(st, &indir[sel], ops + i, subops, blsize, bloff + (sel * nextsz)))
173 if((sel == (1 << blsize) - 1) && (indir[sel].d == ((d - 1) | 0x80))) {
177 } else if(indir[sel].d == 0) {
180 tree->d = indir[0].d;
181 tree->a = indir[0].a;
186 if(storeput(st, indir, c * sizeof(struct btnode), &na))
193 int btputmany(struct store *st, struct btnode *tree, struct btop *ops, int numops, size_t blsize)
195 return(btputmany2(st, tree, ops, numops, blsize, 0));
198 int btput(struct store *st, struct btnode *tree, block_t bl, void *buf, size_t len, size_t blsize)
202 memset(&ops, 0, sizeof(ops));
206 return(btputmany(st, tree, &ops, 1, blsize));
209 void btmkop(struct btop *op, block_t bl, void *buf, size_t len)
211 memset(op, 0, sizeof(*op));
217 static int opcmp(const struct btop **op1, const struct btop **op2)
219 if(ISDELOP(**op1) && ISDELOP(**op2))
220 return((*op2)->blk - (*op1)->blk);
221 else if(!ISDELOP(**op1) && ISDELOP(**op2))
223 else if(ISDELOP(**op1) && !ISDELOP(**op2))
226 return((*op1)->blk - (*op2)->blk);
229 void btsortops(struct btop *ops, int numops)
231 qsort(ops, numops, sizeof(*ops), (int (*)(const void *, const void *))opcmp);
234 block_t btcount(struct store *st, struct btnode *tree, size_t blsize)
237 struct btnode indir[1 << blsize];
245 return(1LL << (d * blsize));
252 if((sz = storeget(st, indir, sizeof(indir), &tree->a)) < 0)
254 c = sz / sizeof(struct btnode);
255 ret += (c - 1) * (1LL << ((d - 1) * blsize));
256 d = indir[c - 1].d & 0x7f;
257 f = indir[c - 1].d & 0x80;
259 return(ret + (1LL << (d * blsize)));
260 tree = &indir[c - 1];