Branch data 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 : : s64 start1, start2;
117 : :
118 : 0 : start1 = r1->start;
119 : 0 : start2 = r2->start;
120 : :
121 : 0 : return start1 - start2;
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 : }
|
