Lines Matching refs:node
161 struct xfs_iext_node *node = ifp->if_u1.if_root; in xfs_iext_find_first_leaf() local
168 node = node->ptrs[0]; in xfs_iext_find_first_leaf()
169 ASSERT(node); in xfs_iext_find_first_leaf()
172 return node; in xfs_iext_find_first_leaf()
179 struct xfs_iext_node *node = ifp->if_u1.if_root; in xfs_iext_find_last_leaf() local
187 if (!node->ptrs[i]) in xfs_iext_find_last_leaf()
189 node = node->ptrs[i - 1]; in xfs_iext_find_last_leaf()
190 ASSERT(node); in xfs_iext_find_last_leaf()
193 return node; in xfs_iext_find_last_leaf()
277 struct xfs_iext_node *node, in xfs_iext_key_cmp() argument
281 if (node->keys[n] > offset) in xfs_iext_key_cmp()
283 if (node->keys[n] < offset) in xfs_iext_key_cmp()
309 struct xfs_iext_node *node = ifp->if_u1.if_root; in xfs_iext_find_level() local
317 if (xfs_iext_key_cmp(node, i, offset) > 0) in xfs_iext_find_level()
320 node = node->ptrs[i - 1]; in xfs_iext_find_level()
321 if (!node) in xfs_iext_find_level()
325 return node; in xfs_iext_find_level()
330 struct xfs_iext_node *node, in xfs_iext_node_pos() argument
336 if (xfs_iext_key_cmp(node, i, offset) > 0) in xfs_iext_node_pos()
345 struct xfs_iext_node *node, in xfs_iext_node_insert_pos() argument
351 if (xfs_iext_key_cmp(node, i, offset) > 0) in xfs_iext_node_insert_pos()
360 struct xfs_iext_node *node, in xfs_iext_node_nr_entries() argument
366 if (node->keys[i] == XFS_IEXT_KEY_INVALID) in xfs_iext_node_nr_entries()
401 struct xfs_iext_node *node = kmem_zalloc(NODE_SIZE, KM_NOFS); in xfs_iext_grow() local
407 node->keys[0] = xfs_iext_leaf_key(prev, 0); in xfs_iext_grow()
408 node->ptrs[0] = prev; in xfs_iext_grow()
414 node->keys[0] = prev->keys[0]; in xfs_iext_grow()
415 node->ptrs[0] = prev; in xfs_iext_grow()
419 node->keys[i] = XFS_IEXT_KEY_INVALID; in xfs_iext_grow()
421 ifp->if_u1.if_root = node; in xfs_iext_grow()
433 struct xfs_iext_node *node = ifp->if_u1.if_root; in xfs_iext_update_node() local
438 if (i > 0 && xfs_iext_key_cmp(node, i, old_offset) > 0) in xfs_iext_update_node()
440 if (node->keys[i] == old_offset) in xfs_iext_update_node()
441 node->keys[i] = new_offset; in xfs_iext_update_node()
443 node = node->ptrs[i - 1]; in xfs_iext_update_node()
444 ASSERT(node); in xfs_iext_update_node()
447 ASSERT(node == ptr); in xfs_iext_update_node()
456 struct xfs_iext_node *node = *nodep; in xfs_iext_split_node() local
472 new->keys[i] = node->keys[nr_keep + i]; in xfs_iext_split_node()
473 new->ptrs[i] = node->ptrs[nr_keep + i]; in xfs_iext_split_node()
475 node->keys[nr_keep + i] = XFS_IEXT_KEY_INVALID; in xfs_iext_split_node()
476 node->ptrs[nr_keep + i] = NULL; in xfs_iext_split_node()
499 struct xfs_iext_node *node, *new; in xfs_iext_insert_node() local
507 node = xfs_iext_find_level(ifp, offset, level); in xfs_iext_insert_node()
508 pos = xfs_iext_node_insert_pos(node, offset); in xfs_iext_insert_node()
509 nr_entries = xfs_iext_node_nr_entries(node, pos); in xfs_iext_insert_node()
511 ASSERT(pos >= nr_entries || xfs_iext_key_cmp(node, pos, offset) != 0); in xfs_iext_insert_node()
515 new = xfs_iext_split_node(&node, &pos, &nr_entries); in xfs_iext_insert_node()
521 if (node != new && pos == 0 && nr_entries > 0) in xfs_iext_insert_node()
522 xfs_iext_update_node(ifp, node->keys[0], offset, level, node); in xfs_iext_insert_node()
525 node->keys[i] = node->keys[i - 1]; in xfs_iext_insert_node()
526 node->ptrs[i] = node->ptrs[i - 1]; in xfs_iext_insert_node()
528 node->keys[pos] = offset; in xfs_iext_insert_node()
529 node->ptrs[pos] = ptr; in xfs_iext_insert_node()
675 struct xfs_iext_node *node, in xfs_iext_rebalance_node() argument
684 return node; in xfs_iext_rebalance_node()
692 prev->keys[nr_prev + i] = node->keys[i]; in xfs_iext_rebalance_node()
693 prev->ptrs[nr_prev + i] = node->ptrs[i]; in xfs_iext_rebalance_node()
695 return node; in xfs_iext_rebalance_node()
710 node->keys[nr_entries + i] = next->keys[i]; in xfs_iext_rebalance_node()
711 node->ptrs[nr_entries + i] = next->ptrs[i]; in xfs_iext_rebalance_node()
728 struct xfs_iext_node *node, *parent; in xfs_iext_remove_node() local
732 node = xfs_iext_find_level(ifp, offset, level); in xfs_iext_remove_node()
733 pos = xfs_iext_node_pos(node, offset); in xfs_iext_remove_node()
735 ASSERT(node->ptrs[pos]); in xfs_iext_remove_node()
736 ASSERT(node->ptrs[pos] == victim); in xfs_iext_remove_node()
739 nr_entries = xfs_iext_node_nr_entries(node, pos) - 1; in xfs_iext_remove_node()
740 offset = node->keys[0]; in xfs_iext_remove_node()
742 node->keys[i] = node->keys[i + 1]; in xfs_iext_remove_node()
743 node->ptrs[i] = node->ptrs[i + 1]; in xfs_iext_remove_node()
745 node->keys[nr_entries] = XFS_IEXT_KEY_INVALID; in xfs_iext_remove_node()
746 node->ptrs[nr_entries] = NULL; in xfs_iext_remove_node()
749 xfs_iext_update_node(ifp, offset, node->keys[0], level, node); in xfs_iext_remove_node()
750 offset = node->keys[0]; in xfs_iext_remove_node()
767 ASSERT(parent->ptrs[pos] == node); in xfs_iext_remove_node()
769 node = xfs_iext_rebalance_node(parent, &pos, node, nr_entries); in xfs_iext_remove_node()
770 if (node) { in xfs_iext_remove_node()
771 victim = node; in xfs_iext_remove_node()
772 node = parent; in xfs_iext_remove_node()
780 ASSERT(node == ifp->if_u1.if_root); in xfs_iext_remove_node()
781 ifp->if_u1.if_root = node->ptrs[0]; in xfs_iext_remove_node()
783 kmem_free(node); in xfs_iext_remove_node()
1025 struct xfs_iext_node *node, in xfs_iext_destroy_node() argument
1032 if (node->keys[i] == XFS_IEXT_KEY_INVALID) in xfs_iext_destroy_node()
1034 xfs_iext_destroy_node(node->ptrs[i], level - 1); in xfs_iext_destroy_node()
1038 kmem_free(node); in xfs_iext_destroy_node()