src/sn_network.c: Fix the Pairwise Sorting network for arbitrary n.

[sort-networks.git] / src / sn_network.c

diff --git a/src/sn_network.c b/src/sn_network.c
index 0fdaaa3..90a86cf 100644 (file)
--- a/src/sn_network.c
+++ b/src/sn_network.c
@@ -223,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);
@@ -242,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);
@@ -270,6 +278,7 @@ 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);
@@ -285,6 +294,9 @@ int sn_network_network_add (sn_network_t *n, sn_network_t *other) /* {{{ */
 
   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);
@@ -423,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) /* {{{ */
@@ -550,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;
@@ -1171,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 : */