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