linux-master/lib/maple_tree.c

18  * In regular B-Tree terms, pivots are called keys.  The term pivot is used to
45  * a slot, but the last offset has an implied pivot from the node above (or
124 	unsigned long pivot[MAPLE_BIG_NODE_SLOTS - 1];
656 		return node->ma64.pivot;
659 		return node->mr64.pivot;
688  * mas_safe_pivot() - get the pivot at @piv or mas->max.
691  * @piv: The pivot to fetch
694  * Return: The pivot at @piv within the limit of the @pivots array, @mas->max
711  * @offset: The offset into the pivot array
725  * mte_set_pivot() - Set a pivot to a value in an encoded maple node.
727  * @piv: The pivot offset
728  * @val: The value of the pivot
740 		node->mr64.pivot[piv] = val;
743 		node->ma64.pivot[piv] = val;
896 		pivots = mn->mr64.pivot;
1500 	 * Check the first implied pivot optimizes the loop below and slot 1 may
1514 	 * Check end implied pivot which can only be a gap on the right most
1790 	memmove(b_node->pivot + shift, b_node->pivot, size);
1899 		       ((bn->pivot[split] - min) < slot_count - 1) &&
1937 		b_node->pivot[j] = pivots[i++];
1945 		b_node->pivot[j] = pivots[i];
1946 		if (unlikely(!b_node->pivot[j]))
1949 		if (unlikely(mas->max == b_node->pivot[j]))
1954 		b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt);
2008 		pivots[j++] = b_node->pivot[i++];
2009 	} while (i <= mab_end && likely(b_node->pivot[i]));
2015 		mas->max = b_node->pivot[i - 1];
2083 		piv = b_node->pivot[b_end - 1];
2092 		b_node->pivot[b_end++] = mas->index - 1;
2098 	b_node->pivot[b_end] = mas->last;
2117 		b_node->pivot[b_end] = piv;
2397  * @mas - the maple state to get the pivot (mas->max)
2410 	b_node->pivot[b_node->b_end++] = mas->max;
2683 		mast->m->min = mast->bn->pivot[split] + 1;
2690 		mast->r->min = mast->bn->pivot[split] + 1;
2716 	if (mast->bn->pivot[mast->bn->b_end - 1] >= mast->orig_r->max)
3177 	memset(mast->bn->pivot, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->pivot));
3194 	if (mast->bn->pivot[mast->bn->b_end - 1] == mas->max)
3221 	mast->l->max = mast->bn->pivot[split];
3530  * @piv: The pivot value being written
3546 	/* Contained in this pivot, fast path */
4250 	 * single pivot needs to be inserted (as well as writing the entry).  If
4456 	unsigned long pivot;
4470 		pivot = mas_safe_min(mas, pivots, mas->offset);
4475 		if (pivot <= min)
4531  * @max: The maximum pivot value to check.
4630 	unsigned long pivot;
4645 			pivot = pivots[mas->offset];
4647 			pivot = mas->max;
4652 		if (pivot >= max) { /* Was at the limit, next will extend beyond */
4832 	unsigned long pivot, min, gap = 0;
4852 		pivot = mas_safe_pivot(mas, pivots, offset, type);
4855 		if (mas->index > pivot)
4861 			gap = min(pivot, mas->last) - max(mas->index, min) + 1;
4870 			if (mas->index <= pivot) {
4873 				mas->max = pivot;
4879 		min = pivot + 1;
4880 		if (mas->last <= pivot) {
7142 			pr_cont("%p %lX ", node->slot[i], node->pivot[i]);
7145 			pr_cont("%p %lu ", node->slot[i], node->pivot[i]);
7153 			last = node->pivot[i];
7170 				pr_err("node %p last (%lx) > max (%lx) at pivot %d!\n",
7174 				pr_err("node %p last (%lu) > max (%lu) at pivot %d!\n",
7205 			pr_cont("%p %lX ", node->slot[i], node->pivot[i]);
7208 			pr_cont("%p %lu ", node->slot[i], node->pivot[i]);
7216 			last = node->pivot[i];
7231 			pr_err("node %p last (%lu) > max (%lu) at pivot %d!\n",
7475 			pr_err("Missing node limit pivot at %p[%u]",