src/sn_network.c

   1 /**
   2  * collectd - src/sn_network.c
   3  * Copyright (C) 2008  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 <octo at verplant.org>
  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 <stdio.h>
  31 #include <string.h>
  32 #include <strings.h>
  33 #include <ctype.h>
  34 #include <assert.h>
  35
  36 #include "sn_network.h"
  37 #include "sn_random.h"
  38
  39 sn_network_t *sn_network_create (int inputs_num)
  40 {
  41   sn_network_t *n;
  42
  43   n = (sn_network_t *) malloc (sizeof (sn_network_t));
  44   if (n == NULL)
  45     return (NULL);
  46   memset (n, '\0', sizeof (sn_network_t));
  47
  48   n->inputs_num = inputs_num;
  49
  50   return (n);
  51 } /* sn_network_t *sn_network_create */
  52
  53 void sn_network_destroy (sn_network_t *n)
  54 {
  55   if (n == NULL)
  56     return;
  57
  58   if (n->stages != NULL)
  59   {
  60     int i;
  61     for (i = 0; i < n->stages_num; i++)
  62     {
  63       sn_stage_destroy (n->stages[i]);
  64       n->stages[i] = NULL;
  65     }
  66     free (n->stages);
  67     n->stages = NULL;
  68   }
  69
  70   free (n);
  71 } /* void sn_network_destroy */
  72
  73 int sn_network_stage_add (sn_network_t *n, sn_stage_t *s)
  74 {
  75   sn_stage_t **temp;
  76
  77   temp = (sn_stage_t **) realloc (n->stages, (n->stages_num + 1)
  78       * sizeof (sn_stage_t *));
  79   if (temp == NULL)
  80     return (-1);
  81
  82   n->stages = temp;
  83   SN_STAGE_DEPTH (s) = n->stages_num;
  84   n->stages[n->stages_num] = s;
  85   n->stages_num++;
  86
  87   return (0);
  88 } /* int sn_network_stage_add */
  89
  90 int sn_network_stage_remove (sn_network_t *n, int s_num)
  91 {
  92   int nmemb = n->stages_num - (s_num + 1);
  93   sn_stage_t **temp;
  94
  95   assert (s_num < n->stages_num);
  96
  97   sn_stage_destroy (n->stages[s_num]);
  98   n->stages[s_num] = NULL;
  99
 100   if (nmemb > 0)
 101   {
 102     memmove (n->stages + s_num, n->stages + (s_num + 1),
 103         nmemb * sizeof (sn_stage_t *));
 104     n->stages[n->stages_num - 1] = NULL;
 105   }
 106   n->stages_num--;
 107
 108   /* Free the unused memory */
 109   if (n->stages_num == 0)
 110   {
 111     free (n->stages);
 112     n->stages = NULL;
 113   }
 114   else
 115   {
 116     temp = (sn_stage_t **) realloc (n->stages,
 117         n->stages_num * sizeof (sn_stage_t *));
 118     if (temp == NULL)
 119       return (-1);
 120     n->stages = temp;
 121   }
 122
 123   return (0);
 124 } /* int sn_network_stage_remove */
 125
 126 sn_network_t *sn_network_clone (const sn_network_t *n)
 127 {
 128   sn_network_t *n_copy;
 129   int i;
 130
 131   n_copy = sn_network_create (n->inputs_num);
 132   if (n_copy == NULL)
 133     return (NULL);
 134
 135   for (i = 0; i < n->stages_num; i++)
 136   {
 137     sn_stage_t *s;
 138     int status;
 139
 140     s = sn_stage_clone (n->stages[i]);
 141     if (s == NULL)
 142       break;
 143
 144     status = sn_network_stage_add (n_copy, s);
 145     if (status != 0)
 146       break;
 147   }
 148
 149   if (i < n->stages_num)
 150   {
 151     sn_network_destroy (n_copy);
 152     return (NULL);
 153   }
 154
 155   return (n_copy);
 156 } /* sn_network_t *sn_network_clone */
 157
 158 int sn_network_show (sn_network_t *n)
 159 {
 160   int i;
 161
 162   for (i = 0; i < n->stages_num; i++)
 163     sn_stage_show (n->stages[i]);
 164
 165   return (0);
 166 } /* int sn_network_show */
 167
 168 int sn_network_invert (sn_network_t *n)
 169 {
 170   int i;
 171
 172   for (i = 0; i < n->stages_num; i++)
 173     sn_stage_invert (n->stages[i]);
 174
 175   return (0);
 176 } /* int sn_network_invert */
 177
 178 int sn_network_compress (sn_network_t *n)
 179 {
 180   int i;
 181   int j;
 182   int k;
 183
 184   for (i = 1; i < n->stages_num; i++)
 185   {
 186     sn_stage_t *s;
 187
 188     s = n->stages[i];
 189
 190     for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
 191     {
 192       sn_comparator_t *c = SN_STAGE_COMP_GET (s, j);
 193       int move_to = i;
 194
 195       for (k = i - 1; k >= 0; k--)
 196       {
 197         int conflict;
 198
 199         conflict = sn_stage_comparator_check_conflict (n->stages[k], c);
 200         if (conflict == 0)
 201         {
 202           move_to = k;
 203           continue;
 204         }
 205
 206         if (conflict == 2)
 207           move_to = -1;
 208         break;
 209       }
 210
 211       if (move_to < i)
 212       {
 213         if (move_to >= 0)
 214           sn_stage_comparator_add (n->stages[move_to], c);
 215         sn_stage_comparator_remove (s, j);
 216         j--;
 217       }
 218     }
 219   }
 220
 221   while ((n->stages_num > 0)
 222       && (SN_STAGE_COMP_NUM (n->stages[n->stages_num - 1]) == 0))
 223     sn_network_stage_remove (n, n->stages_num - 1);
 224
 225   return (0);
 226 } /* int sn_network_compress */
 227
 228 int sn_network_normalize (sn_network_t *n)
 229 {
 230   int i;
 231
 232   for (i = n->stages_num - 1; i >= 0; i--)
 233   {
 234     sn_stage_t *s;
 235     int j;
 236
 237     s = n->stages[i];
 238
 239     for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
 240     {
 241       sn_comparator_t *c;
 242       int min;
 243       int max;
 244
 245       c = SN_STAGE_COMP_GET (s, j);
 246
 247       min = c->min;
 248       max = c->max;
 249
 250       if (min > max)
 251       {
 252         int k;
 253
 254         for (k = i; k >= 0; k--)
 255           sn_stage_swap (n->stages[k], min, max);
 256       }
 257     } /* for (j = 0 .. #comparators) */
 258   } /* for (i = n->stages_num - 1 .. 0) */
 259
 260   return (0);
 261 } /* int sn_network_normalize */
 262
 263 int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir)
 264 {
 265   int i;
 266   int position = input;
 267
 268   for (i = 0; i < n->stages_num; i++)
 269   {
 270     sn_stage_t *s;
 271     int new_position;
 272
 273     s = n->stages[i];
 274     new_position = sn_stage_cut_at (s, position, dir);
 275
 276     if (position != new_position)
 277     {
 278       int j;
 279
 280       for (j = 0; j < i; j++)
 281         sn_stage_swap (n->stages[j], position, new_position);
 282     }
 283
 284     position = new_position;
 285   }
 286
 287   assert (((dir == DIR_MIN) && (position == 0))
 288       || ((dir == DIR_MAX) && (position == (n->inputs_num - 1))));
 289
 290   for (i = 0; i < n->stages_num; i++)
 291     sn_stage_remove_input (n->stages[i], position);
 292
 293   n->inputs_num--;
 294
 295   return (0);
 296 } /* int sn_network_cut_at */
 297
 298 static int sn_network_add_bitonic_merger_recursive (sn_network_t *n,
 299     int low, int num)
 300 {
 301   sn_stage_t *s;
 302   int m;
 303   int i;
 304
 305   if (num == 1)
 306     return (0);
 307
 308   s = sn_stage_create (n->stages_num);
 309   if (s == NULL)
 310     return (-1);
 311
 312   m = num / 2;
 313
 314   for (i = low; i < (low + m); i++)
 315   {
 316     sn_comparator_t c;
 317
 318     c.min = i;
 319     c.max = i + m;
 320
 321     sn_stage_comparator_add (s, &c);
 322   }
 323
 324   sn_network_stage_add (n, s);
 325
 326   sn_network_add_bitonic_merger_recursive (n, low, m);
 327   sn_network_add_bitonic_merger_recursive (n, low + m, m);
 328
 329   return (0);
 330 } /* int sn_network_add_bitonic_merger_recursive */
 331
 332 static int sn_network_add_bitonic_merger (sn_network_t *n)
 333 {
 334   sn_stage_t *s;
 335   int m;
 336   int i;
 337
 338   s = sn_stage_create (n->stages_num);
 339   if (s == NULL)
 340     return (-1);
 341
 342   m = n->inputs_num / 2;
 343
 344   for (i = 0; i < m; i++)
 345   {
 346     sn_comparator_t c;
 347
 348     c.min = i;
 349     c.max = n->inputs_num - (i + 1);
 350
 351     sn_stage_comparator_add (s, &c);
 352   }
 353
 354   sn_network_stage_add (n, s);
 355
 356   sn_network_add_bitonic_merger_recursive (n, 0, m);
 357   sn_network_add_bitonic_merger_recursive (n, m, m);
 358
 359   return (0);
 360 } /* int sn_network_add_bitonic_merger */
 361
 362 static int sn_network_add_odd_even_merger_recursive (sn_network_t *n,
 363     int *indizes, int indizes_num)
 364 {
 365   if (indizes_num > 2)
 366   {
 367     sn_comparator_t c;
 368     sn_stage_t *s;
 369     int indizes_half_num;
 370     int *indizes_half;
 371     int status;
 372     int i;
 373
 374     indizes_half_num = indizes_num / 2;
 375     indizes_half = (int *) malloc (indizes_num * sizeof (int));
 376     if (indizes_half == NULL)
 377       return (-1);
 378
 379     for (i = 0; i < indizes_half_num; i++)
 380     {
 381       indizes_half[i] = indizes[2 * i];
 382       indizes_half[indizes_half_num + i] = indizes[(2 * i) + 1];
 383     }
 384
 385     status = sn_network_add_odd_even_merger_recursive (n,
 386         indizes_half, indizes_half_num);
 387     if (status != 0)
 388     {
 389       free (indizes_half);
 390       return (status);
 391     }
 392
 393     status = sn_network_add_odd_even_merger_recursive (n,
 394         indizes_half + indizes_half_num, indizes_half_num);
 395     if (status != 0)
 396     {
 397       free (indizes_half);
 398       return (status);
 399     }
 400
 401     free (indizes_half);
 402
 403     s = sn_stage_create (n->stages_num);
 404     if (s == NULL)
 405       return (-1);
 406
 407     for (i = 1; i < (indizes_num - 2); i += 2)
 408     {
 409       c.min = indizes[i];
 410       c.max = indizes[i + 1];
 411
 412       sn_stage_comparator_add (s, &c);
 413     }
 414
 415     sn_network_stage_add (n, s);
 416   }
 417   else
 418   {
 419     sn_comparator_t c;
 420     sn_stage_t *s;
 421
 422     assert (indizes_num == 2);
 423
 424     c.min = indizes[0];
 425     c.max = indizes[1];
 426
 427     s = sn_stage_create (n->stages_num);
 428     if (s == NULL)
 429       return (-1);
 430
 431     sn_stage_comparator_add (s, &c);
 432     sn_network_stage_add (n, s);
 433   }
 434
 435   return (0);
 436 } /* int sn_network_add_odd_even_merger_recursive */
 437
 438 static int sn_network_add_odd_even_merger (sn_network_t *n)
 439 {
 440   int *indizes;
 441   int indizes_num;
 442   int status;
 443   int i;
 444
 445   indizes_num = n->inputs_num;
 446   indizes = (int *) malloc (indizes_num * sizeof (int));
 447   if (indizes == NULL)
 448     return (-1);
 449
 450   for (i = 0; i < indizes_num; i++)
 451     indizes[i] = i;
 452
 453   status = sn_network_add_odd_even_merger_recursive (n,
 454       indizes, indizes_num);
 455
 456   free (indizes);
 457   return (status);
 458 } /* int sn_network_add_bitonic_merger */
 459
 460 sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1)
 461 {
 462   sn_network_t *n;
 463   int stages_num;
 464   int i;
 465   int j;
 466
 467   stages_num = (n0->stages_num > n1->stages_num)
 468     ? n0->stages_num
 469     : n1->stages_num;
 470
 471   n = sn_network_create (n0->inputs_num + n1->inputs_num);
 472   if (n == NULL)
 473     return (NULL);
 474
 475   for (i = 0; i < stages_num; i++)
 476   {
 477     sn_stage_t *s = sn_stage_create (i);
 478
 479     if (i < n0->stages_num)
 480       for (j = 0; j < SN_STAGE_COMP_NUM (n0->stages[i]); j++)
 481       {
 482         sn_comparator_t *c = SN_STAGE_COMP_GET (n0->stages[i], j);
 483         sn_stage_comparator_add (s, c);
 484       }
 485
 486     if (i < n1->stages_num)
 487       for (j = 0; j < SN_STAGE_COMP_NUM (n1->stages[i]); j++)
 488       {
 489         sn_comparator_t *c_orig = SN_STAGE_COMP_GET (n1->stages[i], j);
 490         sn_comparator_t  c_copy;
 491
 492         SN_COMP_MIN(&c_copy) = SN_COMP_MIN(c_orig) + n0->inputs_num;
 493         SN_COMP_MAX(&c_copy) = SN_COMP_MAX(c_orig) + n0->inputs_num;
 494
 495         sn_stage_comparator_add (s, &c_copy);
 496       }
 497
 498     sn_network_stage_add (n, s);
 499   }
 500
 501   if (sn_bounded_random (0, 1) == 0)
 502   {
 503     sn_network_add_bitonic_merger (n);
 504   }
 505   else
 506   {
 507     sn_network_add_odd_even_merger (n);
 508   }
 509
 510   sn_network_compress (n);
 511
 512   return (n);
 513 } /* sn_network_t *sn_network_combine */
 514
 515 int sn_network_sort (sn_network_t *n, int *values)
 516 {
 517   int status;
 518   int i;
 519
 520   status = 0;
 521   for (i = 0; i < n->stages_num; i++)
 522   {
 523     status = sn_stage_sort (n->stages[i], values);
 524     if (status != 0)
 525       return (status);
 526   }
 527
 528   return (status);
 529 } /* int sn_network_sort */
 530
 531 int sn_network_brute_force_check (sn_network_t *n)
 532 {
 533   int test_pattern[n->inputs_num];
 534   int values[n->inputs_num];
 535   int status;
 536   int i;
 537
 538   memset (test_pattern, 0, sizeof (test_pattern));
 539   while (42)
 540   {
 541     int previous;
 542     int overflow;
 543
 544     /* Copy the current pattern and let the network sort it */
 545     memcpy (values, test_pattern, sizeof (values));
 546     status = sn_network_sort (n, values);
 547     if (status != 0)
 548       return (status);
 549
 550     /* Check if the array is now sorted. */
 551     previous = values[0];
 552     for (i = 1; i < n->inputs_num; i++)
 553     {
 554       if (previous > values[i])
 555         return (1);
 556       previous = values[i];
 557     }
 558
 559     /* Generate the next test pattern */
 560     overflow = 1;
 561     for (i = 0; i < n->inputs_num; i++)
 562     {
 563       if (test_pattern[i] == 0)
 564       {
 565         test_pattern[i] = 1;
 566         overflow = 0;
 567         break;
 568       }
 569       else
 570       {
 571         test_pattern[i] = 0;
 572         overflow = 1;
 573       }
 574     }
 575
 576     /* Break out of the while loop if we tested all possible patterns */
 577     if (overflow == 1)
 578       break;
 579   } /* while (42) */
 580
 581   /* All tests successfull */
 582   return (0);
 583 } /* int sn_network_brute_force_check */
 584
 585 sn_network_t *sn_network_read (FILE *fh)
 586 {
 587   sn_network_t *n;
 588   char buffer[64];
 589
 590   int opt_inputs = 0;
 591
 592   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 593   {
 594     char *str_key = buffer;
 595     char *str_value = NULL;
 596     int   buffer_len = strlen (buffer);
 597
 598     while ((buffer_len > 0) && ((buffer[buffer_len - 1] == '\n')
 599           || (buffer[buffer_len - 1] == '\r')))
 600     {
 601       buffer_len--;
 602       buffer[buffer_len] = '\0';
 603     }
 604     if (buffer_len == 0)
 605       break;
 606
 607     str_value = strchr (buffer, ':');
 608     if (str_value == NULL)
 609     {
 610       printf ("Cannot parse line: %s\n", buffer);
 611       continue;
 612     }
 613
 614     *str_value = '\0'; str_value++;
 615     while ((*str_value != '\0') && (isspace (*str_value) != 0))
 616       str_value++;
 617
 618     if (strcasecmp ("Inputs", str_key) == 0)
 619       opt_inputs = atoi (str_value);
 620     else
 621       printf ("Unknown key: %s\n", str_key);
 622   } /* while (fgets) */
 623
 624   if (opt_inputs < 2)
 625     return (NULL);
 626
 627   n = sn_network_create (opt_inputs);
 628
 629   while (42)
 630   {
 631     sn_stage_t *s;
 632
 633     s = sn_stage_read (fh);
 634     if (s == NULL)
 635       break;
 636
 637     sn_network_stage_add (n, s);
 638   }
 639
 640   if (SN_NETWORK_STAGE_NUM (n) < 1)
 641   {
 642     sn_network_destroy (n);
 643     return (NULL);
 644   }
 645
 646   return (n);
 647 } /* sn_network_t *sn_network_read */
 648
 649 sn_network_t *sn_network_read_file (const char *file)
 650 {
 651   sn_network_t *n;
 652   FILE *fh;
 653
 654   fh = fopen (file, "r");
 655   if (fh == NULL)
 656     return (NULL);
 657
 658   n = sn_network_read (fh);
 659
 660   fclose (fh);
 661
 662   return (n);
 663 } /* sn_network_t *sn_network_read_file */
 664
 665 int sn_network_write (sn_network_t *n, FILE *fh)
 666 {
 667   int i;
 668
 669   fprintf (fh, "Inputs: %i\n", n->inputs_num);
 670   fprintf (fh, "\n");
 671
 672   for (i = 0; i < n->stages_num; i++)
 673     sn_stage_write (n->stages[i], fh);
 674
 675   return (0);
 676 } /* int sn_network_write */
 677
 678 int sn_network_write_file (sn_network_t *n, const char *file)
 679 {
 680   int status;
 681   FILE *fh;
 682
 683   fh = fopen (file, "w");
 684   if (fh == NULL)
 685     return (-1);
 686
 687   status = sn_network_write (n, fh);
 688
 689   fclose (fh);
 690
 691   return (status);
 692 } /* int sn_network_write_file */
 693
 694 int sn_network_serialize (sn_network_t *n, char **ret_buffer,
 695     size_t *ret_buffer_size)
 696 {
 697   char *buffer;
 698   size_t buffer_size;
 699   int status;
 700   int i;
 701
 702   buffer = *ret_buffer;
 703   buffer_size = *ret_buffer_size;
 704
 705 #define SNPRINTF_OR_FAIL(...) \
 706   status = snprintf (buffer, buffer_size, __VA_ARGS__); \
 707   if ((status < 1) || (status >= buffer_size)) \
 708     return (-1); \
 709   buffer += status; \
 710   buffer_size -= status;
 711
 712   SNPRINTF_OR_FAIL ("Inputs: %i\r\n\r\n", n->inputs_num);
 713
 714   for (i = 0; i < n->stages_num; i++)
 715   {
 716     status = sn_stage_serialize (n->stages[i], &buffer, &buffer_size);
 717     if (status != 0)
 718       return (status);
 719   }
 720
 721   *ret_buffer = buffer;
 722   *ret_buffer_size = buffer_size;
 723   return (0);
 724 } /* int sn_network_serialize */
 725
 726 sn_network_t *sn_network_unserialize (char *buffer, size_t buffer_size)
 727 {
 728   sn_network_t *n;
 729   int opt_inputs = 0;
 730
 731   if (buffer_size == 0)
 732     return (NULL);
 733
 734   /* Read options first */
 735   while (buffer_size > 0)
 736   {
 737     char *endptr;
 738     char *str_key;
 739     char *str_value;
 740     char *line;
 741     int   line_len;
 742
 743     line = buffer;
 744     endptr = strchr (buffer, '\n');
 745     if (endptr == NULL)
 746       return (NULL);
 747
 748     *endptr = 0;
 749     endptr++;
 750     buffer = endptr;
 751     line_len = strlen (line);
 752
 753     if ((line_len > 0) && (line[line_len - 1] == '\r'))
 754     {
 755       line[line_len - 1] = 0;
 756       line_len--;
 757     }
 758
 759     if (line_len == 0)
 760       break;
 761
 762     str_key = line;
 763     str_value = strchr (line, ':');
 764     if (str_value == NULL)
 765     {
 766       printf ("Cannot parse line: %s\n", line);
 767       continue;
 768     }
 769
 770     *str_value = '\0'; str_value++;
 771     while ((*str_value != '\0') && (isspace (*str_value) != 0))
 772       str_value++;
 773
 774     if (strcasecmp ("Inputs", str_key) == 0)
 775       opt_inputs = atoi (str_value);
 776     else
 777       printf ("Unknown key: %s\n", str_key);
 778   } /* while (fgets) */
 779
 780   if (opt_inputs < 2)
 781     return (NULL);
 782
 783   n = sn_network_create (opt_inputs);
 784
 785   while (42)
 786   {
 787     sn_stage_t *s;
 788
 789     s = sn_stage_unserialize (&buffer, &buffer_size);
 790     if (s == NULL)
 791       break;
 792
 793     sn_network_stage_add (n, s);
 794   }
 795
 796   if (SN_NETWORK_STAGE_NUM (n) < 1)
 797   {
 798     sn_network_destroy (n);
 799     return (NULL);
 800   }
 801
 802   return (n);
 803 } /* sn_network_t *sn_network_unserialize */
 804
 805 /* vim: set shiftwidth=2 softtabstop=2 : */