Lines Matching refs:offset
734 mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset) in mas_safe_min() argument
736 if (likely(offset)) in mas_safe_min()
737 return pivots[offset - 1] + 1; in mas_safe_min()
756 unsigned char offset, enum maple_type type) in mas_logical_pivot() argument
758 unsigned long lpiv = mas_safe_pivot(mas, pivots, offset, type); in mas_logical_pivot()
763 if (likely(offset)) in mas_logical_pivot()
825 void __rcu **slots, unsigned char offset) in mt_slot() argument
827 return rcu_dereference_check(slots[offset], mt_locked(mt)); in mt_slot()
831 unsigned char offset) in mt_slot_locked() argument
833 return rcu_dereference_protected(slots[offset], mt_locked(mt)); in mt_slot_locked()
844 unsigned char offset) in mas_slot_locked() argument
846 return mt_slot_locked(mas->tree, slots, offset); in mas_slot_locked()
858 unsigned char offset) in mas_slot() argument
860 return mt_slot(mas->tree, slots, offset); in mas_slot()
909 unsigned char offset, unsigned char end) in ma_set_meta() argument
913 meta->gap = offset; in ma_set_meta()
989 unsigned char offset) in ma_set_meta_gap() argument
994 meta->gap = offset; in ma_set_meta_gap()
1061 if (mas->offset) in mas_descend()
1062 mas->min = pivots[mas->offset - 1] + 1; in mas_descend()
1063 mas->max = mas_safe_pivot(mas, pivots, mas->offset, type); in mas_descend()
1064 mas->node = mas_slot(mas, slots, mas->offset); in mas_descend()
1108 mas->offset = 0; in mas_ascend()
1117 mas->offset = mte_parent_slot(mas->node); in mas_ascend()
1409 mas->offset = 0; in mas_start()
1419 mas->offset = MAPLE_NODE_SLOTS; in mas_start()
1425 mas->offset = MAPLE_NODE_SLOTS; in mas_start()
1452 unsigned char offset; in ma_data_end() local
1460 offset = mt_pivots[type] - 1; in ma_data_end()
1461 if (likely(!pivots[offset])) in ma_data_end()
1464 if (likely(pivots[offset] == max)) in ma_data_end()
1465 return offset; in ma_data_end()
1483 unsigned char offset; in mas_data_end() local
1495 offset = mt_pivots[type] - 1; in mas_data_end()
1496 if (likely(!pivots[offset])) in mas_data_end()
1499 if (likely(pivots[offset] == mas->max)) in mas_data_end()
1500 return offset; in mas_data_end()
1596 unsigned char offset, i; in ma_max_gap() local
1599 i = offset = ma_meta_end(node, mt); in ma_max_gap()
1603 offset = i; in ma_max_gap()
1607 *off = offset; in ma_max_gap()
1622 unsigned char offset; in mas_max_gap() local
1631 offset = ma_meta_gap(node, mt); in mas_max_gap()
1632 if (offset == MAPLE_ARANGE64_META_MAX) in mas_max_gap()
1636 return gaps[offset]; in mas_max_gap()
1648 static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, in mas_parent_gap() argument
1670 pgaps[offset] = new; in mas_parent_gap()
1675 if (offset != meta_offset) { in mas_parent_gap()
1679 ma_set_meta_gap(pnode, pmt, offset); in mas_parent_gap()
1693 offset = mte_parent_slot(penode); in mas_parent_gap()
1738 unsigned char offset; in mas_adopt_children() local
1740 offset = ma_data_end(node, type, pivots, mas->max); in mas_adopt_children()
1742 child = mas_slot_locked(mas, slots, offset); in mas_adopt_children()
1743 mte_set_parent(child, parent, offset); in mas_adopt_children()
1744 } while (offset--); in mas_adopt_children()
1757 unsigned char offset; in mas_put_in_tree() local
1766 offset = mte_parent_slot(mas->node); in mas_put_in_tree()
1769 rcu_assign_pointer(slots[offset], mas->node); in mas_put_in_tree()
1799 unsigned char offset; in mas_find_child() local
1811 for (offset = mas->offset; offset <= end; offset++) { in mas_find_child()
1812 entry = mas_slot_locked(mas, slots, offset); in mas_find_child()
1815 mas->offset = offset + 1; in mas_find_child()
1816 child->offset = offset; in mas_find_child()
1818 child->offset = 0; in mas_find_child()
2080 unsigned char offset = 15; in mab_mas_cp() local
2086 offset = j; in mab_mas_cp()
2091 ma_set_meta(node, mt, offset, end); in mab_mas_cp()
2138 slot = mas->offset; in mas_store_b_node()
2156 mas->offset = b_end; in mas_store_b_node()
2210 mas->offset = p_slot - 1; in mas_prev_sibling()
2230 parent.offset = mte_parent_slot(mas->node) + 1; in mas_next_sibling()
2231 if (parent.offset > mas_data_end(&parent)) in mas_next_sibling()
2265 unsigned char offset; in mas_wr_node_walk() local
2270 mas->offset = mas->index = mas->min; in mas_wr_node_walk()
2278 offset = mas->offset; in mas_wr_node_walk()
2279 min = mas_safe_min(mas, wr_mas->pivots, offset); in mas_wr_node_walk()
2280 if (unlikely(offset == count)) in mas_wr_node_walk()
2283 max = wr_mas->pivots[offset]; in mas_wr_node_walk()
2288 if (unlikely(!max && offset)) in mas_wr_node_walk()
2292 while (++offset < count) { in mas_wr_node_walk()
2293 max = wr_mas->pivots[offset]; in mas_wr_node_walk()
2307 wr_mas->offset_end = mas->offset = offset; in mas_wr_node_walk()
2339 mast->l->offset += end; in mast_rebalance_prev()
2362 if (mast->orig_r->offset < mas_data_end(mast->orig_r)) { in mast_spanning_rebalance()
2363 mast->orig_r->offset++; in mast_spanning_rebalance()
2366 mast->orig_r->offset = 0; in mast_spanning_rebalance()
2372 } else if (mast->orig_l->offset != 0) { in mast_spanning_rebalance()
2373 mast->orig_l->offset--; in mast_spanning_rebalance()
2376 mast->orig_l->offset = in mast_spanning_rebalance()
2404 mast->orig_r->offset = 0; in mast_ascend()
2413 mast->orig_l->offset = 0; in mast_ascend()
2575 slot = mast->l->offset; in mast_set_split_parents()
2641 tmp[0].offset = 0; in mas_topiary_replace()
2674 tmp[0].offset = 0; in mas_topiary_replace()
2783 unsigned char l_slot = mast->orig_l->offset; in mast_combine_cp_left()
2801 mas_mab_cp(mast->orig_r, mast->orig_r->offset + 1, in mast_combine_cp_right()
2836 unsigned char offset; in mtree_range_walk() local
2849 offset = 0; in mtree_range_walk()
2858 if (pivots[offset] >= mas->index) { in mtree_range_walk()
2861 max = pivots[offset]; in mtree_range_walk()
2866 offset++; in mtree_range_walk()
2867 } while ((offset < end) && (pivots[offset] < mas->index)); in mtree_range_walk()
2870 min = pivots[offset - 1] + 1; in mtree_range_walk()
2872 if (likely(offset < end && pivots[offset])) in mtree_range_walk()
2873 max = pivots[offset]; in mtree_range_walk()
2877 next = mt_slot(mas->tree, slots, offset); in mtree_range_walk()
2882 mas->offset = offset; in mtree_range_walk()
2975 l_mas.offset = mast->bn->b_end; in mas_spanning_rebalance()
3026 mas->offset = l_mas.offset; in mas_spanning_rebalance()
3081 mas->offset += shift; in mas_rebalance()
3104 unsigned char offset, tmp, split = mt_slots[mt] / 2; in mas_destroy_rebalance() local
3189 offset = mte_parent_slot(mas->node); in mas_destroy_rebalance()
3195 rcu_assign_pointer(slots[offset], mas->node); in mas_destroy_rebalance()
3196 rcu_assign_pointer(slots[offset - 1], l_mas.node); in mas_destroy_rebalance()
3197 pivs[offset - 1] = l_mas.max; in mas_destroy_rebalance()
3237 mte_set_parent(mast->l->node, ancestor, mast->l->offset); in mas_split_final_node()
3238 mte_set_parent(mast->r->node, ancestor, mast->r->offset); in mas_split_final_node()
3243 mas->offset = mast->bn->b_end - 1; in mas_split_final_node()
3269 mas->offset = mte_parent_slot(mas->node); in mast_fill_bnode()
3272 if (cp && mast->l->offset) in mast_fill_bnode()
3273 mas_mab_cp(mas, 0, mast->l->offset - 1, mast->bn, 0); in mast_fill_bnode()
3277 mast->r->offset = mast->bn->b_end; in mast_fill_bnode()
3305 mast->l->offset = mte_parent_slot(mas->node); in mast_split_data()
3311 p_slot = mast->orig_l->offset; in mast_split_data()
3384 mast->orig_l->offset += end + 1; in mas_push_data()
3586 mas->offset = slot; in mas_root_expand()
3678 wr_mas->mas->offset = 0; in mas_wr_walk_traverse()
3699 mas->offset); in mas_wr_walk()
3716 mas->offset); in mas_wr_walk_index()
3736 l_slot = l_mas->offset; in mas_extend_spanning_null()
3748 l_mas->offset = l_slot - 1; in mas_extend_spanning_null()
3754 r_mas->offset++; in mas_extend_spanning_null()
3757 !mas_slot_locked(r_mas, r_wr_mas->slots, r_mas->offset + 1)) { in mas_extend_spanning_null()
3759 r_wr_mas->type, r_mas->offset + 1); in mas_extend_spanning_null()
3760 r_mas->offset++; in mas_extend_spanning_null()
3790 unsigned char offset; in mtree_lookup_walk() local
3801 offset = 0; in mtree_lookup_walk()
3809 if (pivots[offset] >= mas->index) { in mtree_lookup_walk()
3810 max = pivots[offset]; in mtree_lookup_walk()
3813 } while (++offset < end); in mtree_lookup_walk()
3816 next = mt_slot(mas->tree, slots, offset); in mtree_lookup_walk()
3944 mas->offset = l_mas.offset; in mas_wr_spanning_store()
3959 if (r_mas.offset <= r_wr_mas.node_end) in mas_wr_spanning_store()
3960 mas_mab_cp(&r_mas, r_mas.offset, r_wr_mas.node_end, in mas_wr_spanning_store()
3990 unsigned char offset; in mas_wr_node_store() local
3996 offset = mas->offset; in mas_wr_node_store()
4000 new_end = offset; in mas_wr_node_store()
4013 new_end -= wr_mas->offset_end - offset - 1; in mas_wr_node_store()
4045 memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * (offset + 1)); in mas_wr_node_store()
4046 memcpy(dst_slots, wr_mas->slots, sizeof(void *) * (offset + 1)); in mas_wr_node_store()
4047 dst_offset = offset; in mas_wr_node_store()
4051 mas->offset++; in mas_wr_node_store()
4059 mas->offset = dst_offset; in mas_wr_node_store()
4113 unsigned char offset = mas->offset; in mas_wr_slot_store() local
4116 (offset != wr_mas->node_end))) in mas_wr_slot_store()
4119 if (offset == wr_mas->node_end - 1) in mas_wr_slot_store()
4122 lmax = wr_mas->pivots[offset + 1]; in mas_wr_slot_store()
4134 rcu_assign_pointer(wr_mas->slots[offset], wr_mas->entry); in mas_wr_slot_store()
4135 wr_mas->pivots[offset] = mas->last; in mas_wr_slot_store()
4144 if ((offset + 1 < mt_pivots[wr_mas->type]) && in mas_wr_slot_store()
4145 (wr_mas->entry || wr_mas->pivots[offset + 1])) in mas_wr_slot_store()
4146 wr_mas->pivots[offset + 1] = mas->last; in mas_wr_slot_store()
4148 rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry); in mas_wr_slot_store()
4149 wr_mas->pivots[offset] = mas->index - 1; in mas_wr_slot_store()
4150 mas->offset++; /* Keep mas accurate. */ in mas_wr_slot_store()
4182 if (mas->index == wr_mas->r_min && mas->offset && in mas_wr_extend_null()
4183 !wr_mas->slots[mas->offset - 1]) { in mas_wr_extend_null()
4184 mas->offset--; in mas_wr_extend_null()
4186 mas_safe_min(mas, wr_mas->pivots, mas->offset); in mas_wr_extend_null()
4187 wr_mas->r_max = wr_mas->pivots[mas->offset]; in mas_wr_extend_null()
4227 mas->offset = new_end; in mas_wr_append()
4267 return wr_mas->node_end - wr_mas->offset_end + wr_mas->mas->offset + 2; in mas_wr_node_size()
4278 rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry); in mas_wr_modify()
4293 (mas->offset == wr_mas->node_end) && mas_wr_append(wr_mas)) { in mas_wr_modify()
4299 if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas)) in mas_wr_modify()
4386 wr_mas.offset_end = mas->offset; in mas_insert()
4435 int offset, level; in mas_prev_node() local
4457 offset = mas->offset; in mas_prev_node()
4460 } while (!offset); in mas_prev_node()
4462 offset--; in mas_prev_node()
4467 mas->node = mas_slot(mas, slots, offset); in mas_prev_node()
4474 offset = ma_data_end(node, mt, pivots, max); in mas_prev_node()
4480 mas->node = mas_slot(mas, slots, offset); in mas_prev_node()
4485 if (likely(offset)) in mas_prev_node()
4486 mas->min = pivots[offset - 1] + 1; in mas_prev_node()
4488 mas->offset = mas_data_end(mas); in mas_prev_node()
4529 pivot = mas_safe_min(mas, pivots, mas->offset); in mas_prev_slot()
4538 if (likely(mas->offset)) { in mas_prev_slot()
4539 mas->offset--; in mas_prev_slot()
4541 mas->index = mas_safe_min(mas, pivots, mas->offset); in mas_prev_slot()
4555 mas->index = pivots[mas->offset - 1] + 1; in mas_prev_slot()
4559 entry = mas_slot(mas, slots, mas->offset); in mas_prev_slot()
4612 } while (unlikely(mas->offset == node_end)); in mas_next_node()
4615 mas->offset++; in mas_next_node()
4616 enode = mas_slot(mas, slots, mas->offset); in mas_next_node()
4621 mas->offset = 0; in mas_next_node()
4634 if (!mas->offset) in mas_next_node()
4637 mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt); in mas_next_node()
4683 if (likely(mas->offset < data_end)) in mas_next_slot()
4684 pivot = pivots[mas->offset]; in mas_next_slot()
4695 if (likely(mas->offset < data_end)) { in mas_next_slot()
4696 mas->index = pivots[mas->offset] + 1; in mas_next_slot()
4697 mas->offset++; in mas_next_slot()
4698 if (likely(mas->offset < data_end)) in mas_next_slot()
4699 mas->last = pivots[mas->offset]; in mas_next_slot()
4711 mas->offset = 0; in mas_next_slot()
4720 entry = mt_slot(mas->tree, slots, mas->offset); in mas_next_slot()
4728 if (!mas->offset) in mas_next_slot()
4774 unsigned char offset; in mas_rev_awalk() local
4781 mas->offset = (unsigned char)(mas->index - mas->min); in mas_rev_awalk()
4788 offset = mas->offset; in mas_rev_awalk()
4789 min = mas_safe_min(mas, pivots, offset); in mas_rev_awalk()
4792 min = mas_safe_min(mas, pivots, --offset); in mas_rev_awalk()
4794 max = mas_safe_pivot(mas, pivots, offset, type); in mas_rev_awalk()
4798 gap = gaps[offset]; in mas_rev_awalk()
4799 else if (!mas_slot(mas, slots, offset)) in mas_rev_awalk()
4808 if (offset < 2) in mas_rev_awalk()
4811 offset -= 2; in mas_rev_awalk()
4812 max = pivots[offset]; in mas_rev_awalk()
4813 min = mas_safe_min(mas, pivots, offset); in mas_rev_awalk()
4818 if (!offset) in mas_rev_awalk()
4821 offset--; in mas_rev_awalk()
4823 min = mas_safe_min(mas, pivots, offset); in mas_rev_awalk()
4830 mas->offset = offset; in mas_rev_awalk()
4837 mas->node = mas_slot(mas, slots, offset); in mas_rev_awalk()
4840 mas->offset = mas_data_end(mas); in mas_rev_awalk()
4856 unsigned char offset, data_end; in mas_anode_descend() local
4863 mas->offset = (unsigned char)(mas->index - mas->min); in mas_anode_descend()
4871 offset = mas->offset; in mas_anode_descend()
4872 min = mas_safe_min(mas, pivots, offset); in mas_anode_descend()
4874 for (; offset <= data_end; offset++) { in mas_anode_descend()
4875 pivot = mas_logical_pivot(mas, pivots, offset, type); in mas_anode_descend()
4882 gap = gaps[offset]; in mas_anode_descend()
4883 else if (!mas_slot(mas, slots, offset)) in mas_anode_descend()
4894 mas->node = mas_slot(mas, slots, offset); in mas_anode_descend()
4897 offset = 0; in mas_anode_descend()
4912 mas->offset = offset; in mas_anode_descend()
4960 slot = mas->offset; in mas_rewind_node()
4965 slot = mas->offset; in mas_rewind_node()
4969 mas->offset = --slot; in mas_rewind_node()
4986 if (mas->offset >= mas_data_end(mas)) { in mas_skip_node()
4993 } while (mas->offset >= mas_data_end(mas)); in mas_skip_node()
4995 mas->offset++; in mas_skip_node()
5062 mas->offset = slot; in mas_fill_gap()
5107 unsigned char offset; in mas_empty_area() local
5116 else if (mas->offset >= 2) in mas_empty_area()
5117 mas->offset -= 2; in mas_empty_area()
5135 offset = mas->offset; in mas_empty_area()
5136 if (unlikely(offset == MAPLE_NODE_SLOTS)) in mas_empty_area()
5141 min = mas_safe_min(mas, pivots, offset); in mas_empty_area()
5167 mas->offset = mas_data_end(mas); in mas_empty_area_rev()
5168 } else if (mas->offset >= 2) { in mas_empty_area_rev()
5169 mas->offset -= 2; in mas_empty_area_rev()
5196 if (unlikely(mas->offset == MAPLE_NODE_SLOTS)) in mas_empty_area_rev()
5229 if (mas->offset == MAPLE_NODE_SLOTS) in mas_alloc()
5237 if (mas->offset) in mas_alloc()
5238 min = mte_pivot(mas->node, mas->offset - 1) + 1; in mas_alloc()
5243 mas_fill_gap(mas, entry, mas->offset, size, index); in mas_alloc()
5263 if (mas->offset == MAPLE_NODE_SLOTS) in mas_rev_alloc()
5266 mas_fill_gap(mas, entry, mas->offset, size, index); in mas_rev_alloc()
5290 int offset; in mte_dead_leaves() local
5292 for (offset = 0; offset < mt_slot_count(enode); offset++) { in mte_dead_leaves()
5293 entry = mt_slot(mt, slots, offset); in mte_dead_leaves()
5302 rcu_assign_pointer(slots[offset], node); in mte_dead_leaves()
5305 return offset; in mte_dead_leaves()
5315 static void __rcu **mte_dead_walk(struct maple_enode **enode, unsigned char offset) in mte_dead_walk() argument
5325 next = rcu_dereference_protected(slots[offset], in mte_dead_walk()
5327 offset = 0; in mte_dead_walk()
5344 unsigned char offset; in mt_free_walk() local
5358 offset = node->parent_slot + 1; in mt_free_walk()
5365 if ((offset < mt_slots[type]) && in mt_free_walk()
5366 rcu_dereference_protected(slots[offset], in mt_free_walk()
5368 slots = mte_dead_walk(&enode, offset); in mt_free_walk()
5370 } while ((node != start) || (node->slot_len < offset)); in mt_free_walk()
5380 struct maple_tree *mt, struct maple_enode *prev, unsigned char offset) in mte_destroy_descend() argument
5400 node->parent_slot = offset; in mte_destroy_descend()
5401 offset = next_offset; in mte_destroy_descend()
5426 unsigned char offset; in mt_destroy_walk() local
5432 offset = node->parent_slot + 1; in mt_destroy_walk()
5439 if (offset >= mt_slots[type]) in mt_destroy_walk()
5442 tmp = mt_slot_locked(mt, slots, offset); in mt_destroy_walk()
5446 slots = mte_destroy_descend(&enode, mt, parent, offset); in mt_destroy_walk()
5641 if (node_size == wr_mas.node_end && wr_mas.offset_end - mas->offset == 1) in mas_preallocate()
5651 if (node_size == wr_mas.node_end + 1 && mas->offset == wr_mas.node_end) in mas_preallocate()
6472 mas.offset = 0; in mtree_alloc_range()
6564 if (mas->offset) { in mas_dup_free()
6565 mas->offset--; in mas_dup_free()
6568 mas->offset = mas_data_end(mas); in mas_dup_free()
6713 } while (mas->offset == mas_data_end(mas)); in mas_dup_build()
6716 mas->offset++; in mas_dup_build()
6717 new_mas->offset++; in mas_dup_build()
6723 mas->offset = 0; in mas_dup_build()
6724 new_mas->offset = 0; in mas_dup_build()
7010 unsigned char offset) in mas_get_slot() argument
7013 offset); in mas_get_slot()
7041 mas->offset = 0; in mas_first_entry()
7069 mas->offset = 1; in mas_first_entry()
7512 unsigned char offset = 0; in mt_validate_nulls() local
7525 entry = mas_slot(&mas, slots, offset); in mt_validate_nulls()
7528 mas_mn(&mas), offset); in mt_validate_nulls()
7532 if (offset == mas_data_end(&mas)) { in mt_validate_nulls()
7536 offset = 0; in mt_validate_nulls()
7540 offset++; in mt_validate_nulls()