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   int i;
 156
 157   s_copy = sn_stage_create (s->depth);
 158   if (s_copy == NULL)
 159     return (NULL);
 160
 161   s_copy->comparators = (sn_comparator_t *) malloc (s->comparators_num
 162       * sizeof (sn_comparator_t));
 163   if (s_copy->comparators == NULL)
 164   {
 165     free (s_copy);
 166     return (NULL);
 167   }
 168
 169   memcpy (s_copy->comparators, s->comparators,
 170       s->comparators_num * sizeof (sn_comparator_t));
 171   s_copy->comparators_num = s->comparators_num;
 172
 173   return (s_copy);
 174 } /* sn_stage_t *sn_stage_clone */
 175
 176 int sn_stage_comparator_check_conflict (sn_stage_t *s, const sn_comparator_t *c0)
 177 {
 178   int i;
 179
 180   for (i = 0; i < s->comparators_num; i++)
 181   {
 182     sn_comparator_t *c1 = s->comparators + i;
 183     if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
 184         || (SN_COMP_MIN(c0) == SN_COMP_MAX(c1))
 185         || (SN_COMP_MAX(c0) == SN_COMP_MIN(c1))
 186         || (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
 187     {
 188       if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
 189           && (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
 190         return (2);
 191       else
 192         return (1);
 193     }
 194   }
 195
 196   return (0);
 197 } /* int sn_stage_comparator_check_conflict */
 198
 199 int sn_stage_show (sn_stage_t *s)
 200 {
 201   int lines[s->comparators_num];
 202   int right[s->comparators_num];
 203   int lines_used = 0;
 204   int i;
 205   int j;
 206   int k;
 207
 208   for (i = 0; i < s->comparators_num; i++)
 209   {
 210     lines[i] = -1;
 211     right[i] = -1;
 212   }
 213
 214   for (i = 0; i < s->comparators_num; i++)
 215   {
 216     int j;
 217     sn_comparator_t *c = s->comparators + i;
 218
 219     for (j = 0; j < lines_used; j++)
 220       if (SN_COMP_LEFT (c) > right[j])
 221         break;
 222
 223     lines[i] = j;
 224     right[j] = SN_COMP_RIGHT (c);
 225     if (j >= lines_used)
 226       lines_used = j + 1;
 227   }
 228
 229   for (i = 0; i < lines_used; i++)
 230   {
 231     printf ("%3i: ", s->depth);
 232
 233     for (j = 0; j <= right[i]; j++)
 234     {
 235       int on_elem = 0;
 236       int line_after = 0;
 237
 238       for (k = 0; k < s->comparators_num; k++)
 239       {
 240         sn_comparator_t *c = s->comparators + k;
 241
 242         /* Check if this comparator is displayed on another line */
 243         if (lines[k] != i)
 244           continue;
 245
 246         if (j == SN_COMP_MIN (c))
 247           on_elem = -1;
 248         else if (j == SN_COMP_MAX (c))
 249           on_elem = 1;
 250
 251         if ((j >= SN_COMP_LEFT (c)) && (j < SN_COMP_RIGHT (c)))
 252           line_after = 1;
 253
 254         if ((on_elem != 0) || (line_after != 0))
 255           break;
 256       }
 257
 258       if (on_elem == 0)
 259       {
 260         if (line_after == 0)
 261           printf ("     ");
 262         else
 263           printf ("-----");
 264       }
 265       else if (on_elem == -1)
 266       {
 267         if (line_after == 0)
 268           printf ("-!   ");
 269         else
 270           printf (" !---");
 271       }
 272       else
 273       {
 274         if (line_after == 0)
 275           printf ("->   ");
 276         else
 277           printf (" <---");
 278       }
 279     } /* for (columns) */
 280
 281     printf ("\n");
 282   } /* for (lines) */
 283
 284   return (0);
 285 } /* int sn_stage_show */
 286
 287 int sn_stage_invert (sn_stage_t *s)
 288 {
 289   int i;
 290
 291   if (s == NULL)
 292     return (EINVAL);
 293
 294   for (i = 0; i < s->comparators_num; i++)
 295     sn_comparator_invert (s->comparators + i);
 296
 297   return (0);
 298 } /* int sn_stage_invert */
 299
 300 int sn_stage_shift (sn_stage_t *s, int sw, int inputs_num)
 301 {
 302   int i;
 303
 304   if ((s == NULL) || (inputs_num < 2))
 305     return (EINVAL);
 306
 307   sw %= inputs_num;
 308   if (sw == 0)
 309     return (0);
 310
 311   for (i = 0; i < s->comparators_num; i++)
 312     sn_comparator_shift (s->comparators + i, sw, inputs_num);
 313
 314   return (0);
 315 } /* int sn_stage_shift */
 316
 317 int sn_stage_swap (sn_stage_t *s, int con0, int con1)
 318 {
 319   int i;
 320
 321   if (s == NULL)
 322     return (EINVAL);
 323
 324   for (i = 0; i < s->comparators_num; i++)
 325     sn_comparator_swap (s->comparators + i, con0, con1);
 326
 327   return (0);
 328 } /* int sn_stage_swap */
 329
 330 int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir)
 331 {
 332   int new_position = input;
 333   int i;
 334
 335   if ((s == NULL) || (input < 0))
 336     return (-EINVAL);
 337
 338   for (i = 0; i < s->comparators_num; i++)
 339   {
 340     sn_comparator_t *c = s->comparators + i;
 341
 342     if ((SN_COMP_MIN (c) != input) && (SN_COMP_MAX (c) != input))
 343       continue;
 344
 345     if ((dir == DIR_MIN) && (SN_COMP_MAX (c) == input))
 346     {
 347       new_position = SN_COMP_MIN (c);
 348     }
 349     else if ((dir == DIR_MAX) && (SN_COMP_MIN (c) == input))
 350     {
 351       new_position = SN_COMP_MAX (c);
 352     }
 353     break;
 354   }
 355
 356   /*
 357   if (i < s->comparators_num)
 358     sn_stage_comparator_remove (s, i);
 359     */
 360
 361   return (new_position);
 362 } /* int sn_stage_cut_at */
 363
 364 int sn_stage_cut (sn_stage_t *s, int *mask, /* {{{ */
 365     sn_stage_t **prev)
 366 {
 367   int i;
 368
 369   if ((s == NULL) || (mask == NULL) || (prev == NULL))
 370     return (EINVAL);
 371
 372   for (i = 0; i < s->comparators_num; i++)
 373   {
 374     sn_comparator_t *c = s->comparators + i;
 375     int left = SN_COMP_LEFT (c);
 376     int right = SN_COMP_RIGHT (c);
 377
 378     if ((mask[left] == 0)
 379         && (mask[right] == 0))
 380       continue;
 381
 382     /* Check if we need to update the cut position */
 383     if ((mask[left] != mask[right])
 384         && ((mask[left] > 0) || (mask[right] < 0)))
 385     {
 386       int tmp;
 387       int j;
 388
 389       tmp = mask[right];
 390       mask[right] = mask[left];
 391       mask[left] = tmp;
 392
 393       for (j = s->depth - 1; j >= 0; j--)
 394         sn_stage_swap (prev[j],
 395             left, right);
 396     }
 397
 398     sn_stage_comparator_remove (s, i);
 399     i--;
 400   } /* for (i = 0; i < s->comparators_num; i++) */
 401
 402   return (0);
 403 } /* }}} int sn_stage_cut */
 404
 405 int sn_stage_remove_input (sn_stage_t *s, int input)
 406 {
 407   int i;
 408
 409   for (i = 0; i < s->comparators_num; i++)
 410   {
 411     sn_comparator_t *c = s->comparators + i;
 412
 413     if ((SN_COMP_MIN (c) == input) || (SN_COMP_MAX (c) == input))
 414     {
 415       sn_stage_comparator_remove (s, i);
 416       i--;
 417       continue;
 418     }
 419
 420     if (SN_COMP_MIN (c) > input)
 421       SN_COMP_MIN (c) = SN_COMP_MIN (c) - 1;
 422     if (SN_COMP_MAX (c) > input)
 423       SN_COMP_MAX (c) = SN_COMP_MAX (c) - 1;
 424   }
 425
 426   return (0);
 427 }
 428
 429 sn_stage_t *sn_stage_read (FILE *fh)
 430 {
 431   sn_stage_t *s;
 432   char buffer[64];
 433   char *buffer_ptr;
 434
 435   s = sn_stage_create (0);
 436   if (s == NULL)
 437     return (NULL);
 438
 439   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 440   {
 441     char *endptr;
 442     sn_comparator_t c;
 443
 444     if ((buffer[0] == '\0') || (buffer[0] == '\n') || (buffer[0] == '\r'))
 445       break;
 446
 447     buffer_ptr = buffer;
 448     endptr = NULL;
 449     c.min = (int) strtol (buffer_ptr, &endptr, 0);
 450     if (buffer_ptr == endptr)
 451       continue;
 452
 453     buffer_ptr = endptr;
 454     endptr = NULL;
 455     c.max = (int) strtol (buffer_ptr, &endptr, 0);
 456     if (buffer_ptr == endptr)
 457       continue;
 458
 459     sn_stage_comparator_add (s, &c);
 460   }
 461
 462   if (s->comparators_num == 0)
 463   {
 464     sn_stage_destroy (s);
 465     return (NULL);
 466   }
 467
 468   return (s);
 469 } /* sn_stage_t *sn_stage_read */
 470
 471 int sn_stage_write (sn_stage_t *s, FILE *fh)
 472 {
 473   int i;
 474
 475   if (s->comparators_num <= 0)
 476     return (0);
 477
 478   for (i = 0; i < s->comparators_num; i++)
 479     fprintf (fh, "%i %i\n",
 480         SN_COMP_MIN (s->comparators + i),
 481         SN_COMP_MAX (s->comparators + i));
 482   fprintf (fh, "\n");
 483
 484   return (0);
 485 } /* int sn_stage_write */
 486
 487 int sn_stage_serialize (sn_stage_t *s,
 488     char **ret_buffer, size_t *ret_buffer_size)
 489 {
 490   char *buffer;
 491   size_t buffer_size;
 492   int status;
 493   int i;
 494
 495   if (s->comparators_num <= 0)
 496     return (0);
 497
 498   buffer = *ret_buffer;
 499   buffer_size = *ret_buffer_size;
 500
 501 #define SNPRINTF_OR_FAIL(...) \
 502   status = snprintf (buffer, buffer_size, __VA_ARGS__); \
 503   if ((status < 1) || (((size_t) status) >= buffer_size)) \
 504     return (-1); \
 505   buffer += status; \
 506   buffer_size -= status;
 507
 508   for (i = 0; i < s->comparators_num; i++)
 509   {
 510     SNPRINTF_OR_FAIL ("%i %i\r\n",
 511         SN_COMP_MIN (s->comparators + i),
 512         SN_COMP_MAX (s->comparators + i));
 513   }
 514
 515   SNPRINTF_OR_FAIL ("\r\n");
 516
 517   *ret_buffer = buffer;
 518   *ret_buffer_size = buffer_size;
 519   return (0);
 520 } /* int sn_stage_serialize */
 521
 522 sn_stage_t *sn_stage_unserialize (char **ret_buffer, size_t *ret_buffer_size)
 523 {
 524   sn_stage_t *s;
 525   char *buffer;
 526   size_t buffer_size;
 527   int status;
 528
 529   buffer = *ret_buffer;
 530   buffer_size = *ret_buffer_size;
 531
 532   if (buffer_size == 0)
 533     return (NULL);
 534
 535   s = sn_stage_create (0);
 536   if (s == NULL)
 537     return (NULL);
 538
 539   status = 0;
 540   while (buffer_size > 0)
 541   {
 542     sn_comparator_t c;
 543     char *endptr;
 544     char *substr;
 545     size_t substr_length;
 546
 547     endptr = strchr (buffer, '\n');
 548     if (endptr == NULL)
 549     {
 550       status = -1;
 551       break;
 552     }
 553
 554     *endptr = 0;
 555     endptr++;
 556
 557     substr = buffer;
 558     substr_length = strlen (buffer);
 559     buffer = endptr;
 560     buffer_size -= (substr_length + 1);
 561
 562     if ((substr_length > 0) && (substr[substr_length - 1] == '\r'))
 563     {
 564       substr[substr_length - 1] = 0;
 565       substr_length--;
 566     }
 567
 568     if (substr_length == 0)
 569     {
 570       status = 0;
 571       break;
 572     }
 573
 574     endptr = NULL;
 575     c.min = (int) strtol (substr, &endptr, 0);
 576     if (substr == endptr)
 577     {
 578       status = -1;
 579       break;
 580     }
 581
 582     substr = endptr;
 583     endptr = NULL;
 584     c.max = (int) strtol (substr, &endptr, 0);
 585     if (substr == endptr)
 586     {
 587       status = -1;
 588       break;
 589     }
 590
 591     sn_stage_comparator_add (s, &c);
 592   } /* while (buffer_size > 0) */
 593
 594   if ((status != 0) || (s->comparators_num == 0))
 595   {
 596     sn_stage_destroy (s);
 597     return (NULL);
 598   }
 599
 600   *ret_buffer = buffer;
 601   *ret_buffer_size = buffer_size;
 602   return (s);
 603 } /* sn_stage_t *sn_stage_unserialize */
 604
 605 /* vim: set shiftwidth=2 softtabstop=2 expandtab : */