Lines Matching defs:mast
2230 * @mast: The maple subtree state
2233 static inline void mast_rebalance_next(struct maple_subtree_state *mast)
2235 unsigned char b_end = mast->bn->b_end;
2237 mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node),
2238 mast->bn, b_end);
2239 mast->orig_r->last = mast->orig_r->max;
2244 * @mast: The maple subtree state
2247 static inline void mast_rebalance_prev(struct maple_subtree_state *mast)
2249 unsigned char end = mas_data_end(mast->orig_l) + 1;
2250 unsigned char b_end = mast->bn->b_end;
2252 mab_shift_right(mast->bn, end);
2253 mas_mab_cp(mast->orig_l, 0, end - 1, mast->bn, 0);
2254 mast->l->min = mast->orig_l->min;
2255 mast->orig_l->index = mast->orig_l->min;
2256 mast->bn->b_end = end + b_end;
2257 mast->l->offset += end;
2264 * Data is copied into the @mast->bn.
2265 * @mast: The maple_subtree_state.
2268 bool mast_spanning_rebalance(struct maple_subtree_state *mast)
2270 struct ma_state r_tmp = *mast->orig_r;
2271 struct ma_state l_tmp = *mast->orig_l;
2275 mas_ascend(mast->orig_r);
2276 mas_ascend(mast->orig_l);
2278 if (mast->orig_r->offset < mas_data_end(mast->orig_r)) {
2279 mast->orig_r->offset++;
2281 mas_descend(mast->orig_r);
2282 mast->orig_r->offset = 0;
2285 mast_rebalance_next(mast);
2286 *mast->orig_l = l_tmp;
2288 } else if (mast->orig_l->offset != 0) {
2289 mast->orig_l->offset--;
2291 mas_descend(mast->orig_l);
2292 mast->orig_l->offset =
2293 mas_data_end(mast->orig_l);
2296 mast_rebalance_prev(mast);
2297 *mast->orig_r = r_tmp;
2300 } while (!mte_is_root(mast->orig_r->node));
2302 *mast->orig_r = r_tmp;
2303 *mast->orig_l = l_tmp;
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)
2316 MA_WR_STATE(wr_mas, mast->orig_r, NULL);
2317 mas_ascend(mast->orig_l);
2318 mas_ascend(mast->orig_r);
2320 mast->orig_r->offset = 0;
2321 mast->orig_r->index = mast->r->max;
2323 if (mast->orig_r->last < mast->orig_r->index)
2324 mast->orig_r->last = mast->orig_r->index;
2326 wr_mas.type = mte_node_type(mast->orig_r->node);
2329 mast->orig_l->offset = 0;
2330 mast->orig_l->index = mast->l->min;
2331 wr_mas.mas = mast->orig_l;
2332 wr_mas.type = mte_node_type(mast->orig_l->node);
2335 mast->bn->type = wr_mas.type;
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,
2485 if (mas_is_none(mast->l))
2491 slot = mast->l->offset;
2494 mas_set_split_parent(mast->l, l, r, &slot, split);
2497 mas_set_split_parent(mast->m, l, r, &slot, split);
2500 mas_set_split_parent(mast->r, l, r, &slot, split);
2656 * @mast: The maple subtree state
2663 static inline void mast_cp_to_nodes(struct maple_subtree_state *mast,
2669 mas_node_or_none(mast->l, left);
2670 mas_node_or_none(mast->m, middle);
2671 mas_node_or_none(mast->r, right);
2673 mast->l->min = mast->orig_l->min;
2674 if (split == mast->bn->b_end) {
2675 mast->l->max = mast->orig_r->max;
2679 mab_mas_cp(mast->bn, 0, split, mast->l, new_lmax);
2682 mab_mas_cp(mast->bn, 1 + split, mid_split, mast->m, true);
2683 mast->m->min = mast->bn->pivot[split] + 1;
2687 mast->r->max = mast->orig_r->max;
2689 mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r, false);
2690 mast->r->min = mast->bn->pivot[split] + 1;
2697 * @mast: The maple subtree state
2699 static inline void mast_combine_cp_left(struct maple_subtree_state *mast)
2701 unsigned char l_slot = mast->orig_l->offset;
2706 mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0);
2712 * @mast: The maple subtree state
2714 static inline void mast_combine_cp_right(struct maple_subtree_state *mast)
2716 if (mast->bn->pivot[mast->bn->b_end - 1] >= mast->orig_r->max)
2719 mas_mab_cp(mast->orig_r, mast->orig_r->offset + 1,
2720 mt_slot_count(mast->orig_r->node), mast->bn,
2721 mast->bn->b_end);
2722 mast->orig_r->last = mast->orig_r->max;
2728 * @mast: the maple subtree state
2730 static inline bool mast_sufficient(struct maple_subtree_state *mast)
2732 if (mast->bn->b_end > mt_min_slot_count(mast->orig_l->node))
2741 * @mast: The maple subtree state
2743 static inline bool mast_overflow(struct maple_subtree_state *mast)
2745 if (mast->bn->b_end >= mt_slot_count(mast->orig_l->node))
2814 * @mast: The maple_subtree_state, keeps track of 4 maple states.
2830 struct maple_subtree_state *mast, unsigned char count)
2845 mast->l = &l_mas;
2846 mast->m = &m_mas;
2847 mast->r = &r_mas;
2851 if (((mast->orig_l->min != 0) || (mast->orig_r->max != ULONG_MAX)) &&
2852 unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type]))
2853 mast_spanning_rebalance(mast);
2869 mast->bn->b_end--;
2870 mast->bn->type = mte_node_type(mast->orig_l->node);
2871 split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle,
2872 &mid_split, mast->orig_l->min);
2873 mast_set_split_parents(mast, left, middle, right, split,
2875 mast_cp_to_nodes(mast, left, middle, right, split, mid_split);
2878 * Copy data from next level in the tree to mast->bn from next
2881 memset(mast->bn, 0, sizeof(struct maple_big_node));
2882 mast->bn->type = mte_node_type(left);
2886 if (mas_is_root_limits(mast->l))
2889 mast_ascend(mast);
2890 mast_combine_cp_left(mast);
2891 l_mas.offset = mast->bn->b_end;
2892 mab_set_b_end(mast->bn, &l_mas, left);
2893 mab_set_b_end(mast->bn, &m_mas, middle);
2894 mab_set_b_end(mast->bn, &r_mas, right);
2897 mast_combine_cp_right(mast);
2898 mast->orig_l->last = mast->orig_l->max;
2900 if (mast_sufficient(mast))
2903 if (mast_overflow(mast))
2906 /* May be a new root stored in mast->bn */
2907 if (mas_is_root_limits(mast->orig_l))
2910 mast_spanning_rebalance(mast);
2918 mte_node_type(mast->orig_l->node));
2920 mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true);
2928 if (mas_is_root_limits(mast->l)) {
2930 mas_mn(mast->l)->parent = ma_parent_ptr(mas_tree_parent(mas));
2931 while (!mte_is_root(mast->orig_l->node))
2932 mast_ascend(mast);
2934 mas_mn(&l_mas)->parent = mas_mn(mast->orig_l)->parent;
2937 old_enode = mast->orig_l->node;
2945 return mast->bn->b_end;
2962 struct maple_subtree_state mast;
2983 mast.orig_l = &l_mas;
2984 mast.orig_r = &r_mas;
2985 mast.bn = b_node;
2986 mast.bn->type = mte_node_type(mas->node);
3003 return mas_spanning_rebalance(mas, &mast, empty_count);
3132 * @mast: the maple subtree state
3136 static inline void mas_split_final_node(struct maple_subtree_state *mast,
3143 mast->bn->type = maple_arange_64;
3145 mast->bn->type = maple_range_64;
3152 ancestor = mas_new_ma_node(mas, mast->bn);
3153 mas_set_parent(mas, mast->l->node, ancestor, mast->l->offset);
3154 mas_set_parent(mas, mast->r->node, ancestor, mast->r->offset);
3157 mast->l->node = ancestor;
3158 mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, mast->l, true);
3159 mas->offset = mast->bn->b_end - 1;
3164 * @mast: The maple subtree state
3168 static inline void mast_fill_bnode(struct maple_subtree_state *mast,
3175 memset(mast->bn->gap, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->gap));
3176 memset(mast->bn->slot, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->slot));
3177 memset(mast->bn->pivot, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->pivot));
3178 mast->bn->b_end = 0;
3187 if (cp && mast->l->offset)
3188 mas_mab_cp(mas, 0, mast->l->offset - 1, mast->bn, 0);
3190 split = mast->bn->b_end;
3191 mab_set_b_end(mast->bn, mast->l, mast->l->node);
3192 mast->r->offset = mast->bn->b_end;
3193 mab_set_b_end(mast->bn, mast->r, mast->r->node);
3194 if (mast->bn->pivot[mast->bn->b_end - 1] == mas->max)
3199 mast->bn, mast->bn->b_end);
3201 mast->bn->b_end--;
3202 mast->bn->type = mte_node_type(mas->node);
3208 * @mast: The maple subtree state
3212 static inline void mast_split_data(struct maple_subtree_state *mast,
3217 mab_mas_cp(mast->bn, 0, split, mast->l, true);
3218 mte_set_pivot(mast->r->node, 0, mast->r->max);
3219 mab_mas_cp(mast->bn, split + 1, mast->bn->b_end, mast->r, false);
3220 mast->l->offset = mte_parent_slot(mas->node);
3221 mast->l->max = mast->bn->pivot[split];
3222 mast->r->min = mast->l->max + 1;
3226 p_slot = mast->orig_l->offset;
3227 mas_set_split_parent(mast->orig_l, mast->l->node, mast->r->node,
3229 mas_set_split_parent(mast->orig_r, mast->l->node, mast->r->node,
3238 * @mast: The maple subtree state
3246 struct maple_subtree_state *mast, bool left)
3248 unsigned char slot_total = mast->bn->b_end;
3253 tmp_mas.depth = mast->l->depth;
3264 if (ma_is_leaf(mast->bn->type))
3273 /* Get the data; Fill mast->bn */
3274 mast->bn->b_end++;
3276 mab_shift_right(mast->bn, end + 1);
3277 mas_mab_cp(&tmp_mas, 0, end, mast->bn, 0);
3278 mast->bn->b_end = slot_total + 1;
3280 mas_mab_cp(&tmp_mas, 0, end, mast->bn, mast->bn->b_end);
3283 /* Configure mast for splitting of mast->bn */
3284 split = mt_slots[mast->bn->type] - 2;
3288 /* Start using mast->l for the left side. */
3289 tmp_mas.node = mast->l->node;
3290 *mast->l = tmp_mas;
3292 tmp_mas.node = mast->r->node;
3293 *mast->r = tmp_mas;
3296 split = mab_no_null_split(mast->bn, split, mt_slots[mast->bn->type]);
3299 mast->orig_l->offset += end + 1;
3301 mast_split_data(mast, mas, split);
3302 mast_fill_bnode(mast, mas, 2);
3303 mas_split_final_node(mast, mas, height + 1);
3315 struct maple_subtree_state mast;
3349 mast.l = &l_mas;
3350 mast.r = &r_mas;
3351 mast.orig_l = &prev_l_mas;
3352 mast.orig_r = &prev_r_mas;
3353 mast.bn = b_node;
3357 mas_split_final_node(&mast, mas, height);
3372 if (mas_push_data(mas, height, &mast, true))
3375 if (mas_push_data(mas, height, &mast, false))
3379 mast_split_data(&mast, mas, split);
3384 mast.r->max = mas->max;
3385 mast_fill_bnode(&mast, mas, 1);
3386 prev_l_mas = *mast.l;
3387 prev_r_mas = *mast.r;
3785 struct maple_subtree_state mast;
3866 mast.bn = &b_node;
3867 mast.orig_l = &l_mas;
3868 mast.orig_r = &r_mas;
3870 return mas_spanning_rebalance(mas, &mast, height + 1);