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()
95 nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level) in nilfs_btree_node_set_level() argument
97 node->bn_level = level; in nilfs_btree_node_set_level()
162 int level, int nchildren, int ncmax, in nilfs_btree_node_init() argument
170 nilfs_btree_node_set_level(node, level); in nilfs_btree_node_init()
342 int level, flags, nchildren; in nilfs_btree_node_broken() local
345 level = nilfs_btree_node_get_level(node); in nilfs_btree_node_broken()
349 if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN || in nilfs_btree_node_broken()
350 level >= NILFS_BTREE_LEVEL_MAX || in nilfs_btree_node_broken()
355 "bad btree node (ino=%lu, blocknr=%llu): level = %d, flags = 0x%x, nchildren = %d", in nilfs_btree_node_broken()
356 inode->i_ino, (unsigned long long)blocknr, level, in nilfs_btree_node_broken()
373 int level, flags, nchildren; in nilfs_btree_root_broken() local
376 level = nilfs_btree_node_get_level(node); in nilfs_btree_root_broken()
380 if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN || in nilfs_btree_root_broken()
381 level >= NILFS_BTREE_LEVEL_MAX || in nilfs_btree_root_broken()
385 "bad btree root (ino=%lu): level = %d, flags = 0x%x, nchildren = %d", in nilfs_btree_root_broken()
386 inode->i_ino, level, flags, nchildren); in nilfs_btree_root_broken()
415 nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level) in nilfs_btree_get_nonroot_node() argument
417 return (struct nilfs_btree_node *)path[level].bp_bh->b_data; in nilfs_btree_get_nonroot_node()
421 nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level) in nilfs_btree_get_sib_node() argument
423 return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data; in nilfs_btree_get_sib_node()
434 int level, int *ncmaxp) in nilfs_btree_get_node() argument
438 if (level == nilfs_btree_height(btree) - 1) { in nilfs_btree_get_node()
442 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_get_node()
449 struct nilfs_btree_node *node, int level) in nilfs_btree_bad_node() argument
451 if (unlikely(nilfs_btree_node_get_level(node) != level)) { in nilfs_btree_bad_node()
454 "btree level mismatch (ino=%lu): %d != %d", in nilfs_btree_bad_node()
456 nilfs_btree_node_get_level(node), level); in nilfs_btree_bad_node()
543 int level, index, found, ncmax, ret; in nilfs_btree_do_lookup() local
546 level = nilfs_btree_node_get_level(node); in nilfs_btree_do_lookup()
547 if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0) in nilfs_btree_do_lookup()
553 path[level].bp_bh = NULL; in nilfs_btree_do_lookup()
554 path[level].bp_index = index; in nilfs_btree_do_lookup()
558 while (--level >= minlevel) { in nilfs_btree_do_lookup()
560 if (level == NILFS_BTREE_LEVEL_NODE_MIN && readahead) { in nilfs_btree_do_lookup()
561 p.node = nilfs_btree_get_node(btree, path, level + 1, in nilfs_btree_do_lookup()
567 ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh, in nilfs_btree_do_lookup()
572 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_lookup()
573 if (nilfs_btree_bad_node(btree, node, level)) in nilfs_btree_do_lookup()
582 WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN); in nilfs_btree_do_lookup()
586 path[level].bp_index = index; in nilfs_btree_do_lookup()
603 int index, level, ncmax, ret; in nilfs_btree_do_lookup_last() local
609 level = nilfs_btree_node_get_level(node); in nilfs_btree_do_lookup_last()
612 path[level].bp_bh = NULL; in nilfs_btree_do_lookup_last()
613 path[level].bp_index = index; in nilfs_btree_do_lookup_last()
616 for (level--; level > 0; level--) { in nilfs_btree_do_lookup_last()
617 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh); in nilfs_btree_do_lookup_last()
620 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_lookup_last()
621 if (nilfs_btree_bad_node(btree, node, level)) in nilfs_btree_do_lookup_last()
625 path[level].bp_index = index; in nilfs_btree_do_lookup_last()
640 * @minlevel: start level
652 int index, next_adj, level; in nilfs_btree_get_next_key() local
656 for (level = minlevel; level <= maxlevel; level++) { in nilfs_btree_get_next_key()
657 if (level == maxlevel) in nilfs_btree_get_next_key()
660 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_get_next_key()
662 index = path[level].bp_index + next_adj; in nilfs_btree_get_next_key()
675 __u64 key, int level, __u64 *ptrp) in nilfs_btree_lookup() argument
684 ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0); in nilfs_btree_lookup()
700 int level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_lookup_contig() local
708 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1); in nilfs_btree_lookup_contig()
724 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_lookup_contig()
725 index = path[level].bp_index + 1; in nilfs_btree_lookup_contig()
743 if (level == maxlevel) in nilfs_btree_lookup_contig()
747 p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax); in nilfs_btree_lookup_contig()
748 p.index = path[level + 1].bp_index + 1; in nilfs_btree_lookup_contig()
754 path[level + 1].bp_index = p.index; in nilfs_btree_lookup_contig()
756 brelse(path[level].bp_bh); in nilfs_btree_lookup_contig()
757 path[level].bp_bh = NULL; in nilfs_btree_lookup_contig()
759 ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh, in nilfs_btree_lookup_contig()
763 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_lookup_contig()
766 path[level].bp_index = index; in nilfs_btree_lookup_contig()
778 int level, __u64 key) in nilfs_btree_promote_key() argument
780 if (level < nilfs_btree_height(btree) - 1) { in nilfs_btree_promote_key()
783 nilfs_btree_get_nonroot_node(path, level), in nilfs_btree_promote_key()
784 path[level].bp_index, key); in nilfs_btree_promote_key()
785 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_promote_key()
786 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_promote_key()
787 } while ((path[level].bp_index == 0) && in nilfs_btree_promote_key()
788 (++level < nilfs_btree_height(btree) - 1)); in nilfs_btree_promote_key()
792 if (level == nilfs_btree_height(btree) - 1) { in nilfs_btree_promote_key()
794 path[level].bp_index, key); in nilfs_btree_promote_key()
800 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_do_insert() argument
805 if (level < nilfs_btree_height(btree) - 1) { in nilfs_btree_do_insert()
806 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_insert()
808 nilfs_btree_node_insert(node, path[level].bp_index, in nilfs_btree_do_insert()
810 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_do_insert()
811 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_do_insert()
813 if (path[level].bp_index == 0) in nilfs_btree_do_insert()
814 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_do_insert()
819 nilfs_btree_node_insert(node, path[level].bp_index, in nilfs_btree_do_insert()
827 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_carry_left() argument
832 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_carry_left()
833 left = nilfs_btree_get_sib_node(path, level); in nilfs_btree_carry_left()
840 if (n > path[level].bp_index) { in nilfs_btree_carry_left()
848 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_carry_left()
849 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_carry_left()
850 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_carry_left()
851 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_carry_left()
853 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_carry_left()
857 brelse(path[level].bp_bh); in nilfs_btree_carry_left()
858 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_carry_left()
859 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_left()
860 path[level].bp_index += lnchildren; in nilfs_btree_carry_left()
861 path[level + 1].bp_index--; in nilfs_btree_carry_left()
863 brelse(path[level].bp_sib_bh); in nilfs_btree_carry_left()
864 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_left()
865 path[level].bp_index -= n; in nilfs_btree_carry_left()
868 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_carry_left()
873 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_carry_right() argument
878 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_carry_right()
879 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_carry_right()
886 if (n > nchildren - path[level].bp_index) { in nilfs_btree_carry_right()
894 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_carry_right()
895 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_carry_right()
896 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_carry_right()
897 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_carry_right()
899 path[level + 1].bp_index++; in nilfs_btree_carry_right()
900 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_carry_right()
902 path[level + 1].bp_index--; in nilfs_btree_carry_right()
905 brelse(path[level].bp_bh); in nilfs_btree_carry_right()
906 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_carry_right()
907 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_right()
908 path[level].bp_index -= nilfs_btree_node_get_nchildren(node); in nilfs_btree_carry_right()
909 path[level + 1].bp_index++; in nilfs_btree_carry_right()
911 brelse(path[level].bp_sib_bh); in nilfs_btree_carry_right()
912 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_right()
915 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_carry_right()
920 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_split() argument
925 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_split()
926 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_split()
932 if (n > nchildren - path[level].bp_index) { in nilfs_btree_split()
939 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_split()
940 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_split()
941 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_split()
942 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_split()
945 path[level].bp_index -= nilfs_btree_node_get_nchildren(node); in nilfs_btree_split()
946 nilfs_btree_node_insert(right, path[level].bp_index, in nilfs_btree_split()
950 *ptrp = path[level].bp_newreq.bpr_ptr; in nilfs_btree_split()
952 brelse(path[level].bp_bh); in nilfs_btree_split()
953 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_split()
954 path[level].bp_sib_bh = NULL; in nilfs_btree_split()
956 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_split()
959 *ptrp = path[level].bp_newreq.bpr_ptr; in nilfs_btree_split()
961 brelse(path[level].bp_sib_bh); in nilfs_btree_split()
962 path[level].bp_sib_bh = NULL; in nilfs_btree_split()
965 path[level + 1].bp_index++; in nilfs_btree_split()
970 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_grow() argument
976 child = nilfs_btree_get_sib_node(path, level); in nilfs_btree_grow()
983 nilfs_btree_node_set_level(root, level + 1); in nilfs_btree_grow()
985 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_grow()
986 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_grow()
988 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_grow()
989 path[level].bp_sib_bh = NULL; in nilfs_btree_grow()
991 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_grow()
994 *ptrp = path[level].bp_newreq.bpr_ptr; in nilfs_btree_grow()
1001 int level, ncmax; in nilfs_btree_find_near() local
1007 level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_find_near()
1008 if (path[level].bp_index > 0) { in nilfs_btree_find_near()
1009 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_find_near()
1011 path[level].bp_index - 1, in nilfs_btree_find_near()
1016 level = NILFS_BTREE_LEVEL_NODE_MIN + 1; in nilfs_btree_find_near()
1017 if (level <= nilfs_btree_height(btree) - 1) { in nilfs_btree_find_near()
1018 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_find_near()
1019 return nilfs_btree_node_get_ptr(node, path[level].bp_index, in nilfs_btree_find_near()
1054 int pindex, level, ncmax, ncblk, ret; in nilfs_btree_prepare_insert() local
1058 level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_prepare_insert()
1062 path[level].bp_newreq.bpr_ptr = in nilfs_btree_prepare_insert()
1067 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1073 for (level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_prepare_insert()
1074 level < nilfs_btree_height(btree) - 1; in nilfs_btree_prepare_insert()
1075 level++) { in nilfs_btree_prepare_insert()
1076 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_prepare_insert()
1078 path[level].bp_op = nilfs_btree_do_insert; in nilfs_btree_prepare_insert()
1083 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_prepare_insert()
1084 pindex = path[level + 1].bp_index; in nilfs_btree_prepare_insert()
1095 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1096 path[level].bp_op = nilfs_btree_carry_left; in nilfs_btree_prepare_insert()
1113 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1114 path[level].bp_op = nilfs_btree_carry_right; in nilfs_btree_prepare_insert()
1123 path[level].bp_newreq.bpr_ptr = in nilfs_btree_prepare_insert()
1124 path[level - 1].bp_newreq.bpr_ptr + 1; in nilfs_btree_prepare_insert()
1126 &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1130 path[level].bp_newreq.bpr_ptr, in nilfs_btree_prepare_insert()
1138 nilfs_btree_node_init(sib, 0, level, 0, ncblk, NULL, NULL); in nilfs_btree_prepare_insert()
1139 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1140 path[level].bp_op = nilfs_btree_split; in nilfs_btree_prepare_insert()
1147 path[level].bp_op = nilfs_btree_do_insert; in nilfs_btree_prepare_insert()
1153 path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1; in nilfs_btree_prepare_insert()
1154 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1157 ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr, in nilfs_btree_prepare_insert()
1163 0, level, 0, ncblk, NULL, NULL); in nilfs_btree_prepare_insert()
1164 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1165 path[level].bp_op = nilfs_btree_grow; in nilfs_btree_prepare_insert()
1167 level++; in nilfs_btree_prepare_insert()
1168 path[level].bp_op = nilfs_btree_do_insert; in nilfs_btree_prepare_insert()
1175 *levelp = level; in nilfs_btree_prepare_insert()
1180 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1182 for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) { in nilfs_btree_prepare_insert()
1183 nilfs_btnode_delete(path[level].bp_sib_bh); in nilfs_btree_prepare_insert()
1184 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1188 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1190 *levelp = level; in nilfs_btree_prepare_insert()
1200 int level; in nilfs_btree_commit_insert() local
1209 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { in nilfs_btree_commit_insert()
1211 &path[level - 1].bp_newreq, dat); in nilfs_btree_commit_insert()
1212 path[level].bp_op(btree, path, level, &key, &ptr); in nilfs_btree_commit_insert()
1223 int level, ret; in nilfs_btree_insert() local
1237 ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats); in nilfs_btree_insert()
1240 nilfs_btree_commit_insert(btree, path, level, key, ptr); in nilfs_btree_insert()
1250 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_do_delete() argument
1255 if (level < nilfs_btree_height(btree) - 1) { in nilfs_btree_do_delete()
1256 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_delete()
1258 nilfs_btree_node_delete(node, path[level].bp_index, in nilfs_btree_do_delete()
1260 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_do_delete()
1261 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_do_delete()
1262 if (path[level].bp_index == 0) in nilfs_btree_do_delete()
1263 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_do_delete()
1267 nilfs_btree_node_delete(node, path[level].bp_index, in nilfs_btree_do_delete()
1275 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_borrow_left() argument
1280 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_borrow_left()
1282 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_borrow_left()
1283 left = nilfs_btree_get_sib_node(path, level); in nilfs_btree_borrow_left()
1292 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_borrow_left()
1293 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_borrow_left()
1294 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_borrow_left()
1295 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_borrow_left()
1297 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_borrow_left()
1300 brelse(path[level].bp_sib_bh); in nilfs_btree_borrow_left()
1301 path[level].bp_sib_bh = NULL; in nilfs_btree_borrow_left()
1302 path[level].bp_index += n; in nilfs_btree_borrow_left()
1307 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_borrow_right() argument
1312 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_borrow_right()
1314 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_borrow_right()
1315 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_borrow_right()
1324 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_borrow_right()
1325 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_borrow_right()
1326 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_borrow_right()
1327 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_borrow_right()
1329 path[level + 1].bp_index++; in nilfs_btree_borrow_right()
1330 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_borrow_right()
1332 path[level + 1].bp_index--; in nilfs_btree_borrow_right()
1334 brelse(path[level].bp_sib_bh); in nilfs_btree_borrow_right()
1335 path[level].bp_sib_bh = NULL; in nilfs_btree_borrow_right()
1340 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_concat_left() argument
1345 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_concat_left()
1347 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_concat_left()
1348 left = nilfs_btree_get_sib_node(path, level); in nilfs_btree_concat_left()
1355 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_concat_left()
1356 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_concat_left()
1358 nilfs_btnode_delete(path[level].bp_bh); in nilfs_btree_concat_left()
1359 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_concat_left()
1360 path[level].bp_sib_bh = NULL; in nilfs_btree_concat_left()
1361 path[level].bp_index += nilfs_btree_node_get_nchildren(left); in nilfs_btree_concat_left()
1366 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_concat_right() argument
1371 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_concat_right()
1373 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_concat_right()
1374 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_concat_right()
1381 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_concat_right()
1382 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_concat_right()
1384 nilfs_btnode_delete(path[level].bp_sib_bh); in nilfs_btree_concat_right()
1385 path[level].bp_sib_bh = NULL; in nilfs_btree_concat_right()
1386 path[level + 1].bp_index++; in nilfs_btree_concat_right()
1391 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_shrink() argument
1396 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_shrink()
1399 child = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_shrink()
1404 nilfs_btree_node_set_level(root, level); in nilfs_btree_shrink()
1409 nilfs_btnode_delete(path[level].bp_bh); in nilfs_btree_shrink()
1410 path[level].bp_bh = NULL; in nilfs_btree_shrink()
1415 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_nop() argument
1428 int pindex, dindex, level, ncmin, ncmax, ncblk, ret; in nilfs_btree_prepare_delete() local
1435 for (level = NILFS_BTREE_LEVEL_NODE_MIN, dindex = path[level].bp_index; in nilfs_btree_prepare_delete()
1436 level < nilfs_btree_height(btree) - 1; in nilfs_btree_prepare_delete()
1437 level++) { in nilfs_btree_prepare_delete()
1438 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_prepare_delete()
1439 path[level].bp_oldreq.bpr_ptr = in nilfs_btree_prepare_delete()
1442 &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1447 path[level].bp_op = nilfs_btree_do_delete; in nilfs_btree_prepare_delete()
1452 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_prepare_delete()
1453 pindex = path[level + 1].bp_index; in nilfs_btree_prepare_delete()
1465 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1466 path[level].bp_op = nilfs_btree_borrow_left; in nilfs_btree_prepare_delete()
1470 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1471 path[level].bp_op = nilfs_btree_concat_left; in nilfs_btree_prepare_delete()
1485 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1486 path[level].bp_op = nilfs_btree_borrow_right; in nilfs_btree_prepare_delete()
1490 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1491 path[level].bp_op = nilfs_btree_concat_right; in nilfs_btree_prepare_delete()
1506 WARN_ON(level != nilfs_btree_height(btree) - 2); in nilfs_btree_prepare_delete()
1509 path[level].bp_op = nilfs_btree_shrink; in nilfs_btree_prepare_delete()
1511 level++; in nilfs_btree_prepare_delete()
1512 path[level].bp_op = nilfs_btree_nop; in nilfs_btree_prepare_delete()
1515 path[level].bp_op = nilfs_btree_do_delete; in nilfs_btree_prepare_delete()
1523 path[level].bp_op = nilfs_btree_do_delete; in nilfs_btree_prepare_delete()
1528 path[level].bp_oldreq.bpr_ptr = in nilfs_btree_prepare_delete()
1532 ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1538 *levelp = level; in nilfs_btree_prepare_delete()
1543 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1545 for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) { in nilfs_btree_prepare_delete()
1546 brelse(path[level].bp_sib_bh); in nilfs_btree_prepare_delete()
1547 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1549 *levelp = level; in nilfs_btree_prepare_delete()
1558 int level; in nilfs_btree_commit_delete() local
1560 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { in nilfs_btree_commit_delete()
1561 nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_commit_delete()
1562 path[level].bp_op(btree, path, level, NULL, NULL); in nilfs_btree_commit_delete()
1575 int level, ret; in nilfs_btree_delete() local
1589 ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat); in nilfs_btree_delete()
1592 nilfs_btree_commit_delete(btree, path, level, dat); in nilfs_btree_delete()
1806 /* create child node at level 1 */ in nilfs_btree_commit_convert_and_insert()
1818 /* create root node at level 2 */ in nilfs_btree_commit_convert_and_insert()
1827 /* create root node at level 1 */ in nilfs_btree_commit_convert_and_insert()
1885 int level, in nilfs_btree_propagate_p() argument
1888 while ((++level < nilfs_btree_height(btree) - 1) && in nilfs_btree_propagate_p()
1889 !buffer_dirty(path[level].bp_bh)) in nilfs_btree_propagate_p()
1890 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_propagate_p()
1897 int level, struct inode *dat) in nilfs_btree_prepare_update_v() argument
1902 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_prepare_update_v()
1903 path[level].bp_oldreq.bpr_ptr = in nilfs_btree_prepare_update_v()
1904 nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, in nilfs_btree_prepare_update_v()
1906 path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1; in nilfs_btree_prepare_update_v()
1907 ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req, in nilfs_btree_prepare_update_v()
1908 &path[level].bp_newreq.bpr_req); in nilfs_btree_prepare_update_v()
1912 if (buffer_nilfs_node(path[level].bp_bh)) { in nilfs_btree_prepare_update_v()
1913 path[level].bp_ctxt.oldkey = path[level].bp_oldreq.bpr_ptr; in nilfs_btree_prepare_update_v()
1914 path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr; in nilfs_btree_prepare_update_v()
1915 path[level].bp_ctxt.bh = path[level].bp_bh; in nilfs_btree_prepare_update_v()
1918 &path[level].bp_ctxt); in nilfs_btree_prepare_update_v()
1921 &path[level].bp_oldreq.bpr_req, in nilfs_btree_prepare_update_v()
1922 &path[level].bp_newreq.bpr_req); in nilfs_btree_prepare_update_v()
1932 int level, struct inode *dat) in nilfs_btree_commit_update_v() argument
1937 nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req, in nilfs_btree_commit_update_v()
1938 &path[level].bp_newreq.bpr_req, in nilfs_btree_commit_update_v()
1941 if (buffer_nilfs_node(path[level].bp_bh)) { in nilfs_btree_commit_update_v()
1944 &path[level].bp_ctxt); in nilfs_btree_commit_update_v()
1945 path[level].bp_bh = path[level].bp_ctxt.bh; in nilfs_btree_commit_update_v()
1947 set_buffer_nilfs_volatile(path[level].bp_bh); in nilfs_btree_commit_update_v()
1949 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_commit_update_v()
1950 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, in nilfs_btree_commit_update_v()
1951 path[level].bp_newreq.bpr_ptr, ncmax); in nilfs_btree_commit_update_v()
1956 int level, struct inode *dat) in nilfs_btree_abort_update_v() argument
1958 nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req, in nilfs_btree_abort_update_v()
1959 &path[level].bp_newreq.bpr_req); in nilfs_btree_abort_update_v()
1960 if (buffer_nilfs_node(path[level].bp_bh)) in nilfs_btree_abort_update_v()
1963 &path[level].bp_ctxt); in nilfs_btree_abort_update_v()
1971 int level, ret; in nilfs_btree_prepare_propagate_v() local
1973 level = minlevel; in nilfs_btree_prepare_propagate_v()
1974 if (!buffer_nilfs_volatile(path[level].bp_bh)) { in nilfs_btree_prepare_propagate_v()
1975 ret = nilfs_btree_prepare_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
1979 while ((++level < nilfs_btree_height(btree) - 1) && in nilfs_btree_prepare_propagate_v()
1980 !buffer_dirty(path[level].bp_bh)) { in nilfs_btree_prepare_propagate_v()
1982 WARN_ON(buffer_nilfs_volatile(path[level].bp_bh)); in nilfs_btree_prepare_propagate_v()
1983 ret = nilfs_btree_prepare_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
1989 *maxlevelp = level - 1; in nilfs_btree_prepare_propagate_v()
1994 while (--level > minlevel) in nilfs_btree_prepare_propagate_v()
1995 nilfs_btree_abort_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
1996 if (!buffer_nilfs_volatile(path[level].bp_bh)) in nilfs_btree_prepare_propagate_v()
1997 nilfs_btree_abort_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
2007 int level; in nilfs_btree_commit_propagate_v() local
2012 for (level = minlevel + 1; level <= maxlevel; level++) in nilfs_btree_commit_propagate_v()
2013 nilfs_btree_commit_update_v(btree, path, level, dat); in nilfs_btree_commit_propagate_v()
2018 int level, struct buffer_head *bh) in nilfs_btree_propagate_v() argument
2027 path[level].bp_bh = bh; in nilfs_btree_propagate_v()
2028 ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel, in nilfs_btree_propagate_v()
2033 if (buffer_nilfs_volatile(path[level].bp_bh)) { in nilfs_btree_propagate_v()
2034 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_propagate_v()
2036 path[level + 1].bp_index, in nilfs_btree_propagate_v()
2043 nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat); in nilfs_btree_propagate_v()
2046 brelse(path[level].bp_bh); in nilfs_btree_propagate_v()
2047 path[level].bp_bh = NULL; in nilfs_btree_propagate_v()
2057 int level, ret; in nilfs_btree_propagate() local
2068 level = nilfs_btree_node_get_level(node); in nilfs_btree_propagate()
2071 level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_propagate()
2074 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0); in nilfs_btree_propagate()
2078 "writing node/leaf block does not appear in b-tree (ino=%lu) at key=%llu, level=%d", in nilfs_btree_propagate()
2080 (unsigned long long)key, level); in nilfs_btree_propagate()
2085 nilfs_btree_propagate_v(btree, path, level, bh) : in nilfs_btree_propagate()
2086 nilfs_btree_propagate_p(btree, path, level, bh); in nilfs_btree_propagate()
2108 int level; in nilfs_btree_add_dirty_buffer() local
2113 level = nilfs_btree_node_get_level(node); in nilfs_btree_add_dirty_buffer()
2114 if (level < NILFS_BTREE_LEVEL_NODE_MIN || in nilfs_btree_add_dirty_buffer()
2115 level >= NILFS_BTREE_LEVEL_MAX) { in nilfs_btree_add_dirty_buffer()
2118 "invalid btree level: %d (key=%llu, ino=%lu, blocknr=%llu)", in nilfs_btree_add_dirty_buffer()
2119 level, (unsigned long long)key, in nilfs_btree_add_dirty_buffer()
2125 list_for_each(head, &lists[level]) { in nilfs_btree_add_dirty_buffer()
2143 int level, i; in nilfs_btree_lookup_dirty_buffers() local
2145 for (level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_lookup_dirty_buffers()
2146 level < NILFS_BTREE_LEVEL_MAX; in nilfs_btree_lookup_dirty_buffers()
2147 level++) in nilfs_btree_lookup_dirty_buffers()
2148 INIT_LIST_HEAD(&lists[level]); in nilfs_btree_lookup_dirty_buffers()
2166 for (level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_lookup_dirty_buffers()
2167 level < NILFS_BTREE_LEVEL_MAX; in nilfs_btree_lookup_dirty_buffers()
2168 level++) in nilfs_btree_lookup_dirty_buffers()
2169 list_splice_tail(&lists[level], listp); in nilfs_btree_lookup_dirty_buffers()
2174 int level, in nilfs_btree_assign_p() argument
2184 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_assign_p()
2185 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, in nilfs_btree_assign_p()
2188 path[level].bp_ctxt.oldkey = ptr; in nilfs_btree_assign_p()
2189 path[level].bp_ctxt.newkey = blocknr; in nilfs_btree_assign_p()
2190 path[level].bp_ctxt.bh = *bh; in nilfs_btree_assign_p()
2193 &path[level].bp_ctxt); in nilfs_btree_assign_p()
2198 &path[level].bp_ctxt); in nilfs_btree_assign_p()
2199 *bh = path[level].bp_ctxt.bh; in nilfs_btree_assign_p()
2202 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr, in nilfs_btree_assign_p()
2205 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); in nilfs_btree_assign_p()
2208 binfo->bi_dat.bi_level = level; in nilfs_btree_assign_p()
2215 int level, in nilfs_btree_assign_v() argument
2227 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_assign_v()
2228 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, in nilfs_btree_assign_v()
2236 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); in nilfs_btree_assign_v()
2252 int level, ret; in nilfs_btree_assign() local
2261 level = nilfs_btree_node_get_level(node); in nilfs_btree_assign()
2264 level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_assign()
2267 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0); in nilfs_btree_assign()
2274 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) : in nilfs_btree_assign()
2275 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo); in nilfs_btree_assign()
2310 static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level) in nilfs_btree_mark() argument
2321 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0); in nilfs_btree_mark()