From 02dd5a8e9890f7b16b950db238eeff42a57e9142 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Fri, 1 Feb 2008 16:52:55 +0100 Subject: [PATCH] Imported the initial C files that make up a decent sorting network toolkit already. The files built up to know are: - sn-cut: Does a min/max cut on a given input. - sn-merge: Merges two networks (files) by appending a bitonic merge. - sn-show: Pretty-prints a network to stdout. --- src/Makefile | 17 +++ src/sn-cut.c | 42 ++++++ src/sn-merge.c | 44 ++++++ src/sn-show.c | 35 +++++ src/sn_comparator.c | 74 ++++++++++ src/sn_comparator.h | 25 ++++ src/sn_network.c | 391 ++++++++++++++++++++++++++++++++++++++++++++++++++++ src/sn_network.h | 39 ++++++ src/sn_stage.c | 328 +++++++++++++++++++++++++++++++++++++++++++ src/sn_stage.h | 44 ++++++ 10 files changed, 1039 insertions(+) create mode 100644 src/Makefile create mode 100644 src/sn-cut.c create mode 100644 src/sn-merge.c create mode 100644 src/sn-show.c create mode 100644 src/sn_comparator.c create mode 100644 src/sn_comparator.h create mode 100644 src/sn_network.c create mode 100644 src/sn_network.h create mode 100644 src/sn_stage.c create mode 100644 src/sn_stage.h diff --git a/src/Makefile b/src/Makefile new file mode 100644 index 0000000..bff684f --- /dev/null +++ b/src/Makefile @@ -0,0 +1,17 @@ +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 + diff --git a/src/sn-cut.c b/src/sn-cut.c new file mode 100644 index 0000000..1227723 --- /dev/null +++ b/src/sn-cut.c @@ -0,0 +1,42 @@ +#include +#include +#include + +#include "sn_network.h" + +void exit_usage (const char *name) +{ + printf ("%s \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 : */ diff --git a/src/sn-merge.c b/src/sn-merge.c new file mode 100644 index 0000000..4649389 --- /dev/null +++ b/src/sn-merge.c @@ -0,0 +1,44 @@ +#include +#include + +#include "sn_network.h" + +void exit_usage (const char *name) +{ + printf ("%s \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 : */ diff --git a/src/sn-show.c b/src/sn-show.c new file mode 100644 index 0000000..cd6ea3d --- /dev/null +++ b/src/sn-show.c @@ -0,0 +1,35 @@ +#include +#include + +#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 : */ diff --git a/src/sn_comparator.c b/src/sn_comparator.c new file mode 100644 index 0000000..6bfc611 --- /dev/null +++ b/src/sn_comparator.c @@ -0,0 +1,74 @@ +#include +#include + +#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 : */ diff --git a/src/sn_comparator.h b/src/sn_comparator.h new file mode 100644 index 0000000..dcdc136 --- /dev/null +++ b/src/sn_comparator.h @@ -0,0 +1,25 @@ +#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 : */ diff --git a/src/sn_network.c b/src/sn_network.c new file mode 100644 index 0000000..07d811d --- /dev/null +++ b/src/sn_network.c @@ -0,0 +1,391 @@ +#include +#include +#include +#include +#include +#include + +#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 : */ diff --git a/src/sn_network.h b/src/sn_network.h new file mode 100644 index 0000000..7e13973 --- /dev/null +++ b/src/sn_network.h @@ -0,0 +1,39 @@ +#ifndef SN_NETWORK_H +#define SN_NETWORK_H 1 + +#include + +#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 : */ diff --git a/src/sn_stage.c b/src/sn_stage.c new file mode 100644 index 0000000..0cfabe9 --- /dev/null +++ b/src/sn_stage.c @@ -0,0 +1,328 @@ +#include +#include +#include + +#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 : */ diff --git a/src/sn_stage.h b/src/sn_stage.h new file mode 100644 index 0000000..465a4c2 --- /dev/null +++ b/src/sn_stage.h @@ -0,0 +1,44 @@ +#ifndef SN_STAGE_H +#define SN_STAGE_H 1 + +#include + +#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 : */ -- 2.11.0