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_fh (sn_stage_t *s, FILE *fh) /* {{{ */
 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     fprintf (fh, "%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           fprintf (fh, "     ");
 268         else
 269           fprintf (fh, "-----");
 270       }
 271       else if (on_elem == -1)
 272       {
 273         if (line_after == 0)
 274           fprintf (fh, "-!   ");
 275         else
 276           fprintf (fh, " !---");
 277       }
 278       else
 279       {
 280         if (line_after == 0)
 281           fprintf (fh, "->   ");
 282         else
 283           fprintf (fh, " <---");
 284       }
 285     } /* for (columns) */
 286
 287     fprintf (fh, "\n");
 288   } /* for (lines) */
 289
 290   return (0);
 291 } /* }}} int sn_stage_show_fh */
 292
 293 int sn_stage_show (sn_stage_t *s) /* {{{ */
 294 {
 295   return (sn_stage_show_fh (s, stdout));
 296 } /* }}} int sn_stage_show */
 297
 298 int sn_stage_invert (sn_stage_t *s)
 299 {
 300   int i;
 301
 302   if (s == NULL)
 303     return (EINVAL);
 304
 305   for (i = 0; i < s->comparators_num; i++)
 306     sn_comparator_invert (s->comparators + i);
 307
 308   return (0);
 309 } /* int sn_stage_invert */
 310
 311 int sn_stage_shift (sn_stage_t *s, int sw, int inputs_num)
 312 {
 313   int i;
 314
 315   if ((s == NULL) || (inputs_num < 2))
 316     return (EINVAL);
 317
 318   sw %= inputs_num;
 319   if (sw == 0)
 320     return (0);
 321
 322   for (i = 0; i < s->comparators_num; i++)
 323     sn_comparator_shift (s->comparators + i, sw, inputs_num);
 324
 325   return (0);
 326 } /* int sn_stage_shift */
 327
 328 static int sn_stage_unify__qsort_callback (const void *p0, const void *p1) /* {{{ */
 329 {
 330   return (sn_comparator_compare (p0, p1));
 331 } /* }}} int sn_stage_unify__qsort_callback */
 332
 333 int sn_stage_unify (sn_stage_t *s) /* {{{ */
 334 {
 335   if (s == NULL)
 336     return (EINVAL);
 337
 338   qsort (s->comparators,
 339       (size_t) s->comparators_num,
 340       sizeof (*s->comparators),
 341       sn_stage_unify__qsort_callback);
 342
 343   return (0);
 344 } /* }}} int sn_stage_unify */
 345
 346 int sn_stage_swap (sn_stage_t *s, int con0, int con1)
 347 {
 348   int i;
 349
 350   if (s == NULL)
 351     return (EINVAL);
 352
 353   for (i = 0; i < s->comparators_num; i++)
 354     sn_comparator_swap (s->comparators + i, con0, con1);
 355
 356   return (0);
 357 } /* int sn_stage_swap */
 358
 359 int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir)
 360 {
 361   int new_position = input;
 362   int i;
 363
 364   if ((s == NULL) || (input < 0))
 365     return (-EINVAL);
 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       continue;
 373
 374     if ((dir == DIR_MIN) && (SN_COMP_MAX (c) == input))
 375     {
 376       new_position = SN_COMP_MIN (c);
 377     }
 378     else if ((dir == DIR_MAX) && (SN_COMP_MIN (c) == input))
 379     {
 380       new_position = SN_COMP_MAX (c);
 381     }
 382     break;
 383   }
 384
 385   /*
 386   if (i < s->comparators_num)
 387     sn_stage_comparator_remove (s, i);
 388     */
 389
 390   return (new_position);
 391 } /* int sn_stage_cut_at */
 392
 393 int sn_stage_cut (sn_stage_t *s, int *mask, /* {{{ */
 394     sn_stage_t **prev)
 395 {
 396   int i;
 397
 398   if ((s == NULL) || (mask == NULL) || (prev == NULL))
 399     return (EINVAL);
 400
 401   for (i = 0; i < s->comparators_num; i++)
 402   {
 403     sn_comparator_t *c = s->comparators + i;
 404     int left = SN_COMP_LEFT (c);
 405     int right = SN_COMP_RIGHT (c);
 406
 407     if ((mask[left] == 0)
 408         && (mask[right] == 0))
 409       continue;
 410
 411     /* Check if we need to update the cut position */
 412     if ((mask[left] != mask[right])
 413         && ((mask[left] > 0) || (mask[right] < 0)))
 414     {
 415       int tmp;
 416       int j;
 417
 418       tmp = mask[right];
 419       mask[right] = mask[left];
 420       mask[left] = tmp;
 421
 422       for (j = s->depth - 1; j >= 0; j--)
 423         sn_stage_swap (prev[j],
 424             left, right);
 425     }
 426
 427     sn_stage_comparator_remove (s, i);
 428     i--;
 429   } /* for (i = 0; i < s->comparators_num; i++) */
 430
 431   return (0);
 432 } /* }}} int sn_stage_cut */
 433
 434 int sn_stage_remove_input (sn_stage_t *s, int input)
 435 {
 436   int i;
 437
 438   for (i = 0; i < s->comparators_num; i++)
 439   {
 440     sn_comparator_t *c = s->comparators + i;
 441
 442     if ((SN_COMP_MIN (c) == input) || (SN_COMP_MAX (c) == input))
 443     {
 444       sn_stage_comparator_remove (s, i);
 445       i--;
 446       continue;
 447     }
 448
 449     if (SN_COMP_MIN (c) > input)
 450       SN_COMP_MIN (c) = SN_COMP_MIN (c) - 1;
 451     if (SN_COMP_MAX (c) > input)
 452       SN_COMP_MAX (c) = SN_COMP_MAX (c) - 1;
 453   }
 454
 455   return (0);
 456 }
 457
 458 sn_stage_t *sn_stage_read (FILE *fh)
 459 {
 460   sn_stage_t *s;
 461   char buffer[64];
 462   char *buffer_ptr;
 463
 464   s = sn_stage_create (0);
 465   if (s == NULL)
 466     return (NULL);
 467
 468   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 469   {
 470     char *endptr;
 471     sn_comparator_t c;
 472
 473     if ((buffer[0] == '\0') || (buffer[0] == '\n') || (buffer[0] == '\r'))
 474       break;
 475
 476     buffer_ptr = buffer;
 477     endptr = NULL;
 478     c.min = (int) strtol (buffer_ptr, &endptr, 0);
 479     if (buffer_ptr == endptr)
 480       continue;
 481
 482     buffer_ptr = endptr;
 483     endptr = NULL;
 484     c.max = (int) strtol (buffer_ptr, &endptr, 0);
 485     if (buffer_ptr == endptr)
 486       continue;
 487
 488     sn_stage_comparator_add (s, &c);
 489   }
 490
 491   if (s->comparators_num == 0)
 492   {
 493     sn_stage_destroy (s);
 494     return (NULL);
 495   }
 496
 497   return (s);
 498 } /* sn_stage_t *sn_stage_read */
 499
 500 int sn_stage_write (sn_stage_t *s, FILE *fh)
 501 {
 502   int i;
 503
 504   if (s->comparators_num <= 0)
 505     return (0);
 506
 507   for (i = 0; i < s->comparators_num; i++)
 508     fprintf (fh, "%i %i\n",
 509         SN_COMP_MIN (s->comparators + i),
 510         SN_COMP_MAX (s->comparators + i));
 511   fprintf (fh, "\n");
 512
 513   return (0);
 514 } /* int sn_stage_write */
 515
 516 int sn_stage_serialize (sn_stage_t *s,
 517     char **ret_buffer, size_t *ret_buffer_size)
 518 {
 519   char *buffer;
 520   size_t buffer_size;
 521   int status;
 522   int i;
 523
 524   if (s->comparators_num <= 0)
 525     return (0);
 526
 527   buffer = *ret_buffer;
 528   buffer_size = *ret_buffer_size;
 529
 530 #define SNPRINTF_OR_FAIL(...) \
 531   status = snprintf (buffer, buffer_size, __VA_ARGS__); \
 532   if ((status < 1) || (((size_t) status) >= buffer_size)) \
 533     return (-1); \
 534   buffer += status; \
 535   buffer_size -= status;
 536
 537   for (i = 0; i < s->comparators_num; i++)
 538   {
 539     SNPRINTF_OR_FAIL ("%i %i\r\n",
 540         SN_COMP_MIN (s->comparators + i),
 541         SN_COMP_MAX (s->comparators + i));
 542   }
 543
 544   SNPRINTF_OR_FAIL ("\r\n");
 545
 546   *ret_buffer = buffer;
 547   *ret_buffer_size = buffer_size;
 548   return (0);
 549 } /* int sn_stage_serialize */
 550
 551 sn_stage_t *sn_stage_unserialize (char **ret_buffer, size_t *ret_buffer_size)
 552 {
 553   sn_stage_t *s;
 554   char *buffer;
 555   size_t buffer_size;
 556   int status;
 557
 558   buffer = *ret_buffer;
 559   buffer_size = *ret_buffer_size;
 560
 561   if (buffer_size == 0)
 562     return (NULL);
 563
 564   s = sn_stage_create (0);
 565   if (s == NULL)
 566     return (NULL);
 567
 568   status = 0;
 569   while (buffer_size > 0)
 570   {
 571     sn_comparator_t c;
 572     char *endptr;
 573     char *substr;
 574     size_t substr_length;
 575
 576     endptr = strchr (buffer, '\n');
 577     if (endptr == NULL)
 578     {
 579       status = -1;
 580       break;
 581     }
 582
 583     *endptr = 0;
 584     endptr++;
 585
 586     substr = buffer;
 587     substr_length = strlen (buffer);
 588     buffer = endptr;
 589     buffer_size -= (substr_length + 1);
 590
 591     if ((substr_length > 0) && (substr[substr_length - 1] == '\r'))
 592     {
 593       substr[substr_length - 1] = 0;
 594       substr_length--;
 595     }
 596
 597     if (substr_length == 0)
 598     {
 599       status = 0;
 600       break;
 601     }
 602
 603     endptr = NULL;
 604     c.min = (int) strtol (substr, &endptr, 0);
 605     if (substr == endptr)
 606     {
 607       status = -1;
 608       break;
 609     }
 610
 611     substr = endptr;
 612     endptr = NULL;
 613     c.max = (int) strtol (substr, &endptr, 0);
 614     if (substr == endptr)
 615     {
 616       status = -1;
 617       break;
 618     }
 619
 620     sn_stage_comparator_add (s, &c);
 621   } /* while (buffer_size > 0) */
 622
 623   if ((status != 0) || (s->comparators_num == 0))
 624   {
 625     sn_stage_destroy (s);
 626     return (NULL);
 627   }
 628
 629   *ret_buffer = buffer;
 630   *ret_buffer_size = buffer_size;
 631   return (s);
 632 } /* sn_stage_t *sn_stage_unserialize */
 633
 634 int sn_stage_compare (const sn_stage_t *s0, const sn_stage_t *s1) /* {{{ */
 635 {
 636   int status;
 637   int i;
 638
 639   if (s0 == s1)
 640     return (0);
 641   else if (s0 == NULL)
 642     return (-1);
 643   else if (s1 == NULL)
 644     return (1);
 645
 646   if (s0->comparators_num < s1->comparators_num)
 647     return (-1);
 648   else if (s0->comparators_num > s1->comparators_num)
 649     return (1);
 650
 651   for (i = 0; i < s0->comparators_num; i++)
 652   {
 653     status = sn_comparator_compare (s0->comparators + i, s1->comparators + i);
 654     if (status != 0)
 655       return (status);
 656   }
 657
 658   return (0);
 659 } /* }}} int sn_stage_compare */
 660
 661 uint64_t sn_stage_get_hashval (const sn_stage_t *s) /* {{{ */
 662 {
 663   uint64_t hash;
 664   int i;
 665
 666   if (s == NULL)
 667     return (0);
 668
 669   hash = (uint64_t) s->depth;
 670
 671   for (i = 0; i < s->comparators_num; i++)
 672     hash = (hash * 99991) + sn_comparator_get_hashval (s->comparators + i);
 673
 674   return (hash);
 675 } /* }}} uint64_t sn_stage_get_hashval */
 676
 677 /* vim: set shiftwidth=2 softtabstop=2 expandtab fdm=marker : */