Root/kernel/range.c

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

Archive Download this file



interactive