diff options
| -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 | ||
