Back to home page

LXR

 
 

    


0001 /*
0002  * Range add and subtract
0003  */
0004 #include <linux/kernel.h>
0005 #include <linux/init.h>
0006 #include <linux/sort.h>
0007 #include <linux/string.h>
0008 #include <linux/range.h>
0009 
0010 int add_range(struct range *range, int az, int nr_range, u64 start, u64 end)
0011 {
0012     if (start >= end)
0013         return nr_range;
0014 
0015     /* Out of slots: */
0016     if (nr_range >= az)
0017         return nr_range;
0018 
0019     range[nr_range].start = start;
0020     range[nr_range].end = end;
0021 
0022     nr_range++;
0023 
0024     return nr_range;
0025 }
0026 
0027 int add_range_with_merge(struct range *range, int az, int nr_range,
0028              u64 start, u64 end)
0029 {
0030     int i;
0031 
0032     if (start >= end)
0033         return nr_range;
0034 
0035     /* get new start/end: */
0036     for (i = 0; i < nr_range; i++) {
0037         u64 common_start, common_end;
0038 
0039         if (!range[i].end)
0040             continue;
0041 
0042         common_start = max(range[i].start, start);
0043         common_end = min(range[i].end, end);
0044         if (common_start > common_end)
0045             continue;
0046 
0047         /* new start/end, will add it back at last */
0048         start = min(range[i].start, start);
0049         end = max(range[i].end, end);
0050 
0051         memmove(&range[i], &range[i + 1],
0052             (nr_range - (i + 1)) * sizeof(range[i]));
0053         range[nr_range - 1].start = 0;
0054         range[nr_range - 1].end   = 0;
0055         nr_range--;
0056         i--;
0057     }
0058 
0059     /* Need to add it: */
0060     return add_range(range, az, nr_range, start, end);
0061 }
0062 
0063 void subtract_range(struct range *range, int az, u64 start, u64 end)
0064 {
0065     int i, j;
0066 
0067     if (start >= end)
0068         return;
0069 
0070     for (j = 0; j < az; j++) {
0071         if (!range[j].end)
0072             continue;
0073 
0074         if (start <= range[j].start && end >= range[j].end) {
0075             range[j].start = 0;
0076             range[j].end = 0;
0077             continue;
0078         }
0079 
0080         if (start <= range[j].start && end < range[j].end &&
0081             range[j].start < end) {
0082             range[j].start = end;
0083             continue;
0084         }
0085 
0086 
0087         if (start > range[j].start && end >= range[j].end &&
0088             range[j].end > start) {
0089             range[j].end = start;
0090             continue;
0091         }
0092 
0093         if (start > range[j].start && end < range[j].end) {
0094             /* Find the new spare: */
0095             for (i = 0; i < az; i++) {
0096                 if (range[i].end == 0)
0097                     break;
0098             }
0099             if (i < az) {
0100                 range[i].end = range[j].end;
0101                 range[i].start = end;
0102             } else {
0103                 pr_err("%s: run out of slot in ranges\n",
0104                     __func__);
0105             }
0106             range[j].end = start;
0107             continue;
0108         }
0109     }
0110 }
0111 
0112 static int cmp_range(const void *x1, const void *x2)
0113 {
0114     const struct range *r1 = x1;
0115     const struct range *r2 = x2;
0116 
0117     if (r1->start < r2->start)
0118         return -1;
0119     if (r1->start > r2->start)
0120         return 1;
0121     return 0;
0122 }
0123 
0124 int clean_sort_range(struct range *range, int az)
0125 {
0126     int i, j, k = az - 1, nr_range = az;
0127 
0128     for (i = 0; i < k; i++) {
0129         if (range[i].end)
0130             continue;
0131         for (j = k; j > i; j--) {
0132             if (range[j].end) {
0133                 k = j;
0134                 break;
0135             }
0136         }
0137         if (j == i)
0138             break;
0139         range[i].start = range[k].start;
0140         range[i].end   = range[k].end;
0141         range[k].start = 0;
0142         range[k].end   = 0;
0143         k--;
0144     }
0145     /* count it */
0146     for (i = 0; i < az; i++) {
0147         if (!range[i].end) {
0148             nr_range = i;
0149             break;
0150         }
0151     }
0152 
0153     /* sort them */
0154     sort(range, nr_range, sizeof(struct range), cmp_range, NULL);
0155 
0156     return nr_range;
0157 }
0158 
0159 void sort_range(struct range *range, int nr_range)
0160 {
0161     /* sort them */
0162     sort(range, nr_range, sizeof(struct range), cmp_range, NULL);
0163 }