2 * libsortnetwork - src/sn_stage.c
3 * Copyright (C) 2008-2010 Florian octo Forster
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License as published by the
7 * Free Software Foundation; only version 2 of the License is applicable.
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
14 * You should have received a copy of the GNU General Public License along
15 * with this program; if not, write to the Free Software Foundation, Inc.,
16 * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 * Florian octo Forster <ff at octo.it>
22 #ifndef _ISOC99_SOURCE
23 # define _ISOC99_SOURCE
25 #ifndef _POSIX_C_SOURCE
26 # define _POSIX_C_SOURCE 200112L
34 #include "sn_comparator.h"
37 sn_stage_t *sn_stage_create (int depth)
41 s = (sn_stage_t *) malloc (sizeof (sn_stage_t));
44 memset (s, '\0', sizeof (sn_stage_t));
49 } /* sn_stage_t *sn_stage_create */
51 void sn_stage_destroy (sn_stage_t *s)
55 if (s->comparators != NULL)
56 free (s->comparators);
58 } /* void sn_stage_destroy */
60 int sn_stage_sort (sn_stage_t *s, int *values)
65 for (i = 0; i < s->comparators_num; i++)
67 c = s->comparators + i;
68 if (values[c->min] > values[c->max])
72 temp = values[c->min];
73 values[c->min] = values[c->max];
74 values[c->max] = temp;
79 } /* int sn_stage_sort */
81 int sn_stage_comparator_add (sn_stage_t *s, const sn_comparator_t *c)
83 sn_comparator_t *temp;
86 if ((s == NULL) || (c == NULL))
89 i = sn_stage_comparator_check_conflict (s, c);
93 temp = (sn_comparator_t *) realloc (s->comparators,
94 (s->comparators_num + 1) * sizeof (sn_comparator_t));
97 s->comparators = temp;
100 for (i = 0; i < s->comparators_num; i++)
101 if (sn_comparator_compare (c, s->comparators + i) <= 0)
104 /* Insert the elements in ascending order */
105 assert (i <= s->comparators_num);
106 if (i < s->comparators_num)
108 int nmemb = s->comparators_num - i;
109 memmove (s->comparators + (i + 1), s->comparators + i,
110 nmemb * sizeof (sn_comparator_t));
112 memcpy (s->comparators + i, c, sizeof (sn_comparator_t));
113 s->comparators_num++;
116 } /* int sn_stage_comparator_add */
118 int sn_stage_comparator_remove (sn_stage_t *s, int c_num)
120 int nmemb = s->comparators_num - (c_num + 1);
121 sn_comparator_t *temp;
123 if ((s == NULL) || (s->comparators_num <= c_num))
126 assert (c_num < s->comparators_num);
130 memmove (s->comparators + c_num, s->comparators + (c_num + 1),
131 nmemb * sizeof (sn_comparator_t));
132 s->comparators_num--;
134 /* Free the unused memory */
135 if (s->comparators_num == 0)
137 free (s->comparators);
138 s->comparators = NULL;
142 temp = (sn_comparator_t *) realloc (s->comparators,
143 s->comparators_num * sizeof (sn_comparator_t));
146 s->comparators = temp;
150 } /* int sn_stage_comparator_remove */
152 sn_stage_t *sn_stage_clone (const sn_stage_t *s)
157 s_copy = sn_stage_create (s->depth);
161 s_copy->comparators = (sn_comparator_t *) malloc (s->comparators_num
162 * sizeof (sn_comparator_t));
163 if (s_copy->comparators == NULL)
169 for (i = 0; i < s->comparators_num; i++)
171 SN_COMP_MIN (s_copy->comparators + i) = SN_COMP_MIN (s->comparators + i);
172 SN_COMP_MAX (s_copy->comparators + i) = SN_COMP_MAX (s->comparators + i);
173 SN_COMP_USER_DATA (s_copy->comparators + i) = NULL;
174 SN_COMP_FREE_FUNC (s_copy->comparators + i) = NULL;
176 s_copy->comparators_num = s->comparators_num;
179 } /* sn_stage_t *sn_stage_clone */
181 int sn_stage_comparator_check_conflict (sn_stage_t *s, const sn_comparator_t *c0)
185 for (i = 0; i < s->comparators_num; i++)
187 sn_comparator_t *c1 = s->comparators + i;
188 if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
189 || (SN_COMP_MIN(c0) == SN_COMP_MAX(c1))
190 || (SN_COMP_MAX(c0) == SN_COMP_MIN(c1))
191 || (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
193 if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
194 && (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
202 } /* int sn_stage_comparator_check_conflict */
204 int sn_stage_show (sn_stage_t *s)
206 int lines[s->comparators_num];
207 int right[s->comparators_num];
213 for (i = 0; i < s->comparators_num; i++)
219 for (i = 0; i < s->comparators_num; i++)
222 sn_comparator_t *c = s->comparators + i;
224 for (j = 0; j < lines_used; j++)
225 if (SN_COMP_LEFT (c) > right[j])
229 right[j] = SN_COMP_RIGHT (c);
234 for (i = 0; i < lines_used; i++)
236 printf ("%3i: ", s->depth);
238 for (j = 0; j <= right[i]; j++)
243 for (k = 0; k < s->comparators_num; k++)
245 sn_comparator_t *c = s->comparators + k;
247 /* Check if this comparator is displayed on another line */
251 if (j == SN_COMP_MIN (c))
253 else if (j == SN_COMP_MAX (c))
256 if ((j >= SN_COMP_LEFT (c)) && (j < SN_COMP_RIGHT (c)))
259 if ((on_elem != 0) || (line_after != 0))
270 else if (on_elem == -1)
284 } /* for (columns) */
290 } /* int sn_stage_show */
292 int sn_stage_invert (sn_stage_t *s)
299 for (i = 0; i < s->comparators_num; i++)
300 sn_comparator_invert (s->comparators + i);
303 } /* int sn_stage_invert */
305 int sn_stage_shift (sn_stage_t *s, int sw, int inputs_num)
309 if ((s == NULL) || (inputs_num < 2))
316 for (i = 0; i < s->comparators_num; i++)
317 sn_comparator_shift (s->comparators + i, sw, inputs_num);
320 } /* int sn_stage_shift */
322 int sn_stage_swap (sn_stage_t *s, int con0, int con1)
329 for (i = 0; i < s->comparators_num; i++)
330 sn_comparator_swap (s->comparators + i, con0, con1);
333 } /* int sn_stage_swap */
335 int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir)
337 int new_position = input;
340 if ((s == NULL) || (input < 0))
343 for (i = 0; i < s->comparators_num; i++)
345 sn_comparator_t *c = s->comparators + i;
347 if ((SN_COMP_MIN (c) != input) && (SN_COMP_MAX (c) != input))
350 if ((dir == DIR_MIN) && (SN_COMP_MAX (c) == input))
352 new_position = SN_COMP_MIN (c);
354 else if ((dir == DIR_MAX) && (SN_COMP_MIN (c) == input))
356 new_position = SN_COMP_MAX (c);
362 if (i < s->comparators_num)
363 sn_stage_comparator_remove (s, i);
366 return (new_position);
367 } /* int sn_stage_cut_at */
369 int sn_stage_cut (sn_stage_t *s, int *mask, /* {{{ */
374 if ((s == NULL) || (mask == NULL) || (prev == NULL))
377 for (i = 0; i < s->comparators_num; i++)
379 sn_comparator_t *c = s->comparators + i;
380 int left = SN_COMP_LEFT (c);
381 int right = SN_COMP_RIGHT (c);
383 if ((mask[left] == 0)
384 && (mask[right] == 0))
387 /* Check if we need to update the cut position */
388 if ((mask[left] != mask[right])
389 && ((mask[left] > 0) || (mask[right] < 0)))
395 mask[right] = mask[left];
398 for (j = s->depth - 1; j >= 0; j--)
399 sn_stage_swap (prev[j],
403 sn_stage_comparator_remove (s, i);
405 } /* for (i = 0; i < s->comparators_num; i++) */
408 } /* }}} int sn_stage_cut */
410 int sn_stage_remove_input (sn_stage_t *s, int input)
414 for (i = 0; i < s->comparators_num; i++)
416 sn_comparator_t *c = s->comparators + i;
418 if ((SN_COMP_MIN (c) == input) || (SN_COMP_MAX (c) == input))
420 sn_stage_comparator_remove (s, i);
425 if (SN_COMP_MIN (c) > input)
426 SN_COMP_MIN (c) = SN_COMP_MIN (c) - 1;
427 if (SN_COMP_MAX (c) > input)
428 SN_COMP_MAX (c) = SN_COMP_MAX (c) - 1;
434 sn_stage_t *sn_stage_read (FILE *fh)
440 s = sn_stage_create (0);
444 while (fgets (buffer, sizeof (buffer), fh) != NULL)
449 if ((buffer[0] == '\0') || (buffer[0] == '\n') || (buffer[0] == '\r'))
454 c.min = (int) strtol (buffer_ptr, &endptr, 0);
455 if (buffer_ptr == endptr)
460 c.max = (int) strtol (buffer_ptr, &endptr, 0);
461 if (buffer_ptr == endptr)
464 sn_stage_comparator_add (s, &c);
467 if (s->comparators_num == 0)
469 sn_stage_destroy (s);
474 } /* sn_stage_t *sn_stage_read */
476 int sn_stage_write (sn_stage_t *s, FILE *fh)
480 if (s->comparators_num <= 0)
483 for (i = 0; i < s->comparators_num; i++)
484 fprintf (fh, "%i %i\n",
485 SN_COMP_MIN (s->comparators + i),
486 SN_COMP_MAX (s->comparators + i));
490 } /* int sn_stage_write */
492 int sn_stage_serialize (sn_stage_t *s,
493 char **ret_buffer, size_t *ret_buffer_size)
500 if (s->comparators_num <= 0)
503 buffer = *ret_buffer;
504 buffer_size = *ret_buffer_size;
506 #define SNPRINTF_OR_FAIL(...) \
507 status = snprintf (buffer, buffer_size, __VA_ARGS__); \
508 if ((status < 1) || (((size_t) status) >= buffer_size)) \
511 buffer_size -= status;
513 for (i = 0; i < s->comparators_num; i++)
515 SNPRINTF_OR_FAIL ("%i %i\r\n",
516 SN_COMP_MIN (s->comparators + i),
517 SN_COMP_MAX (s->comparators + i));
520 SNPRINTF_OR_FAIL ("\r\n");
522 *ret_buffer = buffer;
523 *ret_buffer_size = buffer_size;
525 } /* int sn_stage_serialize */
527 sn_stage_t *sn_stage_unserialize (char **ret_buffer, size_t *ret_buffer_size)
534 buffer = *ret_buffer;
535 buffer_size = *ret_buffer_size;
537 if (buffer_size == 0)
540 s = sn_stage_create (0);
545 while (buffer_size > 0)
550 size_t substr_length;
552 endptr = strchr (buffer, '\n');
563 substr_length = strlen (buffer);
565 buffer_size -= (substr_length + 1);
567 if ((substr_length > 0) && (substr[substr_length - 1] == '\r'))
569 substr[substr_length - 1] = 0;
573 if (substr_length == 0)
580 c.min = (int) strtol (substr, &endptr, 0);
581 if (substr == endptr)
589 c.max = (int) strtol (substr, &endptr, 0);
590 if (substr == endptr)
596 sn_stage_comparator_add (s, &c);
597 } /* while (buffer_size > 0) */
599 if ((status != 0) || (s->comparators_num == 0))
601 sn_stage_destroy (s);
605 *ret_buffer = buffer;
606 *ret_buffer_size = buffer_size;
608 } /* sn_stage_t *sn_stage_unserialize */
610 /* vim: set shiftwidth=2 softtabstop=2 expandtab : */