Root/
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 | int 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 | |
27 | int 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 | |
60 | void 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 | |
108 | static 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 | |
120 | int 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 | |
155 | void 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 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9