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