56 static void node_shift(struct btree_node *n, int shift)  in node_shift()  argument
58 	uint32_t nr_entries = le32_to_cpu(n->header.nr_entries);  in node_shift()
59 	uint32_t value_size = le32_to_cpu(n->header.value_size);  in node_shift()
64 		BUG_ON((void *) key_ptr(n, shift) >= value_ptr(n, shift));  in node_shift()
65 		memmove(key_ptr(n, 0),  in node_shift()
66 			key_ptr(n, shift),  in node_shift()
68 		memmove(value_ptr(n, 0),  in node_shift()
69 			value_ptr(n, shift),  in node_shift()
72 		BUG_ON(nr_entries + shift > le32_to_cpu(n->header.max_entries));  in node_shift()
73 		memmove(key_ptr(n, shift),  in node_shift()
74 			key_ptr(n, 0),  in node_shift()
76 		memmove(value_ptr(n, shift),  in node_shift()
77 			value_ptr(n, 0),  in node_shift()
111 static void delete_at(struct btree_node *n, unsigned index)  in delete_at()  argument
113 	unsigned nr_entries = le32_to_cpu(n->header.nr_entries);  in delete_at()
115 	uint32_t value_size = le32_to_cpu(n->header.value_size);  in delete_at()
119 		memmove(key_ptr(n, index),  in delete_at()
120 			key_ptr(n, index + 1),  in delete_at()
123 		memmove(value_ptr(n, index),  in delete_at()
124 			value_ptr(n, index + 1),  in delete_at()
128 	n->header.nr_entries = cpu_to_le32(nr_entries - 1);  in delete_at()
131 static unsigned merge_threshold(struct btree_node *n)  in merge_threshold()  argument
133 	return le32_to_cpu(n->header.max_entries) / 3;  in merge_threshold()
139 	struct btree_node *n;  member
157 	result->n = dm_block_data(result->block);  in init_child()
160 		inc_children(info->tm, result->n, vt);  in init_child()
202 	struct btree_node *left = l->n;  in __rebalance2()
203 	struct btree_node *right = r->n;  in __rebalance2()
344 	struct btree_node *left = l->n;  in __rebalance3()
345 	struct btree_node *center = c->n;  in __rebalance3()
346 	struct btree_node *right = r->n;  in __rebalance3()
406 	struct btree_node *n;  in rebalance_children()  local
408 	n = dm_block_data(shadow_current(s));  in rebalance_children()
410 	if (le32_to_cpu(n->header.nr_entries) == 1) {  in rebalance_children()
412 		dm_block_t b = value64(n, 0);  in rebalance_children()
418 		memcpy(n, dm_block_data(child),  in rebalance_children()
426 	i = lower_bound(n, key);  in rebalance_children()
431 	has_right_sibling = i < (le32_to_cpu(n->header.nr_entries) - 1);  in rebalance_children()
445 static int do_leaf(struct btree_node *n, uint64_t key, unsigned *index)  in do_leaf()  argument
447 	int i = lower_bound(n, key);  in do_leaf()
450 	    (i >= le32_to_cpu(n->header.nr_entries)) ||  in do_leaf()
451 	    (le64_to_cpu(n->keys[i]) != key))  in do_leaf()
468 	struct btree_node *n;  in remove_raw()  local
486 		n = dm_block_data(shadow_current(s));  in remove_raw()
488 		if (le32_to_cpu(n->header.flags) & LEAF_NODE)  in remove_raw()
489 			return do_leaf(n, key, index);  in remove_raw()
495 		n = dm_block_data(shadow_current(s));  in remove_raw()
496 		if (le32_to_cpu(n->header.flags) & LEAF_NODE)  in remove_raw()
497 			return do_leaf(n, key, index);  in remove_raw()
499 		i = lower_bound(n, key);  in remove_raw()
506 		root = value64(n, i);  in remove_raw()
518 	struct btree_node *n;  in dm_btree_remove()  local
531 		n = dm_block_data(shadow_current(&spine));  in dm_btree_remove()
533 			root = value64(n, index);  in dm_btree_remove()
537 		BUG_ON(index < 0 || index >= le32_to_cpu(n->header.nr_entries));  in dm_btree_remove()
541 					     value_ptr(n, index));  in dm_btree_remove()
543 		delete_at(n, index);  in dm_btree_remove()
560 	struct btree_node *n;  in remove_nearest()  local
578 		n = dm_block_data(shadow_current(s));  in remove_nearest()
580 		if (le32_to_cpu(n->header.flags) & LEAF_NODE) {  in remove_nearest()
581 			*index = lower_bound(n, key);  in remove_nearest()
589 		n = dm_block_data(shadow_current(s));  in remove_nearest()
590 		if (le32_to_cpu(n->header.flags) & LEAF_NODE) {  in remove_nearest()
591 			*index = lower_bound(n, key);  in remove_nearest()
595 		i = lower_bound(n, key);  in remove_nearest()
602 		root = value64(n, i);  in remove_nearest()
615 	struct btree_node *n;  in remove_one()  local
627 		n = dm_block_data(shadow_current(&spine));  in remove_one()
628 		root = value64(n, index);  in remove_one()
636 	n = dm_block_data(shadow_current(&spine));  in remove_one()
641 	if (index >= le32_to_cpu(n->header.nr_entries)) {  in remove_one()
646 	k = le64_to_cpu(n->keys[index]);  in remove_one()
650 					     value_ptr(n, index));  in remove_one()
652 		delete_at(n, index);  in remove_one()