the-tree/kernel/range.c

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