Implement the bitonic sort in src/sn_network.c.

The new implementation can handle input numbers which are not a power of
two. Also sn-bitonicmerge has been added which works analogously to
sn-oddevenmerge.

diff --git a/README b/README
index afac4ac..3278196 100644 (file)
--- a/README
+++ b/README
@@ -19,6 +19,10 @@ The distribution includes the following utility programs:
     Reads a list of values from STDIN and applies a given comparator network to
     the list. The resulting list of printed to STDOUT.
 
     Reads a list of values from STDIN and applies a given comparator network to
     the list. The resulting list of printed to STDOUT.
 

+  * sn-bitonicmerge
+    Create a bitonic merge network with a given number of left and right
+    inputs. The resulting network is printed to STDOUT.
+

   * sn-bitonicsort
     Creates a bitonic mergesort network with a given number of inputs and
     prints the network to STDOUT. The number of inputs must be a power of two.
   * sn-bitonicsort
     Creates a bitonic mergesort network with a given number of inputs and
     prints the network to STDOUT. The number of inputs must be a power of two.

diff --git a/src/Makefile.am b/src/Makefile.am
index 8923b41..1924258 100644 (file)
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -2,7 +2,9 @@ include_HEADERS = sn_network.h sn_stage.h sn_comparator.h
 
 lib_LTLIBRARIES = libsortnetwork.la
 
 
 lib_LTLIBRARIES = libsortnetwork.la
 

-bin_PROGRAMS = sn-apply sn-bitonicsort sn-bb sn-bb-merge sn-check-bf sn-cut \
+bin_PROGRAMS = sn-apply \
+              sn-bitonicmerge sn-bitonicsort \
+              sn-bb sn-bb-merge sn-check-bf sn-cut \

               sn-info sn-markov sn-merge sn-normalize \
               sn-oddevenmerge sn-oddevensort sn-pairwisesort \
               sn-shmoo sn-show sn-svg sn-tex
               sn-info sn-markov sn-merge sn-normalize \
               sn-oddevenmerge sn-oddevensort sn-pairwisesort \
               sn-shmoo sn-show sn-svg sn-tex


@@ -23,6 +25,9 @@ sn_bb_merge_SOURCES = sn-bb.c
 sn_bb_merge_CPPFLAGS = $(AM_CPPFLAGS) -DBUILD_MERGE=1
 sn_bb_merge_LDADD = libsortnetwork.la -lm
 
 sn_bb_merge_CPPFLAGS = $(AM_CPPFLAGS) -DBUILD_MERGE=1
 sn_bb_merge_LDADD = libsortnetwork.la -lm
 

+sn_bitonicmerge_SOURCES = sn-bitonicmerge.c
+sn_bitonicmerge_LDADD = libsortnetwork.la
+

 sn_bitonicsort_SOURCES = sn-bitonicsort.c
 sn_bitonicsort_LDADD = libsortnetwork.la
 
 sn_bitonicsort_SOURCES = sn-bitonicsort.c
 sn_bitonicsort_LDADD = libsortnetwork.la
 

diff --git a/src/sn-bitonicmerge.c b/src/sn-bitonicmerge.c
new file mode 100644 (file)
index 0000000..5503e13
--- /dev/null
+++ b/src/sn-bitonicmerge.c
@@ -0,0 +1,70 @@
+/**
+ * libsortnetwork - src/sn-bitonicmerge.c
+ * Copyright (C) 2008-2010  Florian octo Forster
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; only version 2 of the License is applicable.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
+ *
+ * Authors:
+ *   Florian octo Forster <ff at octo.it>
+ **/
+
+#ifndef _ISOC99_SOURCE
+# define _ISOC99_SOURCE
+#endif
+#ifndef _POSIX_C_SOURCE
+# define _POSIX_C_SOURCE 200112L
+#endif
+
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "sn_network.h"
+
+int main (int argc, char **argv)
+{
+  sn_network_t *sn_left;
+  sn_network_t *sn_right;
+  sn_network_t *bm;
+  int inputs_left;
+  int inputs_right;
+
+  if (argc != 3)
+  {
+    printf ("Usage: %s <inputs left> <inputs right>\n", argv[0]);
+    return (0);
+  }
+
+  inputs_left =  atoi (argv[1]);
+  inputs_right = atoi (argv[2]);
+  if ((inputs_left < 1) || (inputs_right < 1))
+  {
+    fprintf (stderr, "Invalid number of inputs: %i/%i\n",
+       inputs_left, inputs_right);
+    return (1);
+  }
+
+  sn_left = sn_network_create (inputs_left);
+  sn_right = sn_network_create (inputs_right);
+  bm = sn_network_combine_bitonic_merge (sn_left, sn_right);
+
+  sn_network_write (bm, stdout);
+
+  sn_network_destroy (sn_left);
+  sn_network_destroy (sn_right);
+  sn_network_destroy (bm);
+
+  return (0);
+} /* int main */
+
+/* vim: set shiftwidth=2 softtabstop=2 : */

