--- /dev/null
+CC = gcc
+CFLAGS = -Wall -Werror -std=c99 -O3
+
+all: sn-cut sn-merge sn-show
+
+sn_comparator.o: sn_comparator.c sn_comparator.h
+
+sn_stage.o: sn_stage.c sn_stage.h sn_comparator.h
+
+sn_network.o: sn_network.c sn_network.h sn_stage.h sn_comparator.h
+
+sn-cut: sn-cut.c sn_network.o sn_stage.o sn_comparator.o
+
+sn-merge: sn-merge.c sn_network.o sn_stage.o sn_comparator.o
+
+sn-show: sn-show.c sn_network.o sn_stage.o sn_comparator.o
+
--- /dev/null
+#include <stdlib.h>
+#include <stdio.h>
+#include <strings.h>
+
+#include "sn_network.h"
+
+void exit_usage (const char *name)
+{
+ printf ("%s <position> <min|max>\n", name);
+ exit (1);
+}
+
+int main (int argc, char **argv)
+{
+ sn_network_t *n;
+
+ int pos = 0;
+ enum sn_network_cut_dir_e dir = DIR_MIN;
+
+ if (argc != 3)
+ exit_usage (argv[0]);
+
+ pos = atoi (argv[1]);
+ if (strcasecmp ("max", argv[2]) == 0)
+ dir = DIR_MAX;
+
+ n = sn_network_read (stdin);
+ if (n == NULL)
+ {
+ printf ("n == NULL!\n");
+ return (1);
+ }
+
+ sn_network_cut_at (n, pos, dir);
+ sn_network_compress (n);
+
+ sn_network_write (n, stdout);
+
+ return (0);
+} /* int main */
+
+/* vim: set shiftwidth=2 softtabstop=2 : */
--- /dev/null
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "sn_network.h"
+
+void exit_usage (const char *name)
+{
+ printf ("%s <file0> <file1>\n", name);
+ exit (1);
+} /* void exit_usage */
+
+int main (int argc, char **argv)
+{
+ sn_network_t *n0;
+ sn_network_t *n1;
+ sn_network_t *n;
+
+ if (argc != 3)
+ exit_usage (argv[0]);
+
+ n0 = sn_network_read_file (argv[1]);
+ if (n0 == NULL)
+ {
+ printf ("n0 == NULL\n");
+ return (1);
+ }
+
+ n1 = sn_network_read_file (argv[2]);
+ if (n1 == NULL)
+ {
+ printf ("n1 == NULL\n");
+ return (1);
+ }
+
+ n = sn_network_combine (n0, n1);
+ sn_network_destroy (n0);
+ sn_network_destroy (n1);
+
+ sn_network_write (n, stdout);
+
+ return (0);
+} /* int main */
+
+/* vim: set shiftwidth=2 softtabstop=2 : */
--- /dev/null
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "sn_network.h"
+
+int main (int argc, char **argv)
+{
+ sn_network_t *n;
+ FILE *fh = NULL;
+
+ if (argc == 1)
+ fh = stdin;
+ else if (argc == 2)
+ fh = fopen (argv[1], "r");
+
+ if (fh == NULL)
+ {
+ printf ("fh == NULL!\n");
+ return (1);
+ }
+
+ n = sn_network_read (fh);
+
+ if (n == NULL)
+ {
+ printf ("n == NULL!\n");
+ return (1);
+ }
+
+ sn_network_show (n);
+
+ return (0);
+} /* int main */
+
+/* vim: set shiftwidth=2 softtabstop=2 : */
--- /dev/null
+#include <stdlib.h>
+#include <string.h>
+
+#include "sn_comparator.h"
+
+sn_comparator_t *sn_comparator_create (int min, int max)
+{
+ sn_comparator_t *c;
+
+ c = (sn_comparator_t *) malloc (sizeof (sn_comparator_t));
+ if (c == NULL)
+ return (NULL);
+ memset (c, '\0', sizeof (sn_comparator_t));
+
+ c->min = min;
+ c->max = max;
+
+ return (c);
+} /* sn_comparator_t *sn_comparator_create */
+
+void sn_comparator_destroy (sn_comparator_t *c)
+{
+ if (c != NULL)
+ free (c);
+} /* void sn_comparator_destroy */
+
+void sn_comparator_invert (sn_comparator_t *c)
+{
+ int max = c->min;
+ int min = c->max;
+
+ c->min = min;
+ c->max = max;
+} /* void sn_comparator_invert */
+
+void sn_comparator_swap (sn_comparator_t *c, int con0, int con1)
+{
+ if (c->min == con0)
+ {
+ c->min = con1;
+ }
+ else if (c->min == con1)
+ {
+ c->min = con0;
+ }
+
+ if (c->max == con0)
+ {
+ c->max = con1;
+ }
+ else if (c->max == con1)
+ {
+ c->max = con0;
+ }
+} /* void sn_comparator_swap */
+
+int sn_comparator_compare (const void *v0, const void *v1)
+{
+ sn_comparator_t *c0 = (sn_comparator_t *) v0;
+ sn_comparator_t *c1 = (sn_comparator_t *) v1;
+
+ if (SN_COMP_LEFT (c0) < SN_COMP_LEFT (c1))
+ return (-1);
+ else if (SN_COMP_LEFT (c0) > SN_COMP_LEFT (c1))
+ return (1);
+ else if (SN_COMP_RIGHT (c0) < SN_COMP_RIGHT (c1))
+ return (-1);
+ else if (SN_COMP_RIGHT (c0) > SN_COMP_RIGHT (c1))
+ return (1);
+ else
+ return (0);
+} /* int sn_comparator_compare */
+
+/* vim: set shiftwidth=2 softtabstop=2 : */
--- /dev/null
+#ifndef SN_COMPARATOR_H
+#define SN_COMPARATOR_H 1
+
+struct sn_comparator_s
+{
+ int min;
+ int max;
+};
+typedef struct sn_comparator_s sn_comparator_t;
+
+#define SN_COMP_LEFT(c) (((c)->min < (c)->max) ? (c)->min : (c)->max)
+#define SN_COMP_RIGHT(c) (((c)->min > (c)->max) ? (c)->min : (c)->max)
+#define SN_COMP_MIN(c) (c)->min
+#define SN_COMP_MAX(c) (c)->max
+
+sn_comparator_t *sn_comparator_create (int min, int max);
+void sn_comparator_destroy (sn_comparator_t *c);
+void sn_comparator_invert (sn_comparator_t *c);
+void sn_comparator_swap (sn_comparator_t *c, int con0, int con1);
+
+int sn_comparator_compare (const void *, const void *);
+
+#endif /* SN_COMPARATOR_H */
+
+/* vim: set shiftwidth=2 softtabstop=2 : */
--- /dev/null
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <strings.h>
+#include <ctype.h>
+#include <assert.h>
+
+#include "sn_network.h"
+
+sn_network_t *sn_network_create (int inputs_num)
+{
+ sn_network_t *n;
+
+ n = (sn_network_t *) malloc (sizeof (sn_network_t));
+ if (n == NULL)
+ return (NULL);
+ memset (n, '\0', sizeof (sn_network_t));
+
+ n->inputs_num = inputs_num;
+
+ return (n);
+} /* sn_network_t *sn_network_create */
+
+void sn_network_destroy (sn_network_t *n)
+{
+ if (n == NULL)
+ return;
+
+ if (n->stages != NULL)
+ {
+ int i;
+ for (i = 0; i < n->stages_num; i++)
+ {
+ sn_stage_destroy (n->stages[i]);
+ n->stages[i] = NULL;
+ }
+ n->stages = NULL;
+ }
+
+ free (n);
+} /* void sn_network_destroy */
+
+int sn_network_stage_add (sn_network_t *n, sn_stage_t *s)
+{
+ sn_stage_t **temp;
+
+ temp = (sn_stage_t **) realloc (n->stages, (n->stages_num + 1)
+ * sizeof (sn_stage_t *));
+ if (temp == NULL)
+ return (-1);
+
+ n->stages = temp;
+ SN_STAGE_DEPTH (s) = n->stages_num;
+ n->stages[n->stages_num] = s;
+ n->stages_num++;
+
+ return (0);
+} /* int sn_network_stage_add */
+
+int sn_network_stage_remove (sn_network_t *n, int s_num)
+{
+ int nmemb = n->stages_num - (s_num + 1);
+ sn_stage_t **temp;
+
+ assert (s_num < n->stages_num);
+
+ sn_stage_destroy (n->stages[s_num]);
+ n->stages[s_num] = NULL;
+
+ if (nmemb > 0)
+ memmove (n->stages + s_num, n->stages + (s_num + 1),
+ nmemb * sizeof (sn_stage_t *));
+ n->stages_num--;
+
+ /* Free the unused memory */
+ temp = (sn_stage_t **) realloc (n->stages,
+ n->stages_num * sizeof (sn_stage_t *));
+ if (temp == NULL)
+ return (-1);
+ n->stages = temp;
+
+ return (0);
+} /* int sn_network_stage_remove */
+
+int sn_network_show (sn_network_t *n)
+{
+ int i;
+
+ for (i = 0; i < n->stages_num; i++)
+ sn_stage_show (n->stages[i]);
+
+ return (0);
+} /* int sn_network_show */
+
+int sn_network_invert (sn_network_t *n)
+{
+ int i;
+
+ for (i = 0; i < n->stages_num; i++)
+ sn_stage_invert (n->stages[i]);
+
+ return (0);
+} /* int sn_network_invert */
+
+int sn_network_compress (sn_network_t *n)
+{
+ int i;
+ int j;
+ int k;
+
+ for (i = 1; i < n->stages_num; i++)
+ {
+ sn_stage_t *s;
+
+ s = n->stages[i];
+
+ for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
+ {
+ sn_comparator_t *c = SN_STAGE_COMP_GET (s, j);
+ int move_to = i;
+
+ for (k = i - 1; k >= 0; k--)
+ {
+ int conflict;
+
+ conflict = sn_stage_comparator_check_conflict (n->stages[k], c);
+ if (conflict == 0)
+ {
+ move_to = k;
+ continue;
+ }
+
+ if (conflict == 2)
+ move_to = -1;
+ break;
+ }
+
+ if (move_to < i)
+ {
+ if (move_to >= 0)
+ sn_stage_comparator_add (n->stages[move_to], c);
+ sn_stage_comparator_remove (s, j);
+ j--;
+ }
+ }
+ }
+
+ return (0);
+} /* int sn_network_compress */
+
+int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir)
+{
+ int i;
+ int position = input;
+
+ for (i = 0; i < n->stages_num; i++)
+ {
+ sn_stage_t *s;
+ int new_position;
+
+ s = n->stages[i];
+ new_position = sn_stage_cut_at (s, position, dir);
+
+ if (position != new_position)
+ {
+ int j;
+
+ for (j = 0; j < i; j++)
+ sn_stage_swap (n->stages[j], position, new_position);
+ }
+
+ position = new_position;
+ }
+
+ assert (((dir == DIR_MIN) && (position == 0))
+ || ((dir == DIR_MAX) && (position == (n->inputs_num - 1))));
+
+
+ for (i = 0; i < n->stages_num; i++)
+ sn_stage_remove_input (n->stages[i], position);
+
+ n->inputs_num--;
+
+ return (0);
+} /* int sn_network_cut_at */
+
+static int sn_network_add_bitonic_merger_recursive (sn_network_t *n,
+ int low, int num)
+{
+ sn_stage_t *s;
+ int m;
+ int i;
+
+ s = sn_stage_create (n->stages_num);
+ if (s == NULL)
+ return (-1);
+
+ if (num == 1)
+ return (0);
+
+ m = num / 2;
+
+ for (i = low; i < (low + m); i++)
+ {
+ sn_comparator_t c;
+
+ c.min = i;
+ c.max = i + m;
+
+ sn_stage_comparator_add (s, &c);
+ }
+
+ 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)
+{
+ 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;
+
+ for (i = 0; i < m; i++)
+ {
+ sn_comparator_t c;
+
+ c.min = i;
+ c.max = n->inputs_num - (i + 1);
+
+ sn_stage_comparator_add (s, &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);
+
+ return (0);
+} /* int sn_network_add_bitonic_merger */
+
+sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1)
+{
+ sn_network_t *n;
+ int stages_num;
+ int i;
+ int j;
+
+ stages_num = (n0->stages_num > n1->stages_num)
+ ? n0->stages_num
+ : n1->stages_num;
+
+ n = sn_network_create (n0->inputs_num + n1->inputs_num);
+ if (n == NULL)
+ return (NULL);
+
+ for (i = 0; i < stages_num; i++)
+ {
+ sn_stage_t *s = sn_stage_create (i);
+
+ if (i < n0->stages_num)
+ for (j = 0; j < SN_STAGE_COMP_NUM (n0->stages[i]); j++)
+ {
+ sn_comparator_t *c = SN_STAGE_COMP_GET (n0->stages[i], j);
+ sn_stage_comparator_add (s, c);
+ }
+
+ if (i < n1->stages_num)
+ for (j = 0; j < SN_STAGE_COMP_NUM (n1->stages[i]); j++)
+ {
+ sn_comparator_t *c_orig = SN_STAGE_COMP_GET (n1->stages[i], j);
+ sn_comparator_t c_copy;
+
+ SN_COMP_MIN(&c_copy) = SN_COMP_MIN(c_orig) + n0->inputs_num;
+ SN_COMP_MAX(&c_copy) = SN_COMP_MAX(c_orig) + n0->inputs_num;
+
+ sn_stage_comparator_add (s, &c_copy);
+ }
+
+ sn_network_stage_add (n, s);
+ }
+
+ sn_network_add_bitonic_merger (n);
+ sn_network_compress (n);
+
+ return (n);
+} /* sn_network_t *sn_network_combine */
+
+sn_network_t *sn_network_read (FILE *fh)
+{
+ sn_network_t *n;
+ char buffer[64];
+
+ int opt_inputs = 0;
+
+ while (fgets (buffer, sizeof (buffer), fh) != NULL)
+ {
+ char *str_key = buffer;
+ char *str_value = NULL;
+ int buffer_len = strlen (buffer);
+
+ while ((buffer_len > 0) && ((buffer[buffer_len - 1] == '\n')
+ || (buffer[buffer_len - 1] == '\r')))
+ {
+ buffer_len--;
+ buffer[buffer_len] = '\0';
+ }
+ if (buffer_len == 0)
+ break;
+
+ str_value = strchr (buffer, ':');
+ if (str_value == NULL)
+ {
+ printf ("Cannot parse line: %s\n", buffer);
+ 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_read (fh);
+ 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_read */
+
+sn_network_t *sn_network_read_file (const char *file)
+{
+ sn_network_t *n;
+ FILE *fh;
+
+ fh = fopen (file, "r");
+ if (fh == NULL)
+ return (NULL);
+
+ n = sn_network_read (fh);
+
+ fclose (fh);
+
+ return (n);
+} /* sn_network_t *sn_network_read_file */
+
+int sn_network_write (sn_network_t *n, FILE *fh)
+{
+ int i;
+
+ fprintf (fh, "Inputs: %i\n", n->inputs_num);
+ fprintf (fh, "\n");
+
+ for (i = 0; i < n->stages_num; i++)
+ sn_stage_write (n->stages[i], fh);
+
+ return (0);
+} /* int sn_network_write */
+
+/* vim: set shiftwidth=2 softtabstop=2 : */
--- /dev/null
+#ifndef SN_NETWORK_H
+#define SN_NETWORK_H 1
+
+#include <stdio.h>
+
+#include "sn_comparator.h"
+#include "sn_stage.h"
+
+struct sn_network_s
+{
+ int inputs_num;
+ sn_stage_t **stages;
+ int stages_num;
+};
+typedef struct sn_network_s sn_network_t;
+
+#define SN_NETWORK_STAGE_NUM(n) (n)->stages_num
+#define SN_NETWORK_STAGE_GET(n,i) ((n)->stages[i])
+
+sn_network_t *sn_network_create (int inputs_num);
+void sn_network_destroy (sn_network_t *n);
+
+int sn_network_stage_add (sn_network_t *n, sn_stage_t *s);
+int sn_network_stage_remove (sn_network_t *n, int s_num);
+
+int sn_network_show (sn_network_t *n);
+int sn_network_invert (sn_network_t *n);
+int sn_network_compress (sn_network_t *n);
+
+int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir);
+sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1);
+
+sn_network_t *sn_network_read (FILE *fh);
+sn_network_t *sn_network_read_file (const char *file);
+int sn_network_write (sn_network_t *n, FILE *fh);
+
+#endif /* SN_NETWORK_H */
+
+/* vim: set shiftwidth=2 softtabstop=2 : */
--- /dev/null
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+#include "sn_comparator.h"
+#include "sn_stage.h"
+
+sn_stage_t *sn_stage_create (int depth)
+{
+ sn_stage_t *s;
+
+ s = (sn_stage_t *) malloc (sizeof (sn_stage_t));
+ if (s == NULL)
+ return (NULL);
+ memset (s, '\0', sizeof (sn_stage_t));
+
+ s->depth = depth;
+
+ return (s);
+} /* sn_stage_t *sn_stage_create */
+
+void sn_stage_destroy (sn_stage_t *s)
+{
+ if (s == NULL)
+ return;
+ if (s->comparators != NULL)
+ free (s->comparators);
+ free (s);
+} /* void sn_stage_destroy */
+
+int sn_stage_comparator_add (sn_stage_t *s, const sn_comparator_t *c)
+{
+ sn_comparator_t *temp;
+ int i;
+
+ temp = (sn_comparator_t *) realloc (s->comparators,
+ (s->comparators_num + 1) * sizeof (sn_comparator_t));
+ if (temp == NULL)
+ return (-1);
+ s->comparators = temp;
+ temp = NULL;
+
+ for (i = 0; i < s->comparators_num; i++)
+ if (sn_comparator_compare (c, s->comparators + i) <= 0)
+ break;
+
+ /* Insert the elements in ascending order */
+ assert (i <= s->comparators_num);
+ if (i < s->comparators_num)
+ {
+ int nmemb = s->comparators_num - i;
+ memmove (s->comparators + (i + 1), s->comparators + i,
+ nmemb * sizeof (sn_comparator_t));
+ }
+ memcpy (s->comparators + i, c, sizeof (sn_comparator_t));
+ s->comparators_num++;
+
+ return (0);
+} /* int sn_stage_comparator_add */
+
+int sn_stage_comparator_remove (sn_stage_t *s, int c_num)
+{
+ int nmemb = s->comparators_num - (c_num + 1);
+ sn_comparator_t *temp;
+
+ assert (c_num < s->comparators_num);
+
+ if (nmemb > 0)
+ memmove (s->comparators + c_num, s->comparators + (c_num + 1),
+ nmemb * sizeof (sn_comparator_t));
+ s->comparators_num--;
+
+ /* Free the unused memory */
+ temp = (sn_comparator_t *) realloc (s->comparators,
+ s->comparators_num * sizeof (sn_comparator_t));
+ if (temp == NULL)
+ return (-1);
+ s->comparators = temp;
+
+ return (0);
+} /* int sn_stage_comparator_remove */
+
+int sn_stage_comparator_check_conflict (sn_stage_t *s, const sn_comparator_t *c0)
+{
+ int i;
+
+ for (i = 0; i < s->comparators_num; i++)
+ {
+ sn_comparator_t *c1 = s->comparators + i;
+ if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
+ || (SN_COMP_MIN(c0) == SN_COMP_MAX(c1))
+ || (SN_COMP_MAX(c0) == SN_COMP_MIN(c1))
+ || (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
+ {
+ if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
+ && (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
+ return (2);
+ else
+ return (1);
+ }
+ }
+
+ return (0);
+} /* int sn_stage_comparator_check_conflict */
+
+int sn_stage_show (sn_stage_t *s)
+{
+ int lines[s->comparators_num];
+ int right[s->comparators_num];
+ int lines_used = 0;
+ int i;
+ int j;
+ int k;
+
+
+ for (i = 0; i < s->comparators_num; i++)
+ {
+ lines[i] = -1;
+ right[i] = -1;
+ }
+
+ for (i = 0; i < s->comparators_num; i++)
+ {
+ int j;
+ sn_comparator_t *c = s->comparators + i;
+
+ for (j = 0; j < lines_used; j++)
+ if (SN_COMP_LEFT (c) > right[j])
+ break;
+
+ lines[i] = j;
+ right[j] = SN_COMP_RIGHT (c);
+ if (j >= lines_used)
+ lines_used = j + 1;
+ }
+
+ for (i = 0; i < lines_used; i++)
+ {
+ printf ("%3i: ", s->depth);
+
+ for (j = 0; j <= right[i]; j++)
+ {
+ int on_elem = 0;
+ int line_after = 0;
+
+ for (k = 0; k < s->comparators_num; k++)
+ {
+ sn_comparator_t *c = s->comparators + k;
+
+ /* Check if this comparator is displayed on another line */
+ if (lines[k] != i)
+ continue;
+
+ if (j == SN_COMP_MIN (c))
+ on_elem = -1;
+ else if (j == SN_COMP_MAX (c))
+ on_elem = 1;
+
+ if ((j >= SN_COMP_LEFT (c)) && (j < SN_COMP_RIGHT (c)))
+ line_after = 1;
+
+ if ((on_elem != 0) || (line_after != 0))
+ break;
+ }
+
+ if (on_elem == 0)
+ {
+ if (line_after == 0)
+ printf (" ");
+ else
+ printf ("-----");
+ }
+ else if (on_elem == -1)
+ {
+ if (line_after == 0)
+ printf ("-! ");
+ else
+ printf (" !---");
+ }
+ else
+ {
+ if (line_after == 0)
+ printf ("-> ");
+ else
+ printf (" <---");
+ }
+ } /* for (columns) */
+
+ printf ("\n");
+ } /* for (lines) */
+
+ return (0);
+} /* int sn_stage_show */
+
+int sn_stage_invert (sn_stage_t *s)
+{
+ int i;
+
+ for (i = 0; i < s->comparators_num; i++)
+ sn_comparator_invert (s->comparators + i);
+
+ return (0);
+} /* int sn_stage_invert */
+
+int sn_stage_swap (sn_stage_t *s, int con0, int con1)
+{
+ int i;
+
+ for (i = 0; i < s->comparators_num; i++)
+ sn_comparator_swap (s->comparators + i, con0, con1);
+
+ return (0);
+} /* int sn_stage_swap */
+
+int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir)
+{
+ int new_position = input;
+ int i;
+
+ for (i = 0; i < s->comparators_num; i++)
+ {
+ sn_comparator_t *c = s->comparators + i;
+
+ if ((SN_COMP_MIN (c) != input) && (SN_COMP_MAX (c) != input))
+ continue;
+
+ if ((dir == DIR_MIN) && (SN_COMP_MAX (c) == input))
+ {
+ new_position = SN_COMP_MIN (c);
+ }
+ else if ((dir == DIR_MAX) && (SN_COMP_MIN (c) == input))
+ {
+ new_position = SN_COMP_MAX (c);
+ }
+ break;
+ }
+
+ /*
+ if (i < s->comparators_num)
+ sn_stage_comparator_remove (s, i);
+ */
+
+ return (new_position);
+} /* int sn_stage_cut_at */
+
+int sn_stage_remove_input (sn_stage_t *s, int input)
+{
+ int i;
+
+ for (i = 0; i < s->comparators_num; i++)
+ {
+ sn_comparator_t *c = s->comparators + i;
+
+ if ((SN_COMP_MIN (c) == input) || (SN_COMP_MAX (c) == input))
+ {
+ sn_stage_comparator_remove (s, i);
+ i--;
+ continue;
+ }
+
+ if (SN_COMP_MIN (c) > input)
+ SN_COMP_MIN (c) = SN_COMP_MIN (c) - 1;
+ if (SN_COMP_MAX (c) > input)
+ SN_COMP_MAX (c) = SN_COMP_MAX (c) - 1;
+ }
+
+ return (0);
+}
+
+sn_stage_t *sn_stage_read (FILE *fh)
+{
+ sn_stage_t *s;
+ char buffer[64];
+ char *buffer_ptr;
+
+ s = sn_stage_create (0);
+ if (s == NULL)
+ return (NULL);
+
+ while (fgets (buffer, sizeof (buffer), fh) != NULL)
+ {
+ char *endptr;
+ sn_comparator_t c;
+
+ if ((buffer[0] == '\0') || (buffer[0] == '\n') || (buffer[0] == '\r'))
+ break;
+
+ buffer_ptr = buffer;
+ endptr = NULL;
+ c.min = (int) strtol (buffer_ptr, &endptr, 0);
+ if (buffer_ptr == endptr)
+ continue;
+
+ buffer_ptr = endptr;
+ endptr = NULL;
+ c.max = (int) strtol (buffer_ptr, &endptr, 0);
+ if (buffer_ptr == endptr)
+ continue;
+
+ sn_stage_comparator_add (s, &c);
+ }
+
+ if (s->comparators_num == 0)
+ {
+ sn_stage_destroy (s);
+ return (NULL);
+ }
+
+ return (s);
+} /* sn_stage_t *sn_stage_read */
+
+int sn_stage_write (sn_stage_t *s, FILE *fh)
+{
+ int i;
+
+ if (s->comparators_num <= 0)
+ return (0);
+
+ for (i = 0; i < s->comparators_num; i++)
+ fprintf (fh, "%i %i\n",
+ SN_COMP_MIN (s->comparators + i),
+ SN_COMP_MAX (s->comparators + i));
+ fprintf (fh, "\n");
+
+ return (0);
+} /* int sn_stage_write */
+
+/* vim: set shiftwidth=2 softtabstop=2 : */
--- /dev/null
+#ifndef SN_STAGE_H
+#define SN_STAGE_H 1
+
+#include <stdio.h>
+
+#include "sn_comparator.h"
+
+struct sn_stage_s
+{
+ int depth;
+ sn_comparator_t *comparators;
+ int comparators_num;
+};
+typedef struct sn_stage_s sn_stage_t;
+
+enum sn_network_cut_dir_e
+{
+ DIR_MIN,
+ DIR_MAX
+};
+
+#define SN_STAGE_DEPTH(s) (s)->depth
+#define SN_STAGE_COMP_NUM(s) (s)->comparators_num
+#define SN_STAGE_COMP_GET(s,n) ((s)->comparators + (n))
+
+sn_stage_t *sn_stage_create (int depth);
+void sn_stage_destroy (sn_stage_t *s);
+
+int sn_stage_comparator_add (sn_stage_t *s, const sn_comparator_t *c);
+int sn_stage_comparator_remove (sn_stage_t *s, int c_num);
+int sn_stage_comparator_check_conflict (sn_stage_t *s, const sn_comparator_t *c);
+
+int sn_stage_show (sn_stage_t *s);
+int sn_stage_invert (sn_stage_t *s);
+int sn_stage_swap (sn_stage_t *s, int con0, int con1);
+int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir);
+int sn_stage_remove_input (sn_stage_t *s, int input);
+
+sn_stage_t *sn_stage_read (FILE *fh);
+int sn_stage_write (sn_stage_t *s, FILE *fh);
+
+#endif /* SN_STAGE_H */
+
+/* vim: set shiftwidth=2 softtabstop=2 : */
projects / sort-networks.git / commitdiff