X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=src%2Fsn_network.c;h=05beb7936c1d83a38ff8d60ff28ae8feb95f55ea;hb=8764b3122abba9e60cacb591f16a5e71abb5155f;hp=a1ada08d5d6eb845c8aca01c45af3d225280423c;hpb=76c8993c0e5a4cab6a63d838cc3653c4e5ef82bf;p=sort-networks.git diff --git a/src/sn_network.c b/src/sn_network.c index a1ada08..05beb79 100644 --- a/src/sn_network.c +++ b/src/sn_network.c @@ -1,6 +1,6 @@ /** - * collectd - src/sn_network.c - * Copyright (C) 2008 Florian octo Forster + * libsortnetwork - src/sn_network.c + * Copyright (C) 2008-2010 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 @@ -16,7 +16,7 @@ * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA * * Authors: - * Florian octo Forster + * Florian octo Forster **/ #ifndef _ISOC99_SOURCE @@ -26,6 +26,12 @@ # define _POSIX_C_SOURCE 200112L #endif +#if 0 +# define DPRINTF(...) fprintf (stderr, "sn_network: " __VA_ARGS__) +#else +# define DPRINTF(...) /**/ +#endif + #include #include #include @@ -70,6 +76,64 @@ void sn_network_destroy (sn_network_t *n) /* {{{ */ free (n); } /* }}} void sn_network_destroy */ +sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num) /* {{{ */ +{ + sn_network_t *n; + + n = sn_network_create (inputs_num); + + assert (inputs_num > 0); + if (inputs_num == 1) + { + return (n); + } + if (inputs_num == 2) + { + sn_stage_t *s; + sn_comparator_t c; + + c.min = 0; + c.max = 1; + + s = sn_stage_create (/* depth = */ 0); + sn_stage_comparator_add (s, &c); + sn_network_stage_add (n, s); + + return (n); + } + else + { + sn_network_t *n_left; + sn_network_t *n_right; + int inputs_left; + int inputs_right; + + inputs_left = inputs_num / 2; + inputs_right = inputs_num - inputs_left; + + n_left = sn_network_create_odd_even_mergesort (inputs_left); + if (n_left == NULL) + return (NULL); + + n_right = sn_network_create_odd_even_mergesort (inputs_right); + if (n_right == NULL) + { + sn_network_destroy (n_left); + return (NULL); + } + + n = sn_network_combine_odd_even_merge (n_left, n_right); + + sn_network_destroy (n_left); + sn_network_destroy (n_right); + + if (n != NULL) + sn_network_compress (n); + + return (n); + } +} /* }}} sn_network_t *sn_network_create_odd_even_mergesort */ + int sn_network_stage_add (sn_network_t *n, sn_stage_t *s) /* {{{ */ { sn_stage_t **temp; @@ -100,7 +164,7 @@ int sn_network_stage_remove (sn_network_t *n, int s_num) /* {{{ */ if (nmemb > 0) { memmove (n->stages + s_num, n->stages + (s_num + 1), - nmemb * sizeof (sn_stage_t *)); + nmemb * sizeof (sn_stage_t *)); n->stages[n->stages_num - 1] = NULL; } n->stages_num--; @@ -114,7 +178,7 @@ int sn_network_stage_remove (sn_network_t *n, int s_num) /* {{{ */ else { temp = (sn_stage_t **) realloc (n->stages, - n->stages_num * sizeof (sn_stage_t *)); + n->stages_num * sizeof (sn_stage_t *)); if (temp == NULL) return (-1); n->stages = temp; @@ -155,6 +219,47 @@ sn_network_t *sn_network_clone (const sn_network_t *n) /* {{{ */ return (n_copy); } /* }}} sn_network_t *sn_network_clone */ +int sn_network_comparator_add (sn_network_t *n, /* {{{ */ + const sn_comparator_t *c) +{ + sn_stage_t *s; + + if ((n == NULL) || (c == NULL)) + return (-1); + + if (n->stages_num > 0) + { + s = n->stages[n->stages_num - 1]; + + if (sn_stage_comparator_check_conflict (s, c) == 0) + { + sn_stage_comparator_add (s, c); + return (0); + } + } + + s = sn_stage_create (n->stages_num); + sn_stage_comparator_add (s, c); + sn_network_stage_add (n, s); + + return (0); +} /* }}} int sn_network_comparator_add */ + +int sn_network_get_comparator_num (const sn_network_t *n) /* {{{ */ +{ + int num; + int i; + + if (n == NULL) + return (-1); + + num = 0; + for (i = 0; i < n->stages_num; i++) + num += n->stages[i]->comparators_num; + + return (num); +} /* }}} int sn_network_get_comparator_num */ + int sn_network_show (sn_network_t *n) /* {{{ */ { int i; @@ -194,9 +299,9 @@ int sn_network_compress (sn_network_t *n) /* {{{ */ 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); @@ -204,26 +309,26 @@ int sn_network_compress (sn_network_t *n) /* {{{ */ 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; + 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--; + if (move_to >= 0) + sn_stage_comparator_add (n->stages[move_to], c); + sn_stage_comparator_remove (s, j); + j--; } } } @@ -239,7 +344,7 @@ int sn_network_normalize (sn_network_t *n) /* {{{ */ { int i; - for (i = n->stages_num - 1; i >= 0; i--) + for (i = 0; i < n->stages_num; i++) { sn_stage_t *s; int j; @@ -259,10 +364,13 @@ int sn_network_normalize (sn_network_t *n) /* {{{ */ if (min > max) { - int k; + int k; + + for (k = i; k < n->stages_num; k++) + sn_stage_swap (n->stages[k], min, max); - for (k = i; k >= 0; k--) - sn_stage_swap (n->stages[k], min, max); + i = -1; + break; /* for (j) */ } } /* for (j = 0 .. #comparators) */ } /* for (i = n->stages_num - 1 .. 0) */ @@ -289,7 +397,7 @@ int sn_network_cut_at (sn_network_t *n, int input, /* {{{ */ int j; for (j = 0; j < i; j++) - sn_stage_swap (n->stages[j], position, new_position); + sn_stage_swap (n->stages[j], position, new_position); } position = new_position; @@ -306,6 +414,56 @@ int sn_network_cut_at (sn_network_t *n, int input, /* {{{ */ return (0); } /* }}} int sn_network_cut_at */ +/* sn_network_concatenate + * + * `Glues' two networks together, resulting in a comparator network with twice + * as many inputs but one that doesn't really sort anymore. It produces a + * bitonic sequence, though, that can be used by the mergers below. */ +static sn_network_t *sn_network_concatenate (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); + } + + return (n); +} /* }}} sn_network_t *sn_network_concatenate */ + static int sn_network_add_bitonic_merger_recursive (sn_network_t *n, /* {{{ */ int low, int num) { @@ -342,6 +500,7 @@ static int sn_network_add_bitonic_merger_recursive (sn_network_t *n, /* {{{ */ static int sn_network_add_bitonic_merger (sn_network_t *n) /* {{{ */ { +#if 0 sn_stage_t *s; int m; int i; @@ -366,157 +525,194 @@ static int sn_network_add_bitonic_merger (sn_network_t *n) /* {{{ */ sn_network_add_bitonic_merger_recursive (n, 0, m); sn_network_add_bitonic_merger_recursive (n, m, m); +#else + sn_network_add_bitonic_merger_recursive (n, 0, SN_NETWORK_INPUT_NUM (n)); +#endif 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) +static int sn_network_add_odd_even_merger (sn_network_t *n, /* {{{ */ + int *indizes_left, int indizes_left_num, + int *indizes_right, int indizes_right_num) { - if (indizes_num > 2) + int tmp_left[indizes_left_num]; + int tmp_left_num; + int tmp_right[indizes_left_num]; + int tmp_right_num; + int max_index; + sn_stage_t *s; + int i; + + if ((indizes_left_num == 0) || (indizes_right_num == 0)) + { + return (0); + } + else if ((indizes_left_num == 1) && (indizes_right_num == 1)) { 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) + c.min = *indizes_left; + c.max = *indizes_right; + + s = sn_stage_create (n->stages_num); + if (s == 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]; - } + sn_stage_comparator_add (s, &c); + sn_network_stage_add (n, s); - status = sn_network_add_odd_even_merger_recursive (n, - indizes_half, indizes_half_num); - if (status != 0) - { - free (indizes_half); - return (status); - } + return (0); + } - 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); - } + /* Merge odd sequences */ + tmp_left_num = (indizes_left_num + 1) / 2; + for (i = 0; i < tmp_left_num; i++) + tmp_left[i] = indizes_left[2 * i]; - free (indizes_half); + tmp_right_num = (indizes_right_num + 1) / 2; + for (i = 0; i < tmp_right_num; i++) + tmp_right[i] = indizes_right[2 * i]; - s = sn_stage_create (n->stages_num); - if (s == NULL) - return (-1); + sn_network_add_odd_even_merger (n, + tmp_left, tmp_left_num, + tmp_right, tmp_right_num); - for (i = 1; i < (indizes_num - 2); i += 2) - { - c.min = indizes[i]; - c.max = indizes[i + 1]; + /* Merge even sequences */ + tmp_left_num = indizes_left_num / 2; + for (i = 0; i < tmp_left_num; i++) + tmp_left[i] = indizes_left[(2 * i) + 1]; - sn_stage_comparator_add (s, &c); - } + tmp_right_num = indizes_right_num / 2; + for (i = 0; i < tmp_right_num; i++) + tmp_right[i] = indizes_right[(2 * i) + 1]; - sn_network_stage_add (n, s); - } + sn_network_add_odd_even_merger (n, + tmp_left, tmp_left_num, + tmp_right, tmp_right_num); + + /* Apply ``comparison-interchange'' operations. */ + s = sn_stage_create (n->stages_num); + + max_index = indizes_left_num + indizes_right_num; + if ((max_index % 2) == 0) + max_index -= 3; else + max_index -= 2; + + for (i = 1; i <= max_index; i += 2) { sn_comparator_t c; - sn_stage_t *s; - assert (indizes_num == 2); - - c.min = indizes[0]; - c.max = indizes[1]; + if (i < indizes_left_num) + c.min = indizes_left[i]; + else + c.min = indizes_right[i - indizes_left_num]; - s = sn_stage_create (n->stages_num); - if (s == NULL) - return (-1); + if ((i + 1) < indizes_left_num) + c.max = indizes_left[i + 1]; + else + c.max = indizes_right[i + 1 - indizes_left_num]; sn_stage_comparator_add (s, &c); - sn_network_stage_add (n, s); } + sn_network_stage_add (n, s); + return (0); -} /* }}} int sn_network_add_odd_even_merger_recursive */ +} /* }}} int sn_network_add_odd_even_merger */ -static int sn_network_add_odd_even_merger (sn_network_t *n) /* {{{ */ +static sn_network_t *sn_network_combine_bitonic_shift (sn_network_t *n0, /* {{{ */ + sn_network_t *n1, int do_shift) { - int *indizes; - int indizes_num; - int status; - int i; + sn_network_t *n; + sn_network_t *n1_clone; + int shift; - indizes_num = n->inputs_num; - indizes = (int *) malloc (indizes_num * sizeof (int)); - if (indizes == NULL) - return (-1); + n1_clone = sn_network_clone (n1); + if (n1_clone == NULL) + return (NULL); - for (i = 0; i < indizes_num; i++) - indizes[i] = i; + sn_network_invert (n1_clone); - status = sn_network_add_odd_even_merger_recursive (n, - indizes, indizes_num); - - free (indizes); - return (status); -} /* }}} int sn_network_add_bitonic_merger */ + n = sn_network_concatenate (n0, n1_clone); + if (n == NULL) + return (NULL); -sn_network_t *sn_network_combine (sn_network_t *n0, /* {{{ */ + sn_network_destroy (n1_clone); + + if (do_shift) + shift = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n) - 1); + else + shift = 0; + + if (shift > 0) + { + DPRINTF ("sn_network_combine_bitonic_shift: Shifting by %i.\n", shift); + sn_network_shift (n, shift); + } + + sn_network_add_bitonic_merger (n); + + return (n); +} /* }}} sn_network_t *sn_network_combine_bitonic_shift */ + +sn_network_t *sn_network_combine_bitonic (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_odd_even_merge (sn_network_t *n0, /* {{{ */ sn_network_t *n1) { sn_network_t *n; - int stages_num; + int indizes_left[n0->inputs_num]; + int indizes_left_num; + int indizes_right[n1->inputs_num]; + int indizes_right_num; + int status; int i; - int j; - stages_num = (n0->stages_num > n1->stages_num) - ? n0->stages_num - : n1->stages_num; + indizes_left_num = n0->inputs_num; + indizes_right_num = n1->inputs_num; + for (i = 0; i < indizes_left_num; i++) + indizes_left[i] = i; + for (i = 0; i < indizes_right_num; i++) + indizes_right[i] = indizes_left_num + i; - n = sn_network_create (n0->inputs_num + n1->inputs_num); + n = sn_network_concatenate (n0, n1); if (n == NULL) return (NULL); - for (i = 0; i < stages_num; i++) + status = sn_network_add_odd_even_merger (n, + indizes_left, indizes_left_num, + indizes_right, indizes_right_num); + if (status != 0) { - 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_network_destroy (n); + return (NULL); + } - sn_stage_comparator_add (s, &c_copy); - } + sn_network_compress (n); + return (n); +} /* }}} sn_network_t *sn_network_combine */ - sn_network_stage_add (n, s); - } +sn_network_t *sn_network_combine (sn_network_t *n0, /* {{{ */ + sn_network_t *n1, int is_power_of_two) +{ + sn_network_t *n; - if (sn_bounded_random (0, 1) == 0) + if ((is_power_of_two != 0) && (sn_bounded_random (0, 9) == 0)) { - sn_network_add_bitonic_merger (n); + DPRINTF ("sn_network_combine: Using the bitonic merger.\n"); + n = sn_network_combine_bitonic_shift (n0, n1, /* do_shift = */ 1); } else { - sn_network_add_odd_even_merger (n); + DPRINTF ("sn_network_combine: Using the odd-even merger.\n"); + n = sn_network_combine_odd_even_merge (n0, n1); } sn_network_compress (n); @@ -564,7 +760,7 @@ int sn_network_brute_force_check (sn_network_t *n) /* {{{ */ for (i = 1; i < n->inputs_num; i++) { if (previous > values[i]) - return (1); + return (1); previous = values[i]; } @@ -574,14 +770,14 @@ int sn_network_brute_force_check (sn_network_t *n) /* {{{ */ { if (test_pattern[i] == 0) { - test_pattern[i] = 1; - overflow = 0; - break; + test_pattern[i] = 1; + overflow = 0; + break; } else { - test_pattern[i] = 0; - overflow = 1; + test_pattern[i] = 0; + overflow = 1; } } @@ -608,7 +804,7 @@ sn_network_t *sn_network_read (FILE *fh) /* {{{ */ int buffer_len = strlen (buffer); while ((buffer_len > 0) && ((buffer[buffer_len - 1] == '\n') - || (buffer[buffer_len - 1] == '\r'))) + || (buffer[buffer_len - 1] == '\r'))) { buffer_len--; buffer[buffer_len] = '\0'; @@ -716,7 +912,7 @@ int sn_network_serialize (sn_network_t *n, char **ret_buffer, /* {{{ */ #define SNPRINTF_OR_FAIL(...) \ status = snprintf (buffer, buffer_size, __VA_ARGS__); \ - if ((status < 1) || (status >= buffer_size)) \ + if ((status < 1) || (((size_t) status) >= buffer_size)) \ return (-1); \ buffer += status; \ buffer_size -= status;