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