linux-master/lib/maple_tree.c

378 	return !mas->min && mas->max == ULONG_MAX;
721 	return mas->min;
1019 		mas->min = pivots[mas->offset - 1] + 1;
1046  * Sets the @mas->max and @mas->min to the correct values when walking up.  This
1047  * may cause several levels of walking up to find the correct min and max.
1059 	unsigned long min, max;
1085 		mas->min = 0;
1089 	min = 0;
1092 		min = mas->min;
1112 			min = pivots[a_slot - 1] + 1;
1129 	mas->min = min;
1263 		max_req = min(requested, max_req);
1343  * If mas->status == mas_start, then set the min, max and depth to
1357 		mas->min = 0;
1505 		max_gap = pivots[0] - mas->min + 1;
1522 		if (max_gap > pivots[max_piv] - mas->min)
1853 	 struct maple_big_node *bn, unsigned char *mid_split, unsigned long min)
1899 		       ((bn->pivot[split] - min) < slot_count - 1) &&
1943 	piv_end = min(mas_end, mt_pivots[mt]);
2085 		piv = mas->min - 1;
2210 		mas->offset = mas->index = mas->min;
2254 	mast->l->min = mast->orig_l->min;
2255 	mast->orig_l->index = mast->orig_l->min;
2330 	mast->orig_l->index = mast->l->min;
2369 	unsigned char *mid_split, unsigned long min)
2382 		split = mab_calc_split(mas, b_node, mid_split, min);
2607 				if ((tmp_next[n].min >= tmp_next->index) &&
2673 	mast->l->min = mast->orig_l->min;
2683 		mast->m->min = mast->bn->pivot[split] + 1;
2690 		mast->r->min = mast->bn->pivot[split] + 1;
2760 	unsigned long max, min;
2764 	min = mas->min;
2772 		prev_min = min;
2789 		min = pivots[offset - 1] + 1;
2799 	mas->index = min;
2801 	mas->min = prev_min;
2851 	if (((mast->orig_l->min != 0) || (mast->orig_r->max != ULONG_MAX)) &&
2872 					&mid_split, mast->orig_l->min);
2940 	mas->min = l_mas.min;
3000 		l_mas.index = l_mas.last = l_mas.min;
3060 	mas->min = l_mas.max + 1;
3222 	mast->r->min = mast->l->max + 1;
3378 		split = mab_calc_split(mas, b_node, &mid_split, prev_l_mas.min);
3579 	wr_mas->mas->min = wr_mas->r_min;
3649 			l_mas->index = l_mas->min;
4309 	unsigned long min = range_lo;
4312 	range_lo = max(min, *next);
4318 	if (ret < 0 && range_lo > min) {
4319 		ret = mas_empty_area(mas, min, range_hi, 1);
4365  * @min: The lower limit to search
4371 static int mas_prev_node(struct ma_state *mas, unsigned long min)
4381 	if (!mas->min)
4384 	max = mas->min - 1;
4385 	if (max < min)
4425 		mas->min = pivots[offset - 1] + 1;
4452 static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty)
4469 	if (mas->min <= min) {
4475 		if (pivot <= min)
4485 		if (mas->index <= min)
4488 		if (mas_prev_node(mas, min)) {
4513 		if (mas->index <= min) {
4540 	unsigned long min;
4552 	min = mas->max + 1;
4604 	mas->min = min;
4681 		mas->index = mas->min;
4750 	unsigned long max, min;
4758 		mas->offset = (unsigned char)(mas->index - mas->min);
4766 	min = mas_safe_min(mas, pivots, offset);
4768 	while (mas->last < min)
4769 		min = mas_safe_min(mas, pivots, --offset);
4777 			gap = max - min + 1;
4780 			if ((size <= gap) && (size <= mas->last - min + 1))
4790 				min = mas_safe_min(mas, pivots, offset);
4799 		max = min - 1;
4800 		min = mas_safe_min(mas, pivots, offset);
4808 		*gap_min = min;
4809 		*gap_max = min + gap - 1;
4815 	mas->min = min;
4832 	unsigned long pivot, min, gap = 0;
4840 		mas->offset = (unsigned char)(mas->index - mas->min);
4849 	min = mas_safe_min(mas, pivots, offset);
4861 			gap = min(pivot, mas->last) - max(mas->index, min) + 1;
4872 				mas->min = min;
4879 		min = pivot + 1;
5007  * @min: the minimum range
5012 static inline int mas_sparse_area(struct ma_state *mas, unsigned long min,
5015 	if (!unlikely(mas_is_none(mas)) && min == 0) {
5016 		min++;
5018 		 * At this time, min is increased, we need to recheck whether
5021 		if (min > max || max - min + 1 < size)
5027 		mas->index = min;
5028 		mas->last = min + size - 1;
5040  * @min: The lowest value of the range
5044 int mas_empty_area(struct ma_state *mas, unsigned long min,
5052 	if (min > max)
5055 	if (size == 0 || max - min < size - 1)
5067 		return mas_sparse_area(mas, min, max, size, true);
5070 	mas->index = min;
5084 	min = mas_safe_min(mas, pivots, offset);
5085 	if (mas->index < min)
5086 		mas->index = min;
5097  * @min: The lowest value of the range
5101 int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
5106 	if (min > max)
5109 	if (size == 0 || max - min < size - 1)
5123 		return mas_sparse_area(mas, min, max, size, false);
5126 	mas->index = min;
5129 	while (!mas_rev_awalk(mas, size, &min, &max)) {
5811 static bool mas_prev_setup(struct ma_state *mas, unsigned long min, void **entry)
5813 	if (unlikely(mas->index <= min)) {
5829 		/* underflowed before but the min changed */
5875  * @min: The minimum value to check.
5883 void *mas_prev(struct ma_state *mas, unsigned long min)
5887 	if (mas_prev_setup(mas, min, &entry))
5890 	return mas_prev_slot(mas, min, false);
5897  * @min: The minimum value to check.
5906 void *mas_prev_range(struct ma_state *mas, unsigned long min)
5910 	if (mas_prev_setup(mas, min, &entry))
5913 	return mas_prev_slot(mas, min, true);
5921  * @min: The minimum index to check
5929 void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min)
5935 	entry = mas_prev(&mas, min);
6102  * @min: The minimum index
6107 static bool mas_find_rev_setup(struct ma_state *mas, unsigned long min,
6117 		if (unlikely(mas->index <= min)) {
6125 		if (mas->index <= min)
6132 		if (unlikely(mas->index <= min)) {
6140 		if (unlikely(mas->index <= min))
6153 		if (mas->index < min)
6176 	if (mas->index < min)
6188  * mas->index down to %min.  Otherwise find the first non-null entry below
6189  * mas->index down to %min.
6191  * @min: The minimum value to check.
6199 void *mas_find_rev(struct ma_state *mas, unsigned long min)
6203 	if (mas_find_rev_setup(mas, min, &entry))
6207 	return mas_prev_slot(mas, min, false);
6214  * below mas->index down to %min.  Otherwise advance to the previous slot after
6215  * mas->index down to %min.
6217  * @min: The minimum value to check.
6225 void *mas_find_range_rev(struct ma_state *mas, unsigned long min)
6229 	if (mas_find_rev_setup(mas, min, &entry))
6233 	return mas_prev_slot(mas, min, true);
6457 		void *entry, unsigned long size, unsigned long min,
6471 	ret = mas_empty_area(&mas, min, max, size);
6538 		void *entry, unsigned long size, unsigned long min,
6552 	ret = mas_empty_area_rev(&mas, min, max, size);
6749 	new_mas->min = 0;
7079 		p_min = mas->min;
7086 	mas->min = p_min;
7091 		unsigned long min, unsigned long max, unsigned int depth,
7093 static void mt_dump_range(unsigned long min, unsigned long max,
7100 		if (min == max)
7101 			pr_info("%.*s%lx: ", depth * 2, spaces, min);
7103 			pr_info("%.*s%lx-%lx: ", depth * 2, spaces, min, max);
7106 		if (min == max)
7107 			pr_info("%.*s%lu: ", depth * 2, spaces, min);
7109 			pr_info("%.*s%lu-%lu: ", depth * 2, spaces, min, max);
7113 static void mt_dump_entry(void *entry, unsigned long min, unsigned long max,
7116 	mt_dump_range(min, max, depth, format);
7130 		unsigned long min, unsigned long max, unsigned int depth,
7135 	unsigned long first = min;
7183 	unsigned long min, unsigned long max, unsigned int depth,
7188 	unsigned long first = min;
7240 		unsigned long min, unsigned long max, unsigned int depth,
7247 	mt_dump_range(min, max, depth, format);
7255 			if (min + i > max)
7258 					min + i, min + i, depth, format);
7263 		mt_dump_range64(mt, entry, min, max, depth, format);
7266 		mt_dump_arange64(mt, entry, min, max, depth, format);
7297 	unsigned long p_end, p_start = mas->min;
7457  * Validate all pivots are within mas->min and mas->max, check metadata ends
7486 		if (piv < mas->min) {
7488 				piv, mas->min);
7489 			MAS_WARN_ON(mas, piv < mas->min);
7568  * 1. The limits (pivots are within mas->min to mas->max)
7638 	pr_err("     min=%lx max=%lx alloc=%p, depth=%u, flags=%x\n",
7639 	       mas->min, mas->max, mas->alloc, mas->depth, mas->mas_flags);