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()
545 int level, index, found, ncmax, ret; in nilfs_btree_do_lookup() local
548 level = nilfs_btree_node_get_level(node); in nilfs_btree_do_lookup()
549 if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0) in nilfs_btree_do_lookup()
555 path[level].bp_bh = NULL; in nilfs_btree_do_lookup()
556 path[level].bp_index = index; in nilfs_btree_do_lookup()
560 while (--level >= minlevel) { in nilfs_btree_do_lookup()
562 if (level == NILFS_BTREE_LEVEL_NODE_MIN && readahead) { in nilfs_btree_do_lookup()
563 p.node = nilfs_btree_get_node(btree, path, level + 1, in nilfs_btree_do_lookup()
569 ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh, in nilfs_btree_do_lookup()
574 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_lookup()
575 if (nilfs_btree_bad_node(btree, node, level)) in nilfs_btree_do_lookup()
584 WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN); in nilfs_btree_do_lookup()
588 path[level].bp_index = index; in nilfs_btree_do_lookup()
605 int index, level, ncmax, ret; in nilfs_btree_do_lookup_last() local
611 level = nilfs_btree_node_get_level(node); in nilfs_btree_do_lookup_last()
614 path[level].bp_bh = NULL; in nilfs_btree_do_lookup_last()
615 path[level].bp_index = index; in nilfs_btree_do_lookup_last()
618 for (level--; level > 0; level--) { in nilfs_btree_do_lookup_last()
619 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh); in nilfs_btree_do_lookup_last()
622 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_lookup_last()
623 if (nilfs_btree_bad_node(btree, node, level)) in nilfs_btree_do_lookup_last()
627 path[level].bp_index = index; in nilfs_btree_do_lookup_last()
642 * @minlevel: start level
654 int index, next_adj, level; in nilfs_btree_get_next_key() local
658 for (level = minlevel; level <= maxlevel; level++) { in nilfs_btree_get_next_key()
659 if (level == maxlevel) in nilfs_btree_get_next_key()
662 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_get_next_key()
664 index = path[level].bp_index + next_adj; in nilfs_btree_get_next_key()
677 __u64 key, int level, __u64 *ptrp) in nilfs_btree_lookup() argument
686 ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0); in nilfs_btree_lookup()
702 int level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_lookup_contig() local
710 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1); in nilfs_btree_lookup_contig()
726 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_lookup_contig()
727 index = path[level].bp_index + 1; in nilfs_btree_lookup_contig()
744 if (level == maxlevel) in nilfs_btree_lookup_contig()
748 p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax); in nilfs_btree_lookup_contig()
749 p.index = path[level + 1].bp_index + 1; in nilfs_btree_lookup_contig()
755 path[level + 1].bp_index = p.index; in nilfs_btree_lookup_contig()
757 brelse(path[level].bp_bh); in nilfs_btree_lookup_contig()
758 path[level].bp_bh = NULL; in nilfs_btree_lookup_contig()
760 ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh, in nilfs_btree_lookup_contig()
764 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_lookup_contig()
767 path[level].bp_index = index; in nilfs_btree_lookup_contig()
779 int level, __u64 key) in nilfs_btree_promote_key() argument
781 if (level < nilfs_btree_height(btree) - 1) { in nilfs_btree_promote_key()
784 nilfs_btree_get_nonroot_node(path, level), in nilfs_btree_promote_key()
785 path[level].bp_index, key); in nilfs_btree_promote_key()
786 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_promote_key()
787 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_promote_key()
788 } while ((path[level].bp_index == 0) && in nilfs_btree_promote_key()
789 (++level < nilfs_btree_height(btree) - 1)); in nilfs_btree_promote_key()
793 if (level == nilfs_btree_height(btree) - 1) { in nilfs_btree_promote_key()
795 path[level].bp_index, key); in nilfs_btree_promote_key()
801 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_do_insert() argument
806 if (level < nilfs_btree_height(btree) - 1) { in nilfs_btree_do_insert()
807 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_insert()
809 nilfs_btree_node_insert(node, path[level].bp_index, in nilfs_btree_do_insert()
811 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_do_insert()
812 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_do_insert()
814 if (path[level].bp_index == 0) in nilfs_btree_do_insert()
815 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_do_insert()
820 nilfs_btree_node_insert(node, path[level].bp_index, in nilfs_btree_do_insert()
828 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_carry_left() argument
833 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_carry_left()
834 left = nilfs_btree_get_sib_node(path, level); in nilfs_btree_carry_left()
841 if (n > path[level].bp_index) { in nilfs_btree_carry_left()
849 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_carry_left()
850 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_carry_left()
851 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_carry_left()
852 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_carry_left()
854 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_carry_left()
858 brelse(path[level].bp_bh); in nilfs_btree_carry_left()
859 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_carry_left()
860 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_left()
861 path[level].bp_index += lnchildren; in nilfs_btree_carry_left()
862 path[level + 1].bp_index--; in nilfs_btree_carry_left()
864 brelse(path[level].bp_sib_bh); in nilfs_btree_carry_left()
865 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_left()
866 path[level].bp_index -= n; in nilfs_btree_carry_left()
869 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_carry_left()
874 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_carry_right() argument
879 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_carry_right()
880 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_carry_right()
887 if (n > nchildren - path[level].bp_index) { in nilfs_btree_carry_right()
895 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_carry_right()
896 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_carry_right()
897 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_carry_right()
898 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_carry_right()
900 path[level + 1].bp_index++; in nilfs_btree_carry_right()
901 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_carry_right()
903 path[level + 1].bp_index--; in nilfs_btree_carry_right()
906 brelse(path[level].bp_bh); in nilfs_btree_carry_right()
907 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_carry_right()
908 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_right()
909 path[level].bp_index -= nilfs_btree_node_get_nchildren(node); in nilfs_btree_carry_right()
910 path[level + 1].bp_index++; in nilfs_btree_carry_right()
912 brelse(path[level].bp_sib_bh); in nilfs_btree_carry_right()
913 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_right()
916 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_carry_right()
921 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_split() argument
926 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_split()
927 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_split()
933 if (n > nchildren - path[level].bp_index) { in nilfs_btree_split()
940 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_split()
941 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_split()
942 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_split()
943 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_split()
946 path[level].bp_index -= nilfs_btree_node_get_nchildren(node); in nilfs_btree_split()
947 nilfs_btree_node_insert(right, path[level].bp_index, in nilfs_btree_split()
951 *ptrp = path[level].bp_newreq.bpr_ptr; in nilfs_btree_split()
953 brelse(path[level].bp_bh); in nilfs_btree_split()
954 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_split()
955 path[level].bp_sib_bh = NULL; in nilfs_btree_split()
957 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_split()
960 *ptrp = path[level].bp_newreq.bpr_ptr; in nilfs_btree_split()
962 brelse(path[level].bp_sib_bh); in nilfs_btree_split()
963 path[level].bp_sib_bh = NULL; in nilfs_btree_split()
966 path[level + 1].bp_index++; in nilfs_btree_split()
971 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_grow() argument
977 child = nilfs_btree_get_sib_node(path, level); in nilfs_btree_grow()
984 nilfs_btree_node_set_level(root, level + 1); in nilfs_btree_grow()
986 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_grow()
987 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_grow()
989 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_grow()
990 path[level].bp_sib_bh = NULL; in nilfs_btree_grow()
992 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_grow()
995 *ptrp = path[level].bp_newreq.bpr_ptr; in nilfs_btree_grow()
1002 int level, ncmax; in nilfs_btree_find_near() local
1008 level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_find_near()
1009 if (path[level].bp_index > 0) { in nilfs_btree_find_near()
1010 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_find_near()
1012 path[level].bp_index - 1, in nilfs_btree_find_near()
1017 level = NILFS_BTREE_LEVEL_NODE_MIN + 1; in nilfs_btree_find_near()
1018 if (level <= nilfs_btree_height(btree) - 1) { in nilfs_btree_find_near()
1019 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_find_near()
1020 return nilfs_btree_node_get_ptr(node, path[level].bp_index, in nilfs_btree_find_near()
1055 int pindex, level, ncmax, ncblk, ret; in nilfs_btree_prepare_insert() local
1059 level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_prepare_insert()
1063 path[level].bp_newreq.bpr_ptr = in nilfs_btree_prepare_insert()
1068 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1074 for (level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_prepare_insert()
1075 level < nilfs_btree_height(btree) - 1; in nilfs_btree_prepare_insert()
1076 level++) { in nilfs_btree_prepare_insert()
1077 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_prepare_insert()
1079 path[level].bp_op = nilfs_btree_do_insert; in nilfs_btree_prepare_insert()
1084 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_prepare_insert()
1085 pindex = path[level + 1].bp_index; in nilfs_btree_prepare_insert()
1096 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1097 path[level].bp_op = nilfs_btree_carry_left; in nilfs_btree_prepare_insert()
1114 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1115 path[level].bp_op = nilfs_btree_carry_right; in nilfs_btree_prepare_insert()
1124 path[level].bp_newreq.bpr_ptr = in nilfs_btree_prepare_insert()
1125 path[level - 1].bp_newreq.bpr_ptr + 1; in nilfs_btree_prepare_insert()
1127 &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1131 path[level].bp_newreq.bpr_ptr, in nilfs_btree_prepare_insert()
1139 nilfs_btree_node_init(sib, 0, level, 0, ncblk, NULL, NULL); in nilfs_btree_prepare_insert()
1140 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1141 path[level].bp_op = nilfs_btree_split; in nilfs_btree_prepare_insert()
1148 path[level].bp_op = nilfs_btree_do_insert; in nilfs_btree_prepare_insert()
1154 path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1; in nilfs_btree_prepare_insert()
1155 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1158 ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr, in nilfs_btree_prepare_insert()
1164 0, level, 0, ncblk, NULL, NULL); in nilfs_btree_prepare_insert()
1165 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1166 path[level].bp_op = nilfs_btree_grow; in nilfs_btree_prepare_insert()
1168 level++; in nilfs_btree_prepare_insert()
1169 path[level].bp_op = nilfs_btree_do_insert; in nilfs_btree_prepare_insert()
1176 *levelp = level; in nilfs_btree_prepare_insert()
1181 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1183 for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) { in nilfs_btree_prepare_insert()
1184 nilfs_btnode_delete(path[level].bp_sib_bh); in nilfs_btree_prepare_insert()
1185 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1189 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1191 *levelp = level; in nilfs_btree_prepare_insert()
1201 int level; in nilfs_btree_commit_insert() local
1210 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { in nilfs_btree_commit_insert()
1212 &path[level - 1].bp_newreq, dat); in nilfs_btree_commit_insert()
1213 path[level].bp_op(btree, path, level, &key, &ptr); in nilfs_btree_commit_insert()
1224 int level, ret; in nilfs_btree_insert() local
1238 ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats); in nilfs_btree_insert()
1241 nilfs_btree_commit_insert(btree, path, level, key, ptr); in nilfs_btree_insert()
1251 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_do_delete() argument
1256 if (level < nilfs_btree_height(btree) - 1) { in nilfs_btree_do_delete()
1257 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_delete()
1259 nilfs_btree_node_delete(node, path[level].bp_index, in nilfs_btree_do_delete()
1261 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_do_delete()
1262 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_do_delete()
1263 if (path[level].bp_index == 0) in nilfs_btree_do_delete()
1264 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_do_delete()
1268 nilfs_btree_node_delete(node, path[level].bp_index, in nilfs_btree_do_delete()
1276 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_borrow_left() argument
1281 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_borrow_left()
1283 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_borrow_left()
1284 left = nilfs_btree_get_sib_node(path, level); in nilfs_btree_borrow_left()
1293 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_borrow_left()
1294 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_borrow_left()
1295 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_borrow_left()
1296 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_borrow_left()
1298 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_borrow_left()
1301 brelse(path[level].bp_sib_bh); in nilfs_btree_borrow_left()
1302 path[level].bp_sib_bh = NULL; in nilfs_btree_borrow_left()
1303 path[level].bp_index += n; in nilfs_btree_borrow_left()
1308 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_borrow_right() argument
1313 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_borrow_right()
1315 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_borrow_right()
1316 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_borrow_right()
1325 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_borrow_right()
1326 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_borrow_right()
1327 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_borrow_right()
1328 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_borrow_right()
1330 path[level + 1].bp_index++; in nilfs_btree_borrow_right()
1331 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_borrow_right()
1333 path[level + 1].bp_index--; in nilfs_btree_borrow_right()
1335 brelse(path[level].bp_sib_bh); in nilfs_btree_borrow_right()
1336 path[level].bp_sib_bh = NULL; in nilfs_btree_borrow_right()
1341 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_concat_left() argument
1346 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_concat_left()
1348 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_concat_left()
1349 left = nilfs_btree_get_sib_node(path, level); in nilfs_btree_concat_left()
1356 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_concat_left()
1357 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_concat_left()
1359 nilfs_btnode_delete(path[level].bp_bh); in nilfs_btree_concat_left()
1360 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_concat_left()
1361 path[level].bp_sib_bh = NULL; in nilfs_btree_concat_left()
1362 path[level].bp_index += nilfs_btree_node_get_nchildren(left); in nilfs_btree_concat_left()
1367 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_concat_right() argument
1372 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_concat_right()
1374 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_concat_right()
1375 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_concat_right()
1382 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_concat_right()
1383 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_concat_right()
1385 nilfs_btnode_delete(path[level].bp_sib_bh); in nilfs_btree_concat_right()
1386 path[level].bp_sib_bh = NULL; in nilfs_btree_concat_right()
1387 path[level + 1].bp_index++; in nilfs_btree_concat_right()
1392 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_shrink() argument
1397 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_shrink()
1400 child = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_shrink()
1405 nilfs_btree_node_set_level(root, level); in nilfs_btree_shrink()
1410 nilfs_btnode_delete(path[level].bp_bh); in nilfs_btree_shrink()
1411 path[level].bp_bh = NULL; in nilfs_btree_shrink()
1416 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_nop() argument
1429 int pindex, dindex, level, ncmin, ncmax, ncblk, ret; in nilfs_btree_prepare_delete() local
1436 for (level = NILFS_BTREE_LEVEL_NODE_MIN, dindex = path[level].bp_index; in nilfs_btree_prepare_delete()
1437 level < nilfs_btree_height(btree) - 1; in nilfs_btree_prepare_delete()
1438 level++) { in nilfs_btree_prepare_delete()
1439 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_prepare_delete()
1440 path[level].bp_oldreq.bpr_ptr = in nilfs_btree_prepare_delete()
1443 &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1448 path[level].bp_op = nilfs_btree_do_delete; in nilfs_btree_prepare_delete()
1453 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_prepare_delete()
1454 pindex = path[level + 1].bp_index; in nilfs_btree_prepare_delete()
1466 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1467 path[level].bp_op = nilfs_btree_borrow_left; in nilfs_btree_prepare_delete()
1471 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1472 path[level].bp_op = nilfs_btree_concat_left; in nilfs_btree_prepare_delete()
1486 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1487 path[level].bp_op = nilfs_btree_borrow_right; in nilfs_btree_prepare_delete()
1491 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1492 path[level].bp_op = nilfs_btree_concat_right; in nilfs_btree_prepare_delete()
1507 WARN_ON(level != nilfs_btree_height(btree) - 2); in nilfs_btree_prepare_delete()
1510 path[level].bp_op = nilfs_btree_shrink; in nilfs_btree_prepare_delete()
1512 level++; in nilfs_btree_prepare_delete()
1513 path[level].bp_op = nilfs_btree_nop; in nilfs_btree_prepare_delete()
1516 path[level].bp_op = nilfs_btree_do_delete; in nilfs_btree_prepare_delete()
1524 path[level].bp_op = nilfs_btree_do_delete; in nilfs_btree_prepare_delete()
1529 path[level].bp_oldreq.bpr_ptr = in nilfs_btree_prepare_delete()
1533 ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1539 *levelp = level; in nilfs_btree_prepare_delete()
1544 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1546 for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) { in nilfs_btree_prepare_delete()
1547 brelse(path[level].bp_sib_bh); in nilfs_btree_prepare_delete()
1548 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1550 *levelp = level; in nilfs_btree_prepare_delete()
1559 int level; in nilfs_btree_commit_delete() local
1561 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { in nilfs_btree_commit_delete()
1562 nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_commit_delete()
1563 path[level].bp_op(btree, path, level, NULL, NULL); in nilfs_btree_commit_delete()
1576 int level, ret; in nilfs_btree_delete() local
1590 ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat); in nilfs_btree_delete()
1593 nilfs_btree_commit_delete(btree, path, level, dat); in nilfs_btree_delete()
1809 /* create child node at level 1 */ in nilfs_btree_commit_convert_and_insert()
1821 /* create root node at level 2 */ in nilfs_btree_commit_convert_and_insert()
1830 /* create root node at level 1 */ in nilfs_btree_commit_convert_and_insert()
1888 int level, in nilfs_btree_propagate_p() argument
1891 while ((++level < nilfs_btree_height(btree) - 1) && in nilfs_btree_propagate_p()
1892 !buffer_dirty(path[level].bp_bh)) in nilfs_btree_propagate_p()
1893 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_propagate_p()
1900 int level, struct inode *dat) in nilfs_btree_prepare_update_v() argument
1905 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_prepare_update_v()
1906 path[level].bp_oldreq.bpr_ptr = in nilfs_btree_prepare_update_v()
1907 nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, in nilfs_btree_prepare_update_v()
1909 path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1; in nilfs_btree_prepare_update_v()
1910 ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req, in nilfs_btree_prepare_update_v()
1911 &path[level].bp_newreq.bpr_req); in nilfs_btree_prepare_update_v()
1915 if (buffer_nilfs_node(path[level].bp_bh)) { in nilfs_btree_prepare_update_v()
1916 path[level].bp_ctxt.oldkey = path[level].bp_oldreq.bpr_ptr; in nilfs_btree_prepare_update_v()
1917 path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr; in nilfs_btree_prepare_update_v()
1918 path[level].bp_ctxt.bh = path[level].bp_bh; in nilfs_btree_prepare_update_v()
1921 &path[level].bp_ctxt); in nilfs_btree_prepare_update_v()
1924 &path[level].bp_oldreq.bpr_req, in nilfs_btree_prepare_update_v()
1925 &path[level].bp_newreq.bpr_req); in nilfs_btree_prepare_update_v()
1935 int level, struct inode *dat) in nilfs_btree_commit_update_v() argument
1940 nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req, in nilfs_btree_commit_update_v()
1941 &path[level].bp_newreq.bpr_req, in nilfs_btree_commit_update_v()
1944 if (buffer_nilfs_node(path[level].bp_bh)) { in nilfs_btree_commit_update_v()
1947 &path[level].bp_ctxt); in nilfs_btree_commit_update_v()
1948 path[level].bp_bh = path[level].bp_ctxt.bh; in nilfs_btree_commit_update_v()
1950 set_buffer_nilfs_volatile(path[level].bp_bh); in nilfs_btree_commit_update_v()
1952 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_commit_update_v()
1953 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, in nilfs_btree_commit_update_v()
1954 path[level].bp_newreq.bpr_ptr, ncmax); in nilfs_btree_commit_update_v()
1959 int level, struct inode *dat) in nilfs_btree_abort_update_v() argument
1961 nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req, in nilfs_btree_abort_update_v()
1962 &path[level].bp_newreq.bpr_req); in nilfs_btree_abort_update_v()
1963 if (buffer_nilfs_node(path[level].bp_bh)) in nilfs_btree_abort_update_v()
1966 &path[level].bp_ctxt); in nilfs_btree_abort_update_v()
1974 int level, ret; in nilfs_btree_prepare_propagate_v() local
1976 level = minlevel; in nilfs_btree_prepare_propagate_v()
1977 if (!buffer_nilfs_volatile(path[level].bp_bh)) { in nilfs_btree_prepare_propagate_v()
1978 ret = nilfs_btree_prepare_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
1982 while ((++level < nilfs_btree_height(btree) - 1) && in nilfs_btree_prepare_propagate_v()
1983 !buffer_dirty(path[level].bp_bh)) { in nilfs_btree_prepare_propagate_v()
1985 WARN_ON(buffer_nilfs_volatile(path[level].bp_bh)); in nilfs_btree_prepare_propagate_v()
1986 ret = nilfs_btree_prepare_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
1992 *maxlevelp = level - 1; in nilfs_btree_prepare_propagate_v()
1997 while (--level > minlevel) in nilfs_btree_prepare_propagate_v()
1998 nilfs_btree_abort_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
1999 if (!buffer_nilfs_volatile(path[level].bp_bh)) in nilfs_btree_prepare_propagate_v()
2000 nilfs_btree_abort_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
2010 int level; in nilfs_btree_commit_propagate_v() local
2015 for (level = minlevel + 1; level <= maxlevel; level++) in nilfs_btree_commit_propagate_v()
2016 nilfs_btree_commit_update_v(btree, path, level, dat); in nilfs_btree_commit_propagate_v()
2021 int level, struct buffer_head *bh) in nilfs_btree_propagate_v() argument
2030 path[level].bp_bh = bh; in nilfs_btree_propagate_v()
2031 ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel, in nilfs_btree_propagate_v()
2036 if (buffer_nilfs_volatile(path[level].bp_bh)) { in nilfs_btree_propagate_v()
2037 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_propagate_v()
2039 path[level + 1].bp_index, in nilfs_btree_propagate_v()
2046 nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat); in nilfs_btree_propagate_v()
2049 brelse(path[level].bp_bh); in nilfs_btree_propagate_v()
2050 path[level].bp_bh = NULL; in nilfs_btree_propagate_v()
2060 int level, ret; in nilfs_btree_propagate() local
2071 level = nilfs_btree_node_get_level(node); in nilfs_btree_propagate()
2074 level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_propagate()
2077 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0); in nilfs_btree_propagate()
2081 "writing node/leaf block does not appear in b-tree (ino=%lu) at key=%llu, level=%d", in nilfs_btree_propagate()
2083 (unsigned long long)key, level); in nilfs_btree_propagate()
2088 nilfs_btree_propagate_v(btree, path, level, bh) : in nilfs_btree_propagate()
2089 nilfs_btree_propagate_p(btree, path, level, bh); in nilfs_btree_propagate()
2111 int level; in nilfs_btree_add_dirty_buffer() local
2116 level = nilfs_btree_node_get_level(node); in nilfs_btree_add_dirty_buffer()
2117 if (level < NILFS_BTREE_LEVEL_NODE_MIN || in nilfs_btree_add_dirty_buffer()
2118 level >= NILFS_BTREE_LEVEL_MAX) { in nilfs_btree_add_dirty_buffer()
2121 "invalid btree level: %d (key=%llu, ino=%lu, blocknr=%llu)", in nilfs_btree_add_dirty_buffer()
2122 level, (unsigned long long)key, in nilfs_btree_add_dirty_buffer()
2128 list_for_each(head, &lists[level]) { in nilfs_btree_add_dirty_buffer()
2147 int level, i; in nilfs_btree_lookup_dirty_buffers() local
2149 for (level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_lookup_dirty_buffers()
2150 level < NILFS_BTREE_LEVEL_MAX; in nilfs_btree_lookup_dirty_buffers()
2151 level++) in nilfs_btree_lookup_dirty_buffers()
2152 INIT_LIST_HEAD(&lists[level]); in nilfs_btree_lookup_dirty_buffers()
2170 for (level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_lookup_dirty_buffers()
2171 level < NILFS_BTREE_LEVEL_MAX; in nilfs_btree_lookup_dirty_buffers()
2172 level++) in nilfs_btree_lookup_dirty_buffers()
2173 list_splice_tail(&lists[level], listp); in nilfs_btree_lookup_dirty_buffers()
2178 int level, in nilfs_btree_assign_p() argument
2188 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_assign_p()
2189 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, in nilfs_btree_assign_p()
2192 path[level].bp_ctxt.oldkey = ptr; in nilfs_btree_assign_p()
2193 path[level].bp_ctxt.newkey = blocknr; in nilfs_btree_assign_p()
2194 path[level].bp_ctxt.bh = *bh; in nilfs_btree_assign_p()
2197 &path[level].bp_ctxt); in nilfs_btree_assign_p()
2202 &path[level].bp_ctxt); in nilfs_btree_assign_p()
2203 *bh = path[level].bp_ctxt.bh; in nilfs_btree_assign_p()
2206 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr, in nilfs_btree_assign_p()
2209 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); in nilfs_btree_assign_p()
2212 binfo->bi_dat.bi_level = level; in nilfs_btree_assign_p()
2219 int level, in nilfs_btree_assign_v() argument
2231 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_assign_v()
2232 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, in nilfs_btree_assign_v()
2240 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); in nilfs_btree_assign_v()
2256 int level, ret; in nilfs_btree_assign() local
2265 level = nilfs_btree_node_get_level(node); in nilfs_btree_assign()
2268 level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_assign()
2271 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0); in nilfs_btree_assign()
2278 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) : in nilfs_btree_assign()
2279 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo); in nilfs_btree_assign()
2314 static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level) in nilfs_btree_mark() argument
2325 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0); in nilfs_btree_mark()