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