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