71e0021281fe52304f0c52f824eb1fc75c1f5e5f
[linux-2.6.git] / kernel / range.c
1 /*
2  * Range add and subtract
3  */
4 #include <linux/module.h>
5 #include <linux/init.h>
6 #include <linux/sort.h>
7
8 #include <linux/range.h>
9
10 #ifndef ARRAY_SIZE
11 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
12 #endif
13
14 int add_range(struct range *range, int az, int nr_range, u64 start, u64 end)
15 {
16         if (start > end)
17                 return nr_range;
18
19         /* Out of slots: */
20         if (nr_range >= az)
21                 return nr_range;
22
23         range[nr_range].start = start;
24         range[nr_range].end = end;
25
26         nr_range++;
27
28         return nr_range;
29 }
30
31 int add_range_with_merge(struct range *range, int az, int nr_range,
32                      u64 start, u64 end)
33 {
34         int i;
35
36         if (start > end)
37                 return nr_range;
38
39         /* Try to merge it with old one: */
40         for (i = 0; i < nr_range; i++) {
41                 u64 final_start, final_end;
42                 u64 common_start, common_end;
43
44                 if (!range[i].end)
45                         continue;
46
47                 common_start = max(range[i].start, start);
48                 common_end = min(range[i].end, end);
49                 if (common_start > common_end + 1)
50                         continue;
51
52                 final_start = min(range[i].start, start);
53                 final_end = max(range[i].end, end);
54
55                 range[i].start = final_start;
56                 range[i].end =  final_end;
57                 return nr_range;
58         }
59
60         /* Need to add it: */
61         return add_range(range, az, nr_range, start, end);
62 }
63
64 void subtract_range(struct range *range, int az, u64 start, u64 end)
65 {
66         int i, j;
67
68         if (start > end)
69                 return;
70
71         for (j = 0; j < az; j++) {
72                 if (!range[j].end)
73                         continue;
74
75                 if (start <= range[j].start && end >= range[j].end) {
76                         range[j].start = 0;
77                         range[j].end = 0;
78                         continue;
79                 }
80
81                 if (start <= range[j].start && end < range[j].end &&
82                     range[j].start < end + 1) {
83                         range[j].start = end + 1;
84                         continue;
85                 }
86
87
88                 if (start > range[j].start && end >= range[j].end &&
89                     range[j].end > start - 1) {
90                         range[j].end = start - 1;
91                         continue;
92                 }
93
94                 if (start > range[j].start && end < range[j].end) {
95                         /* Find the new spare: */
96                         for (i = 0; i < az; i++) {
97                                 if (range[i].end == 0)
98                                         break;
99                         }
100                         if (i < az) {
101                                 range[i].end = range[j].end;
102                                 range[i].start = end + 1;
103                         } else {
104                                 printk(KERN_ERR "run of slot in ranges\n");
105                         }
106                         range[j].end = start - 1;
107                         continue;
108                 }
109         }
110 }
111
112 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         start1 = r1->start;
119         start2 = r2->start;
120
121         return start1 - start2;
122 }
123
124 int clean_sort_range(struct range *range, int az)
125 {
126         int i, j, k = az - 1, nr_range = 0;
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
159 void sort_range(struct range *range, int nr_range)
160 {
161         /* sort them */
162         sort(range, nr_range, sizeof(struct range), cmp_range, NULL);
163 }