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 #define _ISOC99_SOURCE
  23 #define _POSIX_C_SOURCE 200112L
  24
  25 #include <stdlib.h>
  26 #include <stdio.h>
  27 #include <stdint.h>
  28 #include <string.h>
  29 #include <assert.h>
  30 #include <pthread.h>
  31
  32 #include "sn_population.h"
  33 #include "sn_network.h"
  34 #include "sn_random.h"
  35
  36 struct sn_population_s
  37 {
  38   uint32_t size;
  39
  40   sn_network_t **networks;
  41   int *ratings;
  42   uint32_t networks_num;
  43
  44   pthread_mutex_t lock;
  45 };
  46
  47 static int rate_network (const sn_network_t *n)
  48 {
  49   int rate;
  50   int i;
  51
  52   rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
  53   for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
  54   {
  55     sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
  56     rate += SN_STAGE_COMP_NUM (s);
  57   }
  58
  59   return (rate);
  60 } /* int rate_network */
  61
  62 sn_population_t *sn_population_create (uint32_t size)
  63 {
  64   sn_population_t *p;
  65   int status;
  66
  67   p = (sn_population_t *) malloc (sizeof (sn_population_t));
  68   if (p == NULL)
  69     return (NULL);
  70   memset (p, 0, sizeof (sn_population_t));
  71   p->size = size;
  72
  73   p->networks = (sn_network_t **) calloc ((size_t) size,
  74       sizeof (sn_network_t *));
  75   if (p->networks == NULL)
  76   {
  77     free (p);
  78     return (NULL);
  79   }
  80
  81   p->ratings = (int *) calloc ((size_t) size, sizeof (int));
  82   if (p->ratings == NULL)
  83   {
  84     free (p->networks);
  85     free (p);
  86     return (NULL);
  87   }
  88
  89   status = pthread_mutex_init (&p->lock, /* attr = */ NULL);
  90   if (status != 0)
  91   {
  92     fprintf (stderr, "sn_population_create: pthread_mutex_init failed: %i\n",
  93         status);
  94     free (p->ratings);
  95     free (p->networks);
  96     free (p);
  97     return (NULL);
  98   }
  99
 100   return (p);
 101 } /* sn_population_t *sn_population_create */
 102
 103 void sn_population_destroy (sn_population_t *p)
 104 {
 105   uint32_t i;
 106
 107   if (p == NULL)
 108     return;
 109
 110   for (i = 0; i < p->size; i++)
 111     if (p->networks[i] != NULL)
 112       sn_network_destroy (p->networks[i]);
 113
 114   pthread_mutex_destroy (&p->lock);
 115
 116   free (p->ratings);
 117   free (p->networks);
 118   free (p);
 119 } /* void sn_population_destroy */
 120
 121 int sn_population_push (sn_population_t *p, sn_network_t *n)
 122 {
 123   sn_network_t *n_copy;
 124   int rating;
 125
 126   n_copy = sn_network_clone (n);
 127   if (n_copy == NULL)
 128   {
 129     fprintf (stderr, "sn_population_push: sn_network_clone failed.\n");
 130     return (-1);
 131   }
 132
 133   rating = rate_network (n_copy);
 134
 135   pthread_mutex_lock (&p->lock);
 136
 137   if (p->networks_num < p->size)
 138   {
 139     p->networks[p->networks_num] = n_copy;
 140     p->ratings[p->networks_num] = rating;
 141     p->networks_num++;
 142   }
 143   else
 144   {
 145     int index;
 146     sn_network_t *n_removed = n_copy;
 147     int i;
 148
 149     for (i = 0; i < (1 + (p->networks_num / 16)); i++)
 150     {
 151       index = sn_bounded_random (0, p->networks_num - 1);
 152       if (p->ratings[index] < rating)
 153         continue;
 154
 155       n_removed = p->networks[index];
 156       p->networks[index] = n_copy;
 157       p->ratings[index] = rating;
 158       break;
 159     }
 160
 161     sn_network_destroy (n_removed);
 162   }
 163
 164   pthread_mutex_unlock (&p->lock);
 165
 166   return (0);
 167 } /* int sn_population_push */
 168
 169 sn_network_t *sn_population_pop (sn_population_t *p)
 170 {
 171   int index;
 172   sn_network_t *n_copy;
 173
 174   pthread_mutex_lock (&p->lock);
 175
 176   if (p->networks_num <= 0)
 177   {
 178     pthread_mutex_unlock (&p->lock);
 179     return (NULL);
 180   }
 181
 182   index = sn_bounded_random (0, p->networks_num - 1);
 183   n_copy = sn_network_clone (p->networks[index]);
 184
 185   pthread_mutex_unlock (&p->lock);
 186
 187   return (n_copy);
 188 } /* sn_population_t *sn_population_pop */
 189
 190 sn_network_t *sn_population_best (sn_population_t *p)
 191 {
 192   uint32_t i;
 193
 194   uint32_t index = 0;
 195   int rating = -1;
 196   sn_network_t *n_copy;
 197
 198   if (p == NULL)
 199     return (NULL);
 200
 201   pthread_mutex_lock (&p->lock);
 202
 203   if (p->networks_num <= 0)
 204   {
 205     pthread_mutex_unlock (&p->lock);
 206     return (NULL);
 207   }
 208
 209   for (i = 0; i < p->networks_num; i++)
 210   {
 211     if ((p->ratings[i] < rating) || (rating < 0))
 212     {
 213       rating = p->ratings[i];
 214       index = i;
 215     }
 216   }
 217
 218   n_copy = sn_network_clone (p->networks[index]);
 219
 220   pthread_mutex_unlock (&p->lock);
 221
 222   return (n_copy);
 223 } /* sn_network_t *sn_population_best */
 224
 225 int sn_population_best_rating (sn_population_t *p)
 226 {
 227   uint32_t i;
 228   int rating = -1;
 229
 230   pthread_mutex_lock (&p->lock);
 231
 232   if (p->networks_num <= 0)
 233   {
 234     pthread_mutex_unlock (&p->lock);
 235     return (-1);
 236   }
 237
 238   for (i = 0; i < p->networks_num; i++)
 239     if ((p->ratings[i] < rating) || (rating < 0))
 240       rating = p->ratings[i];
 241
 242   pthread_mutex_unlock (&p->lock);
 243
 244   return (rating);
 245 } /* int sn_population_best_rating */
 246
 247 /* vim: set shiftwidth=2 softtabstop=2 : */