Merge branch 'ff/libpopulation'
[sort-networks.git] / 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 : */