Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
range.c
Go to the documentation of this file.
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 
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 }