Lines Matching refs:tree
87 zfs_btree_poison_node(zfs_btree_t *tree, zfs_btree_hdr_t *hdr) in zfs_btree_poison_node() argument
90 size_t size = tree->bt_elem_size; in zfs_btree_poison_node()
112 zfs_btree_poison_node_at(zfs_btree_t *tree, zfs_btree_hdr_t *hdr, in zfs_btree_poison_node_at() argument
116 size_t size = tree->bt_elem_size; in zfs_btree_poison_node_at()
128 ASSERT3U(idx, <=, tree->bt_leaf_cap); in zfs_btree_poison_node_at()
129 ASSERT3U(idx + count, <=, tree->bt_leaf_cap); in zfs_btree_poison_node_at()
138 zfs_btree_verify_poison_at(zfs_btree_t *tree, zfs_btree_hdr_t *hdr, in zfs_btree_verify_poison_at() argument
142 size_t size = tree->bt_elem_size; in zfs_btree_verify_poison_at()
151 ASSERT3U(idx, <, tree->bt_leaf_cap); in zfs_btree_verify_poison_at()
153 if (idx >= tree->bt_leaf_cap - hdr->bth_first) in zfs_btree_verify_poison_at()
177 zfs_btree_create(zfs_btree_t *tree, int (*compar) (const void *, const void *), in zfs_btree_create() argument
182 bzero(tree, sizeof (*tree)); in zfs_btree_create()
183 tree->bt_compar = compar; in zfs_btree_create()
184 tree->bt_elem_size = size; in zfs_btree_create()
185 tree->bt_leaf_cap = P2ALIGN(BTREE_LEAF_ESIZE / size, 2); in zfs_btree_create()
186 tree->bt_height = -1; in zfs_btree_create()
187 tree->bt_bulk = NULL; in zfs_btree_create()
194 zfs_btree_find_in_buf(zfs_btree_t *tree, uint8_t *buf, uint32_t nelems, in zfs_btree_find_in_buf() argument
201 uint8_t *cur = buf + idx * tree->bt_elem_size; in zfs_btree_find_in_buf()
202 int comp = tree->bt_compar(cur, value); in zfs_btree_find_in_buf()
224 zfs_btree_find(zfs_btree_t *tree, const void *value, zfs_btree_index_t *where) in zfs_btree_find() argument
226 if (tree->bt_height == -1) { in zfs_btree_find()
231 ASSERT0(tree->bt_num_elems); in zfs_btree_find()
242 size_t size = tree->bt_elem_size; in zfs_btree_find()
243 if (tree->bt_bulk != NULL) { in zfs_btree_find()
244 zfs_btree_leaf_t *last_leaf = tree->bt_bulk; in zfs_btree_find()
245 int comp = tree->bt_compar(last_leaf->btl_elems + in zfs_btree_find()
271 if (tree->bt_compar(last_leaf->btl_elems + in zfs_btree_find()
278 void *d = zfs_btree_find_in_buf(tree, in zfs_btree_find()
299 for (node = (zfs_btree_core_t *)tree->bt_root; depth < tree->bt_height; in zfs_btree_find()
302 void *d = zfs_btree_find_in_buf(tree, node->btc_elems, in zfs_btree_find()
321 (zfs_btree_leaf_t *)tree->bt_root : (zfs_btree_leaf_t *)node); in zfs_btree_find()
322 void *d = zfs_btree_find_in_buf(tree, leaf->btl_elems + in zfs_btree_find()
393 bt_shift_core(zfs_btree_t *tree, zfs_btree_core_t *node, uint32_t idx, in bt_shift_core() argument
397 size_t size = tree->bt_elem_size; in bt_shift_core()
420 bt_shift_core_left(zfs_btree_t *tree, zfs_btree_core_t *node, uint32_t idx, in bt_shift_core_left() argument
423 bt_shift_core(tree, node, idx, count, 1, shape, BSD_LEFT); in bt_shift_core_left()
431 bt_shift_core_right(zfs_btree_t *tree, zfs_btree_core_t *node, uint32_t idx, in bt_shift_core_right() argument
434 bt_shift_core(tree, node, idx, count, 1, shape, BSD_RIGHT); in bt_shift_core_right()
443 bt_shift_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *node, uint32_t idx, in bt_shift_leaf() argument
446 size_t size = tree->bt_elem_size; in bt_shift_leaf()
462 bt_grow_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *leaf, uint32_t idx, in bt_grow_leaf() argument
468 uint32_t capacity = tree->bt_leaf_cap; in bt_grow_leaf()
476 bt_shift_leaf(tree, leaf, n, idx, n, BSD_LEFT); in bt_grow_leaf()
479 bt_shift_leaf(tree, leaf, idx, hdr->bth_count - idx, n, in bt_grow_leaf()
486 bt_shift_leaf(tree, leaf, fn, idx, fn, BSD_LEFT); in bt_grow_leaf()
487 bt_shift_leaf(tree, leaf, fn + idx, hdr->bth_count - idx, in bt_grow_leaf()
497 bt_shrink_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *leaf, uint32_t idx, in bt_shrink_leaf() argument
506 bt_shift_leaf(tree, leaf, 0, idx, n, BSD_RIGHT); in bt_shrink_leaf()
507 zfs_btree_poison_node_at(tree, hdr, 0, n); in bt_shrink_leaf()
510 bt_shift_leaf(tree, leaf, idx + n, hdr->bth_count - idx - n, n, in bt_shrink_leaf()
512 zfs_btree_poison_node_at(tree, hdr, hdr->bth_count - n, n); in bt_shrink_leaf()
522 bt_transfer_core(zfs_btree_t *tree, zfs_btree_core_t *source, uint32_t sidx, in bt_transfer_core() argument
526 size_t size = tree->bt_elem_size; in bt_transfer_core()
540 bt_transfer_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *source, uint32_t sidx, in bt_transfer_leaf() argument
543 size_t size = tree->bt_elem_size; in bt_transfer_leaf()
557 zfs_btree_first_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr, in zfs_btree_first_helper() argument
573 return (&leaf->btl_elems[node->bth_first * tree->bt_elem_size]); in zfs_btree_first_helper()
578 zfs_btree_insert_core_impl(zfs_btree_t *tree, zfs_btree_core_t *parent, in zfs_btree_insert_core_impl() argument
581 size_t size = tree->bt_elem_size; in zfs_btree_insert_core_impl()
587 zfs_btree_verify_poison_at(tree, par_hdr, in zfs_btree_insert_core_impl()
592 bt_shift_core_right(tree, parent, offset, count, in zfs_btree_insert_core_impl()
606 zfs_btree_insert_into_parent(zfs_btree_t *tree, zfs_btree_hdr_t *old_node, in zfs_btree_insert_into_parent() argument
610 size_t size = tree->bt_elem_size; in zfs_btree_insert_into_parent()
619 ASSERT3P(old_node, ==, tree->bt_root); in zfs_btree_insert_into_parent()
620 tree->bt_num_nodes++; in zfs_btree_insert_into_parent()
634 tree->bt_height++; in zfs_btree_insert_into_parent()
635 tree->bt_root = new_root_hdr; in zfs_btree_insert_into_parent()
636 zfs_btree_poison_node(tree, new_root_hdr); in zfs_btree_insert_into_parent()
646 VERIFY3P(zfs_btree_find_in_buf(tree, parent->btc_elems, in zfs_btree_insert_into_parent()
658 zfs_btree_insert_core_impl(tree, parent, offset, new_node, buf); in zfs_btree_insert_into_parent()
680 uint32_t move_count = MAX((BTREE_CORE_ELEMS / (tree->bt_bulk == NULL ? in zfs_btree_insert_into_parent()
684 tree->bt_num_nodes++; in zfs_btree_insert_into_parent()
691 zfs_btree_poison_node(tree, new_par_hdr); in zfs_btree_insert_into_parent()
695 bt_transfer_core(tree, parent, keep_count + 1, move_count, new_parent, in zfs_btree_insert_into_parent()
702 zfs_btree_poison_node(tree, par_hdr); in zfs_btree_insert_into_parent()
706 zfs_btree_insert_core_impl(tree, parent, offset, new_node, in zfs_btree_insert_into_parent()
716 zfs_btree_insert_core_impl(tree, new_parent, in zfs_btree_insert_into_parent()
729 bt_shift_core_right(tree, new_parent, 0, move_count, in zfs_btree_insert_into_parent()
736 zfs_btree_poison_node(tree, par_hdr); in zfs_btree_insert_into_parent()
748 zfs_btree_insert_into_parent(tree, &parent->btc_hdr, in zfs_btree_insert_into_parent()
754 zfs_btree_insert_leaf_impl(zfs_btree_t *tree, zfs_btree_leaf_t *leaf, in zfs_btree_insert_leaf_impl() argument
757 size_t size = tree->bt_elem_size; in zfs_btree_insert_leaf_impl()
759 ASSERT3U(leaf->btl_hdr.bth_count, <, tree->bt_leaf_cap); in zfs_btree_insert_leaf_impl()
762 zfs_btree_verify_poison_at(tree, &leaf->btl_hdr, in zfs_btree_insert_leaf_impl()
766 bt_grow_leaf(tree, leaf, idx, 1); in zfs_btree_insert_leaf_impl()
772 zfs_btree_verify_order_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr);
776 zfs_btree_insert_into_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *leaf, in zfs_btree_insert_into_leaf() argument
779 size_t size = tree->bt_elem_size; in zfs_btree_insert_into_leaf()
780 uint32_t capacity = tree->bt_leaf_cap; in zfs_btree_insert_into_leaf()
787 zfs_btree_insert_leaf_impl(tree, leaf, idx, value); in zfs_btree_insert_into_leaf()
805 uint32_t move_count = MAX(capacity / (tree->bt_bulk ? 4 : 2), 1) - 1; in zfs_btree_insert_into_leaf()
813 tree->bt_num_nodes++; in zfs_btree_insert_into_leaf()
818 new_hdr->bth_first = (tree->bt_bulk ? 0 : capacity / 4) + in zfs_btree_insert_into_leaf()
821 zfs_btree_poison_node(tree, new_hdr); in zfs_btree_insert_into_leaf()
823 if (tree->bt_bulk != NULL && leaf == tree->bt_bulk) in zfs_btree_insert_into_leaf()
824 tree->bt_bulk = new_leaf; in zfs_btree_insert_into_leaf()
827 bt_transfer_leaf(tree, leaf, keep_count + 1, move_count, new_leaf, 0); in zfs_btree_insert_into_leaf()
834 bt_shrink_leaf(tree, leaf, keep_count, 1 + move_count); in zfs_btree_insert_into_leaf()
838 zfs_btree_insert_leaf_impl(tree, leaf, idx, value); in zfs_btree_insert_into_leaf()
841 zfs_btree_insert_leaf_impl(tree, new_leaf, idx - keep_count - in zfs_btree_insert_into_leaf()
848 zfs_btree_insert_leaf_impl(tree, new_leaf, 0, buf); in zfs_btree_insert_into_leaf()
856 zfs_btree_insert_into_parent(tree, &leaf->btl_hdr, &new_leaf->btl_hdr, in zfs_btree_insert_into_leaf()
862 zfs_btree_find_parent_idx(zfs_btree_t *tree, zfs_btree_hdr_t *hdr) in zfs_btree_find_parent_idx() argument
869 hdr->bth_first * tree->bt_elem_size; in zfs_btree_find_parent_idx()
873 VERIFY3P(zfs_btree_find_in_buf(tree, parent->btc_elems, in zfs_btree_find_parent_idx()
891 zfs_btree_bulk_finish(zfs_btree_t *tree) in zfs_btree_bulk_finish() argument
893 ASSERT3P(tree->bt_bulk, !=, NULL); in zfs_btree_bulk_finish()
894 ASSERT3P(tree->bt_root, !=, NULL); in zfs_btree_bulk_finish()
895 zfs_btree_leaf_t *leaf = tree->bt_bulk; in zfs_btree_bulk_finish()
898 size_t size = tree->bt_elem_size; in zfs_btree_bulk_finish()
899 uint32_t capacity = tree->bt_leaf_cap; in zfs_btree_bulk_finish()
906 tree->bt_bulk = NULL; in zfs_btree_bulk_finish()
923 VERIFY3P(zfs_btree_prev(tree, &idx, &idx), !=, NULL); in zfs_btree_bulk_finish()
928 VERIFY3P(zfs_btree_prev(tree, &idx, &idx), !=, NULL); in zfs_btree_bulk_finish()
938 zfs_btree_verify_poison_at(tree, hdr, in zfs_btree_bulk_finish()
944 bt_grow_leaf(tree, leaf, 0, move_count); in zfs_btree_bulk_finish()
956 bt_transfer_leaf(tree, l_neighbor, l_hdr->bth_count - in zfs_btree_bulk_finish()
967 bt_shrink_leaf(tree, l_neighbor, l_hdr->bth_count - move_count, in zfs_btree_bulk_finish()
995 uint32_t parent_idx = zfs_btree_find_parent_idx(tree, hdr); in zfs_btree_bulk_finish()
1005 zfs_btree_verify_poison_at(tree, hdr, in zfs_btree_bulk_finish()
1010 bt_shift_core(tree, cur, 0, hdr->bth_count, move_count, in zfs_btree_bulk_finish()
1025 bt_transfer_core(tree, l_neighbor, move_idx, move_count, cur, 0, in zfs_btree_bulk_finish()
1041 zfs_btree_poison_node(tree, &l_neighbor->btc_hdr); in zfs_btree_bulk_finish()
1047 tree->bt_bulk = NULL; in zfs_btree_bulk_finish()
1048 zfs_btree_verify(tree); in zfs_btree_bulk_finish()
1055 zfs_btree_add_idx(zfs_btree_t *tree, const void *value, in zfs_btree_add_idx() argument
1061 if (tree->bt_bulk != NULL) { in zfs_btree_add_idx()
1062 if (where->bti_node != &tree->bt_bulk->btl_hdr) { in zfs_btree_add_idx()
1063 zfs_btree_bulk_finish(tree); in zfs_btree_add_idx()
1064 VERIFY3P(zfs_btree_find(tree, value, &idx), ==, NULL); in zfs_btree_add_idx()
1069 tree->bt_num_elems++; in zfs_btree_add_idx()
1075 ASSERT3U(tree->bt_num_elems, ==, 1); in zfs_btree_add_idx()
1076 ASSERT3S(tree->bt_height, ==, -1); in zfs_btree_add_idx()
1077 ASSERT3P(tree->bt_root, ==, NULL); in zfs_btree_add_idx()
1080 tree->bt_num_nodes++; in zfs_btree_add_idx()
1083 tree->bt_root = &leaf->btl_hdr; in zfs_btree_add_idx()
1084 tree->bt_height++; in zfs_btree_add_idx()
1090 zfs_btree_poison_node(tree, hdr); in zfs_btree_add_idx()
1092 zfs_btree_insert_into_leaf(tree, leaf, value, 0); in zfs_btree_add_idx()
1093 tree->bt_bulk = leaf; in zfs_btree_add_idx()
1099 zfs_btree_insert_into_leaf(tree, in zfs_btree_add_idx()
1118 size_t size = tree->bt_elem_size; in zfs_btree_add_idx()
1128 VERIFY3P(zfs_btree_first_helper(tree, subtree, &new_idx), !=, in zfs_btree_add_idx()
1132 zfs_btree_insert_into_leaf(tree, in zfs_btree_add_idx()
1136 zfs_btree_verify(tree); in zfs_btree_add_idx()
1144 zfs_btree_first(zfs_btree_t *tree, zfs_btree_index_t *where) in zfs_btree_first() argument
1146 if (tree->bt_height == -1) { in zfs_btree_first()
1147 ASSERT0(tree->bt_num_elems); in zfs_btree_first()
1150 return (zfs_btree_first_helper(tree, tree->bt_root, where)); in zfs_btree_first()
1182 zfs_btree_last(zfs_btree_t *tree, zfs_btree_index_t *where) in zfs_btree_last() argument
1184 if (tree->bt_height == -1) { in zfs_btree_last()
1185 ASSERT0(tree->bt_num_elems); in zfs_btree_last()
1188 return (zfs_btree_last_helper(tree, tree->bt_root, where)); in zfs_btree_last()
1198 zfs_btree_next_helper(zfs_btree_t *tree, const zfs_btree_index_t *idx, in zfs_btree_next_helper() argument
1203 ASSERT3S(tree->bt_height, ==, -1); in zfs_btree_next_helper()
1225 new_off) * tree->bt_elem_size); in zfs_btree_next_helper()
1233 uint32_t i = zfs_btree_find_parent_idx(tree, prev); in zfs_btree_next_helper()
1235 done_func(tree, prev); in zfs_btree_next_helper()
1243 return (node->btc_elems + i * tree->bt_elem_size); in zfs_btree_next_helper()
1246 done_func(tree, prev); in zfs_btree_next_helper()
1259 return (node->btc_elems + offset * tree->bt_elem_size); in zfs_btree_next_helper()
1267 return (zfs_btree_first_helper(tree, child, out_idx)); in zfs_btree_next_helper()
1275 zfs_btree_next(zfs_btree_t *tree, const zfs_btree_index_t *idx, in zfs_btree_next() argument
1278 return (zfs_btree_next_helper(tree, idx, out_idx, NULL)); in zfs_btree_next()
1286 zfs_btree_prev(zfs_btree_t *tree, const zfs_btree_index_t *idx, in zfs_btree_prev() argument
1290 ASSERT3S(tree->bt_height, ==, -1); in zfs_btree_prev()
1311 offset - 1) * tree->bt_elem_size); in zfs_btree_prev()
1318 uint32_t i = zfs_btree_find_parent_idx(tree, prev); in zfs_btree_prev()
1326 return (node->btc_elems + (i - 1) * tree->bt_elem_size); in zfs_btree_prev()
1342 return (zfs_btree_last_helper(tree, child, out_idx)); in zfs_btree_prev()
1353 zfs_btree_get(zfs_btree_t *tree, zfs_btree_index_t *idx) in zfs_btree_get() argument
1356 size_t size = tree->bt_elem_size; in zfs_btree_get()
1368 zfs_btree_add(zfs_btree_t *tree, const void *node) in zfs_btree_add() argument
1371 VERIFY3P(zfs_btree_find(tree, node, &where), ==, NULL); in zfs_btree_add()
1372 zfs_btree_add_idx(tree, node, &where); in zfs_btree_add()
1377 zfs_btree_node_destroy(zfs_btree_t *tree, zfs_btree_hdr_t *node) in zfs_btree_node_destroy() argument
1379 tree->bt_num_nodes--; in zfs_btree_node_destroy()
1384 BTREE_CORE_ELEMS * tree->bt_elem_size); in zfs_btree_node_destroy()
1394 zfs_btree_remove_from_node(zfs_btree_t *tree, zfs_btree_core_t *node, in zfs_btree_remove_from_node() argument
1397 size_t size = tree->bt_elem_size; in zfs_btree_remove_from_node()
1406 ASSERT3P(tree->bt_root, ==, node); in zfs_btree_remove_from_node()
1408 tree->bt_root = node->btc_children[0]; in zfs_btree_remove_from_node()
1410 zfs_btree_node_destroy(tree, hdr); in zfs_btree_remove_from_node()
1411 tree->bt_height--; in zfs_btree_remove_from_node()
1432 bt_shift_core_left(tree, node, idx, hdr->bth_count - idx, in zfs_btree_remove_from_node()
1435 zfs_btree_poison_node_at(tree, hdr, hdr->bth_count, 1); in zfs_btree_remove_from_node()
1456 uint32_t parent_idx = zfs_btree_find_parent_idx(tree, hdr); in zfs_btree_remove_from_node()
1469 bt_shift_core_right(tree, node, 0, idx - 1, BSS_TRAPEZOID); in zfs_btree_remove_from_node()
1489 zfs_btree_poison_node_at(tree, l_hdr, l_hdr->bth_count, 1); in zfs_btree_remove_from_node()
1504 bt_shift_core_left(tree, node, idx, hdr->bth_count - idx, in zfs_btree_remove_from_node()
1531 bt_shift_core_left(tree, neighbor, 1, r_hdr->bth_count, in zfs_btree_remove_from_node()
1533 zfs_btree_poison_node_at(tree, r_hdr, r_hdr->bth_count, 1); in zfs_btree_remove_from_node()
1568 zfs_btree_verify_poison_at(tree, keep_hdr, in zfs_btree_remove_from_node()
1581 bt_transfer_core(tree, rm, 0, new_rm_hdr->bth_count, keep, in zfs_btree_remove_from_node()
1595 bt_shift_core_left(tree, keep, new_idx, keep_hdr->bth_count - new_idx, in zfs_btree_remove_from_node()
1608 zfs_btree_poison_node_at(tree, keep_hdr, keep_hdr->bth_count, 1); in zfs_btree_remove_from_node()
1611 zfs_btree_remove_from_node(tree, parent, new_rm_hdr); in zfs_btree_remove_from_node()
1612 zfs_btree_node_destroy(tree, new_rm_hdr); in zfs_btree_remove_from_node()
1617 zfs_btree_remove_idx(zfs_btree_t *tree, zfs_btree_index_t *where) in zfs_btree_remove_idx() argument
1619 size_t size = tree->bt_elem_size; in zfs_btree_remove_idx()
1624 if (tree->bt_bulk != NULL) { in zfs_btree_remove_idx()
1631 uint8_t *value = zfs_btree_get(tree, where); in zfs_btree_remove_idx()
1634 zfs_btree_bulk_finish(tree); in zfs_btree_remove_idx()
1635 VERIFY3P(zfs_btree_find(tree, tmp, where), !=, NULL); in zfs_btree_remove_idx()
1641 tree->bt_num_elems--; in zfs_btree_remove_idx()
1651 void *new_value = zfs_btree_last_helper(tree, left_subtree, in zfs_btree_remove_idx()
1671 uint32_t min_count = (tree->bt_leaf_cap / 2) - 1; in zfs_btree_remove_idx()
1678 bt_shrink_leaf(tree, leaf, idx, 1); in zfs_btree_remove_idx()
1680 ASSERT0(tree->bt_height); in zfs_btree_remove_idx()
1682 tree->bt_root = NULL; in zfs_btree_remove_idx()
1683 tree->bt_height--; in zfs_btree_remove_idx()
1684 zfs_btree_node_destroy(tree, &leaf->btl_hdr); in zfs_btree_remove_idx()
1687 zfs_btree_verify(tree); in zfs_btree_remove_idx()
1706 uint32_t parent_idx = zfs_btree_find_parent_idx(tree, hdr); in zfs_btree_remove_idx()
1719 bt_shift_leaf(tree, leaf, 0, idx, 1, BSD_RIGHT); in zfs_btree_remove_idx()
1732 bt_shrink_leaf(tree, neighbor, l_hdr->bth_count - 1, 1); in zfs_btree_remove_idx()
1733 zfs_btree_verify(tree); in zfs_btree_remove_idx()
1749 bt_shift_leaf(tree, leaf, idx + 1, hdr->bth_count - idx - 1, in zfs_btree_remove_idx()
1763 bt_shrink_leaf(tree, neighbor, 0, 1); in zfs_btree_remove_idx()
1764 zfs_btree_verify(tree); in zfs_btree_remove_idx()
1797 zfs_btree_verify_poison_at(tree, k_hdr, in zfs_btree_remove_idx()
1806 bt_shrink_leaf(tree, leaf, idx, 1); in zfs_btree_remove_idx()
1810 bt_grow_leaf(tree, keep, k_count, 1 + rm_hdr->bth_count); in zfs_btree_remove_idx()
1819 bt_transfer_leaf(tree, rm, 0, rm_hdr->bth_count, keep, k_count + 1); in zfs_btree_remove_idx()
1822 zfs_btree_remove_from_node(tree, parent, rm_hdr); in zfs_btree_remove_idx()
1823 zfs_btree_node_destroy(tree, rm_hdr); in zfs_btree_remove_idx()
1824 zfs_btree_verify(tree); in zfs_btree_remove_idx()
1829 zfs_btree_remove(zfs_btree_t *tree, const void *value) in zfs_btree_remove() argument
1832 VERIFY3P(zfs_btree_find(tree, value, &where), !=, NULL); in zfs_btree_remove()
1833 zfs_btree_remove_idx(tree, &where); in zfs_btree_remove()
1838 zfs_btree_numnodes(zfs_btree_t *tree) in zfs_btree_numnodes() argument
1840 return (tree->bt_num_elems); in zfs_btree_numnodes()
1862 zfs_btree_destroy_nodes(zfs_btree_t *tree, zfs_btree_index_t **cookie) in zfs_btree_destroy_nodes() argument
1865 if (tree->bt_height == -1) in zfs_btree_destroy_nodes()
1868 return (zfs_btree_first(tree, *cookie)); in zfs_btree_destroy_nodes()
1871 void *rval = zfs_btree_next_helper(tree, *cookie, *cookie, in zfs_btree_destroy_nodes()
1874 tree->bt_root = NULL; in zfs_btree_destroy_nodes()
1875 tree->bt_height = -1; in zfs_btree_destroy_nodes()
1876 tree->bt_num_elems = 0; in zfs_btree_destroy_nodes()
1878 tree->bt_bulk = NULL; in zfs_btree_destroy_nodes()
1884 zfs_btree_clear_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr) in zfs_btree_clear_helper() argument
1889 zfs_btree_clear_helper(tree, btc->btc_children[i]); in zfs_btree_clear_helper()
1892 zfs_btree_node_destroy(tree, hdr); in zfs_btree_clear_helper()
1896 zfs_btree_clear(zfs_btree_t *tree) in zfs_btree_clear() argument
1898 if (tree->bt_root == NULL) { in zfs_btree_clear()
1899 ASSERT0(tree->bt_num_elems); in zfs_btree_clear()
1903 zfs_btree_clear_helper(tree, tree->bt_root); in zfs_btree_clear()
1904 tree->bt_num_elems = 0; in zfs_btree_clear()
1905 tree->bt_root = NULL; in zfs_btree_clear()
1906 tree->bt_num_nodes = 0; in zfs_btree_clear()
1907 tree->bt_height = -1; in zfs_btree_clear()
1908 tree->bt_bulk = NULL; in zfs_btree_clear()
1912 zfs_btree_destroy(zfs_btree_t *tree) in zfs_btree_destroy() argument
1914 ASSERT0(tree->bt_num_elems); in zfs_btree_destroy()
1915 ASSERT3P(tree->bt_root, ==, NULL); in zfs_btree_destroy()
1920 zfs_btree_verify_pointers_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr) in zfs_btree_verify_pointers_helper() argument
1928 zfs_btree_verify_pointers_helper(tree, node->btc_children[i]); in zfs_btree_verify_pointers_helper()
1934 zfs_btree_verify_pointers(zfs_btree_t *tree) in zfs_btree_verify_pointers() argument
1936 if (tree->bt_height == -1) { in zfs_btree_verify_pointers()
1937 VERIFY3P(tree->bt_root, ==, NULL); in zfs_btree_verify_pointers()
1940 VERIFY3P(tree->bt_root->bth_parent, ==, NULL); in zfs_btree_verify_pointers()
1941 zfs_btree_verify_pointers_helper(tree, tree->bt_root); in zfs_btree_verify_pointers()
1949 zfs_btree_verify_counts_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr) in zfs_btree_verify_counts_helper() argument
1952 if (tree->bt_root != hdr && tree->bt_bulk && in zfs_btree_verify_counts_helper()
1953 hdr != &tree->bt_bulk->btl_hdr) { in zfs_btree_verify_counts_helper()
1954 VERIFY3U(hdr->bth_count, >=, tree->bt_leaf_cap / 2 - 1); in zfs_btree_verify_counts_helper()
1962 if (tree->bt_root != hdr && tree->bt_bulk == NULL) in zfs_btree_verify_counts_helper()
1965 ret += zfs_btree_verify_counts_helper(tree, in zfs_btree_verify_counts_helper()
1978 zfs_btree_verify_counts(zfs_btree_t *tree) in zfs_btree_verify_counts() argument
1980 EQUIV(tree->bt_num_elems == 0, tree->bt_height == -1); in zfs_btree_verify_counts()
1981 if (tree->bt_height == -1) { in zfs_btree_verify_counts()
1984 VERIFY3P(zfs_btree_verify_counts_helper(tree, tree->bt_root), ==, in zfs_btree_verify_counts()
1985 tree->bt_num_elems); in zfs_btree_verify_counts()
1993 zfs_btree_verify_height_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr, in zfs_btree_verify_height_helper() argument
2004 ret += zfs_btree_verify_height_helper(tree, in zfs_btree_verify_height_helper()
2015 zfs_btree_verify_height(zfs_btree_t *tree) in zfs_btree_verify_height() argument
2017 EQUIV(tree->bt_height == -1, tree->bt_root == NULL); in zfs_btree_verify_height()
2018 if (tree->bt_height == -1) { in zfs_btree_verify_height()
2022 VERIFY3U(zfs_btree_verify_height_helper(tree, tree->bt_root, in zfs_btree_verify_height()
2023 tree->bt_height), ==, tree->bt_num_nodes); in zfs_btree_verify_height()
2032 zfs_btree_verify_order_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr) in zfs_btree_verify_order_helper() argument
2034 size_t size = tree->bt_elem_size; in zfs_btree_verify_order_helper()
2038 VERIFY3S(tree->bt_compar(leaf->btl_elems + in zfs_btree_verify_order_helper()
2048 VERIFY3S(tree->bt_compar(node->btc_elems + (i - 1) * size, in zfs_btree_verify_order_helper()
2066 int comp = tree->bt_compar(node->btc_elems + i * size, in zfs_btree_verify_order_helper()
2086 comp = tree->bt_compar(node->btc_elems + i * size, in zfs_btree_verify_order_helper()
2095 zfs_btree_verify_order_helper(tree, node->btc_children[i]); in zfs_btree_verify_order_helper()
2100 zfs_btree_verify_order(zfs_btree_t *tree) in zfs_btree_verify_order() argument
2102 EQUIV(tree->bt_height == -1, tree->bt_root == NULL); in zfs_btree_verify_order()
2103 if (tree->bt_height == -1) { in zfs_btree_verify_order()
2107 zfs_btree_verify_order_helper(tree, tree->bt_root); in zfs_btree_verify_order()
2113 zfs_btree_verify_poison_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr) in zfs_btree_verify_poison_helper() argument
2115 size_t size = tree->bt_elem_size; in zfs_btree_verify_poison_helper()
2136 zfs_btree_verify_poison_helper(tree, in zfs_btree_verify_poison_helper()
2145 zfs_btree_verify_poison(zfs_btree_t *tree) in zfs_btree_verify_poison() argument
2148 if (tree->bt_height == -1) in zfs_btree_verify_poison()
2150 zfs_btree_verify_poison_helper(tree, tree->bt_root); in zfs_btree_verify_poison()
2155 zfs_btree_verify(zfs_btree_t *tree) in zfs_btree_verify() argument
2159 zfs_btree_verify_height(tree); in zfs_btree_verify()
2162 zfs_btree_verify_pointers(tree); in zfs_btree_verify()
2165 zfs_btree_verify_counts(tree); in zfs_btree_verify()
2168 zfs_btree_verify_order(tree); in zfs_btree_verify()
2172 zfs_btree_verify_poison(tree); in zfs_btree_verify()