Lines Matching refs:offset
717 mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset) in mas_safe_min() argument
719 if (likely(offset)) in mas_safe_min()
720 return pivots[offset - 1] + 1; in mas_safe_min()
787 void __rcu **slots, unsigned char offset) in mt_slot() argument
789 return rcu_dereference_check(slots[offset], mt_locked(mt)); in mt_slot()
793 void __rcu **slots, unsigned char offset) in mt_slot_locked() argument
795 return rcu_dereference_protected(slots[offset], mt_write_locked(mt)); in mt_slot_locked()
806 void __rcu **slots, unsigned char offset) in mas_slot_locked() argument
808 return mt_slot_locked(mas->tree, slots, offset); in mas_slot_locked()
820 unsigned char offset) in mas_slot() argument
822 return mt_slot(mas->tree, slots, offset); in mas_slot()
871 unsigned char offset, unsigned char end) in ma_set_meta() argument
875 meta->gap = offset; in ma_set_meta()
945 unsigned char offset) in ma_set_meta_gap() argument
950 meta->gap = offset; in ma_set_meta_gap()
1017 if (mas->offset) in mas_descend()
1018 mas->min = pivots[mas->offset - 1] + 1; in mas_descend()
1019 mas->max = mas_safe_pivot(mas, pivots, mas->offset, type); in mas_descend()
1020 mas->node = mas_slot(mas, slots, mas->offset); in mas_descend()
1064 mas->offset = 0; in mas_ascend()
1073 mas->offset = mte_parent_slot(mas->node); in mas_ascend()
1090 if (!mas->offset) { in mas_ascend()
1367 mas->offset = 0; in mas_start()
1378 mas->offset = MAPLE_NODE_SLOTS; in mas_start()
1384 mas->offset = MAPLE_NODE_SLOTS; in mas_start()
1409 unsigned char offset; in ma_data_end() local
1417 offset = mt_pivots[type] - 1; in ma_data_end()
1418 if (likely(!pivots[offset])) in ma_data_end()
1421 if (likely(pivots[offset] == max)) in ma_data_end()
1422 return offset; in ma_data_end()
1440 unsigned char offset; in mas_data_end() local
1452 offset = mt_pivots[type] - 1; in mas_data_end()
1453 if (likely(!pivots[offset])) in mas_data_end()
1456 if (likely(pivots[offset] == mas->max)) in mas_data_end()
1457 return offset; in mas_data_end()
1556 unsigned char offset, i; in ma_max_gap() local
1559 i = offset = ma_meta_end(node, mt); in ma_max_gap()
1563 offset = i; in ma_max_gap()
1567 *off = offset; in ma_max_gap()
1580 unsigned char offset; in mas_max_gap() local
1590 offset = ma_meta_gap(node); in mas_max_gap()
1592 return gaps[offset]; in mas_max_gap()
1604 static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, in mas_parent_gap() argument
1624 pgaps[offset] = new; in mas_parent_gap()
1629 if (offset != meta_offset) { in mas_parent_gap()
1633 ma_set_meta_gap(pnode, pmt, offset); in mas_parent_gap()
1646 offset = mte_parent_slot(penode); in mas_parent_gap()
1691 unsigned char offset; in mas_adopt_children() local
1693 offset = ma_data_end(node, type, pivots, mas->max); in mas_adopt_children()
1695 child = mas_slot_locked(mas, slots, offset); in mas_adopt_children()
1696 mas_set_parent(mas, child, parent, offset); in mas_adopt_children()
1697 } while (offset--); in mas_adopt_children()
1710 unsigned char offset; in mas_put_in_tree() local
1719 offset = mte_parent_slot(mas->node); in mas_put_in_tree()
1722 rcu_assign_pointer(slots[offset], mas->node); in mas_put_in_tree()
1752 unsigned char offset; in mas_find_child() local
1764 for (offset = mas->offset; offset <= end; offset++) { in mas_find_child()
1765 entry = mas_slot_locked(mas, slots, offset); in mas_find_child()
1768 mas->offset = offset + 1; in mas_find_child()
1769 child->offset = offset; in mas_find_child()
1771 child->offset = 0; in mas_find_child()
2008 unsigned char offset = 0; in mab_mas_cp() local
2014 offset = j; in mab_mas_cp()
2019 ma_set_meta(node, mt, offset, end); in mab_mas_cp()
2066 slot = mas->offset; in mas_store_b_node()
2084 mas->offset = b_end; in mas_store_b_node()
2138 mas->offset = p_slot - 1; in mas_prev_sibling()
2158 parent.offset = mte_parent_slot(mas->node) + 1; in mas_next_sibling()
2159 if (parent.offset > mas_data_end(&parent)) in mas_next_sibling()
2197 unsigned char count, offset; in mas_wr_node_walk() local
2201 mas->offset = mas->index = mas->min; in mas_wr_node_walk()
2209 offset = mas->offset; in mas_wr_node_walk()
2211 while (offset < count && mas->index > wr_mas->pivots[offset]) in mas_wr_node_walk()
2212 offset++; in mas_wr_node_walk()
2214 wr_mas->r_max = offset < count ? wr_mas->pivots[offset] : mas->max; in mas_wr_node_walk()
2215 wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, offset); in mas_wr_node_walk()
2216 wr_mas->offset_end = mas->offset = offset; in mas_wr_node_walk()
2246 mast->l->offset += end; in mast_rebalance_prev()
2267 if (mast->orig_r->offset < mas_data_end(mast->orig_r)) { in mast_spanning_rebalance()
2268 mast->orig_r->offset++; in mast_spanning_rebalance()
2271 mast->orig_r->offset = 0; in mast_spanning_rebalance()
2277 } else if (mast->orig_l->offset != 0) { in mast_spanning_rebalance()
2278 mast->orig_l->offset--; in mast_spanning_rebalance()
2281 mast->orig_l->offset = in mast_spanning_rebalance()
2309 mast->orig_r->offset = 0; in mast_ascend()
2318 mast->orig_l->offset = 0; in mast_ascend()
2480 slot = mast->l->offset; in mast_set_split_parents()
2547 tmp[0].offset = 0; in mas_topiary_replace()
2580 tmp[0].offset = 0; in mas_topiary_replace()
2689 unsigned char l_slot = mast->orig_l->offset; in mast_combine_cp_left()
2707 mas_mab_cp(mast->orig_r, mast->orig_r->offset + 1, in mast_combine_cp_right()
2742 unsigned char offset; in mtree_range_walk() local
2763 offset = 0; in mtree_range_walk()
2768 offset = 1; in mtree_range_walk()
2769 while (offset < end) { in mtree_range_walk()
2770 if (pivots[offset] >= mas->index) { in mtree_range_walk()
2771 max = pivots[offset]; in mtree_range_walk()
2774 offset++; in mtree_range_walk()
2777 min = pivots[offset - 1] + 1; in mtree_range_walk()
2780 next = mt_slot(mas->tree, slots, offset); in mtree_range_walk()
2786 mas->offset = offset; in mtree_range_walk()
2877 l_mas.offset = mast->bn->b_end; in mas_spanning_rebalance()
2928 mas->offset = l_mas.offset; in mas_spanning_rebalance()
2978 mas->offset += shift; in mas_rebalance()
3001 unsigned char offset, tmp, split = mt_slots[mt] / 2; in mas_destroy_rebalance() local
3081 offset = mte_parent_slot(mas->node); in mas_destroy_rebalance()
3087 rcu_assign_pointer(slots[offset], mas->node); in mas_destroy_rebalance()
3088 rcu_assign_pointer(slots[offset - 1], l_mas.node); in mas_destroy_rebalance()
3089 pivs[offset - 1] = l_mas.max; in mas_destroy_rebalance()
3129 mas_set_parent(mas, mast->l->node, ancestor, mast->l->offset); in mas_split_final_node()
3130 mas_set_parent(mas, mast->r->node, ancestor, mast->r->offset); in mas_split_final_node()
3135 mas->offset = mast->bn->b_end - 1; in mas_split_final_node()
3160 mas->offset = mte_parent_slot(mas->node); in mast_fill_bnode()
3163 if (cp && mast->l->offset) in mast_fill_bnode()
3164 mas_mab_cp(mas, 0, mast->l->offset - 1, mast->bn, 0); in mast_fill_bnode()
3168 mast->r->offset = mast->bn->b_end; in mast_fill_bnode()
3196 mast->l->offset = mte_parent_slot(mas->node); in mast_split_data()
3202 p_slot = mast->orig_l->offset; in mast_split_data()
3275 mast->orig_l->offset += end + 1; in mas_push_data()
3418 mas->offset = slot; in mas_root_expand()
3506 wr_mas->mas->offset = 0; in mas_wr_walk_traverse()
3527 mas->offset); in mas_wr_walk()
3544 mas->offset); in mas_wr_walk_index()
3562 l_slot = l_mas->offset; in mas_extend_spanning_null()
3574 l_mas->offset = l_slot - 1; in mas_extend_spanning_null()
3580 r_mas->offset++; in mas_extend_spanning_null()
3583 !mas_slot_locked(r_mas, r_wr_mas->slots, r_mas->offset + 1)) { in mas_extend_spanning_null()
3585 r_wr_mas->type, r_mas->offset + 1); in mas_extend_spanning_null()
3586 r_mas->offset++; in mas_extend_spanning_null()
3616 unsigned char offset; in mtree_lookup_walk() local
3629 offset = 0; in mtree_lookup_walk()
3631 if (pivots[offset] >= mas->index) in mtree_lookup_walk()
3633 } while (++offset < end); in mtree_lookup_walk()
3636 next = mt_slot(mas->tree, slots, offset); in mtree_lookup_walk()
3754 mas->offset = l_mas.offset; in mas_wr_spanning_store()
3770 mas_mab_cp(&r_mas, r_mas.offset, r_mas.end, in mas_wr_spanning_store()
3819 memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset); in mas_wr_node_store()
3820 memcpy(dst_slots, wr_mas->slots, sizeof(void *) * mas->offset); in mas_wr_node_store()
3824 rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content); in mas_wr_node_store()
3825 dst_pivots[mas->offset++] = mas->index - 1; in mas_wr_node_store()
3829 if (mas->offset < node_pivots) in mas_wr_node_store()
3830 dst_pivots[mas->offset] = mas->last; in mas_wr_node_store()
3831 rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry); in mas_wr_node_store()
3840 dst_offset = mas->offset + 1; in mas_wr_node_store()
3874 unsigned char offset = mas->offset; in mas_wr_slot_store() local
3878 gap |= !mt_slot_locked(mas->tree, slots, offset); in mas_wr_slot_store()
3879 gap |= !mt_slot_locked(mas->tree, slots, offset + 1); in mas_wr_slot_store()
3881 if (wr_mas->offset_end - offset == 1) { in mas_wr_slot_store()
3884 rcu_assign_pointer(slots[offset], wr_mas->entry); in mas_wr_slot_store()
3885 wr_mas->pivots[offset] = mas->last; in mas_wr_slot_store()
3888 rcu_assign_pointer(slots[offset + 1], wr_mas->entry); in mas_wr_slot_store()
3889 wr_mas->pivots[offset] = mas->index - 1; in mas_wr_slot_store()
3890 mas->offset++; /* Keep mas accurate. */ in mas_wr_slot_store()
3897 gap |= !mt_slot_locked(mas->tree, slots, offset + 2); in mas_wr_slot_store()
3898 rcu_assign_pointer(slots[offset + 1], wr_mas->entry); in mas_wr_slot_store()
3899 wr_mas->pivots[offset] = mas->index - 1; in mas_wr_slot_store()
3900 wr_mas->pivots[offset + 1] = mas->last; in mas_wr_slot_store()
3901 mas->offset++; /* Keep mas accurate. */ in mas_wr_slot_store()
3943 if (mas->index == wr_mas->r_min && mas->offset && in mas_wr_extend_null()
3944 !wr_mas->slots[mas->offset - 1]) { in mas_wr_extend_null()
3945 mas->offset--; in mas_wr_extend_null()
3947 mas_safe_min(mas, wr_mas->pivots, mas->offset); in mas_wr_extend_null()
3948 wr_mas->r_max = wr_mas->pivots[mas->offset]; in mas_wr_extend_null()
3970 new_end -= wr_mas->offset_end - mas->offset; in mas_wr_new_end()
4007 mas->offset = new_end; in mas_wr_append()
4020 mas->offset = end + 1; in mas_wr_append()
4067 rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry); in mas_wr_store_entry()
4234 if (!mt_in_rcu(mas->tree) && (mas->offset == mas->end)) { in mas_wr_store_type()
4240 (wr_mas->offset_end - mas->offset == 1))) { in mas_wr_store_type()
4315 wr_mas.offset_end = mas->offset; in mas_insert()
4416 int offset, level; in mas_prev_node() local
4438 offset = mas->offset; in mas_prev_node()
4441 } while (!offset); in mas_prev_node()
4443 offset--; in mas_prev_node()
4448 mas->node = mas_slot(mas, slots, offset); in mas_prev_node()
4455 offset = ma_data_end(node, mt, pivots, max); in mas_prev_node()
4461 mas->node = mas_slot(mas, slots, offset); in mas_prev_node()
4466 if (likely(offset)) in mas_prev_node()
4467 mas->min = pivots[offset - 1] + 1; in mas_prev_node()
4469 mas->offset = mas_data_end(mas); in mas_prev_node()
4473 mas->end = mas->offset; in mas_prev_node()
4511 pivot = mas_safe_min(mas, pivots, mas->offset); in mas_prev_slot()
4521 if (likely(mas->offset)) { in mas_prev_slot()
4522 mas->offset--; in mas_prev_slot()
4524 mas->index = mas_safe_min(mas, pivots, mas->offset); in mas_prev_slot()
4541 mas->index = pivots[mas->offset - 1] + 1; in mas_prev_slot()
4545 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()
4684 if (likely(mas->offset < mas->end)) in mas_next_slot()
4685 pivot = pivots[mas->offset]; in mas_next_slot()
4698 if (likely(mas->offset < mas->end)) { in mas_next_slot()
4699 mas->index = pivots[mas->offset] + 1; in mas_next_slot()
4701 mas->offset++; in mas_next_slot()
4702 if (likely(mas->offset < mas->end)) in mas_next_slot()
4703 mas->last = pivots[mas->offset]; in mas_next_slot()
4720 mas->offset = 0; in mas_next_slot()
4729 entry = mt_slot(mas->tree, slots, mas->offset); in mas_next_slot()
4791 unsigned char offset; in mas_rev_awalk() local
4798 mas->offset = (unsigned char)(mas->index - mas->min); in mas_rev_awalk()
4805 offset = mas->offset; in mas_rev_awalk()
4806 min = mas_safe_min(mas, pivots, offset); in mas_rev_awalk()
4809 min = mas_safe_min(mas, pivots, --offset); in mas_rev_awalk()
4811 max = mas_safe_pivot(mas, pivots, offset, type); in mas_rev_awalk()
4815 gap = gaps[offset]; in mas_rev_awalk()
4816 else if (!mas_slot(mas, slots, offset)) in mas_rev_awalk()
4825 if (offset < 2) in mas_rev_awalk()
4828 offset -= 2; in mas_rev_awalk()
4829 max = pivots[offset]; in mas_rev_awalk()
4830 min = mas_safe_min(mas, pivots, offset); in mas_rev_awalk()
4835 if (!offset) in mas_rev_awalk()
4838 offset--; in mas_rev_awalk()
4840 min = mas_safe_min(mas, pivots, offset); in mas_rev_awalk()
4847 mas->offset = offset; in mas_rev_awalk()
4854 mas->node = mas_slot(mas, slots, offset); in mas_rev_awalk()
4857 mas->offset = mas_data_end(mas); in mas_rev_awalk()
4873 unsigned char offset, data_end; in mas_anode_descend() local
4880 mas->offset = (unsigned char)(mas->index - mas->min); in mas_anode_descend()
4888 offset = mas->offset; in mas_anode_descend()
4889 min = mas_safe_min(mas, pivots, offset); in mas_anode_descend()
4891 for (; offset <= data_end; offset++) { in mas_anode_descend()
4892 pivot = mas_safe_pivot(mas, pivots, offset, type); in mas_anode_descend()
4899 gap = gaps[offset]; in mas_anode_descend()
4900 else if (!mas_slot(mas, slots, offset)) in mas_anode_descend()
4911 mas->node = mas_slot(mas, slots, offset); in mas_anode_descend()
4914 offset = 0; in mas_anode_descend()
4929 mas->offset = offset; in mas_anode_descend()
4977 slot = mas->offset; in mas_rewind_node()
4982 slot = mas->offset; in mas_rewind_node()
4986 mas->offset = --slot; in mas_rewind_node()
5003 if (mas->offset >= mas_data_end(mas)) { in mas_skip_node()
5010 } while (mas->offset >= mas_data_end(mas)); in mas_skip_node()
5012 mas->offset++; in mas_skip_node()
5087 unsigned char offset; in mas_empty_area() local
5100 else if (mas->offset >= 2) in mas_empty_area()
5101 mas->offset -= 2; in mas_empty_area()
5117 offset = mas->offset; in mas_empty_area()
5118 if (unlikely(offset == MAPLE_NODE_SLOTS)) in mas_empty_area()
5124 min = mas_safe_min(mas, pivots, offset); in mas_empty_area()
5154 else if ((mas->offset < 2) && (!mas_rewind_node(mas))) in mas_empty_area_rev()
5159 else if (mas->offset >= 2) in mas_empty_area_rev()
5160 mas->offset -= 2; in mas_empty_area_rev()
5162 mas->offset = mas_data_end(mas); in mas_empty_area_rev()
5181 if (unlikely(mas->offset == MAPLE_NODE_SLOTS)) in mas_empty_area_rev()
5211 int offset; in mte_dead_leaves() local
5213 for (offset = 0; offset < mt_slot_count(enode); offset++) { in mte_dead_leaves()
5214 entry = mt_slot(mt, slots, offset); in mte_dead_leaves()
5223 rcu_assign_pointer(slots[offset], node); in mte_dead_leaves()
5226 return offset; in mte_dead_leaves()
5236 static void __rcu **mte_dead_walk(struct maple_enode **enode, unsigned char offset) in mte_dead_walk() argument
5246 next = rcu_dereference_protected(slots[offset], in mte_dead_walk()
5248 offset = 0; in mte_dead_walk()
5265 unsigned char offset; in mt_free_walk() local
5279 offset = node->parent_slot + 1; in mt_free_walk()
5286 if ((offset < mt_slots[type]) && in mt_free_walk()
5287 rcu_dereference_protected(slots[offset], in mt_free_walk()
5289 slots = mte_dead_walk(&enode, offset); in mt_free_walk()
5291 } while ((node != start) || (node->slot_len < offset)); in mt_free_walk()
5301 struct maple_tree *mt, struct maple_enode *prev, unsigned char offset) in mte_destroy_descend() argument
5321 node->parent_slot = offset; in mte_destroy_descend()
5322 offset = next_offset; in mte_destroy_descend()
5348 unsigned char offset; in mt_destroy_walk() local
5354 offset = node->parent_slot + 1; in mt_destroy_walk()
5361 if (offset >= mt_slots[type]) in mt_destroy_walk()
5364 tmp = mt_slot_locked(mt, slots, offset); in mt_destroy_walk()
5368 slots = mte_destroy_descend(&enode, mt, parent, offset); in mt_destroy_walk()
5516 wr_mas.content = mas_slot_locked(mas, wr_mas.slots, mas->offset); in mas_store_prealloc()
6621 if (mas->offset) { in mas_dup_free()
6622 mas->offset--; in mas_dup_free()
6625 mas->offset = mas_data_end(mas); in mas_dup_free()
6770 } while (mas->offset == mas_data_end(mas)); in mas_dup_build()
6773 mas->offset++; in mas_dup_build()
6774 new_mas->offset++; in mas_dup_build()
6780 mas->offset = 0; in mas_dup_build()
6781 new_mas->offset = 0; in mas_dup_build()
7067 unsigned char offset) in mas_get_slot() argument
7070 offset); in mas_get_slot()
7312 unsigned char p_slot, offset; in mas_validate_gaps() local
7362 offset = ma_meta_gap(node); in mas_validate_gaps()
7363 if (offset > i) { in mas_validate_gaps()
7364 pr_err("gap offset %p[%u] is invalid\n", node, offset); in mas_validate_gaps()
7368 if (gaps[offset] != max_gap) { in mas_validate_gaps()
7370 node, offset, max_gap); in mas_validate_gaps()
7546 unsigned char offset = 0; in mt_validate_nulls() local
7559 entry = mas_slot(&mas, slots, offset); in mt_validate_nulls()
7562 mas_mn(&mas), offset); in mt_validate_nulls()
7566 if (offset == mas_data_end(&mas)) { in mt_validate_nulls()
7570 offset = 0; in mt_validate_nulls()
7574 offset++; in mt_validate_nulls()
7681 pr_err("[%u/%u] index=%lx last=%lx\n", mas->offset, mas->end, in mas_dump()