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 <errno.h>
  65 #include <stdint.h>
  66 #include <inttypes.h>
  67 #include <string.h>
  68 #include <stdio.h>
  69 #include <limits.h>
  70 #include <pthread.h>
  71 #include <math.h>
  72 #include <unistd.h>
  73 #include <fcntl.h>
  74 #include <sys/types.h>
  75 #include <sys/socket.h>
  76 #include <netdb.h>
  77
  78 /*
  79  * Data types
  80  */
  81 struct individual_s
  82 {
  83   void *ptr;
  84   int rating;
  85 };
  86 typedef struct individual_s individual_t;
  87
  88 struct population_s
  89 {
  90   pthread_mutex_t lock;
  91
  92   /* Callback functions */
  93   pi_rate_f rate;
  94   pi_free_f free;
  95   pi_copy_f copy;
  96
  97   /* Optional serialization */
  98   pi_serialize_f serialize;
  99   pi_unserialize_f unserialize;
 100
 101   int *peers;
 102   size_t peers_num;
 103
 104   individual_t fittest;
 105
 106   individual_t *individuals;
 107   size_t individuals_num;
 108 };
 109
 110 /*
 111  * Private functions
 112  */
 113 static int population_send_to_peer (population_t *p, void *pi) /* {{{ */
 114 {
 115   char buffer[1450];
 116   size_t buffer_size;
 117   size_t buffer_free;
 118   char *buffer_ptr;
 119
 120   int fd;
 121   int i;
 122   int status;
 123
 124   if (p == NULL)
 125     return (-1);
 126
 127   if (pi == NULL)
 128     return (-1);
 129
 130   buffer_size = sizeof (buffer);
 131   memset (buffer, 0, buffer_size);
 132
 133   pthread_mutex_lock (&p->lock);
 134
 135   if (p->serialize == NULL)
 136   {
 137     pthread_mutex_unlock (&p->lock);
 138     fprintf (stderr, "population_send_to_peer: Cannot send to peer without "
 139         "serialization function!\n");
 140     return (-1);
 141   }
 142
 143   i = (int) (((double) p->peers_num) * (rand() / (RAND_MAX + 1.0)));
 144   fd = p->peers[i];
 145
 146   buffer_ptr = buffer;
 147   buffer_free = sizeof (buffer);
 148   status = p->serialize (pi, &buffer_ptr, &buffer_free);
 149   if (status != 0)
 150   {
 151     pthread_mutex_unlock (&p->lock);
 152     fprintf (stderr, "population_send_to_peer: p->serialize failed "
 153         "with status %i.\n", status);
 154     return (-1);
 155   }
 156
 157   buffer_size = sizeof (buffer) - buffer_free;
 158   if (buffer_size < 1)
 159   {
 160     pthread_mutex_unlock (&p->lock);
 161     fprintf (stderr, "population_send_to_peer: p->serialize didn't put "
 162         "anything into the buffer..\n");
 163     return (-1);
 164   }
 165
 166   /* write should not block - hopefully */
 167   status = send (fd, buffer, buffer_size, MSG_DONTWAIT | MSG_NOSIGNAL);
 168   if (status < 0)
 169   {
 170     pthread_mutex_unlock (&p->lock);
 171     status = errno;
 172     if (status != ECONNREFUSED)
 173     {
 174       fprintf (stderr, "population_send_to_peer: Writing to socket failed: "
 175           "send(2) returned with error %i.\n", status);
 176     }
 177     return (-1);
 178   }
 179   else if (((size_t) status) != buffer_size)
 180   {
 181     pthread_mutex_unlock (&p->lock);
 182     fprintf (stderr, "population_send_to_peer: Writing to socket failed: "
 183         "send(2) returned %i (expected %zu).\n",
 184         status, buffer_size);
 185     return (-1);
 186   }
 187
 188   pthread_mutex_unlock (&p->lock);
 189   return (0);
 190 } /* }}} int population_send_to_peer */
 191
 192 /*
 193  * Constructor and destructor
 194  */
 195 population_t *population_create (pi_rate_f rate, pi_copy_f copy, /* {{{ */
 196     pi_free_f f)
 197 {
 198   population_t *p;
 199   size_t i;
 200
 201   p = (population_t *) malloc (sizeof (population_t));
 202   if (p == NULL)
 203     return (NULL);
 204
 205   memset (p, 0, sizeof (*p));
 206   pthread_mutex_init (&p->lock, /* attr = */ NULL);
 207
 208   p->rate = rate;
 209   p->copy = copy;
 210   p->free = f;
 211
 212   p->fittest.ptr = NULL;
 213   p->fittest.rating = -1;
 214
 215   p->individuals = malloc (32 * sizeof (p->individuals[0]));
 216   if (p->individuals == NULL)
 217   {
 218     free (p);
 219     return (NULL);
 220   }
 221   memset (p->individuals, 0, 32 * sizeof (p->individuals[0]));
 222   p->individuals_num = 32;
 223
 224   for (i = 0; i < p->individuals_num; i++)
 225   {
 226     p->individuals[i].ptr = NULL;
 227     p->individuals[i].rating = -1;
 228   }
 229
 230   return (p);
 231 } /* }}} population_t *population_create */
 232
 233 void population_destroy (population_t *p) /* {{{ */
 234 {
 235   if (p == NULL)
 236     return;
 237
 238   if (p->fittest.ptr != NULL)
 239     p->free (p->fittest.ptr);
 240   p->fittest.ptr = NULL;
 241   p->fittest.rating = -1;
 242
 243   if (p->individuals_num > 0)
 244   {
 245     size_t i;
 246
 247     for (i = 0; i < p->individuals_num; i++)
 248     {
 249       if (p->individuals[i].ptr != NULL)
 250         p->free (p->individuals[i].ptr);
 251       p->individuals[i].ptr = NULL;
 252       p->individuals[i].rating = -1;
 253     }
 254
 255     free (p->individuals);
 256     p->individuals = NULL;
 257     p->individuals_num = 0;
 258   }
 259
 260   memset (p, 0, sizeof (*p));
 261   free (p);
 262 } /* }}} void population_destroy */
 263
 264 int population_set_size (population_t *p, /* {{{ */
 265     size_t population_size)
 266 {
 267   size_t i;
 268   individual_t *temp;
 269
 270   if (p == NULL)
 271     return (-1);
 272
 273   pthread_mutex_lock (&p->lock);
 274
 275   if (p->individuals_num == population_size)
 276   {
 277     pthread_mutex_unlock (&p->lock);
 278     return (0);
 279   }
 280
 281   for (i = population_size; i < p->individuals_num; i++)
 282   {
 283     p->free (p->individuals[i].ptr);
 284     p->individuals[i].ptr = NULL;
 285     p->individuals[i].rating = -1;
 286   }
 287
 288   temp = (individual_t *) realloc (p->individuals,
 289       population_size * sizeof (p->individuals[0]));
 290   if (temp == NULL)
 291   {
 292     pthread_mutex_unlock (&p->lock);
 293     return (-1);
 294   }
 295   p->individuals = temp;
 296
 297   for (i = p->individuals_num; i < population_size; i++)
 298   {
 299     p->individuals[i].ptr = NULL;
 300     p->individuals[i].rating = -1;
 301   }
 302
 303   p->individuals_num = population_size;
 304
 305   pthread_mutex_unlock (&p->lock);
 306
 307   return (0);
 308 } /* }}} */
 309
 310 int population_set_serialization (population_t *p,
 311     pi_serialize_f serialize, pi_unserialize_f unserialize) /* {{{ */
 312 {
 313   if (p == NULL)
 314     return (-1);
 315
 316   pthread_mutex_lock (&p->lock);
 317
 318   p->serialize = serialize;
 319   p->unserialize = unserialize;
 320
 321   pthread_mutex_unlock (&p->lock);
 322   return (0);
 323 } /* }}} int population_set_serialization */
 324
 325 int population_add_peer (population_t *p, const char *node, /* {{{ */
 326     const char *port)
 327 {
 328   struct addrinfo  ai_hints;
 329   struct addrinfo *ai_list;
 330   struct addrinfo *ai_ptr;
 331   int status;
 332
 333   if (p == NULL)
 334     return (-1);
 335
 336   if (node == NULL)
 337     return (-1);
 338
 339   if (port == NULL)
 340     port = POPULATION_DEFAULT_PORT;
 341
 342   ai_list = NULL;
 343
 344   memset (&ai_hints, 0, sizeof (ai_hints));
 345   ai_hints.ai_flags = 0;
 346 #ifdef AI_ADDRCONFIG
 347   ai_hints.ai_flags |= AI_ADDRCONFIG;
 348 #endif
 349   ai_hints.ai_family = AF_UNSPEC;
 350   ai_hints.ai_socktype = SOCK_DGRAM;
 351   ai_hints.ai_protocol = 0;
 352
 353   status = getaddrinfo (node, port, &ai_hints, &ai_list);
 354   if (status != 0)
 355   {
 356     fprintf (stderr, "population_add_peer: getaddrinfo (%s) failed: %s\n",
 357         node, gai_strerror (status));
 358     return (-1);
 359   }
 360
 361   pthread_mutex_lock (&p->lock);
 362
 363   for (ai_ptr = ai_list; ai_ptr != NULL; ai_ptr = ai_ptr->ai_next)
 364   {
 365     int *temp;
 366
 367     temp = (int *) realloc (p->peers, sizeof (int) * (p->peers_num + 1));
 368     if (temp == NULL)
 369     {
 370       fprintf (stderr, "population_add_peer: realloc failed.\n");
 371       continue;
 372     }
 373     p->peers = temp;
 374
 375     p->peers[p->peers_num] = socket (ai_ptr->ai_family, ai_ptr->ai_socktype,
 376         ai_ptr->ai_protocol);
 377     if (p->peers[p->peers_num] < 0)
 378       continue;
 379
 380     status = connect (p->peers[p->peers_num],
 381         ai_ptr->ai_addr, ai_ptr->ai_addrlen);
 382     if (status != 0)
 383     {
 384       fprintf (stderr, "population_add_peer: connect(2) failed.\n");
 385       close (p->peers[p->peers_num]);
 386       continue;
 387     }
 388
 389     status = fcntl (p->peers[p->peers_num], F_SETFL, O_NONBLOCK);
 390     if (status != 0)
 391     {
 392       fprintf (stderr, "population_add_peer: fcntl (F_SETFL, O_NONBLOCK) "
 393           "failed. Will use the socket with blocking.\n");
 394     }
 395
 396     p->peers_num++;
 397   }
 398   pthread_mutex_unlock (&p->lock);
 399
 400   freeaddrinfo (ai_list);
 401
 402   return (0);
 403 } /* }}} int population_add_peer */
 404
 405 void *population_get_random (population_t *p) /* {{{ */
 406 {
 407   void *ret = NULL;
 408   size_t i;
 409
 410   pthread_mutex_lock (&p->lock);
 411
 412   if (p->individuals_num < 1)
 413   {
 414     pthread_mutex_unlock (&p->lock);
 415     return (NULL);
 416   }
 417
 418   while (ret == NULL)
 419   {
 420     i = (size_t) (((double) p->individuals_num)
 421         * (rand() / (RAND_MAX + 1.0)));
 422     if (p->individuals[i].ptr == NULL)
 423       continue;
 424
 425     ret = p->copy (p->individuals[i].ptr);
 426   }
 427
 428   pthread_mutex_unlock (&p->lock);
 429
 430   return (ret);
 431 } /* }}} void *population_pick_random */
 432
 433 void *population_get_fittest (population_t *p) /* {{{ */
 434 {
 435   void *ret = NULL;
 436
 437   if (p == NULL)
 438     return (NULL);
 439
 440   pthread_mutex_lock (&p->lock);
 441
 442   if (p->fittest.ptr == NULL)
 443   {
 444     pthread_mutex_unlock (&p->lock);
 445     return (NULL);
 446   }
 447
 448   ret = p->copy (p->fittest.ptr);
 449
 450   pthread_mutex_unlock (&p->lock);
 451
 452   return (ret);
 453 } /* }}} void *population_get_fittest */
 454
 455 int population_insert (population_t *p, void *pi_orig) /* {{{ */
 456 {
 457   void *pi;
 458   int pi_rating;
 459   int num_tries;
 460   int i;
 461
 462   if (p == NULL)
 463     return (-1);
 464
 465   if (pi_orig == NULL)
 466     return (-1);
 467
 468   pi = p->copy (pi_orig);
 469   if (pi == NULL)
 470   {
 471     fprintf (stderr, "population_insert: p->copy failed.\n");
 472     return (-1);
 473   }
 474
 475   pi_rating = p->rate (pi);
 476
 477   pthread_mutex_lock (&p->lock);
 478
 479   if (p->peers_num > 0)
 480   {
 481     double prob;
 482
 483     prob = ((double) rand ()) / (((double) RAND_MAX) + 1.0);
 484     if (prob < 0.01)
 485     {
 486       pthread_mutex_unlock (&p->lock);
 487       population_send_to_peer (p, pi);
 488       pthread_mutex_lock (&p->lock);
 489     }
 490   }
 491
 492   /* Keep track of the all time best. */
 493   if ((p->fittest.ptr == NULL) || (p->fittest.rating > pi_rating))
 494   {
 495     void *temp;
 496
 497     temp = p->copy (pi);
 498     if (temp != NULL)
 499     {
 500       if (p->fittest.ptr != NULL)
 501         p->free (p->fittest.ptr);
 502       p->fittest.ptr = temp;
 503       p->fittest.rating = pi_rating;
 504     }
 505   }
 506
 507   if (p->individuals_num <= 0)
 508   {
 509     pthread_mutex_unlock (&p->lock);
 510     p->free (pi);
 511     return (-1);
 512   }
 513
 514   do
 515   {
 516     size_t j;
 517
 518     int chance_j;
 519     int chance_pi;
 520     int chance;
 521
 522     j = (size_t) (((double) p->individuals_num) * (rand() / (RAND_MAX + 1.0)));
 523
 524     if (p->individuals[j].ptr == NULL)
 525     {
 526       p->individuals[j].ptr = pi;
 527       p->individuals[j].rating = pi_rating;
 528       pi = NULL;
 529       break;
 530     }
 531
 532     /* large distance from fittest => high probability of losing. */
 533     chance_j = 1 + p->individuals[j].rating - p->fittest.rating;
 534     chance_pi = 1 + pi_rating - p->fittest.rating;
 535
 536     chance = (int) (((double) (chance_j + chance_pi))
 537         * (rand() / (RAND_MAX + 1.0)));
 538     if (chance < chance_j) /* j looses ;) */
 539     {
 540       void *temp0;
 541       int temp1;
 542
 543       temp0 = p->individuals[j].ptr;
 544       p->individuals[j].ptr = pi;
 545       pi = temp0;
 546
 547       temp1 = p->individuals[j].rating;
 548       p->individuals[j].rating = pi_rating;
 549       pi_rating = temp1;
 550     }
 551   } while (0);
 552
 553   pthread_mutex_unlock (&p->lock);
 554
 555   if (pi != NULL)
 556   {
 557     p->free (pi);
 558     pi = NULL;
 559   }
 560
 561   return (0);
 562 } /* }}} int population_insert */
 563
 564 /* vim: set sw=2 sts=2 et fdm=marker : */
 565