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_remove_input (sn_stage_t *s, int input)
 365 {
 366   int i;
 367
 368   for (i = 0; i < s->comparators_num; i++)
 369   {
 370     sn_comparator_t *c = s->comparators + i;
 371
 372     if ((SN_COMP_MIN (c) == input) || (SN_COMP_MAX (c) == input))
 373     {
 374       sn_stage_comparator_remove (s, i);
 375       i--;
 376       continue;
 377     }
 378
 379     if (SN_COMP_MIN (c) > input)
 380       SN_COMP_MIN (c) = SN_COMP_MIN (c) - 1;
 381     if (SN_COMP_MAX (c) > input)
 382       SN_COMP_MAX (c) = SN_COMP_MAX (c) - 1;
 383   }
 384
 385   return (0);
 386 }
 387
 388 sn_stage_t *sn_stage_read (FILE *fh)
 389 {
 390   sn_stage_t *s;
 391   char buffer[64];
 392   char *buffer_ptr;
 393
 394   s = sn_stage_create (0);
 395   if (s == NULL)
 396     return (NULL);
 397
 398   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 399   {
 400     char *endptr;
 401     sn_comparator_t c;
 402
 403     if ((buffer[0] == '\0') || (buffer[0] == '\n') || (buffer[0] == '\r'))
 404       break;
 405
 406     buffer_ptr = buffer;
 407     endptr = NULL;
 408     c.min = (int) strtol (buffer_ptr, &endptr, 0);
 409     if (buffer_ptr == endptr)
 410       continue;
 411
 412     buffer_ptr = endptr;
 413     endptr = NULL;
 414     c.max = (int) strtol (buffer_ptr, &endptr, 0);
 415     if (buffer_ptr == endptr)
 416       continue;
 417
 418     sn_stage_comparator_add (s, &c);
 419   }
 420
 421   if (s->comparators_num == 0)
 422   {
 423     sn_stage_destroy (s);
 424     return (NULL);
 425   }
 426
 427   return (s);
 428 } /* sn_stage_t *sn_stage_read */
 429
 430 int sn_stage_write (sn_stage_t *s, FILE *fh)
 431 {
 432   int i;
 433
 434   if (s->comparators_num <= 0)
 435     return (0);
 436
 437   for (i = 0; i < s->comparators_num; i++)
 438     fprintf (fh, "%i %i\n",
 439         SN_COMP_MIN (s->comparators + i),
 440         SN_COMP_MAX (s->comparators + i));
 441   fprintf (fh, "\n");
 442
 443   return (0);
 444 } /* int sn_stage_write */
 445
 446 int sn_stage_serialize (sn_stage_t *s,
 447     char **ret_buffer, size_t *ret_buffer_size)
 448 {
 449   char *buffer;
 450   size_t buffer_size;
 451   int status;
 452   int i;
 453
 454   if (s->comparators_num <= 0)
 455     return (0);
 456
 457   buffer = *ret_buffer;
 458   buffer_size = *ret_buffer_size;
 459
 460 #define SNPRINTF_OR_FAIL(...) \
 461   status = snprintf (buffer, buffer_size, __VA_ARGS__); \
 462   if ((status < 1) || (((size_t) status) >= buffer_size)) \
 463     return (-1); \
 464   buffer += status; \
 465   buffer_size -= status;
 466
 467   for (i = 0; i < s->comparators_num; i++)
 468   {
 469     SNPRINTF_OR_FAIL ("%i %i\r\n",
 470         SN_COMP_MIN (s->comparators + i),
 471         SN_COMP_MAX (s->comparators + i));
 472   }
 473
 474   SNPRINTF_OR_FAIL ("\r\n");
 475
 476   *ret_buffer = buffer;
 477   *ret_buffer_size = buffer_size;
 478   return (0);
 479 } /* int sn_stage_serialize */
 480
 481 sn_stage_t *sn_stage_unserialize (char **ret_buffer, size_t *ret_buffer_size)
 482 {
 483   sn_stage_t *s;
 484   char *buffer;
 485   size_t buffer_size;
 486   int status;
 487
 488   buffer = *ret_buffer;
 489   buffer_size = *ret_buffer_size;
 490
 491   if (buffer_size == 0)
 492     return (NULL);
 493
 494   s = sn_stage_create (0);
 495   if (s == NULL)
 496     return (NULL);
 497
 498   status = 0;
 499   while (buffer_size > 0)
 500   {
 501     sn_comparator_t c;
 502     char *endptr;
 503     char *substr;
 504     size_t substr_length;
 505
 506     endptr = strchr (buffer, '\n');
 507     if (endptr == NULL)
 508     {
 509       status = -1;
 510       break;
 511     }
 512
 513     *endptr = 0;
 514     endptr++;
 515
 516     substr = buffer;
 517     substr_length = strlen (buffer);
 518     buffer = endptr;
 519     buffer_size -= (substr_length + 1);
 520
 521     if ((substr_length > 0) && (substr[substr_length - 1] == '\r'))
 522     {
 523       substr[substr_length - 1] = 0;
 524       substr_length--;
 525     }
 526
 527     if (substr_length == 0)
 528     {
 529       status = 0;
 530       break;
 531     }
 532
 533     endptr = NULL;
 534     c.min = (int) strtol (substr, &endptr, 0);
 535     if (substr == endptr)
 536     {
 537       status = -1;
 538       break;
 539     }
 540
 541     substr = endptr;
 542     endptr = NULL;
 543     c.max = (int) strtol (substr, &endptr, 0);
 544     if (substr == endptr)
 545     {
 546       status = -1;
 547       break;
 548     }
 549
 550     sn_stage_comparator_add (s, &c);
 551   } /* while (buffer_size > 0) */
 552
 553   if ((status != 0) || (s->comparators_num == 0))
 554   {
 555     sn_stage_destroy (s);
 556     return (NULL);
 557   }
 558
 559   *ret_buffer = buffer;
 560   *ret_buffer_size = buffer_size;
 561   return (s);
 562 } /* sn_stage_t *sn_stage_unserialize */
 563
 564 /* vim: set shiftwidth=2 softtabstop=2 expandtab : */