Lines Matching full:mast
2262 * @mast: The maple subtree state
2265 static inline void mast_rebalance_next(struct maple_subtree_state *mast) in mast_rebalance_next() argument
2267 unsigned char b_end = mast->bn->b_end; in mast_rebalance_next()
2269 mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node), in mast_rebalance_next()
2270 mast->bn, b_end); in mast_rebalance_next()
2271 mast->orig_r->last = mast->orig_r->max; in mast_rebalance_next()
2276 * @mast: The maple subtree state
2279 static inline void mast_rebalance_prev(struct maple_subtree_state *mast) in mast_rebalance_prev() argument
2281 unsigned char end = mas_data_end(mast->orig_l) + 1; in mast_rebalance_prev()
2282 unsigned char b_end = mast->bn->b_end; in mast_rebalance_prev()
2284 mab_shift_right(mast->bn, end); in mast_rebalance_prev()
2285 mas_mab_cp(mast->orig_l, 0, end - 1, mast->bn, 0); in mast_rebalance_prev()
2286 mast->l->min = mast->orig_l->min; in mast_rebalance_prev()
2287 mast->orig_l->index = mast->orig_l->min; in mast_rebalance_prev()
2288 mast->bn->b_end = end + b_end; in mast_rebalance_prev()
2289 mast->l->offset += end; in mast_rebalance_prev()
2296 * Data is copied into the @mast->bn.
2297 * @mast: The maple_subtree_state.
2300 bool mast_spanning_rebalance(struct maple_subtree_state *mast) in mast_spanning_rebalance() argument
2302 struct ma_state r_tmp = *mast->orig_r; in mast_spanning_rebalance()
2303 struct ma_state l_tmp = *mast->orig_l; in mast_spanning_rebalance()
2306 r_tmp = *mast->orig_r; in mast_spanning_rebalance()
2307 l_tmp = *mast->orig_l; in mast_spanning_rebalance()
2309 mas_ascend(mast->orig_r); in mast_spanning_rebalance()
2310 mas_ascend(mast->orig_l); in mast_spanning_rebalance()
2312 if (mast->orig_r->offset < mas_data_end(mast->orig_r)) { in mast_spanning_rebalance()
2313 mast->orig_r->offset++; in mast_spanning_rebalance()
2315 mas_descend(mast->orig_r); in mast_spanning_rebalance()
2316 mast->orig_r->offset = 0; in mast_spanning_rebalance()
2319 mast_rebalance_next(mast); in mast_spanning_rebalance()
2320 *mast->orig_l = l_tmp; in mast_spanning_rebalance()
2322 } else if (mast->orig_l->offset != 0) { in mast_spanning_rebalance()
2323 mast->orig_l->offset--; in mast_spanning_rebalance()
2325 mas_descend(mast->orig_l); in mast_spanning_rebalance()
2326 mast->orig_l->offset = in mast_spanning_rebalance()
2327 mas_data_end(mast->orig_l); in mast_spanning_rebalance()
2330 mast_rebalance_prev(mast); in mast_spanning_rebalance()
2331 *mast->orig_r = r_tmp; in mast_spanning_rebalance()
2334 } while (!mte_is_root(mast->orig_r->node)); in mast_spanning_rebalance()
2336 *mast->orig_r = r_tmp; in mast_spanning_rebalance()
2337 *mast->orig_l = l_tmp; in mast_spanning_rebalance()
2343 * @mast: the maple subtree state.
2346 * data already in the new tree (@mast->l and @mast->r).
2348 static inline void mast_ascend(struct maple_subtree_state *mast) in mast_ascend() argument
2350 MA_WR_STATE(wr_mas, mast->orig_r, NULL); in mast_ascend()
2351 mas_ascend(mast->orig_l); in mast_ascend()
2352 mas_ascend(mast->orig_r); in mast_ascend()
2354 mast->orig_r->offset = 0; in mast_ascend()
2355 mast->orig_r->index = mast->r->max; in mast_ascend()
2357 if (mast->orig_r->last < mast->orig_r->index) in mast_ascend()
2358 mast->orig_r->last = mast->orig_r->index; in mast_ascend()
2360 wr_mas.type = mte_node_type(mast->orig_r->node); in mast_ascend()
2363 mast->orig_l->offset = 0; in mast_ascend()
2364 mast->orig_l->index = mast->l->min; in mast_ascend()
2365 wr_mas.mas = mast->orig_l; in mast_ascend()
2366 wr_mas.type = mte_node_type(mast->orig_l->node); in mast_ascend()
2369 mast->bn->type = wr_mas.type; in mast_ascend()
2502 * is taken from @mast->l.
2503 * @mast - the maple subtree state
2508 static inline void mast_set_split_parents(struct maple_subtree_state *mast, in mast_set_split_parents() argument
2519 if (mas_is_none(mast->l)) in mast_set_split_parents()
2525 slot = mast->l->offset; in mast_set_split_parents()
2528 mas_set_split_parent(mast->l, l, r, &slot, split); in mast_set_split_parents()
2531 mas_set_split_parent(mast->m, l, r, &slot, split); in mast_set_split_parents()
2534 mas_set_split_parent(mast->r, l, r, &slot, split); in mast_set_split_parents()
2688 * @mast: The maple subtree state
2695 static inline void mast_cp_to_nodes(struct maple_subtree_state *mast, in mast_cp_to_nodes() argument
2701 mast->l->node = mte_node_or_none(left); in mast_cp_to_nodes()
2702 mast->m->node = mte_node_or_none(middle); in mast_cp_to_nodes()
2703 mast->r->node = mte_node_or_none(right); in mast_cp_to_nodes()
2705 mast->l->min = mast->orig_l->min; in mast_cp_to_nodes()
2706 if (split == mast->bn->b_end) { in mast_cp_to_nodes()
2707 mast->l->max = mast->orig_r->max; in mast_cp_to_nodes()
2711 mab_mas_cp(mast->bn, 0, split, mast->l, new_lmax); in mast_cp_to_nodes()
2714 mab_mas_cp(mast->bn, 1 + split, mid_split, mast->m, true); in mast_cp_to_nodes()
2715 mast->m->min = mast->bn->pivot[split] + 1; in mast_cp_to_nodes()
2719 mast->r->max = mast->orig_r->max; in mast_cp_to_nodes()
2721 mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r, false); in mast_cp_to_nodes()
2722 mast->r->min = mast->bn->pivot[split] + 1; in mast_cp_to_nodes()
2729 * @mast: The maple subtree state
2731 static inline void mast_combine_cp_left(struct maple_subtree_state *mast) in mast_combine_cp_left() argument
2733 unsigned char l_slot = mast->orig_l->offset; in mast_combine_cp_left()
2738 mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0); in mast_combine_cp_left()
2744 * @mast: The maple subtree state
2746 static inline void mast_combine_cp_right(struct maple_subtree_state *mast) in mast_combine_cp_right() argument
2748 if (mast->bn->pivot[mast->bn->b_end - 1] >= mast->orig_r->max) in mast_combine_cp_right()
2751 mas_mab_cp(mast->orig_r, mast->orig_r->offset + 1, in mast_combine_cp_right()
2752 mt_slot_count(mast->orig_r->node), mast->bn, in mast_combine_cp_right()
2753 mast->bn->b_end); in mast_combine_cp_right()
2754 mast->orig_r->last = mast->orig_r->max; in mast_combine_cp_right()
2760 * @mast: the maple subtree state
2762 static inline bool mast_sufficient(struct maple_subtree_state *mast) in mast_sufficient() argument
2764 if (mast->bn->b_end > mt_min_slot_count(mast->orig_l->node)) in mast_sufficient()
2773 * @mast: The maple subtree state
2775 static inline bool mast_overflow(struct maple_subtree_state *mast) in mast_overflow() argument
2777 if (mast->bn->b_end >= mt_slot_count(mast->orig_l->node)) in mast_overflow()
2848 * @mast: The maple_subtree_state, keeps track of 4 maple states.
2864 struct maple_subtree_state *mast, unsigned char count) in mas_spanning_rebalance() argument
2879 mast->l = &l_mas; in mas_spanning_rebalance()
2880 mast->m = &m_mas; in mas_spanning_rebalance()
2881 mast->r = &r_mas; in mas_spanning_rebalance()
2885 if (((mast->orig_l->min != 0) || (mast->orig_r->max != ULONG_MAX)) && in mas_spanning_rebalance()
2886 unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type])) in mas_spanning_rebalance()
2887 mast_spanning_rebalance(mast); in mas_spanning_rebalance()
2903 mast->bn->b_end--; in mas_spanning_rebalance()
2904 mast->bn->type = mte_node_type(mast->orig_l->node); in mas_spanning_rebalance()
2905 split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle, in mas_spanning_rebalance()
2906 &mid_split, mast->orig_l->min); in mas_spanning_rebalance()
2907 mast_set_split_parents(mast, left, middle, right, split, in mas_spanning_rebalance()
2909 mast_cp_to_nodes(mast, left, middle, right, split, mid_split); in mas_spanning_rebalance()
2912 * Copy data from next level in the tree to mast->bn from next in mas_spanning_rebalance()
2915 memset(mast->bn, 0, sizeof(struct maple_big_node)); in mas_spanning_rebalance()
2916 mast->bn->type = mte_node_type(left); in mas_spanning_rebalance()
2920 if (mas_is_root_limits(mast->l)) in mas_spanning_rebalance()
2923 mast_ascend(mast); in mas_spanning_rebalance()
2924 mast_combine_cp_left(mast); in mas_spanning_rebalance()
2925 l_mas.offset = mast->bn->b_end; in mas_spanning_rebalance()
2926 mab_set_b_end(mast->bn, &l_mas, left); in mas_spanning_rebalance()
2927 mab_set_b_end(mast->bn, &m_mas, middle); in mas_spanning_rebalance()
2928 mab_set_b_end(mast->bn, &r_mas, right); in mas_spanning_rebalance()
2931 mast_combine_cp_right(mast); in mas_spanning_rebalance()
2932 mast->orig_l->last = mast->orig_l->max; in mas_spanning_rebalance()
2934 if (mast_sufficient(mast)) in mas_spanning_rebalance()
2937 if (mast_overflow(mast)) in mas_spanning_rebalance()
2940 /* May be a new root stored in mast->bn */ in mas_spanning_rebalance()
2941 if (mas_is_root_limits(mast->orig_l)) in mas_spanning_rebalance()
2944 mast_spanning_rebalance(mast); in mas_spanning_rebalance()
2952 mte_node_type(mast->orig_l->node)); in mas_spanning_rebalance()
2954 mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true); in mas_spanning_rebalance()
2962 if (mas_is_root_limits(mast->l)) { in mas_spanning_rebalance()
2964 mas_mn(mast->l)->parent = ma_parent_ptr(mas_tree_parent(mas)); in mas_spanning_rebalance()
2965 while (!mte_is_root(mast->orig_l->node)) in mas_spanning_rebalance()
2966 mast_ascend(mast); in mas_spanning_rebalance()
2968 mas_mn(&l_mas)->parent = mas_mn(mast->orig_l)->parent; in mas_spanning_rebalance()
2971 old_enode = mast->orig_l->node; in mas_spanning_rebalance()
2979 return mast->bn->b_end; in mas_spanning_rebalance()
2996 struct maple_subtree_state mast; in mas_rebalance() local
3017 mast.orig_l = &l_mas; in mas_rebalance()
3018 mast.orig_r = &r_mas; in mas_rebalance()
3019 mast.bn = b_node; in mas_rebalance()
3020 mast.bn->type = mte_node_type(mas->node); in mas_rebalance()
3037 return mas_spanning_rebalance(mas, &mast, empty_count); in mas_rebalance()
3166 * @mast: the maple subtree state
3170 static inline bool mas_split_final_node(struct maple_subtree_state *mast, in mas_split_final_node() argument
3177 mast->bn->type = maple_arange_64; in mas_split_final_node()
3179 mast->bn->type = maple_range_64; in mas_split_final_node()
3186 ancestor = mas_new_ma_node(mas, mast->bn); in mas_split_final_node()
3187 mas_set_parent(mas, mast->l->node, ancestor, mast->l->offset); in mas_split_final_node()
3188 mas_set_parent(mas, mast->r->node, ancestor, mast->r->offset); in mas_split_final_node()
3191 mast->l->node = ancestor; in mas_split_final_node()
3192 mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, mast->l, true); in mas_split_final_node()
3193 mas->offset = mast->bn->b_end - 1; in mas_split_final_node()
3199 * @mast: The maple subtree state
3203 static inline void mast_fill_bnode(struct maple_subtree_state *mast, in mast_fill_bnode() argument
3210 memset(mast->bn->gap, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->gap)); in mast_fill_bnode()
3211 memset(mast->bn->slot, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->slot)); in mast_fill_bnode()
3212 memset(mast->bn->pivot, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->pivot)); in mast_fill_bnode()
3213 mast->bn->b_end = 0; in mast_fill_bnode()
3222 if (cp && mast->l->offset) in mast_fill_bnode()
3223 mas_mab_cp(mas, 0, mast->l->offset - 1, mast->bn, 0); in mast_fill_bnode()
3225 split = mast->bn->b_end; in mast_fill_bnode()
3226 mab_set_b_end(mast->bn, mast->l, mast->l->node); in mast_fill_bnode()
3227 mast->r->offset = mast->bn->b_end; in mast_fill_bnode()
3228 mab_set_b_end(mast->bn, mast->r, mast->r->node); in mast_fill_bnode()
3229 if (mast->bn->pivot[mast->bn->b_end - 1] == mas->max) in mast_fill_bnode()
3234 mast->bn, mast->bn->b_end); in mast_fill_bnode()
3236 mast->bn->b_end--; in mast_fill_bnode()
3237 mast->bn->type = mte_node_type(mas->node); in mast_fill_bnode()
3243 * @mast: The maple subtree state
3247 static inline void mast_split_data(struct maple_subtree_state *mast, in mast_split_data() argument
3252 mab_mas_cp(mast->bn, 0, split, mast->l, true); in mast_split_data()
3253 mte_set_pivot(mast->r->node, 0, mast->r->max); in mast_split_data()
3254 mab_mas_cp(mast->bn, split + 1, mast->bn->b_end, mast->r, false); in mast_split_data()
3255 mast->l->offset = mte_parent_slot(mas->node); in mast_split_data()
3256 mast->l->max = mast->bn->pivot[split]; in mast_split_data()
3257 mast->r->min = mast->l->max + 1; in mast_split_data()
3261 p_slot = mast->orig_l->offset; in mast_split_data()
3262 mas_set_split_parent(mast->orig_l, mast->l->node, mast->r->node, in mast_split_data()
3264 mas_set_split_parent(mast->orig_r, mast->l->node, mast->r->node, in mast_split_data()
3273 * @mast: The maple subtree state
3281 struct maple_subtree_state *mast, bool left) in mas_push_data() argument
3283 unsigned char slot_total = mast->bn->b_end; in mas_push_data()
3288 tmp_mas.depth = mast->l->depth; in mas_push_data()
3299 if (ma_is_leaf(mast->bn->type)) in mas_push_data()
3308 /* Get the data; Fill mast->bn */ in mas_push_data()
3309 mast->bn->b_end++; in mas_push_data()
3311 mab_shift_right(mast->bn, end + 1); in mas_push_data()
3312 mas_mab_cp(&tmp_mas, 0, end, mast->bn, 0); in mas_push_data()
3313 mast->bn->b_end = slot_total + 1; in mas_push_data()
3315 mas_mab_cp(&tmp_mas, 0, end, mast->bn, mast->bn->b_end); in mas_push_data()
3318 /* Configure mast for splitting of mast->bn */ in mas_push_data()
3319 split = mt_slots[mast->bn->type] - 2; in mas_push_data()
3323 /* Start using mast->l for the left side. */ in mas_push_data()
3324 tmp_mas.node = mast->l->node; in mas_push_data()
3325 *mast->l = tmp_mas; in mas_push_data()
3327 tmp_mas.node = mast->r->node; in mas_push_data()
3328 *mast->r = tmp_mas; in mas_push_data()
3331 split = mab_no_null_split(mast->bn, split, mt_slots[mast->bn->type]); in mas_push_data()
3334 mast->orig_l->offset += end + 1; in mas_push_data()
3336 mast_split_data(mast, mas, split); in mas_push_data()
3337 mast_fill_bnode(mast, mas, 2); in mas_push_data()
3338 mas_split_final_node(mast, mas, height + 1); in mas_push_data()
3350 struct maple_subtree_state mast; in mas_split() local
3384 mast.l = &l_mas; in mas_split()
3385 mast.r = &r_mas; in mas_split()
3386 mast.orig_l = &prev_l_mas; in mas_split()
3387 mast.orig_r = &prev_r_mas; in mas_split()
3388 mast.bn = b_node; in mas_split()
3392 mas_split_final_node(&mast, mas, height); in mas_split()
3407 if (mas_push_data(mas, height, &mast, true)) in mas_split()
3411 if (mas_push_data(mas, height, &mast, false)) in mas_split()
3415 mast_split_data(&mast, mas, split); in mas_split()
3420 mast.r->max = mas->max; in mas_split()
3421 mast_fill_bnode(&mast, mas, 1); in mas_split()
3422 prev_l_mas = *mast.l; in mas_split()
3423 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()