Lines Matching refs:path
25 struct nilfs_btree_path *path;
28 path = kmem_cache_alloc(nilfs_btree_path_cache, GFP_NOFS);
29 if (path == NULL)
33 path[level].bp_bh = NULL;
34 path[level].bp_sib_bh = NULL;
35 path[level].bp_index = 0;
36 path[level].bp_oldreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
37 path[level].bp_newreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
38 path[level].bp_op = NULL;
42 return path;
45 static void nilfs_btree_free_path(struct nilfs_btree_path *path)
50 brelse(path[level].bp_bh);
52 kmem_cache_free(nilfs_btree_path_cache, path);
416 nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level)
418 return (struct nilfs_btree_node *)path[level].bp_bh->b_data;
422 nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level)
424 return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data;
434 const struct nilfs_btree_path *path,
443 node = nilfs_btree_get_nonroot_node(path, level);
547 struct nilfs_btree_path *path,
564 path[level].bp_bh = NULL;
565 path[level].bp_index = index;
572 p.node = nilfs_btree_get_node(btree, path, level + 1,
578 ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh,
583 node = nilfs_btree_get_nonroot_node(path, level);
597 path[level].bp_index = index;
609 struct nilfs_btree_path *path,
623 path[level].bp_bh = NULL;
624 path[level].bp_index = index;
628 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh);
631 node = nilfs_btree_get_nonroot_node(path, level);
636 path[level].bp_index = index;
648 * nilfs_btree_get_next_key - get next valid key from btree path array
650 * @path: array of nilfs_btree_path struct
658 const struct nilfs_btree_path *path,
671 node = nilfs_btree_get_nonroot_node(path, level);
673 index = path[level].bp_index + next_adj;
688 struct nilfs_btree_path *path;
691 path = nilfs_btree_alloc_path();
692 if (path == NULL)
695 ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0);
697 nilfs_btree_free_path(path);
706 struct nilfs_btree_path *path;
715 path = nilfs_btree_alloc_path();
716 if (path == NULL)
719 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1);
735 node = nilfs_btree_get_node(btree, path, level, &ncmax);
736 index = path[level].bp_index + 1;
758 p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax);
759 p.index = path[level + 1].bp_index + 1;
765 path[level + 1].bp_index = p.index;
767 brelse(path[level].bp_bh);
768 path[level].bp_bh = NULL;
770 ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh,
774 node = nilfs_btree_get_nonroot_node(path, level);
777 path[level].bp_index = index;
783 nilfs_btree_free_path(path);
788 struct nilfs_btree_path *path,
794 nilfs_btree_get_nonroot_node(path, level),
795 path[level].bp_index, key);
796 if (!buffer_dirty(path[level].bp_bh))
797 mark_buffer_dirty(path[level].bp_bh);
798 } while ((path[level].bp_index == 0) &&
805 path[level].bp_index, key);
810 struct nilfs_btree_path *path,
817 node = nilfs_btree_get_nonroot_node(path, level);
819 nilfs_btree_node_insert(node, path[level].bp_index,
821 if (!buffer_dirty(path[level].bp_bh))
822 mark_buffer_dirty(path[level].bp_bh);
824 if (path[level].bp_index == 0)
825 nilfs_btree_promote_key(btree, path, level + 1,
830 nilfs_btree_node_insert(node, path[level].bp_index,
837 struct nilfs_btree_path *path,
843 node = nilfs_btree_get_nonroot_node(path, level);
844 left = nilfs_btree_get_sib_node(path, level);
851 if (n > path[level].bp_index) {
859 if (!buffer_dirty(path[level].bp_bh))
860 mark_buffer_dirty(path[level].bp_bh);
861 if (!buffer_dirty(path[level].bp_sib_bh))
862 mark_buffer_dirty(path[level].bp_sib_bh);
864 nilfs_btree_promote_key(btree, path, level + 1,
868 brelse(path[level].bp_bh);
869 path[level].bp_bh = path[level].bp_sib_bh;
870 path[level].bp_sib_bh = NULL;
871 path[level].bp_index += lnchildren;
872 path[level + 1].bp_index--;
874 brelse(path[level].bp_sib_bh);
875 path[level].bp_sib_bh = NULL;
876 path[level].bp_index -= n;
879 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
883 struct nilfs_btree_path *path,
889 node = nilfs_btree_get_nonroot_node(path, level);
890 right = nilfs_btree_get_sib_node(path, level);
897 if (n > nchildren - path[level].bp_index) {
905 if (!buffer_dirty(path[level].bp_bh))
906 mark_buffer_dirty(path[level].bp_bh);
907 if (!buffer_dirty(path[level].bp_sib_bh))
908 mark_buffer_dirty(path[level].bp_sib_bh);
910 path[level + 1].bp_index++;
911 nilfs_btree_promote_key(btree, path, level + 1,
913 path[level + 1].bp_index--;
916 brelse(path[level].bp_bh);
917 path[level].bp_bh = path[level].bp_sib_bh;
918 path[level].bp_sib_bh = NULL;
919 path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
920 path[level + 1].bp_index++;
922 brelse(path[level].bp_sib_bh);
923 path[level].bp_sib_bh = NULL;
926 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
930 struct nilfs_btree_path *path,
936 node = nilfs_btree_get_nonroot_node(path, level);
937 right = nilfs_btree_get_sib_node(path, level);
943 if (n > nchildren - path[level].bp_index) {
950 if (!buffer_dirty(path[level].bp_bh))
951 mark_buffer_dirty(path[level].bp_bh);
952 if (!buffer_dirty(path[level].bp_sib_bh))
953 mark_buffer_dirty(path[level].bp_sib_bh);
956 path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
957 nilfs_btree_node_insert(right, path[level].bp_index,
961 *ptrp = path[level].bp_newreq.bpr_ptr;
963 brelse(path[level].bp_bh);
964 path[level].bp_bh = path[level].bp_sib_bh;
965 path[level].bp_sib_bh = NULL;
967 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
970 *ptrp = path[level].bp_newreq.bpr_ptr;
972 brelse(path[level].bp_sib_bh);
973 path[level].bp_sib_bh = NULL;
976 path[level + 1].bp_index++;
980 struct nilfs_btree_path *path,
987 child = nilfs_btree_get_sib_node(path, level);
996 if (!buffer_dirty(path[level].bp_sib_bh))
997 mark_buffer_dirty(path[level].bp_sib_bh);
999 path[level].bp_bh = path[level].bp_sib_bh;
1000 path[level].bp_sib_bh = NULL;
1002 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
1005 *ptrp = path[level].bp_newreq.bpr_ptr;
1009 const struct nilfs_btree_path *path)
1014 if (path == NULL)
1019 if (path[level].bp_index > 0) {
1020 node = nilfs_btree_get_node(btree, path, level, &ncmax);
1022 path[level].bp_index - 1,
1029 node = nilfs_btree_get_node(btree, path, level, &ncmax);
1030 return nilfs_btree_node_get_ptr(node, path[level].bp_index,
1038 const struct nilfs_btree_path *path,
1048 ptr = nilfs_btree_find_near(btree, path);
1058 struct nilfs_btree_path *path,
1073 path[level].bp_newreq.bpr_ptr =
1074 nilfs_btree_find_target_v(btree, path, key);
1078 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1087 node = nilfs_btree_get_nonroot_node(path, level);
1089 path[level].bp_op = nilfs_btree_do_insert;
1094 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1095 pindex = path[level + 1].bp_index;
1106 path[level].bp_sib_bh = bh;
1107 path[level].bp_op = nilfs_btree_carry_left;
1124 path[level].bp_sib_bh = bh;
1125 path[level].bp_op = nilfs_btree_carry_right;
1134 path[level].bp_newreq.bpr_ptr =
1135 path[level - 1].bp_newreq.bpr_ptr + 1;
1137 &path[level].bp_newreq, dat);
1141 path[level].bp_newreq.bpr_ptr,
1150 path[level].bp_sib_bh = bh;
1151 path[level].bp_op = nilfs_btree_split;
1158 path[level].bp_op = nilfs_btree_do_insert;
1164 path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1;
1165 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1168 ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr,
1175 path[level].bp_sib_bh = bh;
1176 path[level].bp_op = nilfs_btree_grow;
1179 path[level].bp_op = nilfs_btree_do_insert;
1191 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1194 nilfs_btnode_delete(path[level].bp_sib_bh);
1195 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1199 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1207 struct nilfs_btree_path *path,
1214 ptr = path[NILFS_BTREE_LEVEL_DATA].bp_newreq.bpr_ptr;
1222 &path[level - 1].bp_newreq, dat);
1223 path[level].bp_op(btree, path, level, &key, &ptr);
1232 struct nilfs_btree_path *path;
1236 path = nilfs_btree_alloc_path();
1237 if (path == NULL)
1240 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1248 ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats);
1251 nilfs_btree_commit_insert(btree, path, level, key, ptr);
1255 nilfs_btree_free_path(path);
1260 struct nilfs_btree_path *path,
1267 node = nilfs_btree_get_nonroot_node(path, level);
1269 nilfs_btree_node_delete(node, path[level].bp_index,
1271 if (!buffer_dirty(path[level].bp_bh))
1272 mark_buffer_dirty(path[level].bp_bh);
1273 if (path[level].bp_index == 0)
1274 nilfs_btree_promote_key(btree, path, level + 1,
1278 nilfs_btree_node_delete(node, path[level].bp_index,
1285 struct nilfs_btree_path *path,
1291 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1293 node = nilfs_btree_get_nonroot_node(path, level);
1294 left = nilfs_btree_get_sib_node(path, level);
1303 if (!buffer_dirty(path[level].bp_bh))
1304 mark_buffer_dirty(path[level].bp_bh);
1305 if (!buffer_dirty(path[level].bp_sib_bh))
1306 mark_buffer_dirty(path[level].bp_sib_bh);
1308 nilfs_btree_promote_key(btree, path, level + 1,
1311 brelse(path[level].bp_sib_bh);
1312 path[level].bp_sib_bh = NULL;
1313 path[level].bp_index += n;
1317 struct nilfs_btree_path *path,
1323 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1325 node = nilfs_btree_get_nonroot_node(path, level);
1326 right = nilfs_btree_get_sib_node(path, level);
1335 if (!buffer_dirty(path[level].bp_bh))
1336 mark_buffer_dirty(path[level].bp_bh);
1337 if (!buffer_dirty(path[level].bp_sib_bh))
1338 mark_buffer_dirty(path[level].bp_sib_bh);
1340 path[level + 1].bp_index++;
1341 nilfs_btree_promote_key(btree, path, level + 1,
1343 path[level + 1].bp_index--;
1345 brelse(path[level].bp_sib_bh);
1346 path[level].bp_sib_bh = NULL;
1350 struct nilfs_btree_path *path,
1356 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1358 node = nilfs_btree_get_nonroot_node(path, level);
1359 left = nilfs_btree_get_sib_node(path, level);
1366 if (!buffer_dirty(path[level].bp_sib_bh))
1367 mark_buffer_dirty(path[level].bp_sib_bh);
1369 nilfs_btnode_delete(path[level].bp_bh);
1370 path[level].bp_bh = path[level].bp_sib_bh;
1371 path[level].bp_sib_bh = NULL;
1372 path[level].bp_index += nilfs_btree_node_get_nchildren(left);
1376 struct nilfs_btree_path *path,
1382 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1384 node = nilfs_btree_get_nonroot_node(path, level);
1385 right = nilfs_btree_get_sib_node(path, level);
1392 if (!buffer_dirty(path[level].bp_bh))
1393 mark_buffer_dirty(path[level].bp_bh);
1395 nilfs_btnode_delete(path[level].bp_sib_bh);
1396 path[level].bp_sib_bh = NULL;
1397 path[level + 1].bp_index++;
1401 struct nilfs_btree_path *path,
1407 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1410 child = nilfs_btree_get_nonroot_node(path, level);
1420 nilfs_btnode_delete(path[level].bp_bh);
1421 path[level].bp_bh = NULL;
1425 struct nilfs_btree_path *path,
1431 struct nilfs_btree_path *path,
1446 for (level = NILFS_BTREE_LEVEL_NODE_MIN, dindex = path[level].bp_index;
1449 node = nilfs_btree_get_nonroot_node(path, level);
1450 path[level].bp_oldreq.bpr_ptr =
1453 &path[level].bp_oldreq, dat);
1458 path[level].bp_op = nilfs_btree_do_delete;
1463 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1464 pindex = path[level + 1].bp_index;
1476 path[level].bp_sib_bh = bh;
1477 path[level].bp_op = nilfs_btree_borrow_left;
1481 path[level].bp_sib_bh = bh;
1482 path[level].bp_op = nilfs_btree_concat_left;
1496 path[level].bp_sib_bh = bh;
1497 path[level].bp_op = nilfs_btree_borrow_right;
1501 path[level].bp_sib_bh = bh;
1502 path[level].bp_op = nilfs_btree_concat_right;
1520 path[level].bp_op = nilfs_btree_shrink;
1523 path[level].bp_op = nilfs_btree_nop;
1526 path[level].bp_op = nilfs_btree_do_delete;
1534 path[level].bp_op = nilfs_btree_do_delete;
1539 path[level].bp_oldreq.bpr_ptr =
1543 ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat);
1554 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1557 brelse(path[level].bp_sib_bh);
1558 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1566 struct nilfs_btree_path *path,
1572 nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat);
1573 path[level].bp_op(btree, path, level, NULL, NULL);
1583 struct nilfs_btree_path *path;
1588 path = nilfs_btree_alloc_path();
1589 if (path == NULL)
1592 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1600 ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat);
1603 nilfs_btree_commit_delete(btree, path, level, dat);
1607 nilfs_btree_free_path(path);
1614 struct nilfs_btree_path *path;
1618 path = nilfs_btree_alloc_path();
1619 if (!path)
1622 ret = nilfs_btree_do_lookup(btree, path, start, NULL, minlevel, 0);
1626 ret = nilfs_btree_get_next_key(btree, path, minlevel, keyp);
1628 nilfs_btree_free_path(path);
1634 struct nilfs_btree_path *path;
1637 path = nilfs_btree_alloc_path();
1638 if (path == NULL)
1641 ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL);
1643 nilfs_btree_free_path(path);
1899 struct nilfs_btree_path *path,
1904 !buffer_dirty(path[level].bp_bh))
1905 mark_buffer_dirty(path[level].bp_bh);
1911 struct nilfs_btree_path *path,
1917 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1918 path[level].bp_oldreq.bpr_ptr =
1919 nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
1921 path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1;
1922 ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req,
1923 &path[level].bp_newreq.bpr_req);
1927 if (buffer_nilfs_node(path[level].bp_bh)) {
1928 path[level].bp_ctxt.oldkey = path[level].bp_oldreq.bpr_ptr;
1929 path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr;
1930 path[level].bp_ctxt.bh = path[level].bp_bh;
1933 &path[level].bp_ctxt);
1936 &path[level].bp_oldreq.bpr_req,
1937 &path[level].bp_newreq.bpr_req);
1946 struct nilfs_btree_path *path,
1952 nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req,
1953 &path[level].bp_newreq.bpr_req,
1956 if (buffer_nilfs_node(path[level].bp_bh)) {
1959 &path[level].bp_ctxt);
1960 path[level].bp_bh = path[level].bp_ctxt.bh;
1962 set_buffer_nilfs_volatile(path[level].bp_bh);
1964 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1965 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index,
1966 path[level].bp_newreq.bpr_ptr, ncmax);
1970 struct nilfs_btree_path *path,
1973 nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req,
1974 &path[level].bp_newreq.bpr_req);
1975 if (buffer_nilfs_node(path[level].bp_bh))
1978 &path[level].bp_ctxt);
1982 struct nilfs_btree_path *path,
1989 if (!buffer_nilfs_volatile(path[level].bp_bh)) {
1990 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
1995 !buffer_dirty(path[level].bp_bh)) {
1997 WARN_ON(buffer_nilfs_volatile(path[level].bp_bh));
1998 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
2010 nilfs_btree_abort_update_v(btree, path, level, dat);
2011 if (!buffer_nilfs_volatile(path[level].bp_bh))
2012 nilfs_btree_abort_update_v(btree, path, level, dat);
2017 struct nilfs_btree_path *path,
2024 if (!buffer_nilfs_volatile(path[minlevel].bp_bh))
2025 nilfs_btree_commit_update_v(btree, path, minlevel, dat);
2028 nilfs_btree_commit_update_v(btree, path, level, dat);
2032 struct nilfs_btree_path *path,
2042 path[level].bp_bh = bh;
2043 ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel,
2048 if (buffer_nilfs_volatile(path[level].bp_bh)) {
2049 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2051 path[level + 1].bp_index,
2058 nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat);
2061 brelse(path[level].bp_bh);
2062 path[level].bp_bh = NULL;
2069 struct nilfs_btree_path *path;
2076 path = nilfs_btree_alloc_path();
2077 if (path == NULL)
2089 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
2100 nilfs_btree_propagate_v(btree, path, level, bh) :
2101 nilfs_btree_propagate_p(btree, path, level, bh);
2104 nilfs_btree_free_path(path);
2189 struct nilfs_btree_path *path,
2200 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2201 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
2204 path[level].bp_ctxt.oldkey = ptr;
2205 path[level].bp_ctxt.newkey = blocknr;
2206 path[level].bp_ctxt.bh = *bh;
2209 &path[level].bp_ctxt);
2214 &path[level].bp_ctxt);
2215 *bh = path[level].bp_ctxt.bh;
2218 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr,
2221 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
2230 struct nilfs_btree_path *path,
2243 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2244 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
2252 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
2265 struct nilfs_btree_path *path;
2270 path = nilfs_btree_alloc_path();
2271 if (path == NULL)
2283 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
2290 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) :
2291 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo);
2294 nilfs_btree_free_path(path);
2329 struct nilfs_btree_path *path;
2333 path = nilfs_btree_alloc_path();
2334 if (path == NULL)
2337 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0);
2355 nilfs_btree_free_path(path);