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
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    /* Try to merge it with old one: */
36    for (i = 0; i < nr_range; i++) {
37        u64 final_start, final_end;
38        u64 common_start, common_end;
39
40        if (!range[i].end)
41            continue;
42
43        common_start = max(range[i].start, start);
44        common_end = min(range[i].end, end);
45        if (common_start > common_end)
46            continue;
47
48        final_start = min(range[i].start, start);
49        final_end = max(range[i].end, end);
50
51        range[i].start = final_start;
52        range[i].end = final_end;
53        return nr_range;
54    }
55
56    /* Need to add it: */
57    return add_range(range, az, nr_range, start, end);
58}
59
60void subtract_range(struct range *range, int az, u64 start, u64 end)
61{
62    int i, j;
63
64    if (start >= end)
65        return;
66
67    for (j = 0; j < az; j++) {
68        if (!range[j].end)
69            continue;
70
71        if (start <= range[j].start && end >= range[j].end) {
72            range[j].start = 0;
73            range[j].end = 0;
74            continue;
75        }
76
77        if (start <= range[j].start && end < range[j].end &&
78            range[j].start < end) {
79            range[j].start = end;
80            continue;
81        }
82
83
84        if (start > range[j].start && end >= range[j].end &&
85            range[j].end > start) {
86            range[j].end = start;
87            continue;
88        }
89
90        if (start > range[j].start && end < range[j].end) {
91            /* Find the new spare: */
92            for (i = 0; i < az; i++) {
93                if (range[i].end == 0)
94                    break;
95            }
96            if (i < az) {
97                range[i].end = range[j].end;
98                range[i].start = end;
99            } else {
100                printk(KERN_ERR "run of slot in ranges\n");
101            }
102            range[j].end = start;
103            continue;
104        }
105    }
106}
107
108static int cmp_range(const void *x1, const void *x2)
109{
110    const struct range *r1 = x1;
111    const struct range *r2 = x2;
112    s64 start1, start2;
113
114    start1 = r1->start;
115    start2 = r2->start;
116
117    return start1 - start2;
118}
119
120int clean_sort_range(struct range *range, int az)
121{
122    int i, j, k = az - 1, nr_range = az;
123
124    for (i = 0; i < k; i++) {
125        if (range[i].end)
126            continue;
127        for (j = k; j > i; j--) {
128            if (range[j].end) {
129                k = j;
130                break;
131            }
132        }
133        if (j == i)
134            break;
135        range[i].start = range[k].start;
136        range[i].end = range[k].end;
137        range[k].start = 0;
138        range[k].end = 0;
139        k--;
140    }
141    /* count it */
142    for (i = 0; i < az; i++) {
143        if (!range[i].end) {
144            nr_range = i;
145            break;
146        }
147    }
148
149    /* sort them */
150    sort(range, nr_range, sizeof(struct range), cmp_range, NULL);
151
152    return nr_range;
153}
154
155void sort_range(struct range *range, int nr_range)
156{
157    /* sort them */
158    sort(range, nr_range, sizeof(struct range), cmp_range, NULL);
159}
160

Archive Download this file



interactive