X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=src%2Fsn_network.c;h=1b3dd3630515aaa92adbdd18eeed51cd2a2fb427;hb=2b64b183834075911f9e53a6f0132d116bf45a76;hp=cd5835edc7bb43a073f84f1c84080d01161222b5;hpb=79789cfc25a65312d8b91000abc7eb9209322555;p=sort-networks.git diff --git a/src/sn_network.c b/src/sn_network.c index cd5835e..1b3dd36 100644 --- a/src/sn_network.c +++ b/src/sn_network.c @@ -1,6 +1,6 @@ /** - * collectd - src/sn_network.c - * Copyright (C) 2008,2009 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 @@ -38,6 +38,7 @@ #include #include #include +#include #include "sn_network.h" #include "sn_random.h" @@ -134,10 +135,85 @@ sn_network_t *sn_network_create_odd_even_mergesort (int inputs_num) /* {{{ */ } } /* }}} sn_network_t *sn_network_create_odd_even_mergesort */ +static int sn_network_create_pairwise_internal (sn_network_t *n, /* {{{ */ + int *inputs, int inputs_num) +{ + int i; + int inputs_copy[inputs_num]; + int m; + + for (i = 1; i < inputs_num; i += 2) + { + sn_comparator_t *c = sn_comparator_create (inputs[i-1], inputs[i]); + sn_network_comparator_add (n, c); + sn_comparator_destroy (c); + } + + if (inputs_num <= 2) + return (0); + + /* Sort "pairs" recursively. Like with odd-even mergesort, odd and even lines + * are handled recursively and later reunited. */ + for (i = 0; i < inputs_num; i += 2) + inputs_copy[(int) (i / 2)] = inputs[i]; + /* Recursive call #1 with first set of lines */ + sn_network_create_pairwise_internal (n, inputs_copy, + (int) ((inputs_num + 1) / 2)); + + for (i = 1; i < inputs_num; i += 2) + inputs_copy[(int) (i / 2)] = inputs[i]; + /* Recursive call #2 with second set of lines */ + sn_network_create_pairwise_internal (n, inputs_copy, + (int) (inputs_num/ 2)); + + /* m is the "amplitude" of the sorted pairs. This is a bit tricky to read due + * to different indices being used in the paper, unfortunately. */ + m = inputs_num / 2; + while (m > 1) + { + for (i = 1; (i + (m - 1)) < inputs_num; i += 2) + { + int left = i; + int right = i + (m - 1); + sn_comparator_t *c; + + assert (left < right); + c = sn_comparator_create (inputs[left], inputs[right]); + sn_network_comparator_add (n, c); + sn_comparator_destroy (c); + } + + m = m / 2; + } /* while (m > 1) */ + + return (0); +} /* }}} int sn_network_create_pairwise_internal */ + +sn_network_t *sn_network_create_pairwise (int inputs_num) /* {{{ */ +{ + sn_network_t *n = sn_network_create (inputs_num); + int inputs[inputs_num]; + int i; + + if (n == NULL) + return (NULL); + + for (i = 0; i < inputs_num; i++) + inputs[i] = i; + + sn_network_create_pairwise_internal (n, inputs, inputs_num); + sn_network_compress (n); + + return (n); +} /* }}} sn_network_t *sn_network_create_pairwise */ + 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 +232,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; @@ -164,7 +241,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--; @@ -178,7 +255,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; @@ -219,6 +296,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 (EINVAL); + + 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; @@ -233,6 +351,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]); @@ -243,6 +364,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)); @@ -258,9 +385,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); @@ -268,26 +395,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--; } } } @@ -323,10 +450,10 @@ 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 < n->stages_num; k++) + sn_stage_swap (n->stages[k], min, max); i = -1; break; /* for (j) */ @@ -356,7 +483,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; @@ -401,20 +528,20 @@ static sn_network_t *sn_network_concatenate (sn_network_t *n0, /* {{{ */ 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); + 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_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_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_stage_comparator_add (s, &c_copy); } sn_network_stage_add (n, s); @@ -617,11 +744,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) @@ -656,27 +783,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) /* {{{ */ @@ -719,7 +831,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]; } @@ -729,14 +841,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; } } @@ -763,7 +875,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'; @@ -871,7 +983,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;