X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=src%2Fsn_network.c;h=4dfd6d71f143cf7f6aea9f7e0bc46d112cb64bab;hb=5ee080c95c65e7933c951a1ce143c6560d8f73f9;hp=3fdb7195559fa57b3ce475c828dc7a90e8376cc9;hpb=8e4a1e11b964e446370df12fbc2d072eb31a7fda;p=sort-networks.git

diff --git a/src/sn_network.c b/src/sn_network.c
index 3fdb719..4dfd6d7 100644
--- a/src/sn_network.c
+++ b/src/sn_network.c
@@ -19,6 +19,13 @@
  *   Florian octo Forster <octo at verplant.org>
  **/
 
+#ifndef _ISOC99_SOURCE
+# define _ISOC99_SOURCE
+#endif
+#ifndef _POSIX_C_SOURCE
+# define _POSIX_C_SOURCE 200112L
+#endif
+
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>
@@ -29,7 +36,7 @@
 #include "sn_network.h"
 #include "sn_random.h"
 
-sn_network_t *sn_network_create (int inputs_num)
+sn_network_t *sn_network_create (int inputs_num) /* {{{ */
 {
   sn_network_t *n;
 
@@ -41,9 +48,9 @@ sn_network_t *sn_network_create (int inputs_num)
   n->inputs_num = inputs_num;
 
   return (n);
-} /* sn_network_t *sn_network_create */
+} /* }}} sn_network_t *sn_network_create */
 
-void sn_network_destroy (sn_network_t *n)
+void sn_network_destroy (sn_network_t *n) /* {{{ */
 {
   if (n == NULL)
     return;
@@ -61,9 +68,9 @@ void sn_network_destroy (sn_network_t *n)
   }
 
   free (n);
-} /* void sn_network_destroy */
+} /* }}} void sn_network_destroy */
 
-int sn_network_stage_add (sn_network_t *n, sn_stage_t *s)
+int sn_network_stage_add (sn_network_t *n, sn_stage_t *s) /* {{{ */
 {
   sn_stage_t **temp;
 
@@ -78,9 +85,9 @@ int sn_network_stage_add (sn_network_t *n, sn_stage_t *s)
   n->stages_num++;
 
   return (0);
-} /* int sn_network_stage_add */
+} /* }}} int sn_network_stage_add */
 
-int sn_network_stage_remove (sn_network_t *n, int s_num)
+int sn_network_stage_remove (sn_network_t *n, int s_num) /* {{{ */
 {
   int nmemb = n->stages_num - (s_num + 1);
   sn_stage_t **temp;
@@ -114,9 +121,9 @@ int sn_network_stage_remove (sn_network_t *n, int s_num)
   }
 
   return (0);
-} /* int sn_network_stage_remove */
+} /* }}} int sn_network_stage_remove */
 
-sn_network_t *sn_network_clone (const sn_network_t *n)
+sn_network_t *sn_network_clone (const sn_network_t *n) /* {{{ */
 {
   sn_network_t *n_copy;
   int i;
@@ -146,9 +153,9 @@ sn_network_t *sn_network_clone (const sn_network_t *n)
   }
 
   return (n_copy);
-} /* sn_network_t *sn_network_clone */
+} /* }}} sn_network_t *sn_network_clone */
 
-int sn_network_show (sn_network_t *n)
+int sn_network_show (sn_network_t *n) /* {{{ */
 {
   int i;
 
@@ -156,9 +163,9 @@ int sn_network_show (sn_network_t *n)
     sn_stage_show (n->stages[i]);
 
   return (0);
-} /* int sn_network_show */
+} /* }}} int sn_network_show */
 
-int sn_network_invert (sn_network_t *n)
+int sn_network_invert (sn_network_t *n) /* {{{ */
 {
   int i;
 
@@ -166,9 +173,9 @@ int sn_network_invert (sn_network_t *n)
     sn_stage_invert (n->stages[i]);
 
   return (0);
-} /* int sn_network_invert */
+} /* }}} int sn_network_invert */
 
-int sn_network_compress (sn_network_t *n)
+int sn_network_compress (sn_network_t *n) /* {{{ */
 {
   int i;
   int j;
@@ -216,9 +223,9 @@ int sn_network_compress (sn_network_t *n)
     sn_network_stage_remove (n, n->stages_num - 1);
 
   return (0);
-} /* int sn_network_compress */
+} /* }}} int sn_network_compress */
 
-int sn_network_normalize (sn_network_t *n)
+int sn_network_normalize (sn_network_t *n) /* {{{ */
 {
   int i;
 
@@ -251,9 +258,10 @@ int sn_network_normalize (sn_network_t *n)
   } /* for (i = n->stages_num - 1 .. 0) */
 
   return (0);
-} /* int sn_network_normalize */
+} /* }}} int sn_network_normalize */
 
