Lines Matching +full:top +full:- +full:level
7 #include "dm-btree-internal.h"
8 #include "dm-space-map.h"
9 #include "dm-transaction-manager.h"
12 #include <linux/device-mapper.h>
16 /*----------------------------------------------------------------
18 *--------------------------------------------------------------*/
33 (nr_elts - index) * elt_size); in array_insert()
38 /*----------------------------------------------------------------*/
43 int lo = -1, hi = le32_to_cpu(n->header.nr_entries); in bsearch()
45 while (hi - lo > 1) { in bsearch()
46 int mid = lo + ((hi - lo) / 2); in bsearch()
47 uint64_t mid_key = le64_to_cpu(n->keys[mid]); in bsearch()
75 uint32_t nr_entries = le32_to_cpu(n->header.nr_entries); in inc_children()
77 if (le32_to_cpu(n->header.flags) & INTERNAL_NODE) in inc_children()
80 else if (vt->inc) in inc_children()
82 vt->inc(vt->context, value_ptr(n, i)); in inc_children()
89 uint32_t nr_entries = le32_to_cpu(node->header.nr_entries); in insert_at()
93 index >= le32_to_cpu(node->header.max_entries)) { in insert_at()
96 return -ENOMEM; in insert_at()
101 array_insert(node->keys, sizeof(*node->keys), nr_entries, index, &key_le); in insert_at()
103 node->header.nr_entries = cpu_to_le32(nr_entries + 1); in insert_at()
108 /*----------------------------------------------------------------*/
119 block_size -= sizeof(struct node_header); in calc_max_entries()
138 block_size = dm_bm_block_size(dm_tm_get_bm(info->tm)); in dm_btree_empty()
139 max_entries = calc_max_entries(info->value_type.size, block_size); in dm_btree_empty()
143 n->header.flags = cpu_to_le32(LEAF_NODE); in dm_btree_empty()
144 n->header.nr_entries = cpu_to_le32(0); in dm_btree_empty()
145 n->header.max_entries = cpu_to_le32(max_entries); in dm_btree_empty()
146 n->header.value_size = cpu_to_le32(info->value_type.size); in dm_btree_empty()
155 /*----------------------------------------------------------------*/
165 unsigned level; member
173 int top; member
179 if (s->top < 0) { in top_frame()
181 return -EINVAL; in top_frame()
184 *f = s->spine + s->top; in top_frame()
191 return s->top >= 0; in unprocessed_frames()
197 struct dm_block_manager *bm = dm_tm_get_bm(s->tm); in prefetch_children()
199 for (i = 0; i < f->nr_children; i++) in prefetch_children()
200 dm_bm_prefetch(bm, value64(f->n, i)); in prefetch_children()
205 return f->level < (info->levels - 1); in is_internal_level()
208 static int push_frame(struct del_stack *s, dm_block_t b, unsigned level) in push_frame() argument
213 if (s->top >= MAX_SPINE_DEPTH - 1) { in push_frame()
215 return -ENOMEM; in push_frame()
218 r = dm_tm_ref(s->tm, b, &ref_count); in push_frame()
227 dm_tm_dec(s->tm, b); in push_frame()
231 struct frame *f = s->spine + ++s->top; in push_frame()
233 r = dm_tm_read_lock(s->tm, b, &btree_node_validator, &f->b); in push_frame()
235 s->top--; in push_frame()
239 f->n = dm_block_data(f->b); in push_frame()
240 f->level = level; in push_frame()
241 f->nr_children = le32_to_cpu(f->n->header.nr_entries); in push_frame()
242 f->current_child = 0; in push_frame()
244 flags = le32_to_cpu(f->n->header.flags); in push_frame()
245 if (flags & INTERNAL_NODE || is_internal_level(s->info, f)) in push_frame()
254 struct frame *f = s->spine + s->top--; in pop_frame()
256 dm_tm_dec(s->tm, dm_block_location(f->b)); in pop_frame()
257 dm_tm_unlock(s->tm, f->b); in pop_frame()
265 f = s->spine + s->top--; in unlock_all_frames()
266 dm_tm_unlock(s->tm, f->b); in unlock_all_frames()
282 return -ENOMEM; in dm_btree_del()
283 s->info = info; in dm_btree_del()
284 s->tm = info->tm; in dm_btree_del()
285 s->top = -1; in dm_btree_del()
300 if (f->current_child >= f->nr_children) { in dm_btree_del()
305 flags = le32_to_cpu(f->n->header.flags); in dm_btree_del()
307 b = value64(f->n, f->current_child); in dm_btree_del()
308 f->current_child++; in dm_btree_del()
309 r = push_frame(s, b, f->level); in dm_btree_del()
314 b = value64(f->n, f->current_child); in dm_btree_del()
315 f->current_child++; in dm_btree_del()
316 r = push_frame(s, b, f->level + 1); in dm_btree_del()
321 if (info->value_type.dec) { in dm_btree_del()
324 for (i = 0; i < f->nr_children; i++) in dm_btree_del()
325 info->value_type.dec(info->value_type.context, in dm_btree_del()
326 value_ptr(f->n, i)); in dm_btree_del()
342 /*----------------------------------------------------------------*/
358 flags = le32_to_cpu(ro_node(s)->header.flags); in btree_lookup_raw()
359 nr_entries = le32_to_cpu(ro_node(s)->header.nr_entries); in btree_lookup_raw()
361 return -ENODATA; in btree_lookup_raw()
368 *result_key = le64_to_cpu(ro_node(s)->keys[i]); in btree_lookup_raw()
377 unsigned level, last_level = info->levels - 1; in dm_btree_lookup() local
378 int r = -ENODATA; in dm_btree_lookup()
384 for (level = 0; level < info->levels; level++) { in dm_btree_lookup()
388 if (level == last_level) { in dm_btree_lookup()
390 size = info->value_type.size; in dm_btree_lookup()
397 r = btree_lookup_raw(&spine, root, keys[level], in dm_btree_lookup()
402 if (rkey != keys[level]) { in dm_btree_lookup()
404 return -ENODATA; in dm_btree_lookup()
432 flags = le32_to_cpu(n->header.flags); in dm_btree_lookup_next_single()
433 nr_entries = le32_to_cpu(n->header.nr_entries); in dm_btree_lookup_next_single()
439 * avoid early -ENODATA return when all entries are in dm_btree_lookup_next_single()
445 r = -ENODATA; in dm_btree_lookup_next_single()
450 if (r == -ENODATA && i < (nr_entries - 1)) { in dm_btree_lookup_next_single()
458 r = -ENODATA; in dm_btree_lookup_next_single()
462 *rkey = le64_to_cpu(n->keys[i]); in dm_btree_lookup_next_single()
463 memcpy(value_le, value_ptr(n, i), info->value_type.size); in dm_btree_lookup_next_single()
466 dm_tm_unlock(info->tm, node); in dm_btree_lookup_next_single()
473 unsigned level; in dm_btree_lookup_next() local
474 int r = -ENODATA; in dm_btree_lookup_next()
479 for (level = 0; level < info->levels - 1u; level++) { in dm_btree_lookup_next()
480 r = btree_lookup_raw(&spine, root, keys[level], in dm_btree_lookup_next()
486 if (*rkey != keys[level]) { in dm_btree_lookup_next()
487 r = -ENODATA; in dm_btree_lookup_next()
494 r = dm_btree_lookup_next_single(info, root, keys[level], rkey, value_le); in dm_btree_lookup_next()
508 * +--------+
510 * +--------+
513 * +----------+
515 * +----------+
519 * +--------+
521 * +--------+
523 * v +------+
524 * +---------+ |
526 * +---------+ +-------+
528 * +-------+
544 r = new_block(s->info, &right); in btree_split_sibling()
551 nr_left = le32_to_cpu(ln->header.nr_entries) / 2; in btree_split_sibling()
552 nr_right = le32_to_cpu(ln->header.nr_entries) - nr_left; in btree_split_sibling()
554 ln->header.nr_entries = cpu_to_le32(nr_left); in btree_split_sibling()
556 rn->header.flags = ln->header.flags; in btree_split_sibling()
557 rn->header.nr_entries = cpu_to_le32(nr_right); in btree_split_sibling()
558 rn->header.max_entries = ln->header.max_entries; in btree_split_sibling()
559 rn->header.value_size = ln->header.value_size; in btree_split_sibling()
560 memcpy(rn->keys, ln->keys + nr_left, nr_right * sizeof(rn->keys[0])); in btree_split_sibling()
562 size = le32_to_cpu(ln->header.flags) & INTERNAL_NODE ? in btree_split_sibling()
563 sizeof(uint64_t) : s->info->value_type.size; in btree_split_sibling()
582 le64_to_cpu(rn->keys[0]), &location); in btree_split_sibling()
584 unlock_block(s->info, right); in btree_split_sibling()
588 if (key < le64_to_cpu(rn->keys[0])) { in btree_split_sibling()
589 unlock_block(s->info, right); in btree_split_sibling()
590 s->nodes[1] = left; in btree_split_sibling()
592 unlock_block(s->info, left); in btree_split_sibling()
593 s->nodes[1] = right; in btree_split_sibling()
603 * +----------+
605 * +----------+
609 * +------------+
611 * +------------+
613 * +------+ +----+
616 * +-------+ +-------+
618 * +-------+ +-------+
632 size = le32_to_cpu(pn->header.flags) & INTERNAL_NODE ? in btree_split_beneath()
633 sizeof(__le64) : s->info->value_type.size; in btree_split_beneath()
636 r = new_block(s->info, &left); in btree_split_beneath()
641 nr_left = le32_to_cpu(pn->header.nr_entries) / 2; in btree_split_beneath()
643 ln->header.flags = pn->header.flags; in btree_split_beneath()
644 ln->header.nr_entries = cpu_to_le32(nr_left); in btree_split_beneath()
645 ln->header.max_entries = pn->header.max_entries; in btree_split_beneath()
646 ln->header.value_size = pn->header.value_size; in btree_split_beneath()
647 memcpy(ln->keys, pn->keys, nr_left * sizeof(pn->keys[0])); in btree_split_beneath()
651 r = new_block(s->info, &right); in btree_split_beneath()
653 unlock_block(s->info, left); in btree_split_beneath()
658 nr_right = le32_to_cpu(pn->header.nr_entries) - nr_left; in btree_split_beneath()
660 rn->header.flags = pn->header.flags; in btree_split_beneath()
661 rn->header.nr_entries = cpu_to_le32(nr_right); in btree_split_beneath()
662 rn->header.max_entries = pn->header.max_entries; in btree_split_beneath()
663 rn->header.value_size = pn->header.value_size; in btree_split_beneath()
664 memcpy(rn->keys, pn->keys + nr_left, nr_right * sizeof(pn->keys[0])); in btree_split_beneath()
669 pn->header.flags = cpu_to_le32(INTERNAL_NODE); in btree_split_beneath()
670 pn->header.nr_entries = cpu_to_le32(2); in btree_split_beneath()
671 pn->header.max_entries = cpu_to_le32( in btree_split_beneath()
674 dm_tm_get_bm(s->info->tm)))); in btree_split_beneath()
675 pn->header.value_size = cpu_to_le32(sizeof(__le64)); in btree_split_beneath()
679 pn->keys[0] = ln->keys[0]; in btree_split_beneath()
684 pn->keys[1] = rn->keys[0]; in btree_split_beneath()
687 unlock_block(s->info, left); in btree_split_beneath()
688 unlock_block(s->info, right); in btree_split_beneath()
696 int r, i = *index, top = 1; in btree_insert_raw() local
721 if (node->header.nr_entries == node->header.max_entries) { in btree_insert_raw()
722 if (top) in btree_insert_raw()
735 if (le32_to_cpu(node->header.flags) & LEAF_NODE) in btree_insert_raw()
740 node->keys[0] = cpu_to_le64(key); in btree_insert_raw()
745 top = 0; in btree_insert_raw()
748 if (i < 0 || le64_to_cpu(node->keys[i]) != key) in btree_insert_raw()
756 unsigned level, unsigned index) in need_insert() argument
758 return ((index >= le32_to_cpu(node->header.nr_entries)) || in need_insert()
759 (le64_to_cpu(node->keys[index]) != keys[level])); in need_insert()
768 unsigned level, index = -1, last_level = info->levels - 1; in insert() local
774 init_le64_type(info->tm, &le64_type); in insert()
777 for (level = 0; level < (info->levels - 1); level++) { in insert()
778 r = btree_insert_raw(&spine, block, &le64_type, keys[level], &index); in insert()
784 if (need_insert(n, keys, level, index)) { in insert()
796 keys[level], &new_le); in insert()
801 if (level < last_level) in insert()
805 r = btree_insert_raw(&spine, block, &info->value_type, in insert()
806 keys[level], &index); in insert()
812 if (need_insert(n, keys, level, index)) { in insert()
816 r = insert_at(info->value_type.size, n, index, in insert()
817 keys[level], value); in insert()
824 if (info->value_type.dec && in insert()
825 (!info->value_type.equal || in insert()
826 !info->value_type.equal( in insert()
827 info->value_type.context, in insert()
830 info->value_type.dec(info->value_type.context, in insert()
834 value, info->value_type.size); in insert()
866 /*----------------------------------------------------------------*/
879 flags = le32_to_cpu(ro_node(s)->header.flags); in find_key()
880 i = le32_to_cpu(ro_node(s)->header.nr_entries); in find_key()
882 return -ENODATA; in find_key()
884 i--; in find_key()
887 *result_key = le64_to_cpu(ro_node(s)->keys[i]); in find_key()
889 *result_key = le64_to_cpu(ro_node(s)->keys[0]); in find_key()
908 int r = 0, count = 0, level; in dm_btree_find_key() local
912 for (level = 0; level < info->levels; level++) { in dm_btree_find_key()
913 r = find_key(&spine, root, find_highest, result_keys + level, in dm_btree_find_key()
914 level == info->levels - 1 ? NULL : &root); in dm_btree_find_key()
915 if (r == -ENODATA) { in dm_btree_find_key()
943 /*----------------------------------------------------------------*/
947 * space. Also this only works for single level trees.
965 nr = le32_to_cpu(n->header.nr_entries); in walk_node()
967 if (le32_to_cpu(n->header.flags) & INTERNAL_NODE) { in walk_node()
980 dm_tm_unlock(info->tm, node); in walk_node()
988 BUG_ON(info->levels > 1); in dm_btree_walk()
993 /*----------------------------------------------------------------*/
999 struct cursor_node *n = c->nodes + c->depth - 1; in prefetch_values()
1000 struct btree_node *bn = dm_block_data(n->b); in prefetch_values()
1001 struct dm_block_manager *bm = dm_tm_get_bm(c->info->tm); in prefetch_values()
1003 BUG_ON(c->info->value_type.size != sizeof(value_le)); in prefetch_values()
1005 nr = le32_to_cpu(bn->header.nr_entries); in prefetch_values()
1014 struct cursor_node *n = c->nodes + c->depth - 1; in leaf_node()
1015 struct btree_node *bn = dm_block_data(n->b); in leaf_node()
1017 return le32_to_cpu(bn->header.flags) & LEAF_NODE; in leaf_node()
1023 struct cursor_node *n = c->nodes + c->depth; in push_node()
1025 if (c->depth >= DM_BTREE_CURSOR_MAX_DEPTH - 1) { in push_node()
1027 return -EINVAL; in push_node()
1030 r = bn_read_lock(c->info, b, &n->b); in push_node()
1034 n->index = 0; in push_node()
1035 c->depth++; in push_node()
1037 if (c->prefetch_leaves || !leaf_node(c)) in push_node()
1045 c->depth--; in pop_node()
1046 unlock_block(c->info, c->nodes[c->depth].b); in pop_node()
1055 if (!c->depth) in inc_or_backtrack()
1056 return -ENODATA; in inc_or_backtrack()
1058 n = c->nodes + c->depth - 1; in inc_or_backtrack()
1059 bn = dm_block_data(n->b); in inc_or_backtrack()
1061 n->index++; in inc_or_backtrack()
1062 if (n->index < le32_to_cpu(bn->header.nr_entries)) in inc_or_backtrack()
1079 n = c->nodes + c->depth - 1; in find_leaf()
1080 bn = dm_block_data(n->b); in find_leaf()
1082 if (le32_to_cpu(bn->header.flags) & LEAF_NODE) in find_leaf()
1085 memcpy(&value_le, value_ptr(bn, n->index), sizeof(value_le)); in find_leaf()
1093 if (!r && (le32_to_cpu(bn->header.nr_entries) == 0)) in find_leaf()
1094 return -ENODATA; in find_leaf()
1104 c->info = info; in dm_btree_cursor_begin()
1105 c->root = root; in dm_btree_cursor_begin()
1106 c->depth = 0; in dm_btree_cursor_begin()
1107 c->prefetch_leaves = prefetch_leaves; in dm_btree_cursor_begin()
1119 while (c->depth) in dm_btree_cursor_end()
1141 while (count-- && !r) in dm_btree_cursor_skip()
1150 if (c->depth) { in dm_btree_cursor_get_value()
1151 struct cursor_node *n = c->nodes + c->depth - 1; in dm_btree_cursor_get_value()
1152 struct btree_node *bn = dm_block_data(n->b); in dm_btree_cursor_get_value()
1154 if (le32_to_cpu(bn->header.flags) & INTERNAL_NODE) in dm_btree_cursor_get_value()
1155 return -EINVAL; in dm_btree_cursor_get_value()
1157 *key = le64_to_cpu(*key_ptr(bn, n->index)); in dm_btree_cursor_get_value()
1158 memcpy(value_le, value_ptr(bn, n->index), c->info->value_type.size); in dm_btree_cursor_get_value()
1162 return -ENODATA; in dm_btree_cursor_get_value()