Lines Matching full:level
26 int level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_alloc_path() local
32 for (; level < NILFS_BTREE_LEVEL_MAX; level++) { in nilfs_btree_alloc_path()
33 path[level].bp_bh = NULL; in nilfs_btree_alloc_path()
34 path[level].bp_sib_bh = NULL; in nilfs_btree_alloc_path()
35 path[level].bp_index = 0; in nilfs_btree_alloc_path()
36 path[level].bp_oldreq.bpr_ptr = NILFS_BMAP_INVALID_PTR; in nilfs_btree_alloc_path()
37 path[level].bp_newreq.bpr_ptr = NILFS_BMAP_INVALID_PTR; in nilfs_btree_alloc_path()
38 path[level].bp_op = NULL; in nilfs_btree_alloc_path()
47 int level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_free_path() local
49 for (; level < NILFS_BTREE_LEVEL_MAX; level++) in nilfs_btree_free_path()
50 brelse(path[level].bp_bh); in nilfs_btree_free_path()
96 nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level) in nilfs_btree_node_set_level() argument
98 node->bn_level = level; in nilfs_btree_node_set_level()
163 int level, int nchildren, int ncmax, in nilfs_btree_node_init() argument
171 nilfs_btree_node_set_level(node, level); in nilfs_btree_node_init()
343 int level, flags, nchildren; in nilfs_btree_node_broken() local
346 level = nilfs_btree_node_get_level(node); in nilfs_btree_node_broken()
350 if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN || in nilfs_btree_node_broken()
351 level >= NILFS_BTREE_LEVEL_MAX || in nilfs_btree_node_broken()
356 "bad btree node (ino=%lu, blocknr=%llu): level = %d, flags = 0x%x, nchildren = %d", in nilfs_btree_node_broken()
357 inode->i_ino, (unsigned long long)blocknr, level, in nilfs_btree_node_broken()
374 int level, flags, nchildren; in nilfs_btree_root_broken() local
377 level = nilfs_btree_node_get_level(node); in nilfs_btree_root_broken()
381 if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN || in nilfs_btree_root_broken()
382 level >= NILFS_BTREE_LEVEL_MAX || in nilfs_btree_root_broken()
386 "bad btree root (ino=%lu): level = %d, flags = 0x%x, nchildren = %d", in nilfs_btree_root_broken()
387 inode->i_ino, level, flags, nchildren); in nilfs_btree_root_broken()
416 nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level) in nilfs_btree_get_nonroot_node() argument
418 return (struct nilfs_btree_node *)path[level].bp_bh->b_data; in nilfs_btree_get_nonroot_node()
422 nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level) in nilfs_btree_get_sib_node() argument
424 return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data; in nilfs_btree_get_sib_node()
435 int level, int *ncmaxp) in nilfs_btree_get_node() argument
439 if (level == nilfs_btree_height(btree) - 1) { in nilfs_btree_get_node()
443 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_get_node()
450 struct nilfs_btree_node *node, int level) in nilfs_btree_bad_node() argument
452 if (unlikely(nilfs_btree_node_get_level(node) != level)) { in nilfs_btree_bad_node()
455 "btree level mismatch (ino=%lu): %d != %d", in nilfs_btree_bad_node()
457 nilfs_btree_node_get_level(node), level); in nilfs_btree_bad_node()
554 int level, index, found, ncmax, ret; in nilfs_btree_do_lookup() local
557 level = nilfs_btree_node_get_level(node); in nilfs_btree_do_lookup()
558 if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0) in nilfs_btree_do_lookup()
564 path[level].bp_bh = NULL; in nilfs_btree_do_lookup()
565 path[level].bp_index = index; in nilfs_btree_do_lookup()
569 while (--level >= minlevel) { in nilfs_btree_do_lookup()
571 if (level == NILFS_BTREE_LEVEL_NODE_MIN && readahead) { in nilfs_btree_do_lookup()
572 p.node = nilfs_btree_get_node(btree, path, level + 1, in nilfs_btree_do_lookup()
578 ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh, in nilfs_btree_do_lookup()
583 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_lookup()
584 if (nilfs_btree_bad_node(btree, node, level)) in nilfs_btree_do_lookup()
593 WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN); in nilfs_btree_do_lookup()
597 path[level].bp_index = index; in nilfs_btree_do_lookup()
614 int index, level, ncmax, ret; in nilfs_btree_do_lookup_last() local
620 level = nilfs_btree_node_get_level(node); in nilfs_btree_do_lookup_last()
623 path[level].bp_bh = NULL; in nilfs_btree_do_lookup_last()
624 path[level].bp_index = index; in nilfs_btree_do_lookup_last()
627 for (level--; level > 0; level--) { in nilfs_btree_do_lookup_last()
628 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh); in nilfs_btree_do_lookup_last()
631 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_lookup_last()
632 if (nilfs_btree_bad_node(btree, node, level)) in nilfs_btree_do_lookup_last()
636 path[level].bp_index = index; in nilfs_btree_do_lookup_last()
651 * @minlevel: start level
663 int index, next_adj, level; in nilfs_btree_get_next_key() local
667 for (level = minlevel; level <= maxlevel; level++) { in nilfs_btree_get_next_key()
668 if (level == maxlevel) in nilfs_btree_get_next_key()
671 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_get_next_key()
673 index = path[level].bp_index + next_adj; in nilfs_btree_get_next_key()
686 __u64 key, int level, __u64 *ptrp) in nilfs_btree_lookup() argument
695 ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0); in nilfs_btree_lookup()
711 int level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_lookup_contig() local
719 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1); in nilfs_btree_lookup_contig()
735 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_lookup_contig()
736 index = path[level].bp_index + 1; in nilfs_btree_lookup_contig()
754 if (level == maxlevel) in nilfs_btree_lookup_contig()
758 p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax); in nilfs_btree_lookup_contig()
759 p.index = path[level + 1].bp_index + 1; in nilfs_btree_lookup_contig()
765 path[level + 1].bp_index = p.index; in nilfs_btree_lookup_contig()
767 brelse(path[level].bp_bh); in nilfs_btree_lookup_contig()
768 path[level].bp_bh = NULL; in nilfs_btree_lookup_contig()
770 ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh, in nilfs_btree_lookup_contig()
774 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_lookup_contig()
777 path[level].bp_index = index; in nilfs_btree_lookup_contig()
789 int level, __u64 key) in nilfs_btree_promote_key() argument
791 if (level < nilfs_btree_height(btree) - 1) { in nilfs_btree_promote_key()
794 nilfs_btree_get_nonroot_node(path, level), in nilfs_btree_promote_key()
795 path[level].bp_index, key); in nilfs_btree_promote_key()
796 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_promote_key()
797 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_promote_key()
798 } while ((path[level].bp_index == 0) && in nilfs_btree_promote_key()
799 (++level < nilfs_btree_height(btree) - 1)); in nilfs_btree_promote_key()
803 if (level == nilfs_btree_height(btree) - 1) { in nilfs_btree_promote_key()
805 path[level].bp_index, key); in nilfs_btree_promote_key()
811 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_do_insert() argument
816 if (level < nilfs_btree_height(btree) - 1) { in nilfs_btree_do_insert()
817 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_insert()
819 nilfs_btree_node_insert(node, path[level].bp_index, in nilfs_btree_do_insert()
821 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_do_insert()
822 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_do_insert()
824 if (path[level].bp_index == 0) in nilfs_btree_do_insert()
825 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_do_insert()
830 nilfs_btree_node_insert(node, path[level].bp_index, in nilfs_btree_do_insert()
838 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_carry_left() argument
843 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_carry_left()
844 left = nilfs_btree_get_sib_node(path, level); in nilfs_btree_carry_left()
851 if (n > path[level].bp_index) { in nilfs_btree_carry_left()
859 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_carry_left()
860 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_carry_left()
861 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_carry_left()
862 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_carry_left()
864 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_carry_left()
868 brelse(path[level].bp_bh); in nilfs_btree_carry_left()
869 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_carry_left()
870 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_left()
871 path[level].bp_index += lnchildren; in nilfs_btree_carry_left()
872 path[level + 1].bp_index--; in nilfs_btree_carry_left()
874 brelse(path[level].bp_sib_bh); in nilfs_btree_carry_left()
875 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_left()
876 path[level].bp_index -= n; in nilfs_btree_carry_left()
879 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_carry_left()
884 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_carry_right() argument
889 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_carry_right()
890 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_carry_right()
897 if (n > nchildren - path[level].bp_index) { in nilfs_btree_carry_right()
905 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_carry_right()
906 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_carry_right()
907 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_carry_right()
908 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_carry_right()
910 path[level + 1].bp_index++; in nilfs_btree_carry_right()
911 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_carry_right()
913 path[level + 1].bp_index--; in nilfs_btree_carry_right()
916 brelse(path[level].bp_bh); in nilfs_btree_carry_right()
917 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_carry_right()
918 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_right()
919 path[level].bp_index -= nilfs_btree_node_get_nchildren(node); in nilfs_btree_carry_right()
920 path[level + 1].bp_index++; in nilfs_btree_carry_right()
922 brelse(path[level].bp_sib_bh); in nilfs_btree_carry_right()
923 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_right()
926 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_carry_right()
931 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_split() argument
936 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_split()
937 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_split()
943 if (n > nchildren - path[level].bp_index) { in nilfs_btree_split()
950 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_split()
951 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_split()
952 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_split()
953 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_split()
956 path[level].bp_index -= nilfs_btree_node_get_nchildren(node); in nilfs_btree_split()
957 nilfs_btree_node_insert(right, path[level].bp_index, in nilfs_btree_split()
961 *ptrp = path[level].bp_newreq.bpr_ptr; in nilfs_btree_split()
963 brelse(path[level].bp_bh); in nilfs_btree_split()
964 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_split()
965 path[level].bp_sib_bh = NULL; in nilfs_btree_split()
967 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_split()
970 *ptrp = path[level].bp_newreq.bpr_ptr; in nilfs_btree_split()
972 brelse(path[level].bp_sib_bh); in nilfs_btree_split()
973 path[level].bp_sib_bh = NULL; in nilfs_btree_split()
976 path[level + 1].bp_index++; in nilfs_btree_split()
981 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_grow() argument
987 child = nilfs_btree_get_sib_node(path, level); in nilfs_btree_grow()
994 nilfs_btree_node_set_level(root, level + 1); in nilfs_btree_grow()
996 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_grow()
997 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_grow()
999 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_grow()
1000 path[level].bp_sib_bh = NULL; in nilfs_btree_grow()
1002 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_grow()
1005 *ptrp = path[level].bp_newreq.bpr_ptr; in nilfs_btree_grow()
1012 int level, ncmax; in nilfs_btree_find_near() local
1018 level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_find_near()
1019 if (path[level].bp_index > 0) { in nilfs_btree_find_near()
1020 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_find_near()
1022 path[level].bp_index - 1, in nilfs_btree_find_near()
1027 level = NILFS_BTREE_LEVEL_NODE_MIN + 1; in nilfs_btree_find_near()
1028 if (level <= nilfs_btree_height(btree) - 1) { in nilfs_btree_find_near()
1029 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_find_near()
1030 return nilfs_btree_node_get_ptr(node, path[level].bp_index, in nilfs_btree_find_near()
1065 int pindex, level, ncmax, ncblk, ret; in nilfs_btree_prepare_insert() local
1069 level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_prepare_insert()
1073 path[level].bp_newreq.bpr_ptr = in nilfs_btree_prepare_insert()
1078 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1084 for (level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_prepare_insert()
1085 level < nilfs_btree_height(btree) - 1; in nilfs_btree_prepare_insert()
1086 level++) { in nilfs_btree_prepare_insert()
1087 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_prepare_insert()
1089 path[level].bp_op = nilfs_btree_do_insert; in nilfs_btree_prepare_insert()
1094 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_prepare_insert()
1095 pindex = path[level + 1].bp_index; in nilfs_btree_prepare_insert()
1106 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1107 path[level].bp_op = nilfs_btree_carry_left; in nilfs_btree_prepare_insert()
1124 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1125 path[level].bp_op = nilfs_btree_carry_right; in nilfs_btree_prepare_insert()
1134 path[level].bp_newreq.bpr_ptr = in nilfs_btree_prepare_insert()
1135 path[level - 1].bp_newreq.bpr_ptr + 1; in nilfs_btree_prepare_insert()
1137 &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1141 path[level].bp_newreq.bpr_ptr, in nilfs_btree_prepare_insert()
1149 nilfs_btree_node_init(sib, 0, level, 0, ncblk, NULL, NULL); in nilfs_btree_prepare_insert()
1150 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1151 path[level].bp_op = nilfs_btree_split; in nilfs_btree_prepare_insert()
1158 path[level].bp_op = nilfs_btree_do_insert; in nilfs_btree_prepare_insert()
1164 path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1; in nilfs_btree_prepare_insert()
1165 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1168 ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr, in nilfs_btree_prepare_insert()
1174 0, level, 0, ncblk, NULL, NULL); in nilfs_btree_prepare_insert()
1175 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1176 path[level].bp_op = nilfs_btree_grow; in nilfs_btree_prepare_insert()
1178 level++; in nilfs_btree_prepare_insert()
1179 path[level].bp_op = nilfs_btree_do_insert; in nilfs_btree_prepare_insert()
1186 *levelp = level; in nilfs_btree_prepare_insert()
1191 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1193 for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) { in nilfs_btree_prepare_insert()
1194 nilfs_btnode_delete(path[level].bp_sib_bh); in nilfs_btree_prepare_insert()
1195 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1199 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1201 *levelp = level; in nilfs_btree_prepare_insert()
1211 int level; in nilfs_btree_commit_insert() local
1220 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { in nilfs_btree_commit_insert()
1222 &path[level - 1].bp_newreq, dat); in nilfs_btree_commit_insert()
1223 path[level].bp_op(btree, path, level, &key, &ptr); in nilfs_btree_commit_insert()
1234 int level, ret; in nilfs_btree_insert() local
1248 ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats); in nilfs_btree_insert()
1251 nilfs_btree_commit_insert(btree, path, level, key, ptr); in nilfs_btree_insert()
1261 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_do_delete() argument
1266 if (level < nilfs_btree_height(btree) - 1) { in nilfs_btree_do_delete()
1267 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_delete()
1269 nilfs_btree_node_delete(node, path[level].bp_index, in nilfs_btree_do_delete()
1271 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_do_delete()
1272 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_do_delete()
1273 if (path[level].bp_index == 0) in nilfs_btree_do_delete()
1274 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_do_delete()
1278 nilfs_btree_node_delete(node, path[level].bp_index, in nilfs_btree_do_delete()
1286 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_borrow_left() argument
1291 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_borrow_left()
1293 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_borrow_left()
1294 left = nilfs_btree_get_sib_node(path, level); in nilfs_btree_borrow_left()
1303 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_borrow_left()
1304 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_borrow_left()
1305 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_borrow_left()
1306 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_borrow_left()
1308 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_borrow_left()
1311 brelse(path[level].bp_sib_bh); in nilfs_btree_borrow_left()
1312 path[level].bp_sib_bh = NULL; in nilfs_btree_borrow_left()
1313 path[level].bp_index += n; in nilfs_btree_borrow_left()
1318 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_borrow_right() argument
1323 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_borrow_right()
1325 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_borrow_right()
1326 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_borrow_right()
1335 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_borrow_right()
1336 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_borrow_right()
1337 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_borrow_right()
1338 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_borrow_right()
1340 path[level + 1].bp_index++; in nilfs_btree_borrow_right()
1341 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_borrow_right()
1343 path[level + 1].bp_index--; in nilfs_btree_borrow_right()
1345 brelse(path[level].bp_sib_bh); in nilfs_btree_borrow_right()
1346 path[level].bp_sib_bh = NULL; in nilfs_btree_borrow_right()
1351 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_concat_left() argument
1356 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_concat_left()
1358 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_concat_left()
1359 left = nilfs_btree_get_sib_node(path, level); in nilfs_btree_concat_left()
1366 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_concat_left()
1367 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_concat_left()
1369 nilfs_btnode_delete(path[level].bp_bh); in nilfs_btree_concat_left()
1370 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_concat_left()
1371 path[level].bp_sib_bh = NULL; in nilfs_btree_concat_left()
1372 path[level].bp_index += nilfs_btree_node_get_nchildren(left); in nilfs_btree_concat_left()
1377 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_concat_right() argument
1382 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_concat_right()
1384 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_concat_right()
1385 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_concat_right()
1392 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_concat_right()
1393 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_concat_right()
1395 nilfs_btnode_delete(path[level].bp_sib_bh); in nilfs_btree_concat_right()
1396 path[level].bp_sib_bh = NULL; in nilfs_btree_concat_right()
1397 path[level + 1].bp_index++; in nilfs_btree_concat_right()
1402 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_shrink() argument
1407 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_shrink()
1410 child = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_shrink()
1415 nilfs_btree_node_set_level(root, level); in nilfs_btree_shrink()
1420 nilfs_btnode_delete(path[level].bp_bh); in nilfs_btree_shrink()
1421 path[level].bp_bh = NULL; in nilfs_btree_shrink()
1426 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_nop() argument
1439 int pindex, dindex, level, ncmin, ncmax, ncblk, ret; in nilfs_btree_prepare_delete() local
1446 for (level = NILFS_BTREE_LEVEL_NODE_MIN, dindex = path[level].bp_index; in nilfs_btree_prepare_delete()
1447 level < nilfs_btree_height(btree) - 1; in nilfs_btree_prepare_delete()
1448 level++) { in nilfs_btree_prepare_delete()
1449 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_prepare_delete()
1450 path[level].bp_oldreq.bpr_ptr = in nilfs_btree_prepare_delete()
1453 &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1458 path[level].bp_op = nilfs_btree_do_delete; in nilfs_btree_prepare_delete()
1463 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_prepare_delete()
1464 pindex = path[level + 1].bp_index; in nilfs_btree_prepare_delete()
1476 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1477 path[level].bp_op = nilfs_btree_borrow_left; in nilfs_btree_prepare_delete()
1481 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1482 path[level].bp_op = nilfs_btree_concat_left; in nilfs_btree_prepare_delete()
1496 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1497 path[level].bp_op = nilfs_btree_borrow_right; in nilfs_btree_prepare_delete()
1501 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1502 path[level].bp_op = nilfs_btree_concat_right; in nilfs_btree_prepare_delete()
1517 WARN_ON(level != nilfs_btree_height(btree) - 2); in nilfs_btree_prepare_delete()
1520 path[level].bp_op = nilfs_btree_shrink; in nilfs_btree_prepare_delete()
1522 level++; in nilfs_btree_prepare_delete()
1523 path[level].bp_op = nilfs_btree_nop; in nilfs_btree_prepare_delete()
1526 path[level].bp_op = nilfs_btree_do_delete; in nilfs_btree_prepare_delete()
1534 path[level].bp_op = nilfs_btree_do_delete; in nilfs_btree_prepare_delete()
1539 path[level].bp_oldreq.bpr_ptr = in nilfs_btree_prepare_delete()
1543 ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1549 *levelp = level; in nilfs_btree_prepare_delete()
1554 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1556 for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) { in nilfs_btree_prepare_delete()
1557 brelse(path[level].bp_sib_bh); in nilfs_btree_prepare_delete()
1558 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1560 *levelp = level; in nilfs_btree_prepare_delete()
1569 int level; in nilfs_btree_commit_delete() local
1571 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { in nilfs_btree_commit_delete()
1572 nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_commit_delete()
1573 path[level].bp_op(btree, path, level, NULL, NULL); in nilfs_btree_commit_delete()
1586 int level, ret; in nilfs_btree_delete() local
1600 ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat); in nilfs_btree_delete()
1603 nilfs_btree_commit_delete(btree, path, level, dat); in nilfs_btree_delete()
1821 /* create child node at level 1 */ in nilfs_btree_commit_convert_and_insert()
1833 /* create root node at level 2 */ in nilfs_btree_commit_convert_and_insert()
1842 /* create root node at level 1 */ in nilfs_btree_commit_convert_and_insert()
1900 int level, in nilfs_btree_propagate_p() argument
1903 while ((++level < nilfs_btree_height(btree) - 1) && in nilfs_btree_propagate_p()
1904 !buffer_dirty(path[level].bp_bh)) in nilfs_btree_propagate_p()
1905 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_propagate_p()
1912 int level, struct inode *dat) in nilfs_btree_prepare_update_v() argument
1917 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_prepare_update_v()
1918 path[level].bp_oldreq.bpr_ptr = in nilfs_btree_prepare_update_v()
1919 nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, in nilfs_btree_prepare_update_v()
1921 path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1; in nilfs_btree_prepare_update_v()
1922 ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req, in nilfs_btree_prepare_update_v()
1923 &path[level].bp_newreq.bpr_req); in nilfs_btree_prepare_update_v()
1927 if (buffer_nilfs_node(path[level].bp_bh)) { in nilfs_btree_prepare_update_v()
1928 path[level].bp_ctxt.oldkey = path[level].bp_oldreq.bpr_ptr; in nilfs_btree_prepare_update_v()
1929 path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr; in nilfs_btree_prepare_update_v()
1930 path[level].bp_ctxt.bh = path[level].bp_bh; in nilfs_btree_prepare_update_v()
1933 &path[level].bp_ctxt); in nilfs_btree_prepare_update_v()
1936 &path[level].bp_oldreq.bpr_req, in nilfs_btree_prepare_update_v()
1937 &path[level].bp_newreq.bpr_req); in nilfs_btree_prepare_update_v()
1947 int level, struct inode *dat) in nilfs_btree_commit_update_v() argument
1952 nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req, in nilfs_btree_commit_update_v()
1953 &path[level].bp_newreq.bpr_req, in nilfs_btree_commit_update_v()
1956 if (buffer_nilfs_node(path[level].bp_bh)) { in nilfs_btree_commit_update_v()
1959 &path[level].bp_ctxt); in nilfs_btree_commit_update_v()
1960 path[level].bp_bh = path[level].bp_ctxt.bh; in nilfs_btree_commit_update_v()
1962 set_buffer_nilfs_volatile(path[level].bp_bh); in nilfs_btree_commit_update_v()
1964 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_commit_update_v()
1965 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, in nilfs_btree_commit_update_v()
1966 path[level].bp_newreq.bpr_ptr, ncmax); in nilfs_btree_commit_update_v()
1971 int level, struct inode *dat) in nilfs_btree_abort_update_v() argument
1973 nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req, in nilfs_btree_abort_update_v()
1974 &path[level].bp_newreq.bpr_req); in nilfs_btree_abort_update_v()
1975 if (buffer_nilfs_node(path[level].bp_bh)) in nilfs_btree_abort_update_v()
1978 &path[level].bp_ctxt); in nilfs_btree_abort_update_v()
1986 int level, ret; in nilfs_btree_prepare_propagate_v() local
1988 level = minlevel; in nilfs_btree_prepare_propagate_v()
1989 if (!buffer_nilfs_volatile(path[level].bp_bh)) { in nilfs_btree_prepare_propagate_v()
1990 ret = nilfs_btree_prepare_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
1994 while ((++level < nilfs_btree_height(btree) - 1) && in nilfs_btree_prepare_propagate_v()
1995 !buffer_dirty(path[level].bp_bh)) { in nilfs_btree_prepare_propagate_v()
1997 WARN_ON(buffer_nilfs_volatile(path[level].bp_bh)); in nilfs_btree_prepare_propagate_v()
1998 ret = nilfs_btree_prepare_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
2004 *maxlevelp = level - 1; in nilfs_btree_prepare_propagate_v()
2009 while (--level > minlevel) in nilfs_btree_prepare_propagate_v()
2010 nilfs_btree_abort_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
2011 if (!buffer_nilfs_volatile(path[level].bp_bh)) in nilfs_btree_prepare_propagate_v()
2012 nilfs_btree_abort_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
2022 int level; in nilfs_btree_commit_propagate_v() local
2027 for (level = minlevel + 1; level <= maxlevel; level++) in nilfs_btree_commit_propagate_v()
2028 nilfs_btree_commit_update_v(btree, path, level, dat); in nilfs_btree_commit_propagate_v()
2033 int level, struct buffer_head *bh) in nilfs_btree_propagate_v() argument
2042 path[level].bp_bh = bh; in nilfs_btree_propagate_v()
2043 ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel, in nilfs_btree_propagate_v()
2048 if (buffer_nilfs_volatile(path[level].bp_bh)) { in nilfs_btree_propagate_v()
2049 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_propagate_v()
2051 path[level + 1].bp_index, in nilfs_btree_propagate_v()
2058 nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat); in nilfs_btree_propagate_v()
2061 brelse(path[level].bp_bh); in nilfs_btree_propagate_v()
2062 path[level].bp_bh = NULL; in nilfs_btree_propagate_v()
2072 int level, ret; in nilfs_btree_propagate() local
2083 level = nilfs_btree_node_get_level(node); in nilfs_btree_propagate()
2086 level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_propagate()
2089 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0); in nilfs_btree_propagate()
2093 "writing node/leaf block does not appear in b-tree (ino=%lu) at key=%llu, level=%d", in nilfs_btree_propagate()
2095 (unsigned long long)key, level); in nilfs_btree_propagate()
2100 nilfs_btree_propagate_v(btree, path, level, bh) : in nilfs_btree_propagate()
2101 nilfs_btree_propagate_p(btree, path, level, bh); in nilfs_btree_propagate()
2123 int level; in nilfs_btree_add_dirty_buffer() local
2128 level = nilfs_btree_node_get_level(node); in nilfs_btree_add_dirty_buffer()
2129 if (level < NILFS_BTREE_LEVEL_NODE_MIN || in nilfs_btree_add_dirty_buffer()
2130 level >= NILFS_BTREE_LEVEL_MAX) { in nilfs_btree_add_dirty_buffer()
2133 "invalid btree level: %d (key=%llu, ino=%lu, blocknr=%llu)", in nilfs_btree_add_dirty_buffer()
2134 level, (unsigned long long)key, in nilfs_btree_add_dirty_buffer()
2140 list_for_each(head, &lists[level]) { in nilfs_btree_add_dirty_buffer()
2159 int level, i; in nilfs_btree_lookup_dirty_buffers() local
2161 for (level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_lookup_dirty_buffers()
2162 level < NILFS_BTREE_LEVEL_MAX; in nilfs_btree_lookup_dirty_buffers()
2163 level++) in nilfs_btree_lookup_dirty_buffers()
2164 INIT_LIST_HEAD(&lists[level]); in nilfs_btree_lookup_dirty_buffers()
2182 for (level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_lookup_dirty_buffers()
2183 level < NILFS_BTREE_LEVEL_MAX; in nilfs_btree_lookup_dirty_buffers()
2184 level++) in nilfs_btree_lookup_dirty_buffers()
2185 list_splice_tail(&lists[level], listp); in nilfs_btree_lookup_dirty_buffers()
2190 int level, in nilfs_btree_assign_p() argument
2200 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_assign_p()
2201 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, in nilfs_btree_assign_p()
2204 path[level].bp_ctxt.oldkey = ptr; in nilfs_btree_assign_p()
2205 path[level].bp_ctxt.newkey = blocknr; in nilfs_btree_assign_p()
2206 path[level].bp_ctxt.bh = *bh; in nilfs_btree_assign_p()
2209 &path[level].bp_ctxt); in nilfs_btree_assign_p()
2214 &path[level].bp_ctxt); in nilfs_btree_assign_p()
2215 *bh = path[level].bp_ctxt.bh; in nilfs_btree_assign_p()
2218 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr, in nilfs_btree_assign_p()
2221 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); in nilfs_btree_assign_p()
2224 binfo->bi_dat.bi_level = level; in nilfs_btree_assign_p()
2231 int level, in nilfs_btree_assign_v() argument
2243 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_assign_v()
2244 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, in nilfs_btree_assign_v()
2252 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); in nilfs_btree_assign_v()
2268 int level, ret; in nilfs_btree_assign() local
2277 level = nilfs_btree_node_get_level(node); in nilfs_btree_assign()
2280 level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_assign()
2283 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0); in nilfs_btree_assign()
2290 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) : in nilfs_btree_assign()
2291 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo); in nilfs_btree_assign()
2326 static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level) in nilfs_btree_mark() argument
2337 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0); in nilfs_btree_mark()