Lines Matching defs:hdr
75 zfs_btree_is_core(struct zfs_btree_hdr *hdr)
77 return (hdr->bth_first == -1);
87 zfs_btree_poison_node(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
91 if (zfs_btree_is_core(hdr)) {
92 zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
93 for (uint32_t i = hdr->bth_count + 1; i <= BTREE_CORE_ELEMS;
98 (void) memset(node->btc_elems + hdr->bth_count * size, 0x0f,
99 (BTREE_CORE_ELEMS - hdr->bth_count) * size);
101 zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
102 (void) memset(leaf->btl_elems, 0x0f, hdr->bth_first * size);
104 (hdr->bth_first + hdr->bth_count) * size, 0x0f,
106 (hdr->bth_first + hdr->bth_count) * size);
112 zfs_btree_poison_node_at(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
117 if (zfs_btree_is_core(hdr)) {
118 ASSERT3U(idx, >=, hdr->bth_count);
121 zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
130 zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
132 (hdr->bth_first + idx) * size, 0x0f, count * size);
138 zfs_btree_verify_poison_at(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
143 if (zfs_btree_is_core(hdr)) {
145 zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
152 zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
153 if (idx >= tree->bt_leaf_cap - hdr->bth_first)
156 VERIFY3U(leaf->btl_elems[(hdr->bth_first + idx)
483 zfs_btree_hdr_t *hdr = &node->btl_hdr;
484 ASSERT(!zfs_btree_is_core(hdr));
488 uint8_t *start = node->btl_elems + (hdr->bth_first + idx) * size;
501 zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
502 ASSERT(!zfs_btree_is_core(hdr));
503 ASSERT3U(idx, <=, hdr->bth_count);
505 ASSERT3U(hdr->bth_count + n, <=, capacity);
506 boolean_t cl = (hdr->bth_first >= n);
507 boolean_t cr = (hdr->bth_first + hdr->bth_count + n <= capacity);
509 if (cl && (!cr || idx <= hdr->bth_count / 2)) {
511 hdr->bth_first -= n;
515 bt_shift_leaf(tree, leaf, idx, hdr->bth_count - idx, n,
519 uint32_t fn = hdr->bth_first -
520 (capacity - (hdr->bth_count + n)) / 2;
521 hdr->bth_first -= fn;
523 bt_shift_leaf(tree, leaf, fn + idx, hdr->bth_count - idx,
526 hdr->bth_count += n;
536 zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
537 ASSERT(!zfs_btree_is_core(hdr));
538 ASSERT3U(idx, <=, hdr->bth_count);
539 ASSERT3U(idx + n, <=, hdr->bth_count);
541 if (idx <= (hdr->bth_count - n) / 2) {
543 zfs_btree_poison_node_at(tree, hdr, 0, n);
544 hdr->bth_first += n;
546 bt_shift_leaf(tree, leaf, idx + n, hdr->bth_count - idx - n, n,
548 zfs_btree_poison_node_at(tree, hdr, hdr->bth_count - n, n);
550 hdr->bth_count -= n;
589 * Find the first element in the subtree rooted at hdr, return its value and
593 zfs_btree_first_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
598 for (node = hdr; zfs_btree_is_core(node);
794 zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
803 uint8_t *start = leaf->btl_elems + (hdr->bth_first + idx) * size;
808 zfs_btree_verify_order_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr);
897 zfs_btree_find_parent_idx(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
900 if (zfs_btree_is_core(hdr)) {
901 buf = ((zfs_btree_core_t *)hdr)->btc_elems;
903 buf = ((zfs_btree_leaf_t *)hdr)->btl_elems +
904 hdr->bth_first * tree->bt_elem_size;
907 zfs_btree_core_t *parent = hdr->bth_parent;
912 ASSERT3P(parent->btc_children[idx.bti_offset], ==, hdr);
931 zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
932 zfs_btree_core_t *parent = hdr->bth_parent;
946 if (hdr->bth_count < capacity / 2) {
955 .bti_node = hdr,
967 uint32_t move_count = (capacity / 2) - hdr->bth_count;
973 zfs_btree_verify_poison_at(tree, hdr,
984 (hdr->bth_first + move_count - 1) * size;
1006 ASSERT3U(hdr->bth_count, >=, capacity / 2);
1016 zfs_btree_hdr_t *hdr = &cur->btc_hdr;
1017 parent = hdr->bth_parent;
1022 if (hdr->bth_count >= capacity / 2)
1030 uint32_t parent_idx = zfs_btree_find_parent_idx(tree, hdr);
1034 uint32_t move_count = (capacity / 2) - hdr->bth_count;
1040 zfs_btree_verify_poison_at(tree, hdr,
1041 hdr->bth_count + i);
1045 bt_shift_core(tree, cur, 0, hdr->bth_count, move_count,
1071 hdr->bth_count += move_count + 1;
1074 ASSERT3U(hdr->bth_count, >=, capacity / 2);
1078 for (uint32_t i = 0; i <= hdr->bth_count; i++)
1120 zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
1121 hdr->bth_parent = NULL;
1122 hdr->bth_first = 0;
1123 hdr->bth_count = 0;
1124 zfs_btree_poison_node(tree, hdr);
1188 * Find the last element in the subtree rooted at hdr, return its value and
1192 zfs_btree_last_helper(zfs_btree_t *btree, zfs_btree_hdr_t *hdr,
1197 for (node = hdr; zfs_btree_is_core(node); node =
1265 zfs_btree_hdr_t *hdr = &node->btc_hdr;
1266 ASSERT(zfs_btree_is_core(hdr));
1270 if (i == hdr->bth_count) {
1271 prev = hdr;
1274 out_idx->bti_node = hdr;
1350 zfs_btree_hdr_t *hdr = &node->btc_hdr;
1351 ASSERT(zfs_btree_is_core(hdr));
1354 prev = hdr;
1357 out_idx->bti_node = hdr;
1433 zfs_btree_hdr_t *hdr = &node->btc_hdr;
1438 if (hdr->bth_parent == NULL && hdr->bth_count <= 1) {
1439 ASSERT3U(hdr->bth_count, ==, 1);
1444 zfs_btree_node_destroy(tree, hdr);
1450 for (idx = 0; idx <= hdr->bth_count; idx++) {
1454 ASSERT3U(idx, <=, hdr->bth_count);
1460 if (hdr->bth_parent == NULL ||
1461 hdr->bth_count > min_count) {
1466 bt_shift_core_left(tree, node, idx, hdr->bth_count - idx,
1468 hdr->bth_count--;
1469 zfs_btree_poison_node_at(tree, hdr, hdr->bth_count, 1);
1473 ASSERT3U(hdr->bth_count, ==, min_count);
1489 zfs_btree_core_t *parent = hdr->bth_parent;
1490 uint32_t parent_idx = zfs_btree_find_parent_idx(tree, hdr);
1538 bt_shift_core_left(tree, node, idx, hdr->bth_count - idx,
1546 bcpy(separator, node->btc_elems + (hdr->bth_count - 1) * size,
1553 node->btc_children[hdr->bth_count] = neighbor->btc_children[0];
1554 node->btc_children[hdr->bth_count]->bth_parent = node;
1585 new_rm_hdr = hdr;
1589 keep_hdr = hdr;
1654 zfs_btree_hdr_t *hdr = where->bti_node;
1671 hdr = where->bti_node;
1682 if (zfs_btree_is_core(hdr)) {
1683 zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
1691 hdr = where->bti_node;
1701 ASSERT(!zfs_btree_is_core(hdr));
1702 zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
1703 ASSERT3U(hdr->bth_count, >, 0);
1711 if (hdr->bth_count > min_count || hdr->bth_parent == NULL) {
1713 if (hdr->bth_parent == NULL) {
1715 if (hdr->bth_count == 0) {
1724 ASSERT3U(hdr->bth_count, ==, min_count);
1739 zfs_btree_core_t *parent = hdr->bth_parent;
1740 uint32_t parent_idx = zfs_btree_find_parent_idx(tree, hdr);
1758 bcpy(separator, leaf->btl_elems + hdr->bth_first * size, size);
1783 bt_shift_leaf(tree, leaf, idx + 1, hdr->bth_count - idx - 1,
1788 bcpy(separator, leaf->btl_elems + (hdr->bth_first +
1789 hdr->bth_count - 1) * size, size);
1815 rm_hdr = hdr;
1818 k_hdr = hdr;
1918 zfs_btree_clear_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
1920 if (zfs_btree_is_core(hdr)) {
1921 zfs_btree_core_t *btc = (zfs_btree_core_t *)hdr;
1922 for (uint32_t i = 0; i <= hdr->bth_count; i++)
1926 zfs_btree_node_destroy(tree, hdr);
1954 zfs_btree_verify_pointers_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
1956 if (!zfs_btree_is_core(hdr))
1959 zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
1960 for (uint32_t i = 0; i <= hdr->bth_count; i++) {
1961 VERIFY3P(node->btc_children[i]->bth_parent, ==, hdr);
1983 zfs_btree_verify_counts_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
1985 if (!zfs_btree_is_core(hdr)) {
1986 if (tree->bt_root != hdr && tree->bt_bulk &&
1987 hdr != &tree->bt_bulk->btl_hdr) {
1988 VERIFY3U(hdr->bth_count, >=, tree->bt_leaf_cap / 2 - 1);
1991 return (hdr->bth_count);
1994 zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
1995 uint64_t ret = hdr->bth_count;
1996 if (tree->bt_root != hdr && tree->bt_bulk == NULL)
1997 VERIFY3P(hdr->bth_count, >=, BTREE_CORE_ELEMS / 2 - 1);
1998 for (uint32_t i = 0; i <= hdr->bth_count; i++) {
2027 zfs_btree_verify_height_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
2030 if (!zfs_btree_is_core(hdr)) {
2035 zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
2037 for (uint32_t i = 0; i <= hdr->bth_count; i++) {
2066 zfs_btree_verify_order_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
2069 if (!zfs_btree_is_core(hdr)) {
2070 zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
2071 for (uint32_t i = 1; i < hdr->bth_count; i++) {
2073 (hdr->bth_first + i - 1) * size,
2075 (hdr->bth_first + i) * size), ==, -1);
2080 zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
2081 for (uint32_t i = 1; i < hdr->bth_count; i++) {
2085 for (uint32_t i = 0; i < hdr->bth_count; i++) {
2128 for (uint32_t i = 0; i <= hdr->bth_count; i++)
2147 zfs_btree_verify_poison_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
2150 if (!zfs_btree_is_core(hdr)) {
2151 zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
2152 for (size_t i = 0; i < hdr->bth_first * size; i++)
2156 for (size_t i = (hdr->bth_first + hdr->bth_count) * size;
2160 zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
2161 for (size_t i = hdr->bth_count * size;
2165 for (uint32_t i = hdr->bth_count + 1; i <= BTREE_CORE_ELEMS;
2171 for (uint32_t i = 0; i <= hdr->bth_count; i++) {