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()
90 uint32_t max_entries = le32_to_cpu(node->header.max_entries); in insert_at()
98 return -ENOMEM; in insert_at()
103 array_insert(node->keys, sizeof(*node->keys), nr_entries, index, &key_le); in insert_at()
105 node->header.nr_entries = cpu_to_le32(nr_entries + 1); in insert_at()
110 /*----------------------------------------------------------------*/
121 block_size -= sizeof(struct node_header); in calc_max_entries()
140 block_size = dm_bm_block_size(dm_tm_get_bm(info->tm)); in dm_btree_empty()
141 max_entries = calc_max_entries(info->value_type.size, block_size); in dm_btree_empty()
145 n->header.flags = cpu_to_le32(LEAF_NODE); in dm_btree_empty()
146 n->header.nr_entries = cpu_to_le32(0); in dm_btree_empty()
147 n->header.max_entries = cpu_to_le32(max_entries); in dm_btree_empty()
148 n->header.value_size = cpu_to_le32(info->value_type.size); in dm_btree_empty()
157 /*----------------------------------------------------------------*/
167 unsigned level; member
175 int top; member
181 if (s->top < 0) { in top_frame()
183 return -EINVAL; in top_frame()
186 *f = s->spine + s->top; in top_frame()
193 return s->top >= 0; in unprocessed_frames()
199 struct dm_block_manager *bm = dm_tm_get_bm(s->tm); in prefetch_children()
201 for (i = 0; i < f->nr_children; i++) in prefetch_children()
202 dm_bm_prefetch(bm, value64(f->n, i)); in prefetch_children()
207 return f->level < (info->levels - 1); in is_internal_level()
210 static int push_frame(struct del_stack *s, dm_block_t b, unsigned level) in push_frame() argument
215 if (s->top >= MAX_SPINE_DEPTH - 1) { in push_frame()
217 return -ENOMEM; in push_frame()
220 r = dm_tm_ref(s->tm, b, &ref_count); in push_frame()
229 dm_tm_dec(s->tm, b); in push_frame()
233 struct frame *f = s->spine + ++s->top; in push_frame()
235 r = dm_tm_read_lock(s->tm, b, &btree_node_validator, &f->b); in push_frame()
237 s->top--; in push_frame()
241 f->n = dm_block_data(f->b); in push_frame()
242 f->level = level; in push_frame()
243 f->nr_children = le32_to_cpu(f->n->header.nr_entries); in push_frame()
244 f->current_child = 0; in push_frame()
246 flags = le32_to_cpu(f->n->header.flags); in push_frame()
247 if (flags & INTERNAL_NODE || is_internal_level(s->info, f)) in push_frame()
256 struct frame *f = s->spine + s->top--; in pop_frame()
258 dm_tm_dec(s->tm, dm_block_location(f->b)); in pop_frame()
259 dm_tm_unlock(s->tm, f->b); in pop_frame()
267 f = s->spine + s->top--; in unlock_all_frames()
268 dm_tm_unlock(s->tm, f->b); in unlock_all_frames()
284 return -ENOMEM; in dm_btree_del()
285 s->info = info; in dm_btree_del()
286 s->tm = info->tm; in dm_btree_del()
287 s->top = -1; in dm_btree_del()
302 if (f->current_child >= f->nr_children) { in dm_btree_del()
307 flags = le32_to_cpu(f->n->header.flags); in dm_btree_del()
309 b = value64(f->n, f->current_child); in dm_btree_del()
310 f->current_child++; in dm_btree_del()
311 r = push_frame(s, b, f->level); in dm_btree_del()
316 b = value64(f->n, f->current_child); in dm_btree_del()
317 f->current_child++; in dm_btree_del()
318 r = push_frame(s, b, f->level + 1); in dm_btree_del()
323 if (info->value_type.dec) { in dm_btree_del()
326 for (i = 0; i < f->nr_children; i++) in dm_btree_del()
327 info->value_type.dec(info->value_type.context, in dm_btree_del()
328 value_ptr(f->n, i)); in dm_btree_del()
344 /*----------------------------------------------------------------*/
360 flags = le32_to_cpu(ro_node(s)->header.flags); in btree_lookup_raw()
361 nr_entries = le32_to_cpu(ro_node(s)->header.nr_entries); in btree_lookup_raw()
363 return -ENODATA; in btree_lookup_raw()
370 *result_key = le64_to_cpu(ro_node(s)->keys[i]); in btree_lookup_raw()
380 unsigned level, last_level = info->levels - 1; in dm_btree_lookup() local
381 int r = -ENODATA; in dm_btree_lookup()
387 for (level = 0; level < info->levels; level++) { in dm_btree_lookup()
391 if (level == last_level) { in dm_btree_lookup()
393 size = info->value_type.size; in dm_btree_lookup()
400 r = btree_lookup_raw(&spine, root, keys[level], in dm_btree_lookup()
405 if (rkey != keys[level]) { in dm_btree_lookup()
407 return -ENODATA; in dm_btree_lookup()
435 flags = le32_to_cpu(n->header.flags); in dm_btree_lookup_next_single()
436 nr_entries = le32_to_cpu(n->header.nr_entries); in dm_btree_lookup_next_single()
442 * avoid early -ENODATA return when all entries are in dm_btree_lookup_next_single()
448 r = -ENODATA; in dm_btree_lookup_next_single()
453 if (r == -ENODATA && i < (nr_entries - 1)) { in dm_btree_lookup_next_single()
461 r = -ENODATA; in dm_btree_lookup_next_single()
465 *rkey = le64_to_cpu(n->keys[i]); in dm_btree_lookup_next_single()
466 memcpy(value_le, value_ptr(n, i), info->value_type.size); in dm_btree_lookup_next_single()
469 dm_tm_unlock(info->tm, node); in dm_btree_lookup_next_single()
476 unsigned level; in dm_btree_lookup_next() local
477 int r = -ENODATA; in dm_btree_lookup_next()
482 for (level = 0; level < info->levels - 1u; level++) { in dm_btree_lookup_next()
483 r = btree_lookup_raw(&spine, root, keys[level], in dm_btree_lookup_next()
489 if (*rkey != keys[level]) { in dm_btree_lookup_next()
490 r = -ENODATA; in dm_btree_lookup_next()
497 r = dm_btree_lookup_next_single(info, root, keys[level], rkey, value_le); in dm_btree_lookup_next()
511 * +--------+
513 * +--------+
516 * +----------+
518 * +----------+
522 * +--------+
524 * +--------+
526 * v +------+
527 * +---------+ |
529 * +---------+ +-------+
531 * +-------+
547 r = new_block(s->info, &right); in btree_split_sibling()
554 nr_left = le32_to_cpu(ln->header.nr_entries) / 2; in btree_split_sibling()
555 nr_right = le32_to_cpu(ln->header.nr_entries) - nr_left; in btree_split_sibling()
557 ln->header.nr_entries = cpu_to_le32(nr_left); in btree_split_sibling()
559 rn->header.flags = ln->header.flags; in btree_split_sibling()
560 rn->header.nr_entries = cpu_to_le32(nr_right); in btree_split_sibling()
561 rn->header.max_entries = ln->header.max_entries; in btree_split_sibling()
562 rn->header.value_size = ln->header.value_size; in btree_split_sibling()
563 memcpy(rn->keys, ln->keys + nr_left, nr_right * sizeof(rn->keys[0])); in btree_split_sibling()
565 size = le32_to_cpu(ln->header.flags) & INTERNAL_NODE ? in btree_split_sibling()
566 sizeof(uint64_t) : s->info->value_type.size; in btree_split_sibling()
585 le64_to_cpu(rn->keys[0]), &location); in btree_split_sibling()
587 unlock_block(s->info, right); in btree_split_sibling()
591 if (key < le64_to_cpu(rn->keys[0])) { in btree_split_sibling()
592 unlock_block(s->info, right); in btree_split_sibling()
593 s->nodes[1] = left; in btree_split_sibling()
595 unlock_block(s->info, left); in btree_split_sibling()
596 s->nodes[1] = right; in btree_split_sibling()
606 * +----------+
608 * +----------+
612 * +------------+
614 * +------------+
616 * +------+ +----+
619 * +-------+ +-------+
621 * +-------+ +-------+
635 size = le32_to_cpu(pn->header.flags) & INTERNAL_NODE ? in btree_split_beneath()
636 sizeof(__le64) : s->info->value_type.size; in btree_split_beneath()
639 r = new_block(s->info, &left); in btree_split_beneath()
644 nr_left = le32_to_cpu(pn->header.nr_entries) / 2; in btree_split_beneath()
646 ln->header.flags = pn->header.flags; in btree_split_beneath()
647 ln->header.nr_entries = cpu_to_le32(nr_left); in btree_split_beneath()
648 ln->header.max_entries = pn->header.max_entries; in btree_split_beneath()
649 ln->header.value_size = pn->header.value_size; in btree_split_beneath()
650 memcpy(ln->keys, pn->keys, nr_left * sizeof(pn->keys[0])); in btree_split_beneath()
654 r = new_block(s->info, &right); in btree_split_beneath()
656 unlock_block(s->info, left); in btree_split_beneath()
661 nr_right = le32_to_cpu(pn->header.nr_entries) - nr_left; in btree_split_beneath()
663 rn->header.flags = pn->header.flags; in btree_split_beneath()
664 rn->header.nr_entries = cpu_to_le32(nr_right); in btree_split_beneath()
665 rn->header.max_entries = pn->header.max_entries; in btree_split_beneath()
666 rn->header.value_size = pn->header.value_size; in btree_split_beneath()
667 memcpy(rn->keys, pn->keys + nr_left, nr_right * sizeof(pn->keys[0])); in btree_split_beneath()
672 pn->header.flags = cpu_to_le32(INTERNAL_NODE); in btree_split_beneath()
673 pn->header.nr_entries = cpu_to_le32(2); in btree_split_beneath()
674 pn->header.max_entries = cpu_to_le32( in btree_split_beneath()
677 dm_tm_get_bm(s->info->tm)))); in btree_split_beneath()
678 pn->header.value_size = cpu_to_le32(sizeof(__le64)); in btree_split_beneath()
682 pn->keys[0] = ln->keys[0]; in btree_split_beneath()
687 pn->keys[1] = rn->keys[0]; in btree_split_beneath()
690 unlock_block(s->info, left); in btree_split_beneath()
691 unlock_block(s->info, right); in btree_split_beneath()
699 int r, i = *index, top = 1; in btree_insert_raw() local
724 if (node->header.nr_entries == node->header.max_entries) { in btree_insert_raw()
725 if (top) in btree_insert_raw()
738 if (le32_to_cpu(node->header.flags) & LEAF_NODE) in btree_insert_raw()
743 node->keys[0] = cpu_to_le64(key); in btree_insert_raw()
748 top = 0; in btree_insert_raw()
751 if (i < 0 || le64_to_cpu(node->keys[i]) != key) in btree_insert_raw()
759 unsigned level, unsigned index) in need_insert() argument
761 return ((index >= le32_to_cpu(node->header.nr_entries)) || in need_insert()
762 (le64_to_cpu(node->keys[index]) != keys[level])); in need_insert()
771 unsigned level, index = -1, last_level = info->levels - 1; in insert() local
777 init_le64_type(info->tm, &le64_type); in insert()
780 for (level = 0; level < (info->levels - 1); level++) { in insert()
781 r = btree_insert_raw(&spine, block, &le64_type, keys[level], &index); in insert()
787 if (need_insert(n, keys, level, index)) { in insert()
799 keys[level], &new_le); in insert()
804 if (level < last_level) in insert()
808 r = btree_insert_raw(&spine, block, &info->value_type, in insert()
809 keys[level], &index); in insert()
815 if (need_insert(n, keys, level, index)) { in insert()
819 r = insert_at(info->value_type.size, n, index, in insert()
820 keys[level], value); in insert()
827 if (info->value_type.dec && in insert()
828 (!info->value_type.equal || in insert()
829 !info->value_type.equal( in insert()
830 info->value_type.context, in insert()
833 info->value_type.dec(info->value_type.context, in insert()
837 value, info->value_type.size); in insert()
869 /*----------------------------------------------------------------*/
882 flags = le32_to_cpu(ro_node(s)->header.flags); in find_key()
883 i = le32_to_cpu(ro_node(s)->header.nr_entries); in find_key()
885 return -ENODATA; in find_key()
887 i--; in find_key()
890 *result_key = le64_to_cpu(ro_node(s)->keys[i]); in find_key()
892 *result_key = le64_to_cpu(ro_node(s)->keys[0]); in find_key()
911 int r = 0, count = 0, level; in dm_btree_find_key() local
915 for (level = 0; level < info->levels; level++) { in dm_btree_find_key()
916 r = find_key(&spine, root, find_highest, result_keys + level, in dm_btree_find_key()
917 level == info->levels - 1 ? NULL : &root); in dm_btree_find_key()
918 if (r == -ENODATA) { in dm_btree_find_key()
946 /*----------------------------------------------------------------*/
950 * space. Also this only works for single level trees.
968 nr = le32_to_cpu(n->header.nr_entries); in walk_node()
970 if (le32_to_cpu(n->header.flags) & INTERNAL_NODE) { in walk_node()
983 dm_tm_unlock(info->tm, node); in walk_node()
991 BUG_ON(info->levels > 1); in dm_btree_walk()
996 /*----------------------------------------------------------------*/
1002 struct cursor_node *n = c->nodes + c->depth - 1; in prefetch_values()
1003 struct btree_node *bn = dm_block_data(n->b); in prefetch_values()
1004 struct dm_block_manager *bm = dm_tm_get_bm(c->info->tm); in prefetch_values()
1006 BUG_ON(c->info->value_type.size != sizeof(value_le)); in prefetch_values()
1008 nr = le32_to_cpu(bn->header.nr_entries); in prefetch_values()
1017 struct cursor_node *n = c->nodes + c->depth - 1; in leaf_node()
1018 struct btree_node *bn = dm_block_data(n->b); in leaf_node()
1020 return le32_to_cpu(bn->header.flags) & LEAF_NODE; in leaf_node()
1026 struct cursor_node *n = c->nodes + c->depth; in push_node()
1028 if (c->depth >= DM_BTREE_CURSOR_MAX_DEPTH - 1) { in push_node()
1030 return -EINVAL; in push_node()
1033 r = bn_read_lock(c->info, b, &n->b); in push_node()
1037 n->index = 0; in push_node()
1038 c->depth++; in push_node()
1040 if (c->prefetch_leaves || !leaf_node(c)) in push_node()
1048 c->depth--; in pop_node()
1049 unlock_block(c->info, c->nodes[c->depth].b); in pop_node()
1058 if (!c->depth) in inc_or_backtrack()
1059 return -ENODATA; in inc_or_backtrack()
1061 n = c->nodes + c->depth - 1; in inc_or_backtrack()
1062 bn = dm_block_data(n->b); in inc_or_backtrack()
1064 n->index++; in inc_or_backtrack()
1065 if (n->index < le32_to_cpu(bn->header.nr_entries)) in inc_or_backtrack()
1082 n = c->nodes + c->depth - 1; in find_leaf()
1083 bn = dm_block_data(n->b); in find_leaf()
1085 if (le32_to_cpu(bn->header.flags) & LEAF_NODE) in find_leaf()
1088 memcpy(&value_le, value_ptr(bn, n->index), sizeof(value_le)); in find_leaf()
1096 if (!r && (le32_to_cpu(bn->header.nr_entries) == 0)) in find_leaf()
1097 return -ENODATA; in find_leaf()
1107 c->info = info; in dm_btree_cursor_begin()
1108 c->root = root; in dm_btree_cursor_begin()
1109 c->depth = 0; in dm_btree_cursor_begin()
1110 c->prefetch_leaves = prefetch_leaves; in dm_btree_cursor_begin()
1122 while (c->depth) in dm_btree_cursor_end()
1144 while (count-- && !r) in dm_btree_cursor_skip()
1153 if (c->depth) { in dm_btree_cursor_get_value()
1154 struct cursor_node *n = c->nodes + c->depth - 1; in dm_btree_cursor_get_value()
1155 struct btree_node *bn = dm_block_data(n->b); in dm_btree_cursor_get_value()
1157 if (le32_to_cpu(bn->header.flags) & INTERNAL_NODE) in dm_btree_cursor_get_value()
1158 return -EINVAL; in dm_btree_cursor_get_value()
1160 *key = le64_to_cpu(*key_ptr(bn, n->index)); in dm_btree_cursor_get_value()
1161 memcpy(value_le, value_ptr(bn, n->index), c->info->value_type.size); in dm_btree_cursor_get_value()
1165 return -ENODATA; in dm_btree_cursor_get_value()