Lines Matching full:mast
2253 * @mast: The maple subtree state
2256 static inline void mast_rebalance_next(struct maple_subtree_state *mast) in mast_rebalance_next() argument
2258 unsigned char b_end = mast->bn->b_end; in mast_rebalance_next()
2260 mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node), in mast_rebalance_next()
2261 mast->bn, b_end); in mast_rebalance_next()
2262 mast->orig_r->last = mast->orig_r->max; in mast_rebalance_next()
2267 * @mast: The maple subtree state
2270 static inline void mast_rebalance_prev(struct maple_subtree_state *mast) in mast_rebalance_prev() argument
2272 unsigned char end = mas_data_end(mast->orig_l) + 1; in mast_rebalance_prev()
2273 unsigned char b_end = mast->bn->b_end; in mast_rebalance_prev()
2275 mab_shift_right(mast->bn, end); in mast_rebalance_prev()
2276 mas_mab_cp(mast->orig_l, 0, end - 1, mast->bn, 0); in mast_rebalance_prev()
2277 mast->l->min = mast->orig_l->min; in mast_rebalance_prev()
2278 mast->orig_l->index = mast->orig_l->min; in mast_rebalance_prev()
2279 mast->bn->b_end = end + b_end; in mast_rebalance_prev()
2280 mast->l->offset += end; in mast_rebalance_prev()
2287 * Data is copied into the @mast->bn.
2288 * @mast: The maple_subtree_state.
2291 bool mast_spanning_rebalance(struct maple_subtree_state *mast) in mast_spanning_rebalance() argument
2293 struct ma_state r_tmp = *mast->orig_r; in mast_spanning_rebalance()
2294 struct ma_state l_tmp = *mast->orig_l; in mast_spanning_rebalance()
2297 r_tmp = *mast->orig_r; in mast_spanning_rebalance()
2298 l_tmp = *mast->orig_l; in mast_spanning_rebalance()
2300 mas_ascend(mast->orig_r); in mast_spanning_rebalance()
2301 mas_ascend(mast->orig_l); in mast_spanning_rebalance()
2303 if (mast->orig_r->offset < mas_data_end(mast->orig_r)) { in mast_spanning_rebalance()
2304 mast->orig_r->offset++; in mast_spanning_rebalance()
2306 mas_descend(mast->orig_r); in mast_spanning_rebalance()
2307 mast->orig_r->offset = 0; in mast_spanning_rebalance()
2310 mast_rebalance_next(mast); in mast_spanning_rebalance()
2311 *mast->orig_l = l_tmp; in mast_spanning_rebalance()
2313 } else if (mast->orig_l->offset != 0) { in mast_spanning_rebalance()
2314 mast->orig_l->offset--; in mast_spanning_rebalance()
2316 mas_descend(mast->orig_l); in mast_spanning_rebalance()
2317 mast->orig_l->offset = in mast_spanning_rebalance()
2318 mas_data_end(mast->orig_l); in mast_spanning_rebalance()
2321 mast_rebalance_prev(mast); in mast_spanning_rebalance()
2322 *mast->orig_r = r_tmp; in mast_spanning_rebalance()
2325 } while (!mte_is_root(mast->orig_r->node)); in mast_spanning_rebalance()
2327 *mast->orig_r = r_tmp; in mast_spanning_rebalance()
2328 *mast->orig_l = l_tmp; in mast_spanning_rebalance()
2334 * @mast: the maple subtree state.
2337 * data already in the new tree (@mast->l and @mast->r).
2339 static inline void mast_ascend(struct maple_subtree_state *mast) in mast_ascend() argument
2341 MA_WR_STATE(wr_mas, mast->orig_r, NULL); in mast_ascend()
2342 mas_ascend(mast->orig_l); in mast_ascend()
2343 mas_ascend(mast->orig_r); in mast_ascend()
2345 mast->orig_r->offset = 0; in mast_ascend()
2346 mast->orig_r->index = mast->r->max; in mast_ascend()
2348 if (mast->orig_r->last < mast->orig_r->index) in mast_ascend()
2349 mast->orig_r->last = mast->orig_r->index; in mast_ascend()
2351 wr_mas.type = mte_node_type(mast->orig_r->node); in mast_ascend()
2354 mast->orig_l->offset = 0; in mast_ascend()
2355 mast->orig_l->index = mast->l->min; in mast_ascend()
2356 wr_mas.mas = mast->orig_l; in mast_ascend()
2357 wr_mas.type = mte_node_type(mast->orig_l->node); in mast_ascend()
2360 mast->bn->type = wr_mas.type; in mast_ascend()
2493 * is taken from @mast->l.
2494 * @mast - the maple subtree state
2499 static inline void mast_set_split_parents(struct maple_subtree_state *mast, in mast_set_split_parents() argument
2510 if (mas_is_none(mast->l)) in mast_set_split_parents()
2516 slot = mast->l->offset; in mast_set_split_parents()
2519 mas_set_split_parent(mast->l, l, r, &slot, split); in mast_set_split_parents()
2522 mas_set_split_parent(mast->m, l, r, &slot, split); in mast_set_split_parents()
2525 mas_set_split_parent(mast->r, l, r, &slot, split); in mast_set_split_parents()
2679 * @mast: The maple subtree state
2686 static inline void mast_cp_to_nodes(struct maple_subtree_state *mast, in mast_cp_to_nodes() argument
2692 mast->l->node = mte_node_or_none(left); in mast_cp_to_nodes()
2693 mast->m->node = mte_node_or_none(middle); in mast_cp_to_nodes()
2694 mast->r->node = mte_node_or_none(right); in mast_cp_to_nodes()
2696 mast->l->min = mast->orig_l->min; in mast_cp_to_nodes()
2697 if (split == mast->bn->b_end) { in mast_cp_to_nodes()
2698 mast->l->max = mast->orig_r->max; in mast_cp_to_nodes()
2702 mab_mas_cp(mast->bn, 0, split, mast->l, new_lmax); in mast_cp_to_nodes()
2705 mab_mas_cp(mast->bn, 1 + split, mid_split, mast->m, true); in mast_cp_to_nodes()
2706 mast->m->min = mast->bn->pivot[split] + 1; in mast_cp_to_nodes()
2710 mast->r->max = mast->orig_r->max; in mast_cp_to_nodes()
2712 mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r, false); in mast_cp_to_nodes()
2713 mast->r->min = mast->bn->pivot[split] + 1; in mast_cp_to_nodes()
2720 * @mast: The maple subtree state
2722 static inline void mast_combine_cp_left(struct maple_subtree_state *mast) in mast_combine_cp_left() argument
2724 unsigned char l_slot = mast->orig_l->offset; in mast_combine_cp_left()
2729 mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0); in mast_combine_cp_left()
2735 * @mast: The maple subtree state
2737 static inline void mast_combine_cp_right(struct maple_subtree_state *mast) in mast_combine_cp_right() argument
2739 if (mast->bn->pivot[mast->bn->b_end - 1] >= mast->orig_r->max) in mast_combine_cp_right()
2742 mas_mab_cp(mast->orig_r, mast->orig_r->offset + 1, in mast_combine_cp_right()
2743 mt_slot_count(mast->orig_r->node), mast->bn, in mast_combine_cp_right()
2744 mast->bn->b_end); in mast_combine_cp_right()
2745 mast->orig_r->last = mast->orig_r->max; in mast_combine_cp_right()
2751 * @mast: the maple subtree state
2753 static inline bool mast_sufficient(struct maple_subtree_state *mast) in mast_sufficient() argument
2755 if (mast->bn->b_end > mt_min_slot_count(mast->orig_l->node)) in mast_sufficient()
2764 * @mast: The maple subtree state
2766 static inline bool mast_overflow(struct maple_subtree_state *mast) in mast_overflow() argument
2768 if (mast->bn->b_end >= mt_slot_count(mast->orig_l->node)) in mast_overflow()
2839 * @mast: The maple_subtree_state, keeps track of 4 maple states.
2855 struct maple_subtree_state *mast, unsigned char count) in mas_spanning_rebalance() argument
2870 mast->l = &l_mas; in mas_spanning_rebalance()
2871 mast->m = &m_mas; in mas_spanning_rebalance()
2872 mast->r = &r_mas; in mas_spanning_rebalance()
2876 if (((mast->orig_l->min != 0) || (mast->orig_r->max != ULONG_MAX)) && in mas_spanning_rebalance()
2877 unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type])) in mas_spanning_rebalance()
2878 mast_spanning_rebalance(mast); in mas_spanning_rebalance()
2894 mast->bn->b_end--; in mas_spanning_rebalance()
2895 mast->bn->type = mte_node_type(mast->orig_l->node); in mas_spanning_rebalance()
2896 split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle, in mas_spanning_rebalance()
2898 mast_set_split_parents(mast, left, middle, right, split, in mas_spanning_rebalance()
2900 mast_cp_to_nodes(mast, left, middle, right, split, mid_split); in mas_spanning_rebalance()
2903 * Copy data from next level in the tree to mast->bn from next in mas_spanning_rebalance()
2906 memset(mast->bn, 0, sizeof(struct maple_big_node)); in mas_spanning_rebalance()
2907 mast->bn->type = mte_node_type(left); in mas_spanning_rebalance()
2911 if (mas_is_root_limits(mast->l)) in mas_spanning_rebalance()
2914 mast_ascend(mast); in mas_spanning_rebalance()
2915 mast_combine_cp_left(mast); in mas_spanning_rebalance()
2916 l_mas.offset = mast->bn->b_end; in mas_spanning_rebalance()
2917 mab_set_b_end(mast->bn, &l_mas, left); in mas_spanning_rebalance()
2918 mab_set_b_end(mast->bn, &m_mas, middle); in mas_spanning_rebalance()
2919 mab_set_b_end(mast->bn, &r_mas, right); in mas_spanning_rebalance()
2922 mast_combine_cp_right(mast); in mas_spanning_rebalance()
2923 mast->orig_l->last = mast->orig_l->max; in mas_spanning_rebalance()
2925 if (mast_sufficient(mast)) in mas_spanning_rebalance()
2928 if (mast_overflow(mast)) in mas_spanning_rebalance()
2931 /* May be a new root stored in mast->bn */ in mas_spanning_rebalance()
2932 if (mas_is_root_limits(mast->orig_l)) in mas_spanning_rebalance()
2935 mast_spanning_rebalance(mast); in mas_spanning_rebalance()
2943 mte_node_type(mast->orig_l->node)); in mas_spanning_rebalance()
2945 mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true); in mas_spanning_rebalance()
2953 if (mas_is_root_limits(mast->l)) { in mas_spanning_rebalance()
2955 mas_mn(mast->l)->parent = ma_parent_ptr(mas_tree_parent(mas)); in mas_spanning_rebalance()
2956 while (!mte_is_root(mast->orig_l->node)) in mas_spanning_rebalance()
2957 mast_ascend(mast); in mas_spanning_rebalance()
2959 mas_mn(&l_mas)->parent = mas_mn(mast->orig_l)->parent; in mas_spanning_rebalance()
2962 old_enode = mast->orig_l->node; in mas_spanning_rebalance()
2970 return mast->bn->b_end; in mas_spanning_rebalance()
2987 struct maple_subtree_state mast; in mas_rebalance() local
3008 mast.orig_l = &l_mas; in mas_rebalance()
3009 mast.orig_r = &r_mas; in mas_rebalance()
3010 mast.bn = b_node; in mas_rebalance()
3011 mast.bn->type = mte_node_type(mas->node); in mas_rebalance()
3028 return mas_spanning_rebalance(mas, &mast, empty_count); in mas_rebalance()
3157 * @mast: the maple subtree state
3161 static inline bool mas_split_final_node(struct maple_subtree_state *mast, in mas_split_final_node() argument
3168 mast->bn->type = maple_arange_64; in mas_split_final_node()
3170 mast->bn->type = maple_range_64; in mas_split_final_node()
3177 ancestor = mas_new_ma_node(mas, mast->bn); in mas_split_final_node()
3178 mas_set_parent(mas, mast->l->node, ancestor, mast->l->offset); in mas_split_final_node()
3179 mas_set_parent(mas, mast->r->node, ancestor, mast->r->offset); in mas_split_final_node()
3182 mast->l->node = ancestor; in mas_split_final_node()
3183 mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, mast->l, true); in mas_split_final_node()
3184 mas->offset = mast->bn->b_end - 1; in mas_split_final_node()
3190 * @mast: The maple subtree state
3194 static inline void mast_fill_bnode(struct maple_subtree_state *mast, in mast_fill_bnode() argument
3201 memset(mast->bn->gap, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->gap)); in mast_fill_bnode()
3202 memset(mast->bn->slot, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->slot)); in mast_fill_bnode()
3203 memset(mast->bn->pivot, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->pivot)); in mast_fill_bnode()
3204 mast->bn->b_end = 0; in mast_fill_bnode()
3213 if (cp && mast->l->offset) in mast_fill_bnode()
3214 mas_mab_cp(mas, 0, mast->l->offset - 1, mast->bn, 0); in mast_fill_bnode()
3216 split = mast->bn->b_end; in mast_fill_bnode()
3217 mab_set_b_end(mast->bn, mast->l, mast->l->node); in mast_fill_bnode()
3218 mast->r->offset = mast->bn->b_end; in mast_fill_bnode()
3219 mab_set_b_end(mast->bn, mast->r, mast->r->node); in mast_fill_bnode()
3220 if (mast->bn->pivot[mast->bn->b_end - 1] == mas->max) in mast_fill_bnode()
3225 mast->bn, mast->bn->b_end); in mast_fill_bnode()
3227 mast->bn->b_end--; in mast_fill_bnode()
3228 mast->bn->type = mte_node_type(mas->node); in mast_fill_bnode()
3234 * @mast: The maple subtree state
3238 static inline void mast_split_data(struct maple_subtree_state *mast, in mast_split_data() argument
3243 mab_mas_cp(mast->bn, 0, split, mast->l, true); in mast_split_data()
3244 mte_set_pivot(mast->r->node, 0, mast->r->max); in mast_split_data()
3245 mab_mas_cp(mast->bn, split + 1, mast->bn->b_end, mast->r, false); in mast_split_data()
3246 mast->l->offset = mte_parent_slot(mas->node); in mast_split_data()
3247 mast->l->max = mast->bn->pivot[split]; in mast_split_data()
3248 mast->r->min = mast->l->max + 1; in mast_split_data()
3252 p_slot = mast->orig_l->offset; in mast_split_data()
3253 mas_set_split_parent(mast->orig_l, mast->l->node, mast->r->node, in mast_split_data()
3255 mas_set_split_parent(mast->orig_r, mast->l->node, mast->r->node, in mast_split_data()
3264 * @mast: The maple subtree state
3272 struct maple_subtree_state *mast, bool left) in mas_push_data() argument
3274 unsigned char slot_total = mast->bn->b_end; in mas_push_data()
3279 tmp_mas.depth = mast->l->depth; in mas_push_data()
3290 if (ma_is_leaf(mast->bn->type)) in mas_push_data()
3299 /* Get the data; Fill mast->bn */ in mas_push_data()
3300 mast->bn->b_end++; in mas_push_data()
3302 mab_shift_right(mast->bn, end + 1); in mas_push_data()
3303 mas_mab_cp(&tmp_mas, 0, end, mast->bn, 0); in mas_push_data()
3304 mast->bn->b_end = slot_total + 1; in mas_push_data()
3306 mas_mab_cp(&tmp_mas, 0, end, mast->bn, mast->bn->b_end); in mas_push_data()
3309 /* Configure mast for splitting of mast->bn */ in mas_push_data()
3310 split = mt_slots[mast->bn->type] - 2; in mas_push_data()
3314 /* Start using mast->l for the left side. */ in mas_push_data()
3315 tmp_mas.node = mast->l->node; in mas_push_data()
3316 *mast->l = tmp_mas; in mas_push_data()
3318 tmp_mas.node = mast->r->node; in mas_push_data()
3319 *mast->r = tmp_mas; in mas_push_data()
3322 split = mab_no_null_split(mast->bn, split, mt_slots[mast->bn->type]); in mas_push_data()
3325 mast->orig_l->offset += end + 1; in mas_push_data()
3327 mast_split_data(mast, mas, split); in mas_push_data()
3328 mast_fill_bnode(mast, mas, 2); in mas_push_data()
3329 mas_split_final_node(mast, mas, height + 1); in mas_push_data()
3341 struct maple_subtree_state mast; in mas_split() local
3375 mast.l = &l_mas; in mas_split()
3376 mast.r = &r_mas; in mas_split()
3377 mast.orig_l = &prev_l_mas; in mas_split()
3378 mast.orig_r = &prev_r_mas; in mas_split()
3379 mast.bn = b_node; in mas_split()
3383 mas_split_final_node(&mast, mas, height); in mas_split()
3398 if (mas_push_data(mas, height, &mast, true)) in mas_split()
3402 if (mas_push_data(mas, height, &mast, false)) in mas_split()
3406 mast_split_data(&mast, mas, split); in mas_split()
3411 mast.r->max = mas->max; in mas_split()
3412 mast_fill_bnode(&mast, mas, 1); in mas_split()
3413 prev_l_mas = *mast.l; in mas_split()
3414 prev_r_mas = *mast.r; in mas_split()
3824 struct maple_subtree_state mast; in mas_wr_spanning_store() local
3905 mast.bn = &b_node; in mas_wr_spanning_store()
3906 mast.orig_l = &l_mas; in mas_wr_spanning_store()
3907 mast.orig_r = &r_mas; in mas_wr_spanning_store()
3909 return mas_spanning_rebalance(mas, &mast, height + 1); in mas_wr_spanning_store()