src/sn_stage.c

   1 /**
   2  * libsortnetwork - src/sn_stage.c
   3  * Copyright (C) 2008-2010  Florian octo Forster
   4  *
   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.
   8  *
   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.
  13  *
  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
  17  *
  18  * Authors:
  19  *   Florian octo Forster <ff at octo.it>
  20  **/
  21
  22 #ifndef _ISOC99_SOURCE
  23 # define _ISOC99_SOURCE
  24 #endif
  25 #ifndef _POSIX_C_SOURCE
  26 # define _POSIX_C_SOURCE 200112L
  27 #endif
  28
  29 #include <stdlib.h>
  30 #include <string.h>
  31 #include <assert.h>
  32
  33 #include "sn_comparator.h"
  34 #include "sn_stage.h"
  35
  36 sn_stage_t *sn_stage_create (int depth)
  37 {
  38   sn_stage_t *s;
  39
  40   s = (sn_stage_t *) malloc (sizeof (sn_stage_t));
  41   if (s == NULL)
  42     return (NULL);
  43   memset (s, '\0', sizeof (sn_stage_t));
  44
  45   s->depth = depth;
  46
  47   return (s);
  48 } /* sn_stage_t *sn_stage_create */
  49
  50 void sn_stage_destroy (sn_stage_t *s)
  51 {
  52   if (s == NULL)
  53     return;
  54   if (s->comparators != NULL)
  55     free (s->comparators);
  56   free (s);
  57 } /* void sn_stage_destroy */
  58
  59 int sn_stage_sort (sn_stage_t *s, int *values)
  60 {
  61   sn_comparator_t *c;
  62   int i;
  63
  64   for (i = 0; i < s->comparators_num; i++)
  65   {
  66     c = s->comparators + i;
  67     if (values[c->min] > values[c->max])
  68     {
  69       int temp;
  70
  71       temp = values[c->min];
  72       values[c->min] = values[c->max];
  73       values[c->max] = temp;
  74     }
  75   }
  76
  77   return (0);
  78 } /* int sn_stage_sort */
  79
  80 int sn_stage_comparator_add (sn_stage_t *s, const sn_comparator_t *c)
  81 {
  82   sn_comparator_t *temp;
  83   int i;
  84
  85   temp = (sn_comparator_t *) realloc (s->comparators,
  86       (s->comparators_num + 1) * sizeof (sn_comparator_t));
  87   if (temp == NULL)
  88     return (-1);
  89   s->comparators = temp;
  90   temp = NULL;
  91
  92   for (i = 0; i < s->comparators_num; i++)
  93     if (sn_comparator_compare (c, s->comparators + i) <= 0)
  94       break;
  95
  96   /* Insert the elements in ascending order */
  97   assert (i <= s->comparators_num);
  98   if (i < s->comparators_num)
  99   {
 100     int nmemb = s->comparators_num - i;
 101     memmove (s->comparators + (i + 1), s->comparators + i,
 102         nmemb * sizeof (sn_comparator_t));
 103   }
 104   memcpy (s->comparators + i, c, sizeof (sn_comparator_t));
 105   s->comparators_num++;
 106
 107   return (0);
 108 } /* int sn_stage_comparator_add */
 109
 110 int sn_stage_comparator_remove (sn_stage_t *s, int c_num)
 111 {
 112   int nmemb = s->comparators_num - (c_num + 1);
 113   sn_comparator_t *temp;
 114
 115   assert (c_num < s->comparators_num);
 116   assert (c_num >= 0);
 117
 118   if (nmemb > 0)
 119     memmove (s->comparators + c_num, s->comparators + (c_num + 1),
 120         nmemb * sizeof (sn_comparator_t));
 121   s->comparators_num--;
 122
 123   /* Free the unused memory */
 124   if (s->comparators_num == 0)
 125   {
 126     free (s->comparators);
 127     s->comparators = NULL;
 128   }
 129   else
 130   {
 131     temp = (sn_comparator_t *) realloc (s->comparators,
 132         s->comparators_num * sizeof (sn_comparator_t));
 133     if (temp == NULL)
 134       return (-1);
 135     s->comparators = temp;
 136   }
 137
 138   return (0);
 139 } /* int sn_stage_comparator_remove */
 140
 141 sn_stage_t *sn_stage_clone (const sn_stage_t *s)
 142 {
 143   sn_stage_t *s_copy;
 144
 145   s_copy = sn_stage_create (s->depth);
 146   if (s_copy == NULL)
 147     return (NULL);
 148
 149   s_copy->comparators = (sn_comparator_t *) malloc (s->comparators_num
 150       * sizeof (sn_comparator_t));
 151   if (s_copy->comparators == NULL)
 152   {
 153     free (s_copy);
 154     return (NULL);
 155   }
 156
 157   memcpy (s_copy->comparators, s->comparators,
 158       s->comparators_num * sizeof (sn_comparator_t));
 159   s_copy->comparators_num = s->comparators_num;
 160
 161   return (s_copy);
 162 } /* sn_stage_t *sn_stage_clone */
 163
 164 int sn_stage_comparator_check_conflict (sn_stage_t *s, const sn_comparator_t *c0)
 165 {
 166   int i;
 167
 168   for (i = 0; i < s->comparators_num; i++)
 169   {
 170     sn_comparator_t *c1 = s->comparators + i;
 171     if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
 172         || (SN_COMP_MIN(c0) == SN_COMP_MAX(c1))
 173         || (SN_COMP_MAX(c0) == SN_COMP_MIN(c1))
 174         || (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
 175     {
 176       if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
 177           && (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
 178         return (2);
 179       else
 180         return (1);
 181     }
 182   }
 183
 184   return (0);
 185 } /* int sn_stage_comparator_check_conflict */
 186
 187 int sn_stage_show (sn_stage_t *s)
 188 {
 189   int lines[s->comparators_num];
 190   int right[s->comparators_num];
 191   int lines_used = 0;
 192   int i;
 193   int j;
 194   int k;
 195
 196   for (i = 0; i < s->comparators_num; i++)
 197   {
 198     lines[i] = -1;
 199     right[i] = -1;
 200   }
 201
 202   for (i = 0; i < s->comparators_num; i++)
 203   {
 204     int j;
 205     sn_comparator_t *c = s->comparators + i;
 206
 207     for (j = 0; j < lines_used; j++)
 208       if (SN_COMP_LEFT (c) > right[j])
 209         break;
 210
 211     lines[i] = j;
 212     right[j] = SN_COMP_RIGHT (c);
 213     if (j >= lines_used)
 214       lines_used = j + 1;
 215   }
 216
 217   for (i = 0; i < lines_used; i++)
 218   {
 219     printf ("%3i: ", s->depth);
 220
 221     for (j = 0; j <= right[i]; j++)
 222     {
 223       int on_elem = 0;
 224       int line_after = 0;
 225
 226       for (k = 0; k < s->comparators_num; k++)
 227       {
 228         sn_comparator_t *c = s->comparators + k;
 229
 230         /* Check if this comparator is displayed on another line */
 231         if (lines[k] != i)
 232           continue;
 233
 234         if (j == SN_COMP_MIN (c))
 235           on_elem = -1;
 236         else if (j == SN_COMP_MAX (c))
 237           on_elem = 1;
 238
 239         if ((j >= SN_COMP_LEFT (c)) && (j < SN_COMP_RIGHT (c)))
 240           line_after = 1;
 241
 242         if ((on_elem != 0) || (line_after != 0))
 243           break;
 244       }
 245
 246       if (on_elem == 0)
 247       {
 248         if (line_after == 0)
 249           printf ("     ");
 250         else
 251           printf ("-----");
 252       }
 253       else if (on_elem == -1)
 254       {
 255         if (line_after == 0)
 256           printf ("-!   ");
 257         else
 258           printf (" !---");
 259       }
 260       else
 261       {
 262         if (line_after == 0)
 263           printf ("->   ");
 264         else
 265           printf (" <---");
 266       }
 267     } /* for (columns) */
 268
 269     printf ("\n");
 270   } /* for (lines) */
 271
 272   return (0);
 273 } /* int sn_stage_show */
 274
 275 int sn_stage_invert (sn_stage_t *s)
 276 {
 277   int i;
 278
 279   for (i = 0; i < s->comparators_num; i++)
 280     sn_comparator_invert (s->comparators + i);
 281
 282   return (0);
 283 } /* int sn_stage_invert */
 284
 285 int sn_stage_shift (sn_stage_t *s, int sw, int inputs_num)
 286 {
 287   int i;
 288
 289   for (i = 0; i < s->comparators_num; i++)
 290     sn_comparator_shift (s->comparators + i, sw, inputs_num);
 291
 292   return (0);
 293 } /* int sn_stage_shift */
 294
 295 int sn_stage_swap (sn_stage_t *s, int con0, int con1)
 296 {
 297   int i;
 298
 299   for (i = 0; i < s->comparators_num; i++)
 300     sn_comparator_swap (s->comparators + i, con0, con1);
 301
 302   return (0);
 303 } /* int sn_stage_swap */
 304
 305 int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir)
 306 {
 307   int new_position = input;
 308   int i;
 309
 310   for (i = 0; i < s->comparators_num; i++)
 311   {
 312     sn_comparator_t *c = s->comparators + i;
 313
 314     if ((SN_COMP_MIN (c) != input) && (SN_COMP_MAX (c) != input))
 315       continue;
 316
 317     if ((dir == DIR_MIN) && (SN_COMP_MAX (c) == input))
 318     {
 319       new_position = SN_COMP_MIN (c);
 320     }
 321     else if ((dir == DIR_MAX) && (SN_COMP_MIN (c) == input))
 322     {
 323       new_position = SN_COMP_MAX (c);
 324     }
 325     break;
 326   }
 327
 328   /*
 329   if (i < s->comparators_num)
 330     sn_stage_comparator_remove (s, i);
 331     */
 332
 333   return (new_position);
 334 } /* int sn_stage_cut_at */
 335
 336 int sn_stage_remove_input (sn_stage_t *s, int input)
 337 {
 338   int i;
 339
 340   for (i = 0; i < s->comparators_num; i++)
 341   {
 342     sn_comparator_t *c = s->comparators + i;
 343
 344     if ((SN_COMP_MIN (c) == input) || (SN_COMP_MAX (c) == input))
 345     {
 346       sn_stage_comparator_remove (s, i);
 347       i--;
 348       continue;
 349     }
 350
 351     if (SN_COMP_MIN (c) > input)
 352       SN_COMP_MIN (c) = SN_COMP_MIN (c) - 1;
 353     if (SN_COMP_MAX (c) > input)
 354       SN_COMP_MAX (c) = SN_COMP_MAX (c) - 1;
 355   }
 356
 357   return (0);
 358 }
 359
 360 sn_stage_t *sn_stage_read (FILE *fh)
 361 {
 362   sn_stage_t *s;
 363   char buffer[64];
 364   char *buffer_ptr;
 365
 366   s = sn_stage_create (0);
 367   if (s == NULL)
 368     return (NULL);
 369
 370   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 371   {
 372     char *endptr;
 373     sn_comparator_t c;
 374
 375     if ((buffer[0] == '\0') || (buffer[0] == '\n') || (buffer[0] == '\r'))
 376       break;
 377
 378     buffer_ptr = buffer;
 379     endptr = NULL;
 380     c.min = (int) strtol (buffer_ptr, &endptr, 0);
 381     if (buffer_ptr == endptr)
 382       continue;
 383
 384     buffer_ptr = endptr;
 385     endptr = NULL;
 386     c.max = (int) strtol (buffer_ptr, &endptr, 0);
 387     if (buffer_ptr == endptr)
 388       continue;
 389
 390     sn_stage_comparator_add (s, &c);
 391   }
 392
 393   if (s->comparators_num == 0)
 394   {
 395     sn_stage_destroy (s);
 396     return (NULL);
 397   }
 398
 399   return (s);
 400 } /* sn_stage_t *sn_stage_read */
 401
 402 int sn_stage_write (sn_stage_t *s, FILE *fh)
 403 {
 404   int i;
 405
 406   if (s->comparators_num <= 0)
 407     return (0);
 408
 409   for (i = 0; i < s->comparators_num; i++)
 410     fprintf (fh, "%i %i\n",
 411         SN_COMP_MIN (s->comparators + i),
 412         SN_COMP_MAX (s->comparators + i));
 413   fprintf (fh, "\n");
 414
 415   return (0);
 416 } /* int sn_stage_write */
 417
 418 int sn_stage_serialize (sn_stage_t *s,
 419     char **ret_buffer, size_t *ret_buffer_size)
 420 {
 421   char *buffer;
 422   size_t buffer_size;
 423   int status;
 424   int i;
 425
 426   if (s->comparators_num <= 0)
 427     return (0);
 428
 429   buffer = *ret_buffer;
 430   buffer_size = *ret_buffer_size;
 431
 432 #define SNPRINTF_OR_FAIL(...) \
 433   status = snprintf (buffer, buffer_size, __VA_ARGS__); \
 434   if ((status < 1) || (status >= buffer_size)) \
 435     return (-1); \
 436   buffer += status; \
 437   buffer_size -= status;
 438
 439   for (i = 0; i < s->comparators_num; i++)
 440   {
 441     SNPRINTF_OR_FAIL ("%i %i\r\n",
 442         SN_COMP_MIN (s->comparators + i),
 443         SN_COMP_MAX (s->comparators + i));
 444   }
 445
 446   SNPRINTF_OR_FAIL ("\r\n");
 447
 448   *ret_buffer = buffer;
 449   *ret_buffer_size = buffer_size;
 450   return (0);
 451 } /* int sn_stage_serialize */
 452
 453 sn_stage_t *sn_stage_unserialize (char **ret_buffer, size_t *ret_buffer_size)
 454 {
 455   sn_stage_t *s;
 456   char *buffer;
 457   size_t buffer_size;
 458   int status;
 459
 460   buffer = *ret_buffer;
 461   buffer_size = *ret_buffer_size;
 462
 463   if (buffer_size == 0)
 464     return (NULL);
 465
 466   s = sn_stage_create (0);
 467   if (s == NULL)
 468     return (NULL);
 469
 470   status = 0;
 471   while (buffer_size > 0)
 472   {
 473     sn_comparator_t c;
 474     char *endptr;
 475     char *substr;
 476     size_t substr_length;
 477
 478     endptr = strchr (buffer, '\n');
 479     if (endptr == NULL)
 480     {
 481       status = -1;
 482       break;
 483     }
 484
 485     *endptr = 0;
 486     endptr++;
 487
 488     substr = buffer;
 489     substr_length = strlen (buffer);
 490     buffer = endptr;
 491     buffer_size -= (substr_length + 1);
 492
 493     if ((substr_length > 0) && (substr[substr_length - 1] == '\r'))
 494     {
 495       substr[substr_length - 1] = 0;
 496       substr_length--;
 497     }
 498
 499     if (substr_length == 0)
 500     {
 501       status = 0;
 502       break;
 503     }
 504
 505     endptr = NULL;
 506     c.min = (int) strtol (substr, &endptr, 0);
 507     if (substr == endptr)
 508     {
 509       status = -1;
 510       break;
 511     }
 512
 513     substr = endptr;
 514     endptr = NULL;
 515     c.max = (int) strtol (substr, &endptr, 0);
 516     if (substr == endptr)
 517     {
 518       status = -1;
 519       break;
 520     }
 521
 522     sn_stage_comparator_add (s, &c);
 523   } /* while (buffer_size > 0) */
 524
 525   if ((status != 0) || (s->comparators_num == 0))
 526   {
 527     sn_stage_destroy (s);
 528     return (NULL);
 529   }
 530
 531   *ret_buffer = buffer;
 532   *ret_buffer_size = buffer_size;
 533   return (s);
 534 } /* sn_stage_t *sn_stage_unserialize */
 535
 536 /* vim: set shiftwidth=2 softtabstop=2 expandtab : */