From: Florian Forster Date: Mon, 17 May 2010 07:53:00 +0000 (+0200) Subject: src/sn_network.[ch]: Rename the bitonic combine method. X-Git-Tag: v1.0.0~45 X-Git-Url: https://git.octo.it/?p=sort-networks.git;a=commitdiff_plain;h=f3635d61e91198d4a40126bab3e4a3c1b1e49724 src/sn_network.[ch]: Rename the bitonic combine method. The sn-merge utility has been improved to accept the "-b" option and use the bitonic variant if supplied. --- diff --git a/src/sn-batcher.c b/src/sn-batcher.c index ee3a42a..13f6d8e 100644 --- a/src/sn-batcher.c +++ b/src/sn-batcher.c @@ -75,11 +75,11 @@ static sn_network_t *create_batcher_sort (size_t inputs_num) if (n_small == NULL) return (NULL); - n = sn_network_combine_bitonic (n_small, n_small); + n = sn_network_combine_bitonic_merge (n_small, n_small); if (n == NULL) { sn_network_destroy (n_small); - fprintf (stderr, "create_batcher_sort: sn_network_combine_bitonic " + fprintf (stderr, "create_batcher_sort: sn_network_combine_bitonic_merge " "failed.\n"); return (NULL); } diff --git a/src/sn-evolution.c b/src/sn-evolution.c index 2f3fba3..71f0c67 100644 --- a/src/sn-evolution.c +++ b/src/sn-evolution.c @@ -229,7 +229,7 @@ static int create_offspring (void) assert (p1 != NULL); /* combine the two parents */ - n = sn_network_combine (p0, p1, inputs_num_is_power_of_two); + n = sn_network_combine (p0, p1); sn_network_destroy (p0); sn_network_destroy (p1); diff --git a/src/sn-merge.c b/src/sn-merge.c index fbd5090..f9d0440 100644 --- a/src/sn-merge.c +++ b/src/sn-merge.c @@ -19,23 +19,76 @@ * Florian octo Forster **/ -#ifndef _ISOC99_SOURCE -# define _ISOC99_SOURCE -#endif -#ifndef _POSIX_C_SOURCE -# define _POSIX_C_SOURCE 200112L -#endif +#include "config.h" #include #include +#include +#include #include "sn_network.h" -void exit_usage (const char *name) +static _Bool use_bitonic = 0; +static const char *file0 = NULL; +static const char *file1 = NULL; + +static void exit_usage (void) /* {{{ */ +{ + printf ("sn-merge [options] \n" + "\n" + "Options:\n" + " -b Use the bitonic merger.\n" + " -o Use the odd-even merger. (default)\n" + " -h Display this help and exit.\n" + "\n"); + exit (EXIT_FAILURE); +} /* }}} void exit_usage */ + +static int read_options (int argc, char **argv) /* {{{ */ { - printf ("%s \n", name); - exit (1); -} /* void exit_usage */ + int option; + + while ((option = getopt (argc, argv, "boh")) != -1) + { + switch (option) + { + case 'b': + use_bitonic = 1; + break; + + case 'o': + use_bitonic = 0; + break; + + case 'h': + default: + exit_usage (); + } + } + + if ((argc - optind) != 2) + exit_usage (); + + file0 = argv[optind]; + file1 = argv[optind + 1]; + + if ((file0 == NULL) || (file1 == NULL)) + exit_usage (); + + return (0); +} /* }}} int read_options */ + +static _Bool is_power_of_two (int n) +{ + if (n < 1) + return (0); + else if ((n == 1) || (n == 2)) + return (1); + else if ((n % 2) != 0) + return (0); + else + return (is_power_of_two (n >> 1)); +} /* _Bool is_power_of_two */ int main (int argc, char **argv) { @@ -43,24 +96,54 @@ int main (int argc, char **argv) sn_network_t *n1; sn_network_t *n; - if (argc != 3) - exit_usage (argv[0]); + read_options (argc, argv); - n0 = sn_network_read_file (argv[1]); + if (strcmp ("-", file0) == 0) + n0 = sn_network_read (stdin); + else + n0 = sn_network_read_file (file0); if (n0 == NULL) { - printf ("n0 == NULL\n"); - return (1); + fprintf (stderr, "Unable to read first network.\n"); + exit (EXIT_FAILURE); } - n1 = sn_network_read_file (argv[2]); + if (strcmp ("-", file1) == 0) + { + if (strcmp ("-", file0) == 0) + n1 = sn_network_clone (n0); + else + n1 = sn_network_read (stdin); + } + else + n1 = sn_network_read_file (file1); if (n1 == NULL) { - printf ("n1 == NULL\n"); - return (1); + fprintf (stderr, "Unable to read second network.\n"); + exit (EXIT_FAILURE); + } + + if (use_bitonic + && ((SN_NETWORK_INPUT_NUM (n0) != SN_NETWORK_INPUT_NUM (n1)) + || !is_power_of_two (SN_NETWORK_INPUT_NUM (n0)))) + { + fprintf (stderr, "Using the bitonic merge is currently only possible " + "if the number of inputs of both networks is identical and a " + "power of two\n"); + exit (EXIT_FAILURE); + } + + if (use_bitonic) + n = sn_network_combine_bitonic_merge (n0, n1); + else + n = sn_network_combine_odd_even_merge (n0, n1); + + if (n == NULL) + { + fprintf (stderr, "Combining the networks faild.\n"); + exit (EXIT_FAILURE); } - n = sn_network_combine (n0, n1, /* is power of two = */ 0); sn_network_destroy (n0); sn_network_destroy (n1); diff --git a/src/sn_network.c b/src/sn_network.c index 05beb79..b490de4 100644 --- a/src/sn_network.c +++ b/src/sn_network.c @@ -38,6 +38,7 @@ #include #include #include +#include #include "sn_network.h" #include "sn_random.h" @@ -138,6 +139,9 @@ int sn_network_stage_add (sn_network_t *n, sn_stage_t *s) /* {{{ */ { sn_stage_t **temp; + if ((n == NULL) || (s == NULL)) + return (EINVAL); + temp = (sn_stage_t **) realloc (n->stages, (n->stages_num + 1) * sizeof (sn_stage_t *)); if (temp == NULL) @@ -156,7 +160,8 @@ 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); + if ((n == NULL) || (s_num >= n->stages_num)) + return (EINVAL); sn_stage_destroy (n->stages[s_num]); n->stages[s_num] = NULL; @@ -225,7 +230,7 @@ int sn_network_comparator_add (sn_network_t *n, /* {{{ */ sn_stage_t *s; if ((n == NULL) || (c == NULL)) - return (-1); + return (EINVAL); if (n->stages_num > 0) { @@ -274,6 +279,9 @@ int sn_network_invert (sn_network_t *n) /* {{{ */ { int i; + if (n == NULL) + return (EINVAL); + for (i = 0; i < n->stages_num; i++) sn_stage_invert (n->stages[i]); @@ -284,6 +292,12 @@ int sn_network_shift (sn_network_t *n, int sw) /* {{{ */ { int i; + if ((n == NULL) || (sw < 0)) + return (EINVAL); + + if (sw == 0) + return (0); + for (i = 0; i < n->stages_num; i++) sn_stage_shift (n->stages[i], sw, SN_NETWORK_INPUT_NUM (n)); @@ -658,11 +672,11 @@ static sn_network_t *sn_network_combine_bitonic_shift (sn_network_t *n0, /* {{{ return (n); } /* }}} sn_network_t *sn_network_combine_bitonic_shift */ -sn_network_t *sn_network_combine_bitonic (sn_network_t *n0, /* {{{ */ +sn_network_t *sn_network_combine_bitonic_merge (sn_network_t *n0, /* {{{ */ sn_network_t *n1) { return (sn_network_combine_bitonic_shift (n0, n1, /* do_shift = */ 0)); -} /* }}} sn_network_t *sn_network_combine_bitonic */ +} /* }}} sn_network_t *sn_network_combine_bitonic_merge */ sn_network_t *sn_network_combine_odd_even_merge (sn_network_t *n0, /* {{{ */ sn_network_t *n1) @@ -697,27 +711,12 @@ sn_network_t *sn_network_combine_odd_even_merge (sn_network_t *n0, /* {{{ */ sn_network_compress (n); return (n); -} /* }}} sn_network_t *sn_network_combine */ +} /* }}} sn_network_t *sn_network_combine_odd_even_merge */ sn_network_t *sn_network_combine (sn_network_t *n0, /* {{{ */ - sn_network_t *n1, int is_power_of_two) + sn_network_t *n1) { - sn_network_t *n; - - if ((is_power_of_two != 0) && (sn_bounded_random (0, 9) == 0)) - { - DPRINTF ("sn_network_combine: Using the bitonic merger.\n"); - n = sn_network_combine_bitonic_shift (n0, n1, /* do_shift = */ 1); - } - else - { - DPRINTF ("sn_network_combine: Using the odd-even merger.\n"); - n = sn_network_combine_odd_even_merge (n0, n1); - } - - sn_network_compress (n); - - return (n); + return (sn_network_combine_odd_even_merge (n0, n1)); } /* }}} sn_network_t *sn_network_combine */ int sn_network_sort (sn_network_t *n, int *values) /* {{{ */ diff --git a/src/sn_network.h b/src/sn_network.h index 33c5188..a734cad 100644 --- a/src/sn_network.h +++ b/src/sn_network.h @@ -206,9 +206,11 @@ int sn_network_normalize (sn_network_t *n); * \return Zero on success, non-zero on failure. */ 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, - int is_power_of_two); -sn_network_t *sn_network_combine_bitonic (sn_network_t *n0, sn_network_t *n1); + +/** + * An alias for sn_network_combine_odd_even_merge(). + */ +sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1); /** * Combines two comparator networks using a bitonic merger. The number of @@ -219,6 +221,7 @@ sn_network_t *sn_network_combine_bitonic (sn_network_t *n0, sn_network_t *n1); * \return Newly allocated network with twice the number of inputs or NULL on * error. */ +sn_network_t *sn_network_combine_bitonic_merge (sn_network_t *n0, sn_network_t *n1); /** * Combines two comparator networks using the odd-even-merger.