X-Git-Url: https://git.octo.it/?a=blobdiff_plain;ds=sidebyside;f=src%2Fsn_network.c;h=1cc2d06fc93e96f2c607eb138dde9700ab59f567;hb=0f2d6e79cfef8b0db5372f832a301fee124039cb;hp=7aa1ae9dd078d1fd316269fcea7a0c0a6373f0d6;hpb=92bfdba1d7e2dcb716eb1fe3ac286e42301db33d;p=sort-networks.git diff --git a/src/sn_network.c b/src/sn_network.c index 7aa1ae9..1cc2d06 100644 --- a/src/sn_network.c +++ b/src/sn_network.c @@ -1,3 +1,31 @@ +/** + * collectd - src/sn_network.c + * Copyright (C) 2008 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 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. + * + * 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 + * + * Authors: + * Florian octo Forster + **/ + +#ifndef _ISOC99_SOURCE +# define _ISOC99_SOURCE +#endif +#ifndef _POSIX_C_SOURCE +# define _POSIX_C_SOURCE 200112L +#endif + #include #include #include @@ -6,6 +34,7 @@ #include #include "sn_network.h" +#include "sn_random.h" sn_network_t *sn_network_create (int inputs_num) { @@ -94,6 +123,38 @@ int sn_network_stage_remove (sn_network_t *n, int s_num) return (0); } /* int sn_network_stage_remove */ +sn_network_t *sn_network_clone (const sn_network_t *n) +{ + sn_network_t *n_copy; + int i; + + n_copy = sn_network_create (n->inputs_num); + if (n_copy == NULL) + return (NULL); + + for (i = 0; i < n->stages_num; i++) + { + sn_stage_t *s; + int status; + + s = sn_stage_clone (n->stages[i]); + if (s == NULL) + break; + + status = sn_network_stage_add (n_copy, s); + if (status != 0) + break; + } + + if (i < n->stages_num) + { + sn_network_destroy (n_copy); + return (NULL); + } + + return (n_copy); +} /* sn_network_t *sn_network_clone */ + int sn_network_show (sn_network_t *n) { int i; @@ -164,6 +225,41 @@ int sn_network_compress (sn_network_t *n) return (0); } /* int sn_network_compress */ +int sn_network_normalize (sn_network_t *n) +{ + int i; + + for (i = n->stages_num - 1; i >= 0; i--) + { + sn_stage_t *s; + int j; + + s = n->stages[i]; + + for (j = 0; j < SN_STAGE_COMP_NUM (s); j++) + { + sn_comparator_t *c; + int min; + int max; + + c = SN_STAGE_COMP_GET (s, j); + + min = c->min; + max = c->max; + + if (min > max) + { + int k; + + for (k = i; k >= 0; k--) + sn_stage_swap (n->stages[k], min, max); + } + } /* for (j = 0 .. #comparators) */ + } /* for (i = n->stages_num - 1 .. 0) */ + + return (0); +} /* int sn_network_normalize */ + int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir) { int i; @@ -263,6 +359,104 @@ static int sn_network_add_bitonic_merger (sn_network_t *n) return (0); } /* int sn_network_add_bitonic_merger */ +static int sn_network_add_odd_even_merger_recursive (sn_network_t *n, + int *indizes, int indizes_num) +{ + if (indizes_num > 2) + { + sn_comparator_t c; + sn_stage_t *s; + int indizes_half_num; + int *indizes_half; + int status; + int i; + + indizes_half_num = indizes_num / 2; + indizes_half = (int *) malloc (indizes_num * sizeof (int)); + if (indizes_half == NULL) + return (-1); + + for (i = 0; i < indizes_half_num; i++) + { + indizes_half[i] = indizes[2 * i]; + indizes_half[indizes_half_num + i] = indizes[(2 * i) + 1]; + } + + status = sn_network_add_odd_even_merger_recursive (n, + indizes_half, indizes_half_num); + if (status != 0) + { + free (indizes_half); + return (status); + } + + status = sn_network_add_odd_even_merger_recursive (n, + indizes_half + indizes_half_num, indizes_half_num); + if (status != 0) + { + free (indizes_half); + return (status); + } + + free (indizes_half); + + s = sn_stage_create (n->stages_num); + if (s == NULL) + return (-1); + + for (i = 1; i < (indizes_num - 2); i += 2) + { + c.min = indizes[i]; + c.max = indizes[i + 1]; + + sn_stage_comparator_add (s, &c); + } + + sn_network_stage_add (n, s); + } + else + { + sn_comparator_t c; + sn_stage_t *s; + + assert (indizes_num == 2); + + c.min = indizes[0]; + c.max = indizes[1]; + + s = sn_stage_create (n->stages_num); + if (s == NULL) + return (-1); + + sn_stage_comparator_add (s, &c); + sn_network_stage_add (n, s); + } + + return (0); +} /* int sn_network_add_odd_even_merger_recursive */ + +static int sn_network_add_odd_even_merger (sn_network_t *n) +{ + int *indizes; + int indizes_num; + int status; + int i; + + indizes_num = n->inputs_num; + indizes = (int *) malloc (indizes_num * sizeof (int)); + if (indizes == NULL) + return (-1); + + for (i = 0; i < indizes_num; i++) + indizes[i] = i; + + status = sn_network_add_odd_even_merger_recursive (n, + indizes, indizes_num); + + free (indizes); + return (status); +} /* int sn_network_add_bitonic_merger */ + sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1) { sn_network_t *n; @@ -304,12 +498,90 @@ sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1) sn_network_stage_add (n, s); } - sn_network_add_bitonic_merger (n); + if (sn_bounded_random (0, 1) == 0) + { + sn_network_add_bitonic_merger (n); + } + else + { + sn_network_add_odd_even_merger (n); + } + sn_network_compress (n); return (n); } /* 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]; + } + + /* 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; @@ -403,4 +675,20 @@ int sn_network_write (sn_network_t *n, FILE *fh) return (0); } /* int sn_network_write */ +int sn_network_write_file (sn_network_t *n, const char *file) +{ + int status; + FILE *fh; + + fh = fopen (file, "w"); + if (fh == NULL) + return (-1); + + status = sn_network_write (n, fh); + + fclose (fh); + + return (status); +} /* int sn_network_write_file */ + /* vim: set shiftwidth=2 softtabstop=2 : */