src/sn_population.c

   1 /**
   2  * collectd - src/sn_population.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 <stdint.h>
  32 #include <string.h>
  33 #include <assert.h>
  34 #include <pthread.h>
  35
  36 #include "sn_population.h"
  37 #include "sn_network.h"
  38 #include "sn_random.h"
  39
  40 struct sn_population_s
  41 {
  42   uint32_t size;
  43
  44   sn_network_t *best_network;
  45   int best_rating;
  46
  47   sn_network_t **networks;
  48   int *ratings;
  49   uint32_t networks_num;
  50
  51   pthread_mutex_t lock;
  52 };
  53
  54 static int rate_network (const sn_network_t *n)
  55 {
  56   int rate;
  57   int i;
  58
  59   rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
  60   for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
  61   {
  62     sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
  63     rate += SN_STAGE_COMP_NUM (s);
  64   }
  65
  66   return (rate);
  67 } /* int rate_network */
  68
  69 static int brute_force_minimize (sn_network_t *n_orig)
  70 {
  71   int stage_index;
  72   int comparator_index;
  73
  74   printf ("brute_force_minimize: Running full fledged brute force optimization.\n");
  75
  76   for (stage_index = 0;
  77       stage_index < SN_NETWORK_STAGE_NUM (n_orig);
  78       stage_index++)
  79   {
  80     sn_stage_t *s_orig;
  81
  82     s_orig = SN_NETWORK_STAGE_GET (n_orig, stage_index);
  83
  84     for (comparator_index = 0;
  85         comparator_index < SN_STAGE_COMP_NUM (s_orig);
  86         comparator_index++)
  87     {
  88       sn_network_t *n_copy;
  89       sn_stage_t *s_copy;
  90       int status;
  91
  92       n_copy = sn_network_clone (n_orig);
  93       if (n_copy == NULL)
  94         continue;
  95
  96       s_copy = SN_NETWORK_STAGE_GET (n_copy, stage_index);
  97       sn_stage_comparator_remove (s_copy, comparator_index);
  98
  99       status = sn_network_brute_force_check (n_copy);
 100       if (status == 0)
 101       {
 102         printf ("brute_force_minimize: Removed a comparator "
 103             "(stage %i, comparator %i).\n",
 104             stage_index, comparator_index);
 105         sn_stage_comparator_remove (s_orig, comparator_index);
 106
 107         comparator_index--;
 108       }
 109
 110       sn_network_destroy (n_copy);
 111       n_copy = NULL;
 112     } /* for (comparator_index) */
 113   } /* for (stage_index) */
 114
 115   /* FIXME: Remove this check after debugging. */
 116   assert (sn_network_brute_force_check (n_orig) == 0);
 117
 118   return (0);
 119 } /* int brute_force_minimize */
 120
 121 sn_population_t *sn_population_create (uint32_t size)
 122 {
 123   sn_population_t *p;
 124   int status;
 125
 126   p = (sn_population_t *) malloc (sizeof (sn_population_t));
 127   if (p == NULL)
 128     return (NULL);
 129   memset (p, 0, sizeof (sn_population_t));
 130   p->size = size;
 131
 132   p->networks = (sn_network_t **) calloc ((size_t) size,
 133       sizeof (sn_network_t *));
 134   if (p->networks == NULL)
 135   {
 136     free (p);
 137     return (NULL);
 138   }
 139
 140   p->ratings = (int *) calloc ((size_t) size, sizeof (int));
 141   if (p->ratings == NULL)
 142   {
 143     free (p->networks);
 144     free (p);
 145     return (NULL);
 146   }
 147
 148   status = pthread_mutex_init (&p->lock, /* attr = */ NULL);
 149   if (status != 0)
 150   {
 151     fprintf (stderr, "sn_population_create: pthread_mutex_init failed: %i\n",
 152         status);
 153     free (p->ratings);
 154     free (p->networks);
 155     free (p);
 156     return (NULL);
 157   }
 158
 159   return (p);
 160 } /* sn_population_t *sn_population_create */
 161
 162 void sn_population_destroy (sn_population_t *p)
 163 {
 164   uint32_t i;
 165
 166   if (p == NULL)
 167     return;
 168
 169   for (i = 0; i < p->size; i++)
 170     if (p->networks[i] != NULL)
 171       sn_network_destroy (p->networks[i]);
 172
 173   pthread_mutex_destroy (&p->lock);
 174
 175   free (p->ratings);
 176   free (p->networks);
 177   free (p);
 178 } /* void sn_population_destroy */
 179
 180 int sn_population_push (sn_population_t *p, sn_network_t *n)
 181 {
 182   sn_network_t *n_copy;
 183   int rating;
 184
 185   n_copy = sn_network_clone (n);
 186   if (n_copy == NULL)
 187   {
 188     fprintf (stderr, "sn_population_push: sn_network_clone failed.\n");
 189     return (-1);
 190   }
 191
 192   rating = rate_network (n_copy);
 193
 194   pthread_mutex_lock (&p->lock);
 195
 196   if (p->best_rating >= rating)
 197   {
 198     pthread_mutex_unlock (&p->lock);
 199
 200     brute_force_minimize (n_copy);
 201     rating = rate_network (n_copy);
 202
 203     pthread_mutex_lock (&p->lock);
 204   }
 205
 206   if ((p->best_rating >= rating)
 207       || (p->best_network == NULL))
 208   {
 209     sn_network_t *n_copy_best;
 210
 211     n_copy_best = sn_network_clone (n);
 212     if (n_copy_best != NULL)
 213     {
 214       if (p->best_network != NULL)
 215         sn_network_destroy (p->best_network);
 216       p->best_network = n_copy_best;
 217       p->best_rating = rating;
 218     }
 219   }
 220
 221   if (p->networks_num < p->size)
 222   {
 223     p->networks[p->networks_num] = n_copy;
 224     p->ratings[p->networks_num] = rating;
 225     p->networks_num++;
 226   }
 227   else
 228   {
 229     int index;
 230     sn_network_t *n_removed = n_copy;
 231     int i;
 232
 233     for (i = 0; i < (1 + (p->networks_num / 16)); i++)
 234     {
 235       index = sn_bounded_random (0, p->networks_num - 1);
 236       if (p->ratings[index] < rating)
 237         continue;
 238
 239       n_removed = p->networks[index];
 240       p->networks[index] = n_copy;
 241       p->ratings[index] = rating;
 242       break;
 243     }
 244
 245     sn_network_destroy (n_removed);
 246   }
 247
 248   pthread_mutex_unlock (&p->lock);
 249
 250   return (0);
 251 } /* int sn_population_push */
 252
 253 sn_network_t *sn_population_pop (sn_population_t *p)
 254 {
 255   int index;
 256   sn_network_t *n_copy;
 257
 258   pthread_mutex_lock (&p->lock);
 259
 260   if (p->networks_num <= 0)
 261   {
 262     pthread_mutex_unlock (&p->lock);
 263     return (NULL);
 264   }
 265
 266   index = sn_bounded_random (0, p->networks_num - 1);
 267   n_copy = sn_network_clone (p->networks[index]);
 268
 269   pthread_mutex_unlock (&p->lock);
 270
 271   return (n_copy);
 272 } /* sn_population_t *sn_population_pop */
 273
 274 sn_network_t *sn_population_best (sn_population_t *p)
 275 {
 276   uint32_t i;
 277
 278   uint32_t index = 0;
 279   int rating = -1;
 280   sn_network_t *n_copy;
 281
 282   if (p == NULL)
 283     return (NULL);
 284
 285   pthread_mutex_lock (&p->lock);
 286
 287   if (p->networks_num <= 0)
 288   {
 289     pthread_mutex_unlock (&p->lock);
 290     return (NULL);
 291   }
 292
 293   for (i = 0; i < p->networks_num; i++)
 294   {
 295     if ((p->ratings[i] < rating) || (rating < 0))
 296     {
 297       rating = p->ratings[i];
 298       index = i;
 299     }
 300   }
 301
 302   n_copy = sn_network_clone (p->networks[index]);
 303
 304   pthread_mutex_unlock (&p->lock);
 305
 306   return (n_copy);
 307 } /* sn_network_t *sn_population_best */
 308
 309 int sn_population_best_rating (sn_population_t *p)
 310 {
 311   uint32_t i;
 312   int rating = -1;
 313
 314   pthread_mutex_lock (&p->lock);
 315
 316   if (p->networks_num <= 0)
 317   {
 318     pthread_mutex_unlock (&p->lock);
 319     return (-1);
 320   }
 321
 322   for (i = 0; i < p->networks_num; i++)
 323     if ((p->ratings[i] < rating) || (rating < 0))
 324       rating = p->ratings[i];
 325
 326   pthread_mutex_unlock (&p->lock);
 327
 328   return (rating);
 329 } /* int sn_population_best_rating */
 330
 331 /* vim: set shiftwidth=2 softtabstop=2 : */