a973e8f8ec4af3a5e155361d313fb32c54b6a1c6
[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 #define ISDELOP(op) (((op).buf == NULL) && ((op).fillfn == NULL))
10
11 ssize_t btget(struct store *st, struct btnode *tree, block_t bl, void *buf, size_t len)
12 {
13     int d;
14     block_t c, sel;
15     struct btnode indir[BT_INDSZ];
16     ssize_t sz;
17     
18     if(tree->d == 0) {
19         errno = ERANGE;
20         return(-1);
21     }
22     while(1) {
23         d = tree->d & 0x7f;
24         /* This check should really only be necessary on the first
25          * iteration, but I felt it was easier to put it in the
26          * loop. */
27         if((bl >> (d * BT_INDBITS)) > 0) {
28             errno = ERANGE;
29             return(-1);
30         }
31         
32         if(d == 0)
33             return(storeget(st, buf, len, &tree->a));
34         
35         /* Luckily, this is tail recursive */
36         if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
37             return(-1);
38         c = sz / sizeof(struct btnode);
39         sel = bl >> ((d - 1) * BT_INDBITS);
40         if(sel >= c) {
41             errno = ERANGE;
42             return(-1);
43         }
44         tree = &indir[sel];
45         bl &= (1LL << ((d - 1) * BT_INDBITS)) - 1;
46     }
47     return(0);
48 }
49
50 static int btputleaf(struct store *st, struct btnode *leaf, struct btop *op, block_t bloff)
51 {
52     void *buf;
53     struct addr na;
54     int ret;
55     
56     if(ISDELOP(*op)) {
57         leaf->d = 0;
58         return(0);
59     }
60     buf = NULL;
61     if(op->buf == NULL) {
62         buf = op->buf = malloc(op->len);
63         if(op->fillfn(buf, op->len, op->pdata))
64             return(-1);
65     }
66     ret = storeput(st, op->buf, op->len, &na);
67     if(buf != NULL)
68         free(buf);
69     if(ret)
70         return(-1);
71     leaf->d = 0x80;
72     leaf->a = na;
73     return(0);
74 }
75
76 static int countops(struct btop *ops, int numops, block_t bloff, block_t maxbl)
77 {
78     int i;
79     
80     for(i = 0; i < numops; i++) {
81         if(ops[i].blk - bloff >= maxbl)
82             break;
83     }
84     return(i);
85 }
86
87 /*
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.
90  */
91 static int btputmany2(struct store *st, struct btnode *tree, struct btop *ops, int numops, block_t bloff)
92 {
93     int i, subops, d, f, hasid;
94     block_t c, sel, bl, nextsz;
95     struct addr na;
96     struct btnode indir[BT_INDSZ];
97     ssize_t sz;
98     
99     d = tree->d & 0x7f;
100     f = tree->d & 0x80;
101
102     hasid = 0;
103     
104     for(i = 0; i < numops; ) {
105         if(ops[i].blk < bloff) {
106             errno = ERANGE;
107             return(-1);
108         }
109         bl = ops[i].blk - bloff;
110     
111         if((d == 0) && (bl == 0)) {
112             if(btputleaf(st, tree, ops, bloff))
113                 return(-1);
114             i++;
115             continue;
116         }
117     
118         if(f && (bl == (1LL << (d * BT_INDBITS)))) {
119             /* New level of indirection */
120             if(hasid) {
121                 if(storeput(st, indir, c * sizeof(struct btnode), &na))
122                     return(-1);
123                 tree->a = na;
124             }
125             indir[0] = *tree;
126             tree->d = ++d;
127             f = 0;
128             c = 1;
129             hasid = 1;
130         } else if(d == 0) {
131             /* New tree */
132             if(bl != 0) {
133                 errno = ERANGE;
134                 return(-1);
135             }
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 <<= BT_INDBITS);
139             tree->d = d;
140             c = 0;
141             hasid = 1;
142         } else {
143             /* Get indirect block */
144             if(!hasid) {
145                 if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
146                     return(-1);
147                 c = sz / sizeof(struct btnode);
148                 hasid = 1;
149             }
150         }
151
152         sel = bl >> ((d - 1) * BT_INDBITS);
153         if(sel > c) {
154             errno = ERANGE;
155             return(-1);
156         }
157     
158         if(sel == c) {
159             /* Append new */
160             if((c > 0) && (!(indir[c - 1].d & 0x80) || ((indir[c - 1].d & 0x7f) < (d - 1)))) {
161                 errno = ERANGE;
162                 return(-1);
163             }
164             indir[c].d = 0;
165             c++;
166         }
167         nextsz = 1LL << ((d - 1) * BT_INDBITS);
168         subops = countops(ops + i, numops - i, bloff + (sel * nextsz), nextsz);
169         if(btputmany2(st, &indir[sel], ops + i, subops, bloff + (sel * nextsz)))
170             return(-1);
171         i += subops;
172         
173         if((sel == BT_INDSZ - 1) && (indir[sel].d == ((d - 1) | 0x80))) {
174             /* Filled up */
175             tree->d |= 0x80;
176             f = 1;
177         } else if(indir[sel].d == 0) {
178             /* Erased */
179             if(--c == 1) {
180                 tree->d = indir[0].d;
181                 tree->a = indir[0].a;
182             }
183         }
184     }
185     if(hasid) {
186         if(storeput(st, indir, c * sizeof(struct btnode), &na))
187             return(-1);
188         tree->a = na;
189     }
190     return(0);
191 }
192
193 int btputmany(struct store *st, struct btnode *tree, struct btop *ops, int numops)
194 {
195     return(btputmany2(st, tree, ops, numops, 0));
196 }
197
198 int btput(struct store *st, struct btnode *tree, block_t bl, void *buf, size_t len)
199 {
200     struct btop ops[1];
201     
202     ops[0].blk = bl;
203     ops[0].buf = buf;
204     ops[0].len = len;
205     return(btputmany(st, tree, ops, 1));
206 }
207
208 void btmkop(struct btop *op, block_t bl, void *buf, size_t len)
209 {
210     memset(op, 0, sizeof(*op));
211     op->blk = bl;
212     op->buf = buf;
213     op->len = len;
214 }
215
216 static int opcmp(const struct btop **op1, const struct btop **op2)
217 {
218     if(ISDELOP(**op1) && ISDELOP(**op2))
219         return((*op2)->blk - (*op1)->blk);
220     else if(!ISDELOP(**op1) && ISDELOP(**op2))
221         return(-1);
222     else if(ISDELOP(**op1) && !ISDELOP(**op2))
223         return(1);
224     else
225         return((*op1)->blk - (*op2)->blk);
226 }
227
228 void btsortops(struct btop *ops, int numops)
229 {
230     qsort(ops, numops, sizeof(*ops), (int (*)(const void *, const void *))opcmp);
231 }
232
233 block_t btcount(struct store *st, struct btnode *tree)
234 {
235     int d, f;
236     struct btnode indir[BT_INDSZ];
237     block_t c, ret;
238     ssize_t sz;
239     
240     d = tree->d & 0x7f;
241     f = tree->d & 0x80;
242     
243     if(f)
244         return(1LL << (d * BT_INDBITS));
245     
246     if(d == 0)
247         return(0);
248     
249     ret = 0;
250     while(1) {
251         if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
252             return(-1);
253         c = sz / sizeof(struct btnode);
254         ret += (c - 1) * (1LL << ((d - 1) * BT_INDBITS));
255         d = indir[c - 1].d & 0x7f;
256         f = indir[c - 1].d & 0x80;
257         if(f)
258             return(ret + (1LL << (d * BT_INDBITS)));
259         tree = &indir[c - 1];
260     }
261 }