src/sn-batcher.c

   1 /**
   2  * libsortnetwork - src/sn-batcher.c
   3  * Copyright (C) 2008-2010  Florian octo Forster
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the
   7  * Free Software Foundation; only version 2 of the License is applicable.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License along
  15  * with this program; if not, write to the Free Software Foundation, Inc.,
  16  * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  17  *
  18  * Authors:
  19  *   Florian octo Forster <ff at octo.it>
  20  **/
  21
  22 #ifndef _ISOC99_SOURCE
  23 # define _ISOC99_SOURCE
  24 #endif
  25 #ifndef _POSIX_C_SOURCE
  26 # define _POSIX_C_SOURCE 200112L
  27 #endif
  28
  29 #include <stdlib.h>
  30 #include <stdio.h>
  31
  32 #include "sn_network.h"
  33
  34 static sn_network_t *create_batcher_sort (size_t inputs_num)
  35 {
  36   sn_network_t *n;
  37   sn_network_t *n_small;
  38
  39   if (inputs_num == 2)
  40   {
  41     sn_stage_t *s;
  42     sn_comparator_t c;
  43
  44     n = sn_network_create (2);
  45     if (n == NULL)
  46     {
  47       fprintf (stderr, "create_batcher_sort: sn_network_create failed.\n");
  48       return (NULL);
  49     }
  50
  51     s = sn_stage_create (0);
  52     if (s == NULL)
  53     {
  54       sn_network_destroy (n);
  55       fprintf (stderr, "create_batcher_sort: sn_stage_create failed.\n");
  56       return (NULL);
  57     }
  58
  59     c.min = 0;
  60     c.max = 1;
  61
  62     sn_stage_comparator_add (s, &c);
  63     sn_network_stage_add (n, s);
  64
  65     return (n);
  66   }
  67   else if ((inputs_num < 2) || ((inputs_num % 2) != 0))
  68   {
  69     fprintf (stderr, "create_batcher_sort: Inputs must be a power of two, "
  70         "sorry.\n");
  71     return (NULL);
  72   }
  73
  74   n_small = create_batcher_sort (inputs_num / 2);
  75   if (n_small == NULL)
  76     return (NULL);
  77
  78   n = sn_network_combine_bitonic_merge (n_small, n_small);
  79   if (n == NULL)
  80   {
  81     sn_network_destroy (n_small);
  82     fprintf (stderr, "create_batcher_sort: sn_network_combine_bitonic_merge "
  83         "failed.\n");
  84     return (NULL);
  85   }
  86
  87   sn_network_destroy (n_small);
  88   sn_network_compress (n);
  89
  90   return (n);
  91 } /* sn_network_t *create_batcher_sort */
  92
  93 int main (int argc, char **argv)
  94 {
  95   sn_network_t *n;
  96   size_t inputs_num;
  97
  98   if (argc != 2)
  99   {
 100     printf ("Usage: %s <num inputs>\n", argv[0]);
 101     return (0);
 102   }
 103
 104   inputs_num = (size_t) atoi (argv[1]);
 105   if (inputs_num < 2)
 106   {
 107     fprintf (stderr, "Invalid number of inputs: %zu\n", inputs_num);
 108     return (1);
 109   }
 110
 111   n = create_batcher_sort (inputs_num);
 112   if (n == NULL)
 113   {
 114     printf ("n == NULL!\n");
 115     return (1);
 116   }
 117
 118   sn_network_write (n, stdout);
 119
 120   return (0);
 121 } /* int main */
 122
 123 /* vim: set shiftwidth=2 softtabstop=2 : */