Lines Matching refs:mast
2323 static inline void mast_topiary(struct maple_subtree_state *mast) in mast_topiary() argument
2325 MA_WR_STATE(wr_mas, mast->orig_l, NULL); in mast_topiary()
2330 wr_mas.type = mte_node_type(mast->orig_l->node); in mast_topiary()
2331 mast->orig_l->index = mast->orig_l->last; in mast_topiary()
2333 l_start = mast->orig_l->offset + 1; in mast_topiary()
2334 l_end = mas_data_end(mast->orig_l); in mast_topiary()
2336 r_end = mast->orig_r->offset; in mast_topiary()
2341 l_slots = ma_slots(mas_mn(mast->orig_l), in mast_topiary()
2342 mte_node_type(mast->orig_l->node)); in mast_topiary()
2344 r_slots = ma_slots(mas_mn(mast->orig_r), in mast_topiary()
2345 mte_node_type(mast->orig_r->node)); in mast_topiary()
2348 mte_dead_node(mas_slot_locked(mast->orig_l, l_slots, l_start))) { in mast_topiary()
2352 if (mte_dead_node(mas_slot_locked(mast->orig_r, r_slots, r_end))) { in mast_topiary()
2357 if ((l_start > r_end) && (mast->orig_l->node == mast->orig_r->node)) in mast_topiary()
2361 if (mast->orig_l->node == mast->orig_r->node) { in mast_topiary()
2362 return mas_topiary_range(mast->orig_l, mast->destroy, in mast_topiary()
2367 if (mte_is_leaf(mast->orig_r->node)) in mast_topiary()
2370 if (mte_dead_node(mas_slot_locked(mast->orig_l, l_slots, l_end))) in mast_topiary()
2375 mas_topiary_range(mast->orig_l, mast->destroy, l_start, l_end); in mast_topiary()
2377 if (mte_dead_node(mas_slot_locked(mast->orig_r, r_slots, r_start))) in mast_topiary()
2381 mas_topiary_range(mast->orig_r, mast->destroy, 0, r_end); in mast_topiary()
2389 static inline void mast_rebalance_next(struct maple_subtree_state *mast) in mast_rebalance_next() argument
2391 unsigned char b_end = mast->bn->b_end; in mast_rebalance_next()
2393 mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node), in mast_rebalance_next()
2394 mast->bn, b_end); in mast_rebalance_next()
2395 mast->orig_r->last = mast->orig_r->max; in mast_rebalance_next()
2403 static inline void mast_rebalance_prev(struct maple_subtree_state *mast) in mast_rebalance_prev() argument
2405 unsigned char end = mas_data_end(mast->orig_l) + 1; in mast_rebalance_prev()
2406 unsigned char b_end = mast->bn->b_end; in mast_rebalance_prev()
2408 mab_shift_right(mast->bn, end); in mast_rebalance_prev()
2409 mas_mab_cp(mast->orig_l, 0, end - 1, mast->bn, 0); in mast_rebalance_prev()
2410 mast->l->min = mast->orig_l->min; in mast_rebalance_prev()
2411 mast->orig_l->index = mast->orig_l->min; in mast_rebalance_prev()
2412 mast->bn->b_end = end + b_end; in mast_rebalance_prev()
2413 mast->l->offset += end; in mast_rebalance_prev()
2424 bool mast_spanning_rebalance(struct maple_subtree_state *mast) in mast_spanning_rebalance() argument
2426 struct ma_state r_tmp = *mast->orig_r; in mast_spanning_rebalance()
2427 struct ma_state l_tmp = *mast->orig_l; in mast_spanning_rebalance()
2432 r_tmp = *mast->orig_r; in mast_spanning_rebalance()
2433 l_tmp = *mast->orig_l; in mast_spanning_rebalance()
2435 mas_ascend(mast->orig_r); in mast_spanning_rebalance()
2436 mas_ascend(mast->orig_l); in mast_spanning_rebalance()
2439 (mast->orig_r->node == mast->orig_l->node)) { in mast_spanning_rebalance()
2440 ancestor = mast->orig_r->node; in mast_spanning_rebalance()
2441 end = mast->orig_r->offset - 1; in mast_spanning_rebalance()
2442 start = mast->orig_l->offset + 1; in mast_spanning_rebalance()
2445 if (mast->orig_r->offset < mas_data_end(mast->orig_r)) { in mast_spanning_rebalance()
2447 ancestor = mast->orig_r->node; in mast_spanning_rebalance()
2451 mast->orig_r->offset++; in mast_spanning_rebalance()
2453 mas_descend(mast->orig_r); in mast_spanning_rebalance()
2454 mast->orig_r->offset = 0; in mast_spanning_rebalance()
2458 mast_rebalance_next(mast); in mast_spanning_rebalance()
2471 mas_topiary_range(&r_tmp, mast->destroy, in mast_spanning_rebalance()
2475 mat_add(mast->free, child); in mast_spanning_rebalance()
2479 *mast->orig_l = l_tmp; in mast_spanning_rebalance()
2482 } else if (mast->orig_l->offset != 0) { in mast_spanning_rebalance()
2484 ancestor = mast->orig_l->node; in mast_spanning_rebalance()
2485 end = mas_data_end(mast->orig_l); in mast_spanning_rebalance()
2488 mast->orig_l->offset--; in mast_spanning_rebalance()
2490 mas_descend(mast->orig_l); in mast_spanning_rebalance()
2491 mast->orig_l->offset = in mast_spanning_rebalance()
2492 mas_data_end(mast->orig_l); in mast_spanning_rebalance()
2496 mast_rebalance_prev(mast); in mast_spanning_rebalance()
2511 mas_topiary_range(&l_tmp, mast->destroy, in mast_spanning_rebalance()
2515 mat_add(mast->free, child); in mast_spanning_rebalance()
2519 *mast->orig_r = r_tmp; in mast_spanning_rebalance()
2522 } while (!mte_is_root(mast->orig_r->node)); in mast_spanning_rebalance()
2524 *mast->orig_r = r_tmp; in mast_spanning_rebalance()
2525 *mast->orig_l = l_tmp; in mast_spanning_rebalance()
2538 mast_ascend_free(struct maple_subtree_state *mast) in mast_ascend_free() argument
2540 MA_WR_STATE(wr_mas, mast->orig_r, NULL); in mast_ascend_free()
2541 struct maple_enode *left = mast->orig_l->node; in mast_ascend_free()
2542 struct maple_enode *right = mast->orig_r->node; in mast_ascend_free()
2544 mas_ascend(mast->orig_l); in mast_ascend_free()
2545 mas_ascend(mast->orig_r); in mast_ascend_free()
2546 mat_add(mast->free, left); in mast_ascend_free()
2549 mat_add(mast->free, right); in mast_ascend_free()
2551 mast->orig_r->offset = 0; in mast_ascend_free()
2552 mast->orig_r->index = mast->r->max; in mast_ascend_free()
2554 if (mast->orig_r->last < mast->orig_r->index) in mast_ascend_free()
2555 mast->orig_r->last = mast->orig_r->index; in mast_ascend_free()
2560 wr_mas.type = mte_node_type(mast->orig_r->node); in mast_ascend_free()
2563 mast->orig_l->offset = 0; in mast_ascend_free()
2564 mast->orig_l->index = mast->l->min; in mast_ascend_free()
2565 wr_mas.mas = mast->orig_l; in mast_ascend_free()
2566 wr_mas.type = mte_node_type(mast->orig_l->node); in mast_ascend_free()
2569 mast->bn->type = wr_mas.type; in mast_ascend_free()
2708 static inline void mast_set_split_parents(struct maple_subtree_state *mast, in mast_set_split_parents() argument
2719 if (mas_is_none(mast->l)) in mast_set_split_parents()
2725 slot = mast->l->offset; in mast_set_split_parents()
2728 mas_set_split_parent(mast->l, l, r, &slot, split); in mast_set_split_parents()
2731 mas_set_split_parent(mast->m, l, r, &slot, split); in mast_set_split_parents()
2734 mas_set_split_parent(mast->r, l, r, &slot, split); in mast_set_split_parents()
2774 static inline void mast_new_root(struct maple_subtree_state *mast, in mast_new_root() argument
2777 mas_mn(mast->l)->parent = in mast_new_root()
2779 if (!mte_dead_node(mast->orig_l->node) && in mast_new_root()
2780 !mte_is_root(mast->orig_l->node)) { in mast_new_root()
2782 mast_ascend_free(mast); in mast_new_root()
2783 mast_topiary(mast); in mast_new_root()
2784 } while (!mte_is_root(mast->orig_l->node)); in mast_new_root()
2786 if ((mast->orig_l->node != mas->node) && in mast_new_root()
2787 (mast->l->depth > mas_mt_height(mas))) { in mast_new_root()
2788 mat_add(mast->free, mas->node); in mast_new_root()
2801 static inline void mast_cp_to_nodes(struct maple_subtree_state *mast, in mast_cp_to_nodes() argument
2807 mast->l->node = mte_node_or_none(left); in mast_cp_to_nodes()
2808 mast->m->node = mte_node_or_none(middle); in mast_cp_to_nodes()
2809 mast->r->node = mte_node_or_none(right); in mast_cp_to_nodes()
2811 mast->l->min = mast->orig_l->min; in mast_cp_to_nodes()
2812 if (split == mast->bn->b_end) { in mast_cp_to_nodes()
2813 mast->l->max = mast->orig_r->max; in mast_cp_to_nodes()
2817 mab_mas_cp(mast->bn, 0, split, mast->l, new_lmax); in mast_cp_to_nodes()
2820 mab_mas_cp(mast->bn, 1 + split, mid_split, mast->m, true); in mast_cp_to_nodes()
2821 mast->m->min = mast->bn->pivot[split] + 1; in mast_cp_to_nodes()
2825 mast->r->max = mast->orig_r->max; in mast_cp_to_nodes()
2827 mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r, false); in mast_cp_to_nodes()
2828 mast->r->min = mast->bn->pivot[split] + 1; in mast_cp_to_nodes()
2837 static inline void mast_combine_cp_left(struct maple_subtree_state *mast) in mast_combine_cp_left() argument
2839 unsigned char l_slot = mast->orig_l->offset; in mast_combine_cp_left()
2844 mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0); in mast_combine_cp_left()
2852 static inline void mast_combine_cp_right(struct maple_subtree_state *mast) in mast_combine_cp_right() argument
2854 if (mast->bn->pivot[mast->bn->b_end - 1] >= mast->orig_r->max) in mast_combine_cp_right()
2857 mas_mab_cp(mast->orig_r, mast->orig_r->offset + 1, in mast_combine_cp_right()
2858 mt_slot_count(mast->orig_r->node), mast->bn, in mast_combine_cp_right()
2859 mast->bn->b_end); in mast_combine_cp_right()
2860 mast->orig_r->last = mast->orig_r->max; in mast_combine_cp_right()
2868 static inline bool mast_sufficient(struct maple_subtree_state *mast) in mast_sufficient() argument
2870 if (mast->bn->b_end > mt_min_slot_count(mast->orig_l->node)) in mast_sufficient()
2881 static inline bool mast_overflow(struct maple_subtree_state *mast) in mast_overflow() argument
2883 if (mast->bn->b_end >= mt_slot_count(mast->orig_l->node)) in mast_overflow()
2970 struct maple_subtree_state *mast, unsigned char count) in mas_spanning_rebalance() argument
2986 mast->l = &l_mas; in mas_spanning_rebalance()
2987 mast->m = &m_mas; in mas_spanning_rebalance()
2988 mast->r = &r_mas; in mas_spanning_rebalance()
2989 mast->free = &free; in mas_spanning_rebalance()
2990 mast->destroy = &destroy; in mas_spanning_rebalance()
2992 if (!(mast->orig_l->min && mast->orig_r->max == ULONG_MAX) && in mas_spanning_rebalance()
2993 unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type])) in mas_spanning_rebalance()
2994 mast_spanning_rebalance(mast); in mas_spanning_rebalance()
2996 mast->orig_l->depth = 0; in mas_spanning_rebalance()
3010 mast->bn->b_end--; in mas_spanning_rebalance()
3011 mast->bn->type = mte_node_type(mast->orig_l->node); in mas_spanning_rebalance()
3012 split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle, in mas_spanning_rebalance()
3013 &mid_split, mast->orig_l->min); in mas_spanning_rebalance()
3014 mast_set_split_parents(mast, left, middle, right, split, in mas_spanning_rebalance()
3016 mast_cp_to_nodes(mast, left, middle, right, split, mid_split); in mas_spanning_rebalance()
3022 memset(mast->bn, 0, sizeof(struct maple_big_node)); in mas_spanning_rebalance()
3023 mast->bn->type = mte_node_type(left); in mas_spanning_rebalance()
3024 mast->orig_l->depth++; in mas_spanning_rebalance()
3027 if (mas_is_root_limits(mast->l)) in mas_spanning_rebalance()
3030 mast_ascend_free(mast); in mas_spanning_rebalance()
3031 mast_combine_cp_left(mast); in mas_spanning_rebalance()
3032 l_mas.offset = mast->bn->b_end; in mas_spanning_rebalance()
3033 mab_set_b_end(mast->bn, &l_mas, left); in mas_spanning_rebalance()
3034 mab_set_b_end(mast->bn, &m_mas, middle); in mas_spanning_rebalance()
3035 mab_set_b_end(mast->bn, &r_mas, right); in mas_spanning_rebalance()
3038 mast_combine_cp_right(mast); in mas_spanning_rebalance()
3039 mast_topiary(mast); in mas_spanning_rebalance()
3040 mast->orig_l->last = mast->orig_l->max; in mas_spanning_rebalance()
3042 if (mast_sufficient(mast)) in mas_spanning_rebalance()
3045 if (mast_overflow(mast)) in mas_spanning_rebalance()
3049 if (mas_is_root_limits(mast->orig_l)) in mas_spanning_rebalance()
3052 mast_spanning_rebalance(mast); in mas_spanning_rebalance()
3060 mte_node_type(mast->orig_l->node)); in mas_spanning_rebalance()
3061 mast->orig_l->depth++; in mas_spanning_rebalance()
3062 mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true); in mas_spanning_rebalance()
3070 if (mas_is_root_limits(mast->l)) { in mas_spanning_rebalance()
3072 mast_new_root(mast, mas); in mas_spanning_rebalance()
3074 mas_mn(&l_mas)->parent = mas_mn(mast->orig_l)->parent; in mas_spanning_rebalance()
3077 if (!mte_dead_node(mast->orig_l->node)) in mas_spanning_rebalance()
3078 mat_add(&free, mast->orig_l->node); in mas_spanning_rebalance()
3080 mas->depth = mast->orig_l->depth; in mas_spanning_rebalance()
3081 *mast->orig_l = l_mas; in mas_spanning_rebalance()
3085 mast->orig_l->depth = mas->depth; in mas_spanning_rebalance()
3086 mast->orig_l->alloc = mas->alloc; in mas_spanning_rebalance()
3087 *mas = *mast->orig_l; in mas_spanning_rebalance()
3090 return mast->bn->b_end; in mas_spanning_rebalance()
3107 struct maple_subtree_state mast; in mas_rebalance() local
3128 mast.orig_l = &l_mas; in mas_rebalance()
3129 mast.orig_r = &r_mas; in mas_rebalance()
3130 mast.bn = b_node; in mas_rebalance()
3131 mast.bn->type = mte_node_type(mas->node); in mas_rebalance()
3148 return mas_spanning_rebalance(mas, &mast, empty_count); in mas_rebalance()
3278 static inline bool mas_split_final_node(struct maple_subtree_state *mast, in mas_split_final_node() argument
3285 mast->bn->type = maple_arange_64; in mas_split_final_node()
3287 mast->bn->type = maple_range_64; in mas_split_final_node()
3294 ancestor = mas_new_ma_node(mas, mast->bn); in mas_split_final_node()
3295 mte_set_parent(mast->l->node, ancestor, mast->l->offset); in mas_split_final_node()
3296 mte_set_parent(mast->r->node, ancestor, mast->r->offset); in mas_split_final_node()
3299 mast->l->node = ancestor; in mas_split_final_node()
3300 mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, mast->l, true); in mas_split_final_node()
3301 mas->offset = mast->bn->b_end - 1; in mas_split_final_node()
3311 static inline void mast_fill_bnode(struct maple_subtree_state *mast, in mast_fill_bnode() argument
3319 memset(mast->bn->gap, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->gap)); in mast_fill_bnode()
3320 memset(mast->bn->slot, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->slot)); in mast_fill_bnode()
3321 memset(mast->bn->pivot, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->pivot)); in mast_fill_bnode()
3322 mast->bn->b_end = 0; in mast_fill_bnode()
3328 mat_add(mast->free, old); in mast_fill_bnode()
3332 if (cp && mast->l->offset) in mast_fill_bnode()
3333 mas_mab_cp(mas, 0, mast->l->offset - 1, mast->bn, 0); in mast_fill_bnode()
3335 split = mast->bn->b_end; in mast_fill_bnode()
3336 mab_set_b_end(mast->bn, mast->l, mast->l->node); in mast_fill_bnode()
3337 mast->r->offset = mast->bn->b_end; in mast_fill_bnode()
3338 mab_set_b_end(mast->bn, mast->r, mast->r->node); in mast_fill_bnode()
3339 if (mast->bn->pivot[mast->bn->b_end - 1] == mas->max) in mast_fill_bnode()
3344 mast->bn, mast->bn->b_end); in mast_fill_bnode()
3346 mast->bn->b_end--; in mast_fill_bnode()
3347 mast->bn->type = mte_node_type(mas->node); in mast_fill_bnode()
3357 static inline void mast_split_data(struct maple_subtree_state *mast, in mast_split_data() argument
3362 mab_mas_cp(mast->bn, 0, split, mast->l, true); in mast_split_data()
3363 mte_set_pivot(mast->r->node, 0, mast->r->max); in mast_split_data()
3364 mab_mas_cp(mast->bn, split + 1, mast->bn->b_end, mast->r, false); in mast_split_data()
3365 mast->l->offset = mte_parent_slot(mas->node); in mast_split_data()
3366 mast->l->max = mast->bn->pivot[split]; in mast_split_data()
3367 mast->r->min = mast->l->max + 1; in mast_split_data()
3371 p_slot = mast->orig_l->offset; in mast_split_data()
3372 mas_set_split_parent(mast->orig_l, mast->l->node, mast->r->node, in mast_split_data()
3374 mas_set_split_parent(mast->orig_r, mast->l->node, mast->r->node, in mast_split_data()
3391 struct maple_subtree_state *mast, bool left) in mas_push_data() argument
3393 unsigned char slot_total = mast->bn->b_end; in mas_push_data()
3398 tmp_mas.depth = mast->l->depth; in mas_push_data()
3409 if (ma_is_leaf(mast->bn->type)) in mas_push_data()
3419 mast->bn->b_end++; in mas_push_data()
3421 mab_shift_right(mast->bn, end + 1); in mas_push_data()
3422 mas_mab_cp(&tmp_mas, 0, end, mast->bn, 0); in mas_push_data()
3423 mast->bn->b_end = slot_total + 1; in mas_push_data()
3425 mas_mab_cp(&tmp_mas, 0, end, mast->bn, mast->bn->b_end); in mas_push_data()
3429 split = mt_slots[mast->bn->type] - 2; in mas_push_data()
3432 mat_add(mast->free, mas->node); in mas_push_data()
3435 tmp_mas.node = mast->l->node; in mas_push_data()
3436 *mast->l = tmp_mas; in mas_push_data()
3438 mat_add(mast->free, tmp_mas.node); in mas_push_data()
3439 tmp_mas.node = mast->r->node; in mas_push_data()
3440 *mast->r = tmp_mas; in mas_push_data()
3443 split = mab_no_null_split(mast->bn, split, mt_slots[mast->bn->type]); in mas_push_data()
3446 mast->orig_l->offset += end + 1; in mas_push_data()
3448 mast_split_data(mast, mas, split); in mas_push_data()
3449 mast_fill_bnode(mast, mas, 2); in mas_push_data()
3450 mas_split_final_node(mast, mas, height + 1); in mas_push_data()
3463 struct maple_subtree_state mast; in mas_split() local
3497 mast.l = &l_mas; in mas_split()
3498 mast.r = &r_mas; in mas_split()
3499 mast.orig_l = &prev_l_mas; in mas_split()
3500 mast.orig_r = &prev_r_mas; in mas_split()
3501 mast.free = &mat; in mas_split()
3502 mast.bn = b_node; in mas_split()
3506 mas_split_final_node(&mast, mas, height); in mas_split()
3521 if (mas_push_data(mas, height, &mast, true)) in mas_split()
3525 if (mas_push_data(mas, height, &mast, false)) in mas_split()
3529 mast_split_data(&mast, mas, split); in mas_split()
3534 mast.r->max = mas->max; in mas_split()
3535 mast_fill_bnode(&mast, mas, 1); in mas_split()
3536 prev_l_mas = *mast.l; in mas_split()
3537 prev_r_mas = *mast.r; in mas_split()
3541 mat_add(mast.free, mas->node); in mas_split()
3543 mas_wmb_replace(mas, mast.free, NULL); in mas_split()
3954 struct maple_subtree_state mast; in mas_wr_spanning_store() local
4036 mast.bn = &b_node; in mas_wr_spanning_store()
4037 mast.orig_l = &l_mas; in mas_wr_spanning_store()
4038 mast.orig_r = &r_mas; in mas_wr_spanning_store()
4040 return mas_spanning_rebalance(mas, &mast, height + 1); in mas_wr_spanning_store()