Branch data     Line data    Source code

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