2 * libsortnetwork - src/sn_stage.c
3 * Copyright (C) 2008-2010 Florian octo Forster
5 * This library is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU Lesser General Public License as published by
7 * the Free Software Foundation; either version 2.1 of the License, or (at
8 * your option) any later version.
10 * This library is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
15 * You should have received a copy of the GNU Lesser General Public License
16 * along with this library; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 * Florian octo Forster <ff at octo.it>
23 #ifndef _ISOC99_SOURCE
24 # define _ISOC99_SOURCE
26 #ifndef _POSIX_C_SOURCE
27 # define _POSIX_C_SOURCE 200112L
35 #include "sn_comparator.h"
38 sn_stage_t *sn_stage_create (int depth)
42 s = (sn_stage_t *) malloc (sizeof (sn_stage_t));
45 memset (s, '\0', sizeof (sn_stage_t));
50 } /* sn_stage_t *sn_stage_create */
52 void sn_stage_destroy (sn_stage_t *s)
56 if (s->comparators != NULL)
57 free (s->comparators);
59 } /* void sn_stage_destroy */
61 int sn_stage_sort (sn_stage_t *s, int *values)
66 for (i = 0; i < s->comparators_num; i++)
68 c = s->comparators + i;
69 if (values[c->min] > values[c->max])
73 temp = values[c->min];
74 values[c->min] = values[c->max];
75 values[c->max] = temp;
80 } /* int sn_stage_sort */
82 int sn_stage_comparator_add (sn_stage_t *s, const sn_comparator_t *c)
84 sn_comparator_t *temp;
87 if ((s == NULL) || (c == NULL))
90 i = sn_stage_comparator_check_conflict (s, c);
94 temp = (sn_comparator_t *) realloc (s->comparators,
95 (s->comparators_num + 1) * sizeof (sn_comparator_t));
98 s->comparators = temp;
101 for (i = 0; i < s->comparators_num; i++)
102 if (sn_comparator_compare (c, s->comparators + i) <= 0)
105 /* Insert the elements in ascending order */
106 assert (i <= s->comparators_num);
107 if (i < s->comparators_num)
109 int nmemb = s->comparators_num - i;
110 memmove (s->comparators + (i + 1), s->comparators + i,
111 nmemb * sizeof (sn_comparator_t));
113 memcpy (s->comparators + i, c, sizeof (sn_comparator_t));
114 s->comparators_num++;
117 } /* int sn_stage_comparator_add */
119 int sn_stage_comparator_remove (sn_stage_t *s, int c_num)
121 int nmemb = s->comparators_num - (c_num + 1);
122 sn_comparator_t *temp;
124 if ((s == NULL) || (s->comparators_num <= c_num))
127 assert (c_num < s->comparators_num);
131 memmove (s->comparators + c_num, s->comparators + (c_num + 1),
132 nmemb * sizeof (sn_comparator_t));
133 s->comparators_num--;
135 /* Free the unused memory */
136 if (s->comparators_num == 0)
138 free (s->comparators);
139 s->comparators = NULL;
143 temp = (sn_comparator_t *) realloc (s->comparators,
144 s->comparators_num * sizeof (sn_comparator_t));
147 s->comparators = temp;
151 } /* int sn_stage_comparator_remove */
153 sn_stage_t *sn_stage_clone (const sn_stage_t *s)
158 s_copy = sn_stage_create (s->depth);
162 s_copy->comparators = (sn_comparator_t *) malloc (s->comparators_num
163 * sizeof (sn_comparator_t));
164 if (s_copy->comparators == NULL)
170 for (i = 0; i < s->comparators_num; i++)
172 SN_COMP_MIN (s_copy->comparators + i) = SN_COMP_MIN (s->comparators + i);
173 SN_COMP_MAX (s_copy->comparators + i) = SN_COMP_MAX (s->comparators + i);
174 SN_COMP_USER_DATA (s_copy->comparators + i) = NULL;
175 SN_COMP_FREE_FUNC (s_copy->comparators + i) = NULL;
177 s_copy->comparators_num = s->comparators_num;
180 } /* sn_stage_t *sn_stage_clone */
182 int sn_stage_comparator_check_conflict (sn_stage_t *s, const sn_comparator_t *c0)
186 for (i = 0; i < s->comparators_num; i++)
188 sn_comparator_t *c1 = s->comparators + i;
189 if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
190 || (SN_COMP_MIN(c0) == SN_COMP_MAX(c1))
191 || (SN_COMP_MAX(c0) == SN_COMP_MIN(c1))
192 || (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
194 if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
195 && (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
203 } /* int sn_stage_comparator_check_conflict */
205 int sn_stage_show (sn_stage_t *s)
207 int lines[s->comparators_num];
208 int right[s->comparators_num];
214 for (i = 0; i < s->comparators_num; i++)
220 for (i = 0; i < s->comparators_num; i++)
223 sn_comparator_t *c = s->comparators + i;
225 for (j = 0; j < lines_used; j++)
226 if (SN_COMP_LEFT (c) > right[j])
230 right[j] = SN_COMP_RIGHT (c);
235 for (i = 0; i < lines_used; i++)
237 printf ("%3i: ", s->depth);
239 for (j = 0; j <= right[i]; j++)
244 for (k = 0; k < s->comparators_num; k++)
246 sn_comparator_t *c = s->comparators + k;
248 /* Check if this comparator is displayed on another line */
252 if (j == SN_COMP_MIN (c))
254 else if (j == SN_COMP_MAX (c))
257 if ((j >= SN_COMP_LEFT (c)) && (j < SN_COMP_RIGHT (c)))
260 if ((on_elem != 0) || (line_after != 0))
271 else if (on_elem == -1)
285 } /* for (columns) */
291 } /* int sn_stage_show */
293 int sn_stage_invert (sn_stage_t *s)
300 for (i = 0; i < s->comparators_num; i++)
301 sn_comparator_invert (s->comparators + i);
304 } /* int sn_stage_invert */
306 int sn_stage_shift (sn_stage_t *s, int sw, int inputs_num)
310 if ((s == NULL) || (inputs_num < 2))
317 for (i = 0; i < s->comparators_num; i++)
318 sn_comparator_shift (s->comparators + i, sw, inputs_num);
321 } /* int sn_stage_shift */
323 static int sn_stage_unify__qsort_callback (const void *p0, const void *p1) /* {{{ */
325 return (sn_comparator_compare (p0, p1));
326 } /* }}} int sn_stage_unify__qsort_callback */
328 int sn_stage_unify (sn_stage_t *s) /* {{{ */
333 qsort (s->comparators,
334 (size_t) s->comparators_num,
335 sizeof (*s->comparators),
336 sn_stage_unify__qsort_callback);
339 } /* }}} int sn_stage_unify */
341 int sn_stage_swap (sn_stage_t *s, int con0, int con1)
348 for (i = 0; i < s->comparators_num; i++)
349 sn_comparator_swap (s->comparators + i, con0, con1);
352 } /* int sn_stage_swap */
354 int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir)
356 int new_position = input;
359 if ((s == NULL) || (input < 0))
362 for (i = 0; i < s->comparators_num; i++)
364 sn_comparator_t *c = s->comparators + i;
366 if ((SN_COMP_MIN (c) != input) && (SN_COMP_MAX (c) != input))
369 if ((dir == DIR_MIN) && (SN_COMP_MAX (c) == input))
371 new_position = SN_COMP_MIN (c);
373 else if ((dir == DIR_MAX) && (SN_COMP_MIN (c) == input))
375 new_position = SN_COMP_MAX (c);
381 if (i < s->comparators_num)
382 sn_stage_comparator_remove (s, i);
385 return (new_position);
386 } /* int sn_stage_cut_at */
388 int sn_stage_cut (sn_stage_t *s, int *mask, /* {{{ */
393 if ((s == NULL) || (mask == NULL) || (prev == NULL))
396 for (i = 0; i < s->comparators_num; i++)
398 sn_comparator_t *c = s->comparators + i;
399 int left = SN_COMP_LEFT (c);
400 int right = SN_COMP_RIGHT (c);
402 if ((mask[left] == 0)
403 && (mask[right] == 0))
406 /* Check if we need to update the cut position */
407 if ((mask[left] != mask[right])
408 && ((mask[left] > 0) || (mask[right] < 0)))
414 mask[right] = mask[left];
417 for (j = s->depth - 1; j >= 0; j--)
418 sn_stage_swap (prev[j],
422 sn_stage_comparator_remove (s, i);
424 } /* for (i = 0; i < s->comparators_num; i++) */
427 } /* }}} int sn_stage_cut */
429 int sn_stage_remove_input (sn_stage_t *s, int input)
433 for (i = 0; i < s->comparators_num; i++)
435 sn_comparator_t *c = s->comparators + i;
437 if ((SN_COMP_MIN (c) == input) || (SN_COMP_MAX (c) == input))
439 sn_stage_comparator_remove (s, i);
444 if (SN_COMP_MIN (c) > input)
445 SN_COMP_MIN (c) = SN_COMP_MIN (c) - 1;
446 if (SN_COMP_MAX (c) > input)
447 SN_COMP_MAX (c) = SN_COMP_MAX (c) - 1;
453 sn_stage_t *sn_stage_read (FILE *fh)
459 s = sn_stage_create (0);
463 while (fgets (buffer, sizeof (buffer), fh) != NULL)
468 if ((buffer[0] == '\0') || (buffer[0] == '\n') || (buffer[0] == '\r'))
473 c.min = (int) strtol (buffer_ptr, &endptr, 0);
474 if (buffer_ptr == endptr)
479 c.max = (int) strtol (buffer_ptr, &endptr, 0);
480 if (buffer_ptr == endptr)
483 sn_stage_comparator_add (s, &c);
486 if (s->comparators_num == 0)
488 sn_stage_destroy (s);
493 } /* sn_stage_t *sn_stage_read */
495 int sn_stage_write (sn_stage_t *s, FILE *fh)
499 if (s->comparators_num <= 0)
502 for (i = 0; i < s->comparators_num; i++)
503 fprintf (fh, "%i %i\n",
504 SN_COMP_MIN (s->comparators + i),
505 SN_COMP_MAX (s->comparators + i));
509 } /* int sn_stage_write */
511 int sn_stage_serialize (sn_stage_t *s,
512 char **ret_buffer, size_t *ret_buffer_size)
519 if (s->comparators_num <= 0)
522 buffer = *ret_buffer;
523 buffer_size = *ret_buffer_size;
525 #define SNPRINTF_OR_FAIL(...) \
526 status = snprintf (buffer, buffer_size, __VA_ARGS__); \
527 if ((status < 1) || (((size_t) status) >= buffer_size)) \
530 buffer_size -= status;
532 for (i = 0; i < s->comparators_num; i++)
534 SNPRINTF_OR_FAIL ("%i %i\r\n",
535 SN_COMP_MIN (s->comparators + i),
536 SN_COMP_MAX (s->comparators + i));
539 SNPRINTF_OR_FAIL ("\r\n");
541 *ret_buffer = buffer;
542 *ret_buffer_size = buffer_size;
544 } /* int sn_stage_serialize */
546 sn_stage_t *sn_stage_unserialize (char **ret_buffer, size_t *ret_buffer_size)
553 buffer = *ret_buffer;
554 buffer_size = *ret_buffer_size;
556 if (buffer_size == 0)
559 s = sn_stage_create (0);
564 while (buffer_size > 0)
569 size_t substr_length;
571 endptr = strchr (buffer, '\n');
582 substr_length = strlen (buffer);
584 buffer_size -= (substr_length + 1);
586 if ((substr_length > 0) && (substr[substr_length - 1] == '\r'))
588 substr[substr_length - 1] = 0;
592 if (substr_length == 0)
599 c.min = (int) strtol (substr, &endptr, 0);
600 if (substr == endptr)
608 c.max = (int) strtol (substr, &endptr, 0);
609 if (substr == endptr)
615 sn_stage_comparator_add (s, &c);
616 } /* while (buffer_size > 0) */
618 if ((status != 0) || (s->comparators_num == 0))
620 sn_stage_destroy (s);
624 *ret_buffer = buffer;
625 *ret_buffer_size = buffer_size;
627 } /* sn_stage_t *sn_stage_unserialize */
629 int sn_stage_compare (const sn_stage_t *s0, const sn_stage_t *s1) /* {{{ */
641 if (s0->comparators_num < s1->comparators_num)
643 else if (s0->comparators_num > s1->comparators_num)
646 for (i = 0; i < s0->comparators_num; i++)
648 status = sn_comparator_compare (s0->comparators + i, s1->comparators + i);
654 } /* }}} int sn_stage_compare */
656 uint64_t sn_stage_get_hashval (const sn_stage_t *s) /* {{{ */
664 hash = (uint64_t) s->depth;
666 for (i = 0; i < s->comparators_num; i++)
667 hash = (hash * 99991) + sn_comparator_get_hashval (s->comparators + i);
670 } /* }}} uint64_t sn_stage_get_hashval */
672 /* vim: set shiftwidth=2 softtabstop=2 expandtab fdm=marker : */