linux-master/lib/maple_tree.c

149 	struct maple_big_node *bn;
1847  * @bn: The maple_big_node with the data
1853 	 struct maple_big_node *bn, unsigned char *mid_split, unsigned long min)
1855 	unsigned char b_end = bn->b_end;
1857 	unsigned char slot_min, slot_count = mt_slots[bn->type];
1867 		split = b_end - mt_min_slots[bn->type];
1869 		if (!ma_is_leaf(bn->type))
1873 		if (!bn->slot[split])
1886 	if (unlikely(mab_middle_node(bn, split, slot_count))) {
1890 		slot_min = mt_min_slots[bn->type];
1899 		       ((bn->pivot[split] - min) < slot_count - 1) &&
1905 	split = mab_no_null_split(bn, split, slot_count);
1908 		*mid_split = mab_no_null_split(bn, *mid_split, slot_count);
2235 	unsigned char b_end = mast->bn->b_end;
2238 		   mast->bn, b_end);
2250 	unsigned char b_end = mast->bn->b_end;
2252 	mab_shift_right(mast->bn, end);
2253 	mas_mab_cp(mast->orig_l, 0, end - 1, mast->bn, 0);
2256 	mast->bn->b_end = end + b_end;
2264  * Data is copied into the @mast->bn.
2335 	mast->bn->type = wr_mas.type;
2674 	if (split == mast->bn->b_end) {
2679 	mab_mas_cp(mast->bn, 0, split, mast->l, new_lmax);
2682 		mab_mas_cp(mast->bn, 1 + split, mid_split, mast->m, true);
2683 		mast->m->min = mast->bn->pivot[split] + 1;
2689 		mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r, false);
2690 		mast->r->min = mast->bn->pivot[split] + 1;
2706 	mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0);
2716 	if (mast->bn->pivot[mast->bn->b_end - 1] >= mast->orig_r->max)
2720 		   mt_slot_count(mast->orig_r->node), mast->bn,
2721 		   mast->bn->b_end);
2732 	if (mast->bn->b_end > mt_min_slot_count(mast->orig_l->node))
2745 	if (mast->bn->b_end >= mt_slot_count(mast->orig_l->node))
2852 	    unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type]))
2869 		mast->bn->b_end--;
2870 		mast->bn->type = mte_node_type(mast->orig_l->node);
2871 		split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle,
2878 		 * Copy data from next level in the tree to mast->bn from next
2881 		memset(mast->bn, 0, sizeof(struct maple_big_node));
2882 		mast->bn->type = mte_node_type(left);
2891 		l_mas.offset = mast->bn->b_end;
2892 		mab_set_b_end(mast->bn, &l_mas, left);
2893 		mab_set_b_end(mast->bn, &m_mas, middle);
2894 		mab_set_b_end(mast->bn, &r_mas, right);
2906 		/* May be a new root stored in mast->bn */
2920 	mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true);
2945 	return mast->bn->b_end;
2985 	mast.bn = b_node;
2986 	mast.bn->type = mte_node_type(mas->node);
3143 			mast->bn->type = maple_arange_64;
3145 			mast->bn->type = maple_range_64;
3152 	ancestor = mas_new_ma_node(mas, mast->bn);
3158 	mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, mast->l, true);
3159 	mas->offset = mast->bn->b_end - 1;
3175 	memset(mast->bn->gap, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->gap));
3176 	memset(mast->bn->slot, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->slot));
3177 	memset(mast->bn->pivot, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->pivot));
3178 	mast->bn->b_end = 0;
3188 		mas_mab_cp(mas, 0, mast->l->offset - 1, mast->bn, 0);
3190 	split = mast->bn->b_end;
3191 	mab_set_b_end(mast->bn, mast->l, mast->l->node);
3192 	mast->r->offset = mast->bn->b_end;
3193 	mab_set_b_end(mast->bn, mast->r, mast->r->node);
3194 	if (mast->bn->pivot[mast->bn->b_end - 1] == mas->max)
3199 			   mast->bn, mast->bn->b_end);
3201 	mast->bn->b_end--;
3202 	mast->bn->type = mte_node_type(mas->node);
3217 	mab_mas_cp(mast->bn, 0, split, mast->l, true);
3219 	mab_mas_cp(mast->bn, split + 1, mast->bn->b_end, mast->r, false);
3221 	mast->l->max = mast->bn->pivot[split];
3248 	unsigned char slot_total = mast->bn->b_end;
3264 	if (ma_is_leaf(mast->bn->type))
3273 	/* Get the data; Fill mast->bn */
3274 	mast->bn->b_end++;
3276 		mab_shift_right(mast->bn, end + 1);
3277 		mas_mab_cp(&tmp_mas, 0, end, mast->bn, 0);
3278 		mast->bn->b_end = slot_total + 1;
3280 		mas_mab_cp(&tmp_mas, 0, end, mast->bn, mast->bn->b_end);
3283 	/* Configure mast for splitting of mast->bn */
3284 	split = mt_slots[mast->bn->type] - 2;
3296 	split = mab_no_null_split(mast->bn, split, mt_slots[mast->bn->type]);
3353 	mast.bn = b_node;
3401  * @bn: The maple big node
3409 			  struct maple_big_node *bn, unsigned char end)
3415 	if (end > bn->b_end) {
3416 		int clear = mt_slots[wr_mas->type] - bn->b_end;
3418 		memset(wr_mas->slots + bn->b_end, 0, sizeof(void *) * clear--);
3419 		memset(wr_mas->pivots + bn->b_end, 0, sizeof(void *) * clear);
3421 	mab_mas_cp(bn, 0, bn->b_end, wr_mas->mas, false);
3866 	mast.bn = &b_node;