d5cf5351 |
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 | |
d5cf5351 |
210 | block_t btcount(struct store *st, struct btnode *tree) |
211 | { |
212 | int d, f; |
213 | struct btnode indir[BT_INDSZ]; |
214 | block_t c, ret; |
215 | ssize_t sz; |
216 | |
217 | d = tree->d & 0x7f; |
218 | f = tree->d & 0x80; |
219 | |
220 | if(f) |
221 | return(1LL << (d * BT_INDBITS)); |
222 | |
223 | if(d == 0) |
224 | return(0); |
225 | |
226 | ret = 0; |
227 | while(1) { |
228 | if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0) |
229 | return(-1); |
230 | c = sz / sizeof(struct btnode); |
231 | ret += (c - 1) * (1LL << ((d - 1) * BT_INDBITS)); |
232 | d = indir[c - 1].d & 0x7f; |
233 | f = indir[c - 1].d & 0x80; |
234 | if(f) |
235 | return(ret + (1LL << (d * BT_INDBITS))); |
236 | tree = &indir[c - 1]; |
237 | } |
238 | } |