Line data    Source code

       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       55986 : void raid_sort(int n, int *v)
      27             : {
      28             :         /* sorting networks generated with Batcher's Merge-Exchange */
      29       55986 :         switch (n) {
      30             :         case 2:
      31          36 :                 RAID_SWAP(0, 1);
      32          36 :                 break;
      33             :         case 3:
      34         216 :                 RAID_SWAP(0, 2);
      35         216 :                 RAID_SWAP(0, 1);
      36         216 :                 RAID_SWAP(1, 2);
      37         216 :                 break;
      38             :         case 4:
      39        1296 :                 RAID_SWAP(0, 2);
      40        1296 :                 RAID_SWAP(1, 3);
      41        1296 :                 RAID_SWAP(0, 1);
      42        1296 :                 RAID_SWAP(2, 3);
      43        1296 :                 RAID_SWAP(1, 2);
      44        1296 :                 break;
      45             :         case 5:
      46        7776 :                 RAID_SWAP(0, 4);
      47        7776 :                 RAID_SWAP(0, 2);
      48        7776 :                 RAID_SWAP(1, 3);
      49        7776 :                 RAID_SWAP(2, 4);
      50        7776 :                 RAID_SWAP(0, 1);
      51        7776 :                 RAID_SWAP(2, 3);
      52        7776 :                 RAID_SWAP(1, 4);
      53        7776 :                 RAID_SWAP(1, 2);
      54        7776 :                 RAID_SWAP(3, 4);
      55        7776 :                 break;
      56             :         case 6:
      57       46656 :                 RAID_SWAP(0, 4);
      58       46656 :                 RAID_SWAP(1, 5);
      59       46656 :                 RAID_SWAP(0, 2);
      60       46656 :                 RAID_SWAP(1, 3);
      61       46656 :                 RAID_SWAP(2, 4);
      62       46656 :                 RAID_SWAP(3, 5);
      63       46656 :                 RAID_SWAP(0, 1);
      64       46656 :                 RAID_SWAP(2, 3);
      65       46656 :                 RAID_SWAP(4, 5);
      66       46656 :                 RAID_SWAP(1, 4);
      67       46656 :                 RAID_SWAP(1, 2);
      68       46656 :                 RAID_SWAP(3, 4);
      69       46656 :                 break;
      70             :         }
      71       55986 : }
      72             : 
      73      324726 : 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      324726 :         v[n] = i;
      81             : 
      82             :         /* swap until in the correct position */
      83      976977 :         while (n > 0 && v[n - 1] > v[n]) {
      84             :                 /* swap */
      85      327525 :                 int t = v[n - 1];
      86             : 
      87      327525 :                 v[n - 1] = v[n];
      88      327525 :                 v[n] = t;
      89             : 
      90             :                 /* previous position */
      91      327525 :                 --n;
      92             :         }
      93      324726 : }
      94             :