8a3c36e8d07add4f12a224771e31e9a13ac0daef
[vcfs.git] / blocktree.c
1 #include <stdlib.h>
2 #include <errno.h>
3 #include <string.h>
4
5 #include "store.h"
6 #include "blocktree.h"
7
8 #define min(a, b) (((b) < (a))?(b):(a))
9
10 ssize_t btget(struct store *st, struct btnode *tree, block_t bl, void *buf, size_t len)
11 {
12     int d;
13     block_t c, sel;
14     struct btnode indir[BT_INDSZ];
15     ssize_t sz;
16     
17     if(tree->d == 0) {
18         errno = ERANGE;
19         return(-1);
20     }
21     while(1) {
22         d = tree->d & 0x7f;
23         /* This check should really only be necessary on the first
24          * iteration, but I felt it was easier to put it in the
25          * loop. */
26         if((bl >> (d * BT_INDBITS)) > 0) {
27             errno = ERANGE;
28             return(-1);
29         }
30         
31         if(d == 0)
32             return(storeget(st, buf, len, &tree->a));
33         
34         /* Luckily, this is tail recursive */
35         if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
36             return(-1);
37         c = sz / sizeof(struct btnode);
38         sel = bl >> ((d - 1) * BT_INDBITS);
39         if(sel >= c) {
40             errno = ERANGE;
41             return(-1);
42         }
43         tree = &indir[sel];
44         bl &= (1LL << ((d - 1) * BT_INDBITS)) - 1;
45     }
46     return(0);
47 }
48
49 static int btputleaf(struct store *st, struct btnode *leaf, struct btop *op, block_t bloff)
50 {
51     void *buf;
52     struct addr na;
53     int ret;
54     
55     buf = NULL;
56     if(op->buf == NULL) {
57         buf = op->buf = malloc(op->len);
58         if(op->fillfn(buf, op->len, op->pdata))
59             return(-1);
60     }
61     ret = storeput(st, op->buf, op->len, &na);
62     if(buf != NULL)
63         free(buf);
64     if(ret)
65         return(-1);
66     leaf->d = 0x80;
67     leaf->a = na;
68     return(0);
69 }
70
71 static int countops(struct btop *ops, int numops, block_t bloff, block_t maxbl)
72 {
73     int i;
74     
75     for(i = 0; i < numops; i++) {
76         if(ops[i].blk - bloff >= maxbl)
77             break;
78     }
79     return(i);
80 }
81
82 /*
83  * blputmany() in many ways makes the code uglier, but it saves a
84  * *lot* of space, since it doesn't need to store intermediary blocks.
85  */
86 static int btputmany2(struct store *st, struct btnode *tree, struct btop *ops, int numops, block_t bloff)
87 {
88     int i, subops, d, f, hasid;
89     block_t c, sel, bl, nextsz;
90     struct addr na;
91     struct btnode indir[BT_INDSZ];
92     ssize_t sz;
93     
94     d = tree->d & 0x7f;
95     f = tree->d & 0x80;
96
97     hasid = 0;
98     
99     for(i = 0; i < numops; ) {
100         bl = ops[i].blk - bloff;
101     
102         if((d == 0) && (bl == 0)) {
103             if(btputleaf(st, tree, ops, bloff))
104                 return(-1);
105             i++;
106             continue;
107         }
108     
109         if(f && (bl == (1LL << (d * BT_INDBITS)))) {
110             /* New level of indirection */
111             if(hasid) {
112                 if(storeput(st, indir, c * sizeof(struct btnode), &na))
113                     return(-1);
114                 tree->a = na;
115             }
116             indir[0] = *tree;
117             tree->d = ++d;
118             f = 0;
119             c = 1;
120             hasid = 1;
121         } else if(d == 0) {
122             /* New tree */
123             if(bl != 0) {
124                 errno = ERANGE;
125                 return(-1);
126             }
127             /* Assume that numops == largest block number + 1 -- gaps
128              * will be detected as errors later */
129             for(bl = numops - 1; bl > 0; d++, bl <<= BT_INDBITS);
130             tree->d = d;
131             c = 0;
132             hasid = 1;
133         } else {
134             /* Get indirect block */
135             if(!hasid) {
136                 if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
137                     return(-1);
138                 c = sz / sizeof(struct btnode);
139                 hasid = 1;
140             }
141         }
142
143         sel = bl >> ((d - 1) * BT_INDBITS);
144         if(sel > c) {
145             errno = ERANGE;
146             return(-1);
147         }
148     
149         if(sel == c) {
150             /* Append new */
151             if((c > 0) && (!(indir[c - 1].d & 0x80) || ((indir[c - 1].d & 0x7f) < (d - 1)))) {
152                 errno = ERANGE;
153                 return(-1);
154             }
155             indir[c].d = 0;
156             c++;
157         }
158         nextsz = 1LL << ((d - 1) * BT_INDBITS);
159         subops = countops(ops + i, numops - i, bloff + (sel * nextsz), nextsz);
160         if(btputmany2(st, &indir[sel], ops + i, subops, bloff + (sel * nextsz)))
161             return(-1);
162         i += subops;
163         
164         if((sel == BT_INDSZ - 1) && (indir[sel].d == ((d - 1) | 0x80))) {
165             tree->d |= 0x80;
166             f = 1;
167         }
168     }
169     if(hasid) {
170         if(storeput(st, indir, c * sizeof(struct btnode), &na))
171             return(-1);
172         tree->a = na;
173     }
174     return(0);
175 }
176
177 int btputmany(struct store *st, struct btnode *tree, struct btop *ops, int numops)
178 {
179     return(btputmany2(st, tree, ops, numops, 0));
180 }
181
182 int btput(struct store *st, struct btnode *tree, block_t bl, void *buf, size_t len)
183 {
184     struct btop ops[1];
185     
186     ops[0].blk = bl;
187     ops[0].buf = buf;
188     ops[0].len = len;
189     return(btputmany(st, tree, ops, 1));
190 }
191
192 void btmkop(struct btop *op, block_t bl, void *buf, size_t len)
193 {
194     memset(op, 0, sizeof(*op));
195     op->blk = bl;
196     op->buf = buf;
197     op->len = len;
198 }
199
200 static int opcmp(const struct btop **op1, const struct btop **op2)
201 {
202     return((*op1)->blk - (*op2)->blk);
203 }
204
205 void btsortops(struct btop *ops, int numops)
206 {
207     qsort(ops, numops, sizeof(*ops), (int (*)(const void *, const void *))opcmp);
208 }
209
210 /*
211 Obsoleted
212
213 int btappend(struct store *st, struct btnode *tree, void *buf, size_t len)
214 {
215     int d, f;
216     struct btnode indir[BT_INDSZ];
217     struct addr na;
218     block_t c;
219     ssize_t sz;
220     
221     d = tree->d & 0x7f;
222     f = tree->d & 0x80;
223     
224     if(f) {
225         if(storeput(st, buf, len, &na))
226             return(-1);
227         indir[0] = *tree;
228         indir[1].d = 0x80;
229         indir[1].a = na;
230         if(storeput(st, indir, 2 * sizeof(*indir), &na))
231             return(-1);
232         tree->d = d + 1;
233         tree->a = na;
234         return(0);
235     }
236     
237     if(d == 0) {
238         if(storeput(st, buf, len, &na))
239             return(-1);
240         tree->d |= 0x80;
241         tree->a = na;
242         return(0);
243     }
244     
245     if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
246         return(-1);
247     c = sz / sizeof(struct btnode);
248     if(!(indir[c - 1].d & 0x80) || ((indir[c - 1].d & 0x7f) < (d - 1))) {
249         if(btappend(st, &indir[c - 1], buf, len))
250             return(-1);
251         if(storeput(st, indir, sz, &na))
252             return(-1);
253         tree->a = na;
254         if((indir[c - 1].d & 0x80) && ((indir[c - 1].d & 0x7f) == (d - 1)))
255             tree->d |= 0x80;
256         return(0);
257     }
258     
259     if(storeput(st, buf, len, &na))
260         return(-1);
261     indir[c].d = 0x80;
262     indir[c].a = na;
263     if(storeput(st, indir, sz + sizeof(struct btnode), &na))
264         return(-1);
265     tree->a = na;
266     return(0);
267 }
268 */
269
270 block_t btcount(struct store *st, struct btnode *tree)
271 {
272     int d, f;
273     struct btnode indir[BT_INDSZ];
274     block_t c, ret;
275     ssize_t sz;
276     
277     d = tree->d & 0x7f;
278     f = tree->d & 0x80;
279     
280     if(f)
281         return(1LL << (d * BT_INDBITS));
282     
283     if(d == 0)
284         return(0);
285     
286     ret = 0;
287     while(1) {
288         if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
289             return(-1);
290         c = sz / sizeof(struct btnode);
291         ret += (c - 1) * (1LL << ((d - 1) * BT_INDBITS));
292         d = indir[c - 1].d & 0x7f;
293         f = indir[c - 1].d & 0x80;
294         if(f)
295             return(ret + (1LL << (d * BT_INDBITS)));
296         tree = &indir[c - 1];
297     }
298 }