linux-master/lib/maple_tree.c

129 			unsigned long gap[MAPLE_BIG_NODE_GAPS];
678 		return node->ma64.gap;
866  * @offset: The offset of the highest sub-gap in this node.
874 	meta->gap = offset;
883  * @offset: The offset of the highest sub-gap in this node.
913 	meta->gap = 0;
931  * ma_meta_gap() - Get the largest gap location of a node from the metadata
936 	return mn->ma64.meta.gap;
940  * ma_set_meta_gap() - Set the largest gap location in a nodes metadata
943  * @offset: The location of the largest gap.
951 	meta->gap = offset;
1025  * mte_set_gap() - Set a maple node gap.
1027  * @gap: The offset of the gap to set
1028  * @val: The gap value
1031 				 unsigned char gap, unsigned long val)
1037 		mte_to_node(mn)->ma64.gap[gap] = val;
1464  * mas_leaf_max_gap() - Returns the largest gap in a leaf node
1467  * Return: The maximum gap in the leaf.
1472 	unsigned long pstart, gap, max_gap;
1484 		gap = 0;
1487 				if (gap > max_gap)
1488 					max_gap = gap;
1489 				gap = 0;
1491 				gap++;
1494 		if (gap > max_gap)
1495 			max_gap = gap;
1501 	 * be skipped if there is a gap in slot 0.
1514 	 * Check end implied pivot which can only be a gap on the right most
1518 		gap = ULONG_MAX - pivots[max_piv];
1519 		if (gap > max_gap)
1520 			max_gap = gap;
1527 		/* data == no gap. */
1532 		gap = pivots[i] - pstart;
1533 		if (gap > max_gap)
1534 			max_gap = gap;
1543  * ma_max_gap() - Get the maximum gap in a maple node (non-leaf)
1547  * @*off: Pointer to store the offset location of the gap.
1551  * Return: The maximum gap value
1573  * mas_max_gap() - find the largest gap in a non-leaf node and set the slot.
1576  * Return: The gap value.
1597  * mas_parent_gap() - Set the parent gap and any gaps above, as needed
1599  * @offset: The gap offset in the parent to set
1600  * @new: The new gap value.
1602  * Set the parent gap then continue to set the gap upwards, using the metadata
1793 		memmove(b_node->gap + shift, b_node->gap, size);
1860 	 * To support gap tracking, all NULL entries are kept together and a node cannot
1963 		memcpy(b_node->gap + mab_start, gaps + mas_start,
2024 			gaps[--j] = b_node->gap[--i];
2091 			b_node->gap[b_end] = mas->index - 1 - piv;
2116 			b_node->gap[b_end] = piv - mas->last + 1;
2409 		b_node->gap[b_node->b_end] = mas_max_gap(mas);
2640  * Updates gap as necessary.
3022 	unsigned long *l_pivs, *pivs, gap;
3116 	gap = mas_leaf_max_gap(mas);
3117 	mte_set_gap(eparent, mte_parent_slot(mas->node), gap);
3118 	gap = mas_leaf_max_gap(&l_mas);
3119 	mte_set_gap(eparent, mte_parent_slot(l_mas.node), gap);
3175 	memset(mast->bn->gap, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->gap));
3977 	bool gap = false;
3979 	gap |= !mt_slot_locked(mas->tree, slots, offset);
3980 	gap |= !mt_slot_locked(mas->tree, slots, offset + 1);
3998 		gap |= !mt_slot_locked(mas->tree, slots, offset + 2);
4009 	 * Only update gap when the new entry is empty or there is an empty
4012 	if (!wr_mas->entry || gap)
4247 	 * tree.  If the insert fits exactly into an existing gap with a value
4251 	 * the new range is within a gap but does not touch any other ranges,
4735  * highest gap address of a given size in a given node and descend.
4749 	unsigned long gap = 0;
4773 		gap = 0;
4775 			gap = gaps[offset];
4777 			gap = max - min + 1;
4779 		if (gap) {
4780 			if ((size <= gap) && (size <= mas->last - min + 1))
4784 				/* Skip the next slot, it cannot be a gap. */
4809 		*gap_max = min + gap - 1;
4832 	unsigned long pivot, min, gap = 0;
4859 			gap = gaps[offset];
4861 			gap = min(pivot, mas->last) - max(mas->index, min) + 1;
4865 		if (gap >= size) {
4977  * mas_awalk() - Allocation walk.  Search from low address to high, for a gap of
4980  * @size: The size of the gap required
4982  * Search between @mas->index and @mas->last for a gap of @size.
4992 	 * no gap found. (return, slot == MAPLE_NODE_SLOTS)
4993 	 * found the gap. (return, slot != MAPLE_NODE_SLOTS)
5005  * searching for a gap in an empty tree.
5009  * @size: The size of the gap
5653 	 * Avoid overflow, assume a gap between each entry and a trailing null.
7195 			pr_cont("%lx ", node->gap[i]);
7198 			pr_cont("%lu ", node->gap[i]);
7201 	pr_cont("| %02X %02X| ", node->meta.end, node->meta.gap);
7288  * Calculate the maximum gap in a node and check if that's what is reported in
7296 	unsigned long gap = 0, max_gap = 0;
7306 				if (gap > max_gap)
7307 					max_gap = gap;
7308 				gap = 0;
7311 			gap++;
7322 				gap = p_end - p_start + 1;
7326 			gap = gaps[i];
7329 			if (gap > p_end - p_start + 1) {
7331 				       mas_mn(mas), i, gap, p_end, p_start,
7333 				MT_BUG_ON(mas->tree, gap > p_end - p_start + 1);
7337 		if (gap > max_gap)
7338 			max_gap = gap;
7350 			pr_err("gap offset %p[%u] is invalid\n", node, offset);
7355 			pr_err("gap %p[%u] is not the largest gap %lu\n",
7362 				pr_err("gap %p[%u] beyond node limit != 0\n",
7376 		pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap);
7569  * 2. The gap is correctly set in the parents