diff options
Diffstat (limited to 'fs/nilfs2')
-rw-r--r-- | fs/nilfs2/btree.c | 456 |
1 files changed, 208 insertions, 248 deletions
diff --git a/fs/nilfs2/btree.c b/fs/nilfs2/btree.c index aa412724b64e..21ed8ccea4b9 100644 --- a/fs/nilfs2/btree.c +++ b/fs/nilfs2/btree.c | |||
@@ -71,21 +71,17 @@ void nilfs_btree_path_cache_destroy(void) | |||
71 | kmem_cache_destroy(nilfs_btree_path_cache); | 71 | kmem_cache_destroy(nilfs_btree_path_cache); |
72 | } | 72 | } |
73 | 73 | ||
74 | static inline struct nilfs_btree_path * | 74 | static inline struct nilfs_btree_path *nilfs_btree_alloc_path(void) |
75 | nilfs_btree_alloc_path(const struct nilfs_btree *btree) | ||
76 | { | 75 | { |
77 | return (struct nilfs_btree_path *) | 76 | return kmem_cache_alloc(nilfs_btree_path_cache, GFP_NOFS); |
78 | kmem_cache_alloc(nilfs_btree_path_cache, GFP_NOFS); | ||
79 | } | 77 | } |
80 | 78 | ||
81 | static inline void nilfs_btree_free_path(const struct nilfs_btree *btree, | 79 | static inline void nilfs_btree_free_path(struct nilfs_btree_path *path) |
82 | struct nilfs_btree_path *path) | ||
83 | { | 80 | { |
84 | kmem_cache_free(nilfs_btree_path_cache, path); | 81 | kmem_cache_free(nilfs_btree_path_cache, path); |
85 | } | 82 | } |
86 | 83 | ||
87 | static void nilfs_btree_init_path(const struct nilfs_btree *btree, | 84 | static void nilfs_btree_init_path(struct nilfs_btree_path *path) |
88 | struct nilfs_btree_path *path) | ||
89 | { | 85 | { |
90 | int level; | 86 | int level; |
91 | 87 | ||
@@ -101,8 +97,7 @@ static void nilfs_btree_init_path(const struct nilfs_btree *btree, | |||
101 | } | 97 | } |
102 | } | 98 | } |
103 | 99 | ||
104 | static void nilfs_btree_clear_path(const struct nilfs_btree *btree, | 100 | static void nilfs_btree_clear_path(struct nilfs_btree_path *path) |
105 | struct nilfs_btree_path *path) | ||
106 | { | 101 | { |
107 | int level; | 102 | int level; |
108 | 103 | ||
@@ -148,129 +143,110 @@ static int nilfs_btree_get_new_block(const struct nilfs_btree *btree, | |||
148 | } | 143 | } |
149 | 144 | ||
150 | static inline int | 145 | static inline int |
151 | nilfs_btree_node_get_flags(const struct nilfs_btree *btree, | 146 | nilfs_btree_node_get_flags(const struct nilfs_btree_node *node) |
152 | const struct nilfs_btree_node *node) | ||
153 | { | 147 | { |
154 | return node->bn_flags; | 148 | return node->bn_flags; |
155 | } | 149 | } |
156 | 150 | ||
157 | static inline void | 151 | static inline void |
158 | nilfs_btree_node_set_flags(struct nilfs_btree *btree, | 152 | nilfs_btree_node_set_flags(struct nilfs_btree_node *node, int flags) |
159 | struct nilfs_btree_node *node, | ||
160 | int flags) | ||
161 | { | 153 | { |
162 | node->bn_flags = flags; | 154 | node->bn_flags = flags; |
163 | } | 155 | } |
164 | 156 | ||
165 | static inline int nilfs_btree_node_root(const struct nilfs_btree *btree, | 157 | static inline int nilfs_btree_node_root(const struct nilfs_btree_node *node) |
166 | const struct nilfs_btree_node *node) | ||
167 | { | 158 | { |
168 | return nilfs_btree_node_get_flags(btree, node) & NILFS_BTREE_NODE_ROOT; | 159 | return nilfs_btree_node_get_flags(node) & NILFS_BTREE_NODE_ROOT; |
169 | } | 160 | } |
170 | 161 | ||
171 | static inline int | 162 | static inline int |
172 | nilfs_btree_node_get_level(const struct nilfs_btree *btree, | 163 | nilfs_btree_node_get_level(const struct nilfs_btree_node *node) |
173 | const struct nilfs_btree_node *node) | ||
174 | { | 164 | { |
175 | return node->bn_level; | 165 | return node->bn_level; |
176 | } | 166 | } |
177 | 167 | ||
178 | static inline void | 168 | static inline void |
179 | nilfs_btree_node_set_level(struct nilfs_btree *btree, | 169 | nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level) |
180 | struct nilfs_btree_node *node, | ||
181 | int level) | ||
182 | { | 170 | { |
183 | node->bn_level = level; | 171 | node->bn_level = level; |
184 | } | 172 | } |
185 | 173 | ||
186 | static inline int | 174 | static inline int |
187 | nilfs_btree_node_get_nchildren(const struct nilfs_btree *btree, | 175 | nilfs_btree_node_get_nchildren(const struct nilfs_btree_node *node) |
188 | const struct nilfs_btree_node *node) | ||
189 | { | 176 | { |
190 | return le16_to_cpu(node->bn_nchildren); | 177 | return le16_to_cpu(node->bn_nchildren); |
191 | } | 178 | } |
192 | 179 | ||
193 | static inline void | 180 | static inline void |
194 | nilfs_btree_node_set_nchildren(struct nilfs_btree *btree, | 181 | nilfs_btree_node_set_nchildren(struct nilfs_btree_node *node, int nchildren) |
195 | struct nilfs_btree_node *node, | ||
196 | int nchildren) | ||
197 | { | 182 | { |
198 | node->bn_nchildren = cpu_to_le16(nchildren); | 183 | node->bn_nchildren = cpu_to_le16(nchildren); |
199 | } | 184 | } |
200 | 185 | ||
201 | static inline int | 186 | static inline int nilfs_btree_node_size(const struct nilfs_btree *btree) |
202 | nilfs_btree_node_size(const struct nilfs_btree *btree) | ||
203 | { | 187 | { |
204 | return 1 << btree->bt_bmap.b_inode->i_blkbits; | 188 | return 1 << btree->bt_bmap.b_inode->i_blkbits; |
205 | } | 189 | } |
206 | 190 | ||
207 | static inline int | 191 | static inline int |
208 | nilfs_btree_node_nchildren_min(const struct nilfs_btree *btree, | 192 | nilfs_btree_node_nchildren_min(const struct nilfs_btree_node *node, |
209 | const struct nilfs_btree_node *node) | 193 | const struct nilfs_btree *btree) |
210 | { | 194 | { |
211 | return nilfs_btree_node_root(btree, node) ? | 195 | return nilfs_btree_node_root(node) ? |
212 | NILFS_BTREE_ROOT_NCHILDREN_MIN : | 196 | NILFS_BTREE_ROOT_NCHILDREN_MIN : |
213 | NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree)); | 197 | NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree)); |
214 | } | 198 | } |
215 | 199 | ||
216 | static inline int | 200 | static inline int |
217 | nilfs_btree_node_nchildren_max(const struct nilfs_btree *btree, | 201 | nilfs_btree_node_nchildren_max(const struct nilfs_btree_node *node, |
218 | const struct nilfs_btree_node *node) | 202 | const struct nilfs_btree *btree) |
219 | { | 203 | { |
220 | return nilfs_btree_node_root(btree, node) ? | 204 | return nilfs_btree_node_root(node) ? |
221 | NILFS_BTREE_ROOT_NCHILDREN_MAX : | 205 | NILFS_BTREE_ROOT_NCHILDREN_MAX : |
222 | NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(btree)); | 206 | NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(btree)); |
223 | } | 207 | } |
224 | 208 | ||
225 | static inline __le64 * | 209 | static inline __le64 * |
226 | nilfs_btree_node_dkeys(const struct nilfs_btree *btree, | 210 | nilfs_btree_node_dkeys(const struct nilfs_btree_node *node) |
227 | const struct nilfs_btree_node *node) | ||
228 | { | 211 | { |
229 | return (__le64 *)((char *)(node + 1) + | 212 | return (__le64 *)((char *)(node + 1) + |
230 | (nilfs_btree_node_root(btree, node) ? | 213 | (nilfs_btree_node_root(node) ? |
231 | 0 : NILFS_BTREE_NODE_EXTRA_PAD_SIZE)); | 214 | 0 : NILFS_BTREE_NODE_EXTRA_PAD_SIZE)); |
232 | } | 215 | } |
233 | 216 | ||
234 | static inline __le64 * | 217 | static inline __le64 * |
235 | nilfs_btree_node_dptrs(const struct nilfs_btree *btree, | 218 | nilfs_btree_node_dptrs(const struct nilfs_btree_node *node, |
236 | const struct nilfs_btree_node *node) | 219 | const struct nilfs_btree *btree) |
237 | { | 220 | { |
238 | return (__le64 *)(nilfs_btree_node_dkeys(btree, node) + | 221 | return (__le64 *)(nilfs_btree_node_dkeys(node) + |
239 | nilfs_btree_node_nchildren_max(btree, node)); | 222 | nilfs_btree_node_nchildren_max(node, btree)); |
240 | } | 223 | } |
241 | 224 | ||
242 | static inline __u64 | 225 | static inline __u64 |
243 | nilfs_btree_node_get_key(const struct nilfs_btree *btree, | 226 | nilfs_btree_node_get_key(const struct nilfs_btree_node *node, int index) |
244 | const struct nilfs_btree_node *node, int index) | ||
245 | { | 227 | { |
246 | return nilfs_bmap_dkey_to_key(*(nilfs_btree_node_dkeys(btree, node) + | 228 | return nilfs_bmap_dkey_to_key(*(nilfs_btree_node_dkeys(node) + index)); |
247 | index)); | ||
248 | } | 229 | } |
249 | 230 | ||
250 | static inline void | 231 | static inline void |
251 | nilfs_btree_node_set_key(struct nilfs_btree *btree, | 232 | nilfs_btree_node_set_key(struct nilfs_btree_node *node, int index, __u64 key) |
252 | struct nilfs_btree_node *node, int index, __u64 key) | ||
253 | { | 233 | { |
254 | *(nilfs_btree_node_dkeys(btree, node) + index) = | 234 | *(nilfs_btree_node_dkeys(node) + index) = nilfs_bmap_key_to_dkey(key); |
255 | nilfs_bmap_key_to_dkey(key); | ||
256 | } | 235 | } |
257 | 236 | ||
258 | static inline __u64 | 237 | static inline __u64 |
259 | nilfs_btree_node_get_ptr(const struct nilfs_btree *btree, | 238 | nilfs_btree_node_get_ptr(const struct nilfs_btree *btree, |
260 | const struct nilfs_btree_node *node, | 239 | const struct nilfs_btree_node *node, int index) |
261 | int index) | ||
262 | { | 240 | { |
263 | return nilfs_bmap_dptr_to_ptr(*(nilfs_btree_node_dptrs(btree, node) + | 241 | return nilfs_bmap_dptr_to_ptr(*(nilfs_btree_node_dptrs(node, btree) + |
264 | index)); | 242 | index)); |
265 | } | 243 | } |
266 | 244 | ||
267 | static inline void | 245 | static inline void |
268 | nilfs_btree_node_set_ptr(struct nilfs_btree *btree, | 246 | nilfs_btree_node_set_ptr(struct nilfs_btree *btree, |
269 | struct nilfs_btree_node *node, | 247 | struct nilfs_btree_node *node, int index, __u64 ptr) |
270 | int index, | ||
271 | __u64 ptr) | ||
272 | { | 248 | { |
273 | *(nilfs_btree_node_dptrs(btree, node) + index) = | 249 | *(nilfs_btree_node_dptrs(node, btree) + index) = |
274 | nilfs_bmap_ptr_to_dptr(ptr); | 250 | nilfs_bmap_ptr_to_dptr(ptr); |
275 | } | 251 | } |
276 | 252 | ||
@@ -283,12 +259,12 @@ static void nilfs_btree_node_init(struct nilfs_btree *btree, | |||
283 | __le64 *dptrs; | 259 | __le64 *dptrs; |
284 | int i; | 260 | int i; |
285 | 261 | ||
286 | nilfs_btree_node_set_flags(btree, node, flags); | 262 | nilfs_btree_node_set_flags(node, flags); |
287 | nilfs_btree_node_set_level(btree, node, level); | 263 | nilfs_btree_node_set_level(node, level); |
288 | nilfs_btree_node_set_nchildren(btree, node, nchildren); | 264 | nilfs_btree_node_set_nchildren(node, nchildren); |
289 | 265 | ||
290 | dkeys = nilfs_btree_node_dkeys(btree, node); | 266 | dkeys = nilfs_btree_node_dkeys(node); |
291 | dptrs = nilfs_btree_node_dptrs(btree, node); | 267 | dptrs = nilfs_btree_node_dptrs(node, btree); |
292 | for (i = 0; i < nchildren; i++) { | 268 | for (i = 0; i < nchildren; i++) { |
293 | dkeys[i] = nilfs_bmap_key_to_dkey(keys[i]); | 269 | dkeys[i] = nilfs_bmap_key_to_dkey(keys[i]); |
294 | dptrs[i] = nilfs_bmap_ptr_to_dptr(ptrs[i]); | 270 | dptrs[i] = nilfs_bmap_ptr_to_dptr(ptrs[i]); |
@@ -305,13 +281,13 @@ static void nilfs_btree_node_move_left(struct nilfs_btree *btree, | |||
305 | __le64 *ldptrs, *rdptrs; | 281 | __le64 *ldptrs, *rdptrs; |
306 | int lnchildren, rnchildren; | 282 | int lnchildren, rnchildren; |
307 | 283 | ||
308 | ldkeys = nilfs_btree_node_dkeys(btree, left); | 284 | ldkeys = nilfs_btree_node_dkeys(left); |
309 | ldptrs = nilfs_btree_node_dptrs(btree, left); | 285 | ldptrs = nilfs_btree_node_dptrs(left, btree); |
310 | lnchildren = nilfs_btree_node_get_nchildren(btree, left); | 286 | lnchildren = nilfs_btree_node_get_nchildren(left); |
311 | 287 | ||
312 | rdkeys = nilfs_btree_node_dkeys(btree, right); | 288 | rdkeys = nilfs_btree_node_dkeys(right); |
313 | rdptrs = nilfs_btree_node_dptrs(btree, right); | 289 | rdptrs = nilfs_btree_node_dptrs(right, btree); |
314 | rnchildren = nilfs_btree_node_get_nchildren(btree, right); | 290 | rnchildren = nilfs_btree_node_get_nchildren(right); |
315 | 291 | ||
316 | memcpy(ldkeys + lnchildren, rdkeys, n * sizeof(*rdkeys)); | 292 | memcpy(ldkeys + lnchildren, rdkeys, n * sizeof(*rdkeys)); |
317 | memcpy(ldptrs + lnchildren, rdptrs, n * sizeof(*rdptrs)); | 293 | memcpy(ldptrs + lnchildren, rdptrs, n * sizeof(*rdptrs)); |
@@ -320,8 +296,8 @@ static void nilfs_btree_node_move_left(struct nilfs_btree *btree, | |||
320 | 296 | ||
321 | lnchildren += n; | 297 | lnchildren += n; |
322 | rnchildren -= n; | 298 | rnchildren -= n; |
323 | nilfs_btree_node_set_nchildren(btree, left, lnchildren); | 299 | nilfs_btree_node_set_nchildren(left, lnchildren); |
324 | nilfs_btree_node_set_nchildren(btree, right, rnchildren); | 300 | nilfs_btree_node_set_nchildren(right, rnchildren); |
325 | } | 301 | } |
326 | 302 | ||
327 | /* Assume that the buffer heads corresponding to left and right are locked. */ | 303 | /* Assume that the buffer heads corresponding to left and right are locked. */ |
@@ -334,13 +310,13 @@ static void nilfs_btree_node_move_right(struct nilfs_btree *btree, | |||
334 | __le64 *ldptrs, *rdptrs; | 310 | __le64 *ldptrs, *rdptrs; |
335 | int lnchildren, rnchildren; | 311 | int lnchildren, rnchildren; |
336 | 312 | ||
337 | ldkeys = nilfs_btree_node_dkeys(btree, left); | 313 | ldkeys = nilfs_btree_node_dkeys(left); |
338 | ldptrs = nilfs_btree_node_dptrs(btree, left); | 314 | ldptrs = nilfs_btree_node_dptrs(left, btree); |
339 | lnchildren = nilfs_btree_node_get_nchildren(btree, left); | 315 | lnchildren = nilfs_btree_node_get_nchildren(left); |
340 | 316 | ||
341 | rdkeys = nilfs_btree_node_dkeys(btree, right); | 317 | rdkeys = nilfs_btree_node_dkeys(right); |
342 | rdptrs = nilfs_btree_node_dptrs(btree, right); | 318 | rdptrs = nilfs_btree_node_dptrs(right, btree); |
343 | rnchildren = nilfs_btree_node_get_nchildren(btree, right); | 319 | rnchildren = nilfs_btree_node_get_nchildren(right); |
344 | 320 | ||
345 | memmove(rdkeys + n, rdkeys, rnchildren * sizeof(*rdkeys)); | 321 | memmove(rdkeys + n, rdkeys, rnchildren * sizeof(*rdkeys)); |
346 | memmove(rdptrs + n, rdptrs, rnchildren * sizeof(*rdptrs)); | 322 | memmove(rdptrs + n, rdptrs, rnchildren * sizeof(*rdptrs)); |
@@ -349,8 +325,8 @@ static void nilfs_btree_node_move_right(struct nilfs_btree *btree, | |||
349 | 325 | ||
350 | lnchildren -= n; | 326 | lnchildren -= n; |
351 | rnchildren += n; | 327 | rnchildren += n; |
352 | nilfs_btree_node_set_nchildren(btree, left, lnchildren); | 328 | nilfs_btree_node_set_nchildren(left, lnchildren); |
353 | nilfs_btree_node_set_nchildren(btree, right, rnchildren); | 329 | nilfs_btree_node_set_nchildren(right, rnchildren); |
354 | } | 330 | } |
355 | 331 | ||
356 | /* Assume that the buffer head corresponding to node is locked. */ | 332 | /* Assume that the buffer head corresponding to node is locked. */ |
@@ -362,9 +338,9 @@ static void nilfs_btree_node_insert(struct nilfs_btree *btree, | |||
362 | __le64 *dptrs; | 338 | __le64 *dptrs; |
363 | int nchildren; | 339 | int nchildren; |
364 | 340 | ||
365 | dkeys = nilfs_btree_node_dkeys(btree, node); | 341 | dkeys = nilfs_btree_node_dkeys(node); |
366 | dptrs = nilfs_btree_node_dptrs(btree, node); | 342 | dptrs = nilfs_btree_node_dptrs(node, btree); |
367 | nchildren = nilfs_btree_node_get_nchildren(btree, node); | 343 | nchildren = nilfs_btree_node_get_nchildren(node); |
368 | if (index < nchildren) { | 344 | if (index < nchildren) { |
369 | memmove(dkeys + index + 1, dkeys + index, | 345 | memmove(dkeys + index + 1, dkeys + index, |
370 | (nchildren - index) * sizeof(*dkeys)); | 346 | (nchildren - index) * sizeof(*dkeys)); |
@@ -374,7 +350,7 @@ static void nilfs_btree_node_insert(struct nilfs_btree *btree, | |||
374 | dkeys[index] = nilfs_bmap_key_to_dkey(key); | 350 | dkeys[index] = nilfs_bmap_key_to_dkey(key); |
375 | dptrs[index] = nilfs_bmap_ptr_to_dptr(ptr); | 351 | dptrs[index] = nilfs_bmap_ptr_to_dptr(ptr); |
376 | nchildren++; | 352 | nchildren++; |
377 | nilfs_btree_node_set_nchildren(btree, node, nchildren); | 353 | nilfs_btree_node_set_nchildren(node, nchildren); |
378 | } | 354 | } |
379 | 355 | ||
380 | /* Assume that the buffer head corresponding to node is locked. */ | 356 | /* Assume that the buffer head corresponding to node is locked. */ |
@@ -388,11 +364,11 @@ static void nilfs_btree_node_delete(struct nilfs_btree *btree, | |||
388 | __le64 *dptrs; | 364 | __le64 *dptrs; |
389 | int nchildren; | 365 | int nchildren; |
390 | 366 | ||
391 | dkeys = nilfs_btree_node_dkeys(btree, node); | 367 | dkeys = nilfs_btree_node_dkeys(node); |
392 | dptrs = nilfs_btree_node_dptrs(btree, node); | 368 | dptrs = nilfs_btree_node_dptrs(node, btree); |
393 | key = nilfs_bmap_dkey_to_key(dkeys[index]); | 369 | key = nilfs_bmap_dkey_to_key(dkeys[index]); |
394 | ptr = nilfs_bmap_dptr_to_ptr(dptrs[index]); | 370 | ptr = nilfs_bmap_dptr_to_ptr(dptrs[index]); |
395 | nchildren = nilfs_btree_node_get_nchildren(btree, node); | 371 | nchildren = nilfs_btree_node_get_nchildren(node); |
396 | if (keyp != NULL) | 372 | if (keyp != NULL) |
397 | *keyp = key; | 373 | *keyp = key; |
398 | if (ptrp != NULL) | 374 | if (ptrp != NULL) |
@@ -405,11 +381,10 @@ static void nilfs_btree_node_delete(struct nilfs_btree *btree, | |||
405 | (nchildren - index - 1) * sizeof(*dptrs)); | 381 | (nchildren - index - 1) * sizeof(*dptrs)); |
406 | } | 382 | } |
407 | nchildren--; | 383 | nchildren--; |
408 | nilfs_btree_node_set_nchildren(btree, node, nchildren); | 384 | nilfs_btree_node_set_nchildren(node, nchildren); |
409 | } | 385 | } |
410 | 386 | ||
411 | static int nilfs_btree_node_lookup(const struct nilfs_btree *btree, | 387 | static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node, |
412 | const struct nilfs_btree_node *node, | ||
413 | __u64 key, int *indexp) | 388 | __u64 key, int *indexp) |
414 | { | 389 | { |
415 | __u64 nkey; | 390 | __u64 nkey; |
@@ -417,12 +392,12 @@ static int nilfs_btree_node_lookup(const struct nilfs_btree *btree, | |||
417 | 392 | ||
418 | /* binary search */ | 393 | /* binary search */ |
419 | low = 0; | 394 | low = 0; |
420 | high = nilfs_btree_node_get_nchildren(btree, node) - 1; | 395 | high = nilfs_btree_node_get_nchildren(node) - 1; |
421 | index = 0; | 396 | index = 0; |
422 | s = 0; | 397 | s = 0; |
423 | while (low <= high) { | 398 | while (low <= high) { |
424 | index = (low + high) / 2; | 399 | index = (low + high) / 2; |
425 | nkey = nilfs_btree_node_get_key(btree, node, index); | 400 | nkey = nilfs_btree_node_get_key(node, index); |
426 | if (nkey == key) { | 401 | if (nkey == key) { |
427 | s = 0; | 402 | s = 0; |
428 | goto out; | 403 | goto out; |
@@ -436,9 +411,8 @@ static int nilfs_btree_node_lookup(const struct nilfs_btree *btree, | |||
436 | } | 411 | } |
437 | 412 | ||
438 | /* adjust index */ | 413 | /* adjust index */ |
439 | if (nilfs_btree_node_get_level(btree, node) > | 414 | if (nilfs_btree_node_get_level(node) > NILFS_BTREE_LEVEL_NODE_MIN) { |
440 | NILFS_BTREE_LEVEL_NODE_MIN) { | 415 | if (s > 0 && index > 0) |
441 | if ((s > 0) && (index > 0)) | ||
442 | index--; | 416 | index--; |
443 | } else if (s < 0) | 417 | } else if (s < 0) |
444 | index++; | 418 | index++; |
@@ -456,25 +430,20 @@ nilfs_btree_get_root(const struct nilfs_btree *btree) | |||
456 | } | 430 | } |
457 | 431 | ||
458 | static inline struct nilfs_btree_node * | 432 | static inline struct nilfs_btree_node * |
459 | nilfs_btree_get_nonroot_node(const struct nilfs_btree *btree, | 433 | nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level) |
460 | const struct nilfs_btree_path *path, | ||
461 | int level) | ||
462 | { | 434 | { |
463 | return (struct nilfs_btree_node *)path[level].bp_bh->b_data; | 435 | return (struct nilfs_btree_node *)path[level].bp_bh->b_data; |
464 | } | 436 | } |
465 | 437 | ||
466 | static inline struct nilfs_btree_node * | 438 | static inline struct nilfs_btree_node * |
467 | nilfs_btree_get_sib_node(const struct nilfs_btree *btree, | 439 | nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level) |
468 | const struct nilfs_btree_path *path, | ||
469 | int level) | ||
470 | { | 440 | { |
471 | return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data; | 441 | return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data; |
472 | } | 442 | } |
473 | 443 | ||
474 | static inline int nilfs_btree_height(const struct nilfs_btree *btree) | 444 | static inline int nilfs_btree_height(const struct nilfs_btree *btree) |
475 | { | 445 | { |
476 | return nilfs_btree_node_get_level(btree, nilfs_btree_get_root(btree)) | 446 | return nilfs_btree_node_get_level(nilfs_btree_get_root(btree)) + 1; |
477 | + 1; | ||
478 | } | 447 | } |
479 | 448 | ||
480 | static inline struct nilfs_btree_node * | 449 | static inline struct nilfs_btree_node * |
@@ -484,7 +453,7 @@ nilfs_btree_get_node(const struct nilfs_btree *btree, | |||
484 | { | 453 | { |
485 | return (level == nilfs_btree_height(btree) - 1) ? | 454 | return (level == nilfs_btree_height(btree) - 1) ? |
486 | nilfs_btree_get_root(btree) : | 455 | nilfs_btree_get_root(btree) : |
487 | nilfs_btree_get_nonroot_node(btree, path, level); | 456 | nilfs_btree_get_nonroot_node(path, level); |
488 | } | 457 | } |
489 | 458 | ||
490 | static int nilfs_btree_do_lookup(const struct nilfs_btree *btree, | 459 | static int nilfs_btree_do_lookup(const struct nilfs_btree *btree, |
@@ -496,12 +465,11 @@ static int nilfs_btree_do_lookup(const struct nilfs_btree *btree, | |||
496 | int level, index, found, ret; | 465 | int level, index, found, ret; |
497 | 466 | ||
498 | node = nilfs_btree_get_root(btree); | 467 | node = nilfs_btree_get_root(btree); |
499 | level = nilfs_btree_node_get_level(btree, node); | 468 | level = nilfs_btree_node_get_level(node); |
500 | if ((level < minlevel) || | 469 | if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0) |
501 | (nilfs_btree_node_get_nchildren(btree, node) <= 0)) | ||
502 | return -ENOENT; | 470 | return -ENOENT; |
503 | 471 | ||
504 | found = nilfs_btree_node_lookup(btree, node, key, &index); | 472 | found = nilfs_btree_node_lookup(node, key, &index); |
505 | ptr = nilfs_btree_node_get_ptr(btree, node, index); | 473 | ptr = nilfs_btree_node_get_ptr(btree, node, index); |
506 | path[level].bp_bh = NULL; | 474 | path[level].bp_bh = NULL; |
507 | path[level].bp_index = index; | 475 | path[level].bp_index = index; |
@@ -510,14 +478,13 @@ static int nilfs_btree_do_lookup(const struct nilfs_btree *btree, | |||
510 | ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh); | 478 | ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh); |
511 | if (ret < 0) | 479 | if (ret < 0) |
512 | return ret; | 480 | return ret; |
513 | node = nilfs_btree_get_nonroot_node(btree, path, level); | 481 | node = nilfs_btree_get_nonroot_node(path, level); |
514 | BUG_ON(level != nilfs_btree_node_get_level(btree, node)); | 482 | BUG_ON(level != nilfs_btree_node_get_level(node)); |
515 | if (!found) | 483 | if (!found) |
516 | found = nilfs_btree_node_lookup(btree, node, key, | 484 | found = nilfs_btree_node_lookup(node, key, &index); |
517 | &index); | ||
518 | else | 485 | else |
519 | index = 0; | 486 | index = 0; |
520 | if (index < nilfs_btree_node_nchildren_max(btree, node)) | 487 | if (index < nilfs_btree_node_nchildren_max(node, btree)) |
521 | ptr = nilfs_btree_node_get_ptr(btree, node, index); | 488 | ptr = nilfs_btree_node_get_ptr(btree, node, index); |
522 | else { | 489 | else { |
523 | WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN); | 490 | WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN); |
@@ -544,10 +511,10 @@ static int nilfs_btree_do_lookup_last(const struct nilfs_btree *btree, | |||
544 | int index, level, ret; | 511 | int index, level, ret; |
545 | 512 | ||
546 | node = nilfs_btree_get_root(btree); | 513 | node = nilfs_btree_get_root(btree); |
547 | index = nilfs_btree_node_get_nchildren(btree, node) - 1; | 514 | index = nilfs_btree_node_get_nchildren(node) - 1; |
548 | if (index < 0) | 515 | if (index < 0) |
549 | return -ENOENT; | 516 | return -ENOENT; |
550 | level = nilfs_btree_node_get_level(btree, node); | 517 | level = nilfs_btree_node_get_level(node); |
551 | ptr = nilfs_btree_node_get_ptr(btree, node, index); | 518 | ptr = nilfs_btree_node_get_ptr(btree, node, index); |
552 | path[level].bp_bh = NULL; | 519 | path[level].bp_bh = NULL; |
553 | path[level].bp_index = index; | 520 | path[level].bp_index = index; |
@@ -556,15 +523,15 @@ static int nilfs_btree_do_lookup_last(const struct nilfs_btree *btree, | |||
556 | ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh); | 523 | ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh); |
557 | if (ret < 0) | 524 | if (ret < 0) |
558 | return ret; | 525 | return ret; |
559 | node = nilfs_btree_get_nonroot_node(btree, path, level); | 526 | node = nilfs_btree_get_nonroot_node(path, level); |
560 | BUG_ON(level != nilfs_btree_node_get_level(btree, node)); | 527 | BUG_ON(level != nilfs_btree_node_get_level(node)); |
561 | index = nilfs_btree_node_get_nchildren(btree, node) - 1; | 528 | index = nilfs_btree_node_get_nchildren(node) - 1; |
562 | ptr = nilfs_btree_node_get_ptr(btree, node, index); | 529 | ptr = nilfs_btree_node_get_ptr(btree, node, index); |
563 | path[level].bp_index = index; | 530 | path[level].bp_index = index; |
564 | } | 531 | } |
565 | 532 | ||
566 | if (keyp != NULL) | 533 | if (keyp != NULL) |
567 | *keyp = nilfs_btree_node_get_key(btree, node, index); | 534 | *keyp = nilfs_btree_node_get_key(node, index); |
568 | if (ptrp != NULL) | 535 | if (ptrp != NULL) |
569 | *ptrp = ptr; | 536 | *ptrp = ptr; |
570 | 537 | ||
@@ -580,18 +547,18 @@ static int nilfs_btree_lookup(const struct nilfs_bmap *bmap, | |||
580 | int ret; | 547 | int ret; |
581 | 548 | ||
582 | btree = (struct nilfs_btree *)bmap; | 549 | btree = (struct nilfs_btree *)bmap; |
583 | path = nilfs_btree_alloc_path(btree); | 550 | path = nilfs_btree_alloc_path(); |
584 | if (path == NULL) | 551 | if (path == NULL) |
585 | return -ENOMEM; | 552 | return -ENOMEM; |
586 | nilfs_btree_init_path(btree, path); | 553 | nilfs_btree_init_path(path); |
587 | 554 | ||
588 | ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level); | 555 | ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level); |
589 | 556 | ||
590 | if (ptrp != NULL) | 557 | if (ptrp != NULL) |
591 | *ptrp = ptr; | 558 | *ptrp = ptr; |
592 | 559 | ||
593 | nilfs_btree_clear_path(btree, path); | 560 | nilfs_btree_clear_path(path); |
594 | nilfs_btree_free_path(btree, path); | 561 | nilfs_btree_free_path(path); |
595 | 562 | ||
596 | return ret; | 563 | return ret; |
597 | } | 564 | } |
@@ -608,10 +575,10 @@ static int nilfs_btree_lookup_contig(const struct nilfs_bmap *bmap, | |||
608 | int level = NILFS_BTREE_LEVEL_NODE_MIN; | 575 | int level = NILFS_BTREE_LEVEL_NODE_MIN; |
609 | int ret, cnt, index, maxlevel; | 576 | int ret, cnt, index, maxlevel; |
610 | 577 | ||
611 | path = nilfs_btree_alloc_path(btree); | 578 | path = nilfs_btree_alloc_path(); |
612 | if (path == NULL) | 579 | if (path == NULL) |
613 | return -ENOMEM; | 580 | return -ENOMEM; |
614 | nilfs_btree_init_path(btree, path); | 581 | nilfs_btree_init_path(path); |
615 | ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level); | 582 | ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level); |
616 | if (ret < 0) | 583 | if (ret < 0) |
617 | goto out; | 584 | goto out; |
@@ -631,8 +598,8 @@ static int nilfs_btree_lookup_contig(const struct nilfs_bmap *bmap, | |||
631 | node = nilfs_btree_get_node(btree, path, level); | 598 | node = nilfs_btree_get_node(btree, path, level); |
632 | index = path[level].bp_index + 1; | 599 | index = path[level].bp_index + 1; |
633 | for (;;) { | 600 | for (;;) { |
634 | while (index < nilfs_btree_node_get_nchildren(btree, node)) { | 601 | while (index < nilfs_btree_node_get_nchildren(node)) { |
635 | if (nilfs_btree_node_get_key(btree, node, index) != | 602 | if (nilfs_btree_node_get_key(node, index) != |
636 | key + cnt) | 603 | key + cnt) |
637 | goto end; | 604 | goto end; |
638 | ptr2 = nilfs_btree_node_get_ptr(btree, node, index); | 605 | ptr2 = nilfs_btree_node_get_ptr(btree, node, index); |
@@ -653,8 +620,8 @@ static int nilfs_btree_lookup_contig(const struct nilfs_bmap *bmap, | |||
653 | /* look-up right sibling node */ | 620 | /* look-up right sibling node */ |
654 | node = nilfs_btree_get_node(btree, path, level + 1); | 621 | node = nilfs_btree_get_node(btree, path, level + 1); |
655 | index = path[level + 1].bp_index + 1; | 622 | index = path[level + 1].bp_index + 1; |
656 | if (index >= nilfs_btree_node_get_nchildren(btree, node) || | 623 | if (index >= nilfs_btree_node_get_nchildren(node) || |
657 | nilfs_btree_node_get_key(btree, node, index) != key + cnt) | 624 | nilfs_btree_node_get_key(node, index) != key + cnt) |
658 | break; | 625 | break; |
659 | ptr2 = nilfs_btree_node_get_ptr(btree, node, index); | 626 | ptr2 = nilfs_btree_node_get_ptr(btree, node, index); |
660 | path[level + 1].bp_index = index; | 627 | path[level + 1].bp_index = index; |
@@ -664,7 +631,7 @@ static int nilfs_btree_lookup_contig(const struct nilfs_bmap *bmap, | |||
664 | ret = nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh); | 631 | ret = nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh); |
665 | if (ret < 0) | 632 | if (ret < 0) |
666 | goto out; | 633 | goto out; |
667 | node = nilfs_btree_get_nonroot_node(btree, path, level); | 634 | node = nilfs_btree_get_nonroot_node(path, level); |
668 | index = 0; | 635 | index = 0; |
669 | path[level].bp_index = index; | 636 | path[level].bp_index = index; |
670 | } | 637 | } |
@@ -672,8 +639,8 @@ static int nilfs_btree_lookup_contig(const struct nilfs_bmap *bmap, | |||
672 | *ptrp = ptr; | 639 | *ptrp = ptr; |
673 | ret = cnt; | 640 | ret = cnt; |
674 | out: | 641 | out: |
675 | nilfs_btree_clear_path(btree, path); | 642 | nilfs_btree_clear_path(path); |
676 | nilfs_btree_free_path(btree, path); | 643 | nilfs_btree_free_path(path); |
677 | return ret; | 644 | return ret; |
678 | } | 645 | } |
679 | 646 | ||
@@ -685,9 +652,7 @@ static void nilfs_btree_promote_key(struct nilfs_btree *btree, | |||
685 | do { | 652 | do { |
686 | lock_buffer(path[level].bp_bh); | 653 | lock_buffer(path[level].bp_bh); |
687 | nilfs_btree_node_set_key( | 654 | nilfs_btree_node_set_key( |
688 | btree, | 655 | nilfs_btree_get_nonroot_node(path, level), |
689 | nilfs_btree_get_nonroot_node( | ||
690 | btree, path, level), | ||
691 | path[level].bp_index, key); | 656 | path[level].bp_index, key); |
692 | if (!buffer_dirty(path[level].bp_bh)) | 657 | if (!buffer_dirty(path[level].bp_bh)) |
693 | nilfs_btnode_mark_dirty(path[level].bp_bh); | 658 | nilfs_btnode_mark_dirty(path[level].bp_bh); |
@@ -698,8 +663,7 @@ static void nilfs_btree_promote_key(struct nilfs_btree *btree, | |||
698 | 663 | ||
699 | /* root */ | 664 | /* root */ |
700 | if (level == nilfs_btree_height(btree) - 1) { | 665 | if (level == nilfs_btree_height(btree) - 1) { |
701 | nilfs_btree_node_set_key(btree, | 666 | nilfs_btree_node_set_key(nilfs_btree_get_root(btree), |
702 | nilfs_btree_get_root(btree), | ||
703 | path[level].bp_index, key); | 667 | path[level].bp_index, key); |
704 | } | 668 | } |
705 | } | 669 | } |
@@ -712,7 +676,7 @@ static void nilfs_btree_do_insert(struct nilfs_btree *btree, | |||
712 | 676 | ||
713 | if (level < nilfs_btree_height(btree) - 1) { | 677 | if (level < nilfs_btree_height(btree) - 1) { |
714 | lock_buffer(path[level].bp_bh); | 678 | lock_buffer(path[level].bp_bh); |
715 | node = nilfs_btree_get_nonroot_node(btree, path, level); | 679 | node = nilfs_btree_get_nonroot_node(path, level); |
716 | nilfs_btree_node_insert(btree, node, *keyp, *ptrp, | 680 | nilfs_btree_node_insert(btree, node, *keyp, *ptrp, |
717 | path[level].bp_index); | 681 | path[level].bp_index); |
718 | if (!buffer_dirty(path[level].bp_bh)) | 682 | if (!buffer_dirty(path[level].bp_bh)) |
@@ -721,8 +685,8 @@ static void nilfs_btree_do_insert(struct nilfs_btree *btree, | |||
721 | 685 | ||
722 | if (path[level].bp_index == 0) | 686 | if (path[level].bp_index == 0) |
723 | nilfs_btree_promote_key(btree, path, level + 1, | 687 | nilfs_btree_promote_key(btree, path, level + 1, |
724 | nilfs_btree_node_get_key( | 688 | nilfs_btree_node_get_key(node, |
725 | btree, node, 0)); | 689 | 0)); |
726 | } else { | 690 | } else { |
727 | node = nilfs_btree_get_root(btree); | 691 | node = nilfs_btree_get_root(btree); |
728 | nilfs_btree_node_insert(btree, node, *keyp, *ptrp, | 692 | nilfs_btree_node_insert(btree, node, *keyp, *ptrp, |
@@ -740,10 +704,10 @@ static void nilfs_btree_carry_left(struct nilfs_btree *btree, | |||
740 | lock_buffer(path[level].bp_bh); | 704 | lock_buffer(path[level].bp_bh); |
741 | lock_buffer(path[level].bp_sib_bh); | 705 | lock_buffer(path[level].bp_sib_bh); |
742 | 706 | ||
743 | node = nilfs_btree_get_nonroot_node(btree, path, level); | 707 | node = nilfs_btree_get_nonroot_node(path, level); |
744 | left = nilfs_btree_get_sib_node(btree, path, level); | 708 | left = nilfs_btree_get_sib_node(path, level); |
745 | nchildren = nilfs_btree_node_get_nchildren(btree, node); | 709 | nchildren = nilfs_btree_node_get_nchildren(node); |
746 | lnchildren = nilfs_btree_node_get_nchildren(btree, left); | 710 | lnchildren = nilfs_btree_node_get_nchildren(left); |
747 | move = 0; | 711 | move = 0; |
748 | 712 | ||
749 | n = (nchildren + lnchildren + 1) / 2 - lnchildren; | 713 | n = (nchildren + lnchildren + 1) / 2 - lnchildren; |
@@ -764,7 +728,7 @@ static void nilfs_btree_carry_left(struct nilfs_btree *btree, | |||
764 | unlock_buffer(path[level].bp_sib_bh); | 728 | unlock_buffer(path[level].bp_sib_bh); |
765 | 729 | ||
766 | nilfs_btree_promote_key(btree, path, level + 1, | 730 | nilfs_btree_promote_key(btree, path, level + 1, |
767 | nilfs_btree_node_get_key(btree, node, 0)); | 731 | nilfs_btree_node_get_key(node, 0)); |
768 | 732 | ||
769 | if (move) { | 733 | if (move) { |
770 | brelse(path[level].bp_bh); | 734 | brelse(path[level].bp_bh); |
@@ -791,10 +755,10 @@ static void nilfs_btree_carry_right(struct nilfs_btree *btree, | |||
791 | lock_buffer(path[level].bp_bh); | 755 | lock_buffer(path[level].bp_bh); |
792 | lock_buffer(path[level].bp_sib_bh); | 756 | lock_buffer(path[level].bp_sib_bh); |
793 | 757 | ||
794 | node = nilfs_btree_get_nonroot_node(btree, path, level); | 758 | node = nilfs_btree_get_nonroot_node(path, level); |
795 | right = nilfs_btree_get_sib_node(btree, path, level); | 759 | right = nilfs_btree_get_sib_node(path, level); |
796 | nchildren = nilfs_btree_node_get_nchildren(btree, node); | 760 | nchildren = nilfs_btree_node_get_nchildren(node); |
797 | rnchildren = nilfs_btree_node_get_nchildren(btree, right); | 761 | rnchildren = nilfs_btree_node_get_nchildren(right); |
798 | move = 0; | 762 | move = 0; |
799 | 763 | ||
800 | n = (nchildren + rnchildren + 1) / 2 - rnchildren; | 764 | n = (nchildren + rnchildren + 1) / 2 - rnchildren; |
@@ -816,15 +780,14 @@ static void nilfs_btree_carry_right(struct nilfs_btree *btree, | |||
816 | 780 | ||
817 | path[level + 1].bp_index++; | 781 | path[level + 1].bp_index++; |
818 | nilfs_btree_promote_key(btree, path, level + 1, | 782 | nilfs_btree_promote_key(btree, path, level + 1, |
819 | nilfs_btree_node_get_key(btree, right, 0)); | 783 | nilfs_btree_node_get_key(right, 0)); |
820 | path[level + 1].bp_index--; | 784 | path[level + 1].bp_index--; |
821 | 785 | ||
822 | if (move) { | 786 | if (move) { |
823 | brelse(path[level].bp_bh); | 787 | brelse(path[level].bp_bh); |
824 | path[level].bp_bh = path[level].bp_sib_bh; | 788 | path[level].bp_bh = path[level].bp_sib_bh; |
825 | path[level].bp_sib_bh = NULL; | 789 | path[level].bp_sib_bh = NULL; |
826 | path[level].bp_index -= | 790 | path[level].bp_index -= nilfs_btree_node_get_nchildren(node); |
827 | nilfs_btree_node_get_nchildren(btree, node); | ||
828 | path[level + 1].bp_index++; | 791 | path[level + 1].bp_index++; |
829 | } else { | 792 | } else { |
830 | brelse(path[level].bp_sib_bh); | 793 | brelse(path[level].bp_sib_bh); |
@@ -846,9 +809,9 @@ static void nilfs_btree_split(struct nilfs_btree *btree, | |||
846 | lock_buffer(path[level].bp_bh); | 809 | lock_buffer(path[level].bp_bh); |
847 | lock_buffer(path[level].bp_sib_bh); | 810 | lock_buffer(path[level].bp_sib_bh); |
848 | 811 | ||
849 | node = nilfs_btree_get_nonroot_node(btree, path, level); | 812 | node = nilfs_btree_get_nonroot_node(path, level); |
850 | right = nilfs_btree_get_sib_node(btree, path, level); | 813 | right = nilfs_btree_get_sib_node(path, level); |
851 | nchildren = nilfs_btree_node_get_nchildren(btree, node); | 814 | nchildren = nilfs_btree_node_get_nchildren(node); |
852 | move = 0; | 815 | move = 0; |
853 | 816 | ||
854 | n = (nchildren + 1) / 2; | 817 | n = (nchildren + 1) / 2; |
@@ -867,16 +830,15 @@ static void nilfs_btree_split(struct nilfs_btree *btree, | |||
867 | unlock_buffer(path[level].bp_bh); | 830 | unlock_buffer(path[level].bp_bh); |
868 | unlock_buffer(path[level].bp_sib_bh); | 831 | unlock_buffer(path[level].bp_sib_bh); |
869 | 832 | ||
870 | newkey = nilfs_btree_node_get_key(btree, right, 0); | 833 | newkey = nilfs_btree_node_get_key(right, 0); |
871 | newptr = path[level].bp_newreq.bpr_ptr; | 834 | newptr = path[level].bp_newreq.bpr_ptr; |
872 | 835 | ||
873 | if (move) { | 836 | if (move) { |
874 | path[level].bp_index -= | 837 | path[level].bp_index -= nilfs_btree_node_get_nchildren(node); |
875 | nilfs_btree_node_get_nchildren(btree, node); | ||
876 | nilfs_btree_node_insert(btree, right, *keyp, *ptrp, | 838 | nilfs_btree_node_insert(btree, right, *keyp, *ptrp, |
877 | path[level].bp_index); | 839 | path[level].bp_index); |
878 | 840 | ||
879 | *keyp = nilfs_btree_node_get_key(btree, right, 0); | 841 | *keyp = nilfs_btree_node_get_key(right, 0); |
880 | *ptrp = path[level].bp_newreq.bpr_ptr; | 842 | *ptrp = path[level].bp_newreq.bpr_ptr; |
881 | 843 | ||
882 | brelse(path[level].bp_bh); | 844 | brelse(path[level].bp_bh); |
@@ -885,7 +847,7 @@ static void nilfs_btree_split(struct nilfs_btree *btree, | |||
885 | } else { | 847 | } else { |
886 | nilfs_btree_do_insert(btree, path, level, keyp, ptrp); | 848 | nilfs_btree_do_insert(btree, path, level, keyp, ptrp); |
887 | 849 | ||
888 | *keyp = nilfs_btree_node_get_key(btree, right, 0); | 850 | *keyp = nilfs_btree_node_get_key(right, 0); |
889 | *ptrp = path[level].bp_newreq.bpr_ptr; | 851 | *ptrp = path[level].bp_newreq.bpr_ptr; |
890 | 852 | ||
891 | brelse(path[level].bp_sib_bh); | 853 | brelse(path[level].bp_sib_bh); |
@@ -905,12 +867,12 @@ static void nilfs_btree_grow(struct nilfs_btree *btree, | |||
905 | lock_buffer(path[level].bp_sib_bh); | 867 | lock_buffer(path[level].bp_sib_bh); |
906 | 868 | ||
907 | root = nilfs_btree_get_root(btree); | 869 | root = nilfs_btree_get_root(btree); |
908 | child = nilfs_btree_get_sib_node(btree, path, level); | 870 | child = nilfs_btree_get_sib_node(path, level); |
909 | 871 | ||
910 | n = nilfs_btree_node_get_nchildren(btree, root); | 872 | n = nilfs_btree_node_get_nchildren(root); |
911 | 873 | ||
912 | nilfs_btree_node_move_right(btree, root, child, n); | 874 | nilfs_btree_node_move_right(btree, root, child, n); |
913 | nilfs_btree_node_set_level(btree, root, level + 1); | 875 | nilfs_btree_node_set_level(root, level + 1); |
914 | 876 | ||
915 | if (!buffer_dirty(path[level].bp_sib_bh)) | 877 | if (!buffer_dirty(path[level].bp_sib_bh)) |
916 | nilfs_btnode_mark_dirty(path[level].bp_sib_bh); | 878 | nilfs_btnode_mark_dirty(path[level].bp_sib_bh); |
@@ -922,7 +884,7 @@ static void nilfs_btree_grow(struct nilfs_btree *btree, | |||
922 | 884 | ||
923 | nilfs_btree_do_insert(btree, path, level, keyp, ptrp); | 885 | nilfs_btree_do_insert(btree, path, level, keyp, ptrp); |
924 | 886 | ||
925 | *keyp = nilfs_btree_node_get_key(btree, child, 0); | 887 | *keyp = nilfs_btree_node_get_key(child, 0); |
926 | *ptrp = path[level].bp_newreq.bpr_ptr; | 888 | *ptrp = path[level].bp_newreq.bpr_ptr; |
927 | } | 889 | } |
928 | 890 | ||
@@ -1007,9 +969,9 @@ static int nilfs_btree_prepare_insert(struct nilfs_btree *btree, | |||
1007 | for (level = NILFS_BTREE_LEVEL_NODE_MIN; | 969 | for (level = NILFS_BTREE_LEVEL_NODE_MIN; |
1008 | level < nilfs_btree_height(btree) - 1; | 970 | level < nilfs_btree_height(btree) - 1; |
1009 | level++) { | 971 | level++) { |
1010 | node = nilfs_btree_get_nonroot_node(btree, path, level); | 972 | node = nilfs_btree_get_nonroot_node(path, level); |
1011 | if (nilfs_btree_node_get_nchildren(btree, node) < | 973 | if (nilfs_btree_node_get_nchildren(node) < |
1012 | nilfs_btree_node_nchildren_max(btree, node)) { | 974 | nilfs_btree_node_nchildren_max(node, btree)) { |
1013 | path[level].bp_op = nilfs_btree_do_insert; | 975 | path[level].bp_op = nilfs_btree_do_insert; |
1014 | stats->bs_nblocks++; | 976 | stats->bs_nblocks++; |
1015 | goto out; | 977 | goto out; |
@@ -1026,8 +988,8 @@ static int nilfs_btree_prepare_insert(struct nilfs_btree *btree, | |||
1026 | if (ret < 0) | 988 | if (ret < 0) |
1027 | goto err_out_child_node; | 989 | goto err_out_child_node; |
1028 | sib = (struct nilfs_btree_node *)bh->b_data; | 990 | sib = (struct nilfs_btree_node *)bh->b_data; |
1029 | if (nilfs_btree_node_get_nchildren(btree, sib) < | 991 | if (nilfs_btree_node_get_nchildren(sib) < |
1030 | nilfs_btree_node_nchildren_max(btree, sib)) { | 992 | nilfs_btree_node_nchildren_max(sib, btree)) { |
1031 | path[level].bp_sib_bh = bh; | 993 | path[level].bp_sib_bh = bh; |
1032 | path[level].bp_op = nilfs_btree_carry_left; | 994 | path[level].bp_op = nilfs_btree_carry_left; |
1033 | stats->bs_nblocks++; | 995 | stats->bs_nblocks++; |
@@ -1038,15 +1000,15 @@ static int nilfs_btree_prepare_insert(struct nilfs_btree *btree, | |||
1038 | 1000 | ||
1039 | /* right sibling */ | 1001 | /* right sibling */ |
1040 | if (pindex < | 1002 | if (pindex < |
1041 | nilfs_btree_node_get_nchildren(btree, parent) - 1) { | 1003 | nilfs_btree_node_get_nchildren(parent) - 1) { |
1042 | sibptr = nilfs_btree_node_get_ptr(btree, parent, | 1004 | sibptr = nilfs_btree_node_get_ptr(btree, parent, |
1043 | pindex + 1); | 1005 | pindex + 1); |
1044 | ret = nilfs_btree_get_block(btree, sibptr, &bh); | 1006 | ret = nilfs_btree_get_block(btree, sibptr, &bh); |
1045 | if (ret < 0) | 1007 | if (ret < 0) |
1046 | goto err_out_child_node; | 1008 | goto err_out_child_node; |
1047 | sib = (struct nilfs_btree_node *)bh->b_data; | 1009 | sib = (struct nilfs_btree_node *)bh->b_data; |
1048 | if (nilfs_btree_node_get_nchildren(btree, sib) < | 1010 | if (nilfs_btree_node_get_nchildren(sib) < |
1049 | nilfs_btree_node_nchildren_max(btree, sib)) { | 1011 | nilfs_btree_node_nchildren_max(sib, btree)) { |
1050 | path[level].bp_sib_bh = bh; | 1012 | path[level].bp_sib_bh = bh; |
1051 | path[level].bp_op = nilfs_btree_carry_right; | 1013 | path[level].bp_op = nilfs_btree_carry_right; |
1052 | stats->bs_nblocks++; | 1014 | stats->bs_nblocks++; |
@@ -1081,8 +1043,8 @@ static int nilfs_btree_prepare_insert(struct nilfs_btree *btree, | |||
1081 | 1043 | ||
1082 | /* root */ | 1044 | /* root */ |
1083 | node = nilfs_btree_get_root(btree); | 1045 | node = nilfs_btree_get_root(btree); |
1084 | if (nilfs_btree_node_get_nchildren(btree, node) < | 1046 | if (nilfs_btree_node_get_nchildren(node) < |
1085 | nilfs_btree_node_nchildren_max(btree, node)) { | 1047 | nilfs_btree_node_nchildren_max(node, btree)) { |
1086 | path[level].bp_op = nilfs_btree_do_insert; | 1048 | path[level].bp_op = nilfs_btree_do_insert; |
1087 | stats->bs_nblocks++; | 1049 | stats->bs_nblocks++; |
1088 | goto out; | 1050 | goto out; |
@@ -1164,10 +1126,10 @@ static int nilfs_btree_insert(struct nilfs_bmap *bmap, __u64 key, __u64 ptr) | |||
1164 | int level, ret; | 1126 | int level, ret; |
1165 | 1127 | ||
1166 | btree = (struct nilfs_btree *)bmap; | 1128 | btree = (struct nilfs_btree *)bmap; |
1167 | path = nilfs_btree_alloc_path(btree); | 1129 | path = nilfs_btree_alloc_path(); |
1168 | if (path == NULL) | 1130 | if (path == NULL) |
1169 | return -ENOMEM; | 1131 | return -ENOMEM; |
1170 | nilfs_btree_init_path(btree, path); | 1132 | nilfs_btree_init_path(path); |
1171 | 1133 | ||
1172 | ret = nilfs_btree_do_lookup(btree, path, key, NULL, | 1134 | ret = nilfs_btree_do_lookup(btree, path, key, NULL, |
1173 | NILFS_BTREE_LEVEL_NODE_MIN); | 1135 | NILFS_BTREE_LEVEL_NODE_MIN); |
@@ -1184,8 +1146,8 @@ static int nilfs_btree_insert(struct nilfs_bmap *bmap, __u64 key, __u64 ptr) | |||
1184 | nilfs_bmap_add_blocks(bmap, stats.bs_nblocks); | 1146 | nilfs_bmap_add_blocks(bmap, stats.bs_nblocks); |
1185 | 1147 | ||
1186 | out: | 1148 | out: |
1187 | nilfs_btree_clear_path(btree, path); | 1149 | nilfs_btree_clear_path(path); |
1188 | nilfs_btree_free_path(btree, path); | 1150 | nilfs_btree_free_path(path); |
1189 | return ret; | 1151 | return ret; |
1190 | } | 1152 | } |
1191 | 1153 | ||
@@ -1197,7 +1159,7 @@ static void nilfs_btree_do_delete(struct nilfs_btree *btree, | |||
1197 | 1159 | ||
1198 | if (level < nilfs_btree_height(btree) - 1) { | 1160 | if (level < nilfs_btree_height(btree) - 1) { |
1199 | lock_buffer(path[level].bp_bh); | 1161 | lock_buffer(path[level].bp_bh); |
1200 | node = nilfs_btree_get_nonroot_node(btree, path, level); | 1162 | node = nilfs_btree_get_nonroot_node(path, level); |
1201 | nilfs_btree_node_delete(btree, node, keyp, ptrp, | 1163 | nilfs_btree_node_delete(btree, node, keyp, ptrp, |
1202 | path[level].bp_index); | 1164 | path[level].bp_index); |
1203 | if (!buffer_dirty(path[level].bp_bh)) | 1165 | if (!buffer_dirty(path[level].bp_bh)) |
@@ -1205,7 +1167,7 @@ static void nilfs_btree_do_delete(struct nilfs_btree *btree, | |||
1205 | unlock_buffer(path[level].bp_bh); | 1167 | unlock_buffer(path[level].bp_bh); |
1206 | if (path[level].bp_index == 0) | 1168 | if (path[level].bp_index == 0) |
1207 | nilfs_btree_promote_key(btree, path, level + 1, | 1169 | nilfs_btree_promote_key(btree, path, level + 1, |
1208 | nilfs_btree_node_get_key(btree, node, 0)); | 1170 | nilfs_btree_node_get_key(node, 0)); |
1209 | } else { | 1171 | } else { |
1210 | node = nilfs_btree_get_root(btree); | 1172 | node = nilfs_btree_get_root(btree); |
1211 | nilfs_btree_node_delete(btree, node, keyp, ptrp, | 1173 | nilfs_btree_node_delete(btree, node, keyp, ptrp, |
@@ -1225,10 +1187,10 @@ static void nilfs_btree_borrow_left(struct nilfs_btree *btree, | |||
1225 | lock_buffer(path[level].bp_bh); | 1187 | lock_buffer(path[level].bp_bh); |
1226 | lock_buffer(path[level].bp_sib_bh); | 1188 | lock_buffer(path[level].bp_sib_bh); |
1227 | 1189 | ||
1228 | node = nilfs_btree_get_nonroot_node(btree, path, level); | 1190 | node = nilfs_btree_get_nonroot_node(path, level); |
1229 | left = nilfs_btree_get_sib_node(btree, path, level); | 1191 | left = nilfs_btree_get_sib_node(path, level); |
1230 | nchildren = nilfs_btree_node_get_nchildren(btree, node); | 1192 | nchildren = nilfs_btree_node_get_nchildren(node); |
1231 | lnchildren = nilfs_btree_node_get_nchildren(btree, left); | 1193 | lnchildren = nilfs_btree_node_get_nchildren(left); |
1232 | 1194 | ||
1233 | n = (nchildren + lnchildren) / 2 - nchildren; | 1195 | n = (nchildren + lnchildren) / 2 - nchildren; |
1234 | 1196 | ||
@@ -1243,7 +1205,7 @@ static void nilfs_btree_borrow_left(struct nilfs_btree *btree, | |||
1243 | unlock_buffer(path[level].bp_sib_bh); | 1205 | unlock_buffer(path[level].bp_sib_bh); |
1244 | 1206 | ||
1245 | nilfs_btree_promote_key(btree, path, level + 1, | 1207 | nilfs_btree_promote_key(btree, path, level + 1, |
1246 | nilfs_btree_node_get_key(btree, node, 0)); | 1208 | nilfs_btree_node_get_key(node, 0)); |
1247 | 1209 | ||
1248 | brelse(path[level].bp_sib_bh); | 1210 | brelse(path[level].bp_sib_bh); |
1249 | path[level].bp_sib_bh = NULL; | 1211 | path[level].bp_sib_bh = NULL; |
@@ -1262,10 +1224,10 @@ static void nilfs_btree_borrow_right(struct nilfs_btree *btree, | |||
1262 | lock_buffer(path[level].bp_bh); | 1224 | lock_buffer(path[level].bp_bh); |
1263 | lock_buffer(path[level].bp_sib_bh); | 1225 | lock_buffer(path[level].bp_sib_bh); |
1264 | 1226 | ||
1265 | node = nilfs_btree_get_nonroot_node(btree, path, level); | 1227 | node = nilfs_btree_get_nonroot_node(path, level); |
1266 | right = nilfs_btree_get_sib_node(btree, path, level); | 1228 | right = nilfs_btree_get_sib_node(path, level); |
1267 | nchildren = nilfs_btree_node_get_nchildren(btree, node); | 1229 | nchildren = nilfs_btree_node_get_nchildren(node); |
1268 | rnchildren = nilfs_btree_node_get_nchildren(btree, right); | 1230 | rnchildren = nilfs_btree_node_get_nchildren(right); |
1269 | 1231 | ||
1270 | n = (nchildren + rnchildren) / 2 - nchildren; | 1232 | n = (nchildren + rnchildren) / 2 - nchildren; |
1271 | 1233 | ||
@@ -1281,7 +1243,7 @@ static void nilfs_btree_borrow_right(struct nilfs_btree *btree, | |||
1281 | 1243 | ||
1282 | path[level + 1].bp_index++; | 1244 | path[level + 1].bp_index++; |
1283 | nilfs_btree_promote_key(btree, path, level + 1, | 1245 | nilfs_btree_promote_key(btree, path, level + 1, |
1284 | nilfs_btree_node_get_key(btree, right, 0)); | 1246 | nilfs_btree_node_get_key(right, 0)); |
1285 | path[level + 1].bp_index--; | 1247 | path[level + 1].bp_index--; |
1286 | 1248 | ||
1287 | brelse(path[level].bp_sib_bh); | 1249 | brelse(path[level].bp_sib_bh); |
@@ -1300,10 +1262,10 @@ static void nilfs_btree_concat_left(struct nilfs_btree *btree, | |||
1300 | lock_buffer(path[level].bp_bh); | 1262 | lock_buffer(path[level].bp_bh); |
1301 | lock_buffer(path[level].bp_sib_bh); | 1263 | lock_buffer(path[level].bp_sib_bh); |
1302 | 1264 | ||
1303 | node = nilfs_btree_get_nonroot_node(btree, path, level); | 1265 | node = nilfs_btree_get_nonroot_node(path, level); |
1304 | left = nilfs_btree_get_sib_node(btree, path, level); | 1266 | left = nilfs_btree_get_sib_node(path, level); |
1305 | 1267 | ||
1306 | n = nilfs_btree_node_get_nchildren(btree, node); | 1268 | n = nilfs_btree_node_get_nchildren(node); |
1307 | 1269 | ||
1308 | nilfs_btree_node_move_left(btree, left, node, n); | 1270 | nilfs_btree_node_move_left(btree, left, node, n); |
1309 | 1271 | ||
@@ -1316,7 +1278,7 @@ static void nilfs_btree_concat_left(struct nilfs_btree *btree, | |||
1316 | nilfs_btnode_delete(path[level].bp_bh); | 1278 | nilfs_btnode_delete(path[level].bp_bh); |
1317 | path[level].bp_bh = path[level].bp_sib_bh; | 1279 | path[level].bp_bh = path[level].bp_sib_bh; |
1318 | path[level].bp_sib_bh = NULL; | 1280 | path[level].bp_sib_bh = NULL; |
1319 | path[level].bp_index += nilfs_btree_node_get_nchildren(btree, left); | 1281 | path[level].bp_index += nilfs_btree_node_get_nchildren(left); |
1320 | } | 1282 | } |
1321 | 1283 | ||
1322 | static void nilfs_btree_concat_right(struct nilfs_btree *btree, | 1284 | static void nilfs_btree_concat_right(struct nilfs_btree *btree, |
@@ -1331,10 +1293,10 @@ static void nilfs_btree_concat_right(struct nilfs_btree *btree, | |||
1331 | lock_buffer(path[level].bp_bh); | 1293 | lock_buffer(path[level].bp_bh); |
1332 | lock_buffer(path[level].bp_sib_bh); | 1294 | lock_buffer(path[level].bp_sib_bh); |
1333 | 1295 | ||
1334 | node = nilfs_btree_get_nonroot_node(btree, path, level); | 1296 | node = nilfs_btree_get_nonroot_node(path, level); |
1335 | right = nilfs_btree_get_sib_node(btree, path, level); | 1297 | right = nilfs_btree_get_sib_node(path, level); |
1336 | 1298 | ||
1337 | n = nilfs_btree_node_get_nchildren(btree, right); | 1299 | n = nilfs_btree_node_get_nchildren(right); |
1338 | 1300 | ||
1339 | nilfs_btree_node_move_left(btree, node, right, n); | 1301 | nilfs_btree_node_move_left(btree, node, right, n); |
1340 | 1302 | ||
@@ -1360,11 +1322,11 @@ static void nilfs_btree_shrink(struct nilfs_btree *btree, | |||
1360 | 1322 | ||
1361 | lock_buffer(path[level].bp_bh); | 1323 | lock_buffer(path[level].bp_bh); |
1362 | root = nilfs_btree_get_root(btree); | 1324 | root = nilfs_btree_get_root(btree); |
1363 | child = nilfs_btree_get_nonroot_node(btree, path, level); | 1325 | child = nilfs_btree_get_nonroot_node(path, level); |
1364 | 1326 | ||
1365 | nilfs_btree_node_delete(btree, root, NULL, NULL, 0); | 1327 | nilfs_btree_node_delete(btree, root, NULL, NULL, 0); |
1366 | nilfs_btree_node_set_level(btree, root, level); | 1328 | nilfs_btree_node_set_level(root, level); |
1367 | n = nilfs_btree_node_get_nchildren(btree, child); | 1329 | n = nilfs_btree_node_get_nchildren(child); |
1368 | nilfs_btree_node_move_left(btree, root, child, n); | 1330 | nilfs_btree_node_move_left(btree, root, child, n); |
1369 | unlock_buffer(path[level].bp_bh); | 1331 | unlock_buffer(path[level].bp_bh); |
1370 | 1332 | ||
@@ -1388,7 +1350,7 @@ static int nilfs_btree_prepare_delete(struct nilfs_btree *btree, | |||
1388 | for (level = NILFS_BTREE_LEVEL_NODE_MIN; | 1350 | for (level = NILFS_BTREE_LEVEL_NODE_MIN; |
1389 | level < nilfs_btree_height(btree) - 1; | 1351 | level < nilfs_btree_height(btree) - 1; |
1390 | level++) { | 1352 | level++) { |
1391 | node = nilfs_btree_get_nonroot_node(btree, path, level); | 1353 | node = nilfs_btree_get_nonroot_node(path, level); |
1392 | path[level].bp_oldreq.bpr_ptr = | 1354 | path[level].bp_oldreq.bpr_ptr = |
1393 | nilfs_btree_node_get_ptr(btree, node, | 1355 | nilfs_btree_node_get_ptr(btree, node, |
1394 | path[level].bp_index); | 1356 | path[level].bp_index); |
@@ -1397,8 +1359,8 @@ static int nilfs_btree_prepare_delete(struct nilfs_btree *btree, | |||
1397 | if (ret < 0) | 1359 | if (ret < 0) |
1398 | goto err_out_child_node; | 1360 | goto err_out_child_node; |
1399 | 1361 | ||
1400 | if (nilfs_btree_node_get_nchildren(btree, node) > | 1362 | if (nilfs_btree_node_get_nchildren(node) > |
1401 | nilfs_btree_node_nchildren_min(btree, node)) { | 1363 | nilfs_btree_node_nchildren_min(node, btree)) { |
1402 | path[level].bp_op = nilfs_btree_do_delete; | 1364 | path[level].bp_op = nilfs_btree_do_delete; |
1403 | stats->bs_nblocks++; | 1365 | stats->bs_nblocks++; |
1404 | goto out; | 1366 | goto out; |
@@ -1415,8 +1377,8 @@ static int nilfs_btree_prepare_delete(struct nilfs_btree *btree, | |||
1415 | if (ret < 0) | 1377 | if (ret < 0) |
1416 | goto err_out_curr_node; | 1378 | goto err_out_curr_node; |
1417 | sib = (struct nilfs_btree_node *)bh->b_data; | 1379 | sib = (struct nilfs_btree_node *)bh->b_data; |
1418 | if (nilfs_btree_node_get_nchildren(btree, sib) > | 1380 | if (nilfs_btree_node_get_nchildren(sib) > |
1419 | nilfs_btree_node_nchildren_min(btree, sib)) { | 1381 | nilfs_btree_node_nchildren_min(sib, btree)) { |
1420 | path[level].bp_sib_bh = bh; | 1382 | path[level].bp_sib_bh = bh; |
1421 | path[level].bp_op = nilfs_btree_borrow_left; | 1383 | path[level].bp_op = nilfs_btree_borrow_left; |
1422 | stats->bs_nblocks++; | 1384 | stats->bs_nblocks++; |
@@ -1428,7 +1390,7 @@ static int nilfs_btree_prepare_delete(struct nilfs_btree *btree, | |||
1428 | /* continue; */ | 1390 | /* continue; */ |
1429 | } | 1391 | } |
1430 | } else if (pindex < | 1392 | } else if (pindex < |
1431 | nilfs_btree_node_get_nchildren(btree, parent) - 1) { | 1393 | nilfs_btree_node_get_nchildren(parent) - 1) { |
1432 | /* right sibling */ | 1394 | /* right sibling */ |
1433 | sibptr = nilfs_btree_node_get_ptr(btree, parent, | 1395 | sibptr = nilfs_btree_node_get_ptr(btree, parent, |
1434 | pindex + 1); | 1396 | pindex + 1); |
@@ -1436,8 +1398,8 @@ static int nilfs_btree_prepare_delete(struct nilfs_btree *btree, | |||
1436 | if (ret < 0) | 1398 | if (ret < 0) |
1437 | goto err_out_curr_node; | 1399 | goto err_out_curr_node; |
1438 | sib = (struct nilfs_btree_node *)bh->b_data; | 1400 | sib = (struct nilfs_btree_node *)bh->b_data; |
1439 | if (nilfs_btree_node_get_nchildren(btree, sib) > | 1401 | if (nilfs_btree_node_get_nchildren(sib) > |
1440 | nilfs_btree_node_nchildren_min(btree, sib)) { | 1402 | nilfs_btree_node_nchildren_min(sib, btree)) { |
1441 | path[level].bp_sib_bh = bh; | 1403 | path[level].bp_sib_bh = bh; |
1442 | path[level].bp_op = nilfs_btree_borrow_right; | 1404 | path[level].bp_op = nilfs_btree_borrow_right; |
1443 | stats->bs_nblocks++; | 1405 | stats->bs_nblocks++; |
@@ -1452,7 +1414,7 @@ static int nilfs_btree_prepare_delete(struct nilfs_btree *btree, | |||
1452 | /* no siblings */ | 1414 | /* no siblings */ |
1453 | /* the only child of the root node */ | 1415 | /* the only child of the root node */ |
1454 | WARN_ON(level != nilfs_btree_height(btree) - 2); | 1416 | WARN_ON(level != nilfs_btree_height(btree) - 2); |
1455 | if (nilfs_btree_node_get_nchildren(btree, node) - 1 <= | 1417 | if (nilfs_btree_node_get_nchildren(node) - 1 <= |
1456 | NILFS_BTREE_ROOT_NCHILDREN_MAX) { | 1418 | NILFS_BTREE_ROOT_NCHILDREN_MAX) { |
1457 | path[level].bp_op = nilfs_btree_shrink; | 1419 | path[level].bp_op = nilfs_btree_shrink; |
1458 | stats->bs_nblocks += 2; | 1420 | stats->bs_nblocks += 2; |
@@ -1523,10 +1485,10 @@ static int nilfs_btree_delete(struct nilfs_bmap *bmap, __u64 key) | |||
1523 | int level, ret; | 1485 | int level, ret; |
1524 | 1486 | ||
1525 | btree = (struct nilfs_btree *)bmap; | 1487 | btree = (struct nilfs_btree *)bmap; |
1526 | path = nilfs_btree_alloc_path(btree); | 1488 | path = nilfs_btree_alloc_path(); |
1527 | if (path == NULL) | 1489 | if (path == NULL) |
1528 | return -ENOMEM; | 1490 | return -ENOMEM; |
1529 | nilfs_btree_init_path(btree, path); | 1491 | nilfs_btree_init_path(path); |
1530 | ret = nilfs_btree_do_lookup(btree, path, key, NULL, | 1492 | ret = nilfs_btree_do_lookup(btree, path, key, NULL, |
1531 | NILFS_BTREE_LEVEL_NODE_MIN); | 1493 | NILFS_BTREE_LEVEL_NODE_MIN); |
1532 | if (ret < 0) | 1494 | if (ret < 0) |
@@ -1539,8 +1501,8 @@ static int nilfs_btree_delete(struct nilfs_bmap *bmap, __u64 key) | |||
1539 | nilfs_bmap_sub_blocks(bmap, stats.bs_nblocks); | 1501 | nilfs_bmap_sub_blocks(bmap, stats.bs_nblocks); |
1540 | 1502 | ||
1541 | out: | 1503 | out: |
1542 | nilfs_btree_clear_path(btree, path); | 1504 | nilfs_btree_clear_path(path); |
1543 | nilfs_btree_free_path(btree, path); | 1505 | nilfs_btree_free_path(path); |
1544 | return ret; | 1506 | return ret; |
1545 | } | 1507 | } |
1546 | 1508 | ||
@@ -1551,15 +1513,15 @@ static int nilfs_btree_last_key(const struct nilfs_bmap *bmap, __u64 *keyp) | |||
1551 | int ret; | 1513 | int ret; |
1552 | 1514 | ||
1553 | btree = (struct nilfs_btree *)bmap; | 1515 | btree = (struct nilfs_btree *)bmap; |
1554 | path = nilfs_btree_alloc_path(btree); | 1516 | path = nilfs_btree_alloc_path(); |
1555 | if (path == NULL) | 1517 | if (path == NULL) |
1556 | return -ENOMEM; | 1518 | return -ENOMEM; |
1557 | nilfs_btree_init_path(btree, path); | 1519 | nilfs_btree_init_path(path); |
1558 | 1520 | ||
1559 | ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL); | 1521 | ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL); |
1560 | 1522 | ||
1561 | nilfs_btree_clear_path(btree, path); | 1523 | nilfs_btree_clear_path(path); |
1562 | nilfs_btree_free_path(btree, path); | 1524 | nilfs_btree_free_path(path); |
1563 | 1525 | ||
1564 | return ret; | 1526 | return ret; |
1565 | } | 1527 | } |
@@ -1581,7 +1543,7 @@ static int nilfs_btree_check_delete(struct nilfs_bmap *bmap, __u64 key) | |||
1581 | node = root; | 1543 | node = root; |
1582 | break; | 1544 | break; |
1583 | case 3: | 1545 | case 3: |
1584 | nchildren = nilfs_btree_node_get_nchildren(btree, root); | 1546 | nchildren = nilfs_btree_node_get_nchildren(root); |
1585 | if (nchildren > 1) | 1547 | if (nchildren > 1) |
1586 | return 0; | 1548 | return 0; |
1587 | ptr = nilfs_btree_node_get_ptr(btree, root, nchildren - 1); | 1549 | ptr = nilfs_btree_node_get_ptr(btree, root, nchildren - 1); |
@@ -1594,10 +1556,10 @@ static int nilfs_btree_check_delete(struct nilfs_bmap *bmap, __u64 key) | |||
1594 | return 0; | 1556 | return 0; |
1595 | } | 1557 | } |
1596 | 1558 | ||
1597 | nchildren = nilfs_btree_node_get_nchildren(btree, node); | 1559 | nchildren = nilfs_btree_node_get_nchildren(node); |
1598 | maxkey = nilfs_btree_node_get_key(btree, node, nchildren - 1); | 1560 | maxkey = nilfs_btree_node_get_key(node, nchildren - 1); |
1599 | nextmaxkey = (nchildren > 1) ? | 1561 | nextmaxkey = (nchildren > 1) ? |
1600 | nilfs_btree_node_get_key(btree, node, nchildren - 2) : 0; | 1562 | nilfs_btree_node_get_key(node, nchildren - 2) : 0; |
1601 | if (bh != NULL) | 1563 | if (bh != NULL) |
1602 | brelse(bh); | 1564 | brelse(bh); |
1603 | 1565 | ||
@@ -1623,7 +1585,7 @@ static int nilfs_btree_gather_data(struct nilfs_bmap *bmap, | |||
1623 | node = root; | 1585 | node = root; |
1624 | break; | 1586 | break; |
1625 | case 3: | 1587 | case 3: |
1626 | nchildren = nilfs_btree_node_get_nchildren(btree, root); | 1588 | nchildren = nilfs_btree_node_get_nchildren(root); |
1627 | WARN_ON(nchildren > 1); | 1589 | WARN_ON(nchildren > 1); |
1628 | ptr = nilfs_btree_node_get_ptr(btree, root, nchildren - 1); | 1590 | ptr = nilfs_btree_node_get_ptr(btree, root, nchildren - 1); |
1629 | ret = nilfs_btree_get_block(btree, ptr, &bh); | 1591 | ret = nilfs_btree_get_block(btree, ptr, &bh); |
@@ -1636,11 +1598,11 @@ static int nilfs_btree_gather_data(struct nilfs_bmap *bmap, | |||
1636 | return -EINVAL; | 1598 | return -EINVAL; |
1637 | } | 1599 | } |
1638 | 1600 | ||
1639 | nchildren = nilfs_btree_node_get_nchildren(btree, node); | 1601 | nchildren = nilfs_btree_node_get_nchildren(node); |
1640 | if (nchildren < nitems) | 1602 | if (nchildren < nitems) |
1641 | nitems = nchildren; | 1603 | nitems = nchildren; |
1642 | dkeys = nilfs_btree_node_dkeys(btree, node); | 1604 | dkeys = nilfs_btree_node_dkeys(node); |
1643 | dptrs = nilfs_btree_node_dptrs(btree, node); | 1605 | dptrs = nilfs_btree_node_dptrs(node, btree); |
1644 | for (i = 0; i < nitems; i++) { | 1606 | for (i = 0; i < nitems; i++) { |
1645 | keys[i] = nilfs_bmap_dkey_to_key(dkeys[i]); | 1607 | keys[i] = nilfs_bmap_dkey_to_key(dkeys[i]); |
1646 | ptrs[i] = nilfs_bmap_dptr_to_ptr(dptrs[i]); | 1608 | ptrs[i] = nilfs_bmap_dptr_to_ptr(dptrs[i]); |
@@ -1986,15 +1948,15 @@ static int nilfs_btree_propagate(const struct nilfs_bmap *bmap, | |||
1986 | WARN_ON(!buffer_dirty(bh)); | 1948 | WARN_ON(!buffer_dirty(bh)); |
1987 | 1949 | ||
1988 | btree = (struct nilfs_btree *)bmap; | 1950 | btree = (struct nilfs_btree *)bmap; |
1989 | path = nilfs_btree_alloc_path(btree); | 1951 | path = nilfs_btree_alloc_path(); |
1990 | if (path == NULL) | 1952 | if (path == NULL) |
1991 | return -ENOMEM; | 1953 | return -ENOMEM; |
1992 | nilfs_btree_init_path(btree, path); | 1954 | nilfs_btree_init_path(path); |
1993 | 1955 | ||
1994 | if (buffer_nilfs_node(bh)) { | 1956 | if (buffer_nilfs_node(bh)) { |
1995 | node = (struct nilfs_btree_node *)bh->b_data; | 1957 | node = (struct nilfs_btree_node *)bh->b_data; |
1996 | key = nilfs_btree_node_get_key(btree, node, 0); | 1958 | key = nilfs_btree_node_get_key(node, 0); |
1997 | level = nilfs_btree_node_get_level(btree, node); | 1959 | level = nilfs_btree_node_get_level(node); |
1998 | } else { | 1960 | } else { |
1999 | key = nilfs_bmap_data_get_key(bmap, bh); | 1961 | key = nilfs_bmap_data_get_key(bmap, bh); |
2000 | level = NILFS_BTREE_LEVEL_DATA; | 1962 | level = NILFS_BTREE_LEVEL_DATA; |
@@ -2013,8 +1975,8 @@ static int nilfs_btree_propagate(const struct nilfs_bmap *bmap, | |||
2013 | nilfs_btree_propagate_p(btree, path, level, bh); | 1975 | nilfs_btree_propagate_p(btree, path, level, bh); |
2014 | 1976 | ||
2015 | out: | 1977 | out: |
2016 | nilfs_btree_clear_path(btree, path); | 1978 | nilfs_btree_clear_path(path); |
2017 | nilfs_btree_free_path(btree, path); | 1979 | nilfs_btree_free_path(path); |
2018 | 1980 | ||
2019 | return ret; | 1981 | return ret; |
2020 | } | 1982 | } |
@@ -2037,12 +1999,12 @@ static void nilfs_btree_add_dirty_buffer(struct nilfs_btree *btree, | |||
2037 | 1999 | ||
2038 | get_bh(bh); | 2000 | get_bh(bh); |
2039 | node = (struct nilfs_btree_node *)bh->b_data; | 2001 | node = (struct nilfs_btree_node *)bh->b_data; |
2040 | key = nilfs_btree_node_get_key(btree, node, 0); | 2002 | key = nilfs_btree_node_get_key(node, 0); |
2041 | level = nilfs_btree_node_get_level(btree, node); | 2003 | level = nilfs_btree_node_get_level(node); |
2042 | list_for_each(head, &lists[level]) { | 2004 | list_for_each(head, &lists[level]) { |
2043 | cbh = list_entry(head, struct buffer_head, b_assoc_buffers); | 2005 | cbh = list_entry(head, struct buffer_head, b_assoc_buffers); |
2044 | cnode = (struct nilfs_btree_node *)cbh->b_data; | 2006 | cnode = (struct nilfs_btree_node *)cbh->b_data; |
2045 | ckey = nilfs_btree_node_get_key(btree, cnode, 0); | 2007 | ckey = nilfs_btree_node_get_key(cnode, 0); |
2046 | if (key < ckey) | 2008 | if (key < ckey) |
2047 | break; | 2009 | break; |
2048 | } | 2010 | } |
@@ -2120,8 +2082,7 @@ static int nilfs_btree_assign_p(struct nilfs_btree *btree, | |||
2120 | nilfs_btree_node_set_ptr(btree, parent, | 2082 | nilfs_btree_node_set_ptr(btree, parent, |
2121 | path[level + 1].bp_index, blocknr); | 2083 | path[level + 1].bp_index, blocknr); |
2122 | 2084 | ||
2123 | key = nilfs_btree_node_get_key(btree, parent, | 2085 | key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); |
2124 | path[level + 1].bp_index); | ||
2125 | /* on-disk format */ | 2086 | /* on-disk format */ |
2126 | binfo->bi_dat.bi_blkoff = nilfs_bmap_key_to_dkey(key); | 2087 | binfo->bi_dat.bi_blkoff = nilfs_bmap_key_to_dkey(key); |
2127 | binfo->bi_dat.bi_level = level; | 2088 | binfo->bi_dat.bi_level = level; |
@@ -2150,8 +2111,7 @@ static int nilfs_btree_assign_v(struct nilfs_btree *btree, | |||
2150 | if (unlikely(ret < 0)) | 2111 | if (unlikely(ret < 0)) |
2151 | return ret; | 2112 | return ret; |
2152 | 2113 | ||
2153 | key = nilfs_btree_node_get_key(btree, parent, | 2114 | key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); |
2154 | path[level + 1].bp_index); | ||
2155 | /* on-disk format */ | 2115 | /* on-disk format */ |
2156 | binfo->bi_v.bi_vblocknr = nilfs_bmap_ptr_to_dptr(ptr); | 2116 | binfo->bi_v.bi_vblocknr = nilfs_bmap_ptr_to_dptr(ptr); |
2157 | binfo->bi_v.bi_blkoff = nilfs_bmap_key_to_dkey(key); | 2117 | binfo->bi_v.bi_blkoff = nilfs_bmap_key_to_dkey(key); |
@@ -2171,15 +2131,15 @@ static int nilfs_btree_assign(struct nilfs_bmap *bmap, | |||
2171 | int level, ret; | 2131 | int level, ret; |
2172 | 2132 | ||
2173 | btree = (struct nilfs_btree *)bmap; | 2133 | btree = (struct nilfs_btree *)bmap; |
2174 | path = nilfs_btree_alloc_path(btree); | 2134 | path = nilfs_btree_alloc_path(); |
2175 | if (path == NULL) | 2135 | if (path == NULL) |
2176 | return -ENOMEM; | 2136 | return -ENOMEM; |
2177 | nilfs_btree_init_path(btree, path); | 2137 | nilfs_btree_init_path(path); |
2178 | 2138 | ||
2179 | if (buffer_nilfs_node(*bh)) { | 2139 | if (buffer_nilfs_node(*bh)) { |
2180 | node = (struct nilfs_btree_node *)(*bh)->b_data; | 2140 | node = (struct nilfs_btree_node *)(*bh)->b_data; |
2181 | key = nilfs_btree_node_get_key(btree, node, 0); | 2141 | key = nilfs_btree_node_get_key(node, 0); |
2182 | level = nilfs_btree_node_get_level(btree, node); | 2142 | level = nilfs_btree_node_get_level(node); |
2183 | } else { | 2143 | } else { |
2184 | key = nilfs_bmap_data_get_key(bmap, *bh); | 2144 | key = nilfs_bmap_data_get_key(bmap, *bh); |
2185 | level = NILFS_BTREE_LEVEL_DATA; | 2145 | level = NILFS_BTREE_LEVEL_DATA; |
@@ -2196,8 +2156,8 @@ static int nilfs_btree_assign(struct nilfs_bmap *bmap, | |||
2196 | nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo); | 2156 | nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo); |
2197 | 2157 | ||
2198 | out: | 2158 | out: |
2199 | nilfs_btree_clear_path(btree, path); | 2159 | nilfs_btree_clear_path(path); |
2200 | nilfs_btree_free_path(btree, path); | 2160 | nilfs_btree_free_path(path); |
2201 | 2161 | ||
2202 | return ret; | 2162 | return ret; |
2203 | } | 2163 | } |
@@ -2219,7 +2179,7 @@ static int nilfs_btree_assign_gc(struct nilfs_bmap *bmap, | |||
2219 | 2179 | ||
2220 | if (buffer_nilfs_node(*bh)) { | 2180 | if (buffer_nilfs_node(*bh)) { |
2221 | node = (struct nilfs_btree_node *)(*bh)->b_data; | 2181 | node = (struct nilfs_btree_node *)(*bh)->b_data; |
2222 | key = nilfs_btree_node_get_key(btree, node, 0); | 2182 | key = nilfs_btree_node_get_key(node, 0); |
2223 | } else | 2183 | } else |
2224 | key = nilfs_bmap_data_get_key(bmap, *bh); | 2184 | key = nilfs_bmap_data_get_key(bmap, *bh); |
2225 | 2185 | ||
@@ -2239,10 +2199,10 @@ static int nilfs_btree_mark(struct nilfs_bmap *bmap, __u64 key, int level) | |||
2239 | int ret; | 2199 | int ret; |
2240 | 2200 | ||
2241 | btree = (struct nilfs_btree *)bmap; | 2201 | btree = (struct nilfs_btree *)bmap; |
2242 | path = nilfs_btree_alloc_path(btree); | 2202 | path = nilfs_btree_alloc_path(); |
2243 | if (path == NULL) | 2203 | if (path == NULL) |
2244 | return -ENOMEM; | 2204 | return -ENOMEM; |
2245 | nilfs_btree_init_path(btree, path); | 2205 | nilfs_btree_init_path(path); |
2246 | 2206 | ||
2247 | ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1); | 2207 | ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1); |
2248 | if (ret < 0) { | 2208 | if (ret < 0) { |
@@ -2262,8 +2222,8 @@ static int nilfs_btree_mark(struct nilfs_bmap *bmap, __u64 key, int level) | |||
2262 | nilfs_bmap_set_dirty(&btree->bt_bmap); | 2222 | nilfs_bmap_set_dirty(&btree->bt_bmap); |
2263 | 2223 | ||
2264 | out: | 2224 | out: |
2265 | nilfs_btree_clear_path(btree, path); | 2225 | nilfs_btree_clear_path(path); |
2266 | nilfs_btree_free_path(btree, path); | 2226 | nilfs_btree_free_path(path); |
2267 | return ret; | 2227 | return ret; |
2268 | } | 2228 | } |
2269 | 2229 | ||