diff --git a/src/sn-bitonicsort.c b/src/sn-bitonicsort.c
index 9a69dc2..3119123 100644 (file)
--- a/src/sn-bitonicsort.c
+++ b/src/sn-bitonicsort.c
@@ -31,88 +31,30 @@
 
 #include "sn_network.h"
 
 
 #include "sn_network.h"
 

-static sn_network_t *create_batcher_sort (size_t inputs_num)
-{
-  sn_network_t *n;
-  sn_network_t *n_small;
-
-  if (inputs_num == 2)
-  {
-    sn_stage_t *s;
-    sn_comparator_t c;
-
-    n = sn_network_create (2);
-    if (n == NULL)
-    {
-      fprintf (stderr, "create_batcher_sort: sn_network_create failed.\n");
-      return (NULL);
-    }
-
-    s = sn_stage_create (0);
-    if (s == NULL)
-    {
-      sn_network_destroy (n);
-      fprintf (stderr, "create_batcher_sort: sn_stage_create failed.\n");
-      return (NULL);
-    }
-
-    c.min = 0;
-    c.max = 1;
-
-    sn_stage_comparator_add (s, &c);
-    sn_network_stage_add (n, s);
-
-    return (n);
-  }
-  else if ((inputs_num < 2) || ((inputs_num % 2) != 0))
-  {
-    fprintf (stderr, "create_batcher_sort: Inputs must be a power of two, "
-       "sorry.\n");
-    return (NULL);
-  }
-
-  n_small = create_batcher_sort (inputs_num / 2);
-  if (n_small == NULL)
-    return (NULL);
-
-  n = sn_network_combine_bitonic_merge (n_small, n_small);
-  if (n == NULL)
-  {
-    sn_network_destroy (n_small);
-    fprintf (stderr, "create_batcher_sort: sn_network_combine_bitonic_merge "
-       "failed.\n");
-    return (NULL);
-  }
-
-  sn_network_destroy (n_small);
-  sn_network_compress (n);
-
-  return (n);
-} /* sn_network_t *create_batcher_sort */
-

 int main (int argc, char **argv)
 {
   sn_network_t *n;
 int main (int argc, char **argv)
 {
   sn_network_t *n;

-  size_t inputs_num;
+  int inputs_num;

 
   if (argc != 2)
   {
 
   if (argc != 2)
   {

-    printf ("Usage: %s <num inputs>\n", argv[0]);
-    return (0);
+    printf ("Usage: sn-bitonicsort <num inputs>\n");
+    exit (EXIT_SUCCESS);

   }
 
   }
 

-  inputs_num = (size_t) atoi (argv[1]);
+  inputs_num = atoi (argv[1]);

   if (inputs_num < 2)
   {
   if (inputs_num < 2)
   {

-    fprintf (stderr, "Invalid number of inputs: %zu\n", inputs_num);
-    return (1);
+    fprintf (stderr, "Invalid number of inputs: %i\n", inputs_num);
+    exit (EXIT_FAILURE);

   }
 
   }
 

-  n = create_batcher_sort (inputs_num);
+  n = sn_network_create_bitonic_mergesort (inputs_num);

   if (n == NULL)
   {
   if (n == NULL)
   {

-    printf ("n == NULL!\n");
-    return (1);
+    fprintf (stderr, "Creating bitonic mergesort network with %i inputs failed.\n",
+       inputs_num);
+    exit (EXIT_FAILURE);

   }
 
   sn_network_write (n, stdout);
   }
 
   sn_network_write (n, stdout);

diff --git a/src/sn_network.c b/src/sn_network.c
index ee4f79e..e7e3144 100644 (file)
--- a/src/sn_network.c
+++ b/src/sn_network.c
@@ -136,6 +136,66 @@ sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num) /* {{{ */
   }
 } /* }}} sn_network_t *sn_network_create_odd_even_mergesort */
 
   }
 } /* }}} sn_network_t *sn_network_create_odd_even_mergesort */
 

