1  // SPDX-License-Identifier: GPL-2.0
2  /*
3   * Range add and subtract
4   */
5  #include <linux/init.h>
6  #include <linux/minmax.h>
7  #include <linux/printk.h>
8  #include <linux/sort.h>
9  #include <linux/string.h>
10  #include <linux/range.h>
11  
add_range(struct range * range,int az,int nr_range,u64 start,u64 end)12  int add_range(struct range *range, int az, int nr_range, u64 start, u64 end)
13  {
14  	if (start >= end)
15  		return nr_range;
16  
17  	/* Out of slots: */
18  	if (nr_range >= az)
19  		return nr_range;
20  
21  	range[nr_range].start = start;
22  	range[nr_range].end = end;
23  
24  	nr_range++;
25  
26  	return nr_range;
27  }
28  
add_range_with_merge(struct range * range,int az,int nr_range,u64 start,u64 end)29  int add_range_with_merge(struct range *range, int az, int nr_range,
30  		     u64 start, u64 end)
31  {
32  	int i;
33  
34  	if (start >= end)
35  		return nr_range;
36  
37  	/* get new start/end: */
38  	for (i = 0; i < nr_range; i++) {
39  		u64 common_start, common_end;
40  
41  		if (!range[i].end)
42  			continue;
43  
44  		common_start = max(range[i].start, start);
45  		common_end = min(range[i].end, end);
46  		if (common_start > common_end)
47  			continue;
48  
49  		/* new start/end, will add it back at last */
50  		start = min(range[i].start, start);
51  		end = max(range[i].end, end);
52  
53  		memmove(&range[i], &range[i + 1],
54  			(nr_range - (i + 1)) * sizeof(range[i]));
55  		range[nr_range - 1].start = 0;
56  		range[nr_range - 1].end   = 0;
57  		nr_range--;
58  		i--;
59  	}
60  
61  	/* Need to add it: */
62  	return add_range(range, az, nr_range, start, end);
63  }
64  
subtract_range(struct range * range,int az,u64 start,u64 end)65  void subtract_range(struct range *range, int az, u64 start, u64 end)
66  {
67  	int i, j;
68  
69  	if (start >= end)
70  		return;
71  
72  	for (j = 0; j < az; j++) {
73  		if (!range[j].end)
74  			continue;
75  
76  		if (start <= range[j].start && end >= range[j].end) {
77  			range[j].start = 0;
78  			range[j].end = 0;
79  			continue;
80  		}
81  
82  		if (start <= range[j].start && end < range[j].end &&
83  		    range[j].start < end) {
84  			range[j].start = end;
85  			continue;
86  		}
87  
88  
89  		if (start > range[j].start && end >= range[j].end &&
90  		    range[j].end > start) {
91  			range[j].end = start;
92  			continue;
93  		}
94  
95  		if (start > range[j].start && end < range[j].end) {
96  			/* Find the new spare: */
97  			for (i = 0; i < az; i++) {
98  				if (range[i].end == 0)
99  					break;
100  			}
101  			if (i < az) {
102  				range[i].end = range[j].end;
103  				range[i].start = end;
104  			} else {
105  				pr_err("%s: run out of slot in ranges\n",
106  					__func__);
107  			}
108  			range[j].end = start;
109  			continue;
110  		}
111  	}
112  }
113  
cmp_range(const void * x1,const void * x2)114  static int cmp_range(const void *x1, const void *x2)
115  {
116  	const struct range *r1 = x1;
117  	const struct range *r2 = x2;
118  
119  	if (r1->start < r2->start)
120  		return -1;
121  	if (r1->start > r2->start)
122  		return 1;
123  	return 0;
124  }
125  
clean_sort_range(struct range * range,int az)126  int clean_sort_range(struct range *range, int az)
127  {
128  	int i, j, k = az - 1, nr_range = az;
129  
130  	for (i = 0; i < k; i++) {
131  		if (range[i].end)
132  			continue;
133  		for (j = k; j > i; j--) {
134  			if (range[j].end) {
135  				k = j;
136  				break;
137  			}
138  		}
139  		if (j == i)
140  			break;
141  		range[i].start = range[k].start;
142  		range[i].end   = range[k].end;
143  		range[k].start = 0;
144  		range[k].end   = 0;
145  		k--;
146  	}
147  	/* count it */
148  	for (i = 0; i < az; i++) {
149  		if (!range[i].end) {
150  			nr_range = i;
151  			break;
152  		}
153  	}
154  
155  	/* sort them */
156  	sort(range, nr_range, sizeof(struct range), cmp_range, NULL);
157  
158  	return nr_range;
159  }
160  
sort_range(struct range * range,int nr_range)161  void sort_range(struct range *range, int nr_range)
162  {
163  	/* sort them */
164  	sort(range, nr_range, sizeof(struct range), cmp_range, NULL);
165  }
166