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;
757 p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax);
758 p.index = path[level + 1].bp_index + 1;
764 path[level + 1].bp_index = p.index;
766 brelse(path[level].bp_bh);
767 path[level].bp_bh = NULL;
769 ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh,
773 node = nilfs_btree_get_nonroot_node(path, level);
776 path[level].bp_index = index;
782 nilfs_btree_free_path(path);
792 struct nilfs_btree_path *path,
798 nilfs_btree_get_nonroot_node(path, level),
799 path[level].bp_index, key);
800 if (!buffer_dirty(path[level].bp_bh))
801 mark_buffer_dirty(path[level].bp_bh);
802 } while ((path[level].bp_index == 0) &&
809 path[level].bp_index, key);
814 struct nilfs_btree_path *path,
821 node = nilfs_btree_get_nonroot_node(path, level);
823 nilfs_btree_node_insert(node, path[level].bp_index,
825 if (!buffer_dirty(path[level].bp_bh))
826 mark_buffer_dirty(path[level].bp_bh);
828 if (path[level].bp_index == 0)
829 nilfs_btree_promote_key(btree, path, level + 1,
834 nilfs_btree_node_insert(node, path[level].bp_index,
841 struct nilfs_btree_path *path,
847 node = nilfs_btree_get_nonroot_node(path, level);
848 left = nilfs_btree_get_sib_node(path, level);
855 if (n > path[level].bp_index) {
863 if (!buffer_dirty(path[level].bp_bh))
864 mark_buffer_dirty(path[level].bp_bh);
865 if (!buffer_dirty(path[level].bp_sib_bh))
866 mark_buffer_dirty(path[level].bp_sib_bh);
868 nilfs_btree_promote_key(btree, path, level + 1,
872 brelse(path[level].bp_bh);
873 path[level].bp_bh = path[level].bp_sib_bh;
874 path[level].bp_sib_bh = NULL;
875 path[level].bp_index += lnchildren;
876 path[level + 1].bp_index--;
878 brelse(path[level].bp_sib_bh);
879 path[level].bp_sib_bh = NULL;
880 path[level].bp_index -= n;
883 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
887 struct nilfs_btree_path *path,
893 node = nilfs_btree_get_nonroot_node(path, level);
894 right = nilfs_btree_get_sib_node(path, level);
901 if (n > nchildren - path[level].bp_index) {
909 if (!buffer_dirty(path[level].bp_bh))
910 mark_buffer_dirty(path[level].bp_bh);
911 if (!buffer_dirty(path[level].bp_sib_bh))
912 mark_buffer_dirty(path[level].bp_sib_bh);
914 path[level + 1].bp_index++;
915 nilfs_btree_promote_key(btree, path, level + 1,
917 path[level + 1].bp_index--;
920 brelse(path[level].bp_bh);
921 path[level].bp_bh = path[level].bp_sib_bh;
922 path[level].bp_sib_bh = NULL;
923 path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
924 path[level + 1].bp_index++;
926 brelse(path[level].bp_sib_bh);
927 path[level].bp_sib_bh = NULL;
930 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
934 struct nilfs_btree_path *path,
940 node = nilfs_btree_get_nonroot_node(path, level);
941 right = nilfs_btree_get_sib_node(path, level);
947 if (n > nchildren - path[level].bp_index) {
954 if (!buffer_dirty(path[level].bp_bh))
955 mark_buffer_dirty(path[level].bp_bh);
956 if (!buffer_dirty(path[level].bp_sib_bh))
957 mark_buffer_dirty(path[level].bp_sib_bh);
960 path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
961 nilfs_btree_node_insert(right, path[level].bp_index,
965 *ptrp = path[level].bp_newreq.bpr_ptr;
967 brelse(path[level].bp_bh);
968 path[level].bp_bh = path[level].bp_sib_bh;
969 path[level].bp_sib_bh = NULL;
971 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
974 *ptrp = path[level].bp_newreq.bpr_ptr;
976 brelse(path[level].bp_sib_bh);
977 path[level].bp_sib_bh = NULL;
980 path[level + 1].bp_index++;
984 struct nilfs_btree_path *path,
991 child = nilfs_btree_get_sib_node(path, level);
1000 if (!buffer_dirty(path[level].bp_sib_bh))
1001 mark_buffer_dirty(path[level].bp_sib_bh);
1003 path[level].bp_bh = path[level].bp_sib_bh;
1004 path[level].bp_sib_bh = NULL;
1006 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
1009 *ptrp = path[level].bp_newreq.bpr_ptr;
1013 const struct nilfs_btree_path *path)
1018 if (path == NULL)
1023 if (path[level].bp_index > 0) {
1024 node = nilfs_btree_get_node(btree, path, level, &ncmax);
1026 path[level].bp_index - 1,
1033 node = nilfs_btree_get_node(btree, path, level, &ncmax);
1034 return nilfs_btree_node_get_ptr(node, path[level].bp_index,
1042 const struct nilfs_btree_path *path,
1052 ptr = nilfs_btree_find_near(btree, path);
1062 struct nilfs_btree_path *path,
1077 path[level].bp_newreq.bpr_ptr =
1078 nilfs_btree_find_target_v(btree, path, key);
1082 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1091 node = nilfs_btree_get_nonroot_node(path, level);
1093 path[level].bp_op = nilfs_btree_do_insert;
1098 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1099 pindex = path[level + 1].bp_index;
1110 path[level].bp_sib_bh = bh;
1111 path[level].bp_op = nilfs_btree_carry_left;
1128 path[level].bp_sib_bh = bh;
1129 path[level].bp_op = nilfs_btree_carry_right;
1138 path[level].bp_newreq.bpr_ptr =
1139 path[level - 1].bp_newreq.bpr_ptr + 1;
1141 &path[level].bp_newreq, dat);
1145 path[level].bp_newreq.bpr_ptr,
1154 path[level].bp_sib_bh = bh;
1155 path[level].bp_op = nilfs_btree_split;
1162 path[level].bp_op = nilfs_btree_do_insert;
1168 path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1;
1169 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1172 ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr,
1179 path[level].bp_sib_bh = bh;
1180 path[level].bp_op = nilfs_btree_grow;
1183 path[level].bp_op = nilfs_btree_do_insert;
1195 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1198 nilfs_btnode_delete(path[level].bp_sib_bh);
1199 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1203 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1211 struct nilfs_btree_path *path,
1218 ptr = path[NILFS_BTREE_LEVEL_DATA].bp_newreq.bpr_ptr;
1226 &path[level - 1].bp_newreq, dat);
1227 path[level].bp_op(btree, path, level, &key, &ptr);
1236 struct nilfs_btree_path *path;
1240 path = nilfs_btree_alloc_path();
1241 if (path == NULL)
1244 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1252 ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats);
1255 nilfs_btree_commit_insert(btree, path, level, key, ptr);
1259 nilfs_btree_free_path(path);
1264 struct nilfs_btree_path *path,
1271 node = nilfs_btree_get_nonroot_node(path, level);
1273 nilfs_btree_node_delete(node, path[level].bp_index,
1275 if (!buffer_dirty(path[level].bp_bh))
1276 mark_buffer_dirty(path[level].bp_bh);
1277 if (path[level].bp_index == 0)
1278 nilfs_btree_promote_key(btree, path, level + 1,
1282 nilfs_btree_node_delete(node, path[level].bp_index,
1289 struct nilfs_btree_path *path,
1295 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1297 node = nilfs_btree_get_nonroot_node(path, level);
1298 left = nilfs_btree_get_sib_node(path, level);
1307 if (!buffer_dirty(path[level].bp_bh))
1308 mark_buffer_dirty(path[level].bp_bh);
1309 if (!buffer_dirty(path[level].bp_sib_bh))
1310 mark_buffer_dirty(path[level].bp_sib_bh);
1312 nilfs_btree_promote_key(btree, path, level + 1,
1315 brelse(path[level].bp_sib_bh);
1316 path[level].bp_sib_bh = NULL;
1317 path[level].bp_index += n;
1321 struct nilfs_btree_path *path,
1327 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1329 node = nilfs_btree_get_nonroot_node(path, level);
1330 right = nilfs_btree_get_sib_node(path, level);
1339 if (!buffer_dirty(path[level].bp_bh))
1340 mark_buffer_dirty(path[level].bp_bh);
1341 if (!buffer_dirty(path[level].bp_sib_bh))
1342 mark_buffer_dirty(path[level].bp_sib_bh);
1344 path[level + 1].bp_index++;
1345 nilfs_btree_promote_key(btree, path, level + 1,
1347 path[level + 1].bp_index--;
1349 brelse(path[level].bp_sib_bh);
1350 path[level].bp_sib_bh = NULL;
1354 struct nilfs_btree_path *path,
1360 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1362 node = nilfs_btree_get_nonroot_node(path, level);
1363 left = nilfs_btree_get_sib_node(path, level);
1370 if (!buffer_dirty(path[level].bp_sib_bh))
1371 mark_buffer_dirty(path[level].bp_sib_bh);
1373 nilfs_btnode_delete(path[level].bp_bh);
1374 path[level].bp_bh = path[level].bp_sib_bh;
1375 path[level].bp_sib_bh = NULL;
1376 path[level].bp_index += nilfs_btree_node_get_nchildren(left);
1380 struct nilfs_btree_path *path,
1386 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1388 node = nilfs_btree_get_nonroot_node(path, level);
1389 right = nilfs_btree_get_sib_node(path, level);
1396 if (!buffer_dirty(path[level].bp_bh))
1397 mark_buffer_dirty(path[level].bp_bh);
1399 nilfs_btnode_delete(path[level].bp_sib_bh);
1400 path[level].bp_sib_bh = NULL;
1401 path[level + 1].bp_index++;
1405 struct nilfs_btree_path *path,
1411 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1414 child = nilfs_btree_get_nonroot_node(path, level);
1424 nilfs_btnode_delete(path[level].bp_bh);
1425 path[level].bp_bh = NULL;
1429 struct nilfs_btree_path *path,
1435 struct nilfs_btree_path *path,
1450 for (level = NILFS_BTREE_LEVEL_NODE_MIN, dindex = path[level].bp_index;
1453 node = nilfs_btree_get_nonroot_node(path, level);
1454 path[level].bp_oldreq.bpr_ptr =
1457 &path[level].bp_oldreq, dat);
1462 path[level].bp_op = nilfs_btree_do_delete;
1467 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1468 pindex = path[level + 1].bp_index;
1480 path[level].bp_sib_bh = bh;
1481 path[level].bp_op = nilfs_btree_borrow_left;
1485 path[level].bp_sib_bh = bh;
1486 path[level].bp_op = nilfs_btree_concat_left;
1500 path[level].bp_sib_bh = bh;
1501 path[level].bp_op = nilfs_btree_borrow_right;
1505 path[level].bp_sib_bh = bh;
1506 path[level].bp_op = nilfs_btree_concat_right;
1524 path[level].bp_op = nilfs_btree_shrink;
1527 path[level].bp_op = nilfs_btree_nop;
1530 path[level].bp_op = nilfs_btree_do_delete;
1538 path[level].bp_op = nilfs_btree_do_delete;
1543 path[level].bp_oldreq.bpr_ptr =
1547 ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat);
1558 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1561 brelse(path[level].bp_sib_bh);
1562 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1570 struct nilfs_btree_path *path,
1576 nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat);
1577 path[level].bp_op(btree, path, level, NULL, NULL);
1587 struct nilfs_btree_path *path;
1592 path = nilfs_btree_alloc_path();
1593 if (path == NULL)
1596 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1604 ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat);
1607 nilfs_btree_commit_delete(btree, path, level, dat);
1611 nilfs_btree_free_path(path);
1618 struct nilfs_btree_path *path;
1622 path = nilfs_btree_alloc_path();
1623 if (!path)
1626 ret = nilfs_btree_do_lookup(btree, path, start, NULL, minlevel, 0);
1630 ret = nilfs_btree_get_next_key(btree, path, minlevel, keyp);
1632 nilfs_btree_free_path(path);
1638 struct nilfs_btree_path *path;
1641 path = nilfs_btree_alloc_path();
1642 if (path == NULL)
1645 ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL);
1647 nilfs_btree_free_path(path);
1901 struct nilfs_btree_path *path,
1906 !buffer_dirty(path[level].bp_bh))
1907 mark_buffer_dirty(path[level].bp_bh);
1913 struct nilfs_btree_path *path,
1919 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1920 path[level].bp_oldreq.bpr_ptr =
1921 nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
1923 path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1;
1924 ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req,
1925 &path[level].bp_newreq.bpr_req);
1929 if (buffer_nilfs_node(path[level].bp_bh)) {
1930 path[level].bp_ctxt.oldkey = path[level].bp_oldreq.bpr_ptr;
1931 path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr;
1932 path[level].bp_ctxt.bh = path[level].bp_bh;
1935 &path[level].bp_ctxt);
1938 &path[level].bp_oldreq.bpr_req,
1939 &path[level].bp_newreq.bpr_req);
1948 struct nilfs_btree_path *path,
1954 nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req,
1955 &path[level].bp_newreq.bpr_req,
1958 if (buffer_nilfs_node(path[level].bp_bh)) {
1961 &path[level].bp_ctxt);
1962 path[level].bp_bh = path[level].bp_ctxt.bh;
1964 set_buffer_nilfs_volatile(path[level].bp_bh);
1966 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1967 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index,
1968 path[level].bp_newreq.bpr_ptr, ncmax);
1972 struct nilfs_btree_path *path,
1975 nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req,
1976 &path[level].bp_newreq.bpr_req);
1977 if (buffer_nilfs_node(path[level].bp_bh))
1980 &path[level].bp_ctxt);
1984 struct nilfs_btree_path *path,
1991 if (!buffer_nilfs_volatile(path[level].bp_bh)) {
1992 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
1997 !buffer_dirty(path[level].bp_bh)) {
1999 WARN_ON(buffer_nilfs_volatile(path[level].bp_bh));
2000 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
2012 nilfs_btree_abort_update_v(btree, path, level, dat);
2013 if (!buffer_nilfs_volatile(path[level].bp_bh))
2014 nilfs_btree_abort_update_v(btree, path, level, dat);
2019 struct nilfs_btree_path *path,
2026 if (!buffer_nilfs_volatile(path[minlevel].bp_bh))
2027 nilfs_btree_commit_update_v(btree, path, minlevel, dat);
2030 nilfs_btree_commit_update_v(btree, path, level, dat);
2034 struct nilfs_btree_path *path,
2044 path[level].bp_bh = bh;
2045 ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel,
2050 if (buffer_nilfs_volatile(path[level].bp_bh)) {
2051 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2053 path[level + 1].bp_index,
2060 nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat);
2063 brelse(path[level].bp_bh);
2064 path[level].bp_bh = NULL;
2071 struct nilfs_btree_path *path;
2078 path = nilfs_btree_alloc_path();
2079 if (path == NULL)
2091 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
2102 nilfs_btree_propagate_v(btree, path, level, bh) :
2103 nilfs_btree_propagate_p(btree, path, level, bh);
2106 nilfs_btree_free_path(path);
2191 struct nilfs_btree_path *path,
2202 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2203 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
2206 path[level].bp_ctxt.oldkey = ptr;
2207 path[level].bp_ctxt.newkey = blocknr;
2208 path[level].bp_ctxt.bh = *bh;
2211 &path[level].bp_ctxt);
2216 &path[level].bp_ctxt);
2217 *bh = path[level].bp_ctxt.bh;
2220 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr,
2223 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
2233 struct nilfs_btree_path *path,
2246 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2247 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
2255 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
2268 struct nilfs_btree_path *path;
2273 path = nilfs_btree_alloc_path();
2274 if (path == NULL)
2286 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
2293 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) :
2294 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo);
2297 nilfs_btree_free_path(path);
2332 struct nilfs_btree_path *path;
2336 path = nilfs_btree_alloc_path();
2337 if (path == NULL)
2340 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0);
2358 nilfs_btree_free_path(path);