Lines Matching refs:pivots
13 * pivots. In the case of dense nodes, the pivots are implied by the position
16 * In regular B-Tree terms, pivots are called keys. The term pivot is used to
23 * The following illustrates the layout of a range64 nodes slots and pivots.
638 * ma_pivots() - Get a pointer to the maple node pivots.
644 * Return: A pointer to the maple node pivots
714 * @pivots: The pointer to the maple node pivots
718 * Return: The pivot at @piv within the limit of the @pivots array, @mas->max
722 mas_safe_pivot(const struct ma_state *mas, unsigned long *pivots,
728 return pivots[piv];
734 * @pivots: The pointer to the maple node pivots
740 mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset)
743 return pivots[offset - 1] + 1;
914 unsigned long *pivots;
920 pivots = mn->mr64.pivot;
921 if (unlikely(pivots[MAPLE_RANGE64_SLOTS - 2])) {
1035 unsigned long *pivots;
1041 pivots = ma_pivots(node, type);
1045 mas->min = pivots[mas->offset - 1] + 1;
1046 mas->max = mas_safe_pivot(mas, pivots, mas->offset, type);
1086 unsigned long *pivots;
1129 pivots = ma_pivots(a_node, a_type);
1136 min = pivots[a_slot - 1] + 1;
1141 max = pivots[a_slot];
1422 * @pivots: The array of pivots in the node
1430 unsigned long *pivots,
1435 if (!pivots)
1442 if (likely(!pivots[offset]))
1445 if (likely(pivots[offset] == max))
1465 unsigned long *pivots;
1472 pivots = ma_pivots(node, type);
1477 if (likely(!pivots[offset]))
1480 if (likely(pivots[offset] == mas->max))
1497 unsigned long *pivots;
1526 pivots = ma_pivots(mn, mt);
1528 max_gap = pivots[0] - mas->min + 1;
1535 max_piv = ma_data_end(mn, mt, pivots, mas->max) - 1;
1541 gap = ULONG_MAX - pivots[max_piv];
1551 pstart = pivots[i - 1];
1552 gap = pivots[i] - pstart;
1710 unsigned long *pivots = ma_pivots(node, type);
1714 offset = ma_data_end(node, type, pivots, mas->max);
1775 unsigned long *pivots;
1783 pivots = ma_pivots(node, mt);
1784 end = ma_data_end(node, mt, pivots, mas->max);
1949 unsigned long *pivots, *gaps;
1955 pivots = ma_pivots(node, mt);
1957 b_node->pivot[j] = pivots[i++];
1965 b_node->pivot[j] = pivots[i];
1974 b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt);
1992 * @pivots: pointer to the maple node pivots
2001 struct maple_node *node, unsigned long *pivots,
2008 if (pivots[end] && pivots[end] < mas->max)
2030 unsigned long *pivots = ma_pivots(node, mt);
2037 if (!pivots[mt_pivots[mt] - 1])
2042 pivots[j++] = b_node->pivot[i++];
2067 mas_leaf_set_meta(mas, node, pivots, mt, end);
2139 piv = mas_safe_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type);
2247 wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type);
2249 wr_mas->pivots, mas->max);
2252 while (offset < count && mas->index > wr_mas->pivots[offset])
2255 wr_mas->r_max = offset < count ? wr_mas->pivots[offset] : mas->max;
2256 wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, offset);
2785 unsigned long *pivots;
2803 pivots = ma_pivots(node, type);
2804 end = ma_data_end(node, type, pivots, max);
2808 if (pivots[offset] >= mas->index) {
2811 max = pivots[offset];
2817 } while ((offset < end) && (pivots[offset] < mas->index));
2820 min = pivots[offset - 1] + 1;
2822 if (likely(offset < end && pivots[offset]))
2823 max = pivots[offset];
3455 memset(wr_mas->pivots + bn->b_end, 0, sizeof(void *) * clear);
3512 unsigned long *pivots;
3520 pivots = ma_pivots(node, type);
3531 pivots[slot++] = mas->index - 1;
3536 pivots[slot] = mas->last;
3538 pivots[++slot] = ULONG_MAX;
3681 l_mas->index = l_wr_mas->pivots[l_slot - 2] + 1;
3695 r_mas->last = mas_safe_pivot(r_mas, r_wr_mas->pivots,
3726 unsigned long *pivots;
3741 pivots = ma_pivots(node, type);
3742 end = ma_data_end(node, type, pivots, max);
3746 if (pivots[offset] >= mas->index) {
3747 max = pivots[offset];
3782 unsigned long *pivots;
3797 pivots = ma_pivots(node, type);
3802 pivots[0] = mas->last;
3957 memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset);
3983 memcpy(dst_pivots + dst_offset, wr_mas->pivots + offset_end,
4024 wr_mas->pivots[offset] = mas->last;
4028 wr_mas->pivots[offset] = mas->index - 1;
4038 wr_mas->pivots[offset] = mas->index - 1;
4039 wr_mas->pivots[offset + 1] = mas->last;
4072 mas->last = wr_mas->pivots[wr_mas->offset_end];
4086 mas_safe_min(mas, wr_mas->pivots, mas->offset);
4087 wr_mas->r_max = wr_mas->pivots[mas->offset];
4095 (wr_mas->mas->last > wr_mas->pivots[wr_mas->offset_end]))
4099 wr_mas->end_piv = wr_mas->pivots[wr_mas->offset_end];
4152 wr_mas->pivots[new_end] = wr_mas->pivots[end];
4161 wr_mas->pivots[end] = mas->index - 1;
4166 wr_mas->pivots[end] = mas->last;
4172 wr_mas->pivots[end + 1] = mas->last;
4174 wr_mas->pivots[end] = mas->index - 1;
4286 * Inserting a new range inserts either 0, 1, or 2 pivots within the
4292 * then two pivots need to be inserted: the start - 1, and the end. As
4365 unsigned long *pivots;
4400 pivots = ma_pivots(node, mt);
4401 offset = ma_data_end(node, mt, pivots, max);
4408 pivots = ma_pivots(node, mt);
4413 mas->min = pivots[offset - 1] + 1;
4446 unsigned long *pivots;
4453 pivots = ma_pivots(node, type);
4458 pivot = mas_safe_min(mas, pivots, mas->offset);
4471 mas->index = mas_safe_min(mas, pivots, mas->offset);
4484 pivots = ma_pivots(node, type);
4485 mas->index = pivots[mas->offset - 1] + 1;
4523 unsigned long *pivots;
4546 pivots = ma_pivots(node, mt);
4547 node_end = ma_data_end(node, mt, pivots, mas->max);
4574 pivots = ma_pivots(node, mt);
4576 mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt);
4607 unsigned long *pivots;
4618 pivots = ma_pivots(node, type);
4619 data_end = ma_data_end(node, type, pivots, mas->max);
4625 pivot = pivots[mas->offset];
4637 mas->index = pivots[mas->offset] + 1;
4641 mas->last = pivots[mas->offset];
4660 pivots = ma_pivots(node, type);
4661 mas->last = pivots[0];
4726 unsigned long *pivots, *gaps;
4741 pivots = ma_pivots(node, type);
4745 min = mas_safe_min(mas, pivots, offset);
4748 min = mas_safe_min(mas, pivots, --offset);
4750 max = mas_safe_pivot(mas, pivots, offset, type);
4768 max = pivots[offset];
4769 min = mas_safe_min(mas, pivots, offset);
4779 min = mas_safe_min(mas, pivots, offset);
4813 unsigned long *gaps, *pivots;
4824 pivots = ma_pivots(node, type);
4828 min = mas_safe_min(mas, pivots, offset);
4829 data_end = ma_data_end(node, type, pivots, mas->max);
4831 pivot = mas_safe_pivot(mas, pivots, offset, type);
5027 unsigned long *pivots;
5060 pivots = ma_pivots(mas_mn(mas), mt);
5061 min = mas_safe_min(mas, pivots, offset);
6932 unsigned long *pivots = ma_pivots(node, mt);
6950 p_end = mas_safe_pivot(mas, pivots, i, mt);
7053 unsigned long *pivots = ma_pivots(mte_to_node(mas->node), type);
7083 if (i < mt_pivots[type] && pivots[i] == mas->max)
7089 * Validate all pivots are within mas->min and mas->max, check metadata ends
7090 * where the maximum ends and ensure there is no slots or pivots set outside of
7099 unsigned long *pivots = ma_pivots(mas_mn(mas), type);
7104 piv = mas_safe_pivot(mas, pivots, i, type);
7149 unsigned long piv = pivots[i];
7200 * 1. The limits (pivots are within mas->min to mas->max)