Lines Matching full:right
28 * Each node may have a left or right sibling. When decending the spine,
36 * ==> rebalance(node, right sibling)
38 * [C] No right sibling
41 * [D] Both siblings, total_entries(left, node, right) <= DEL_THRESHOLD
42 * ==> delete node adding it's contents to left and right
44 * [E] Both siblings, total_entries(left, node, right) > DEL_THRESHOLD
45 * ==> rebalance(left, node, right)
85 static int node_copy(struct btree_node *left, struct btree_node *right, int shift) in node_copy() argument
89 if (value_size != le32_to_cpu(right->header.value_size)) { in node_copy()
103 key_ptr(right, 0), in node_copy()
106 value_ptr(right, 0), in node_copy()
109 if (shift > le32_to_cpu(right->header.max_entries)) { in node_copy()
114 memcpy(key_ptr(right, 0), in node_copy()
117 memcpy(value_ptr(right, 0), in node_copy()
189 static int shift(struct btree_node *left, struct btree_node *right, int count) in shift() argument
193 uint32_t nr_right = le32_to_cpu(right->header.nr_entries); in shift()
195 uint32_t r_max_entries = le32_to_cpu(right->header.max_entries); in shift()
216 node_shift(right, count); in shift()
217 r = node_copy(left, right, count); in shift()
221 r = node_copy(left, right, count); in shift()
224 node_shift(right, count); in shift()
228 right->header.nr_entries = cpu_to_le32(nr_right + count); in shift()
238 struct btree_node *right = r->n; in __rebalance2() local
240 uint32_t nr_right = le32_to_cpu(right->header.nr_entries); in __rebalance2()
253 node_copy(left, right, -nr_right); in __rebalance2()
258 * We need to decrement the right block, but not it's in __rebalance2()
267 ret = shift(left, right, nr_left - target_left); in __rebalance2()
270 *key_ptr(parent, r->index) = right->keys[0]; in __rebalance2()
280 struct child left, right; in rebalance2() local
288 r = init_child(info, vt, parent, left_index + 1, &right); in rebalance2()
294 r = __rebalance2(info, parent, &left, &right); in rebalance2()
297 exit_child(info, &right); in rebalance2()
304 * in right, then rebalance2. This wastes some cpu, but I want something
309 struct btree_node *left, struct btree_node *center, struct btree_node *right, in delete_center_node() argument
331 node_shift(right, shift); in delete_center_node()
332 node_copy(center, right, shift); in delete_center_node()
333 right->header.nr_entries = cpu_to_le32(nr_right + shift); in delete_center_node()
335 *key_ptr(parent, r->index) = right->keys[0]; in delete_center_node()
349 struct btree_node *left, struct btree_node *center, struct btree_node *right, in redistribute3() argument
372 ret = shift(left, right, s); in redistribute3()
383 ret = shift(center, right, target_right - nr_right); in redistribute3()
390 ret = shift(center, right, nr_center); in redistribute3()
394 ret = shift(left, right, s); in redistribute3()
399 ret = shift(center, right, s); in redistribute3()
410 *key_ptr(parent, r->index) = right->keys[0]; in redistribute3()
419 struct btree_node *right = r->n; in __rebalance3() local
423 uint32_t nr_right = le32_to_cpu(right->header.nr_entries); in __rebalance3()
428 (center->header.max_entries != right->header.max_entries)) { in __rebalance3()
434 return delete_center_node(info, parent, l, c, r, left, center, right, in __rebalance3()
438 return redistribute3(info, parent, l, c, r, left, center, right, in __rebalance3()
447 struct child left, center, right; in rebalance3() local
462 r = init_child(info, vt, parent, left_index + 2, &right); in rebalance3()
469 r = __rebalance3(info, parent, &left, ¢er, &right); in rebalance3()
473 exit_child(info, &right); in rebalance3()