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