linux-master/lib/maple_tree.c

1800  * @split: the potential split location
1805 static inline bool mab_middle_node(struct maple_big_node *b_node, int split,
1813 	if (!b_node->slot[split] && (size >= 2 * slot_count - 1))
1820  * mab_no_null_split() - ensure the split doesn't fall on a NULL
1822  * @split: the suggested split location
1825  * Return: the split location.
1828 				    unsigned char split, unsigned char slot_count)
1830 	if (!b_node->slot[split]) {
1832 		 * If the split is less than the max slot && the right side will
1833 		 * still be sufficient, then increment the split on NULL.
1835 		if ((split < slot_count - 1) &&
1836 		    (b_node->b_end - split) > (mt_min_slots[b_node->type]))
1837 			split++;
1839 			split--;
1841 	return split;
1845  * mab_calc_split() - Calculate the split location and if there needs to be two
1848  * @mid_split: The second split, if required.  0 otherwise.
1850  * Return: The first split location.  The middle split is set in @mid_split.
1856 	int split = b_end / 2; /* Assume equal split. */
1862 	 * limitation means that the split of a node must be checked for this condition
1867 		split = b_end - mt_min_slots[bn->type];
1870 			return split;
1873 		if (!bn->slot[split])
1874 			split--;
1875 		return split;
1880 	 * split scenario.  The 3-way split comes about by means of a store of a range
1886 	if (unlikely(mab_middle_node(bn, split, slot_count))) {
1887 		split = b_end / 3;
1888 		*mid_split = split * 2;
1896 		 * NOTE: mt_min_slots is 1 based, b_end and split are zero.
1898 		while ((split < slot_count - 1) &&
1899 		       ((bn->pivot[split] - min) < slot_count - 1) &&
1900 		       (b_end - split > slot_min))
1901 			split++;
1905 	split = mab_no_null_split(bn, split, slot_count);
1910 	return split;
2362  * @mid_split: the split location for the middle node
2364  * Return: the split of left.
2371 	unsigned char split = 0;
2380 		split = b_node->b_end;
2382 		split = mab_calc_split(mas, b_node, mid_split, min);
2389 	return split;
2415  * of @mas->node to either @left or @right, depending on @slot and @split
2421  * @split - the split location between @left and @right
2426 					unsigned char *slot, unsigned char split)
2431 	if ((*slot) <= split)
2434 		mas_set_parent(mas, mas->node, right, (*slot) - split - 1);
2440  * mte_mid_split_check() - Check if the next node passes the mid-split
2445  * @*split: The split location.
2446  * @mid_split: The middle split.
2452 				       unsigned char *split,
2463 	*split = mid_split;
2472  * @split - the split location.
2478 					  unsigned char split,
2493 	mte_mid_split_check(&l, &r, right, slot, &split, mid_split);
2494 	mas_set_split_parent(mast->l, l, r, &slot, split);
2496 	mte_mid_split_check(&l, &r, right, slot, &split, mid_split);
2497 	mas_set_split_parent(mast->m, l, r, &slot, split);
2499 	mte_mid_split_check(&l, &r, right, slot, &split, mid_split);
2500 	mas_set_split_parent(mast->r, l, r, &slot, split);
2660  * @split: The location to split between left and (middle ? middle : right)
2661  * @mid_split: The location to split between middle and right.
2665 	struct maple_enode *right, unsigned char split, unsigned char mid_split)
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;
2684 		split = mid_split;
2689 		mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r, false);
2690 		mast->r->min = mast->bn->pivot[split] + 1;
2818  * is hit.  First @b_node is split into two entries which are inserted into the
2832 	unsigned char split, mid_split;
2871 		split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle,
2873 		mast_set_split_parents(mast, left, middle, right, split,
2875 		mast_cp_to_nodes(mast, left, middle, right, split, mid_split);
3020 	unsigned char offset, tmp, split = mt_slots[mt] / 2;
3049 	if (!l_slots[split])
3050 		split++;
3051 	tmp = mas_data_end(&l_mas) - split;
3053 	memcpy(slots, l_slots + split + 1, sizeof(void *) * tmp);
3054 	memcpy(pivs, l_pivs + split + 1, sizeof(unsigned long) * tmp);
3059 	l_mas.max = l_pivs[split];
3078 			      l_pivs[split]);
3081 		tmp = split + 1;
3084 		ma_set_meta(left, mt, 0, split);
3099 	memcpy(slots, l_slots, sizeof(void *) * split);
3100 	memcpy(pivs, l_pivs, sizeof(unsigned long) * split);
3101 	ma_set_meta(new_left, mt, 0, split);
3173 	unsigned char split;
3190 	split = mast->bn->b_end;
3198 		mas_mab_cp(mas, split + skip, mt_slot_count(mas->node) - 1,
3210  * @split: The location to split the big node
3213 	   struct ma_state *mas, unsigned char split)
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];
3228 			     &p_slot, split);
3230 			     &p_slot, split);
3249 	unsigned char end, space, split;
3263 	/* -2 instead of -1 to ensure there isn't a triple split */
3284 	split = mt_slots[mast->bn->type] - 2;
3294 		split = slot_total - split;
3296 	split = mab_no_null_split(mast->bn, split, mt_slots[mast->bn->type]);
3297 	/* Update parent slot for split calculation. */
3301 	mast_split_data(mast, mas, split);
3317 	unsigned char mid_split, split = 0;
3322 	 * Tree splits upwards.  Splitting up means that the split operation
3328 	 * entries, it is impossible to know if a split is required until the
3335 	 * and right nodes after a split.
3365 		 * Another way that 'jitter' is avoided is to terminate a split up early if the
3378 		split = mab_calc_split(mas, b_node, &mid_split, prev_l_mas.min);
3379 		mast_split_data(&mast, mas, split);
3803 	 * or possibly three nodes (see the 3-way split above).  A ``NULL``
3869 	/* Combine l_mas and r_mas and split them up evenly again. */
4149  * This is where split, rebalance end up.
5665 	/* Add working room for split (2 nodes) + new parents */