Lines Matching refs:node
73 static int nilfs_btree_node_get_flags(const struct nilfs_btree_node *node) in nilfs_btree_node_get_flags() argument
75 return node->bn_flags; in nilfs_btree_node_get_flags()
79 nilfs_btree_node_set_flags(struct nilfs_btree_node *node, int flags) in nilfs_btree_node_set_flags() argument
81 node->bn_flags = flags; in nilfs_btree_node_set_flags()
84 static int nilfs_btree_node_root(const struct nilfs_btree_node *node) in nilfs_btree_node_root() argument
86 return nilfs_btree_node_get_flags(node) & NILFS_BTREE_NODE_ROOT; in nilfs_btree_node_root()
89 static int nilfs_btree_node_get_level(const struct nilfs_btree_node *node) in nilfs_btree_node_get_level() argument
91 return node->bn_level; in nilfs_btree_node_get_level()
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()
100 static int nilfs_btree_node_get_nchildren(const struct nilfs_btree_node *node) in nilfs_btree_node_get_nchildren() argument
102 return le16_to_cpu(node->bn_nchildren); in nilfs_btree_node_get_nchildren()
106 nilfs_btree_node_set_nchildren(struct nilfs_btree_node *node, int nchildren) in nilfs_btree_node_set_nchildren() argument
108 node->bn_nchildren = cpu_to_le16(nchildren); in nilfs_btree_node_set_nchildren()
122 nilfs_btree_node_dkeys(const struct nilfs_btree_node *node) in nilfs_btree_node_dkeys() argument
124 return (__le64 *)((char *)(node + 1) + in nilfs_btree_node_dkeys()
125 (nilfs_btree_node_root(node) ? in nilfs_btree_node_dkeys()
130 nilfs_btree_node_dptrs(const struct nilfs_btree_node *node, int ncmax) in nilfs_btree_node_dptrs() argument
132 return (__le64 *)(nilfs_btree_node_dkeys(node) + ncmax); in nilfs_btree_node_dptrs()
136 nilfs_btree_node_get_key(const struct nilfs_btree_node *node, int index) in nilfs_btree_node_get_key() argument
138 return le64_to_cpu(*(nilfs_btree_node_dkeys(node) + index)); in nilfs_btree_node_get_key()
142 nilfs_btree_node_set_key(struct nilfs_btree_node *node, int index, __u64 key) in nilfs_btree_node_set_key() argument
144 *(nilfs_btree_node_dkeys(node) + index) = cpu_to_le64(key); in nilfs_btree_node_set_key()
148 nilfs_btree_node_get_ptr(const struct nilfs_btree_node *node, int index, in nilfs_btree_node_get_ptr() argument
151 return le64_to_cpu(*(nilfs_btree_node_dptrs(node, ncmax) + index)); in nilfs_btree_node_get_ptr()
155 nilfs_btree_node_set_ptr(struct nilfs_btree_node *node, int index, __u64 ptr, in nilfs_btree_node_set_ptr() argument
158 *(nilfs_btree_node_dptrs(node, ncmax) + index) = cpu_to_le64(ptr); in nilfs_btree_node_set_ptr()
161 static void nilfs_btree_node_init(struct nilfs_btree_node *node, int flags, in nilfs_btree_node_init() argument
169 nilfs_btree_node_set_flags(node, flags); in nilfs_btree_node_init()
170 nilfs_btree_node_set_level(node, level); in nilfs_btree_node_init()
171 nilfs_btree_node_set_nchildren(node, nchildren); in nilfs_btree_node_init()
173 dkeys = nilfs_btree_node_dkeys(node); in nilfs_btree_node_init()
174 dptrs = nilfs_btree_node_dptrs(node, ncmax); in nilfs_btree_node_init()
238 static void nilfs_btree_node_insert(struct nilfs_btree_node *node, int index, in nilfs_btree_node_insert() argument
245 dkeys = nilfs_btree_node_dkeys(node); in nilfs_btree_node_insert()
246 dptrs = nilfs_btree_node_dptrs(node, ncmax); in nilfs_btree_node_insert()
247 nchildren = nilfs_btree_node_get_nchildren(node); in nilfs_btree_node_insert()
257 nilfs_btree_node_set_nchildren(node, nchildren); in nilfs_btree_node_insert()
261 static void nilfs_btree_node_delete(struct nilfs_btree_node *node, int index, in nilfs_btree_node_delete() argument
270 dkeys = nilfs_btree_node_dkeys(node); in nilfs_btree_node_delete()
271 dptrs = nilfs_btree_node_dptrs(node, ncmax); in nilfs_btree_node_delete()
274 nchildren = nilfs_btree_node_get_nchildren(node); in nilfs_btree_node_delete()
287 nilfs_btree_node_set_nchildren(node, nchildren); in nilfs_btree_node_delete()
290 static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node, in nilfs_btree_node_lookup() argument
298 high = nilfs_btree_node_get_nchildren(node) - 1; in nilfs_btree_node_lookup()
303 nkey = nilfs_btree_node_get_key(node, index); in nilfs_btree_node_lookup()
317 if (nilfs_btree_node_get_level(node) > NILFS_BTREE_LEVEL_NODE_MIN) { in nilfs_btree_node_lookup()
338 static int nilfs_btree_node_broken(const struct nilfs_btree_node *node, in nilfs_btree_node_broken() argument
345 level = nilfs_btree_node_get_level(node); in nilfs_btree_node_broken()
346 flags = nilfs_btree_node_get_flags(node); in nilfs_btree_node_broken()
347 nchildren = nilfs_btree_node_get_nchildren(node); in nilfs_btree_node_broken()
370 static int nilfs_btree_root_broken(const struct nilfs_btree_node *node, in nilfs_btree_root_broken() argument
376 level = nilfs_btree_node_get_level(node); in nilfs_btree_root_broken()
377 flags = nilfs_btree_node_get_flags(node); in nilfs_btree_root_broken()
378 nchildren = nilfs_btree_node_get_nchildren(node); in nilfs_btree_root_broken()
436 struct nilfs_btree_node *node; in nilfs_btree_get_node() local
439 node = nilfs_btree_get_root(btree); in nilfs_btree_get_node()
442 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_get_node()
445 return node; 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()
456 nilfs_btree_node_get_level(node), level); in nilfs_btree_bad_node()
463 struct nilfs_btree_node *node; /* parent node */ member
493 ptr2 = nilfs_btree_node_get_ptr(ra->node, i, ra->ncmax); in __nilfs_btree_get_block()
540 struct nilfs_btree_node *node; in nilfs_btree_do_lookup() local
545 node = nilfs_btree_get_root(btree); in nilfs_btree_do_lookup()
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()
550 found = nilfs_btree_node_lookup(node, key, &index); in nilfs_btree_do_lookup()
551 ptr = nilfs_btree_node_get_ptr(node, index, in nilfs_btree_do_lookup()
561 p.node = nilfs_btree_get_node(btree, path, level + 1, 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()
576 found = nilfs_btree_node_lookup(node, key, &index); in nilfs_btree_do_lookup()
580 ptr = nilfs_btree_node_get_ptr(node, index, ncmax); in nilfs_btree_do_lookup()
601 struct nilfs_btree_node *node; in nilfs_btree_do_lookup_last() local
605 node = nilfs_btree_get_root(btree); in nilfs_btree_do_lookup_last()
606 index = nilfs_btree_node_get_nchildren(node) - 1; in nilfs_btree_do_lookup_last()
609 level = nilfs_btree_node_get_level(node); in nilfs_btree_do_lookup_last()
610 ptr = nilfs_btree_node_get_ptr(node, index, 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()
623 index = nilfs_btree_node_get_nchildren(node) - 1; in nilfs_btree_do_lookup_last()
624 ptr = nilfs_btree_node_get_ptr(node, index, ncmax); in nilfs_btree_do_lookup_last()
629 *keyp = nilfs_btree_node_get_key(node, index); in nilfs_btree_do_lookup_last()
650 struct nilfs_btree_node *node; in nilfs_btree_get_next_key() local
658 node = nilfs_btree_get_root(btree); in nilfs_btree_get_next_key()
660 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_get_next_key()
663 if (index < nilfs_btree_node_get_nchildren(node)) { in nilfs_btree_get_next_key()
665 *nextkey = nilfs_btree_node_get_key(node, index); in nilfs_btree_get_next_key()
696 struct nilfs_btree_node *node; in nilfs_btree_lookup_contig() local
724 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_lookup_contig()
727 while (index < nilfs_btree_node_get_nchildren(node)) { in nilfs_btree_lookup_contig()
728 if (nilfs_btree_node_get_key(node, index) != in nilfs_btree_lookup_contig()
731 ptr2 = nilfs_btree_node_get_ptr(node, index, ncmax); in nilfs_btree_lookup_contig()
747 p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax); in nilfs_btree_lookup_contig()
750 if (p.index >= nilfs_btree_node_get_nchildren(p.node) || in nilfs_btree_lookup_contig()
751 nilfs_btree_node_get_key(p.node, p.index) != key + cnt) in nilfs_btree_lookup_contig()
753 ptr2 = nilfs_btree_node_get_ptr(p.node, p.index, p.ncmax); in nilfs_btree_lookup_contig()
763 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_lookup_contig()
802 struct nilfs_btree_node *node; in nilfs_btree_do_insert() local
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()
815 nilfs_btree_node_get_key(node, in nilfs_btree_do_insert()
818 node = nilfs_btree_get_root(btree); in nilfs_btree_do_insert()
819 nilfs_btree_node_insert(node, path[level].bp_index, in nilfs_btree_do_insert()
829 struct nilfs_btree_node *node, *left; in nilfs_btree_carry_left() local
832 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_carry_left()
834 nchildren = nilfs_btree_node_get_nchildren(node); in nilfs_btree_carry_left()
846 nilfs_btree_node_move_left(left, node, n, ncblk, ncblk); in nilfs_btree_carry_left()
854 nilfs_btree_node_get_key(node, 0)); in nilfs_btree_carry_left()
875 struct nilfs_btree_node *node, *right; in nilfs_btree_carry_right() local
878 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_carry_right()
880 nchildren = nilfs_btree_node_get_nchildren(node); in nilfs_btree_carry_right()
892 nilfs_btree_node_move_right(node, right, n, ncblk, ncblk); in nilfs_btree_carry_right()
908 path[level].bp_index -= nilfs_btree_node_get_nchildren(node); in nilfs_btree_carry_right()
922 struct nilfs_btree_node *node, *right; in nilfs_btree_split() local
925 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_split()
927 nchildren = nilfs_btree_node_get_nchildren(node); in nilfs_btree_split()
937 nilfs_btree_node_move_right(node, right, n, ncblk, ncblk); in nilfs_btree_split()
945 path[level].bp_index -= nilfs_btree_node_get_nchildren(node); in nilfs_btree_split()
1000 struct nilfs_btree_node *node; in nilfs_btree_find_near() local
1009 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_find_near()
1010 return nilfs_btree_node_get_ptr(node, 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()
1052 struct nilfs_btree_node *node, *parent, *sib; in nilfs_btree_prepare_insert() local
1076 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_prepare_insert()
1077 if (nilfs_btree_node_get_nchildren(node) < ncblk) { in nilfs_btree_prepare_insert()
1144 node = nilfs_btree_get_root(btree); in nilfs_btree_prepare_insert()
1145 if (nilfs_btree_node_get_nchildren(node) < in nilfs_btree_prepare_insert()
1252 struct nilfs_btree_node *node; in nilfs_btree_do_delete() local
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()
1264 nilfs_btree_node_get_key(node, 0)); in nilfs_btree_do_delete()
1266 node = nilfs_btree_get_root(btree); in nilfs_btree_do_delete()
1267 nilfs_btree_node_delete(node, path[level].bp_index, in nilfs_btree_do_delete()
1277 struct nilfs_btree_node *node, *left; in nilfs_btree_borrow_left() local
1282 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_borrow_left()
1284 nchildren = nilfs_btree_node_get_nchildren(node); in nilfs_btree_borrow_left()
1290 nilfs_btree_node_move_right(left, node, n, ncblk, ncblk); in nilfs_btree_borrow_left()
1298 nilfs_btree_node_get_key(node, 0)); in nilfs_btree_borrow_left()
1309 struct nilfs_btree_node *node, *right; in nilfs_btree_borrow_right() local
1314 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_borrow_right()
1316 nchildren = nilfs_btree_node_get_nchildren(node); in nilfs_btree_borrow_right()
1322 nilfs_btree_node_move_left(node, right, n, ncblk, ncblk); in nilfs_btree_borrow_right()
1342 struct nilfs_btree_node *node, *left; in nilfs_btree_concat_left() local
1347 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_concat_left()
1351 n = nilfs_btree_node_get_nchildren(node); in nilfs_btree_concat_left()
1353 nilfs_btree_node_move_left(left, node, n, ncblk, ncblk); in nilfs_btree_concat_left()
1368 struct nilfs_btree_node *node, *right; in nilfs_btree_concat_right() local
1373 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_concat_right()
1379 nilfs_btree_node_move_left(node, right, n, ncblk, ncblk); in nilfs_btree_concat_right()
1426 struct nilfs_btree_node *node, *parent, *sib; in nilfs_btree_prepare_delete() local
1438 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_prepare_delete()
1440 nilfs_btree_node_get_ptr(node, dindex, ncblk); in nilfs_btree_prepare_delete()
1446 if (nilfs_btree_node_get_nchildren(node) > ncmin) { in nilfs_btree_prepare_delete()
1507 if (nilfs_btree_node_get_nchildren(node) - 1 <= in nilfs_btree_prepare_delete()
1527 node = nilfs_btree_get_root(btree); in nilfs_btree_prepare_delete()
1529 nilfs_btree_node_get_ptr(node, dindex, in nilfs_btree_prepare_delete()
1640 struct nilfs_btree_node *root, *node; in nilfs_btree_check_delete() local
1649 node = root; in nilfs_btree_check_delete()
1660 node = (struct nilfs_btree_node *)bh->b_data; in nilfs_btree_check_delete()
1666 nchildren = nilfs_btree_node_get_nchildren(node); in nilfs_btree_check_delete()
1667 maxkey = nilfs_btree_node_get_key(node, nchildren - 1); in nilfs_btree_check_delete()
1669 nilfs_btree_node_get_key(node, nchildren - 2) : 0; in nilfs_btree_check_delete()
1680 struct nilfs_btree_node *node, *root; in nilfs_btree_gather_data() local
1690 node = root; in nilfs_btree_gather_data()
1701 node = (struct nilfs_btree_node *)bh->b_data; in nilfs_btree_gather_data()
1705 node = NULL; in nilfs_btree_gather_data()
1709 nchildren = nilfs_btree_node_get_nchildren(node); in nilfs_btree_gather_data()
1712 dkeys = nilfs_btree_node_dkeys(node); in nilfs_btree_gather_data()
1713 dptrs = nilfs_btree_node_dptrs(node, ncmax); in nilfs_btree_gather_data()
1787 struct nilfs_btree_node *node; in nilfs_btree_commit_convert_and_insert() local
1807 node = (struct nilfs_btree_node *)bh->b_data; in nilfs_btree_commit_convert_and_insert()
1809 nilfs_btree_node_init(node, 0, 1, n, ncblk, keys, ptrs); in nilfs_btree_commit_convert_and_insert()
1810 nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr, ncblk); in nilfs_btree_commit_convert_and_insert()
1819 node = nilfs_btree_get_root(btree); in nilfs_btree_commit_convert_and_insert()
1821 nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 2, 1, in nilfs_btree_commit_convert_and_insert()
1828 node = nilfs_btree_get_root(btree); in nilfs_btree_commit_convert_and_insert()
1829 nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 1, n, in nilfs_btree_commit_convert_and_insert()
1832 nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr, in nilfs_btree_commit_convert_and_insert()
2055 struct nilfs_btree_node *node; in nilfs_btree_propagate() local
2066 node = (struct nilfs_btree_node *)bh->b_data; in nilfs_btree_propagate()
2067 key = nilfs_btree_node_get_key(node, 0); in nilfs_btree_propagate()
2068 level = nilfs_btree_node_get_level(node); in nilfs_btree_propagate()
2106 struct nilfs_btree_node *node, *cnode; in nilfs_btree_add_dirty_buffer() local
2111 node = (struct nilfs_btree_node *)bh->b_data; in nilfs_btree_add_dirty_buffer()
2112 key = nilfs_btree_node_get_key(node, 0); in nilfs_btree_add_dirty_buffer()
2113 level = nilfs_btree_node_get_level(node); in nilfs_btree_add_dirty_buffer()
2250 struct nilfs_btree_node *node; in nilfs_btree_assign() local
2259 node = (struct nilfs_btree_node *)(*bh)->b_data; in nilfs_btree_assign()
2260 key = nilfs_btree_node_get_key(node, 0); in nilfs_btree_assign()
2261 level = nilfs_btree_node_get_level(node); in nilfs_btree_assign()
2288 struct nilfs_btree_node *node; in nilfs_btree_assign_gc() local
2298 node = (struct nilfs_btree_node *)(*bh)->b_data; in nilfs_btree_assign_gc()
2299 key = nilfs_btree_node_get_key(node, 0); in nilfs_btree_assign_gc()