+sn_network_t *sn_network_create_bitonic_mergesort (int inputs_num) /* {{{ */
+{
+  sn_network_t *n;
+
+  assert (inputs_num > 0);
+  if (inputs_num == 1)
+  {
+    return (sn_network_create (inputs_num));
+  }
+  if (inputs_num == 2)
+  {
+    sn_comparator_t c;
+
+    n = sn_network_create (inputs_num);
+
+    memset (&c, 0, sizeof (c));
+    c.min = 0;
+    c.max = 1;
+
+    sn_network_comparator_add (n, &c);
+
+    return (n);
+  }
+  else
+  {
+    sn_network_t *n_left;
+    sn_network_t *n_right;
+    int inputs_left;
+    int inputs_right;
+
+    inputs_left = inputs_num / 2;
+    inputs_right = inputs_num - inputs_left;
+
+    n_left = sn_network_create_bitonic_mergesort (inputs_left);
+    if (n_left == NULL)
+      return (NULL);
+
+    if (inputs_left != inputs_right)
+      n_right = sn_network_create_bitonic_mergesort (inputs_right);
+    else
+      n_right = n_left;
+    if (n_right == NULL)
+    {
+      sn_network_destroy (n_left);
+      return (NULL);
+    }
+
+    n = sn_network_combine_bitonic_merge (n_left, n_right);
+
+    if (n_left != n_right)
+      sn_network_destroy (n_right);
+    sn_network_destroy (n_left);
+
+    if (n != NULL)
+      sn_network_compress (n);
+
+    return (n);
+  }
+} /* }}} sn_network_t *sn_network_create_bitonic_mergesort */
+

 static int sn_network_create_pairwise_internal (sn_network_t *n, /* {{{ */
     int *inputs, int inputs_num)
 {
 static int sn_network_create_pairwise_internal (sn_network_t *n, /* {{{ */
     int *inputs, int inputs_num)
 {


@@ -616,71 +676,44 @@ static sn_network_t *sn_network_concatenate (sn_network_t *n0, /* {{{ */
   return (n);
 } /* }}} sn_network_t *sn_network_concatenate */
 
   return (n);
 } /* }}} sn_network_t *sn_network_concatenate */
 

-static int sn_network_add_bitonic_merger_recursive (sn_network_t *n, /* {{{ */
-    int low, int num)
+static int sn_network_add_bitonic_merger (sn_network_t *n, /* {{{ */
+    int *indizes, int indizes_num)

 {
 {

-  sn_stage_t *s;
-  int m;

   int i;
 
   int i;
 

-  if (num == 1)
+  if (indizes_num <= 1)

     return (0);
 
     return (0);
 

-  s = sn_stage_create (n->stages_num);
-  if (s == NULL)
-    return (-1);
-
-  m = num / 2;
-
-  for (i = low; i < (low + m); i++)
+  if (indizes_num > 2)

   {
   {

-    sn_comparator_t c;
+    int even_indizes[indizes_num];
+    int even_indizes_num;
+    int odd_indizes[indizes_num];
+    int odd_indizes_num;

 
 

-    c.min = i;
-    c.max = i + m;
+    even_indizes_num = (indizes_num + 1) / 2;
+    odd_indizes_num = indizes_num / 2;

 
 

-    sn_stage_comparator_add (s, &c);
-  }
+    for (i = 0; i < even_indizes_num; i++)
+      even_indizes[i] = indizes[2 * i];
+    for (i = 0; i < odd_indizes_num; i++)
+      odd_indizes[i] = indizes[(2 * i) + 1];

 
 

-  sn_network_stage_add (n, s);
-
-  sn_network_add_bitonic_merger_recursive (n, low, m);
-  sn_network_add_bitonic_merger_recursive (n, low + m, m);
-
-  return (0);
-} /* }}} int sn_network_add_bitonic_merger_recursive */
-
-static int sn_network_add_bitonic_merger (sn_network_t *n) /* {{{ */
-{
-#if 0
-  sn_stage_t *s;
-  int m;
-  int i;
-
-  s = sn_stage_create (n->stages_num);
-  if (s == NULL)
-    return (-1);
-
-  m = n->inputs_num / 2;
+    sn_network_add_bitonic_merger (n, even_indizes, even_indizes_num);
+    sn_network_add_bitonic_merger (n, odd_indizes, odd_indizes_num);
+  }

 
 

-  for (i = 0; i < m; i++)
+  for (i = 1; i < indizes_num; i += 2)

   {
     sn_comparator_t c;
 
   {
     sn_comparator_t c;
 

-    c.min = i;
-    c.max = n->inputs_num - (i + 1);
+    memset (&c, 0, sizeof (c));
+    c.min = indizes[i - 1];
+    c.max = indizes[i];

 
 

-    sn_stage_comparator_add (s, &c);
+    sn_network_comparator_add (n, &c);

   }
 
   }
 

-  sn_network_stage_add (n, s);
-
-  sn_network_add_bitonic_merger_recursive (n, 0, m);
-  sn_network_add_bitonic_merger_recursive (n, m, m);
-#else
-  sn_network_add_bitonic_merger_recursive (n, 0, SN_NETWORK_INPUT_NUM (n));
-#endif
-

   return (0);
 } /* }}} int sn_network_add_bitonic_merger */
 
   return (0);
 } /* }}} int sn_network_add_bitonic_merger */
 


@@ -775,45 +808,37 @@ static int sn_network_add_odd_even_merger (sn_network_t *n, /* {{{ */
   return (0);
 } /* }}} int sn_network_add_odd_even_merger */
 
   return (0);
 } /* }}} int sn_network_add_odd_even_merger */
 

