2023 static inline void mast_rebalance_next(struct maple_subtree_state *mast)  in mast_rebalance_next()  argument
2025 	unsigned char b_end = mast->bn->b_end;  in mast_rebalance_next()
2027 	mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node),  in mast_rebalance_next()
2028 		   mast->bn, b_end);  in mast_rebalance_next()
2029 	mast->orig_r->last = mast->orig_r->max;  in mast_rebalance_next()
2036 static inline void mast_rebalance_prev(struct maple_subtree_state *mast)  in mast_rebalance_prev()  argument
2038 	unsigned char end = mas_data_end(mast->orig_l) + 1;  in mast_rebalance_prev()
2039 	unsigned char b_end = mast->bn->b_end;  in mast_rebalance_prev()
2041 	mab_shift_right(mast->bn, end);  in mast_rebalance_prev()
2042 	mas_mab_cp(mast->orig_l, 0, end - 1, mast->bn, 0);  in mast_rebalance_prev()
2043 	mast->l->min = mast->orig_l->min;  in mast_rebalance_prev()
2044 	mast->orig_l->index = mast->orig_l->min;  in mast_rebalance_prev()
2045 	mast->bn->b_end = end + b_end;  in mast_rebalance_prev()
2046 	mast->l->offset += end;  in mast_rebalance_prev()
2057 bool mast_spanning_rebalance(struct maple_subtree_state *mast)  in mast_spanning_rebalance()  argument
2059 	struct ma_state r_tmp = *mast->orig_r;  in mast_spanning_rebalance()
2060 	struct ma_state l_tmp = *mast->orig_l;  in mast_spanning_rebalance()
2064 		mas_ascend(mast->orig_r);  in mast_spanning_rebalance()
2065 		mas_ascend(mast->orig_l);  in mast_spanning_rebalance()
2067 		if (mast->orig_r->offset < mas_data_end(mast->orig_r)) {  in mast_spanning_rebalance()
2068 			mast->orig_r->offset++;  in mast_spanning_rebalance()
2070 				mas_descend(mast->orig_r);  in mast_spanning_rebalance()
2071 				mast->orig_r->offset = 0;  in mast_spanning_rebalance()
2074 			mast_rebalance_next(mast);  in mast_spanning_rebalance()
2075 			*mast->orig_l = l_tmp;  in mast_spanning_rebalance()
2077 		} else if (mast->orig_l->offset != 0) {  in mast_spanning_rebalance()
2078 			mast->orig_l->offset--;  in mast_spanning_rebalance()
2080 				mas_descend(mast->orig_l);  in mast_spanning_rebalance()
2081 				mast->orig_l->offset =  in mast_spanning_rebalance()
2082 					mas_data_end(mast->orig_l);  in mast_spanning_rebalance()
2085 			mast_rebalance_prev(mast);  in mast_spanning_rebalance()
2086 			*mast->orig_r = r_tmp;  in mast_spanning_rebalance()
2089 	} while (!mte_is_root(mast->orig_r->node));  in mast_spanning_rebalance()
2091 	*mast->orig_r = r_tmp;  in mast_spanning_rebalance()
2092 	*mast->orig_l = l_tmp;  in mast_spanning_rebalance()
2103 static inline void mast_ascend(struct maple_subtree_state *mast)  in mast_ascend()  argument
2105 	MA_WR_STATE(wr_mas, mast->orig_r,  NULL);  in mast_ascend()
2106 	mas_ascend(mast->orig_l);  in mast_ascend()
2107 	mas_ascend(mast->orig_r);  in mast_ascend()
2109 	mast->orig_r->offset = 0;  in mast_ascend()
2110 	mast->orig_r->index = mast->r->max;  in mast_ascend()
2112 	if (mast->orig_r->last < mast->orig_r->index)  in mast_ascend()
2113 		mast->orig_r->last = mast->orig_r->index;  in mast_ascend()
2115 	wr_mas.type = mte_node_type(mast->orig_r->node);  in mast_ascend()
2118 	mast->orig_l->offset = 0;  in mast_ascend()
2119 	mast->orig_l->index = mast->l->min;  in mast_ascend()
2120 	wr_mas.mas = mast->orig_l;  in mast_ascend()
2121 	wr_mas.type = mte_node_type(mast->orig_l->node);  in mast_ascend()
2124 	mast->bn->type = wr_mas.type;  in mast_ascend()
2263 static inline void mast_set_split_parents(struct maple_subtree_state *mast,  in mast_set_split_parents()  argument
2274 	if (mas_is_none(mast->l))  in mast_set_split_parents()
2280 	slot = mast->l->offset;  in mast_set_split_parents()
2283 	mas_set_split_parent(mast->l, l, r, &slot, split);  in mast_set_split_parents()
2286 	mas_set_split_parent(mast->m, l, r, &slot, split);  in mast_set_split_parents()
2289 	mas_set_split_parent(mast->r, l, r, &slot, split);  in mast_set_split_parents()
2450 static inline void mast_cp_to_nodes(struct maple_subtree_state *mast,  in mast_cp_to_nodes()  argument
2456 	mas_node_or_none(mast->l, left);  in mast_cp_to_nodes()
2457 	mas_node_or_none(mast->m, middle);  in mast_cp_to_nodes()
2458 	mas_node_or_none(mast->r, right);  in mast_cp_to_nodes()
2460 	mast->l->min = mast->orig_l->min;  in mast_cp_to_nodes()
2461 	if (split == mast->bn->b_end) {  in mast_cp_to_nodes()
2462 		mast->l->max = mast->orig_r->max;  in mast_cp_to_nodes()
2466 	mab_mas_cp(mast->bn, 0, split, mast->l, new_lmax);  in mast_cp_to_nodes()
2469 		mab_mas_cp(mast->bn, 1 + split, mid_split, mast->m, true);  in mast_cp_to_nodes()
2470 		mast->m->min = mast->bn->pivot[split] + 1;  in mast_cp_to_nodes()
2474 	mast->r->max = mast->orig_r->max;  in mast_cp_to_nodes()
2476 		mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r, false);  in mast_cp_to_nodes()
2477 		mast->r->min = mast->bn->pivot[split] + 1;  in mast_cp_to_nodes()
2486 static inline void mast_combine_cp_left(struct maple_subtree_state *mast)  in mast_combine_cp_left()  argument
2488 	unsigned char l_slot = mast->orig_l->offset;  in mast_combine_cp_left()
2493 	mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0);  in mast_combine_cp_left()
2501 static inline void mast_combine_cp_right(struct maple_subtree_state *mast)  in mast_combine_cp_right()  argument
2503 	if (mast->bn->pivot[mast->bn->b_end - 1] >= mast->orig_r->max)  in mast_combine_cp_right()
2506 	mas_mab_cp(mast->orig_r, mast->orig_r->offset + 1,  in mast_combine_cp_right()
2507 		   mt_slot_count(mast->orig_r->node), mast->bn,  in mast_combine_cp_right()
2508 		   mast->bn->b_end);  in mast_combine_cp_right()
2509 	mast->orig_r->last = mast->orig_r->max;  in mast_combine_cp_right()
2517 static inline bool mast_sufficient(struct maple_subtree_state *mast)  in mast_sufficient()  argument
2519 	if (mast->bn->b_end > mt_min_slot_count(mast->orig_l->node))  in mast_sufficient()
2530 static inline bool mast_overflow(struct maple_subtree_state *mast)  in mast_overflow()  argument
2532 	if (mast->bn->b_end > mt_slot_count(mast->orig_l->node))  in mast_overflow()
2615 		struct maple_subtree_state *mast, unsigned char count)  in mas_spanning_rebalance()  argument
2631 	mast->l = &l_mas;  in mas_spanning_rebalance()
2632 	mast->m = &m_mas;  in mas_spanning_rebalance()
2633 	mast->r = &r_mas;  in mas_spanning_rebalance()
2637 	if (((mast->orig_l->min != 0) || (mast->orig_r->max != ULONG_MAX)) &&  in mas_spanning_rebalance()
2638 	    unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type]))  in mas_spanning_rebalance()
2639 		mast_spanning_rebalance(mast);  in mas_spanning_rebalance()
2653 		mast->bn->b_end--;  in mas_spanning_rebalance()
2654 		mast->bn->type = mte_node_type(mast->orig_l->node);  in mas_spanning_rebalance()
2655 		split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle,  in mas_spanning_rebalance()
2657 		mast_set_split_parents(mast, left, middle, right, split,  in mas_spanning_rebalance()
2659 		mast_cp_to_nodes(mast, left, middle, right, split, mid_split);  in mas_spanning_rebalance()
2666 		memset(mast->bn, 0, sizeof(struct maple_big_node));  in mas_spanning_rebalance()
2667 		mast->bn->type = mte_node_type(left);  in mas_spanning_rebalance()
2670 		if (mas_is_root_limits(mast->l))  in mas_spanning_rebalance()
2673 		mast_ascend(mast);  in mas_spanning_rebalance()
2674 		mast_combine_cp_left(mast);  in mas_spanning_rebalance()
2675 		l_mas.offset = mast->bn->b_end;  in mas_spanning_rebalance()
2676 		mab_set_b_end(mast->bn, &l_mas, left);  in mas_spanning_rebalance()
2677 		mab_set_b_end(mast->bn, &m_mas, middle);  in mas_spanning_rebalance()
2678 		mab_set_b_end(mast->bn, &r_mas, right);  in mas_spanning_rebalance()
2681 		mast_combine_cp_right(mast);  in mas_spanning_rebalance()
2682 		mast->orig_l->last = mast->orig_l->max;  in mas_spanning_rebalance()
2684 		if (mast_sufficient(mast)) {  in mas_spanning_rebalance()
2685 			if (mast_overflow(mast))  in mas_spanning_rebalance()
2688 			if (mast->orig_l->node == mast->orig_r->node) {  in mas_spanning_rebalance()
2693 				slot = mast->l->offset;  in mas_spanning_rebalance()
2701 		if (mas_is_root_limits(mast->orig_l))  in mas_spanning_rebalance()
2704 		mast_spanning_rebalance(mast);  in mas_spanning_rebalance()
2712 				mte_node_type(mast->orig_l->node));  in mas_spanning_rebalance()
2714 	mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true);  in mas_spanning_rebalance()
2723 	if (mas_is_root_limits(mast->l)) {  in mas_spanning_rebalance()
2725 		mas_mn(mast->l)->parent = ma_parent_ptr(mas_tree_parent(mas));  in mas_spanning_rebalance()
2726 		while (!mte_is_root(mast->orig_l->node))  in mas_spanning_rebalance()
2727 			mast_ascend(mast);  in mas_spanning_rebalance()
2729 		mas_mn(&l_mas)->parent = mas_mn(mast->orig_l)->parent;  in mas_spanning_rebalance()
2732 	old_enode = mast->orig_l->node;  in mas_spanning_rebalance()
2755 	struct maple_subtree_state mast;  in mas_rebalance()  local
2773 	mast.orig_l = &l_mas;  in mas_rebalance()
2774 	mast.orig_r = &r_mas;  in mas_rebalance()
2775 	mast.bn = b_node;  in mas_rebalance()
2776 	mast.bn->type = mte_node_type(mas->node);  in mas_rebalance()
2793 	return mas_spanning_rebalance(mas, &mast, empty_count);  in mas_rebalance()
2801 static inline void mas_split_final_node(struct maple_subtree_state *mast,  in mas_split_final_node()  argument
2808 			mast->bn->type = maple_arange_64;  in mas_split_final_node()
2810 			mast->bn->type = maple_range_64;  in mas_split_final_node()
2816 	ancestor = mas_new_ma_node(mas, mast->bn);  in mas_split_final_node()
2817 	mas_set_parent(mas, mast->l->node, ancestor, mast->l->offset);  in mas_split_final_node()
2818 	mas_set_parent(mas, mast->r->node, ancestor, mast->r->offset);  in mas_split_final_node()
2821 	mast->l->node = ancestor;  in mas_split_final_node()
2822 	mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, mast->l, true);  in mas_split_final_node()
2823 	mas->offset = mast->bn->b_end - 1;  in mas_split_final_node()
2832 static inline void mast_fill_bnode(struct maple_subtree_state *mast,  in mast_fill_bnode()  argument
2839 	memset(mast->bn, 0, sizeof(struct maple_big_node));  in mast_fill_bnode()
2848 	if (cp && mast->l->offset)  in mast_fill_bnode()
2849 		mas_mab_cp(mas, 0, mast->l->offset - 1, mast->bn, 0);  in mast_fill_bnode()
2851 	split = mast->bn->b_end;  in mast_fill_bnode()
2852 	mab_set_b_end(mast->bn, mast->l, mast->l->node);  in mast_fill_bnode()
2853 	mast->r->offset = mast->bn->b_end;  in mast_fill_bnode()
2854 	mab_set_b_end(mast->bn, mast->r, mast->r->node);  in mast_fill_bnode()
2855 	if (mast->bn->pivot[mast->bn->b_end - 1] == mas->max)  in mast_fill_bnode()
2860 			   mast->bn, mast->bn->b_end);  in mast_fill_bnode()
2862 	mast->bn->b_end--;  in mast_fill_bnode()
2863 	mast->bn->type = mte_node_type(mas->node);  in mast_fill_bnode()
2873 static inline void mast_split_data(struct maple_subtree_state *mast,  in mast_split_data()  argument
2878 	mab_mas_cp(mast->bn, 0, split, mast->l, true);  in mast_split_data()
2879 	mte_set_pivot(mast->r->node, 0, mast->r->max);  in mast_split_data()
2880 	mab_mas_cp(mast->bn, split + 1, mast->bn->b_end, mast->r, false);  in mast_split_data()
2881 	mast->l->offset = mte_parent_slot(mas->node);  in mast_split_data()
2882 	mast->l->max = mast->bn->pivot[split];  in mast_split_data()
2883 	mast->r->min = mast->l->max + 1;  in mast_split_data()
2887 	p_slot = mast->orig_l->offset;  in mast_split_data()
2888 	mas_set_split_parent(mast->orig_l, mast->l->node, mast->r->node,  in mast_split_data()
2890 	mas_set_split_parent(mast->orig_r, mast->l->node, mast->r->node,  in mast_split_data()
2906 				struct maple_subtree_state *mast, bool left)  in mas_push_data()  argument
2908 	unsigned char slot_total = mast->bn->b_end;  in mas_push_data()
2913 	tmp_mas.depth = mast->l->depth;  in mas_push_data()
2924 	if (ma_is_leaf(mast->bn->type))  in mas_push_data()
2934 	mast->bn->b_end++;  in mas_push_data()
2936 		mab_shift_right(mast->bn, end + 1);  in mas_push_data()
2937 		mas_mab_cp(&tmp_mas, 0, end, mast->bn, 0);  in mas_push_data()
2938 		mast->bn->b_end = slot_total + 1;  in mas_push_data()
2940 		mas_mab_cp(&tmp_mas, 0, end, mast->bn, mast->bn->b_end);  in mas_push_data()
2944 	split = mt_slots[mast->bn->type] - 2;  in mas_push_data()
2949 		tmp_mas.node = mast->l->node;  in mas_push_data()
2950 		*mast->l = tmp_mas;  in mas_push_data()
2952 		tmp_mas.node = mast->r->node;  in mas_push_data()
2953 		*mast->r = tmp_mas;  in mas_push_data()
2956 	split = mab_no_null_split(mast->bn, split, mt_slots[mast->bn->type]);  in mas_push_data()
2959 		mast->orig_l->offset += end + 1;  in mas_push_data()
2961 	mast_split_data(mast, mas, split);  in mas_push_data()
2962 	mast_fill_bnode(mast, mas, 2);  in mas_push_data()
2963 	mas_split_final_node(mast, mas);  in mas_push_data()
2974 	struct maple_subtree_state mast;  in mas_split()  local
3004 	mast.l = &l_mas;  in mas_split()
3005 	mast.r = &r_mas;  in mas_split()
3006 	mast.orig_l = &prev_l_mas;  in mas_split()
3007 	mast.orig_r = &prev_r_mas;  in mas_split()
3008 	mast.bn = b_node;  in mas_split()
3012 			mas_split_final_node(&mast, mas);  in mas_split()
3027 		if (mas_push_data(mas, &mast, true)) {  in mas_split()
3032 		if (mas_push_data(mas, &mast, false)) {  in mas_split()
3038 		mast_split_data(&mast, mas, split);  in mas_split()
3043 		mast.r->max = mas->max;  in mas_split()
3044 		mast_fill_bnode(&mast, mas, 1);  in mas_split()
3045 		prev_l_mas = *mast.l;  in mas_split()
3046 		prev_r_mas = *mast.r;  in mas_split()
3397 	struct maple_subtree_state mast;  in mas_wr_spanning_store()  local
3475 	mast.bn = &b_node;  in mas_wr_spanning_store()
3476 	mast.orig_l = &l_mas;  in mas_wr_spanning_store()
3477 	mast.orig_r = &r_mas;  in mas_wr_spanning_store()
3479 	return mas_spanning_rebalance(mas, &mast, height + 1);  in mas_wr_spanning_store()