Lines Matching refs:split
1820 * @split: the potential split location
1825 static inline bool mab_middle_node(struct maple_big_node *b_node, int split,
1833 if (!b_node->slot[split] && (size >= 2 * slot_count - 1))
1840 * mab_no_null_split() - ensure the split doesn't fall on a NULL
1842 * @split: the suggested split location
1845 * Return: the split location.
1848 unsigned char split, unsigned char slot_count)
1850 if (!b_node->slot[split]) {
1852 * If the split is less than the max slot && the right side will
1853 * still be sufficient, then increment the split on NULL.
1855 if ((split < slot_count - 1) &&
1856 (b_node->b_end - split) > (mt_min_slots[b_node->type]))
1857 split++;
1859 split--;
1861 return split;
1865 * mab_calc_split() - Calculate the split location and if there needs to be two
1868 * @mid_split: The second split, if required. 0 otherwise.
1870 * Return: The first split location. The middle split is set in @mid_split.
1876 int split = b_end / 2; /* Assume equal split. */
1882 * limitation means that the split of a node must be checked for this condition
1887 split = b_end - mt_min_slots[bn->type];
1890 return split;
1893 if (!bn->slot[split])
1894 split--;
1895 return split;
1900 * split scenario. The 3-way split comes about by means of a store of a range
1906 if (unlikely(mab_middle_node(bn, split, slot_count))) {
1907 split = b_end / 3;
1908 *mid_split = split * 2;
1916 * NOTE: mt_min_slots is 1 based, b_end and split are zero.
1918 while ((split < slot_count - 1) &&
1919 ((bn->pivot[split] - min) < slot_count - 1) &&
1920 (b_end - split > slot_min))
1921 split++;
1925 split = mab_no_null_split(bn, split, slot_count);
1930 return split;
2396 * @mid_split: the split location for the middle node
2398 * Return: the split of left.
2405 unsigned char split = 0;
2414 split = b_node->b_end;
2416 split = mab_calc_split(mas, b_node, mid_split, min);
2423 return split;
2449 * of @mas->node to either @left or @right, depending on @slot and @split
2455 * @split - the split location between @left and @right
2460 unsigned char *slot, unsigned char split)
2465 if ((*slot) <= split)
2468 mas_set_parent(mas, mas->node, right, (*slot) - split - 1);
2474 * mte_mid_split_check() - Check if the next node passes the mid-split
2479 * @*split: The split location.
2480 * @mid_split: The middle split.
2486 unsigned char *split,
2497 *split = mid_split;
2506 * @split - the split location.
2512 unsigned char split,
2527 mte_mid_split_check(&l, &r, right, slot, &split, mid_split);
2528 mas_set_split_parent(mast->l, l, r, &slot, split);
2530 mte_mid_split_check(&l, &r, right, slot, &split, mid_split);
2531 mas_set_split_parent(mast->m, l, r, &slot, split);
2533 mte_mid_split_check(&l, &r, right, slot, &split, mid_split);
2534 mas_set_split_parent(mast->r, l, r, &slot, split);
2692 * @split: The location to split between left and (middle ? middle : right)
2693 * @mid_split: The location to split between middle and right.
2697 struct maple_enode *right, unsigned char split, unsigned char mid_split)
2706 if (split == mast->bn->b_end) {
2711 mab_mas_cp(mast->bn, 0, split, mast->l, new_lmax);
2714 mab_mas_cp(mast->bn, 1 + split, mid_split, mast->m, true);
2715 mast->m->min = mast->bn->pivot[split] + 1;
2716 split = mid_split;
2721 mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r, false);
2722 mast->r->min = mast->bn->pivot[split] + 1;
2852 * is hit. First @b_node is split into two entries which are inserted into the
2866 unsigned char split, mid_split;
2905 split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle,
2907 mast_set_split_parents(mast, left, middle, right, split,
2909 mast_cp_to_nodes(mast, left, middle, right, split, mid_split);
3054 unsigned char offset, tmp, split = mt_slots[mt] / 2;
3083 if (!l_slots[split])
3084 split++;
3085 tmp = mas_data_end(&l_mas) - split;
3087 memcpy(slots, l_slots + split + 1, sizeof(void *) * tmp);
3088 memcpy(pivs, l_pivs + split + 1, sizeof(unsigned long) * tmp);
3093 l_mas.max = l_pivs[split];
3112 l_pivs[split]);
3115 tmp = split + 1;
3118 ma_set_meta(left, mt, 0, split);
3133 memcpy(slots, l_slots, sizeof(void *) * split);
3134 memcpy(pivs, l_pivs, sizeof(unsigned long) * split);
3135 ma_set_meta(new_left, mt, 0, split);
3208 unsigned char split;
3225 split = mast->bn->b_end;
3233 mas_mab_cp(mas, split + skip, mt_slot_count(mas->node) - 1,
3245 * @split: The location to split the big node
3248 struct ma_state *mas, unsigned char split)
3252 mab_mas_cp(mast->bn, 0, split, mast->l, true);
3254 mab_mas_cp(mast->bn, split + 1, mast->bn->b_end, mast->r, false);
3256 mast->l->max = mast->bn->pivot[split];
3263 &p_slot, split);
3265 &p_slot, split);
3284 unsigned char end, space, split;
3298 /* -2 instead of -1 to ensure there isn't a triple split */
3319 split = mt_slots[mast->bn->type] - 2;
3329 split = slot_total - split;
3331 split = mab_no_null_split(mast->bn, split, mt_slots[mast->bn->type]);
3332 /* Update parent slot for split calculation. */
3336 mast_split_data(mast, mas, split);
3352 unsigned char mid_split, split = 0;
3357 * Tree splits upwards. Splitting up means that the split operation
3363 * entries, it is impossible to know if a split is required until the
3370 * and right nodes after a split.
3400 * Another way that 'jitter' is avoided is to terminate a split up early if the
3414 split = mab_calc_split(mas, b_node, &mid_split, prev_l_mas.min);
3415 mast_split_data(&mast, mas, split);
3842 * or possibly three nodes (see the 3-way split above). A ``NULL``
3908 /* Combine l_mas and r_mas and split them up evenly again. */
4189 * This is where split, rebalance end up.
5640 /* Add working room for split (2 nodes) + new parents */