2230 static inline void mast_rebalance_next(struct maple_subtree_state *mast)  in mast_rebalance_next()  argument
2232 	unsigned char b_end = mast->bn->b_end;  in mast_rebalance_next()
2234 	mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node),  in mast_rebalance_next()
2235 		   mast->bn, b_end);  in mast_rebalance_next()
2236 	mast->orig_r->last = mast->orig_r->max;  in mast_rebalance_next()
2243 static inline void mast_rebalance_prev(struct maple_subtree_state *mast)  in mast_rebalance_prev()  argument
2245 	unsigned char end = mas_data_end(mast->orig_l) + 1;  in mast_rebalance_prev()
2246 	unsigned char b_end = mast->bn->b_end;  in mast_rebalance_prev()
2248 	mab_shift_right(mast->bn, end);  in mast_rebalance_prev()
2249 	mas_mab_cp(mast->orig_l, 0, end - 1, mast->bn, 0);  in mast_rebalance_prev()
2250 	mast->l->min = mast->orig_l->min;  in mast_rebalance_prev()
2251 	mast->orig_l->index = mast->orig_l->min;  in mast_rebalance_prev()
2252 	mast->bn->b_end = end + b_end;  in mast_rebalance_prev()
2253 	mast->l->offset += end;  in mast_rebalance_prev()
2264 bool mast_spanning_rebalance(struct maple_subtree_state *mast)  in mast_spanning_rebalance()  argument
2266 	struct ma_state r_tmp = *mast->orig_r;  in mast_spanning_rebalance()
2267 	struct ma_state l_tmp = *mast->orig_l;  in mast_spanning_rebalance()
2271 		mas_ascend(mast->orig_r);  in mast_spanning_rebalance()
2272 		mas_ascend(mast->orig_l);  in mast_spanning_rebalance()
2274 		if (mast->orig_r->offset < mas_data_end(mast->orig_r)) {  in mast_spanning_rebalance()
2275 			mast->orig_r->offset++;  in mast_spanning_rebalance()
2277 				mas_descend(mast->orig_r);  in mast_spanning_rebalance()
2278 				mast->orig_r->offset = 0;  in mast_spanning_rebalance()
2281 			mast_rebalance_next(mast);  in mast_spanning_rebalance()
2282 			*mast->orig_l = l_tmp;  in mast_spanning_rebalance()
2284 		} else if (mast->orig_l->offset != 0) {  in mast_spanning_rebalance()
2285 			mast->orig_l->offset--;  in mast_spanning_rebalance()
2287 				mas_descend(mast->orig_l);  in mast_spanning_rebalance()
2288 				mast->orig_l->offset =  in mast_spanning_rebalance()
2289 					mas_data_end(mast->orig_l);  in mast_spanning_rebalance()
2292 			mast_rebalance_prev(mast);  in mast_spanning_rebalance()
2293 			*mast->orig_r = r_tmp;  in mast_spanning_rebalance()
2296 	} while (!mte_is_root(mast->orig_r->node));  in mast_spanning_rebalance()
2298 	*mast->orig_r = r_tmp;  in mast_spanning_rebalance()
2299 	*mast->orig_l = l_tmp;  in mast_spanning_rebalance()
2310 static inline void mast_ascend(struct maple_subtree_state *mast)  in mast_ascend()  argument
2312 	MA_WR_STATE(wr_mas, mast->orig_r,  NULL);  in mast_ascend()
2313 	mas_ascend(mast->orig_l);  in mast_ascend()
2314 	mas_ascend(mast->orig_r);  in mast_ascend()
2316 	mast->orig_r->offset = 0;  in mast_ascend()
2317 	mast->orig_r->index = mast->r->max;  in mast_ascend()
2319 	if (mast->orig_r->last < mast->orig_r->index)  in mast_ascend()
2320 		mast->orig_r->last = mast->orig_r->index;  in mast_ascend()
2322 	wr_mas.type = mte_node_type(mast->orig_r->node);  in mast_ascend()
2325 	mast->orig_l->offset = 0;  in mast_ascend()
2326 	mast->orig_l->index = mast->l->min;  in mast_ascend()
2327 	wr_mas.mas = mast->orig_l;  in mast_ascend()
2328 	wr_mas.type = mte_node_type(mast->orig_l->node);  in mast_ascend()
2331 	mast->bn->type = wr_mas.type;  in mast_ascend()
2470 static inline void mast_set_split_parents(struct maple_subtree_state *mast,  in mast_set_split_parents()  argument
2481 	if (mas_is_none(mast->l))  in mast_set_split_parents()
2487 	slot = mast->l->offset;  in mast_set_split_parents()
2490 	mas_set_split_parent(mast->l, l, r, &slot, split);  in mast_set_split_parents()
2493 	mas_set_split_parent(mast->m, l, r, &slot, split);  in mast_set_split_parents()
2496 	mas_set_split_parent(mast->r, l, r, &slot, split);  in mast_set_split_parents()
2658 static inline void mast_cp_to_nodes(struct maple_subtree_state *mast,  in mast_cp_to_nodes()  argument
2664 	mas_node_or_none(mast->l, left);  in mast_cp_to_nodes()
2665 	mas_node_or_none(mast->m, middle);  in mast_cp_to_nodes()
2666 	mas_node_or_none(mast->r, right);  in mast_cp_to_nodes()
2668 	mast->l->min = mast->orig_l->min;  in mast_cp_to_nodes()
2669 	if (split == mast->bn->b_end) {  in mast_cp_to_nodes()
2670 		mast->l->max = mast->orig_r->max;  in mast_cp_to_nodes()
2674 	mab_mas_cp(mast->bn, 0, split, mast->l, new_lmax);  in mast_cp_to_nodes()
2677 		mab_mas_cp(mast->bn, 1 + split, mid_split, mast->m, true);  in mast_cp_to_nodes()
2678 		mast->m->min = mast->bn->pivot[split] + 1;  in mast_cp_to_nodes()
2682 	mast->r->max = mast->orig_r->max;  in mast_cp_to_nodes()
2684 		mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r, false);  in mast_cp_to_nodes()
2685 		mast->r->min = mast->bn->pivot[split] + 1;  in mast_cp_to_nodes()
2694 static inline void mast_combine_cp_left(struct maple_subtree_state *mast)  in mast_combine_cp_left()  argument
2696 	unsigned char l_slot = mast->orig_l->offset;  in mast_combine_cp_left()
2701 	mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0);  in mast_combine_cp_left()
2709 static inline void mast_combine_cp_right(struct maple_subtree_state *mast)  in mast_combine_cp_right()  argument
2711 	if (mast->bn->pivot[mast->bn->b_end - 1] >= mast->orig_r->max)  in mast_combine_cp_right()
2714 	mas_mab_cp(mast->orig_r, mast->orig_r->offset + 1,  in mast_combine_cp_right()
2715 		   mt_slot_count(mast->orig_r->node), mast->bn,  in mast_combine_cp_right()
2716 		   mast->bn->b_end);  in mast_combine_cp_right()
2717 	mast->orig_r->last = mast->orig_r->max;  in mast_combine_cp_right()
2725 static inline bool mast_sufficient(struct maple_subtree_state *mast)  in mast_sufficient()  argument
2727 	if (mast->bn->b_end > mt_min_slot_count(mast->orig_l->node))  in mast_sufficient()
2738 static inline bool mast_overflow(struct maple_subtree_state *mast)  in mast_overflow()  argument
2740 	if (mast->bn->b_end >= mt_slot_count(mast->orig_l->node))  in mast_overflow()
2823 		struct maple_subtree_state *mast, unsigned char count)  in mas_spanning_rebalance()  argument
2838 	mast->l = &l_mas;  in mas_spanning_rebalance()
2839 	mast->m = &m_mas;  in mas_spanning_rebalance()
2840 	mast->r = &r_mas;  in mas_spanning_rebalance()
2844 	if (((mast->orig_l->min != 0) || (mast->orig_r->max != ULONG_MAX)) &&  in mas_spanning_rebalance()
2845 	    unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type]))  in mas_spanning_rebalance()
2846 		mast_spanning_rebalance(mast);  in mas_spanning_rebalance()
2862 		mast->bn->b_end--;  in mas_spanning_rebalance()
2863 		mast->bn->type = mte_node_type(mast->orig_l->node);  in mas_spanning_rebalance()
2864 		split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle,  in mas_spanning_rebalance()
2866 		mast_set_split_parents(mast, left, middle, right, split,  in mas_spanning_rebalance()
2868 		mast_cp_to_nodes(mast, left, middle, right, split, mid_split);  in mas_spanning_rebalance()
2874 		memset(mast->bn, 0, sizeof(struct maple_big_node));  in mas_spanning_rebalance()
2875 		mast->bn->type = mte_node_type(left);  in mas_spanning_rebalance()
2879 		if (mas_is_root_limits(mast->l))  in mas_spanning_rebalance()
2882 		mast_ascend(mast);  in mas_spanning_rebalance()
2883 		mast_combine_cp_left(mast);  in mas_spanning_rebalance()
2884 		l_mas.offset = mast->bn->b_end;  in mas_spanning_rebalance()
2885 		mab_set_b_end(mast->bn, &l_mas, left);  in mas_spanning_rebalance()
2886 		mab_set_b_end(mast->bn, &m_mas, middle);  in mas_spanning_rebalance()
2887 		mab_set_b_end(mast->bn, &r_mas, right);  in mas_spanning_rebalance()
2890 		mast_combine_cp_right(mast);  in mas_spanning_rebalance()
2891 		mast->orig_l->last = mast->orig_l->max;  in mas_spanning_rebalance()
2893 		if (mast_sufficient(mast))  in mas_spanning_rebalance()
2896 		if (mast_overflow(mast))  in mas_spanning_rebalance()
2900 		if (mas_is_root_limits(mast->orig_l))  in mas_spanning_rebalance()
2903 		mast_spanning_rebalance(mast);  in mas_spanning_rebalance()
2911 				mte_node_type(mast->orig_l->node));  in mas_spanning_rebalance()
2913 	mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true);  in mas_spanning_rebalance()
2921 	if (mas_is_root_limits(mast->l)) {  in mas_spanning_rebalance()
2923 		mas_mn(mast->l)->parent = ma_parent_ptr(mas_tree_parent(mas));  in mas_spanning_rebalance()
2924 		while (!mte_is_root(mast->orig_l->node))  in mas_spanning_rebalance()
2925 			mast_ascend(mast);  in mas_spanning_rebalance()
2927 		mas_mn(&l_mas)->parent = mas_mn(mast->orig_l)->parent;  in mas_spanning_rebalance()
2930 	old_enode = mast->orig_l->node;  in mas_spanning_rebalance()
2953 	struct maple_subtree_state mast;  in mas_rebalance()  local
2971 	mast.orig_l = &l_mas;  in mas_rebalance()
2972 	mast.orig_r = &r_mas;  in mas_rebalance()
2973 	mast.bn = b_node;  in mas_rebalance()
2974 	mast.bn->type = mte_node_type(mas->node);  in mas_rebalance()
2991 	return mas_spanning_rebalance(mas, &mast, empty_count);  in mas_rebalance()
3119 static inline void mas_split_final_node(struct maple_subtree_state *mast,  in mas_split_final_node()  argument
3126 			mast->bn->type = maple_arange_64;  in mas_split_final_node()
3128 			mast->bn->type = maple_range_64;  in mas_split_final_node()
3135 	ancestor = mas_new_ma_node(mas, mast->bn);  in mas_split_final_node()
3136 	mas_set_parent(mas, mast->l->node, ancestor, mast->l->offset);  in mas_split_final_node()
3137 	mas_set_parent(mas, mast->r->node, ancestor, mast->r->offset);  in mas_split_final_node()
3140 	mast->l->node = ancestor;  in mas_split_final_node()
3141 	mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, mast->l, true);  in mas_split_final_node()
3142 	mas->offset = mast->bn->b_end - 1;  in mas_split_final_node()
3151 static inline void mast_fill_bnode(struct maple_subtree_state *mast,  in mast_fill_bnode()  argument
3158 	memset(mast->bn, 0, sizeof(struct maple_big_node));  in mast_fill_bnode()
3167 	if (cp && mast->l->offset)  in mast_fill_bnode()
3168 		mas_mab_cp(mas, 0, mast->l->offset - 1, mast->bn, 0);  in mast_fill_bnode()
3170 	split = mast->bn->b_end;  in mast_fill_bnode()
3171 	mab_set_b_end(mast->bn, mast->l, mast->l->node);  in mast_fill_bnode()
3172 	mast->r->offset = mast->bn->b_end;  in mast_fill_bnode()
3173 	mab_set_b_end(mast->bn, mast->r, mast->r->node);  in mast_fill_bnode()
3174 	if (mast->bn->pivot[mast->bn->b_end - 1] == mas->max)  in mast_fill_bnode()
3179 			   mast->bn, mast->bn->b_end);  in mast_fill_bnode()
3181 	mast->bn->b_end--;  in mast_fill_bnode()
3182 	mast->bn->type = mte_node_type(mas->node);  in mast_fill_bnode()
3192 static inline void mast_split_data(struct maple_subtree_state *mast,  in mast_split_data()  argument
3197 	mab_mas_cp(mast->bn, 0, split, mast->l, true);  in mast_split_data()
3198 	mte_set_pivot(mast->r->node, 0, mast->r->max);  in mast_split_data()
3199 	mab_mas_cp(mast->bn, split + 1, mast->bn->b_end, mast->r, false);  in mast_split_data()
3200 	mast->l->offset = mte_parent_slot(mas->node);  in mast_split_data()
3201 	mast->l->max = mast->bn->pivot[split];  in mast_split_data()
3202 	mast->r->min = mast->l->max + 1;  in mast_split_data()
3206 	p_slot = mast->orig_l->offset;  in mast_split_data()
3207 	mas_set_split_parent(mast->orig_l, mast->l->node, mast->r->node,  in mast_split_data()
3209 	mas_set_split_parent(mast->orig_r, mast->l->node, mast->r->node,  in mast_split_data()
3226 				 struct maple_subtree_state *mast, bool left)  in mas_push_data()  argument
3228 	unsigned char slot_total = mast->bn->b_end;  in mas_push_data()
3233 	tmp_mas.depth = mast->l->depth;  in mas_push_data()
3244 	if (ma_is_leaf(mast->bn->type))  in mas_push_data()
3254 	mast->bn->b_end++;  in mas_push_data()
3256 		mab_shift_right(mast->bn, end + 1);  in mas_push_data()
3257 		mas_mab_cp(&tmp_mas, 0, end, mast->bn, 0);  in mas_push_data()
3258 		mast->bn->b_end = slot_total + 1;  in mas_push_data()
3260 		mas_mab_cp(&tmp_mas, 0, end, mast->bn, mast->bn->b_end);  in mas_push_data()
3264 	split = mt_slots[mast->bn->type] - 2;  in mas_push_data()
3269 		tmp_mas.node = mast->l->node;  in mas_push_data()
3270 		*mast->l = tmp_mas;  in mas_push_data()
3272 		tmp_mas.node = mast->r->node;  in mas_push_data()
3273 		*mast->r = tmp_mas;  in mas_push_data()
3276 	split = mab_no_null_split(mast->bn, split, mt_slots[mast->bn->type]);  in mas_push_data()
3279 		mast->orig_l->offset += end + 1;  in mas_push_data()
3281 	mast_split_data(mast, mas, split);  in mas_push_data()
3282 	mast_fill_bnode(mast, mas, 2);  in mas_push_data()
3283 	mas_split_final_node(mast, mas, height + 1);  in mas_push_data()
3294 	struct maple_subtree_state mast;  in mas_split()  local
3324 	mast.l = &l_mas;  in mas_split()
3325 	mast.r = &r_mas;  in mas_split()
3326 	mast.orig_l = &prev_l_mas;  in mas_split()
3327 	mast.orig_r = &prev_r_mas;  in mas_split()
3328 	mast.bn = b_node;  in mas_split()
3332 			mas_split_final_node(&mast, mas, height);  in mas_split()
3347 		if (mas_push_data(mas, height, &mast, true))  in mas_split()
3350 		if (mas_push_data(mas, height, &mast, false))  in mas_split()
3354 		mast_split_data(&mast, mas, split);  in mas_split()
3359 		mast.r->max = mas->max;  in mas_split()
3360 		mast_fill_bnode(&mast, mas, 1);  in mas_split()
3361 		prev_l_mas = *mast.l;  in mas_split()
3362 		prev_r_mas = *mast.r;  in mas_split()
3706 	struct maple_subtree_state mast;  in mas_wr_spanning_store()  local
3784 	mast.bn = &b_node;  in mas_wr_spanning_store()
3785 	mast.orig_l = &l_mas;  in mas_wr_spanning_store()
3786 	mast.orig_r = &r_mas;  in mas_wr_spanning_store()
3788 	return mas_spanning_rebalance(mas, &mast, height + 1);  in mas_wr_spanning_store()