1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Range add and subtract 4 */ 5 #include <linux/init.h> 6 #include <linux/minmax.h> 7 #include <linux/printk.h> 8 #include <linux/sort.h> 9 #include <linux/string.h> 10 #include <linux/range.h> 11 12 int add_range(struct range *range, int az, int nr_range, u64 start, u64 end) 13 { 14 if (start >= end) 15 return nr_range; 16 17 /* Out of slots: */ 18 if (nr_range >= az) 19 return nr_range; 20 21 range[nr_range].start = start; 22 range[nr_range].end = end; 23 24 nr_range++; 25 26 return nr_range; 27 } 28 29 int add_range_with_merge(struct range *range, int az, int nr_range, 30 u64 start, u64 end) 31 { 32 int i; 33 34 if (start >= end) 35 return nr_range; 36 37 /* get new start/end: */ 38 for (i = 0; i < nr_range; i++) { 39 u64 common_start, common_end; 40 41 if (!range[i].end) 42 continue; 43 44 common_start = max(range[i].start, start); 45 common_end = min(range[i].end, end); 46 if (common_start > common_end) 47 continue; 48 49 /* new start/end, will add it back at last */ 50 start = min(range[i].start, start); 51 end = max(range[i].end, end); 52 53 memmove(&range[i], &range[i + 1], 54 (nr_range - (i + 1)) * sizeof(range[i])); 55 range[nr_range - 1].start = 0; 56 range[nr_range - 1].end = 0; 57 nr_range--; 58 i--; 59 } 60 61 /* Need to add it: */ 62 return add_range(range, az, nr_range, start, end); 63 } 64 65 void subtract_range(struct range *range, int az, u64 start, u64 end) 66 { 67 int i, j; 68 69 if (start >= end) 70 return; 71 72 for (j = 0; j < az; j++) { 73 if (!range[j].end) 74 continue; 75 76 if (start <= range[j].start && end >= range[j].end) { 77 range[j].start = 0; 78 range[j].end = 0; 79 continue; 80 } 81 82 if (start <= range[j].start && end < range[j].end && 83 range[j].start < end) { 84 range[j].start = end; 85 continue; 86 } 87 88 89 if (start > range[j].start && end >= range[j].end && 90 range[j].end > start) { 91 range[j].end = start; 92 continue; 93 } 94 95 if (start > range[j].start && end < range[j].end) { 96 /* Find the new spare: */ 97 for (i = 0; i < az; i++) { 98 if (range[i].end == 0) 99 break; 100 } 101 if (i < az) { 102 range[i].end = range[j].end; 103 range[i].start = end; 104 } else { 105 pr_err("%s: run out of slot in ranges\n", 106 __func__); 107 } 108 range[j].end = start; 109 continue; 110 } 111 } 112 } 113 114 static int cmp_range(const void *x1, const void *x2) 115 { 116 const struct range *r1 = x1; 117 const struct range *r2 = x2; 118 119 if (r1->start < r2->start) 120 return -1; 121 if (r1->start > r2->start) 122 return 1; 123 return 0; 124 } 125 126 int clean_sort_range(struct range *range, int az) 127 { 128 int i, j, k = az - 1, nr_range = az; 129 130 for (i = 0; i < k; i++) { 131 if (range[i].end) 132 continue; 133 for (j = k; j > i; j--) { 134 if (range[j].end) { 135 k = j; 136 break; 137 } 138 } 139 if (j == i) 140 break; 141 range[i].start = range[k].start; 142 range[i].end = range[k].end; 143 range[k].start = 0; 144 range[k].end = 0; 145 k--; 146 } 147 /* count it */ 148 for (i = 0; i < az; i++) { 149 if (!range[i].end) { 150 nr_range = i; 151 break; 152 } 153 } 154 155 /* sort them */ 156 sort(range, nr_range, sizeof(struct range), cmp_range, NULL); 157 158 return nr_range; 159 } 160 161 void sort_range(struct range *range, int nr_range) 162 { 163 /* sort them */ 164 sort(range, nr_range, sizeof(struct range), cmp_range, NULL); 165 } 166