Lines Matching refs:left
25 * Each node may have a left or right sibling. When decending the spine,
32 * [B] No left sibling
36 * ==> rebalance(left sibling, node)
38 * [D] Both siblings, total_entries(left, node, right) <= DEL_THRESHOLD
39 * ==> delete node adding it's contents to left and right
41 * [E] Both siblings, total_entries(left, node, right) > DEL_THRESHOLD
42 * ==> rebalance(left, node, right)
82 static void node_copy(struct btree_node *left, struct btree_node *right, int shift)
84 uint32_t nr_left = le32_to_cpu(left->header.nr_entries);
85 uint32_t value_size = le32_to_cpu(left->header.value_size);
90 BUG_ON(nr_left + shift > le32_to_cpu(left->header.max_entries));
91 memcpy(key_ptr(left, nr_left),
94 memcpy(value_ptr(left, nr_left),
100 key_ptr(left, nr_left - shift),
103 value_ptr(left, nr_left - shift),
173 static void shift(struct btree_node *left, struct btree_node *right, int count)
175 uint32_t nr_left = le32_to_cpu(left->header.nr_entries);
177 uint32_t max_entries = le32_to_cpu(left->header.max_entries);
189 node_copy(left, right, count);
191 node_copy(left, right, count);
195 left->header.nr_entries = cpu_to_le32(nr_left - count);
202 struct btree_node *left = l->n;
204 uint32_t nr_left = le32_to_cpu(left->header.nr_entries);
212 unsigned int threshold = 2 * (merge_threshold(left) + 1);
218 node_copy(left, right, -nr_right);
219 left->header.nr_entries = cpu_to_le32(nr_left + nr_right);
224 * children, since they're still referenced by left.
232 shift(left, right, nr_left - target_left);
242 struct child left, right;
246 r = init_child(info, vt, parent, left_index, &left);
252 exit_child(info, &left);
256 __rebalance2(info, parent, &left, &right);
258 exit_child(info, &left);
265 * We dump as many entries from center as possible into left, then the rest
271 struct btree_node *left, struct btree_node *center, struct btree_node *right,
274 uint32_t max_entries = le32_to_cpu(left->header.max_entries);
278 node_copy(left, center, -shift);
279 left->header.nr_entries = cpu_to_le32(nr_left + shift);
302 struct btree_node *left, struct btree_node *center, struct btree_node *right,
306 uint32_t max_entries = le32_to_cpu(left->header.max_entries);
320 shift(left, center, -nr_center);
322 shift(left, right, s);
325 shift(left, center, s);
335 shift(left, right, s);
340 shift(left, center, nr_left - target_left);
350 struct btree_node *left = l->n;
354 uint32_t nr_left = le32_to_cpu(left->header.nr_entries);
358 unsigned threshold = merge_threshold(left) * 4 + 1;
360 BUG_ON(left->header.max_entries != center->header.max_entries);
364 delete_center_node(info, parent, l, c, r, left, center, right,
367 redistribute3(info, parent, l, c, r, left, center, right,
376 struct child left, center, right;
381 r = init_child(info, vt, parent, left_index, &left);
387 exit_child(info, &left);
393 exit_child(info, &left);
398 __rebalance3(info, parent, &left, ¢er, &right);
400 exit_child(info, &left);