X-Git-Url: https://git.octo.it/?p=sort-networks.git;a=blobdiff_plain;f=src%2Fsn_network.c;h=90a86cf9500e5c0e6ada0de5cf1455fff32d730b;hp=6908cf85f0c1ad42bc08203211d1b3c8d46af46e;hb=b1632a807fc2166da35bb6b59d60738d4db24627;hpb=1e765313eb44b5707ea9cdc3429ce5da48cfbcd3

diff --git a/src/sn_network.c b/src/sn_network.c
index 6908cf8..90a86cf 100644
--- a/src/sn_network.c
+++ b/src/sn_network.c
@@ -2,18 +2,19 @@
  * libsortnetwork - src/sn_network.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 library is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at
+ * your option) any later version.
  *
- * 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.
+ * This library 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 Lesser 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
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this library; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  *
  * Authors:
  *   Florian octo Forster <ff at octo.it>
@@ -81,24 +82,22 @@ sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num) /* {{{ */
 {
   sn_network_t *n;
 
-  n = sn_network_create (inputs_num);
-
   assert (inputs_num > 0);
   if (inputs_num == 1)
   {
-    return (n);
+    return (sn_network_create (inputs_num));
   }
   if (inputs_num == 2)
   {
-    sn_stage_t *s;
     sn_comparator_t c;
 
+    n = sn_network_create (inputs_num);
+
+    memset (&c, 0, sizeof (c));
     c.min = 0;
     c.max = 1;
 
-    s = sn_stage_create (/* depth = */ 0);
-    sn_stage_comparator_add (s, &c);
-    sn_network_stage_add (n, s);
+    sn_network_comparator_add (n, &c);
 
     return (n);
   }
@@ -135,6 +134,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)
 {
@@ -164,17 +223,25 @@ static int sn_network_create_pairwise_internal (sn_network_t *n, /* {{{ */
     inputs_copy[(int) (i / 2)] = inputs[i];
   /* Recursive call #2 with second set of lines */
   sn_network_create_pairwise_internal (n, inputs_copy,
-      (int) (inputs_num/ 2));
+      (int) (inputs_num / 2));
 
   /* m is the "amplitude" of the sorted pairs. This is a bit tricky to read due
    * to different indices being used in the paper, unfortunately. */
-  m = inputs_num / 2;
+  m = (inputs_num + 1) / 2;
   while (m > 1)
   {
-    for (i = 1; (i + (m - 1)) < inputs_num; i += 2)
+    int len;
+
+    /* len = ((int) ((m + 1) / 2)) * 2 - 1; */
+    if ((m % 2) == 0)
+      len = m - 1;
+    else
+      len = m;
+
+    for (i = 1; (i + len) < inputs_num; i += 2)
     {
       int left = i;
-      int right = i + (m - 1);
+      int right = i + len;
       sn_comparator_t *c;
 
       assert (left < right);
@@ -183,7 +250,7 @@ static int sn_network_create_pairwise_internal (sn_network_t *n, /* {{{ */
       sn_comparator_destroy (c);
     }
 
-    m = m / 2;
+    m = (m + 1) / 2;
   } /* while (m > 1) */
 
   return (0);
@@ -207,6 +274,37 @@ sn_network_t *sn_network_create_pairwise (int inputs_num) /* {{{ */
   return (n);
 } /* }}} sn_network_t *sn_network_create_pairwise */
 
+int sn_network_network_add (sn_network_t *n, sn_network_t *other) /* {{{ */
+{
+  int stages_num;
+  sn_stage_t **tmp;
+  int i;
+
+  if ((n == NULL) || (other == NULL))
+    return (EINVAL);
+
+  stages_num = n->stages_num + other->stages_num;
+  if (stages_num <= n->stages_num)
+    return (EINVAL);
+
+  tmp = realloc (n->stages, sizeof (*n->stages) * stages_num);
+  if (tmp == NULL)
+    return (ENOMEM);
+  n->stages = tmp;
+
+  memcpy (n->stages + n->stages_num, other->stages,
+      sizeof (*other->stages) * other->stages_num);
+  for (i = n->stages_num; i < stages_num; i++)
+    SN_STAGE_DEPTH(n->stages[i]) = i;
+
+  n->stages_num = stages_num;
+
+  free (other->stages);
+  free (other);
+
+  return (0);
+} /* }}} int sn_network_network_add */
+
 int sn_network_stage_add (sn_network_t *n, sn_stage_t *s) /* {{{ */
 {
   sn_stage_t **temp;
@@ -337,14 +435,19 @@ int sn_network_get_comparator_num (const sn_network_t *n) /* {{{ */
   return (num);
 } /* }}} int sn_network_get_comparator_num */
 
-int sn_network_show (sn_network_t *n) /* {{{ */
+int sn_network_show_fh (sn_network_t *n, FILE *fh) /* {{{ */
 {
   int i;
 
   for (i = 0; i < n->stages_num; i++)
-    sn_stage_show (n->stages[i]);
+    sn_stage_show_fh (n->stages[i], fh);
 
   return (0);
+} /* }}} int sn_network_show_fh */
+
+int sn_network_show (sn_network_t *n) /* {{{ */
+{
+  return (sn_network_show_fh (n, stdout));
 } /* }}} int sn_network_show */
 
 int sn_network_invert (sn_network_t *n) /* {{{ */
@@ -464,6 +567,22 @@ int sn_network_normalize (sn_network_t *n) /* {{{ */
   return (0);
 } /* }}} int sn_network_normalize */
 
