Lines Matching +full:child +full:- +full:node
7 #include "dm-btree.h"
8 #include "dm-btree-internal.h"
9 #include "dm-transaction-manager.h"
17 * A very important constraint for our btree is that no node, except the
25 * Each node may have a left or right sibling. When decending the spine,
26 * if a node contains only MIN_ENTRIES then we try and increase this to at
29 * [A] No siblings => this can only happen if the node is the root, in which
33 * ==> rebalance(node, right 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)
44 * After these operations it's possible that the our original node no
46 * is performed on the children of the current node. This also avoids
49 * Once this rebalancing has occurred we can then step into the child node
54 * Some little utilities for moving node data around.
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()
62 shift = -shift; in node_shift()
67 (nr_entries - shift) * sizeof(__le64)); in node_shift()
70 (nr_entries - shift) * value_size); in node_shift()
72 BUG_ON(nr_entries + shift > le32_to_cpu(n->header.max_entries)); in node_shift()
84 uint32_t nr_left = le32_to_cpu(left->header.nr_entries); in node_copy()
85 uint32_t value_size = le32_to_cpu(left->header.value_size); in node_copy()
86 BUG_ON(value_size != le32_to_cpu(right->header.value_size)); in node_copy()
89 shift = -shift; in node_copy()
90 BUG_ON(nr_left + shift > le32_to_cpu(left->header.max_entries)); in node_copy()
98 BUG_ON(shift > le32_to_cpu(right->header.max_entries)); in node_copy()
100 key_ptr(left, nr_left - shift), in node_copy()
103 value_ptr(left, nr_left - shift), in node_copy()
109 * Delete a specific entry from a leaf node.
113 unsigned nr_entries = le32_to_cpu(n->header.nr_entries); in delete_at()
114 unsigned nr_to_copy = nr_entries - (index + 1); in delete_at()
115 uint32_t value_size = le32_to_cpu(n->header.value_size); in delete_at()
128 n->header.nr_entries = cpu_to_le32(nr_entries - 1); in delete_at()
133 return le32_to_cpu(n->header.max_entries) / 3; in merge_threshold()
136 struct child { struct
144 unsigned index, struct child *result) in init_child() argument
149 result->index = index; in init_child()
152 r = dm_tm_shadow_block(info->tm, root, &btree_node_validator, in init_child()
153 &result->block, &inc); in init_child()
157 result->n = dm_block_data(result->block); in init_child()
160 inc_children(info->tm, result->n, vt); in init_child()
163 cpu_to_le64(dm_block_location(result->block)); in init_child()
168 static void exit_child(struct dm_btree_info *info, struct child *c) in exit_child()
170 dm_tm_unlock(info->tm, c->block); in exit_child()
175 uint32_t nr_left = le32_to_cpu(left->header.nr_entries); in shift()
176 uint32_t nr_right = le32_to_cpu(right->header.nr_entries); in shift()
177 uint32_t max_entries = le32_to_cpu(left->header.max_entries); in shift()
178 uint32_t r_max_entries = le32_to_cpu(right->header.max_entries); in shift()
181 BUG_ON(nr_left - count > max_entries); in shift()
195 left->header.nr_entries = cpu_to_le32(nr_left - count); in shift()
196 right->header.nr_entries = cpu_to_le32(nr_right + count); in shift()
200 struct child *l, struct child *r) in __rebalance2()
202 struct btree_node *left = l->n; in __rebalance2()
203 struct btree_node *right = r->n; in __rebalance2()
204 uint32_t nr_left = le32_to_cpu(left->header.nr_entries); in __rebalance2()
205 uint32_t nr_right = le32_to_cpu(right->header.nr_entries); in __rebalance2()
207 * Ensure the number of entries in each child will be greater in __rebalance2()
209 * child is used for removal, the number will still be not in __rebalance2()
218 node_copy(left, right, -nr_right); in __rebalance2()
219 left->header.nr_entries = cpu_to_le32(nr_left + nr_right); in __rebalance2()
220 delete_at(parent, r->index); in __rebalance2()
226 dm_tm_dec(info->tm, dm_block_location(r->block)); in __rebalance2()
232 shift(left, right, nr_left - target_left); in __rebalance2()
233 *key_ptr(parent, r->index) = right->keys[0]; in __rebalance2()
242 struct child left, right; in rebalance2()
270 struct child *l, struct child *c, struct child *r, in delete_center_node()
274 uint32_t max_entries = le32_to_cpu(left->header.max_entries); in delete_center_node()
275 unsigned shift = min(max_entries - nr_left, nr_center); in delete_center_node()
278 node_copy(left, center, -shift); in delete_center_node()
279 left->header.nr_entries = cpu_to_le32(nr_left + shift); in delete_center_node()
282 shift = nr_center - shift; in delete_center_node()
286 right->header.nr_entries = cpu_to_le32(nr_right + shift); in delete_center_node()
288 *key_ptr(parent, r->index) = right->keys[0]; in delete_center_node()
290 delete_at(parent, c->index); in delete_center_node()
291 r->index--; in delete_center_node()
293 dm_tm_dec(info->tm, dm_block_location(c->block)); in delete_center_node()
301 struct child *l, struct child *c, struct child *r, in redistribute3()
306 uint32_t max_entries = le32_to_cpu(left->header.max_entries); in redistribute3()
316 s = nr_left - target_left; in redistribute3()
318 if (s < 0 && nr_center < -s) { in redistribute3()
319 /* not enough in central node */ in redistribute3()
320 shift(left, center, -nr_center); in redistribute3()
327 shift(center, right, target_right - nr_right); in redistribute3()
330 s = target_right - nr_right; in redistribute3()
332 /* not enough in central node */ in redistribute3()
334 s -= nr_center; in redistribute3()
336 nr_left -= s; in redistribute3()
340 shift(left, center, nr_left - target_left); in redistribute3()
343 *key_ptr(parent, c->index) = center->keys[0]; in redistribute3()
344 *key_ptr(parent, r->index) = right->keys[0]; in redistribute3()
348 struct child *l, struct child *c, struct child *r) in __rebalance3()
350 struct btree_node *left = l->n; in __rebalance3()
351 struct btree_node *center = c->n; in __rebalance3()
352 struct btree_node *right = r->n; in __rebalance3()
354 uint32_t nr_left = le32_to_cpu(left->header.nr_entries); in __rebalance3()
355 uint32_t nr_center = le32_to_cpu(center->header.nr_entries); in __rebalance3()
356 uint32_t nr_right = le32_to_cpu(right->header.nr_entries); in __rebalance3()
360 BUG_ON(left->header.max_entries != center->header.max_entries); in __rebalance3()
361 BUG_ON(center->header.max_entries != right->header.max_entries); in __rebalance3()
376 struct child left, center, right; in rebalance3()
416 if (le32_to_cpu(n->header.nr_entries) == 1) { in rebalance_children()
417 struct dm_block *child; in rebalance_children() local
420 r = dm_tm_read_lock(info->tm, b, &btree_node_validator, &child); in rebalance_children()
424 memcpy(n, dm_block_data(child), in rebalance_children()
425 dm_bm_block_size(dm_tm_get_bm(info->tm))); in rebalance_children()
426 dm_tm_unlock(info->tm, child); in rebalance_children()
428 dm_tm_dec(info->tm, dm_block_location(child)); in rebalance_children()
434 return -ENODATA; in rebalance_children()
437 has_right_sibling = i < (le32_to_cpu(n->header.nr_entries) - 1); in rebalance_children()
443 r = rebalance2(s, info, vt, i - 1); in rebalance_children()
446 r = rebalance3(s, info, vt, i - 1); in rebalance_children()
456 (i >= le32_to_cpu(n->header.nr_entries)) || in do_leaf()
457 (le64_to_cpu(n->keys[i]) != key)) in do_leaf()
458 return -ENODATA; in do_leaf()
482 * We have to patch up the parent node, ugly, but I don't in remove_raw()
494 if (le32_to_cpu(n->header.flags) & LEAF_NODE) in remove_raw()
502 if (le32_to_cpu(n->header.flags) & LEAF_NODE) in remove_raw()
510 * -ENODATA in remove_raw()
521 unsigned level, last_level = info->levels - 1; in dm_btree_remove()
527 init_le64_type(info->tm, &le64_vt); in dm_btree_remove()
529 for (level = 0; level < info->levels; level++) { in dm_btree_remove()
532 &info->value_type : &le64_vt), in dm_btree_remove()
543 BUG_ON(index < 0 || index >= le32_to_cpu(n->header.nr_entries)); in dm_btree_remove()
545 if (info->value_type.dec) in dm_btree_remove()
546 info->value_type.dec(info->value_type.context, in dm_btree_remove()
559 /*----------------------------------------------------------------*/
574 * We have to patch up the parent node, ugly, but I don't in remove_nearest()
586 if (le32_to_cpu(n->header.flags) & LEAF_NODE) { in remove_nearest()
596 if (le32_to_cpu(n->header.flags) & LEAF_NODE) { in remove_nearest()
606 * -ENODATA in remove_nearest()
618 unsigned level, last_level = info->levels - 1; in remove_one()
625 init_le64_type(info->tm, &le64_vt); in remove_one()
637 r = remove_nearest(&spine, info, &info->value_type, in remove_one()
647 if (index >= le32_to_cpu(n->header.nr_entries)) { in remove_one()
648 r = -ENODATA; in remove_one()
652 k = le64_to_cpu(n->keys[index]); in remove_one()
654 if (info->value_type.dec) in remove_one()
655 info->value_type.dec(info->value_type.context, in remove_one()
662 r = -ENODATA; in remove_one()
685 return r == -ENODATA ? 0 : r; in dm_btree_remove_leaves()