Lines Matching full:mast
2232 * @mast: The maple subtree state
2234 static inline void mast_rebalance_next(struct maple_subtree_state *mast) in mast_rebalance_next() argument
2236 unsigned char b_end = mast->bn->b_end; in mast_rebalance_next()
2238 mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node), in mast_rebalance_next()
2239 mast->bn, b_end); in mast_rebalance_next()
2240 mast->orig_r->last = mast->orig_r->max; in mast_rebalance_next()
2245 * @mast: The maple subtree state
2247 static inline void mast_rebalance_prev(struct maple_subtree_state *mast) in mast_rebalance_prev() argument
2249 unsigned char end = mas_data_end(mast->orig_l) + 1; in mast_rebalance_prev()
2250 unsigned char b_end = mast->bn->b_end; in mast_rebalance_prev()
2252 mab_shift_right(mast->bn, end); in mast_rebalance_prev()
2253 mas_mab_cp(mast->orig_l, 0, end - 1, mast->bn, 0); in mast_rebalance_prev()
2254 mast->l->min = mast->orig_l->min; in mast_rebalance_prev()
2255 mast->orig_l->index = mast->orig_l->min; in mast_rebalance_prev()
2256 mast->bn->b_end = end + b_end; in mast_rebalance_prev()
2257 mast->l->offset += end; in mast_rebalance_prev()
2264 * Data is copied into the @mast->bn.
2265 * @mast: The maple_subtree_state.
2268 bool mast_spanning_rebalance(struct maple_subtree_state *mast) in mast_spanning_rebalance() argument
2270 struct ma_state r_tmp = *mast->orig_r; in mast_spanning_rebalance()
2271 struct ma_state l_tmp = *mast->orig_l; in mast_spanning_rebalance()
2275 mas_ascend(mast->orig_r); in mast_spanning_rebalance()
2276 mas_ascend(mast->orig_l); in mast_spanning_rebalance()
2278 if (mast->orig_r->offset < mas_data_end(mast->orig_r)) { in mast_spanning_rebalance()
2279 mast->orig_r->offset++; in mast_spanning_rebalance()
2281 mas_descend(mast->orig_r); in mast_spanning_rebalance()
2282 mast->orig_r->offset = 0; in mast_spanning_rebalance()
2285 mast_rebalance_next(mast); in mast_spanning_rebalance()
2286 *mast->orig_l = l_tmp; in mast_spanning_rebalance()
2288 } else if (mast->orig_l->offset != 0) { in mast_spanning_rebalance()
2289 mast->orig_l->offset--; in mast_spanning_rebalance()
2291 mas_descend(mast->orig_l); in mast_spanning_rebalance()
2292 mast->orig_l->offset = in mast_spanning_rebalance()
2293 mas_data_end(mast->orig_l); in mast_spanning_rebalance()
2296 mast_rebalance_prev(mast); in mast_spanning_rebalance()
2297 *mast->orig_r = r_tmp; in mast_spanning_rebalance()
2300 } while (!mte_is_root(mast->orig_r->node)); in mast_spanning_rebalance()
2302 *mast->orig_r = r_tmp; in mast_spanning_rebalance()
2303 *mast->orig_l = l_tmp; in mast_spanning_rebalance()
2309 * @mast: the maple subtree state.
2312 * data already in the new tree (@mast->l and @mast->r).
2314 static inline void mast_ascend(struct maple_subtree_state *mast) in mast_ascend() argument
2316 MA_WR_STATE(wr_mas, mast->orig_r, NULL); in mast_ascend()
2317 mas_ascend(mast->orig_l); in mast_ascend()
2318 mas_ascend(mast->orig_r); in mast_ascend()
2320 mast->orig_r->offset = 0; in mast_ascend()
2321 mast->orig_r->index = mast->r->max; in mast_ascend()
2323 if (mast->orig_r->last < mast->orig_r->index) in mast_ascend()
2324 mast->orig_r->last = mast->orig_r->index; in mast_ascend()
2326 wr_mas.type = mte_node_type(mast->orig_r->node); in mast_ascend()
2329 mast->orig_l->offset = 0; in mast_ascend()
2330 mast->orig_l->index = mast->l->min; in mast_ascend()
2331 wr_mas.mas = mast->orig_l; in mast_ascend()
2332 wr_mas.type = mte_node_type(mast->orig_l->node); in mast_ascend()
2335 mast->bn->type = wr_mas.type; in mast_ascend()
2468 * is taken from @mast->l.
2469 * @mast: the maple subtree state
2474 static inline void mast_set_split_parents(struct maple_subtree_state *mast, in mast_set_split_parents() argument
2485 if (mas_is_none(mast->l)) in mast_set_split_parents()
2491 slot = mast->l->offset; in mast_set_split_parents()
2494 mas_set_split_parent(mast->l, l, r, &slot, split); in mast_set_split_parents()
2497 mas_set_split_parent(mast->m, l, r, &slot, split); in mast_set_split_parents()
2500 mas_set_split_parent(mast->r, l, r, &slot, split); in mast_set_split_parents()
2655 * @mast: The maple subtree state
2662 static inline void mast_cp_to_nodes(struct maple_subtree_state *mast, in mast_cp_to_nodes() argument
2668 mas_node_or_none(mast->l, left); in mast_cp_to_nodes()
2669 mas_node_or_none(mast->m, middle); in mast_cp_to_nodes()
2670 mas_node_or_none(mast->r, right); in mast_cp_to_nodes()
2672 mast->l->min = mast->orig_l->min; in mast_cp_to_nodes()
2673 if (split == mast->bn->b_end) { in mast_cp_to_nodes()
2674 mast->l->max = mast->orig_r->max; in mast_cp_to_nodes()
2678 mab_mas_cp(mast->bn, 0, split, mast->l, new_lmax); in mast_cp_to_nodes()
2681 mab_mas_cp(mast->bn, 1 + split, mid_split, mast->m, true); in mast_cp_to_nodes()
2682 mast->m->min = mast->bn->pivot[split] + 1; in mast_cp_to_nodes()
2686 mast->r->max = mast->orig_r->max; in mast_cp_to_nodes()
2688 mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r, false); in mast_cp_to_nodes()
2689 mast->r->min = mast->bn->pivot[split] + 1; in mast_cp_to_nodes()
2696 * @mast: The maple subtree state
2698 static inline void mast_combine_cp_left(struct maple_subtree_state *mast) in mast_combine_cp_left() argument
2700 unsigned char l_slot = mast->orig_l->offset; in mast_combine_cp_left()
2705 mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0); in mast_combine_cp_left()
2711 * @mast: The maple subtree state
2713 static inline void mast_combine_cp_right(struct maple_subtree_state *mast) in mast_combine_cp_right() argument
2715 if (mast->bn->pivot[mast->bn->b_end - 1] >= mast->orig_r->max) in mast_combine_cp_right()
2718 mas_mab_cp(mast->orig_r, mast->orig_r->offset + 1, in mast_combine_cp_right()
2719 mt_slot_count(mast->orig_r->node), mast->bn, in mast_combine_cp_right()
2720 mast->bn->b_end); in mast_combine_cp_right()
2721 mast->orig_r->last = mast->orig_r->max; in mast_combine_cp_right()
2727 * @mast: the maple subtree state
2729 static inline bool mast_sufficient(struct maple_subtree_state *mast) in mast_sufficient() argument
2731 if (mast->bn->b_end > mt_min_slot_count(mast->orig_l->node)) in mast_sufficient()
2740 * @mast: The maple subtree state
2742 static inline bool mast_overflow(struct maple_subtree_state *mast) in mast_overflow() argument
2744 if (mast->bn->b_end >= mt_slot_count(mast->orig_l->node)) in mast_overflow()
2813 * @mast: The maple_subtree_state, keeps track of 4 maple states.
2827 struct maple_subtree_state *mast, unsigned char count) in mas_spanning_rebalance() argument
2842 mast->l = &l_mas; in mas_spanning_rebalance()
2843 mast->m = &m_mas; in mas_spanning_rebalance()
2844 mast->r = &r_mas; in mas_spanning_rebalance()
2848 if (((mast->orig_l->min != 0) || (mast->orig_r->max != ULONG_MAX)) && in mas_spanning_rebalance()
2849 unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type])) in mas_spanning_rebalance()
2850 mast_spanning_rebalance(mast); in mas_spanning_rebalance()
2866 mast->bn->b_end--; in mas_spanning_rebalance()
2867 mast->bn->type = mte_node_type(mast->orig_l->node); in mas_spanning_rebalance()
2868 split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle, in mas_spanning_rebalance()
2870 mast_set_split_parents(mast, left, middle, right, split, in mas_spanning_rebalance()
2872 mast_cp_to_nodes(mast, left, middle, right, split, mid_split); in mas_spanning_rebalance()
2875 * Copy data from next level in the tree to mast->bn from next in mas_spanning_rebalance()
2878 memset(mast->bn, 0, sizeof(struct maple_big_node)); in mas_spanning_rebalance()
2879 mast->bn->type = mte_node_type(left); in mas_spanning_rebalance()
2883 if (mas_is_root_limits(mast->l)) in mas_spanning_rebalance()
2886 mast_ascend(mast); in mas_spanning_rebalance()
2887 mast_combine_cp_left(mast); in mas_spanning_rebalance()
2888 l_mas.offset = mast->bn->b_end; in mas_spanning_rebalance()
2889 mab_set_b_end(mast->bn, &l_mas, left); in mas_spanning_rebalance()
2890 mab_set_b_end(mast->bn, &m_mas, middle); in mas_spanning_rebalance()
2891 mab_set_b_end(mast->bn, &r_mas, right); in mas_spanning_rebalance()
2894 mast_combine_cp_right(mast); in mas_spanning_rebalance()
2895 mast->orig_l->last = mast->orig_l->max; in mas_spanning_rebalance()
2897 if (mast_sufficient(mast)) in mas_spanning_rebalance()
2900 if (mast_overflow(mast)) in mas_spanning_rebalance()
2903 /* May be a new root stored in mast->bn */ in mas_spanning_rebalance()
2904 if (mas_is_root_limits(mast->orig_l)) in mas_spanning_rebalance()
2907 mast_spanning_rebalance(mast); in mas_spanning_rebalance()
2915 mte_node_type(mast->orig_l->node)); in mas_spanning_rebalance()
2917 mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true); in mas_spanning_rebalance()
2925 if (mas_is_root_limits(mast->l)) { in mas_spanning_rebalance()
2927 mas_mn(mast->l)->parent = ma_parent_ptr(mas_tree_parent(mas)); in mas_spanning_rebalance()
2928 while (!mte_is_root(mast->orig_l->node)) in mas_spanning_rebalance()
2929 mast_ascend(mast); in mas_spanning_rebalance()
2931 mas_mn(&l_mas)->parent = mas_mn(mast->orig_l)->parent; in mas_spanning_rebalance()
2934 old_enode = mast->orig_l->node; in mas_spanning_rebalance()
2957 struct maple_subtree_state mast; in mas_rebalance() local
2975 mast.orig_l = &l_mas; in mas_rebalance()
2976 mast.orig_r = &r_mas; in mas_rebalance()
2977 mast.bn = b_node; in mas_rebalance()
2978 mast.bn->type = mte_node_type(mas->node); in mas_rebalance()
2995 return mas_spanning_rebalance(mas, &mast, empty_count); in mas_rebalance()
3119 * @mast: the maple subtree state
3123 static inline void mas_split_final_node(struct maple_subtree_state *mast, in mas_split_final_node() argument
3130 mast->bn->type = maple_arange_64; in mas_split_final_node()
3132 mast->bn->type = maple_range_64; in mas_split_final_node()
3139 ancestor = mas_new_ma_node(mas, mast->bn); in mas_split_final_node()
3140 mas_set_parent(mas, mast->l->node, ancestor, mast->l->offset); in mas_split_final_node()
3141 mas_set_parent(mas, mast->r->node, ancestor, mast->r->offset); in mas_split_final_node()
3144 mast->l->node = ancestor; in mas_split_final_node()
3145 mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, mast->l, true); in mas_split_final_node()
3146 mas->offset = mast->bn->b_end - 1; in mas_split_final_node()
3151 * @mast: The maple subtree state
3155 static inline void mast_fill_bnode(struct maple_subtree_state *mast, in mast_fill_bnode() argument
3162 memset(mast->bn, 0, sizeof(struct maple_big_node)); in mast_fill_bnode()
3171 if (cp && mast->l->offset) in mast_fill_bnode()
3172 mas_mab_cp(mas, 0, mast->l->offset - 1, mast->bn, 0); in mast_fill_bnode()
3174 split = mast->bn->b_end; in mast_fill_bnode()
3175 mab_set_b_end(mast->bn, mast->l, mast->l->node); in mast_fill_bnode()
3176 mast->r->offset = mast->bn->b_end; in mast_fill_bnode()
3177 mab_set_b_end(mast->bn, mast->r, mast->r->node); in mast_fill_bnode()
3178 if (mast->bn->pivot[mast->bn->b_end - 1] == mas->max) in mast_fill_bnode()
3183 mast->bn, mast->bn->b_end); in mast_fill_bnode()
3185 mast->bn->b_end--; in mast_fill_bnode()
3186 mast->bn->type = mte_node_type(mas->node); in mast_fill_bnode()
3192 * @mast: The maple subtree state
3196 static inline void mast_split_data(struct maple_subtree_state *mast, in mast_split_data() argument
3201 mab_mas_cp(mast->bn, 0, split, mast->l, true); in mast_split_data()
3202 mte_set_pivot(mast->r->node, 0, mast->r->max); in mast_split_data()
3203 mab_mas_cp(mast->bn, split + 1, mast->bn->b_end, mast->r, false); in mast_split_data()
3204 mast->l->offset = mte_parent_slot(mas->node); in mast_split_data()
3205 mast->l->max = mast->bn->pivot[split]; in mast_split_data()
3206 mast->r->min = mast->l->max + 1; in mast_split_data()
3210 p_slot = mast->orig_l->offset; in mast_split_data()
3211 mas_set_split_parent(mast->orig_l, mast->l->node, mast->r->node, in mast_split_data()
3213 mas_set_split_parent(mast->orig_r, mast->l->node, mast->r->node, in mast_split_data()
3222 * @mast: The maple subtree state
3230 struct maple_subtree_state *mast, bool left) in mas_push_data() argument
3232 unsigned char slot_total = mast->bn->b_end; in mas_push_data()
3237 tmp_mas.depth = mast->l->depth; in mas_push_data()
3248 if (ma_is_leaf(mast->bn->type)) in mas_push_data()
3257 /* Get the data; Fill mast->bn */ in mas_push_data()
3258 mast->bn->b_end++; in mas_push_data()
3260 mab_shift_right(mast->bn, end + 1); in mas_push_data()
3261 mas_mab_cp(&tmp_mas, 0, end, mast->bn, 0); in mas_push_data()
3262 mast->bn->b_end = slot_total + 1; in mas_push_data()
3264 mas_mab_cp(&tmp_mas, 0, end, mast->bn, mast->bn->b_end); in mas_push_data()
3267 /* Configure mast for splitting of mast->bn */ in mas_push_data()
3268 split = mt_slots[mast->bn->type] - 2; in mas_push_data()
3272 /* Start using mast->l for the left side. */ in mas_push_data()
3273 tmp_mas.node = mast->l->node; in mas_push_data()
3274 *mast->l = tmp_mas; in mas_push_data()
3276 tmp_mas.node = mast->r->node; in mas_push_data()
3277 *mast->r = tmp_mas; in mas_push_data()
3280 split = mab_no_null_split(mast->bn, split, mt_slots[mast->bn->type]); in mas_push_data()
3283 mast->orig_l->offset += end + 1; in mas_push_data()
3285 mast_split_data(mast, mas, split); in mas_push_data()
3286 mast_fill_bnode(mast, mas, 2); in mas_push_data()
3287 mas_split_final_node(mast, mas, height + 1); in mas_push_data()
3298 struct maple_subtree_state mast; in mas_split() local
3328 mast.l = &l_mas; in mas_split()
3329 mast.r = &r_mas; in mas_split()
3330 mast.orig_l = &prev_l_mas; in mas_split()
3331 mast.orig_r = &prev_r_mas; in mas_split()
3332 mast.bn = b_node; in mas_split()
3336 mas_split_final_node(&mast, mas, height); in mas_split()
3351 if (mas_push_data(mas, height, &mast, true)) in mas_split()
3354 if (mas_push_data(mas, height, &mast, false)) in mas_split()
3358 mast_split_data(&mast, mas, split); in mas_split()
3363 mast.r->max = mas->max; in mas_split()
3364 mast_fill_bnode(&mast, mas, 1); in mas_split()
3365 prev_l_mas = *mast.l; in mas_split()
3366 prev_r_mas = *mast.r; in mas_split()
3710 struct maple_subtree_state mast; in mas_wr_spanning_store() local
3788 mast.bn = &b_node; in mas_wr_spanning_store()
3789 mast.orig_l = &l_mas; in mas_wr_spanning_store()
3790 mast.orig_r = &r_mas; in mas_wr_spanning_store()
3792 return mas_spanning_rebalance(mas, &mast, height + 1); in mas_wr_spanning_store()