-int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir)
+int sn_network_cut_at (sn_network_t *n, int input, /* {{{ */
+    enum sn_network_cut_dir_e dir)
 {
   int i;
   int position = input;
@@ -286,9 +294,9 @@ int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir
   n->inputs_num--;
 
   return (0);
-} /* int sn_network_cut_at */
+} /* }}} int sn_network_cut_at */
 
-static int sn_network_add_bitonic_merger_recursive (sn_network_t *n,
+static int sn_network_add_bitonic_merger_recursive (sn_network_t *n, /* {{{ */
     int low, int num)
 {
   sn_stage_t *s;
@@ -320,9 +328,9 @@ static int sn_network_add_bitonic_merger_recursive (sn_network_t *n,
   sn_network_add_bitonic_merger_recursive (n, low + m, m);
 
   return (0);
-} /* int sn_network_add_bitonic_merger_recursive */
+} /* }}} int sn_network_add_bitonic_merger_recursive */
 
-static int sn_network_add_bitonic_merger (sn_network_t *n)
+static int sn_network_add_bitonic_merger (sn_network_t *n) /* {{{ */
 {
   sn_stage_t *s;
   int m;
@@ -350,9 +358,9 @@ static int sn_network_add_bitonic_merger (sn_network_t *n)
   sn_network_add_bitonic_merger_recursive (n, m, m);
 
   return (0);
-} /* int sn_network_add_bitonic_merger */
+} /* }}} int sn_network_add_bitonic_merger */
 
-static int sn_network_add_odd_even_merger_recursive (sn_network_t *n,
+static int sn_network_add_odd_even_merger_recursive (sn_network_t *n, /* {{{ */
     int *indizes, int indizes_num)
 {
   if (indizes_num > 2)
@@ -426,9 +434,9 @@ static int sn_network_add_odd_even_merger_recursive (sn_network_t *n,
   }
 
   return (0);
-} /* int sn_network_add_odd_even_merger_recursive */
+} /* }}} int sn_network_add_odd_even_merger_recursive */
 
-static int sn_network_add_odd_even_merger (sn_network_t *n)
+static int sn_network_add_odd_even_merger (sn_network_t *n) /* {{{ */
 {
   int *indizes;
   int indizes_num;
@@ -448,9 +456,10 @@ static int sn_network_add_odd_even_merger (sn_network_t *n)
   
   free (indizes);
   return (status);
-} /* int sn_network_add_bitonic_merger */
+} /* }}} int sn_network_add_bitonic_merger */
 
-sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1)
+sn_network_t *sn_network_combine (sn_network_t *n0, /* {{{ */
+    sn_network_t *n1)
 {
   sn_network_t *n;
   int stages_num;
@@ -503,9 +512,79 @@ sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1)
   sn_network_compress (n);
 
   return (n);
-} /* sn_network_t *sn_network_combine */
+} /* }}} sn_network_t *sn_network_combine */
+
+int sn_network_sort (sn_network_t *n, int *values) /* {{{ */
+{
+  int status;
+  int i;
+
+  status = 0;
+  for (i = 0; i < n->stages_num; i++)
+  {
+    status = sn_stage_sort (n->stages[i], values);
+    if (status != 0)
+      return (status);
+  }
+
+  return (status);
+} /* }}} int sn_network_sort */
+
+int sn_network_brute_force_check (sn_network_t *n) /* {{{ */
+{
+  int test_pattern[n->inputs_num];
+  int values[n->inputs_num];
+  int status;
+  int i;
+
+  memset (test_pattern, 0, sizeof (test_pattern));
+  while (42)
+  {
+    int previous;
+    int overflow;
+
+    /* Copy the current pattern and let the network sort it */
+    memcpy (values, test_pattern, sizeof (values));
+    status = sn_network_sort (n, values);
+    if (status != 0)
+      return (status);
+
+    /* Check if the array is now sorted. */
+    previous = values[0];
+    for (i = 1; i < n->inputs_num; i++)
+    {
+      if (previous > values[i])
+	return (1);
+      previous = values[i];
+    }
 
-sn_network_t *sn_network_read (FILE *fh)
+    /* Generate the next test pattern */
+    overflow = 1;
+    for (i = 0; i < n->inputs_num; i++)
+    {
+      if (test_pattern[i] == 0)
+      {
+	test_pattern[i] = 1;
+	overflow = 0;
+	break;
+      }
+      else
+      {
+	test_pattern[i] = 0;
+	overflow = 1;
+      }
+    }
+
+    /* Break out of the while loop if we tested all possible patterns */
+    if (overflow == 1)
+      break;
+  } /* while (42) */
+
+  /* All tests successfull */
+  return (0);
+} /* }}} int sn_network_brute_force_check */
+
+sn_network_t *sn_network_read (FILE *fh) /* {{{ */
 {
   sn_network_t *n;
   char buffer[64];
@@ -567,9 +646,9 @@ sn_network_t *sn_network_read (FILE *fh)
   }
 
   return (n);
