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()
347 	struct btree_node *left = l->n;  in __rebalance3()
348 	struct btree_node *center = c->n;  in __rebalance3()
349 	struct btree_node *right = r->n;  in __rebalance3()
422 	struct btree_node *n;  in get_nr_entries()  local
428 	n = dm_block_data(block);  in get_nr_entries()
429 	*result = le32_to_cpu(n->header.nr_entries);  in get_nr_entries()
440 	struct btree_node *n;  in rebalance_children()  local
442 	n = dm_block_data(shadow_current(s));  in rebalance_children()
444 	if (le32_to_cpu(n->header.nr_entries) == 1) {  in rebalance_children()
446 		dm_block_t b = value64(n, 0);  in rebalance_children()
452 		memcpy(n, dm_block_data(child),  in rebalance_children()
462 	i = lower_bound(n, key);  in rebalance_children()
466 	r = get_nr_entries(info->tm, value64(n, i), &child_entries);  in rebalance_children()
471 	has_right_sibling = i < (le32_to_cpu(n->header.nr_entries) - 1);  in rebalance_children()
485 static int do_leaf(struct btree_node *n, uint64_t key, unsigned *index)  in do_leaf()  argument
487 	int i = lower_bound(n, key);  in do_leaf()
490 	    (i >= le32_to_cpu(n->header.nr_entries)) ||  in do_leaf()
491 	    (le64_to_cpu(n->keys[i]) != key))  in do_leaf()
508 	struct btree_node *n;  in remove_raw()  local
526 		n = dm_block_data(shadow_current(s));  in remove_raw()
528 		if (le32_to_cpu(n->header.flags) & LEAF_NODE)  in remove_raw()
529 			return do_leaf(n, key, index);  in remove_raw()
535 		n = dm_block_data(shadow_current(s));  in remove_raw()
536 		if (le32_to_cpu(n->header.flags) & LEAF_NODE)  in remove_raw()
537 			return do_leaf(n, key, index);  in remove_raw()
539 		i = lower_bound(n, key);  in remove_raw()
546 		root = value64(n, i);  in remove_raw()
558 	struct btree_node *n;  in dm_btree_remove()  local
571 		n = dm_block_data(shadow_current(&spine));  in dm_btree_remove()
573 			root = value64(n, index);  in dm_btree_remove()
577 		BUG_ON(index < 0 || index >= le32_to_cpu(n->header.nr_entries));  in dm_btree_remove()
581 					     value_ptr(n, index));  in dm_btree_remove()
583 		delete_at(n, index);  in dm_btree_remove()