Lines Matching +full:in +full:- +full:tree
6 * You may only use this file in accordance with the terms of version
32 * Intensity 1: Verify that the tree's height is consistent throughout.
35 * Intensity 3: Verify that the total number of elements in the tree matches the
36 * sum of the number of elements in each node. Also verifies that each node's
42 * than the last element in the first of the two nodes it separates, and less
43 * than the first element in the second of the two nodes.
51 * operations per element. In addition, when creating large btrees, these
52 * operations are called at every step, resulting in extremely slow operation
77 return (hdr->bth_first == -1);
87 zfs_btree_poison_node(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
90 size_t size = tree->bt_elem_size;
93 for (uint32_t i = hdr->bth_count + 1; i <= BTREE_CORE_ELEMS;
95 node->btc_children[i] =
98 (void) memset(node->btc_elems + hdr->bth_count * size, 0x0f,
99 (BTREE_CORE_ELEMS - hdr->bth_count) * size);
102 (void) memset(leaf->btl_elems, 0x0f, hdr->bth_first * size);
103 (void) memset(leaf->btl_elems +
104 (hdr->bth_first + hdr->bth_count) * size, 0x0f,
105 tree->bt_leaf_size - offsetof(zfs_btree_leaf_t, btl_elems) -
106 (hdr->bth_first + hdr->bth_count) * size);
112 zfs_btree_poison_node_at(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
116 size_t size = tree->bt_elem_size;
118 ASSERT3U(idx, >=, hdr->bth_count);
123 node->btc_children[idx + i] =
126 (void) memset(node->btc_elems + idx * size, 0x0f, count * size);
128 ASSERT3U(idx, <=, tree->bt_leaf_cap);
129 ASSERT3U(idx + count, <=, tree->bt_leaf_cap);
131 (void) memset(leaf->btl_elems +
132 (hdr->bth_first + idx) * size, 0x0f, count * size);
138 zfs_btree_verify_poison_at(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
142 size_t size = tree->bt_elem_size;
147 VERIFY3P(node->btc_children[idx + 1], ==, cval);
149 VERIFY3U(node->btc_elems[idx * size + i], ==, 0x0f);
151 ASSERT3U(idx, <, tree->bt_leaf_cap);
153 if (idx >= tree->bt_leaf_cap - hdr->bth_first)
156 VERIFY3U(leaf->btl_elems[(hdr->bth_first + idx)
177 zfs_btree_leaf_alloc(zfs_btree_t *tree)
179 if (tree->bt_leaf_size == BTREE_LEAF_SIZE)
182 return (kmem_alloc(tree->bt_leaf_size, KM_SLEEP));
186 zfs_btree_leaf_free(zfs_btree_t *tree, void *ptr)
188 if (tree->bt_leaf_size == BTREE_LEAF_SIZE)
191 return (kmem_free(ptr, tree->bt_leaf_size));
195 zfs_btree_create(zfs_btree_t *tree, int (*compar) (const void *, const void *),
198 zfs_btree_create_custom(tree, compar, bt_find_in_buf, size,
203 zfs_btree_find_in_buf(zfs_btree_t *tree, uint8_t *buf, uint32_t nelems,
207 zfs_btree_create_custom(zfs_btree_t *tree,
212 size_t esize = lsize - offsetof(zfs_btree_leaf_t, btl_elems);
215 memset(tree, 0, sizeof (*tree));
216 tree->bt_compar = compar;
217 tree->bt_find_in_buf = (bt_find_in_buf == NULL) ?
219 tree->bt_elem_size = size;
220 tree->bt_leaf_size = lsize;
221 tree->bt_leaf_cap = P2ALIGN_TYPED(esize / size, 2, size_t);
222 tree->bt_height = -1;
223 tree->bt_bulk = NULL;
227 * Find value in the array of elements provided. Uses a simple binary search.
230 zfs_btree_find_in_buf(zfs_btree_t *tree, uint8_t *buf, uint32_t nelems,
237 uint8_t *cur = buf + idx * tree->bt_elem_size;
238 int comp = tree->bt_compar(cur, value);
244 where->bti_offset = idx;
245 where->bti_before = B_FALSE;
250 where->bti_offset = max;
251 where->bti_before = B_TRUE;
256 * Find the given value in the tree. where may be passed as null to use as a
260 zfs_btree_find(zfs_btree_t *tree, const void *value, zfs_btree_index_t *where)
262 if (tree->bt_height == -1) {
264 where->bti_node = NULL;
265 where->bti_offset = 0;
267 ASSERT0(tree->bt_num_elems);
272 * If we're in bulk-insert mode, we check the last spot in the tree
273 * and the last leaf in the tree before doing the normal search,
274 * because for most workloads the vast majority of finds in
275 * bulk-insert mode are to insert new elements.
278 size_t size = tree->bt_elem_size;
279 if (tree->bt_bulk != NULL) {
280 zfs_btree_leaf_t *last_leaf = tree->bt_bulk;
281 int comp = tree->bt_compar(last_leaf->btl_elems +
282 (last_leaf->btl_hdr.bth_first +
283 last_leaf->btl_hdr.bth_count - 1) * size, value);
287 * element, it's not in the tree.
290 where->bti_node = (zfs_btree_hdr_t *)last_leaf;
291 where->bti_offset =
292 last_leaf->btl_hdr.bth_count;
293 where->bti_before = B_TRUE;
298 where->bti_node = (zfs_btree_hdr_t *)last_leaf;
299 where->bti_offset =
300 last_leaf->btl_hdr.bth_count - 1;
301 where->bti_before = B_FALSE;
303 return (last_leaf->btl_elems +
304 (last_leaf->btl_hdr.bth_first +
305 last_leaf->btl_hdr.bth_count - 1) * size);
307 if (tree->bt_compar(last_leaf->btl_elems +
308 last_leaf->btl_hdr.bth_first * size, value) <= 0) {
311 * element in the last leaf, it's in the last leaf or
312 * it's not in the tree.
314 void *d = tree->bt_find_in_buf(tree,
315 last_leaf->btl_elems +
316 last_leaf->btl_hdr.bth_first * size,
317 last_leaf->btl_hdr.bth_count, value, &idx);
332 * Iterate down the tree, finding which child the value should be in
335 for (node = (zfs_btree_core_t *)tree->bt_root; depth < tree->bt_height;
336 node = (zfs_btree_core_t *)node->btc_children[child], depth++) {
338 void *d = tree->bt_find_in_buf(tree, node->btc_elems,
339 node->btc_hdr.bth_count, value, &idx);
353 * The value is in this leaf, or it would be if it were in the
354 * tree. Find its proper location and return it.
357 (zfs_btree_leaf_t *)tree->bt_root : (zfs_btree_leaf_t *)node);
358 void *d = tree->bt_find_in_buf(tree, leaf->btl_elems +
359 leaf->btl_hdr.bth_first * size,
360 leaf->btl_hdr.bth_count, value, &idx);
372 * kinds of shifts used in btree operation. First, a shift is a movement of
388 * current node. A left and right shift are fairly self-explanatory; a left
398 * ---------------
403 * ---------------
405 * Note that a parallelogram shift is always shaped like a "left-leaning"
408 * "right-leaning" parallelogram shifts are needed (shifts where the starting
424 * Shift elements and children in the provided core node by off spots. The
429 bt_shift_core(zfs_btree_t *tree, zfs_btree_core_t *node, uint32_t idx,
433 size_t size = tree->bt_elem_size;
434 ASSERT(zfs_btree_is_core(&node->btc_hdr));
436 uint8_t *e_start = node->btc_elems + idx * size;
437 uint8_t *e_out = (dir == BSD_LEFT ? e_start - off * size :
441 zfs_btree_hdr_t **c_start = node->btc_children + idx +
443 zfs_btree_hdr_t **c_out = (dir == BSD_LEFT ? c_start - off :
450 * Shift elements and children in the provided core node left by one spot.
456 bt_shift_core_left(zfs_btree_t *tree, zfs_btree_core_t *node, uint32_t idx,
459 bt_shift_core(tree, node, idx, count, 1, shape, BSD_LEFT);
463 * Shift elements and children in the provided core node right by one spot.
467 bt_shift_core_right(zfs_btree_t *tree, zfs_btree_core_t *node, uint32_t idx,
470 bt_shift_core(tree, node, idx, count, 1, shape, BSD_RIGHT);
474 * Shift elements and children in the provided leaf node by off spots.
479 bt_shift_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *node, uint32_t idx,
482 size_t size = tree->bt_elem_size;
483 zfs_btree_hdr_t *hdr = &node->btl_hdr;
488 uint8_t *start = node->btl_elems + (hdr->bth_first + idx) * size;
489 uint8_t *out = (dir == BSD_LEFT ? start - off * size :
498 bt_grow_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *leaf, uint32_t idx,
501 zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
503 ASSERT3U(idx, <=, hdr->bth_count);
504 uint32_t capacity = tree->bt_leaf_cap;
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;
512 bt_shift_leaf(tree, leaf, n, idx, n, BSD_LEFT);
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;
522 bt_shift_leaf(tree, leaf, fn, idx, fn, BSD_LEFT);
523 bt_shift_leaf(tree, leaf, fn + idx, hdr->bth_count - idx,
524 n - fn, BSD_RIGHT);
526 hdr->bth_count += n;
533 bt_shrink_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *leaf, uint32_t idx,
536 zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
538 ASSERT3U(idx, <=, hdr->bth_count);
539 ASSERT3U(idx + n, <=, hdr->bth_count);
541 if (idx <= (hdr->bth_count - n) / 2) {
542 bt_shift_leaf(tree, leaf, 0, idx, n, BSD_RIGHT);
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;
555 * parameter behaves the same as it does in the shift logic.
558 bt_transfer_core(zfs_btree_t *tree, zfs_btree_core_t *source, uint32_t sidx,
562 size_t size = tree->bt_elem_size;
563 ASSERT(zfs_btree_is_core(&source->btc_hdr));
564 ASSERT(zfs_btree_is_core(&dest->btc_hdr));
566 bcpy(source->btc_elems + sidx * size, dest->btc_elems + didx * size,
570 bcpy(source->btc_children + sidx + (shape == BSS_TRAPEZOID ? 0 : 1),
571 dest->btc_children + didx + (shape == BSS_TRAPEZOID ? 0 : 1),
572 c_count * sizeof (*source->btc_children));
576 bt_transfer_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *source, uint32_t sidx,
579 size_t size = tree->bt_elem_size;
580 ASSERT(!zfs_btree_is_core(&source->btl_hdr));
581 ASSERT(!zfs_btree_is_core(&dest->btl_hdr));
583 bcpy(source->btl_elems + (source->btl_hdr.bth_first + sidx) * size,
584 dest->btl_elems + (dest->btl_hdr.bth_first + didx) * size,
589 * Find the first element in the subtree rooted at hdr, return its value and
590 * put its location in where if non-null.
593 zfs_btree_first_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
599 node = ((zfs_btree_core_t *)node)->btc_children[0])
605 where->bti_node = node;
606 where->bti_offset = 0;
607 where->bti_before = B_FALSE;
609 return (&leaf->btl_elems[node->bth_first * tree->bt_elem_size]);
614 zfs_btree_insert_core_impl(zfs_btree_t *tree, zfs_btree_core_t *parent,
617 size_t size = tree->bt_elem_size;
618 zfs_btree_hdr_t *par_hdr = &parent->btc_hdr;
619 ASSERT3P(par_hdr, ==, new_node->bth_parent);
620 ASSERT3U(par_hdr->bth_count, <, BTREE_CORE_ELEMS);
623 zfs_btree_verify_poison_at(tree, par_hdr,
624 par_hdr->bth_count);
627 uint32_t count = par_hdr->bth_count - offset;
628 bt_shift_core_right(tree, parent, offset, count,
632 parent->btc_children[offset + 1] = new_node;
633 bcpy(buf, parent->btc_elems + offset * size, size);
634 par_hdr->bth_count++;
642 zfs_btree_insert_into_parent(zfs_btree_t *tree, zfs_btree_hdr_t *old_node,
645 ASSERT3P(old_node->bth_parent, ==, new_node->bth_parent);
646 size_t size = tree->bt_elem_size;
647 zfs_btree_core_t *parent = old_node->bth_parent;
651 * and increase the height of the tree.
654 ASSERT3P(old_node, ==, tree->bt_root);
655 tree->bt_num_nodes++;
659 zfs_btree_hdr_t *new_root_hdr = &new_root->btc_hdr;
660 new_root_hdr->bth_parent = NULL;
661 new_root_hdr->bth_first = -1;
662 new_root_hdr->bth_count = 1;
664 old_node->bth_parent = new_node->bth_parent = new_root;
665 new_root->btc_children[0] = old_node;
666 new_root->btc_children[1] = new_node;
667 bcpy(buf, new_root->btc_elems, size);
669 tree->bt_height++;
670 tree->bt_root = new_root_hdr;
671 zfs_btree_poison_node(tree, new_root_hdr);
679 zfs_btree_hdr_t *par_hdr = &parent->btc_hdr;
682 VERIFY3P(tree->bt_find_in_buf(tree, parent->btc_elems,
683 par_hdr->bth_count, buf, &idx), ==, NULL);
686 ASSERT3U(offset, <=, par_hdr->bth_count);
687 ASSERT3P(parent->btc_children[offset], ==, old_node);
693 if (par_hdr->bth_count != BTREE_CORE_ELEMS) {
694 zfs_btree_insert_core_impl(tree, parent, offset, new_node, buf);
704 * will be used as the new separator in our parent, and the others
707 * Usually we will split the node in half evenly, with
708 * BTREE_CORE_ELEMS/2 elements in each node. If we're bulk loading, we
713 * We do this in two stages: first we split into two nodes, and then we
716 uint32_t move_count = MAX((BTREE_CORE_ELEMS / (tree->bt_bulk == NULL ?
717 2 : 4)) - 1, 2);
718 uint32_t keep_count = BTREE_CORE_ELEMS - move_count - 1;
719 ASSERT3U(BTREE_CORE_ELEMS - move_count, >=, 2);
720 tree->bt_num_nodes++;
723 zfs_btree_hdr_t *new_par_hdr = &new_parent->btc_hdr;
724 new_par_hdr->bth_parent = par_hdr->bth_parent;
725 new_par_hdr->bth_first = -1;
726 new_par_hdr->bth_count = move_count;
727 zfs_btree_poison_node(tree, new_par_hdr);
729 par_hdr->bth_count = keep_count;
731 bt_transfer_core(tree, parent, keep_count + 1, move_count, new_parent,
734 /* Store the new separator in a buffer. */
736 bcpy(parent->btc_elems + keep_count * size, tmp_buf,
738 zfs_btree_poison_node(tree, par_hdr);
742 zfs_btree_insert_core_impl(tree, parent, offset, new_node,
751 new_node->bth_parent = new_parent;
752 zfs_btree_insert_core_impl(tree, new_parent,
753 offset - keep_count - 1, new_node, buf);
762 * with buf. We also need to shift back the elements in the
765 bt_shift_core_right(tree, new_parent, 0, move_count,
767 new_parent->btc_children[0] = new_node;
768 bcpy(tmp_buf, new_parent->btc_elems, size);
769 new_par_hdr->bth_count++;
772 zfs_btree_poison_node(tree, par_hdr);
774 for (uint32_t i = 0; i <= new_parent->btc_hdr.bth_count; i++)
775 new_parent->btc_children[i]->bth_parent = new_parent;
777 for (uint32_t i = 0; i <= parent->btc_hdr.bth_count; i++)
778 ASSERT3P(parent->btc_children[i]->bth_parent, ==, parent);
784 zfs_btree_insert_into_parent(tree, &parent->btc_hdr,
785 &new_parent->btc_hdr, buf);
790 zfs_btree_insert_leaf_impl(zfs_btree_t *tree, zfs_btree_leaf_t *leaf,
793 size_t size = tree->bt_elem_size;
794 zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
795 ASSERT3U(leaf->btl_hdr.bth_count, <, tree->bt_leaf_cap);
798 zfs_btree_verify_poison_at(tree, &leaf->btl_hdr,
799 leaf->btl_hdr.bth_count);
802 bt_grow_leaf(tree, leaf, idx, 1);
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);
812 zfs_btree_insert_into_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *leaf,
815 size_t size = tree->bt_elem_size;
816 uint32_t capacity = tree->bt_leaf_cap;
822 if (leaf->btl_hdr.bth_count != capacity) {
823 zfs_btree_insert_leaf_impl(tree, leaf, idx, value);
832 * tree stays relatively dense. Since the average state after a long
838 * In either case, we're left with one extra element. The leftover
841 uint32_t move_count = MAX(capacity / (tree->bt_bulk ? 4 : 2), 1) - 1;
842 uint32_t keep_count = capacity - move_count - 1;
846 keep_count--;
849 tree->bt_num_nodes++;
850 zfs_btree_leaf_t *new_leaf = zfs_btree_leaf_alloc(tree);
851 zfs_btree_hdr_t *new_hdr = &new_leaf->btl_hdr;
852 new_hdr->bth_parent = leaf->btl_hdr.bth_parent;
853 new_hdr->bth_first = (tree->bt_bulk ? 0 : capacity / 4) +
855 new_hdr->bth_count = move_count;
856 zfs_btree_poison_node(tree, new_hdr);
858 if (tree->bt_bulk != NULL && leaf == tree->bt_bulk)
859 tree->bt_bulk = new_leaf;
862 bt_transfer_leaf(tree, leaf, keep_count + 1, move_count, new_leaf, 0);
864 /* We store the new separator in a buffer we control for simplicity. */
866 bcpy(leaf->btl_elems + (leaf->btl_hdr.bth_first + keep_count) * size,
869 bt_shrink_leaf(tree, leaf, keep_count, 1 + move_count);
873 zfs_btree_insert_leaf_impl(tree, leaf, idx, value);
876 zfs_btree_insert_leaf_impl(tree, new_leaf, idx - keep_count -
883 zfs_btree_insert_leaf_impl(tree, new_leaf, 0, buf);
891 zfs_btree_insert_into_parent(tree, &leaf->btl_hdr, &new_leaf->btl_hdr,
897 zfs_btree_find_parent_idx(zfs_btree_t *tree, zfs_btree_hdr_t *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;
908 VERIFY3P(tree->bt_find_in_buf(tree, parent->btc_elems,
909 parent->btc_hdr.bth_count, buf, &idx), ==, NULL);
911 ASSERT3U(idx.bti_offset, <=, parent->btc_hdr.bth_count);
912 ASSERT3P(parent->btc_children[idx.bti_offset], ==, hdr);
917 * Take the b-tree out of bulk insert mode. During bulk-insert mode, some
918 * nodes may violate the invariant that non-root nodes must be at least half
919 * full. All nodes violating this invariant should be the last node in their
926 zfs_btree_bulk_finish(zfs_btree_t *tree)
928 ASSERT3P(tree->bt_bulk, !=, NULL);
929 ASSERT3P(tree->bt_root, !=, NULL);
930 zfs_btree_leaf_t *leaf = tree->bt_bulk;
931 zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
932 zfs_btree_core_t *parent = hdr->bth_parent;
933 size_t size = tree->bt_elem_size;
934 uint32_t capacity = tree->bt_leaf_cap;
938 * node in the tree we're done.
941 tree->bt_bulk = NULL;
946 if (hdr->bth_count < capacity / 2) {
958 VERIFY3P(zfs_btree_prev(tree, &idx, &idx), !=, NULL);
963 VERIFY3P(zfs_btree_prev(tree, &idx, &idx), !=, NULL);
967 uint32_t move_count = (capacity / 2) - hdr->bth_count;
968 ASSERT3U(l_neighbor->btl_hdr.bth_count - move_count, >=,
973 zfs_btree_verify_poison_at(tree, hdr,
974 leaf->btl_hdr.bth_count + i);
978 /* First, shift elements in leaf back. */
979 bt_grow_leaf(tree, leaf, 0, move_count);
982 uint8_t *separator = common->btc_elems + common_idx * size;
983 uint8_t *out = leaf->btl_elems +
984 (hdr->bth_first + move_count - 1) * size;
989 * fill the remaining spots in leaf.
991 bt_transfer_leaf(tree, l_neighbor, l_hdr->bth_count -
992 (move_count - 1), move_count - 1, leaf, 0);
995 * Finally, move the new last element in the left neighbor to
998 bcpy(l_neighbor->btl_elems + (l_hdr->bth_first +
999 l_hdr->bth_count - move_count) * size, separator, size);
1002 bt_shrink_leaf(tree, l_neighbor, l_hdr->bth_count - move_count,
1005 ASSERT3U(l_hdr->bth_count, >=, capacity / 2);
1006 ASSERT3U(hdr->bth_count, >=, capacity / 2);
1014 while (parent->btc_hdr.bth_parent != NULL) {
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);
1033 (zfs_btree_core_t *)parent->btc_children[parent_idx - 1];
1034 uint32_t move_count = (capacity / 2) - hdr->bth_count;
1035 ASSERT3U(l_neighbor->btc_hdr.bth_count - move_count, >=,
1040 zfs_btree_verify_poison_at(tree, hdr,
1041 hdr->bth_count + i);
1044 /* First, shift things in the right node back. */
1045 bt_shift_core(tree, cur, 0, hdr->bth_count, move_count,
1049 uint8_t *separator = parent->btc_elems + ((parent_idx - 1) *
1051 uint8_t *e_out = cur->btc_elems + ((move_count - 1) * size);
1058 move_count--;
1059 uint32_t move_idx = l_neighbor->btc_hdr.bth_count - move_count;
1060 bt_transfer_core(tree, l_neighbor, move_idx, move_count, cur, 0,
1064 * Finally, move the last element in the left node to the
1067 move_idx--;
1068 bcpy(l_neighbor->btc_elems + move_idx * size, separator, size);
1070 l_neighbor->btc_hdr.bth_count -= move_count + 1;
1071 hdr->bth_count += move_count + 1;
1073 ASSERT3U(l_neighbor->btc_hdr.bth_count, >=, capacity / 2);
1074 ASSERT3U(hdr->bth_count, >=, capacity / 2);
1076 zfs_btree_poison_node(tree, &l_neighbor->btc_hdr);
1078 for (uint32_t i = 0; i <= hdr->bth_count; i++)
1079 cur->btc_children[i]->bth_parent = cur;
1082 tree->bt_bulk = NULL;
1083 zfs_btree_verify(tree);
1087 * Insert value into tree at the location specified by where.
1090 zfs_btree_add_idx(zfs_btree_t *tree, const void *value,
1095 /* If we're not inserting in the last leaf, end bulk insert mode. */
1096 if (tree->bt_bulk != NULL) {
1097 if (where->bti_node != &tree->bt_bulk->btl_hdr) {
1098 zfs_btree_bulk_finish(tree);
1099 VERIFY3P(zfs_btree_find(tree, value, &idx), ==, NULL);
1104 tree->bt_num_elems++;
1106 * If this is the first element in the tree, create a leaf root node
1109 if (where->bti_node == NULL) {
1110 ASSERT3U(tree->bt_num_elems, ==, 1);
1111 ASSERT3S(tree->bt_height, ==, -1);
1112 ASSERT3P(tree->bt_root, ==, NULL);
1113 ASSERT0(where->bti_offset);
1115 tree->bt_num_nodes++;
1116 zfs_btree_leaf_t *leaf = zfs_btree_leaf_alloc(tree);
1117 tree->bt_root = &leaf->btl_hdr;
1118 tree->bt_height++;
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);
1126 zfs_btree_insert_into_leaf(tree, leaf, value, 0);
1127 tree->bt_bulk = leaf;
1128 } else if (!zfs_btree_is_core(where->bti_node)) {
1133 zfs_btree_insert_into_leaf(tree,
1134 (zfs_btree_leaf_t *)where->bti_node, value,
1135 where->bti_offset);
1139 * the existing element in that slot in the same node without
1141 * value in the node at that spot and then insert the old
1142 * separator into the first slot in the subtree to the right.
1144 zfs_btree_core_t *node = (zfs_btree_core_t *)where->bti_node;
1148 * should end up in bti_offset.
1150 uint32_t off = where->bti_offset;
1151 zfs_btree_hdr_t *subtree = node->btc_children[off + 1];
1152 size_t size = tree->bt_elem_size;
1154 bcpy(node->btc_elems + off * size, buf, size);
1155 bcpy(value, node->btc_elems + off * size, size);
1158 * Find the first slot in the subtree to the right, insert
1162 VERIFY3P(zfs_btree_first_helper(tree, subtree, &new_idx), !=,
1166 zfs_btree_insert_into_leaf(tree,
1170 zfs_btree_verify(tree);
1174 * Return the first element in the tree, and put its location in where if
1175 * non-null.
1178 zfs_btree_first(zfs_btree_t *tree, zfs_btree_index_t *where)
1180 if (tree->bt_height == -1) {
1181 ASSERT0(tree->bt_num_elems);
1184 return (zfs_btree_first_helper(tree, tree->bt_root, where));
1188 * Find the last element in the subtree rooted at hdr, return its value and
1189 * put its location in where if non-null.
1198 ((zfs_btree_core_t *)node)->btc_children[node->bth_count])
1203 where->bti_node = node;
1204 where->bti_offset = node->bth_count - 1;
1205 where->bti_before = B_FALSE;
1207 return (leaf->btl_elems + (node->bth_first + node->bth_count - 1) *
1208 btree->bt_elem_size);
1212 * Return the last element in the tree, and put its location in where if
1213 * non-null.
1216 zfs_btree_last(zfs_btree_t *tree, zfs_btree_index_t *where)
1218 if (tree->bt_height == -1) {
1219 ASSERT0(tree->bt_num_elems);
1222 return (zfs_btree_last_helper(tree, tree->bt_root, where));
1226 * This function contains the logic to find the next node in the tree. A
1232 zfs_btree_next_helper(zfs_btree_t *tree, const zfs_btree_index_t *idx,
1236 if (idx->bti_node == NULL) {
1237 ASSERT3S(tree->bt_height, ==, -1);
1241 uint32_t offset = idx->bti_offset;
1242 if (!zfs_btree_is_core(idx->bti_node)) {
1244 * When finding the next element of an element in a leaf,
1245 * there are two cases. If the element isn't the last one in
1246 * the leaf, in which case we just return the next element in
1250 * separator after our ancestor in its parent.
1252 zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)idx->bti_node;
1253 uint32_t new_off = offset + (idx->bti_before ? 0 : 1);
1254 if (leaf->btl_hdr.bth_count > new_off) {
1255 out_idx->bti_node = &leaf->btl_hdr;
1256 out_idx->bti_offset = new_off;
1257 out_idx->bti_before = B_FALSE;
1258 return (leaf->btl_elems + (leaf->btl_hdr.bth_first +
1259 new_off) * tree->bt_elem_size);
1262 zfs_btree_hdr_t *prev = &leaf->btl_hdr;
1263 for (zfs_btree_core_t *node = leaf->btl_hdr.bth_parent;
1264 node != NULL; node = node->btc_hdr.bth_parent) {
1265 zfs_btree_hdr_t *hdr = &node->btc_hdr;
1267 uint32_t i = zfs_btree_find_parent_idx(tree, prev);
1269 done_func(tree, prev);
1270 if (i == hdr->bth_count) {
1274 out_idx->bti_node = hdr;
1275 out_idx->bti_offset = i;
1276 out_idx->bti_before = B_FALSE;
1277 return (node->btc_elems + i * tree->bt_elem_size);
1280 done_func(tree, prev);
1283 * node every time, so this was the last element in the tree.
1288 /* If we were before an element in a core node, return that element. */
1289 ASSERT(zfs_btree_is_core(idx->bti_node));
1290 zfs_btree_core_t *node = (zfs_btree_core_t *)idx->bti_node;
1291 if (idx->bti_before) {
1292 out_idx->bti_before = B_FALSE;
1293 return (node->btc_elems + offset * tree->bt_elem_size);
1297 * The next element from one in a core node is the first element in
1300 zfs_btree_hdr_t *child = node->btc_children[offset + 1];
1301 return (zfs_btree_first_helper(tree, child, out_idx));
1305 * Return the next valued node in the tree. The same address can be safely
1309 zfs_btree_next(zfs_btree_t *tree, const zfs_btree_index_t *idx,
1312 return (zfs_btree_next_helper(tree, idx, out_idx, NULL));
1316 * Return the previous valued node in the tree. The same value can be safely
1320 zfs_btree_prev(zfs_btree_t *tree, const zfs_btree_index_t *idx,
1323 if (idx->bti_node == NULL) {
1324 ASSERT3S(tree->bt_height, ==, -1);
1328 uint32_t offset = idx->bti_offset;
1329 if (!zfs_btree_is_core(idx->bti_node)) {
1331 * When finding the previous element of an element in a leaf,
1332 * there are two cases. If the element isn't the first one in
1333 * the leaf, in which case we just return the previous element
1334 * in the leaf. Otherwise, we need to traverse up our parents
1339 zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)idx->bti_node;
1341 out_idx->bti_node = &leaf->btl_hdr;
1342 out_idx->bti_offset = offset - 1;
1343 out_idx->bti_before = B_FALSE;
1344 return (leaf->btl_elems + (leaf->btl_hdr.bth_first +
1345 offset - 1) * tree->bt_elem_size);
1347 zfs_btree_hdr_t *prev = &leaf->btl_hdr;
1348 for (zfs_btree_core_t *node = leaf->btl_hdr.bth_parent;
1349 node != NULL; node = node->btc_hdr.bth_parent) {
1350 zfs_btree_hdr_t *hdr = &node->btc_hdr;
1352 uint32_t i = zfs_btree_find_parent_idx(tree, prev);
1357 out_idx->bti_node = hdr;
1358 out_idx->bti_offset = i - 1;
1359 out_idx->bti_before = B_FALSE;
1360 return (node->btc_elems + (i - 1) * tree->bt_elem_size);
1364 * node every time, so this was the first node in the tree.
1370 * The previous element from one in a core node is the last element in
1373 ASSERT(zfs_btree_is_core(idx->bti_node));
1374 zfs_btree_core_t *node = (zfs_btree_core_t *)idx->bti_node;
1375 zfs_btree_hdr_t *child = node->btc_children[offset];
1376 return (zfs_btree_last_helper(tree, child, out_idx));
1380 * Get the value at the provided index in the tree.
1384 * elements that could be in the tree.
1387 zfs_btree_get(zfs_btree_t *tree, zfs_btree_index_t *idx)
1389 ASSERT(!idx->bti_before);
1390 size_t size = tree->bt_elem_size;
1391 if (!zfs_btree_is_core(idx->bti_node)) {
1392 zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)idx->bti_node;
1393 return (leaf->btl_elems + (leaf->btl_hdr.bth_first +
1394 idx->bti_offset) * size);
1396 zfs_btree_core_t *node = (zfs_btree_core_t *)idx->bti_node;
1397 return (node->btc_elems + idx->bti_offset * size);
1400 /* Add the given value to the tree. Must not already be in the tree. */
1402 zfs_btree_add(zfs_btree_t *tree, const void *node)
1405 VERIFY3P(zfs_btree_find(tree, node, &where), ==, NULL);
1406 zfs_btree_add_idx(tree, node, &where);
1409 /* Helper function to free a tree node. */
1411 zfs_btree_node_destroy(zfs_btree_t *tree, zfs_btree_hdr_t *node)
1413 tree->bt_num_nodes--;
1415 zfs_btree_leaf_free(tree, node);
1418 BTREE_CORE_ELEMS * tree->bt_elem_size);
1424 * buffer that rm_hdr was stored in may already be freed, so its contents
1428 zfs_btree_remove_from_node(zfs_btree_t *tree, zfs_btree_core_t *node,
1431 size_t size = tree->bt_elem_size;
1432 uint32_t min_count = (BTREE_CORE_ELEMS / 2) - 1;
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);
1440 ASSERT3P(tree->bt_root, ==, node);
1441 ASSERT3P(node->btc_children[1], ==, rm_hdr);
1442 tree->bt_root = node->btc_children[0];
1443 node->btc_children[0]->bth_parent = NULL;
1444 zfs_btree_node_destroy(tree, hdr);
1445 tree->bt_height--;
1450 for (idx = 0; idx <= hdr->bth_count; idx++) {
1451 if (node->btc_children[idx] == rm_hdr)
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);
1487 * implementing in the future for completeness' sake.
1489 zfs_btree_core_t *parent = hdr->bth_parent;
1490 uint32_t parent_idx = zfs_btree_find_parent_idx(tree, hdr);
1493 parent->btc_children[parent_idx - 1]);
1494 if (l_hdr != NULL && l_hdr->bth_count > min_count) {
1500 * Start by shifting the elements and children in the current
1503 bt_shift_core_right(tree, node, 0, idx - 1, BSS_TRAPEZOID);
1507 * element slot in the current node.
1509 uint8_t *separator = parent->btc_elems + (parent_idx - 1) *
1511 bcpy(separator, node->btc_elems, size);
1514 node->btc_children[0] =
1515 neighbor->btc_children[l_hdr->bth_count];
1516 node->btc_children[0]->bth_parent = node;
1519 uint8_t *take_elem = neighbor->btc_elems +
1520 (l_hdr->bth_count - 1) * size;
1522 l_hdr->bth_count--;
1523 zfs_btree_poison_node_at(tree, l_hdr, l_hdr->bth_count, 1);
1527 zfs_btree_hdr_t *r_hdr = (parent_idx == parent->btc_hdr.bth_count ?
1528 NULL : parent->btc_children[parent_idx + 1]);
1529 if (r_hdr != NULL && r_hdr->bth_count > min_count) {
1535 * Shift elements in node left by one spot to overwrite rm_hdr
1538 bt_shift_core_left(tree, node, idx, hdr->bth_count - idx,
1543 * element spot in node.
1545 uint8_t *separator = parent->btc_elems + parent_idx * size;
1546 bcpy(separator, node->btc_elems + (hdr->bth_count - 1) * size,
1550 * Move the first child of neighbor to the last child spot in
1553 node->btc_children[hdr->bth_count] = neighbor->btc_children[0];
1554 node->btc_children[hdr->bth_count]->bth_parent = node;
1557 uint8_t *take_elem = neighbor->btc_elems;
1559 r_hdr->bth_count--;
1565 bt_shift_core_left(tree, neighbor, 1, r_hdr->bth_count,
1567 zfs_btree_poison_node_at(tree, r_hdr, r_hdr->bth_count, 1);
1572 * In this case, neither of our neighbors can spare an element, so we
1586 new_idx += keep_hdr->bth_count + 1;
1601 for (uint32_t i = 0; i < new_rm_hdr->bth_count + 1; i++) {
1602 zfs_btree_verify_poison_at(tree, keep_hdr,
1603 keep_hdr->bth_count + i);
1608 uint8_t *e_out = keep->btc_elems + keep_hdr->bth_count * size;
1609 uint8_t *separator = parent->btc_elems + (parent_idx - 1) *
1612 keep_hdr->bth_count++;
1615 bt_transfer_core(tree, rm, 0, new_rm_hdr->bth_count, keep,
1616 keep_hdr->bth_count, BSS_TRAPEZOID);
1618 uint32_t old_count = keep_hdr->bth_count;
1621 keep_hdr->bth_count += new_rm_hdr->bth_count;
1622 ASSERT3U(keep_hdr->bth_count, ==, (min_count * 2) + 1);
1628 ASSERT3P(keep->btc_children[new_idx], ==, rm_hdr);
1629 bt_shift_core_left(tree, keep, new_idx, keep_hdr->bth_count - new_idx,
1631 keep_hdr->bth_count--;
1634 zfs_btree_hdr_t **new_start = keep->btc_children +
1635 old_count - 1;
1636 for (uint32_t i = 0; i < new_rm_hdr->bth_count + 1; i++)
1637 new_start[i]->bth_parent = keep;
1638 for (uint32_t i = 0; i <= keep_hdr->bth_count; i++) {
1639 ASSERT3P(keep->btc_children[i]->bth_parent, ==, keep);
1640 ASSERT3P(keep->btc_children[i], !=, rm_hdr);
1642 zfs_btree_poison_node_at(tree, keep_hdr, keep_hdr->bth_count, 1);
1644 new_rm_hdr->bth_count = 0;
1645 zfs_btree_remove_from_node(tree, parent, new_rm_hdr);
1646 zfs_btree_node_destroy(tree, new_rm_hdr);
1651 zfs_btree_remove_idx(zfs_btree_t *tree, zfs_btree_index_t *where)
1653 size_t size = tree->bt_elem_size;
1654 zfs_btree_hdr_t *hdr = where->bti_node;
1655 uint32_t idx = where->bti_offset;
1657 ASSERT(!where->bti_before);
1658 if (tree->bt_bulk != NULL) {
1661 * invalid after we correct the tree, so we copy the value
1665 uint8_t *value = zfs_btree_get(tree, where);
1668 zfs_btree_bulk_finish(tree);
1669 VERIFY3P(zfs_btree_find(tree, tmp, where), !=, NULL);
1671 hdr = where->bti_node;
1672 idx = where->bti_offset;
1675 tree->bt_num_elems--;
1677 * If the element happens to be in a core node, we move a leaf node's
1684 zfs_btree_hdr_t *left_subtree = node->btc_children[idx];
1685 void *new_value = zfs_btree_last_helper(tree, left_subtree,
1689 bcpy(new_value, node->btc_elems + idx * size, size);
1691 hdr = where->bti_node;
1692 idx = where->bti_offset;
1693 ASSERT(!where->bti_before);
1703 ASSERT3U(hdr->bth_count, >, 0);
1705 uint32_t min_count = (tree->bt_leaf_cap / 2) - 1;
1711 if (hdr->bth_count > min_count || hdr->bth_parent == NULL) {
1712 bt_shrink_leaf(tree, leaf, idx, 1);
1713 if (hdr->bth_parent == NULL) {
1714 ASSERT0(tree->bt_height);
1715 if (hdr->bth_count == 0) {
1716 tree->bt_root = NULL;
1717 tree->bt_height--;
1718 zfs_btree_node_destroy(tree, &leaf->btl_hdr);
1721 zfs_btree_verify(tree);
1724 ASSERT3U(hdr->bth_count, ==, min_count);
1737 * worth implementing in the future for completeness' sake.
1739 zfs_btree_core_t *parent = hdr->bth_parent;
1740 uint32_t parent_idx = zfs_btree_find_parent_idx(tree, hdr);
1743 parent->btc_children[parent_idx - 1]);
1744 if (l_hdr != NULL && l_hdr->bth_count > min_count) {
1753 bt_shift_leaf(tree, leaf, 0, idx, 1, BSD_RIGHT);
1756 uint8_t *separator = parent->btc_elems + (parent_idx - 1) *
1758 bcpy(separator, leaf->btl_elems + hdr->bth_first * size, size);
1761 uint8_t *take_elem = neighbor->btl_elems +
1762 (l_hdr->bth_first + l_hdr->bth_count - 1) * size;
1766 bt_shrink_leaf(tree, neighbor, l_hdr->bth_count - 1, 1);
1767 zfs_btree_verify(tree);
1771 zfs_btree_hdr_t *r_hdr = (parent_idx == parent->btc_hdr.bth_count ?
1772 NULL : parent->btc_children[parent_idx + 1]);
1773 if (r_hdr != NULL && r_hdr->bth_count > min_count) {
1783 bt_shift_leaf(tree, leaf, idx + 1, hdr->bth_count - idx - 1,
1787 uint8_t *separator = parent->btc_elems + parent_idx * size;
1788 bcpy(separator, leaf->btl_elems + (hdr->bth_first +
1789 hdr->bth_count - 1) * size, size);
1792 uint8_t *take_elem = neighbor->btl_elems +
1793 r_hdr->bth_first * size;
1797 bt_shrink_leaf(tree, neighbor, 0, 1);
1798 zfs_btree_verify(tree);
1803 * In this case, neither of our neighbors can spare an element, so we
1824 ASSERT3U(k_hdr->bth_count, ==, min_count);
1825 ASSERT3U(rm_hdr->bth_count, ==, min_count);
1830 for (uint32_t i = 0; i < rm_hdr->bth_count + 1; i++) {
1831 zfs_btree_verify_poison_at(tree, k_hdr,
1832 k_hdr->bth_count + i);
1838 * but we'll fix it in no time.
1840 bt_shrink_leaf(tree, leaf, idx, 1);
1843 uint32_t k_count = k_hdr->bth_count;
1844 bt_grow_leaf(tree, keep, k_count, 1 + rm_hdr->bth_count);
1845 ASSERT3U(k_hdr->bth_count, ==, min_count * 2);
1848 uint8_t *out = keep->btl_elems + (k_hdr->bth_first + k_count) * size;
1849 uint8_t *separator = parent->btc_elems + (parent_idx - 1) * size;
1853 bt_transfer_leaf(tree, rm, 0, rm_hdr->bth_count, keep, k_count + 1);
1856 zfs_btree_remove_from_node(tree, parent, rm_hdr);
1857 zfs_btree_node_destroy(tree, rm_hdr);
1858 zfs_btree_verify(tree);
1861 /* Remove the given value from the tree. */
1863 zfs_btree_remove(zfs_btree_t *tree, const void *value)
1866 VERIFY3P(zfs_btree_find(tree, value, &where), !=, NULL);
1867 zfs_btree_remove_idx(tree, &where);
1870 /* Return the number of elements in the tree. */
1872 zfs_btree_numnodes(zfs_btree_t *tree)
1874 return (tree->bt_num_elems);
1878 * This function is used to visit all the elements in the tree before
1879 * destroying the tree. This allows the calling code to perform any cleanup it
1890 * while ((node = zfs_btree_destroy_nodes(tree, &cookie)) != NULL)
1891 * free(node->ptr);
1892 * zfs_btree_destroy(tree);
1896 zfs_btree_destroy_nodes(zfs_btree_t *tree, zfs_btree_index_t **cookie)
1899 if (tree->bt_height == -1)
1902 return (zfs_btree_first(tree, *cookie));
1905 void *rval = zfs_btree_next_helper(tree, *cookie, *cookie,
1908 tree->bt_root = NULL;
1909 tree->bt_height = -1;
1910 tree->bt_num_elems = 0;
1912 tree->bt_bulk = NULL;
1918 zfs_btree_clear_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
1922 for (uint32_t i = 0; i <= hdr->bth_count; i++)
1923 zfs_btree_clear_helper(tree, btc->btc_children[i]);
1926 zfs_btree_node_destroy(tree, hdr);
1930 zfs_btree_clear(zfs_btree_t *tree)
1932 if (tree->bt_root == NULL) {
1933 ASSERT0(tree->bt_num_elems);
1937 zfs_btree_clear_helper(tree, tree->bt_root);
1938 tree->bt_num_elems = 0;
1939 tree->bt_root = NULL;
1940 tree->bt_num_nodes = 0;
1941 tree->bt_height = -1;
1942 tree->bt_bulk = NULL;
1946 zfs_btree_destroy(zfs_btree_t *tree)
1948 ASSERT0(tree->bt_num_elems);
1949 ASSERT3P(tree->bt_root, ==, NULL);
1954 zfs_btree_verify_pointers_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
1960 for (uint32_t i = 0; i <= hdr->bth_count; i++) {
1961 VERIFY3P(node->btc_children[i]->bth_parent, ==, hdr);
1962 zfs_btree_verify_pointers_helper(tree, node->btc_children[i]);
1968 zfs_btree_verify_pointers(zfs_btree_t *tree)
1970 if (tree->bt_height == -1) {
1971 VERIFY3P(tree->bt_root, ==, NULL);
1974 VERIFY3P(tree->bt_root->bth_parent, ==, NULL);
1975 zfs_btree_verify_pointers_helper(tree, tree->bt_root);
1980 * invariants, and return the total count in the subtree rooted in this node.
1983 zfs_btree_verify_counts_helper(zfs_btree_t *tree, zfs_btree_hdr_t *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);
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++) {
1999 ret += zfs_btree_verify_counts_helper(tree,
2000 node->btc_children[i]);
2012 zfs_btree_verify_counts(zfs_btree_t *tree)
2014 EQUIV(tree->bt_num_elems == 0, tree->bt_height == -1);
2015 if (tree->bt_height == -1) {
2018 VERIFY3P(zfs_btree_verify_counts_helper(tree, tree->bt_root), ==,
2019 tree->bt_num_elems);
2027 zfs_btree_verify_height_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
2037 for (uint32_t i = 0; i <= hdr->bth_count; i++) {
2038 ret += zfs_btree_verify_height_helper(tree,
2039 node->btc_children[i], height - 1);
2045 * Check that the tree rooted at this node has a uniform height, and that the
2046 * bt_height in the tree is correct.
2049 zfs_btree_verify_height(zfs_btree_t *tree)
2051 EQUIV(tree->bt_height == -1, tree->bt_root == NULL);
2052 if (tree->bt_height == -1) {
2056 VERIFY3U(zfs_btree_verify_height_helper(tree, tree->bt_root,
2057 tree->bt_height), ==, tree->bt_num_nodes);
2061 * Check that the elements in this node are sorted, and that if this is a core
2066 zfs_btree_verify_order_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
2068 size_t size = tree->bt_elem_size;
2071 for (uint32_t i = 1; i < hdr->bth_count; i++) {
2072 VERIFY3S(tree->bt_compar(leaf->btl_elems +
2073 (hdr->bth_first + i - 1) * size,
2074 leaf->btl_elems +
2075 (hdr->bth_first + i) * size), ==, -1);
2081 for (uint32_t i = 1; i < hdr->bth_count; i++) {
2082 VERIFY3S(tree->bt_compar(node->btc_elems + (i - 1) * size,
2083 node->btc_elems + i * size), ==, -1);
2085 for (uint32_t i = 0; i < hdr->bth_count; i++) {
2087 zfs_btree_hdr_t *left_child_hdr = node->btc_children[i];
2091 left_child_last = left_child->btc_elems +
2092 (left_child_hdr->bth_count - 1) * size;
2096 left_child_last = left_child->btl_elems +
2097 (left_child_hdr->bth_first +
2098 left_child_hdr->bth_count - 1) * size;
2100 int comp = tree->bt_compar(node->btc_elems + i * size,
2105 node->btc_elems + i * size, left_child_last);
2109 zfs_btree_hdr_t *right_child_hdr = node->btc_children[i + 1];
2113 right_child_first = right_child->btc_elems;
2117 right_child_first = right_child->btl_elems +
2118 right_child_hdr->bth_first * size;
2120 comp = tree->bt_compar(node->btc_elems + i * size,
2123 panic("btree: compar returned %d (expected -1) at "
2125 node->btc_elems + i * size, right_child_first);
2128 for (uint32_t i = 0; i <= hdr->bth_count; i++)
2129 zfs_btree_verify_order_helper(tree, node->btc_children[i]);
2132 /* Check that all elements in the tree are in sorted order. */
2134 zfs_btree_verify_order(zfs_btree_t *tree)
2136 EQUIV(tree->bt_height == -1, tree->bt_root == NULL);
2137 if (tree->bt_height == -1) {
2141 zfs_btree_verify_order_helper(tree, tree->bt_root);
2147 zfs_btree_verify_poison_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
2149 size_t size = tree->bt_elem_size;
2152 for (size_t i = 0; i < hdr->bth_first * size; i++)
2153 VERIFY3U(leaf->btl_elems[i], ==, 0x0f);
2154 size_t esize = tree->bt_leaf_size -
2156 for (size_t i = (hdr->bth_first + hdr->bth_count) * size;
2158 VERIFY3U(leaf->btl_elems[i], ==, 0x0f);
2161 for (size_t i = hdr->bth_count * size;
2163 VERIFY3U(node->btc_elems[i], ==, 0x0f);
2165 for (uint32_t i = hdr->bth_count + 1; i <= BTREE_CORE_ELEMS;
2167 VERIFY3P(node->btc_children[i], ==,
2171 for (uint32_t i = 0; i <= hdr->bth_count; i++) {
2172 zfs_btree_verify_poison_helper(tree,
2173 node->btc_children[i]);
2179 /* Check that unused memory in the tree is still poisoned. */
2181 zfs_btree_verify_poison(zfs_btree_t *tree)
2184 if (tree->bt_height == -1)
2186 zfs_btree_verify_poison_helper(tree, tree->bt_root);
2191 zfs_btree_verify(zfs_btree_t *tree)
2195 zfs_btree_verify_height(tree);
2198 zfs_btree_verify_pointers(tree);
2201 zfs_btree_verify_counts(tree);
2204 zfs_btree_verify_order(tree);
2208 zfs_btree_verify_poison(tree);