+int sn_network_unify (sn_network_t *n) /* {{{ */
+{
+  int i;
+
+  if (n == NULL)
+    return (EINVAL);
+
+  sn_network_normalize (n);
+  sn_network_compress (n);
+
+  for (i = 0; i < n->stages_num; i++)
+    sn_stage_unify (n->stages[i]);
+
+  return (0);
+} /* }}} int sn_network_unify */
+
 int sn_network_remove_input (sn_network_t *n, int input) /* {{{ */
 {
   int i;
@@ -588,71 +707,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;
-
-    c.min = i;
-    c.max = i + m;
+    int even_indizes[indizes_num];
+    int even_indizes_num;
+    int odd_indizes[indizes_num];
+    int odd_indizes_num;
 
-    sn_stage_comparator_add (s, &c);
-  }
+    even_indizes_num = (indizes_num + 1) / 2;
+    odd_indizes_num = indizes_num / 2;
 
-  sn_network_stage_add (n, s);
+    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_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 */
 
@@ -747,45 +839,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;
-
-  if (shift > 0)
-  {
-    DPRINTF ("sn_network_combine_bitonic_shift: Shifting by %i.\n", shift);
-    sn_network_shift (n, shift);
-  }
+  for (i = 0; i < indizes_num; i++)
+    indizes[i] = i;
 
-  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, /* {{{ */
@@ -1120,4 +1204,52 @@ sn_network_t *sn_network_unserialize (char *buffer, /* {{{ */
   return (n);
 } /* }}} sn_network_t *sn_network_unserialize */
 
+int sn_network_compare (const sn_network_t *n0, const sn_network_t *n1) /* {{{ */
+{
+  int status;
+  int i;
+
+  if (n0 == n1)
+    return (0);
+  else if (n0 == NULL)
+    return (-1);
+  else if (n1 == NULL)
+    return (1);
+
+  if (n0->inputs_num < n1->inputs_num)
+    return (-1);
+  else if (n0->inputs_num > n1->inputs_num)
+    return (1);
+
+  if (n0->stages_num < n1->stages_num)
+    return (-1);
+  else if (n0->stages_num > n1->stages_num)
+    return (1);
+
+  for (i = 0; i < n0->stages_num; i++)
+  {
+    status = sn_stage_compare (n0->stages[i], n1->stages[i]);
+    if (status != 0)
+      return (status);
+  }
+
+  return (0);
+} /* }}} int sn_network_compare */
+
+uint64_t sn_network_get_hashval (const sn_network_t *n) /* {{{ */
+{
+  uint64_t hash;
+  int i;
+
+  if (n == NULL)
+    return (0);
+
+  hash = (uint64_t) n->inputs_num;
+
+  for (i = 0; i < n->stages_num; i++)
+    hash = (hash * 104207) + sn_stage_get_hashval (n->stages[i]);
+
+  return (hash);
+} /* }}} uint64_t sn_network_get_hashval */
+
 /* vim: set sw=2 sts=2 et fdm=marker : */