git.sesse.net Git - bcachefs-tools-debian/blob - c_src/raid/helper.c

   1 /*
   2  * Copyright (C) 2013 Andrea Mazzoleni
   3  *
   4  * This program is free software: you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  */
  14
  15 #include "internal.h"
  16
  17 #define RAID_SWAP(a, b) \
  18         do { \
  19                 if (v[a] > v[b]) { \
  20                         int t = v[a]; \
  21                         v[a] = v[b]; \
  22                         v[b] = t; \
  23                 } \
  24         } while (0)
  25
  26 void raid_sort(int n, int *v)
  27 {
  28         /* sorting networks generated with Batcher's Merge-Exchange */
  29         switch (n) {
  30         case 2:
  31                 RAID_SWAP(0, 1);
  32                 break;
  33         case 3:
  34                 RAID_SWAP(0, 2);
  35                 RAID_SWAP(0, 1);
  36                 RAID_SWAP(1, 2);
  37                 break;
  38         case 4:
  39                 RAID_SWAP(0, 2);
  40                 RAID_SWAP(1, 3);
  41                 RAID_SWAP(0, 1);
  42                 RAID_SWAP(2, 3);
  43                 RAID_SWAP(1, 2);
  44                 break;
  45         case 5:
  46                 RAID_SWAP(0, 4);
  47                 RAID_SWAP(0, 2);
  48                 RAID_SWAP(1, 3);
  49                 RAID_SWAP(2, 4);
  50                 RAID_SWAP(0, 1);
  51                 RAID_SWAP(2, 3);
  52                 RAID_SWAP(1, 4);
  53                 RAID_SWAP(1, 2);
  54                 RAID_SWAP(3, 4);
  55                 break;
  56         case 6:
  57                 RAID_SWAP(0, 4);
  58                 RAID_SWAP(1, 5);
  59                 RAID_SWAP(0, 2);
  60                 RAID_SWAP(1, 3);
  61                 RAID_SWAP(2, 4);
  62                 RAID_SWAP(3, 5);
  63                 RAID_SWAP(0, 1);
  64                 RAID_SWAP(2, 3);
  65                 RAID_SWAP(4, 5);
  66                 RAID_SWAP(1, 4);
  67                 RAID_SWAP(1, 2);
  68                 RAID_SWAP(3, 4);
  69                 break;
  70         }
  71 }
  72
  73 void raid_insert(int n, int *v, int i)
  74 {
  75         /* we don't use binary search because this is intended */
  76         /* for very small vectors and we want to optimize the case */
  77         /* of elements inserted already in order */
  78
  79         /* insert at the end */
  80         v[n] = i;
  81
  82         /* swap until in the correct position */
  83         while (n > 0 && v[n - 1] > v[n]) {
  84                 /* swap */
  85                 int t = v[n - 1];
  86
  87                 v[n - 1] = v[n];
  88                 v[n] = t;
  89
  90                 /* previous position */
  91                 --n;
  92         }
  93 }
  94