-} /* sn_network_t *sn_network_read */
+} /* }}} sn_network_t *sn_network_read */
 
-sn_network_t *sn_network_read_file (const char *file)
+sn_network_t *sn_network_read_file (const char *file) /* {{{ */
 {
   sn_network_t *n;
   FILE *fh;
@@ -583,9 +662,9 @@ sn_network_t *sn_network_read_file (const char *file)
   fclose (fh);
 
   return (n);
-} /* sn_network_t *sn_network_read_file */
+} /* }}} sn_network_t *sn_network_read_file */
 
-int sn_network_write (sn_network_t *n, FILE *fh)
+int sn_network_write (sn_network_t *n, FILE *fh) /* {{{ */
 {
   int i;
 
@@ -596,9 +675,9 @@ int sn_network_write (sn_network_t *n, FILE *fh)
     sn_stage_write (n->stages[i], fh);
 
   return (0);
-} /* int sn_network_write */
+} /* }}} int sn_network_write */
 
-int sn_network_write_file (sn_network_t *n, const char *file)
+int sn_network_write_file (sn_network_t *n, const char *file) /* {{{ */
 {
   int status;
   FILE *fh;
@@ -612,6 +691,118 @@ int sn_network_write_file (sn_network_t *n, const char *file)
   fclose (fh);
 
   return (status);
-} /* int sn_network_write_file */
+} /* }}} int sn_network_write_file */
+
+int sn_network_serialize (sn_network_t *n, char **ret_buffer, /* {{{ */
+    size_t *ret_buffer_size)
+{
+  char *buffer;
+  size_t buffer_size;
+  int status;
+  int i;
+
+  buffer = *ret_buffer;
+  buffer_size = *ret_buffer_size;
+
+#define SNPRINTF_OR_FAIL(...) \
+  status = snprintf (buffer, buffer_size, __VA_ARGS__); \
+  if ((status < 1) || (status >= buffer_size)) \
+    return (-1); \
+  buffer += status; \
+  buffer_size -= status;
+
+  SNPRINTF_OR_FAIL ("Inputs: %i\r\n\r\n", n->inputs_num);
+
+  for (i = 0; i < n->stages_num; i++)
+  {
+    status = sn_stage_serialize (n->stages[i], &buffer, &buffer_size);
+    if (status != 0)
+      return (status);
+  }
+
+  *ret_buffer = buffer;
+  *ret_buffer_size = buffer_size;
+  return (0);
+} /* }}} int sn_network_serialize */
+
+sn_network_t *sn_network_unserialize (char *buffer, /* {{{ */
+    size_t buffer_size)
+{
+  sn_network_t *n;
+  int opt_inputs = 0;
+
+  if (buffer_size == 0)
+    return (NULL);
+
+  /* Read options first */
+  while (buffer_size > 0)
+  {
+    char *endptr;
+    char *str_key;
+    char *str_value;
+    char *line;
+    int   line_len;
+
+    line = buffer;
+    endptr = strchr (buffer, '\n');
+    if (endptr == NULL)
+      return (NULL);
+
+    *endptr = 0;
+    endptr++;
+    buffer = endptr;
+    line_len = strlen (line);
+
+    if ((line_len > 0) && (line[line_len - 1] == '\r'))
+    {
+      line[line_len - 1] = 0;
+      line_len--;
+    }
+
+    if (line_len == 0)
+      break;
+
+    str_key = line;
+    str_value = strchr (line, ':');
+    if (str_value == NULL)
+    {
+      printf ("Cannot parse line: %s\n", line);
+      continue;
+    }
+
+    *str_value = '\0'; str_value++;
+    while ((*str_value != '\0') && (isspace (*str_value) != 0))
+      str_value++;
+
+    if (strcasecmp ("Inputs", str_key) == 0)
+      opt_inputs = atoi (str_value);
+    else
+      printf ("Unknown key: %s\n", str_key);
+  } /* while (fgets) */
+
+  if (opt_inputs < 2)
+    return (NULL);
+
+  n = sn_network_create (opt_inputs);
+
+  while (42)
+  {
+    sn_stage_t *s;
+
+    s = sn_stage_unserialize (&buffer, &buffer_size);
+    if (s == NULL)
+      break;
+
+    sn_network_stage_add (n, s);
+  }
+
+  if (SN_NETWORK_STAGE_NUM (n) < 1)
+  {
+    sn_network_destroy (n);
+    return (NULL);
+  }
+
+  return (n);
+} /* }}} sn_network_t *sn_network_unserialize */
 
-/* vim: set shiftwidth=2 softtabstop=2 : */
+/* vim: set sw=2 sts=2 et fdm=marker : */