2230  * @mast: The maple subtree state
2233 static inline void mast_rebalance_next(struct maple_subtree_state *mast)  in mast_rebalance_next()  argument
2235 	unsigned char b_end = mast->bn->b_end;  in mast_rebalance_next()
2237 	mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node),  in mast_rebalance_next()
2238 		   mast->bn, b_end);  in mast_rebalance_next()
2239 	mast->orig_r->last = mast->orig_r->max;  in mast_rebalance_next()
2244  * @mast: The maple subtree state
2247 static inline void mast_rebalance_prev(struct maple_subtree_state *mast)  in mast_rebalance_prev()  argument
2249 	unsigned char end = mas_data_end(mast->orig_l) + 1;  in mast_rebalance_prev()
2250 	unsigned char b_end = mast->bn->b_end;  in mast_rebalance_prev()
2252 	mab_shift_right(mast->bn, end);  in mast_rebalance_prev()
2253 	mas_mab_cp(mast->orig_l, 0, end - 1, mast->bn, 0);  in mast_rebalance_prev()
2254 	mast->l->min = mast->orig_l->min;  in mast_rebalance_prev()
2255 	mast->orig_l->index = mast->orig_l->min;  in mast_rebalance_prev()
2256 	mast->bn->b_end = end + b_end;  in mast_rebalance_prev()
2257 	mast->l->offset += end;  in mast_rebalance_prev()
2264  * Data is copied into the @mast->bn.
2265  * @mast: The maple_subtree_state.
2268 bool mast_spanning_rebalance(struct maple_subtree_state *mast)  in mast_spanning_rebalance()  argument
2270 	struct ma_state r_tmp = *mast->orig_r;  in mast_spanning_rebalance()
2271 	struct ma_state l_tmp = *mast->orig_l;  in mast_spanning_rebalance()
2274 	r_tmp = *mast->orig_r;  in mast_spanning_rebalance()
2275 	l_tmp = *mast->orig_l;  in mast_spanning_rebalance()
2277 		mas_ascend(mast->orig_r);  in mast_spanning_rebalance()
2278 		mas_ascend(mast->orig_l);  in mast_spanning_rebalance()
2280 		if (mast->orig_r->offset < mas_data_end(mast->orig_r)) {  in mast_spanning_rebalance()
2281 			mast->orig_r->offset++;  in mast_spanning_rebalance()
2283 				mas_descend(mast->orig_r);  in mast_spanning_rebalance()
2284 				mast->orig_r->offset = 0;  in mast_spanning_rebalance()
2287 			mast_rebalance_next(mast);  in mast_spanning_rebalance()
2288 			*mast->orig_l = l_tmp;  in mast_spanning_rebalance()
2290 		} else if (mast->orig_l->offset != 0) {  in mast_spanning_rebalance()
2291 			mast->orig_l->offset--;  in mast_spanning_rebalance()
2293 				mas_descend(mast->orig_l);  in mast_spanning_rebalance()
2294 				mast->orig_l->offset =  in mast_spanning_rebalance()
2295 					mas_data_end(mast->orig_l);  in mast_spanning_rebalance()
2298 			mast_rebalance_prev(mast);  in mast_spanning_rebalance()
2299 			*mast->orig_r = r_tmp;  in mast_spanning_rebalance()
2302 	} while (!mte_is_root(mast->orig_r->node));  in mast_spanning_rebalance()
2304 	*mast->orig_r = r_tmp;  in mast_spanning_rebalance()
2305 	*mast->orig_l = l_tmp;  in mast_spanning_rebalance()
2311  * @mast: the maple subtree state.
2314  * data already in the new tree (@mast->l and @mast->r).
2316 static inline void mast_ascend(struct maple_subtree_state *mast)  in mast_ascend()  argument
2318 	MA_WR_STATE(wr_mas, mast->orig_r,  NULL);  in mast_ascend()
2319 	mas_ascend(mast->orig_l);  in mast_ascend()
2320 	mas_ascend(mast->orig_r);  in mast_ascend()
2322 	mast->orig_r->offset = 0;  in mast_ascend()
2323 	mast->orig_r->index = mast->r->max;  in mast_ascend()
2325 	if (mast->orig_r->last < mast->orig_r->index)  in mast_ascend()
2326 		mast->orig_r->last = mast->orig_r->index;  in mast_ascend()
2328 	wr_mas.type = mte_node_type(mast->orig_r->node);  in mast_ascend()
2331 	mast->orig_l->offset = 0;  in mast_ascend()
2332 	mast->orig_l->index = mast->l->min;  in mast_ascend()
2333 	wr_mas.mas = mast->orig_l;  in mast_ascend()
2334 	wr_mas.type = mte_node_type(mast->orig_l->node);  in mast_ascend()
2337 	mast->bn->type = wr_mas.type;  in mast_ascend()
2470  * is taken from @mast->l.
2471  * @mast - the maple subtree state
2476 static inline void mast_set_split_parents(struct maple_subtree_state *mast,  in mast_set_split_parents()  argument
2487 	if (mas_is_none(mast->l))  in mast_set_split_parents()
2493 	slot = mast->l->offset;  in mast_set_split_parents()
2496 	mas_set_split_parent(mast->l, l, r, &slot, split);  in mast_set_split_parents()
2499 	mas_set_split_parent(mast->m, l, r, &slot, split);  in mast_set_split_parents()
2502 	mas_set_split_parent(mast->r, l, r, &slot, split);  in mast_set_split_parents()
2658  * @mast: The maple subtree state
2665 static inline void mast_cp_to_nodes(struct maple_subtree_state *mast,  in mast_cp_to_nodes()  argument
2671 	mas_node_or_none(mast->l, left);  in mast_cp_to_nodes()
2672 	mas_node_or_none(mast->m, middle);  in mast_cp_to_nodes()
2673 	mas_node_or_none(mast->r, right);  in mast_cp_to_nodes()
2675 	mast->l->min = mast->orig_l->min;  in mast_cp_to_nodes()
2676 	if (split == mast->bn->b_end) {  in mast_cp_to_nodes()
2677 		mast->l->max = mast->orig_r->max;  in mast_cp_to_nodes()
2681 	mab_mas_cp(mast->bn, 0, split, mast->l, new_lmax);  in mast_cp_to_nodes()
2684 		mab_mas_cp(mast->bn, 1 + split, mid_split, mast->m, true);  in mast_cp_to_nodes()
2685 		mast->m->min = mast->bn->pivot[split] + 1;  in mast_cp_to_nodes()
2689 	mast->r->max = mast->orig_r->max;  in mast_cp_to_nodes()
2691 		mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r, false);  in mast_cp_to_nodes()
2692 		mast->r->min = mast->bn->pivot[split] + 1;  in mast_cp_to_nodes()
2699  * @mast: The maple subtree state
2701 static inline void mast_combine_cp_left(struct maple_subtree_state *mast)  in mast_combine_cp_left()  argument
2703 	unsigned char l_slot = mast->orig_l->offset;  in mast_combine_cp_left()
2708 	mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0);  in mast_combine_cp_left()
2714  * @mast: The maple subtree state
2716 static inline void mast_combine_cp_right(struct maple_subtree_state *mast)  in mast_combine_cp_right()  argument
2718 	if (mast->bn->pivot[mast->bn->b_end - 1] >= mast->orig_r->max)  in mast_combine_cp_right()
2721 	mas_mab_cp(mast->orig_r, mast->orig_r->offset + 1,  in mast_combine_cp_right()
2722 		   mt_slot_count(mast->orig_r->node), mast->bn,  in mast_combine_cp_right()
2723 		   mast->bn->b_end);  in mast_combine_cp_right()
2724 	mast->orig_r->last = mast->orig_r->max;  in mast_combine_cp_right()
2730  * @mast: the maple subtree state
2732 static inline bool mast_sufficient(struct maple_subtree_state *mast)  in mast_sufficient()  argument
2734 	if (mast->bn->b_end > mt_min_slot_count(mast->orig_l->node))  in mast_sufficient()
2743  * @mast: The maple subtree state
2745 static inline bool mast_overflow(struct maple_subtree_state *mast)  in mast_overflow()  argument
2747 	if (mast->bn->b_end >= mt_slot_count(mast->orig_l->node))  in mast_overflow()
2816  * @mast: The maple_subtree_state, keeps track of 4 maple states.
2832 		struct maple_subtree_state *mast, unsigned char count)  in mas_spanning_rebalance()  argument
2847 	mast->l = &l_mas;  in mas_spanning_rebalance()
2848 	mast->m = &m_mas;  in mas_spanning_rebalance()
2849 	mast->r = &r_mas;  in mas_spanning_rebalance()
2853 	if (((mast->orig_l->min != 0) || (mast->orig_r->max != ULONG_MAX)) &&  in mas_spanning_rebalance()
2854 	    unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type]))  in mas_spanning_rebalance()
2855 		mast_spanning_rebalance(mast);  in mas_spanning_rebalance()
2871 		mast->bn->b_end--;  in mas_spanning_rebalance()
2872 		mast->bn->type = mte_node_type(mast->orig_l->node);  in mas_spanning_rebalance()
2873 		split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle,  in mas_spanning_rebalance()
2874 					&mid_split, mast->orig_l->min);  in mas_spanning_rebalance()
2875 		mast_set_split_parents(mast, left, middle, right, split,  in mas_spanning_rebalance()
2877 		mast_cp_to_nodes(mast, left, middle, right, split, mid_split);  in mas_spanning_rebalance()
2880 		 * Copy data from next level in the tree to mast->bn from next  in mas_spanning_rebalance()
2883 		memset(mast->bn, 0, sizeof(struct maple_big_node));  in mas_spanning_rebalance()
2884 		mast->bn->type = mte_node_type(left);  in mas_spanning_rebalance()
2888 		if (mas_is_root_limits(mast->l))  in mas_spanning_rebalance()
2891 		mast_ascend(mast);  in mas_spanning_rebalance()
2892 		mast_combine_cp_left(mast);  in mas_spanning_rebalance()
2893 		l_mas.offset = mast->bn->b_end;  in mas_spanning_rebalance()
2894 		mab_set_b_end(mast->bn, &l_mas, left);  in mas_spanning_rebalance()
2895 		mab_set_b_end(mast->bn, &m_mas, middle);  in mas_spanning_rebalance()
2896 		mab_set_b_end(mast->bn, &r_mas, right);  in mas_spanning_rebalance()
2899 		mast_combine_cp_right(mast);  in mas_spanning_rebalance()
2900 		mast->orig_l->last = mast->orig_l->max;  in mas_spanning_rebalance()
2902 		if (mast_sufficient(mast))  in mas_spanning_rebalance()
2905 		if (mast_overflow(mast))  in mas_spanning_rebalance()
2908 		/* May be a new root stored in mast->bn */  in mas_spanning_rebalance()
2909 		if (mas_is_root_limits(mast->orig_l))  in mas_spanning_rebalance()
2912 		mast_spanning_rebalance(mast);  in mas_spanning_rebalance()
2920 				mte_node_type(mast->orig_l->node));  in mas_spanning_rebalance()
2922 	mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true);  in mas_spanning_rebalance()
2930 	if (mas_is_root_limits(mast->l)) {  in mas_spanning_rebalance()
2932 		mas_mn(mast->l)->parent = ma_parent_ptr(mas_tree_parent(mas));  in mas_spanning_rebalance()
2933 		while (!mte_is_root(mast->orig_l->node))  in mas_spanning_rebalance()
2934 			mast_ascend(mast);  in mas_spanning_rebalance()
2936 		mas_mn(&l_mas)->parent = mas_mn(mast->orig_l)->parent;  in mas_spanning_rebalance()
2939 	old_enode = mast->orig_l->node;  in mas_spanning_rebalance()
2947 	return mast->bn->b_end;  in mas_spanning_rebalance()
2964 	struct maple_subtree_state mast;  in mas_rebalance()  local
2985 	mast.orig_l = &l_mas;  in mas_rebalance()
2986 	mast.orig_r = &r_mas;  in mas_rebalance()
2987 	mast.bn = b_node;  in mas_rebalance()
2988 	mast.bn->type = mte_node_type(mas->node);  in mas_rebalance()
3005 	return mas_spanning_rebalance(mas, &mast, empty_count);  in mas_rebalance()
3134  * @mast: the maple subtree state
3138 static inline void mas_split_final_node(struct maple_subtree_state *mast,  in mas_split_final_node()  argument
3145 			mast->bn->type = maple_arange_64;  in mas_split_final_node()
3147 			mast->bn->type = maple_range_64;  in mas_split_final_node()
3154 	ancestor = mas_new_ma_node(mas, mast->bn);  in mas_split_final_node()
3155 	mas_set_parent(mas, mast->l->node, ancestor, mast->l->offset);  in mas_split_final_node()
3156 	mas_set_parent(mas, mast->r->node, ancestor, mast->r->offset);  in mas_split_final_node()
3159 	mast->l->node = ancestor;  in mas_split_final_node()
3160 	mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, mast->l, true);  in mas_split_final_node()
3161 	mas->offset = mast->bn->b_end - 1;  in mas_split_final_node()
3166  * @mast: The maple subtree state
3170 static inline void mast_fill_bnode(struct maple_subtree_state *mast,  in mast_fill_bnode()  argument
3177 	memset(mast->bn->gap, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->gap));  in mast_fill_bnode()
3178 	memset(mast->bn->slot, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->slot));  in mast_fill_bnode()
3179 	memset(mast->bn->pivot, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->pivot));  in mast_fill_bnode()
3180 	mast->bn->b_end = 0;  in mast_fill_bnode()
3189 	if (cp && mast->l->offset)  in mast_fill_bnode()
3190 		mas_mab_cp(mas, 0, mast->l->offset - 1, mast->bn, 0);  in mast_fill_bnode()
3192 	split = mast->bn->b_end;  in mast_fill_bnode()
3193 	mab_set_b_end(mast->bn, mast->l, mast->l->node);  in mast_fill_bnode()
3194 	mast->r->offset = mast->bn->b_end;  in mast_fill_bnode()
3195 	mab_set_b_end(mast->bn, mast->r, mast->r->node);  in mast_fill_bnode()
3196 	if (mast->bn->pivot[mast->bn->b_end - 1] == mas->max)  in mast_fill_bnode()
3201 			   mast->bn, mast->bn->b_end);  in mast_fill_bnode()
3203 	mast->bn->b_end--;  in mast_fill_bnode()
3204 	mast->bn->type = mte_node_type(mas->node);  in mast_fill_bnode()
3210  * @mast: The maple subtree state
3214 static inline void mast_split_data(struct maple_subtree_state *mast,  in mast_split_data()  argument
3219 	mab_mas_cp(mast->bn, 0, split, mast->l, true);  in mast_split_data()
3220 	mte_set_pivot(mast->r->node, 0, mast->r->max);  in mast_split_data()
3221 	mab_mas_cp(mast->bn, split + 1, mast->bn->b_end, mast->r, false);  in mast_split_data()
3222 	mast->l->offset = mte_parent_slot(mas->node);  in mast_split_data()
3223 	mast->l->max = mast->bn->pivot[split];  in mast_split_data()
3224 	mast->r->min = mast->l->max + 1;  in mast_split_data()
3228 	p_slot = mast->orig_l->offset;  in mast_split_data()
3229 	mas_set_split_parent(mast->orig_l, mast->l->node, mast->r->node,  in mast_split_data()
3231 	mas_set_split_parent(mast->orig_r, mast->l->node, mast->r->node,  in mast_split_data()
3240  * @mast: The maple subtree state
3248 				 struct maple_subtree_state *mast, bool left)  in mas_push_data()  argument
3250 	unsigned char slot_total = mast->bn->b_end;  in mas_push_data()
3255 	tmp_mas.depth = mast->l->depth;  in mas_push_data()
3266 	if (ma_is_leaf(mast->bn->type))  in mas_push_data()
3275 	/* Get the data; Fill mast->bn */  in mas_push_data()
3276 	mast->bn->b_end++;  in mas_push_data()
3278 		mab_shift_right(mast->bn, end + 1);  in mas_push_data()
3279 		mas_mab_cp(&tmp_mas, 0, end, mast->bn, 0);  in mas_push_data()
3280 		mast->bn->b_end = slot_total + 1;  in mas_push_data()
3282 		mas_mab_cp(&tmp_mas, 0, end, mast->bn, mast->bn->b_end);  in mas_push_data()
3285 	/* Configure mast for splitting of mast->bn */  in mas_push_data()
3286 	split = mt_slots[mast->bn->type] - 2;  in mas_push_data()
3290 		/* Start using mast->l for the left side. */  in mas_push_data()
3291 		tmp_mas.node = mast->l->node;  in mas_push_data()
3292 		*mast->l = tmp_mas;  in mas_push_data()
3294 		tmp_mas.node = mast->r->node;  in mas_push_data()
3295 		*mast->r = tmp_mas;  in mas_push_data()
3298 	split = mab_no_null_split(mast->bn, split, mt_slots[mast->bn->type]);  in mas_push_data()
3301 		mast->orig_l->offset += end + 1;  in mas_push_data()
3303 	mast_split_data(mast, mas, split);  in mas_push_data()
3304 	mast_fill_bnode(mast, mas, 2);  in mas_push_data()
3305 	mas_split_final_node(mast, mas, height + 1);  in mas_push_data()
3317 	struct maple_subtree_state mast;  in mas_split()  local
3351 	mast.l = &l_mas;  in mas_split()
3352 	mast.r = &r_mas;  in mas_split()
3353 	mast.orig_l = &prev_l_mas;  in mas_split()
3354 	mast.orig_r = &prev_r_mas;  in mas_split()
3355 	mast.bn = b_node;  in mas_split()
3359 			mas_split_final_node(&mast, mas, height);  in mas_split()
3374 		if (mas_push_data(mas, height, &mast, true))  in mas_split()
3377 		if (mas_push_data(mas, height, &mast, false))  in mas_split()
3381 		mast_split_data(&mast, mas, split);  in mas_split()
3386 		mast.r->max = mas->max;  in mas_split()
3387 		mast_fill_bnode(&mast, mas, 1);  in mas_split()
3388 		prev_l_mas = *mast.l;  in mas_split()
3389 		prev_r_mas = *mast.r;  in mas_split()
3787 	struct maple_subtree_state mast;  in mas_wr_spanning_store()  local
3868 	mast.bn = &b_node;  in mas_wr_spanning_store()
3869 	mast.orig_l = &l_mas;  in mas_wr_spanning_store()
3870 	mast.orig_r = &r_mas;  in mas_wr_spanning_store()
3872 	return mas_spanning_rebalance(mas, &mast, height + 1);  in mas_wr_spanning_store()