Implement the bitonic sort in src/sn_network.c.
authorFlorian Forster <octo@leeloo.octo.it>
Tue, 21 Dec 2010 10:35:12 +0000 (11:35 +0100)
committerFlorian Forster <octo@leeloo.octo.it>
Tue, 21 Dec 2010 10:35:12 +0000 (11:35 +0100)
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.

README
src/Makefile.am
src/sn-bitonicmerge.c [new file with mode: 0644]
src/sn-bitonicsort.c
src/sn_network.c
src/sn_network.h

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.
 
+  * 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.
index 8923b41..1924258 100644 (file)
@@ -2,7 +2,9 @@ include_HEADERS = sn_network.h sn_stage.h sn_comparator.h
 
 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
@@ -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_bitonicmerge_SOURCES = sn-bitonicmerge.c
+sn_bitonicmerge_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
@@ -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 : */
index 9a69dc2..3119123 100644 (file)
 
 #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;
-  size_t inputs_num;
+  int inputs_num;
 
   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)
   {
-    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)
   {
-    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);
index ee4f79e..e7e3144 100644 (file)
@@ -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_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)
 {
@@ -616,71 +676,44 @@ static sn_network_t *sn_network_concatenate (sn_network_t *n0, /* {{{ */
   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;
 
-  if (num == 1)
+  if (indizes_num <= 1)
     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;
 
-    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 */
 
@@ -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 */
 
-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 *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);
+  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);
+  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);
-} /* }}} 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, /* {{{ */
index 328d0fe..eb5b2e9 100644 (file)
@@ -87,6 +87,15 @@ void sn_network_destroy (sn_network_t *n);
 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.