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