29  * Each node may have a left or right sibling.  When decending the spine,
36  * [B] No left sibling
40  *     ==> rebalance(left sibling, node)
42  * [D] Both siblings, total_entries(left, node, right) <= DEL_THRESHOLD
43  *     ==> delete node adding it's contents to left and right
45  * [E] Both siblings, total_entries(left, node, right) > DEL_THRESHOLD
46  *     ==> rebalance(left, node, right)
86 static int node_copy(struct btree_node *left, struct btree_node *right, int shift)  in node_copy()  argument
88 	uint32_t nr_left = le32_to_cpu(left->header.nr_entries);  in node_copy()
89 	uint32_t value_size = le32_to_cpu(left->header.value_size);  in node_copy()
99 		if (nr_left + shift > le32_to_cpu(left->header.max_entries)) {  in node_copy()
104 		memcpy(key_ptr(left, nr_left),  in node_copy()
107 		memcpy(value_ptr(left, nr_left),  in node_copy()
117 		       key_ptr(left, nr_left - shift),  in node_copy()
120 		       value_ptr(left, nr_left - shift),  in node_copy()
192 static int shift(struct btree_node *left, struct btree_node *right, int count)  in shift()  argument
195 	uint32_t nr_left = le32_to_cpu(left->header.nr_entries);  in shift()
197 	uint32_t max_entries = le32_to_cpu(left->header.max_entries);  in shift()
220 		r = node_copy(left, right, count);  in shift()
224 		r = node_copy(left, right, count);  in shift()
230 	left->header.nr_entries = cpu_to_le32(nr_left - count);  in shift()
240 	struct btree_node *left = l->n;  in __rebalance2()  local
242 	uint32_t nr_left = le32_to_cpu(left->header.nr_entries);  in __rebalance2()
250 	unsigned int threshold = 2 * (merge_threshold(left) + 1);  in __rebalance2()
256 		node_copy(left, right, -nr_right);  in __rebalance2()
257 		left->header.nr_entries = cpu_to_le32(nr_left + nr_right);  in __rebalance2()
262 		 * children, since they're still referenced by left.  in __rebalance2()
271 		ret = shift(left, right, nr_left - target_left);  in __rebalance2()
284 	struct child left, right;  in rebalance2()  local
288 	r = init_child(info, vt, parent, left_index, &left);  in rebalance2()
294 		exit_child(info, &left);  in rebalance2()
298 	r = __rebalance2(info, parent, &left, &right);  in rebalance2()
300 	exit_child(info, &left);  in rebalance2()
307  * We dump as many entries from center as possible into left, then the rest
313 			      struct btree_node *left, struct btree_node *center, struct btree_node *right,  in delete_center_node()  argument
316 	uint32_t max_entries = le32_to_cpu(left->header.max_entries);  in delete_center_node()
324 	node_copy(left, center, -shift);  in delete_center_node()
325 	left->header.nr_entries = cpu_to_le32(nr_left + shift);  in delete_center_node()
353 			 struct btree_node *left, struct btree_node *center, struct btree_node *right,  in redistribute3()  argument
357 	uint32_t max_entries = le32_to_cpu(left->header.max_entries);  in redistribute3()
371 			ret = shift(left, center, -nr_center);  in redistribute3()
376 			ret = shift(left, right, s);  in redistribute3()
382 			ret = shift(left, center, s);  in redistribute3()
398 			ret = shift(left, right, s);  in redistribute3()
408 		ret = shift(left, center, nr_left - target_left);  in redistribute3()
421 	struct btree_node *left = l->n;  in __rebalance3()  local
425 	uint32_t nr_left = le32_to_cpu(left->header.nr_entries);  in __rebalance3()
429 	unsigned int threshold = merge_threshold(left) * 4 + 1;  in __rebalance3()
431 	if ((left->header.max_entries != center->header.max_entries) ||  in __rebalance3()
438 		return delete_center_node(info, parent, l, c, r, left, center, right,  in __rebalance3()
442 	return redistribute3(info, parent, l, c, r, left, center, right,  in __rebalance3()
451 	struct child left, center, right;  in rebalance3()  local
456 	r = init_child(info, vt, parent, left_index, &left);  in rebalance3()
462 		exit_child(info, &left);  in rebalance3()
468 		exit_child(info, &left);  in rebalance3()
473 	r = __rebalance3(info, parent, &left, &center, &right);  in rebalance3()
475 	exit_child(info, &left);  in rebalance3()