src/libpopulation.c

   1 /**
   2  * libevolve - src/evolve.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 /*
  23  * First tell the compiler to stick to the C99 and POSIX standards as close as
  24  * possible.
  25  */
  26 #ifndef __STRICT_ANSI__ /* {{{ */
  27 # define __STRICT_ANSI__
  28 #endif
  29
  30 #ifndef _ISOC99_SOURCE
  31 # define _ISOC99_SOURCE
  32 #endif
  33
  34 #ifdef _POSIX_C_SOURCE
  35 # undef _POSIX_C_SOURCE
  36 #endif
  37 #define _POSIX_C_SOURCE 200112L
  38
  39 /* Single UNIX needed for strdup. */
  40 #if 0
  41 #ifdef _XOPEN_SOURCE
  42 # undef _XOPEN_SOURCE
  43 #endif
  44 #define _XOPEN_SOURCE 500
  45 #endif
  46
  47 #ifndef _REENTRANT
  48 # define _REENTRANT
  49 #endif
  50
  51 #ifndef _THREAD_SAFE
  52 # define _THREAD_SAFE
  53 #endif
  54
  55 #ifdef _GNU_SOURCE
  56 # undef _GNU_SOURCE
  57 #endif
  58 /* }}} */
  59
  60 #include "config.h"
  61 #include "population.h"
  62
  63 #include <stdlib.h>
  64 #include <stdint.h>
  65 #include <inttypes.h>
  66 #include <string.h>
  67 #include <stdio.h>
  68 #include <limits.h>
  69 #include <pthread.h>
  70 #include <math.h>
  71
  72 /*
  73  * Data types
  74  */
  75 struct population_s
  76 {
  77   pthread_mutex_t lock;
  78
  79   /* Callback functions */
  80   pi_rate_f rate;
  81   pi_free_f free;
  82   pi_copy_f copy;
  83
  84   void **individuals;
  85   size_t individuals_num;
  86 };
  87
  88 /*
  89  * Constructor and destructor
  90  */
  91 population_t *population_create (pi_rate_f rate, pi_copy_f copy, /* {{{ */
  92     pi_free_f f)
  93 {
  94   population_t *p;
  95
  96   p = (population_t *) malloc (sizeof (population_t));
  97   if (p == NULL)
  98     return (NULL);
  99
 100   memset (p, 0, sizeof (*p));
 101   pthread_mutex_init (&p->lock, /* attr = */ NULL);
 102
 103   p->rate = rate;
 104   p->copy = copy;
 105   p->free = f;
 106
 107   p->individuals = (void **) malloc (32 * sizeof (void *));
 108   if (p->individuals == NULL)
 109   {
 110     free (p);
 111     return (NULL);
 112   }
 113   memset (p->individuals, 0, 32 * sizeof (void *));
 114   p->individuals_num = 32;
 115
 116   return (p);
 117 } /* }}} population_t *population_create */
 118
 119 void population_destroy (population_t *p) /* {{{ */
 120 {
 121   if (p == NULL)
 122     return;
 123
 124   if (p->individuals_num > 0)
 125   {
 126     size_t i;
 127
 128     for (i = 0; i < p->individuals_num; i++)
 129     {
 130       p->free (p->individuals[i]);
 131       p->individuals[i] = NULL;
 132     }
 133
 134     free (p->individuals);
 135     p->individuals = NULL;
 136     p->individuals_num = 0;
 137   }
 138
 139   memset (p, 0, sizeof (*p));
 140   free (p);
 141 } /* }}} void population_destroy */
 142
 143 int population_set_size (population_t *p, /* {{{ */
 144     size_t population_size)
 145 {
 146   size_t i;
 147   void **temp;
 148
 149   if (p == NULL)
 150     return (-1);
 151
 152   pthread_mutex_lock (&p->lock);
 153
 154   if (p->individuals_num == population_size)
 155   {
 156     pthread_mutex_unlock (&p->lock);
 157     return (0);
 158   }
 159
 160   for (i = population_size; i < p->individuals_num; i++)
 161   {
 162     p->free (p->individuals[i]);
 163     p->individuals[i] = NULL;
 164   }
 165
 166   temp = (void **) realloc (p->individuals, population_size * sizeof (void *));
 167   if (temp == NULL)
 168   {
 169     pthread_mutex_unlock (&p->lock);
 170     return (-1);
 171   }
 172   p->individuals = temp;
 173
 174   for (i = p->individuals_num; i < population_size; i++)
 175     p->individuals[i] = NULL;
 176
 177   p->individuals_num = population_size;
 178
 179   pthread_mutex_unlock (&p->lock);
 180
 181   return (0);
 182 } /* }}} */
 183
 184 void *population_get_random (population_t *p) /* {{{ */
 185 {
 186   void *ret = NULL;
 187   size_t i;
 188
 189   pthread_mutex_lock (&p->lock);
 190
 191   if (p->individuals_num < 1)
 192   {
 193     pthread_mutex_unlock (&p->lock);
 194     return (NULL);
 195   }
 196
 197   while (ret == NULL)
 198   {
 199     i = (size_t) (((double) p->individuals_num)
 200         * (rand() / (RAND_MAX + 1.0)));
 201     if (p->individuals[i] == NULL)
 202       continue;
 203
 204     ret = p->copy (p->individuals[i]);
 205   }
 206
 207   pthread_mutex_unlock (&p->lock);
 208
 209   return (ret);
 210 } /* }}} void *population_pick_random */
 211
 212 void *population_get_fittest (population_t *p) /* {{{ */
 213 {
 214   void *ret = NULL;
 215   int best_rating;
 216   size_t i;
 217
 218   if (p == NULL)
 219     return (NULL);
 220
 221   pthread_mutex_lock (&p->lock);
 222
 223   best_rating = INT_MAX;
 224   for (i = 0; i < p->individuals_num; i++)
 225   {
 226     int rating;
 227
 228     if (p->individuals[i] == NULL)
 229       continue;
 230
 231     rating = p->rate (p->individuals[i]);
 232     if (rating < best_rating)
 233     {
 234       void *temp;
 235
 236       temp = p->copy (p->individuals[i]);
 237       if (temp != NULL)
 238       {
 239         if (ret != NULL)
 240           p->free (ret);
 241         ret = temp;
 242         best_rating = rating;
 243       }
 244     }
 245   }
 246
 247   pthread_mutex_unlock (&p->lock);
 248
 249   return (ret);
 250 } /* }}} void *population_get_fittest */
 251
 252 int population_insert (population_t *p, void *pi_orig) /* {{{ */
 253 {
 254   void *pi;
 255   int pi_rating;
 256   int num_tries;
 257   int i;
 258
 259   if (p == NULL)
 260     return (-1);
 261
 262   if (pi_orig == NULL)
 263     return (-1);
 264
 265   pi = p->copy (pi_orig);
 266   if (pi == NULL)
 267   {
 268     fprintf (stderr, "population_insert: p->copy failed.\n");
 269     return (-1);
 270   }
 271
 272   pi_rating = p->rate (pi);
 273
 274   pthread_mutex_lock (&p->lock);
 275
 276   if (p->individuals_num <= 0)
 277   {
 278     pthread_mutex_unlock (&p->lock);
 279     p->free (pi);
 280     return (-1);
 281   }
 282
 283   num_tries = (int) ceil (log (p->individuals_num) / log (2.0));
 284   for (i = 0; i < num_tries; i++)
 285   {
 286     size_t j;
 287     int j_rating;
 288
 289     j = (size_t) (((double) p->individuals_num) * (rand() / (RAND_MAX + 1.0)));
 290
 291     if (p->individuals[j] == NULL)
 292     {
 293       p->individuals[j] = pi;
 294       pi = NULL;
 295       break;
 296     }
 297
 298     j_rating = p->rate (p->individuals[j]);
 299
 300     if (pi_rating < j_rating)
 301     {
 302       void *temp;
 303
 304       temp = p->individuals[j];
 305       p->individuals[j] = pi;
 306       pi = temp;
 307
 308       pi_rating = j_rating;
 309     }
 310   }
 311
 312   pthread_mutex_unlock (&p->lock);
 313
 314   if (pi != NULL)
 315   {
 316     p->free (pi);
 317     pi = NULL;
 318   }
 319
 320   return (0);
 321 } /* }}} int population_insert */
 322
 323 /* vim: set sw=2 sts=2 et fdm=marker : */
 324