From: Florian Forster Date: Mon, 20 Dec 2010 08:41:04 +0000 (+0100) Subject: Merge remote branch 'origin/master' X-Git-Tag: v1.0.0~13 X-Git-Url: https://git.octo.it/?p=sort-networks.git;a=commitdiff_plain;h=9f77fbe43254d5920b3b1fac1ab0c01cc3a3adcc;hp=dfe6b1c24c78a546fa0d3e1432d8872c56d2df55 Merge remote branch 'origin/master' Conflicts: src/sn-svg.c --- diff --git a/src/sn-cut.c b/src/sn-cut.c index 9cf9813..e888365 100644 --- a/src/sn-cut.c +++ b/src/sn-cut.c @@ -21,40 +21,80 @@ #include "config.h" +#ifndef _ISOC99_SOURCE +# define _ISOC99_SOURCE +#endif +#ifndef _POSIX_C_SOURCE +# define _POSIX_C_SOURCE 200809L +#endif +#ifdef _XOPEN_SOURCE +# define _XOPEN_SOURCE 700 +#endif + #include #include +#include #include #include "sn_network.h" -void exit_usage (const char *name) +static void exit_usage (const char *name) { - printf ("%s \n", name); + printf ("Usage: %s [:min|max] [[:min|max] ...]\n", name); exit (EXIT_FAILURE); } +static int do_cut (sn_network_t *n, int defs_num, char **defs) +{ + int mask[SN_NETWORK_INPUT_NUM (n)]; + int status; + int i; + + memset (mask, 0, sizeof (mask)); + for (i = 0; i < defs_num; i++) + { + char *endptr = NULL; + int pos; + int val = 1; + + pos = (int) strtol (defs[i], &endptr, /* base = */ 0); + if (strcasecmp (":min", endptr) == 0) + val = -1; + + if ((pos < 0) || (pos >= SN_NETWORK_INPUT_NUM (n))) + { + fprintf (stderr, "Invalid line number: %i\n", pos); + return (-1); + } + + mask[pos] = val; + } + + status = sn_network_cut (n, mask); + if (status != 0) + { + fprintf (stderr, "sn_network_cut failed with status %i.\n", status); + return (-1); + } + + return (0); +} /* }}} int do_cut */ + int main (int argc, char **argv) { sn_network_t *n; - int pos = 0; - enum sn_network_cut_dir_e dir = DIR_MIN; - - if (argc != 3) + if (argc < 2) exit_usage (argv[0]); - pos = atoi (argv[1]); - if (strcasecmp ("max", argv[2]) == 0) - dir = DIR_MAX; - n = sn_network_read (stdin); if (n == NULL) { - printf ("n == NULL!\n"); - return (1); + fprintf (stderr, "Unable to read network from STDIN.\n"); + exit (EXIT_FAILURE); } - sn_network_cut_at (n, pos, dir); + do_cut (n, argc - 1, argv + 1); sn_network_compress (n); sn_network_write (n, stdout); diff --git a/src/sn-evolution-cut.c b/src/sn-evolution-cut.c index f33e873..0e4c1e8 100644 --- a/src/sn-evolution-cut.c +++ b/src/sn-evolution-cut.c @@ -168,40 +168,16 @@ int read_options (int argc, char **argv) /* {{{ */ return (0); } /* }}} int read_options */ -static int apply_cut (sn_network_t *n, int input) /* {{{ */ -{ - enum sn_network_cut_dir_e dir = DIR_MAX; - - if (input < 0) - { - dir = DIR_MIN; - input *= (-1); - } - input--; - - return (sn_network_cut_at (n, input, dir)); -} /* }}} int apply_cut */ - -static int apply (sn_network_t *n, const individuum_t *ind) /* {{{ */ -{ - int i; - - for (i = 0; i < cuts_num; i++) - apply_cut (n, ind[i]); - - return (0); -} /* }}} int apply */ - static int rate_network (const sn_network_t *n) /* {{{ */ { int rate; int i; - rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n); + rate = SN_NETWORK_STAGE_NUM (n); for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++) { sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i); - rate += SN_STAGE_COMP_NUM (s); + rate += 2 * SN_STAGE_COMP_NUM (s); } return (rate); @@ -210,12 +186,15 @@ static int rate_network (const sn_network_t *n) /* {{{ */ static sn_network_t *individuum_to_network (const individuum_t *ind) /* {{{ */ { sn_network_t *n; + int mask[SN_NETWORK_INPUT_NUM (initial_network)]; + + memcpy (mask, ind, sizeof (mask)); n = sn_network_clone (initial_network); if (n == NULL) return (NULL); - apply (n, ind); + sn_network_cut (n, mask); sn_network_normalize (n); sn_network_compress (n); @@ -240,7 +219,7 @@ static int ind_rate (const void *arg) /* {{{ */ static void *ind_copy (const void *in) /* {{{ */ { - size_t s = sizeof (individuum_t) * cuts_num; + size_t s = sizeof (individuum_t) * inputs_num; void *out; out = malloc (s); @@ -257,77 +236,90 @@ static void ind_free (void *ind) /* {{{ */ free (ind); } /* }}} void ind_free */ -static void ind_print (const individuum_t *ind) +static void ind_print (const individuum_t *ind) /* {{{ */ +{ + int i; + + for (i = 0; i < inputs_num; i++) + { + printf ("%3i: %s\n", i, (ind[i] == 0) ? "-" : + (ind[i] < 0) ? "MIN" : "MAX"); + } + + printf ("# sn-cut"); + for (i = 0; i < inputs_num; i++) + { + if (ind[i] == 0) + continue; + printf (" %i:%s", i, (ind[i] < 0) ? "MIN" : "MAX"); + } + printf ("\n"); +} /* }}} void ind_print */ + +/* Simply makes sure the right amount of cutting positions exist. */ +static void mutate (individuum_t *ind, int this_cuts_num) /* {{{ */ { int i; - for (i = 0; i < cuts_num; i++) + if (this_cuts_num < 0) + { + this_cuts_num = 0; + for (i = 0; i < inputs_num; i++) + if (ind[i] != 0) + this_cuts_num++; + } + + while (this_cuts_num != cuts_num) { - int input = ind[i]; - int dir = 0; + i = sn_bounded_random (0, inputs_num - 1); - if (input < 0) + if ((this_cuts_num < cuts_num) + && (ind[i] == 0)) { - input *= -1; - dir = 1; + ind[i] = (sn_bounded_random (0, 1) * 2) - 1; + assert (ind[i] != 0); + this_cuts_num++; + } + else if ((this_cuts_num > cuts_num) + && (ind[i] != 0)) + { + ind[i] = 0; + this_cuts_num--; } - input--; - - printf ("%s(%3i)\n", (dir == 0) ? "MAX" : "MIN", input); } -} /* }}} void ind_print */ +} /* }}} void mutate */ static individuum_t *recombine (individuum_t *i0, individuum_t *i1) /* {{{ */ { individuum_t *offspring; - int cut_at; + int this_cuts_num; int i; if ((i0 == NULL) || (i1 == NULL)) return (NULL); - offspring = malloc (sizeof (*offspring) * cuts_num); + offspring = malloc (sizeof (*offspring) * inputs_num); if (offspring == NULL) return (NULL); - memset (offspring, 0, sizeof (*offspring) * cuts_num); + memset (offspring, 0, sizeof (*offspring) * inputs_num); - cut_at = sn_bounded_random (0, cuts_num); - for (i = 0; i < cuts_num; i++) + this_cuts_num = 0; + for (i = 0; i < this_cuts_num; i++) { - if (i < cut_at) + if (sn_bounded_random (0, 1) == 0) offspring[i] = i0[i]; else offspring[i] = i1[i]; + + if (offspring[i] != 0) + this_cuts_num++; } + mutate (offspring, this_cuts_num); + return (offspring); } /* }}} individuum_t *recombine */ -static void random_cut (individuum_t *ind, int index) /* {{{ */ -{ - int max_input = inputs_num - index; - - ind[index] = 0; - while (ind[index] == 0) - ind[index] = sn_bounded_random ((-1) * max_input, max_input); -} /* }}} void random_cut */ - -static void mutate (individuum_t *ind) /* {{{ */ -{ - int reset_input; - int i; - - reset_input = sn_bounded_random (0, 3 * cuts_num); - for (i = 0; i < cuts_num; i++) - { - if (reset_input == i) - random_cut (ind, i); - - if (sn_bounded_random (0, 100)) - ind[i] *= (-1); - } -} /* }}} void mutate */ - static int create_offspring (void) /* {{{ */ { individuum_t *i0; @@ -338,7 +330,6 @@ static int create_offspring (void) /* {{{ */ i1 = population_get_random (population); i2 = recombine (i0, i1); - mutate (i2); population_insert (population, i2); @@ -489,17 +480,14 @@ int main (int argc, char **argv) /* {{{ */ for (i = 0; i < max_population_size; i++) { /* create a random initial individuum */ individuum_t *ind; - int i; - ind = malloc (sizeof (*ind) * cuts_num); + ind = calloc (inputs_num, sizeof (*ind)); if (ind == NULL) { - fprintf (stderr, "malloc failed.\n"); + fprintf (stderr, "calloc failed.\n"); exit (EXIT_FAILURE); } - - for (i = 0; i < cuts_num; i++) - random_cut (ind, i); + mutate (ind, /* num cuts = */ 0); population_insert (population, ind); ind_free (ind); diff --git a/src/sn-oddevenmerge.c b/src/sn-oddevenmerge.c index 18a5669..e4161be 100644 --- a/src/sn-oddevenmerge.c +++ b/src/sn-oddevenmerge.c @@ -33,30 +33,36 @@ int main (int argc, char **argv) { - sn_network_t *n; - size_t inputs_num; + sn_network_t *sn_left; + sn_network_t *sn_right; + sn_network_t *oem; + int inputs_left; + int inputs_right; - if (argc != 2) + if (argc != 3) { - printf ("Usage: %s \n", argv[0]); + printf ("Usage: %s \n", argv[0]); return (0); } - inputs_num = (size_t) atoi (argv[1]); - if (inputs_num < 2) + inputs_left = atoi (argv[1]); + inputs_right = atoi (argv[2]); + if ((inputs_left < 1) || (inputs_right < 1)) { - fprintf (stderr, "Invalid number of inputs: %zu\n", inputs_num); + fprintf (stderr, "Invalid number of inputs: %i/%i\n", + inputs_left, inputs_right); return (1); } - n = sn_network_create_odd_even_mergesort (inputs_num); - if (n == NULL) - { - printf ("n == NULL!\n"); - return (1); - } + sn_left = sn_network_create (inputs_left); + sn_right = sn_network_create (inputs_right); + oem = sn_network_combine_odd_even_merge (sn_left, sn_right); + + sn_network_write (oem, stdout); - sn_network_write (n, stdout); + sn_network_destroy (sn_left); + sn_network_destroy (sn_right); + sn_network_destroy (oem); return (0); } /* int main */ diff --git a/src/sn-svg.c b/src/sn-svg.c index 850c422..d3da59c 100644 --- a/src/sn-svg.c +++ b/src/sn-svg.c @@ -23,6 +23,7 @@ #include #include +#include #include #include "sn_network.h" @@ -35,6 +36,39 @@ #define Y_SPACING 40 static double x_offset = OUTER_SPACING; +static _Bool embedded = 0; + +static void exit_usage (void) /* {{{ */ +{ + printf ("Usage: sn-svg [options] [file]\n" + "\n" + "Valid options are:\n" + " -e Create output suitable for embedding into other XML files.\n" + "\n"); + exit (EXIT_FAILURE); +} /* }}} void exit_usage */ + +static int read_options (int argc, char **argv) /* {{{ */ +{ + int option; + + while ((option = getopt (argc, argv, "eh?")) != -1) + { + switch (option) + { + case 'e': + embedded = 1; + break; + + case 'h': + case '?': + default: + exit_usage (); + } + } + + return (0); +} /* }}} int read_options */ static double determine_stage_width (sn_stage_t *s) { @@ -86,7 +120,7 @@ static double determine_network_width (sn_network_t *n) /* {{{ */ return (width); } /* }}} double determine_network_width */ -static int sn_svg_show_stage (sn_stage_t *s) +static int sn_svg_show_stage (sn_stage_t *s) /* {{{ */ { int lines[s->comparators_num]; int right[s->comparators_num]; @@ -122,10 +156,10 @@ static int sn_svg_show_stage (sn_stage_t *s) int y1 = Y_OFFSET + (SN_COMP_MIN (c) * Y_SPACING); int y2 = Y_OFFSET + (SN_COMP_MAX (c) * Y_SPACING); - printf (" \n" - " \n" - " \n", + " \n" + " \n", x1, y1, x2, y2, x1, y1, RADIUS, x2, y2, RADIUS); @@ -137,9 +171,9 @@ static int sn_svg_show_stage (sn_stage_t *s) printf ("\n"); return (0); -} /* int sn_svg_show_stage */ +} /* }}} int sn_svg_show_stage */ -int main (int argc, char **argv) +int main (int argc, char **argv) /* {{{ */ { sn_network_t *n; FILE *fh = NULL; @@ -149,16 +183,15 @@ int main (int argc, char **argv) int i; - if (argc == 1) + read_options (argc, argv); + + if ((argc - optind) == 0) fh = stdin; - else if (argc == 2) - fh = fopen (argv[1], "r"); + else if ((argc - optind) == 1) + fh = fopen (argv[optind], "r"); if (fh == NULL) - { - printf ("fh == NULL!\n"); - return (1); - } + exit_usage (); n = sn_network_read (fh); @@ -171,12 +204,16 @@ int main (int argc, char **argv) svg_height = (2 * Y_OFFSET) + ((SN_NETWORK_INPUT_NUM (n) - 1) * Y_SPACING); svg_width = determine_network_width (n); - printf ("\n" - "\n" - "\n", - svg_width, svg_height, svg_width, svg_height); + if (embedded) + printf ("\n", + svg_width, svg_height); + else + printf ("\n" + "\n" + "\n", + svg_width, svg_height, svg_width, svg_height); printf ("\n", PACKAGE_STRING); @@ -185,14 +222,14 @@ int main (int argc, char **argv) printf (" \n"); for (i = 0; i < SN_NETWORK_INPUT_NUM (n); i++) - printf (" \n", 0.0, Y_OFFSET + (i * Y_SPACING), x_offset, Y_OFFSET + (i * Y_SPACING)); - printf ("\n"); + printf ("\n"); return (0); -} /* int main */ +} /* }}} int main */ -/* vim: set shiftwidth=2 softtabstop=2 : */ +/* vim: set shiftwidth=2 softtabstop=2 fdm=marker : */ diff --git a/src/sn_comparator.c b/src/sn_comparator.c index 18361e4..a819576 100644 --- a/src/sn_comparator.c +++ b/src/sn_comparator.c @@ -42,12 +42,17 @@ sn_comparator_t *sn_comparator_create (int min, int max) c->min = min; c->max = max; + c->user_data = NULL; + c->free_func = NULL; return (c); } /* sn_comparator_t *sn_comparator_create */ void sn_comparator_destroy (sn_comparator_t *c) { + if (c->free_func != NULL) + c->free_func (c->user_data); + if (c != NULL) free (c); } /* void sn_comparator_destroy */ diff --git a/src/sn_comparator.h b/src/sn_comparator.h index db46982..6e3f7f5 100644 --- a/src/sn_comparator.h +++ b/src/sn_comparator.h @@ -35,6 +35,8 @@ struct sn_comparator_s { int min; /**< Index of the line onto which the smaller element will be put. */ int max; /**< Index of the line onto which the larger element will be put. */ + void *user_data; /**< Pointer to user data. */ + void (*free_func) (void *); /**< Pointer to a function used to free the user data pointer. */ }; typedef struct sn_comparator_s sn_comparator_t; @@ -47,6 +49,11 @@ typedef struct sn_comparator_s sn_comparator_t; /** Returns the index of the line onto which the larger element will be put. */ #define SN_COMP_MAX(c) (c)->max +/** Expands to the user data pointer. */ +#define SN_COMP_USER_DATA(c) (c)->user_data +/** Expands to the free-function pointer. */ +#define SN_COMP_FREE_FUNC(c) (c)->free_func + /** * Allocates, initializes and returns a new comparator object. The returned * pointer must be freed by sn_comparator_destroy(). diff --git a/src/sn_network.c b/src/sn_network.c index 1b3dd36..6908cf8 100644 --- a/src/sn_network.c +++ b/src/sn_network.c @@ -464,6 +464,21 @@ int sn_network_normalize (sn_network_t *n) /* {{{ */ return (0); } /* }}} int sn_network_normalize */ +int sn_network_remove_input (sn_network_t *n, int input) /* {{{ */ +{ + int i; + + if ((n == NULL) || (input < 0) || (input >= n->inputs_num)) + return (EINVAL); + + for (i = 0; i < n->stages_num; i++) + sn_stage_remove_input (n->stages[i], input); + + n->inputs_num--; + + return (0); +} /* }}} int sn_network_remove_input */ + int sn_network_cut_at (sn_network_t *n, int input, /* {{{ */ enum sn_network_cut_dir_e dir) { @@ -492,13 +507,36 @@ int sn_network_cut_at (sn_network_t *n, int input, /* {{{ */ assert (((dir == DIR_MIN) && (position == 0)) || ((dir == DIR_MAX) && (position == (n->inputs_num - 1)))); + sn_network_remove_input (n, position); + + return (0); +} /* }}} int sn_network_cut_at */ + +int sn_network_cut (sn_network_t *n, int *mask) /* {{{ */ +{ + int inputs_num; + int i; + for (i = 0; i < n->stages_num; i++) - sn_stage_remove_input (n->stages[i], position); + { + sn_stage_t *s = n->stages[i]; - n->inputs_num--; + sn_stage_cut (s, mask, n->stages); + } + + /* Use a copy of this member since it will be updated by + * sn_network_remove_input(). */ + inputs_num = n->inputs_num; + for (i = 0; i < inputs_num; i++) + { + if (mask[i] < 0) + sn_network_remove_input (n, 0); + else if (mask[i] > 0) + sn_network_remove_input (n, n->inputs_num - 1); + } return (0); -} /* }}} int sn_network_cut_at */ +} /* }}} int sn_network_cut */ /* sn_network_concatenate * diff --git a/src/sn_network.h b/src/sn_network.h index f56e3ca..8e6d492 100644 --- a/src/sn_network.h +++ b/src/sn_network.h @@ -26,7 +26,6 @@ * \endverbatim **/ - #ifndef SN_NETWORK_H #define SN_NETWORK_H 1 @@ -211,6 +210,16 @@ int sn_network_compress (sn_network_t *n); int sn_network_normalize (sn_network_t *n); /** + * Removes an input and all comparators touching that input from the comparator + * network. + * + * \param n The network to modify. + * \param input The zero-based index of the input to remove. + * \return Zero on success, non-zero on failure. + */ +int sn_network_remove_input (sn_network_t *n, int input); + +/** * Removes an inputs from a comparator network by assuming positive or negative * infinity to be supplied to a given input. The value will take a * deterministic way through the comparator network. After removing the path @@ -226,6 +235,9 @@ int sn_network_normalize (sn_network_t *n); */ int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir); +/* FIXME: Documentation */ +int sn_network_cut (sn_network_t *n, int *mask); + /** * An alias for sn_network_combine_odd_even_merge(). */ diff --git a/src/sn_stage.c b/src/sn_stage.c index d89fc89..ae61578 100644 --- a/src/sn_stage.c +++ b/src/sn_stage.c @@ -166,8 +166,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); @@ -361,6 +366,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; diff --git a/src/sn_stage.h b/src/sn_stage.h index d947515..6d008d6 100644 --- a/src/sn_stage.h +++ b/src/sn_stage.h @@ -191,6 +191,9 @@ int sn_stage_swap (sn_stage_t *s, int con0, int con1); */ int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir); +/* FIXME: Documentation */ +int sn_stage_cut (sn_stage_t *s, int *mask, sn_stage_t **prev); + /** * Remove an input from a stage, remove all touching comparators and adapt the * input indexes of all remaining comparators.