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