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 sn_network_t *sn_network_read (FILE *fh)
 516 {
 517   sn_network_t *n;
 518   char buffer[64];
 519
 520   int opt_inputs = 0;
 521
 522   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 523   {
 524     char *str_key = buffer;
 525     char *str_value = NULL;
 526     int   buffer_len = strlen (buffer);
 527
 528     while ((buffer_len > 0) && ((buffer[buffer_len - 1] == '\n')
 529           || (buffer[buffer_len - 1] == '\r')))
 530     {
 531       buffer_len--;
 532       buffer[buffer_len] = '\0';
 533     }
 534     if (buffer_len == 0)
 535       break;
 536
 537     str_value = strchr (buffer, ':');
 538     if (str_value == NULL)
 539     {
 540       printf ("Cannot parse line: %s\n", buffer);
 541       continue;
 542     }
 543
 544     *str_value = '\0'; str_value++;
 545     while ((*str_value != '\0') && (isspace (*str_value) != 0))
 546       str_value++;
 547
 548     if (strcasecmp ("Inputs", str_key) == 0)
 549       opt_inputs = atoi (str_value);
 550     else
 551       printf ("Unknown key: %s\n", str_key);
 552   } /* while (fgets) */
 553
 554   if (opt_inputs < 2)
 555     return (NULL);
 556
 557   n = sn_network_create (opt_inputs);
 558
 559   while (42)
 560   {
 561     sn_stage_t *s;
 562
 563     s = sn_stage_read (fh);
 564     if (s == NULL)
 565       break;
 566
 567     sn_network_stage_add (n, s);
 568   }
 569
 570   if (SN_NETWORK_STAGE_NUM (n) < 1)
 571   {
 572     sn_network_destroy (n);
 573     return (NULL);
 574   }
 575
 576   return (n);
 577 } /* sn_network_t *sn_network_read */
 578
 579 sn_network_t *sn_network_read_file (const char *file)
 580 {
 581   sn_network_t *n;
 582   FILE *fh;
 583
 584   fh = fopen (file, "r");
 585   if (fh == NULL)
 586     return (NULL);
 587
 588   n = sn_network_read (fh);
 589
 590   fclose (fh);
 591
 592   return (n);
 593 } /* sn_network_t *sn_network_read_file */
 594
 595 int sn_network_write (sn_network_t *n, FILE *fh)
 596 {
 597   int i;
 598
 599   fprintf (fh, "Inputs: %i\n", n->inputs_num);
 600   fprintf (fh, "\n");
 601
 602   for (i = 0; i < n->stages_num; i++)
 603     sn_stage_write (n->stages[i], fh);
 604
 605   return (0);
 606 } /* int sn_network_write */
 607
 608 int sn_network_write_file (sn_network_t *n, const char *file)
 609 {
 610   int status;
 611   FILE *fh;
 612
 613   fh = fopen (file, "w");
 614   if (fh == NULL)
 615     return (-1);
 616
 617   status = sn_network_write (n, fh);
 618
 619   fclose (fh);
 620
 621   return (status);
 622 } /* int sn_network_write_file */
 623
 624 /* vim: set shiftwidth=2 softtabstop=2 : */