Line data    Source code

       1             : // SPDX-License-Identifier: GPL-2.0-or-later
       2             : // Copyright (C) 2013 Andrea Mazzoleni
       3             : 
       4             : #include "internal.h"
       5             : 
       6             : #define RAID_SWAP(a, b) \
       7             :         do { \
       8             :                 if (v[a] > v[b]) { \
       9             :                         int t = v[a]; \
      10             :                         v[a] = v[b]; \
      11             :                         v[b] = t; \
      12             :                 } \
      13             :         } while (0)
      14             : 
      15       55986 : void raid_sort(int n, int *v)
      16             : {
      17             :         /* sorting networks generated with Batcher's Merge-Exchange */
      18       55986 :         switch (n) {
      19          36 :         case 2:
      20          36 :                 RAID_SWAP(0, 1);
      21          36 :                 break;
      22         216 :         case 3:
      23         216 :                 RAID_SWAP(0, 2);
      24         216 :                 RAID_SWAP(0, 1);
      25         216 :                 RAID_SWAP(1, 2);
      26         216 :                 break;
      27        1296 :         case 4:
      28        1296 :                 RAID_SWAP(0, 2);
      29        1296 :                 RAID_SWAP(1, 3);
      30        1296 :                 RAID_SWAP(0, 1);
      31        1296 :                 RAID_SWAP(2, 3);
      32        1296 :                 RAID_SWAP(1, 2);
      33        1296 :                 break;
      34        7776 :         case 5:
      35        7776 :                 RAID_SWAP(0, 4);
      36        7776 :                 RAID_SWAP(0, 2);
      37        7776 :                 RAID_SWAP(1, 3);
      38        7776 :                 RAID_SWAP(2, 4);
      39        7776 :                 RAID_SWAP(0, 1);
      40        7776 :                 RAID_SWAP(2, 3);
      41        7776 :                 RAID_SWAP(1, 4);
      42        7776 :                 RAID_SWAP(1, 2);
      43        7776 :                 RAID_SWAP(3, 4);
      44        7776 :                 break;
      45       46656 :         case 6:
      46       46656 :                 RAID_SWAP(0, 4);
      47       46656 :                 RAID_SWAP(1, 5);
      48       46656 :                 RAID_SWAP(0, 2);
      49       46656 :                 RAID_SWAP(1, 3);
      50       46656 :                 RAID_SWAP(2, 4);
      51       46656 :                 RAID_SWAP(3, 5);
      52       46656 :                 RAID_SWAP(0, 1);
      53       46656 :                 RAID_SWAP(2, 3);
      54       46656 :                 RAID_SWAP(4, 5);
      55       46656 :                 RAID_SWAP(1, 4);
      56       46656 :                 RAID_SWAP(1, 2);
      57       46656 :                 RAID_SWAP(3, 4);
      58       46656 :                 break;
      59             :         }
      60       55986 : }
      61             : 
      62      324726 : void raid_insert(int n, int *v, int i)
      63             : {
      64             :         /*
      65             :          * We don't use binary search because this is intended
      66             :          * for very small vectors and we want to optimize the case
      67             :          * of elements inserted already in order
      68             :          */
      69             : 
      70             :         /* insert at the end */
      71      324726 :         v[n] = i;
      72             : 
      73             :         /* swap until in the correct position */
      74      652251 :         while (n > 0 && v[n - 1] > v[n]) {
      75             :                 /* swap */
      76      327525 :                 int t = v[n - 1];
      77             : 
      78      327525 :                 v[n - 1] = v[n];
      79      327525 :                 v[n] = t;
      80             : 
      81             :                 /* previous position */
      82      327525 :                 --n;
      83             :         }
      84      324726 : }
      85             :