src/sn_stage.c

   1 /**
   2  * libsortnetwork - src/sn_stage.c
   3  * Copyright (C) 2008-2010  Florian octo Forster
   4  *
   5  * This library is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU Lesser General Public License as published by
   7  * the Free Software Foundation; either version 2.1 of the License, or (at
   8  * your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
  13  * for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public License
  16  * along with this library; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  18  *
  19  * Authors:
  20  *   Florian octo Forster <ff at octo.it>
  21  **/
  22
  23 #ifndef _ISOC99_SOURCE
  24 # define _ISOC99_SOURCE
  25 #endif
  26 #ifndef _POSIX_C_SOURCE
  27 # define _POSIX_C_SOURCE 200112L
  28 #endif
  29
  30 #include <stdlib.h>
  31 #include <string.h>
  32 #include <assert.h>
  33 #include <errno.h>
  34
  35 #include "sn_comparator.h"
  36 #include "sn_stage.h"
  37
  38 sn_stage_t *sn_stage_create (int depth)
  39 {
  40   sn_stage_t *s;
  41
  42   s = (sn_stage_t *) malloc (sizeof (sn_stage_t));
  43   if (s == NULL)
  44     return (NULL);
  45   memset (s, '\0', sizeof (sn_stage_t));
  46
  47   s->depth = depth;
  48
  49   return (s);
  50 } /* sn_stage_t *sn_stage_create */
  51
  52 void sn_stage_destroy (sn_stage_t *s)
  53 {
  54   if (s == NULL)
  55     return;
  56   if (s->comparators != NULL)
  57     free (s->comparators);
  58   free (s);
  59 } /* void sn_stage_destroy */
  60
  61 int sn_stage_sort (sn_stage_t *s, int *values)
  62 {
  63   sn_comparator_t *c;
  64   int i;
  65
  66   for (i = 0; i < s->comparators_num; i++)
  67   {
  68     c = s->comparators + i;
  69     if (values[c->min] > values[c->max])
  70     {
  71       int temp;
  72
  73       temp = values[c->min];
  74       values[c->min] = values[c->max];
  75       values[c->max] = temp;
  76     }
  77   }
  78
  79   return (0);
  80 } /* int sn_stage_sort */
  81
  82 int sn_stage_comparator_add (sn_stage_t *s, const sn_comparator_t *c)
  83 {
  84   sn_comparator_t *temp;
  85   int i;
  86
  87   if ((s == NULL) || (c == NULL))
  88     return (EINVAL);
  89
  90   i = sn_stage_comparator_check_conflict (s, c);
  91   if (i != 0)
  92     return (i);
  93
  94   temp = (sn_comparator_t *) realloc (s->comparators,
  95       (s->comparators_num + 1) * sizeof (sn_comparator_t));
  96   if (temp == NULL)
  97     return (ENOMEM);
  98   s->comparators = temp;
  99   temp = NULL;
 100
 101   for (i = 0; i < s->comparators_num; i++)
 102     if (sn_comparator_compare (c, s->comparators + i) <= 0)
 103       break;
 104
 105   /* Insert the elements in ascending order */
 106   assert (i <= s->comparators_num);
 107   if (i < s->comparators_num)
 108   {
 109     int nmemb = s->comparators_num - i;
 110     memmove (s->comparators + (i + 1), s->comparators + i,
 111         nmemb * sizeof (sn_comparator_t));
 112   }
 113   memcpy (s->comparators + i, c, sizeof (sn_comparator_t));
 114   s->comparators_num++;
 115
 116   return (0);
 117 } /* int sn_stage_comparator_add */
 118
 119 int sn_stage_comparator_remove (sn_stage_t *s, int c_num)
 120 {
 121   int nmemb = s->comparators_num - (c_num + 1);
 122   sn_comparator_t *temp;
 123
 124   if ((s == NULL) || (s->comparators_num <= c_num))
 125     return (EINVAL);
 126
 127   assert (c_num < s->comparators_num);
 128   assert (c_num >= 0);
 129
 130   if (nmemb > 0)
 131     memmove (s->comparators + c_num, s->comparators + (c_num + 1),
 132         nmemb * sizeof (sn_comparator_t));
 133   s->comparators_num--;
 134
 135   /* Free the unused memory */
 136   if (s->comparators_num == 0)
 137   {
 138     free (s->comparators);
 139     s->comparators = NULL;
 140   }
 141   else
 142   {
 143     temp = (sn_comparator_t *) realloc (s->comparators,
 144         s->comparators_num * sizeof (sn_comparator_t));
 145     if (temp == NULL)
 146       return (-1);
 147     s->comparators = temp;
 148   }
 149
 150   return (0);
 151 } /* int sn_stage_comparator_remove */
 152
 153 sn_stage_t *sn_stage_clone (const sn_stage_t *s)
 154 {
 155   sn_stage_t *s_copy;
 156   int i;
 157
 158   s_copy = sn_stage_create (s->depth);
 159   if (s_copy == NULL)
 160     return (NULL);
 161
 162   s_copy->comparators = (sn_comparator_t *) malloc (s->comparators_num
 163       * sizeof (sn_comparator_t));
 164   if (s_copy->comparators == NULL)
 165   {
 166     free (s_copy);
 167     return (NULL);
 168   }
 169
 170   for (i = 0; i < s->comparators_num; i++)
 171   {
 172     SN_COMP_MIN (s_copy->comparators + i) = SN_COMP_MIN (s->comparators + i);
 173     SN_COMP_MAX (s_copy->comparators + i) = SN_COMP_MAX (s->comparators + i);
 174     SN_COMP_USER_DATA (s_copy->comparators + i) = NULL;
 175     SN_COMP_FREE_FUNC (s_copy->comparators + i) = NULL;
 176   }
 177   s_copy->comparators_num = s->comparators_num;
 178
 179   return (s_copy);
 180 } /* sn_stage_t *sn_stage_clone */
 181
 182 int sn_stage_comparator_check_conflict (sn_stage_t *s, const sn_comparator_t *c0)
 183 {
 184   int i;
 185
 186   for (i = 0; i < s->comparators_num; i++)
 187   {
 188     sn_comparator_t *c1 = s->comparators + i;
 189     if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
 190         || (SN_COMP_MIN(c0) == SN_COMP_MAX(c1))
 191         || (SN_COMP_MAX(c0) == SN_COMP_MIN(c1))
 192         || (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
 193     {
 194       if ((SN_COMP_MIN(c0) == SN_COMP_MIN(c1))
 195           && (SN_COMP_MAX(c0) == SN_COMP_MAX(c1)))
 196         return (2);
 197       else
 198         return (1);
 199     }
 200   }
 201
 202   return (0);
 203 } /* int sn_stage_comparator_check_conflict */
 204
 205 int sn_stage_show (sn_stage_t *s)
 206 {
 207   int lines[s->comparators_num];
 208   int right[s->comparators_num];
 209   int lines_used = 0;
 210   int i;
 211   int j;
 212   int k;
 213
 214   for (i = 0; i < s->comparators_num; i++)
 215   {
 216     lines[i] = -1;
 217     right[i] = -1;
 218   }
 219
 220   for (i = 0; i < s->comparators_num; i++)
 221   {
 222     int j;
 223     sn_comparator_t *c = s->comparators + i;
 224
 225     for (j = 0; j < lines_used; j++)
 226       if (SN_COMP_LEFT (c) > right[j])
 227         break;
 228
 229     lines[i] = j;
 230     right[j] = SN_COMP_RIGHT (c);
 231     if (j >= lines_used)
 232       lines_used = j + 1;
 233   }
 234
 235   for (i = 0; i < lines_used; i++)
 236   {
 237     printf ("%3i: ", s->depth);
 238
 239     for (j = 0; j <= right[i]; j++)
 240     {
 241       int on_elem = 0;
 242       int line_after = 0;
 243
 244       for (k = 0; k < s->comparators_num; k++)
 245       {
 246         sn_comparator_t *c = s->comparators + k;
 247
 248         /* Check if this comparator is displayed on another line */
 249         if (lines[k] != i)
 250           continue;
 251
 252         if (j == SN_COMP_MIN (c))
 253           on_elem = -1;
 254         else if (j == SN_COMP_MAX (c))
 255           on_elem = 1;
 256
 257         if ((j >= SN_COMP_LEFT (c)) && (j < SN_COMP_RIGHT (c)))
 258           line_after = 1;
 259
 260         if ((on_elem != 0) || (line_after != 0))
 261           break;
 262       }
 263
 264       if (on_elem == 0)
 265       {
 266         if (line_after == 0)
 267           printf ("     ");
 268         else
 269           printf ("-----");
 270       }
 271       else if (on_elem == -1)
 272       {
 273         if (line_after == 0)
 274           printf ("-!   ");
 275         else
 276           printf (" !---");
 277       }
 278       else
 279       {
 280         if (line_after == 0)
 281           printf ("->   ");
 282         else
 283           printf (" <---");
 284       }
 285     } /* for (columns) */
 286
 287     printf ("\n");
 288   } /* for (lines) */
 289
 290   return (0);
 291 } /* int sn_stage_show */
 292
 293 int sn_stage_invert (sn_stage_t *s)
 294 {
 295   int i;
 296
 297   if (s == NULL)
 298     return (EINVAL);
 299
 300   for (i = 0; i < s->comparators_num; i++)
 301     sn_comparator_invert (s->comparators + i);
 302
 303   return (0);
 304 } /* int sn_stage_invert */
 305
 306 int sn_stage_shift (sn_stage_t *s, int sw, int inputs_num)
 307 {
 308   int i;
 309
 310   if ((s == NULL) || (inputs_num < 2))
 311     return (EINVAL);
 312
 313   sw %= inputs_num;
 314   if (sw == 0)
 315     return (0);
 316
 317   for (i = 0; i < s->comparators_num; i++)
 318     sn_comparator_shift (s->comparators + i, sw, inputs_num);
 319
 320   return (0);
 321 } /* int sn_stage_shift */
 322
 323 int sn_stage_swap (sn_stage_t *s, int con0, int con1)
 324 {
 325   int i;
 326
 327   if (s == NULL)
 328     return (EINVAL);
 329
 330   for (i = 0; i < s->comparators_num; i++)
 331     sn_comparator_swap (s->comparators + i, con0, con1);
 332
 333   return (0);
 334 } /* int sn_stage_swap */
 335
 336 int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir)
 337 {
 338   int new_position = input;
 339   int i;
 340
 341   if ((s == NULL) || (input < 0))
 342     return (-EINVAL);
 343
 344   for (i = 0; i < s->comparators_num; i++)
 345   {
 346     sn_comparator_t *c = s->comparators + i;
 347
 348     if ((SN_COMP_MIN (c) != input) && (SN_COMP_MAX (c) != input))
 349       continue;
 350
 351     if ((dir == DIR_MIN) && (SN_COMP_MAX (c) == input))
 352     {
 353       new_position = SN_COMP_MIN (c);
 354     }
 355     else if ((dir == DIR_MAX) && (SN_COMP_MIN (c) == input))
 356     {
 357       new_position = SN_COMP_MAX (c);
 358     }
 359     break;
 360   }
 361
 362   /*
 363   if (i < s->comparators_num)
 364     sn_stage_comparator_remove (s, i);
 365     */
 366
 367   return (new_position);
 368 } /* int sn_stage_cut_at */
 369
 370 int sn_stage_cut (sn_stage_t *s, int *mask, /* {{{ */
 371     sn_stage_t **prev)
 372 {
 373   int i;
 374
 375   if ((s == NULL) || (mask == NULL) || (prev == NULL))
 376     return (EINVAL);
 377
 378   for (i = 0; i < s->comparators_num; i++)
 379   {
 380     sn_comparator_t *c = s->comparators + i;
 381     int left = SN_COMP_LEFT (c);
 382     int right = SN_COMP_RIGHT (c);
 383
 384     if ((mask[left] == 0)
 385         && (mask[right] == 0))
 386       continue;
 387
 388     /* Check if we need to update the cut position */
 389     if ((mask[left] != mask[right])
 390         && ((mask[left] > 0) || (mask[right] < 0)))
 391     {
 392       int tmp;
 393       int j;
 394
 395       tmp = mask[right];
 396       mask[right] = mask[left];
 397       mask[left] = tmp;
 398
 399       for (j = s->depth - 1; j >= 0; j--)
 400         sn_stage_swap (prev[j],
 401             left, right);
 402     }
 403
 404     sn_stage_comparator_remove (s, i);
 405     i--;
 406   } /* for (i = 0; i < s->comparators_num; i++) */
 407
 408   return (0);
 409 } /* }}} int sn_stage_cut */
 410
 411 int sn_stage_remove_input (sn_stage_t *s, int input)
 412 {
 413   int i;
 414
 415   for (i = 0; i < s->comparators_num; i++)
 416   {
 417     sn_comparator_t *c = s->comparators + i;
 418
 419     if ((SN_COMP_MIN (c) == input) || (SN_COMP_MAX (c) == input))
 420     {
 421       sn_stage_comparator_remove (s, i);
 422       i--;
 423       continue;
 424     }
 425
 426     if (SN_COMP_MIN (c) > input)
 427       SN_COMP_MIN (c) = SN_COMP_MIN (c) - 1;
 428     if (SN_COMP_MAX (c) > input)
 429       SN_COMP_MAX (c) = SN_COMP_MAX (c) - 1;
 430   }
 431
 432   return (0);
 433 }
 434
 435 sn_stage_t *sn_stage_read (FILE *fh)
 436 {
 437   sn_stage_t *s;
 438   char buffer[64];
 439   char *buffer_ptr;
 440
 441   s = sn_stage_create (0);
 442   if (s == NULL)
 443     return (NULL);
 444
 445   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 446   {
 447     char *endptr;
 448     sn_comparator_t c;
 449
 450     if ((buffer[0] == '\0') || (buffer[0] == '\n') || (buffer[0] == '\r'))
 451       break;
 452
 453     buffer_ptr = buffer;
 454     endptr = NULL;
 455     c.min = (int) strtol (buffer_ptr, &endptr, 0);
 456     if (buffer_ptr == endptr)
 457       continue;
 458
 459     buffer_ptr = endptr;
 460     endptr = NULL;
 461     c.max = (int) strtol (buffer_ptr, &endptr, 0);
 462     if (buffer_ptr == endptr)
 463       continue;
 464
 465     sn_stage_comparator_add (s, &c);
 466   }
 467
 468   if (s->comparators_num == 0)
 469   {
 470     sn_stage_destroy (s);
 471     return (NULL);
 472   }
 473
 474   return (s);
 475 } /* sn_stage_t *sn_stage_read */
 476
 477 int sn_stage_write (sn_stage_t *s, FILE *fh)
 478 {
 479   int i;
 480
 481   if (s->comparators_num <= 0)
 482     return (0);
 483
 484   for (i = 0; i < s->comparators_num; i++)
 485     fprintf (fh, "%i %i\n",
 486         SN_COMP_MIN (s->comparators + i),
 487         SN_COMP_MAX (s->comparators + i));
 488   fprintf (fh, "\n");
 489
 490   return (0);
 491 } /* int sn_stage_write */
 492
 493 int sn_stage_serialize (sn_stage_t *s,
 494     char **ret_buffer, size_t *ret_buffer_size)
 495 {
 496   char *buffer;
 497   size_t buffer_size;
 498   int status;
 499   int i;
 500
 501   if (s->comparators_num <= 0)
 502     return (0);
 503
 504   buffer = *ret_buffer;
 505   buffer_size = *ret_buffer_size;
 506
 507 #define SNPRINTF_OR_FAIL(...) \
 508   status = snprintf (buffer, buffer_size, __VA_ARGS__); \
 509   if ((status < 1) || (((size_t) status) >= buffer_size)) \
 510     return (-1); \
 511   buffer += status; \
 512   buffer_size -= status;
 513
 514   for (i = 0; i < s->comparators_num; i++)
 515   {
 516     SNPRINTF_OR_FAIL ("%i %i\r\n",
 517         SN_COMP_MIN (s->comparators + i),
 518         SN_COMP_MAX (s->comparators + i));
 519   }
 520
 521   SNPRINTF_OR_FAIL ("\r\n");
 522
 523   *ret_buffer = buffer;
 524   *ret_buffer_size = buffer_size;
 525   return (0);
 526 } /* int sn_stage_serialize */
 527
 528 sn_stage_t *sn_stage_unserialize (char **ret_buffer, size_t *ret_buffer_size)
 529 {
 530   sn_stage_t *s;
 531   char *buffer;
 532   size_t buffer_size;
 533   int status;
 534
 535   buffer = *ret_buffer;
 536   buffer_size = *ret_buffer_size;
 537
 538   if (buffer_size == 0)
 539     return (NULL);
 540
 541   s = sn_stage_create (0);
 542   if (s == NULL)
 543     return (NULL);
 544
 545   status = 0;
 546   while (buffer_size > 0)
 547   {
 548     sn_comparator_t c;
 549     char *endptr;
 550     char *substr;
 551     size_t substr_length;
 552
 553     endptr = strchr (buffer, '\n');
 554     if (endptr == NULL)
 555     {
 556       status = -1;
 557       break;
 558     }
 559
 560     *endptr = 0;
 561     endptr++;
 562
 563     substr = buffer;
 564     substr_length = strlen (buffer);
 565     buffer = endptr;
 566     buffer_size -= (substr_length + 1);
 567
 568     if ((substr_length > 0) && (substr[substr_length - 1] == '\r'))
 569     {
 570       substr[substr_length - 1] = 0;
 571       substr_length--;
 572     }
 573
 574     if (substr_length == 0)
 575     {
 576       status = 0;
 577       break;
 578     }
 579
 580     endptr = NULL;
 581     c.min = (int) strtol (substr, &endptr, 0);
 582     if (substr == endptr)
 583     {
 584       status = -1;
 585       break;
 586     }
 587
 588     substr = endptr;
 589     endptr = NULL;
 590     c.max = (int) strtol (substr, &endptr, 0);
 591     if (substr == endptr)
 592     {
 593       status = -1;
 594       break;
 595     }
 596
 597     sn_stage_comparator_add (s, &c);
 598   } /* while (buffer_size > 0) */
 599
 600   if ((status != 0) || (s->comparators_num == 0))
 601   {
 602     sn_stage_destroy (s);
 603     return (NULL);
 604   }
 605
 606   *ret_buffer = buffer;
 607   *ret_buffer_size = buffer_size;
 608   return (s);
 609 } /* sn_stage_t *sn_stage_unserialize */
 610
 611 uint32_t sn_stage_get_hashval (const sn_stage_t *s) /* {{{ */
 612 {
 613   uint32_t hash;
 614   int i;
 615
 616   if (s == NULL)
 617     return (0);
 618
 619   hash = (uint32_t) s->depth;
 620
 621   for (i = 0; i < s->comparators_num; i++)
 622     hash = (hash * 99991) + sn_comparator_get_hashval (s->comparators + i);
 623
 624   return (hash);
 625 } /* }}} uint32_t sn_stage_get_hashval */
 626
 627 /* vim: set shiftwidth=2 softtabstop=2 expandtab fdm=marker : */