X-Git-Url: https://git.octo.it/?p=sort-networks.git;a=blobdiff_plain;f=src%2Fsn_stage.c;h=158446985371654b3e705644bd6d8e75f470ce6c;hp=bade6c42b46a375e1525a2e1fb54403dfa129acf;hb=785cb745f68b61aa83820a4f85a8c91a0e015228;hpb=0f2d6e79cfef8b0db5372f832a301fee124039cb diff --git a/src/sn_stage.c b/src/sn_stage.c index bade6c4..1584469 100644 --- a/src/sn_stage.c +++ b/src/sn_stage.c @@ -1,22 +1,23 @@ /** - * collectd - src/sn_stage.c - * Copyright (C) 2008 Florian octo Forster + * libsortnetwork - src/sn_stage.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 - * Free Software Foundation; only version 2 of the License is applicable. + * This library is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License as published by + * the Free Software Foundation; either version 2.1 of the License, or (at + * your option) any later version. * - * 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. + * This library 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 Lesser 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 + * You should have received a copy of the GNU Lesser General Public License + * along with this library; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * * Authors: - * Florian octo Forster + * Florian octo Forster **/ #ifndef _ISOC99_SOURCE @@ -29,6 +30,7 @@ #include #include #include +#include #include "sn_comparator.h" #include "sn_stage.h" @@ -82,10 +84,17 @@ int sn_stage_comparator_add (sn_stage_t *s, const sn_comparator_t *c) sn_comparator_t *temp; int i; + if ((s == NULL) || (c == NULL)) + return (EINVAL); + + i = sn_stage_comparator_check_conflict (s, c); + if (i != 0) + return (i); + temp = (sn_comparator_t *) realloc (s->comparators, (s->comparators_num + 1) * sizeof (sn_comparator_t)); if (temp == NULL) - return (-1); + return (ENOMEM); s->comparators = temp; temp = NULL; @@ -112,6 +121,9 @@ int sn_stage_comparator_remove (sn_stage_t *s, int c_num) int nmemb = s->comparators_num - (c_num + 1); sn_comparator_t *temp; + if ((s == NULL) || (s->comparators_num <= c_num)) + return (EINVAL); + assert (c_num < s->comparators_num); assert (c_num >= 0); @@ -141,6 +153,7 @@ int sn_stage_comparator_remove (sn_stage_t *s, int c_num) sn_stage_t *sn_stage_clone (const sn_stage_t *s) { sn_stage_t *s_copy; + int i; s_copy = sn_stage_create (s->depth); if (s_copy == NULL) @@ -154,8 +167,13 @@ sn_stage_t *sn_stage_clone (const sn_stage_t *s) return (NULL); } - memcpy (s_copy->comparators, s->comparators, - s->comparators_num * sizeof (sn_comparator_t)); + for (i = 0; i < s->comparators_num; i++) + { + SN_COMP_MIN (s_copy->comparators + i) = SN_COMP_MIN (s->comparators + i); + SN_COMP_MAX (s_copy->comparators + i) = SN_COMP_MAX (s->comparators + i); + SN_COMP_USER_DATA (s_copy->comparators + i) = NULL; + SN_COMP_FREE_FUNC (s_copy->comparators + i) = NULL; + } s_copy->comparators_num = s->comparators_num; return (s_copy); @@ -276,16 +294,57 @@ int sn_stage_invert (sn_stage_t *s) { int i; + if (s == NULL) + return (EINVAL); + for (i = 0; i < s->comparators_num; i++) sn_comparator_invert (s->comparators + i); return (0); } /* int sn_stage_invert */ +int sn_stage_shift (sn_stage_t *s, int sw, int inputs_num) +{ + int i; + + if ((s == NULL) || (inputs_num < 2)) + return (EINVAL); + + sw %= inputs_num; + if (sw == 0) + return (0); + + for (i = 0; i < s->comparators_num; i++) + sn_comparator_shift (s->comparators + i, sw, inputs_num); + + return (0); +} /* int sn_stage_shift */ + +static int sn_stage_unify__qsort_callback (const void *p0, const void *p1) /* {{{ */ +{ + return (sn_comparator_compare (p0, p1)); +} /* }}} int sn_stage_unify__qsort_callback */ + +int sn_stage_unify (sn_stage_t *s) /* {{{ */ +{ + if (s == NULL) + return (EINVAL); + + qsort (s->comparators, + (size_t) s->comparators_num, + sizeof (*s->comparators), + sn_stage_unify__qsort_callback); + + return (0); +} /* }}} int sn_stage_unify */ + int sn_stage_swap (sn_stage_t *s, int con0, int con1) { int i; + if (s == NULL) + return (EINVAL); + for (i = 0; i < s->comparators_num; i++) sn_comparator_swap (s->comparators + i, con0, con1); @@ -297,6 +356,9 @@ int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir) int new_position = input; int i; + if ((s == NULL) || (input < 0)) + return (-EINVAL); + for (i = 0; i < s->comparators_num; i++) { sn_comparator_t *c = s->comparators + i; @@ -323,6 +385,47 @@ int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir) return (new_position); } /* int sn_stage_cut_at */ +int sn_stage_cut (sn_stage_t *s, int *mask, /* {{{ */ + sn_stage_t **prev) +{ + int i; + + if ((s == NULL) || (mask == NULL) || (prev == NULL)) + return (EINVAL); + + for (i = 0; i < s->comparators_num; i++) + { + sn_comparator_t *c = s->comparators + i; + int left = SN_COMP_LEFT (c); + int right = SN_COMP_RIGHT (c); + + if ((mask[left] == 0) + && (mask[right] == 0)) + continue; + + /* Check if we need to update the cut position */ + if ((mask[left] != mask[right]) + && ((mask[left] > 0) || (mask[right] < 0))) + { + int tmp; + int j; + + tmp = mask[right]; + mask[right] = mask[left]; + mask[left] = tmp; + + for (j = s->depth - 1; j >= 0; j--) + sn_stage_swap (prev[j], + left, right); + } + + sn_stage_comparator_remove (s, i); + i--; + } /* for (i = 0; i < s->comparators_num; i++) */ + + return (0); +} /* }}} int sn_stage_cut */ + int sn_stage_remove_input (sn_stage_t *s, int input) { int i; @@ -405,4 +508,165 @@ int sn_stage_write (sn_stage_t *s, FILE *fh) return (0); } /* int sn_stage_write */ -/* vim: set shiftwidth=2 softtabstop=2 : */ +int sn_stage_serialize (sn_stage_t *s, + char **ret_buffer, size_t *ret_buffer_size) +{ + char *buffer; + size_t buffer_size; + int status; + int i; + + if (s->comparators_num <= 0) + return (0); + + buffer = *ret_buffer; + buffer_size = *ret_buffer_size; + +#define SNPRINTF_OR_FAIL(...) \ + status = snprintf (buffer, buffer_size, __VA_ARGS__); \ + if ((status < 1) || (((size_t) status) >= buffer_size)) \ + return (-1); \ + buffer += status; \ + buffer_size -= status; + + for (i = 0; i < s->comparators_num; i++) + { + SNPRINTF_OR_FAIL ("%i %i\r\n", + SN_COMP_MIN (s->comparators + i), + SN_COMP_MAX (s->comparators + i)); + } + + SNPRINTF_OR_FAIL ("\r\n"); + + *ret_buffer = buffer; + *ret_buffer_size = buffer_size; + return (0); +} /* int sn_stage_serialize */ + +sn_stage_t *sn_stage_unserialize (char **ret_buffer, size_t *ret_buffer_size) +{ + sn_stage_t *s; + char *buffer; + size_t buffer_size; + int status; + + buffer = *ret_buffer; + buffer_size = *ret_buffer_size; + + if (buffer_size == 0) + return (NULL); + + s = sn_stage_create (0); + if (s == NULL) + return (NULL); + + status = 0; + while (buffer_size > 0) + { + sn_comparator_t c; + char *endptr; + char *substr; + size_t substr_length; + + endptr = strchr (buffer, '\n'); + if (endptr == NULL) + { + status = -1; + break; + } + + *endptr = 0; + endptr++; + + substr = buffer; + substr_length = strlen (buffer); + buffer = endptr; + buffer_size -= (substr_length + 1); + + if ((substr_length > 0) && (substr[substr_length - 1] == '\r')) + { + substr[substr_length - 1] = 0; + substr_length--; + } + + if (substr_length == 0) + { + status = 0; + break; + } + + endptr = NULL; + c.min = (int) strtol (substr, &endptr, 0); + if (substr == endptr) + { + status = -1; + break; + } + + substr = endptr; + endptr = NULL; + c.max = (int) strtol (substr, &endptr, 0); + if (substr == endptr) + { + status = -1; + break; + } + + sn_stage_comparator_add (s, &c); + } /* while (buffer_size > 0) */ + + if ((status != 0) || (s->comparators_num == 0)) + { + sn_stage_destroy (s); + return (NULL); + } + + *ret_buffer = buffer; + *ret_buffer_size = buffer_size; + return (s); +} /* sn_stage_t *sn_stage_unserialize */ + +int sn_stage_compare (const sn_stage_t *s0, const sn_stage_t *s1) /* {{{ */ +{ + int status; + int i; + + if (s0 == s1) + return (0); + else if (s0 == NULL) + return (-1); + else if (s1 == NULL) + return (1); + + if (s0->comparators_num < s1->comparators_num) + return (-1); + else if (s0->comparators_num > s1->comparators_num) + return (1); + + for (i = 0; i < s0->comparators_num; i++) + { + status = sn_comparator_compare (s0->comparators + i, s1->comparators + i); + if (status != 0) + return (status); + } + + return (0); +} /* }}} int sn_stage_compare */ + +uint64_t sn_stage_get_hashval (const sn_stage_t *s) /* {{{ */ +{ + uint64_t hash; + int i; + + if (s == NULL) + return (0); + + hash = (uint64_t) s->depth; + + for (i = 0; i < s->comparators_num; i++) + hash = (hash * 99991) + sn_comparator_get_hashval (s->comparators + i); + + return (hash); +} /* }}} uint64_t sn_stage_get_hashval */ + +/* vim: set shiftwidth=2 softtabstop=2 expandtab fdm=marker : */