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, /* {{{ */
 264     enum sn_network_cut_dir_e dir)
 265 {
 266   int i;
 267   int position = input;
 268
 269   for (i = 0; i < n->stages_num; i++)
 270   {
 271     sn_stage_t *s;
 272     int new_position;
 273
 274     s = n->stages[i];
 275     new_position = sn_stage_cut_at (s, position, dir);
 276
 277     if (position != new_position)
 278     {
 279       int j;
 280
 281       for (j = 0; j < i; j++)
 282         sn_stage_swap (n->stages[j], position, new_position);
 283     }
 284
 285     position = new_position;
 286   }
 287
 288   assert (((dir == DIR_MIN) && (position == 0))
 289       || ((dir == DIR_MAX) && (position == (n->inputs_num - 1))));
 290
 291   for (i = 0; i < n->stages_num; i++)
 292     sn_stage_remove_input (n->stages[i], position);
 293
 294   n->inputs_num--;
 295
 296   return (0);
 297 } /* }}} int sn_network_cut_at */
 298
 299 static int sn_network_add_bitonic_merger_recursive (sn_network_t *n, /* {{{ */
 300     int low, int num)
 301 {
 302   sn_stage_t *s;
 303   int m;
 304   int i;
 305
 306   if (num == 1)
 307     return (0);
 308
 309   s = sn_stage_create (n->stages_num);
 310   if (s == NULL)
 311     return (-1);
 312
 313   m = num / 2;
 314
 315   for (i = low; i < (low + m); i++)
 316   {
 317     sn_comparator_t c;
 318
 319     c.min = i;
 320     c.max = i + m;
 321
 322     sn_stage_comparator_add (s, &c);
 323   }
 324
 325   sn_network_stage_add (n, s);
 326
 327   sn_network_add_bitonic_merger_recursive (n, low, m);
 328   sn_network_add_bitonic_merger_recursive (n, low + m, m);
 329
 330   return (0);
 331 } /* }}} int sn_network_add_bitonic_merger_recursive */
 332
 333 static int sn_network_add_bitonic_merger (sn_network_t *n) /* {{{ */
 334 {
 335   sn_stage_t *s;
 336   int m;
 337   int i;
 338
 339   s = sn_stage_create (n->stages_num);
 340   if (s == NULL)
 341     return (-1);
 342
 343   m = n->inputs_num / 2;
 344
 345   for (i = 0; i < m; i++)
 346   {
 347     sn_comparator_t c;
 348
 349     c.min = i;
 350     c.max = n->inputs_num - (i + 1);
 351
 352     sn_stage_comparator_add (s, &c);
 353   }
 354
 355   sn_network_stage_add (n, s);
 356
 357   sn_network_add_bitonic_merger_recursive (n, 0, m);
 358   sn_network_add_bitonic_merger_recursive (n, m, m);
 359
 360   return (0);
 361 } /* }}} int sn_network_add_bitonic_merger */
 362
 363 static int sn_network_add_odd_even_merger_recursive (sn_network_t *n, /* {{{ */
 364     int *indizes, int indizes_num)
 365 {
 366   if (indizes_num > 2)
 367   {
 368     sn_comparator_t c;
 369     sn_stage_t *s;
 370     int indizes_half_num;
 371     int *indizes_half;
 372     int status;
 373     int i;
 374
 375     indizes_half_num = indizes_num / 2;
 376     indizes_half = (int *) malloc (indizes_num * sizeof (int));
 377     if (indizes_half == NULL)
 378       return (-1);
 379
 380     for (i = 0; i < indizes_half_num; i++)
 381     {
 382       indizes_half[i] = indizes[2 * i];
 383       indizes_half[indizes_half_num + i] = indizes[(2 * i) + 1];
 384     }
 385
 386     status = sn_network_add_odd_even_merger_recursive (n,
 387         indizes_half, indizes_half_num);
 388     if (status != 0)
 389     {
 390       free (indizes_half);
 391       return (status);
 392     }
 393
 394     status = sn_network_add_odd_even_merger_recursive (n,
 395         indizes_half + indizes_half_num, indizes_half_num);
 396     if (status != 0)
 397     {
 398       free (indizes_half);
 399       return (status);
 400     }
 401
 402     free (indizes_half);
 403
 404     s = sn_stage_create (n->stages_num);
 405     if (s == NULL)
 406       return (-1);
 407
 408     for (i = 1; i < (indizes_num - 2); i += 2)
 409     {
 410       c.min = indizes[i];
 411       c.max = indizes[i + 1];
 412
 413       sn_stage_comparator_add (s, &c);
 414     }
 415
 416     sn_network_stage_add (n, s);
 417   }
 418   else
 419   {
 420     sn_comparator_t c;
 421     sn_stage_t *s;
 422
 423     assert (indizes_num == 2);
 424
 425     c.min = indizes[0];
 426     c.max = indizes[1];
 427
 428     s = sn_stage_create (n->stages_num);
 429     if (s == NULL)
 430       return (-1);
 431
 432     sn_stage_comparator_add (s, &c);
 433     sn_network_stage_add (n, s);
 434   }
 435
 436   return (0);
 437 } /* }}} int sn_network_add_odd_even_merger_recursive */
 438
 439 static int sn_network_add_odd_even_merger (sn_network_t *n) /* {{{ */
 440 {
 441   int *indizes;
 442   int indizes_num;
 443   int status;
 444   int i;
 445
 446   indizes_num = n->inputs_num;
 447   indizes = (int *) malloc (indizes_num * sizeof (int));
 448   if (indizes == NULL)
 449     return (-1);
 450
 451   for (i = 0; i < indizes_num; i++)
 452     indizes[i] = i;
 453
 454   status = sn_network_add_odd_even_merger_recursive (n,
 455       indizes, indizes_num);
 456
 457   free (indizes);
 458   return (status);
 459 } /* }}} int sn_network_add_bitonic_merger */
 460
 461 sn_network_t *sn_network_combine (sn_network_t *n0, /* {{{ */
 462     sn_network_t *n1)
 463 {
 464   sn_network_t *n;
 465   int stages_num;
 466   int i;
 467   int j;
 468
 469   stages_num = (n0->stages_num > n1->stages_num)
 470     ? n0->stages_num
 471     : n1->stages_num;
 472
 473   n = sn_network_create (n0->inputs_num + n1->inputs_num);
 474   if (n == NULL)
 475     return (NULL);
 476
 477   for (i = 0; i < stages_num; i++)
 478   {
 479     sn_stage_t *s = sn_stage_create (i);
 480
 481     if (i < n0->stages_num)
 482       for (j = 0; j < SN_STAGE_COMP_NUM (n0->stages[i]); j++)
 483       {
 484         sn_comparator_t *c = SN_STAGE_COMP_GET (n0->stages[i], j);
 485         sn_stage_comparator_add (s, c);
 486       }
 487
 488     if (i < n1->stages_num)
 489       for (j = 0; j < SN_STAGE_COMP_NUM (n1->stages[i]); j++)
 490       {
 491         sn_comparator_t *c_orig = SN_STAGE_COMP_GET (n1->stages[i], j);
 492         sn_comparator_t  c_copy;
 493
 494         SN_COMP_MIN(&c_copy) = SN_COMP_MIN(c_orig) + n0->inputs_num;
 495         SN_COMP_MAX(&c_copy) = SN_COMP_MAX(c_orig) + n0->inputs_num;
 496
 497         sn_stage_comparator_add (s, &c_copy);
 498       }
 499
 500     sn_network_stage_add (n, s);
 501   }
 502
 503   if (sn_bounded_random (0, 1) == 0)
 504   {
 505     sn_network_add_bitonic_merger (n);
 506   }
 507   else
 508   {
 509     sn_network_add_odd_even_merger (n);
 510   }
 511
 512   sn_network_compress (n);
 513
 514   return (n);
 515 } /* }}} sn_network_t *sn_network_combine */
 516
 517 int sn_network_sort (sn_network_t *n, int *values) /* {{{ */
 518 {
 519   int status;
 520   int i;
 521
 522   status = 0;
 523   for (i = 0; i < n->stages_num; i++)
 524   {
 525     status = sn_stage_sort (n->stages[i], values);
 526     if (status != 0)
 527       return (status);
 528   }
 529
 530   return (status);
 531 } /* }}} int sn_network_sort */
 532
 533 int sn_network_brute_force_check (sn_network_t *n) /* {{{ */
 534 {
 535   int test_pattern[n->inputs_num];
 536   int values[n->inputs_num];
 537   int status;
 538   int i;
 539
 540   memset (test_pattern, 0, sizeof (test_pattern));
 541   while (42)
 542   {
 543     int previous;
 544     int overflow;
 545
 546     /* Copy the current pattern and let the network sort it */
 547     memcpy (values, test_pattern, sizeof (values));
 548     status = sn_network_sort (n, values);
 549     if (status != 0)
 550       return (status);
 551
 552     /* Check if the array is now sorted. */
 553     previous = values[0];
 554     for (i = 1; i < n->inputs_num; i++)
 555     {
 556       if (previous > values[i])
 557         return (1);
 558       previous = values[i];
 559     }
 560
 561     /* Generate the next test pattern */
 562     overflow = 1;
 563     for (i = 0; i < n->inputs_num; i++)
 564     {
 565       if (test_pattern[i] == 0)
 566       {
 567         test_pattern[i] = 1;
 568         overflow = 0;
 569         break;
 570       }
 571       else
 572       {
 573         test_pattern[i] = 0;
 574         overflow = 1;
 575       }
 576     }
 577
 578     /* Break out of the while loop if we tested all possible patterns */
 579     if (overflow == 1)
 580       break;
 581   } /* while (42) */
 582
 583   /* All tests successfull */
 584   return (0);
 585 } /* }}} int sn_network_brute_force_check */
 586
 587 sn_network_t *sn_network_read (FILE *fh) /* {{{ */
 588 {
 589   sn_network_t *n;
 590   char buffer[64];
 591
 592   int opt_inputs = 0;
 593
 594   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 595   {
 596     char *str_key = buffer;
 597     char *str_value = NULL;
 598     int   buffer_len = strlen (buffer);
 599
 600     while ((buffer_len > 0) && ((buffer[buffer_len - 1] == '\n')
 601           || (buffer[buffer_len - 1] == '\r')))
 602     {
 603       buffer_len--;
 604       buffer[buffer_len] = '\0';
 605     }
 606     if (buffer_len == 0)
 607       break;
 608
 609     str_value = strchr (buffer, ':');
 610     if (str_value == NULL)
 611     {
 612       printf ("Cannot parse line: %s\n", buffer);
 613       continue;
 614     }
 615
 616     *str_value = '\0'; str_value++;
 617     while ((*str_value != '\0') && (isspace (*str_value) != 0))
 618       str_value++;
 619
 620     if (strcasecmp ("Inputs", str_key) == 0)
 621       opt_inputs = atoi (str_value);
 622     else
 623       printf ("Unknown key: %s\n", str_key);
 624   } /* while (fgets) */
 625
 626   if (opt_inputs < 2)
 627     return (NULL);
 628
 629   n = sn_network_create (opt_inputs);
 630
 631   while (42)
 632   {
 633     sn_stage_t *s;
 634
 635     s = sn_stage_read (fh);
 636     if (s == NULL)
 637       break;
 638
 639     sn_network_stage_add (n, s);
 640   }
 641
 642   if (SN_NETWORK_STAGE_NUM (n) < 1)
 643   {
 644     sn_network_destroy (n);
 645     return (NULL);
 646   }
 647
 648   return (n);
 649 } /* }}} sn_network_t *sn_network_read */
 650
 651 sn_network_t *sn_network_read_file (const char *file) /* {{{ */
 652 {
 653   sn_network_t *n;
 654   FILE *fh;
 655
 656   fh = fopen (file, "r");
 657   if (fh == NULL)
 658     return (NULL);
 659
 660   n = sn_network_read (fh);
 661
 662   fclose (fh);
 663
 664   return (n);
 665 } /* }}} sn_network_t *sn_network_read_file */
 666
 667 int sn_network_write (sn_network_t *n, FILE *fh) /* {{{ */
 668 {
 669   int i;
 670
 671   fprintf (fh, "Inputs: %i\n", n->inputs_num);
 672   fprintf (fh, "\n");
 673
 674   for (i = 0; i < n->stages_num; i++)
 675     sn_stage_write (n->stages[i], fh);
 676
 677   return (0);
 678 } /* }}} int sn_network_write */
 679
 680 int sn_network_write_file (sn_network_t *n, const char *file) /* {{{ */
 681 {
 682   int status;
 683   FILE *fh;
 684
 685   fh = fopen (file, "w");
 686   if (fh == NULL)
 687     return (-1);
 688
 689   status = sn_network_write (n, fh);
 690
 691   fclose (fh);
 692
 693   return (status);
 694 } /* }}} int sn_network_write_file */
 695
 696 int sn_network_serialize (sn_network_t *n, char **ret_buffer, /* {{{ */
 697     size_t *ret_buffer_size)
 698 {
 699   char *buffer;
 700   size_t buffer_size;
 701   int status;
 702   int i;
 703
 704   buffer = *ret_buffer;
 705   buffer_size = *ret_buffer_size;
 706
 707 #define SNPRINTF_OR_FAIL(...) \
 708   status = snprintf (buffer, buffer_size, __VA_ARGS__); \
 709   if ((status < 1) || (status >= buffer_size)) \
 710     return (-1); \
 711   buffer += status; \
 712   buffer_size -= status;
 713
 714   SNPRINTF_OR_FAIL ("Inputs: %i\r\n\r\n", n->inputs_num);
 715
 716   for (i = 0; i < n->stages_num; i++)
 717   {
 718     status = sn_stage_serialize (n->stages[i], &buffer, &buffer_size);
 719     if (status != 0)
 720       return (status);
 721   }
 722
 723   *ret_buffer = buffer;
 724   *ret_buffer_size = buffer_size;
 725   return (0);
 726 } /* }}} int sn_network_serialize */
 727
 728 sn_network_t *sn_network_unserialize (char *buffer, /* {{{ */
 729     size_t buffer_size)
 730 {
 731   sn_network_t *n;
 732   int opt_inputs = 0;
 733
 734   if (buffer_size == 0)
 735     return (NULL);
 736
 737   /* Read options first */
 738   while (buffer_size > 0)
 739   {
 740     char *endptr;
 741     char *str_key;
 742     char *str_value;
 743     char *line;
 744     int   line_len;
 745
 746     line = buffer;
 747     endptr = strchr (buffer, '\n');
 748     if (endptr == NULL)
 749       return (NULL);
 750
 751     *endptr = 0;
 752     endptr++;
 753     buffer = endptr;
 754     line_len = strlen (line);
 755
 756     if ((line_len > 0) && (line[line_len - 1] == '\r'))
 757     {
 758       line[line_len - 1] = 0;
 759       line_len--;
 760     }
 761
 762     if (line_len == 0)
 763       break;
 764
 765     str_key = line;
 766     str_value = strchr (line, ':');
 767     if (str_value == NULL)
 768     {
 769       printf ("Cannot parse line: %s\n", line);
 770       continue;
 771     }
 772
 773     *str_value = '\0'; str_value++;
 774     while ((*str_value != '\0') && (isspace (*str_value) != 0))
 775       str_value++;
 776
 777     if (strcasecmp ("Inputs", str_key) == 0)
 778       opt_inputs = atoi (str_value);
 779     else
 780       printf ("Unknown key: %s\n", str_key);
 781   } /* while (fgets) */
 782
 783   if (opt_inputs < 2)
 784     return (NULL);
 785
 786   n = sn_network_create (opt_inputs);
 787
 788   while (42)
 789   {
 790     sn_stage_t *s;
 791
 792     s = sn_stage_unserialize (&buffer, &buffer_size);
 793     if (s == NULL)
 794       break;
 795
 796     sn_network_stage_add (n, s);
 797   }
 798
 799   if (SN_NETWORK_STAGE_NUM (n) < 1)
 800   {
 801     sn_network_destroy (n);
 802     return (NULL);
 803   }
 804
 805   return (n);
 806 } /* }}} sn_network_t *sn_network_unserialize */
 807
 808 /* vim: set sw=2 sts=2 et fdm=marker : */