1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Range add and subtract 4 */ 5 #include <linux/kernel.h> 6 #include <linux/init.h> 7 #include <linux/sort.h> 8 #include <linux/string.h> 9 #include <linux/range.h> 10 11 int add_range(struct range *range, int az, int nr_range, u64 start, u64 end) 12 { 13 if (start >= end) 14 return nr_range; 15 16 /* Out of slots: */ 17 if (nr_range >= az) 18 return nr_range; 19 20 range[nr_range].start = start; 21 range[nr_range].end = end; 22 23 nr_range++; 24 25 return nr_range; 26 } 27 28 int add_range_with_merge(struct range *range, int az, int nr_range, 29 u64 start, u64 end) 30 { 31 int i; 32 33 if (start >= end) 34 return nr_range; 35 36 /* get new start/end: */ 37 for (i = 0; i < nr_range; i++) { 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 /* new start/end, will add it back at last */ 49 start = min(range[i].start, start); 50 end = max(range[i].end, end); 51 52 memmove(&range[i], &range[i + 1], 53 (nr_range - (i + 1)) * sizeof(range[i])); 54 range[nr_range - 1].start = 0; 55 range[nr_range - 1].end = 0; 56 nr_range--; 57 i--; 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) { 83 range[j].start = end; 84 continue; 85 } 86 87 88 if (start > range[j].start && end >= range[j].end && 89 range[j].end > start) { 90 range[j].end = start; 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; 103 } else { 104 pr_err("%s: run out of slot in ranges\n", 105 __func__); 106 } 107 range[j].end = start; 108 continue; 109 } 110 } 111 } 112 113 static int cmp_range(const void *x1, const void *x2) 114 { 115 const struct range *r1 = x1; 116 const struct range *r2 = x2; 117 118 if (r1->start < r2->start) 119 return -1; 120 if (r1->start > r2->start) 121 return 1; 122 return 0; 123 } 124 125 int clean_sort_range(struct range *range, int az) 126 { 127 int i, j, k = az - 1, nr_range = az; 128 129 for (i = 0; i < k; i++) { 130 if (range[i].end) 131 continue; 132 for (j = k; j > i; j--) { 133 if (range[j].end) { 134 k = j; 135 break; 136 } 137 } 138 if (j == i) 139 break; 140 range[i].start = range[k].start; 141 range[i].end = range[k].end; 142 range[k].start = 0; 143 range[k].end = 0; 144 k--; 145 } 146 /* count it */ 147 for (i = 0; i < az; i++) { 148 if (!range[i].end) { 149 nr_range = i; 150 break; 151 } 152 } 153 154 /* sort them */ 155 sort(range, nr_range, sizeof(struct range), cmp_range, NULL); 156 157 return nr_range; 158 } 159 160 void sort_range(struct range *range, int nr_range) 161 { 162 /* sort them */ 163 sort(range, nr_range, sizeof(struct range), cmp_range, NULL); 164 } 165