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 #include <stdlib.h>
  23 #include <stdio.h>
  24 #include <string.h>
  25 #include <strings.h>
  26 #include <ctype.h>
  27 #include <assert.h>
  28
  29 #include "sn_network.h"
  30 #include "sn_random.h"
  31
  32 sn_network_t *sn_network_create (int inputs_num)
  33 {
  34   sn_network_t *n;
  35
  36   n = (sn_network_t *) malloc (sizeof (sn_network_t));
  37   if (n == NULL)
  38     return (NULL);
  39   memset (n, '\0', sizeof (sn_network_t));
  40
  41   n->inputs_num = inputs_num;
  42
  43   return (n);
  44 } /* sn_network_t *sn_network_create */
  45
  46 void sn_network_destroy (sn_network_t *n)
  47 {
  48   if (n == NULL)
  49     return;
  50
  51   if (n->stages != NULL)
  52   {
  53     int i;
  54     for (i = 0; i < n->stages_num; i++)
  55     {
  56       sn_stage_destroy (n->stages[i]);
  57       n->stages[i] = NULL;
  58     }
  59     free (n->stages);
  60     n->stages = NULL;
  61   }
  62
  63   free (n);
  64 } /* void sn_network_destroy */
  65
  66 int sn_network_stage_add (sn_network_t *n, sn_stage_t *s)
  67 {
  68   sn_stage_t **temp;
  69
  70   temp = (sn_stage_t **) realloc (n->stages, (n->stages_num + 1)
  71       * sizeof (sn_stage_t *));
  72   if (temp == NULL)
  73     return (-1);
  74
  75   n->stages = temp;
  76   SN_STAGE_DEPTH (s) = n->stages_num;
  77   n->stages[n->stages_num] = s;
  78   n->stages_num++;
  79
  80   return (0);
  81 } /* int sn_network_stage_add */
  82
  83 int sn_network_stage_remove (sn_network_t *n, int s_num)
  84 {
  85   int nmemb = n->stages_num - (s_num + 1);
  86   sn_stage_t **temp;
  87
  88   assert (s_num < n->stages_num);
  89
  90   sn_stage_destroy (n->stages[s_num]);
  91   n->stages[s_num] = NULL;
  92
  93   if (nmemb > 0)
  94   {
  95     memmove (n->stages + s_num, n->stages + (s_num + 1),
  96         nmemb * sizeof (sn_stage_t *));
  97     n->stages[n->stages_num - 1] = NULL;
  98   }
  99   n->stages_num--;
 100
 101   /* Free the unused memory */
 102   if (n->stages_num == 0)
 103   {
 104     free (n->stages);
 105     n->stages = NULL;
 106   }
 107   else
 108   {
 109     temp = (sn_stage_t **) realloc (n->stages,
 110         n->stages_num * sizeof (sn_stage_t *));
 111     if (temp == NULL)
 112       return (-1);
 113     n->stages = temp;
 114   }
 115
 116   return (0);
 117 } /* int sn_network_stage_remove */
 118
 119 sn_network_t *sn_network_clone (const sn_network_t *n)
 120 {
 121   sn_network_t *n_copy;
 122   int i;
 123
 124   n_copy = sn_network_create (n->inputs_num);
 125   if (n_copy == NULL)
 126     return (NULL);
 127
 128   for (i = 0; i < n->stages_num; i++)
 129   {
 130     sn_stage_t *s;
 131     int status;
 132
 133     s = sn_stage_clone (n->stages[i]);
 134     if (s == NULL)
 135       break;
 136
 137     status = sn_network_stage_add (n_copy, s);
 138     if (status != 0)
 139       break;
 140   }
 141
 142   if (i < n->stages_num)
 143   {
 144     sn_network_destroy (n_copy);
 145     return (NULL);
 146   }
 147
 148   return (n_copy);
 149 } /* sn_network_t *sn_network_clone */
 150
 151 int sn_network_show (sn_network_t *n)
 152 {
 153   int i;
 154
 155   for (i = 0; i < n->stages_num; i++)
 156     sn_stage_show (n->stages[i]);
 157
 158   return (0);
 159 } /* int sn_network_show */
 160
 161 int sn_network_invert (sn_network_t *n)
 162 {
 163   int i;
 164
 165   for (i = 0; i < n->stages_num; i++)
 166     sn_stage_invert (n->stages[i]);
 167
 168   return (0);
 169 } /* int sn_network_invert */
 170
 171 int sn_network_compress (sn_network_t *n)
 172 {
 173   int i;
 174   int j;
 175   int k;
 176
 177   for (i = 1; i < n->stages_num; i++)
 178   {
 179     sn_stage_t *s;
 180
 181     s = n->stages[i];
 182
 183     for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
 184     {
 185       sn_comparator_t *c = SN_STAGE_COMP_GET (s, j);
 186       int move_to = i;
 187
 188       for (k = i - 1; k >= 0; k--)
 189       {
 190         int conflict;
 191
 192         conflict = sn_stage_comparator_check_conflict (n->stages[k], c);
 193         if (conflict == 0)
 194         {
 195           move_to = k;
 196           continue;
 197         }
 198
 199         if (conflict == 2)
 200           move_to = -1;
 201         break;
 202       }
 203
 204       if (move_to < i)
 205       {
 206         if (move_to >= 0)
 207           sn_stage_comparator_add (n->stages[move_to], c);
 208         sn_stage_comparator_remove (s, j);
 209         j--;
 210       }
 211     }
 212   }
 213
 214   while ((n->stages_num > 0)
 215       && (SN_STAGE_COMP_NUM (n->stages[n->stages_num - 1]) == 0))
 216     sn_network_stage_remove (n, n->stages_num - 1);
 217
 218   return (0);
 219 } /* int sn_network_compress */
 220
 221 int sn_network_normalize (sn_network_t *n)
 222 {
 223   int i;
 224
 225   for (i = n->stages_num - 1; i >= 0; i--)
 226   {
 227     sn_stage_t *s;
 228     int j;
 229
 230     s = n->stages[i];
 231
 232     for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
 233     {
 234       sn_comparator_t *c;
 235       int min;
 236       int max;
 237
 238       c = SN_STAGE_COMP_GET (s, j);
 239
 240       min = c->min;
 241       max = c->max;
 242
 243       if (min > max)
 244       {
 245         int k;
 246
 247         for (k = i; k >= 0; k--)
 248           sn_stage_swap (n->stages[k], min, max);
 249       }
 250     } /* for (j = 0 .. #comparators) */
 251   } /* for (i = n->stages_num - 1 .. 0) */
 252
 253   return (0);
 254 } /* int sn_network_normalize */
 255
 256 int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir)
 257 {
 258   int i;
 259   int position = input;
 260
 261   for (i = 0; i < n->stages_num; i++)
 262   {
 263     sn_stage_t *s;
 264     int new_position;
 265
 266     s = n->stages[i];
 267     new_position = sn_stage_cut_at (s, position, dir);
 268
 269     if (position != new_position)
 270     {
 271       int j;
 272
 273       for (j = 0; j < i; j++)
 274         sn_stage_swap (n->stages[j], position, new_position);
 275     }
 276
 277     position = new_position;
 278   }
 279
 280   assert (((dir == DIR_MIN) && (position == 0))
 281       || ((dir == DIR_MAX) && (position == (n->inputs_num - 1))));
 282
 283   for (i = 0; i < n->stages_num; i++)
 284     sn_stage_remove_input (n->stages[i], position);
 285
 286   n->inputs_num--;
 287
 288   return (0);
 289 } /* int sn_network_cut_at */
 290
 291 static int sn_network_add_bitonic_merger_recursive (sn_network_t *n,
 292     int low, int num)
 293 {
 294   sn_stage_t *s;
 295   int m;
 296   int i;
 297
 298   if (num == 1)
 299     return (0);
 300
 301   s = sn_stage_create (n->stages_num);
 302   if (s == NULL)
 303     return (-1);
 304
 305   m = num / 2;
 306
 307   for (i = low; i < (low + m); i++)
 308   {
 309     sn_comparator_t c;
 310
 311     c.min = i;
 312     c.max = i + m;
 313
 314     sn_stage_comparator_add (s, &c);
 315   }
 316
 317   sn_network_stage_add (n, s);
 318
 319   sn_network_add_bitonic_merger_recursive (n, low, m);
 320   sn_network_add_bitonic_merger_recursive (n, low + m, m);
 321
 322   return (0);
 323 } /* int sn_network_add_bitonic_merger_recursive */
 324
 325 static int sn_network_add_bitonic_merger (sn_network_t *n)
 326 {
 327   sn_stage_t *s;
 328   int m;
 329   int i;
 330
 331   s = sn_stage_create (n->stages_num);
 332   if (s == NULL)
 333     return (-1);
 334
 335   m = n->inputs_num / 2;
 336
 337   for (i = 0; i < m; i++)
 338   {
 339     sn_comparator_t c;
 340
 341     c.min = i;
 342     c.max = n->inputs_num - (i + 1);
 343
 344     sn_stage_comparator_add (s, &c);
 345   }
 346
 347   sn_network_stage_add (n, s);
 348
 349   sn_network_add_bitonic_merger_recursive (n, 0, m);
 350   sn_network_add_bitonic_merger_recursive (n, m, m);
 351
 352   return (0);
 353 } /* int sn_network_add_bitonic_merger */
 354
 355 static int sn_network_add_odd_even_merger_recursive (sn_network_t *n,
 356     int *indizes, int indizes_num)
 357 {
 358   if (indizes_num > 2)
 359   {
 360     sn_comparator_t c;
 361     sn_stage_t *s;
 362     int indizes_half_num;
 363     int *indizes_half;
 364     int status;
 365     int i;
 366
 367     indizes_half_num = indizes_num / 2;
 368     indizes_half = (int *) malloc (indizes_num * sizeof (int));
 369     if (indizes_half == NULL)
 370       return (-1);
 371
 372     for (i = 0; i < indizes_half_num; i++)
 373     {
 374       indizes_half[i] = indizes[2 * i];
 375       indizes_half[indizes_half_num + i] = indizes[(2 * i) + 1];
 376     }
 377
 378     status = sn_network_add_odd_even_merger_recursive (n,
 379         indizes_half, indizes_half_num);
 380     if (status != 0)
 381     {
 382       free (indizes_half);
 383       return (status);
 384     }
 385
 386     status = sn_network_add_odd_even_merger_recursive (n,
 387         indizes_half + indizes_half_num, indizes_half_num);
 388     if (status != 0)
 389     {
 390       free (indizes_half);
 391       return (status);
 392     }
 393
 394     free (indizes_half);
 395
 396     s = sn_stage_create (n->stages_num);
 397     if (s == NULL)
 398       return (-1);
 399
 400     for (i = 1; i < (indizes_num - 2); i += 2)
 401     {
 402       c.min = indizes[i];
 403       c.max = indizes[i + 1];
 404
 405       sn_stage_comparator_add (s, &c);
 406     }
 407
 408     sn_network_stage_add (n, s);
 409   }
 410   else
 411   {
 412     sn_comparator_t c;
 413     sn_stage_t *s;
 414
 415     assert (indizes_num == 2);
 416
 417     c.min = indizes[0];
 418     c.max = indizes[1];
 419
 420     s = sn_stage_create (n->stages_num);
 421     if (s == NULL)
 422       return (-1);
 423
 424     sn_stage_comparator_add (s, &c);
 425     sn_network_stage_add (n, s);
 426   }
 427
 428   return (0);
 429 } /* int sn_network_add_odd_even_merger_recursive */
 430
 431 static int sn_network_add_odd_even_merger (sn_network_t *n)
 432 {
 433   int *indizes;
 434   int indizes_num;
 435   int status;
 436   int i;
 437
 438   indizes_num = n->inputs_num;
 439   indizes = (int *) malloc (indizes_num * sizeof (int));
 440   if (indizes == NULL)
 441     return (-1);
 442
 443   for (i = 0; i < indizes_num; i++)
 444     indizes[i] = i;
 445
 446   status = sn_network_add_odd_even_merger_recursive (n,
 447       indizes, indizes_num);
 448
 449   free (indizes);
 450   return (status);
 451 } /* int sn_network_add_bitonic_merger */
 452
 453 sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1)
 454 {
 455   sn_network_t *n;
 456   int stages_num;
 457   int i;
 458   int j;
 459
 460   stages_num = (n0->stages_num > n1->stages_num)
 461     ? n0->stages_num
 462     : n1->stages_num;
 463
 464   n = sn_network_create (n0->inputs_num + n1->inputs_num);
 465   if (n == NULL)
 466     return (NULL);
 467
 468   for (i = 0; i < stages_num; i++)
 469   {
 470     sn_stage_t *s = sn_stage_create (i);
 471
 472     if (i < n0->stages_num)
 473       for (j = 0; j < SN_STAGE_COMP_NUM (n0->stages[i]); j++)
 474       {
 475         sn_comparator_t *c = SN_STAGE_COMP_GET (n0->stages[i], j);
 476         sn_stage_comparator_add (s, c);
 477       }
 478
 479     if (i < n1->stages_num)
 480       for (j = 0; j < SN_STAGE_COMP_NUM (n1->stages[i]); j++)
 481       {
 482         sn_comparator_t *c_orig = SN_STAGE_COMP_GET (n1->stages[i], j);
 483         sn_comparator_t  c_copy;
 484
 485         SN_COMP_MIN(&c_copy) = SN_COMP_MIN(c_orig) + n0->inputs_num;
 486         SN_COMP_MAX(&c_copy) = SN_COMP_MAX(c_orig) + n0->inputs_num;
 487
 488         sn_stage_comparator_add (s, &c_copy);
 489       }
 490
 491     sn_network_stage_add (n, s);
 492   }
 493
 494   if (sn_bounded_random (0, 1) == 0)
 495   {
 496     sn_network_add_bitonic_merger (n);
 497   }
 498   else
 499   {
 500     sn_network_add_odd_even_merger (n);
 501   }
 502
 503   sn_network_compress (n);
 504
 505   return (n);
 506 } /* sn_network_t *sn_network_combine */
 507
 508 sn_network_t *sn_network_read (FILE *fh)
 509 {
 510   sn_network_t *n;
 511   char buffer[64];
 512
 513   int opt_inputs = 0;
 514
 515   while (fgets (buffer, sizeof (buffer), fh) != NULL)
 516   {
 517     char *str_key = buffer;
 518     char *str_value = NULL;
 519     int   buffer_len = strlen (buffer);
 520
 521     while ((buffer_len > 0) && ((buffer[buffer_len - 1] == '\n')
 522           || (buffer[buffer_len - 1] == '\r')))
 523     {
 524       buffer_len--;
 525       buffer[buffer_len] = '\0';
 526     }
 527     if (buffer_len == 0)
 528       break;
 529
 530     str_value = strchr (buffer, ':');
 531     if (str_value == NULL)
 532     {
 533       printf ("Cannot parse line: %s\n", buffer);
 534       continue;
 535     }
 536
 537     *str_value = '\0'; str_value++;
 538     while ((*str_value != '\0') && (isspace (*str_value) != 0))
 539       str_value++;
 540
 541     if (strcasecmp ("Inputs", str_key) == 0)
 542       opt_inputs = atoi (str_value);
 543     else
 544       printf ("Unknown key: %s\n", str_key);
 545   } /* while (fgets) */
 546
 547   if (opt_inputs < 2)
 548     return (NULL);
 549
 550   n = sn_network_create (opt_inputs);
 551
 552   while (42)
 553   {
 554     sn_stage_t *s;
 555
 556     s = sn_stage_read (fh);
 557     if (s == NULL)
 558       break;
 559
 560     sn_network_stage_add (n, s);
 561   }
 562
 563   if (SN_NETWORK_STAGE_NUM (n) < 1)
 564   {
 565     sn_network_destroy (n);
 566     return (NULL);
 567   }
 568
 569   return (n);
 570 } /* sn_network_t *sn_network_read */
 571
 572 sn_network_t *sn_network_read_file (const char *file)
 573 {
 574   sn_network_t *n;
 575   FILE *fh;
 576
 577   fh = fopen (file, "r");
 578   if (fh == NULL)
 579     return (NULL);
 580
 581   n = sn_network_read (fh);
 582
 583   fclose (fh);
 584
 585   return (n);
 586 } /* sn_network_t *sn_network_read_file */
 587
 588 int sn_network_write (sn_network_t *n, FILE *fh)
 589 {
 590   int i;
 591
 592   fprintf (fh, "Inputs: %i\n", n->inputs_num);
 593   fprintf (fh, "\n");
 594
 595   for (i = 0; i < n->stages_num; i++)
 596     sn_stage_write (n->stages[i], fh);
 597
 598   return (0);
 599 } /* int sn_network_write */
 600
 601 int sn_network_write_file (sn_network_t *n, const char *file)
 602 {
 603   int status;
 604   FILE *fh;
 605
 606   fh = fopen (file, "w");
 607   if (fh == NULL)
 608     return (-1);
 609
 610   status = sn_network_write (n, fh);
 611
 612   fclose (fh);
 613
 614   return (status);
 615 } /* int sn_network_write_file */
 616
 617 /* vim: set shiftwidth=2 softtabstop=2 : */