-static sn_network_t *sn_network_combine_bitonic_shift (sn_network_t *n0, /* {{{ */
-    sn_network_t *n1, int do_shift)
+sn_network_t *sn_network_combine_bitonic_merge (sn_network_t *n0, /* {{{ */
+    sn_network_t *n1)

 {
 {

+  sn_network_t *n0_clone;

   sn_network_t *n;
   sn_network_t *n;

-  sn_network_t *n1_clone;
-  int shift;
+  int indizes_num = SN_NETWORK_INPUT_NUM (n0) + SN_NETWORK_INPUT_NUM (n1);
+  int indizes[indizes_num];
+  int i;

 
 

-  n1_clone = sn_network_clone (n1);
-  if (n1_clone == NULL)
+  /* We need to invert n0, because the sequence must be
+   * z_1 >= z_2 >= ... >= z_k <= z_{k+1} <= ... <= z_p
+   * and NOT the other way around! Otherwise the comparators added in
+   * sn_network_add_bitonic_merger() from comparing (z_0,z_1), (z_2,z_3), ...
+   * to comparing ...,  (z_{n-4},z_{n-3}), (z_{n-2},z_{n-1}), i.e. bound to the
+   * end of the list, possibly leaving z_0 uncompared. */
+  n0_clone = sn_network_clone (n0);
+  if (n0_clone == NULL)

     return (NULL);
     return (NULL);

+  sn_network_invert (n0_clone);

 
 

-  sn_network_invert (n1_clone);
-
-  n = sn_network_concatenate (n0, n1_clone);
+  n = sn_network_concatenate (n0_clone, n1);

   if (n == NULL)
     return (NULL);
   if (n == NULL)
     return (NULL);

+  sn_network_destroy (n0_clone);

 
 

-  sn_network_destroy (n1_clone);
-
-  if (do_shift)
-    shift = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n) - 1);
-  else
-    shift = 0;
+  for (i = 0; i < indizes_num; i++)
+    indizes[i] = i;

 
 

-  if (shift > 0)
-  {
-    DPRINTF ("sn_network_combine_bitonic_shift: Shifting by %i.\n", shift);
-    sn_network_shift (n, shift);
-  }
-
-  sn_network_add_bitonic_merger (n);
+  sn_network_add_bitonic_merger (n, indizes, indizes_num);

 
   return (n);
 
   return (n);

-} /* }}} sn_network_t *sn_network_combine_bitonic_shift */
-
-sn_network_t *sn_network_combine_bitonic_merge (sn_network_t *n0, /* {{{ */
-    sn_network_t *n1)
-{
-  return (sn_network_combine_bitonic_shift (n0, n1, /* do_shift = */ 0));

 } /* }}} sn_network_t *sn_network_combine_bitonic_merge */
 
 sn_network_t *sn_network_combine_odd_even_merge (sn_network_t *n0, /* {{{ */
 } /* }}} sn_network_t *sn_network_combine_bitonic_merge */
 
 sn_network_t *sn_network_combine_odd_even_merge (sn_network_t *n0, /* {{{ */

diff --git a/src/sn_network.h b/src/sn_network.h
index 328d0fe..eb5b2e9 100644 (file)
--- a/src/sn_network.h
+++ b/src/sn_network.h
@@ -87,6 +87,15 @@ void sn_network_destroy (sn_network_t *n);
 sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num);
 
 /**
 sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num);
 
 /**

+ * Creates a new sort network using Batcher's Bitonic-Mergesort algorithm.
+ *
+ * \param inputs_num Number of inputs / outputs of the sorting network.
+ * \return A pointer to the newly allocated sorting network or \c NULL if an
+ *   invalid number of inputs was given or allocation failed.
+ */
+sn_network_t *sn_network_create_bitonic_mergesort (int inputs_num);
+
+/**

  * Creates a new sorting network using the Pairwise sorting algorithm published
  * by Ian Parberry.
  * \param inputs_num Number of inputs / outputs of the sorting network.
  * Creates a new sorting network using the Pairwise sorting algorithm published
  * by Ian Parberry.
  * \param inputs_num Number of inputs / outputs of the sorting network.