2 * libpopulation - src/evolve.c
3 * Copyright (C) 2008,2009 Florian octo Forster
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.
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.
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
19 * Florian octo Forster <octo at verplant.org>
23 * First tell the compiler to stick to the C99 and POSIX standards as close as
26 #ifndef __STRICT_ANSI__ /* {{{ */
27 # define __STRICT_ANSI__
30 #ifndef _ISOC99_SOURCE
31 # define _ISOC99_SOURCE
34 #ifdef _POSIX_C_SOURCE
35 # undef _POSIX_C_SOURCE
37 #define _POSIX_C_SOURCE 200112L
39 /* Single UNIX needed for strdup. */
44 #define _XOPEN_SOURCE 500
61 #include "population.h"
75 #include <sys/types.h>
76 #include <sys/socket.h>
80 #define NETWORK_BUFFER_SIZE 1450
90 typedef struct individual_s individual_t;
96 /* Callback functions */
101 /* Optional serialization */
102 pi_serialize_f serialize;
103 pi_unserialize_f unserialize;
108 #define POPULATION_FLAG_LISTEN 0x01
109 #define POPULATION_FLAG_SHUTDOWN 0x02
111 pthread_t listen_thread_id;
113 individual_t fittest;
115 individual_t *individuals;
116 size_t individuals_num;
119 struct listen_thread_args_s
121 population_t *population;
125 typedef struct listen_thread_args_s listen_thread_args_t;
130 static char *population_strdup (const char *src)
138 s = strlen (src) + 1;
139 ret = (char *) malloc (s);
143 memcpy (ret, src, s);
145 } /* char *population_strdup */
147 static int population_send_to_peer (population_t *p, void *pi) /* {{{ */
149 char buffer[NETWORK_BUFFER_SIZE];
164 buffer_size = sizeof (buffer);
165 memset (buffer, 0, buffer_size);
167 pthread_mutex_lock (&p->lock);
169 if (p->serialize == NULL)
171 pthread_mutex_unlock (&p->lock);
172 fprintf (stderr, "population_send_to_peer: Cannot send to peer without "
173 "serialization function!\n");
177 i = (int) (((double) p->peers_num) * (rand() / (RAND_MAX + 1.0)));
181 buffer_free = sizeof (buffer);
182 status = p->serialize (pi, &buffer_ptr, &buffer_free);
185 pthread_mutex_unlock (&p->lock);
186 fprintf (stderr, "population_send_to_peer: p->serialize failed "
187 "with status %i.\n", status);
191 buffer_size = sizeof (buffer) - buffer_free;
194 pthread_mutex_unlock (&p->lock);
195 fprintf (stderr, "population_send_to_peer: p->serialize didn't put "
196 "anything into the buffer..\n");
200 /* write should not block - hopefully */
201 status = send (fd, buffer, buffer_size, MSG_DONTWAIT | MSG_NOSIGNAL);
204 pthread_mutex_unlock (&p->lock);
206 if (status != ECONNREFUSED)
208 fprintf (stderr, "population_send_to_peer: Writing to socket failed: "
209 "send(2) returned with error %i.\n", status);
213 else if (((size_t) status) != buffer_size)
215 pthread_mutex_unlock (&p->lock);
216 fprintf (stderr, "population_send_to_peer: Writing to socket failed: "
217 "send(2) returned %i (expected %zu).\n",
218 status, buffer_size);
222 pthread_mutex_unlock (&p->lock);
225 printf ("population_send_to_peer: Sent individual with rating %i to peer #%i.\n",
230 } /* }}} int population_send_to_peer */
232 static void *listen_thread (void *data)
234 listen_thread_args_t *args;
241 struct addrinfo ai_hints;
242 struct addrinfo *ai_list;
243 struct addrinfo *ai_ptr;
245 args = (listen_thread_args_t *) data;
246 p = args->population;
248 service = args->service;
252 memset (&ai_hints, 0, sizeof (ai_hints));
253 ai_hints.ai_flags = AI_PASSIVE;
255 ai_hints.ai_flags |= AI_ADDRCONFIG;
257 ai_hints.ai_family = AF_UNSPEC;
258 ai_hints.ai_socktype = SOCK_DGRAM;
259 ai_hints.ai_protocol = 0;
261 status = getaddrinfo (node,
262 (service != NULL) ? service : POPULATION_DEFAULT_PORT,
263 &ai_hints, &ai_list);
266 fprintf (stderr, "listen_thread: getaddrinfo (%s) failed: %s\n",
267 (node != NULL) ? node : "NULL", gai_strerror (status));
268 return ((void *) -1);
272 for (ai_ptr = ai_list; ai_ptr != NULL; ai_ptr = ai_ptr->ai_next)
274 fd = socket (ai_ptr->ai_family, ai_ptr->ai_socktype, ai_ptr->ai_protocol);
278 status = bind (fd, ai_ptr->ai_addr, ai_ptr->ai_addrlen);
289 freeaddrinfo (ai_list);
293 fprintf (stderr, "listen_thread: No socket could be opened.\n");
294 return ((void *) -1);
297 pthread_mutex_lock (&p->lock);
298 p->flags |= POPULATION_FLAG_LISTEN;
299 while ((p->flags & POPULATION_FLAG_SHUTDOWN) == 0)
301 /* Allocate one extra byte to null-terminate the data. */
302 char buffer[NETWORK_BUFFER_SIZE + 1];
305 pthread_mutex_unlock (&p->lock);
307 status = recvfrom (fd, buffer, sizeof (buffer) - 1, /* flags = */ 0,
308 /* from = */ NULL, /* fromlen = */ NULL);
311 fprintf (stderr, "listen_thread: recvfrom(2) failed: status = %i; "
312 "errno = %i;\n", status, errno);
313 pthread_mutex_lock (&p->lock);
316 assert (status < sizeof (buffer));
317 buffer[sizeof (buffer) - 1] = 0;
319 pi = p->unserialize (buffer, (size_t) status);
322 fprintf (stderr, "listen_thread: p->unserialize returned NULL.\n");
323 pthread_mutex_lock (&p->lock);
328 printf ("listen_thread: Received individual with rating %i.\n",
332 population_insert (p, pi);
336 pthread_mutex_lock (&p->lock);
342 /* clear the listen flag */
343 p->flags &= ~(POPULATION_FLAG_LISTEN);
345 pthread_mutex_unlock (&p->lock);
347 } /* void *listen_thread */
350 * Constructor and destructor
352 population_t *population_create (pi_rate_f rate, pi_copy_f copy, /* {{{ */
358 p = (population_t *) malloc (sizeof (population_t));
362 memset (p, 0, sizeof (*p));
363 pthread_mutex_init (&p->lock, /* attr = */ NULL);
369 p->fittest.ptr = NULL;
370 p->fittest.rating = -1;
372 p->individuals = malloc (32 * sizeof (p->individuals[0]));
373 if (p->individuals == NULL)
378 memset (p->individuals, 0, 32 * sizeof (p->individuals[0]));
379 p->individuals_num = 32;
381 for (i = 0; i < p->individuals_num; i++)
383 p->individuals[i].ptr = NULL;
384 p->individuals[i].rating = -1;
388 } /* }}} population_t *population_create */
390 void population_destroy (population_t *p) /* {{{ */
395 pthread_mutex_lock (&p->lock);
396 p->flags |= POPULATION_FLAG_SHUTDOWN;
397 if ((p->flags & POPULATION_FLAG_LISTEN) != 0)
399 pthread_kill (p->listen_thread_id, SIGTERM);
400 pthread_mutex_unlock (&p->lock);
401 pthread_join (p->listen_thread_id, /* return = */ NULL);
402 pthread_mutex_lock (&p->lock);
405 if (p->fittest.ptr != NULL)
406 p->free (p->fittest.ptr);
407 p->fittest.ptr = NULL;
408 p->fittest.rating = -1;
410 if (p->individuals_num > 0)
414 for (i = 0; i < p->individuals_num; i++)
416 if (p->individuals[i].ptr != NULL)
417 p->free (p->individuals[i].ptr);
418 p->individuals[i].ptr = NULL;
419 p->individuals[i].rating = -1;
422 free (p->individuals);
423 p->individuals = NULL;
424 p->individuals_num = 0;
427 memset (p, 0, sizeof (*p));
429 } /* }}} void population_destroy */
431 int population_set_size (population_t *p, /* {{{ */
432 size_t population_size)
440 pthread_mutex_lock (&p->lock);
442 if (p->individuals_num == population_size)
444 pthread_mutex_unlock (&p->lock);
448 for (i = population_size; i < p->individuals_num; i++)
450 p->free (p->individuals[i].ptr);
451 p->individuals[i].ptr = NULL;
452 p->individuals[i].rating = -1;
455 temp = (individual_t *) realloc (p->individuals,
456 population_size * sizeof (p->individuals[0]));
459 pthread_mutex_unlock (&p->lock);
462 p->individuals = temp;
464 for (i = p->individuals_num; i < population_size; i++)
466 p->individuals[i].ptr = NULL;
467 p->individuals[i].rating = -1;
470 p->individuals_num = population_size;
472 pthread_mutex_unlock (&p->lock);
477 int population_set_serialization (population_t *p, /* {{{ */
478 pi_serialize_f serialize, pi_unserialize_f unserialize)
483 pthread_mutex_lock (&p->lock);
485 p->serialize = serialize;
486 p->unserialize = unserialize;
488 pthread_mutex_unlock (&p->lock);
490 } /* }}} int population_set_serialization */
492 int population_add_peer (population_t *p, const char *node, /* {{{ */
495 struct addrinfo ai_hints;
496 struct addrinfo *ai_list;
497 struct addrinfo *ai_ptr;
507 port = POPULATION_DEFAULT_PORT;
511 memset (&ai_hints, 0, sizeof (ai_hints));
512 ai_hints.ai_flags = 0;
514 ai_hints.ai_flags |= AI_ADDRCONFIG;
516 ai_hints.ai_family = AF_UNSPEC;
517 ai_hints.ai_socktype = SOCK_DGRAM;
518 ai_hints.ai_protocol = 0;
520 status = getaddrinfo (node, port, &ai_hints, &ai_list);
523 fprintf (stderr, "population_add_peer: getaddrinfo (%s) failed: %s\n",
524 node, gai_strerror (status));
528 pthread_mutex_lock (&p->lock);
530 for (ai_ptr = ai_list; ai_ptr != NULL; ai_ptr = ai_ptr->ai_next)
534 temp = (int *) realloc (p->peers, sizeof (int) * (p->peers_num + 1));
537 fprintf (stderr, "population_add_peer: realloc failed.\n");
542 p->peers[p->peers_num] = socket (ai_ptr->ai_family, ai_ptr->ai_socktype,
543 ai_ptr->ai_protocol);
544 if (p->peers[p->peers_num] < 0)
547 status = connect (p->peers[p->peers_num],
548 ai_ptr->ai_addr, ai_ptr->ai_addrlen);
551 fprintf (stderr, "population_add_peer: connect(2) failed.\n");
552 close (p->peers[p->peers_num]);
556 status = fcntl (p->peers[p->peers_num], F_SETFL, O_NONBLOCK);
559 fprintf (stderr, "population_add_peer: fcntl (F_SETFL, O_NONBLOCK) "
560 "failed. Will use the socket with blocking.\n");
565 printf ("population_add_peer: Successfully added peer #%i.\n",
568 pthread_mutex_unlock (&p->lock);
570 freeaddrinfo (ai_list);
573 } /* }}} int population_add_peer */
575 int population_start_listen_thread (population_t *p, /* {{{ */
576 const char *node, const char *service)
578 listen_thread_args_t *args;
580 pthread_mutex_lock (&p->lock);
581 if ((p->flags & POPULATION_FLAG_LISTEN) != 0)
583 pthread_mutex_unlock (&p->lock);
584 fprintf (stderr, "population_start_listen_thread: "
585 "Listen thread already started.\n");
589 args = (listen_thread_args_t *) malloc (sizeof (listen_thread_args_t));
592 fprintf (stderr, "population_start_listen_thread: malloc failed.\n");
596 memset (args, 0, sizeof (listen_thread_args_t));
597 args->population = p;
598 args->node = population_strdup (node);
599 args->service = population_strdup (service);
601 pthread_create (&p->listen_thread_id, /* attr = */ NULL,
602 listen_thread, (void *) args);
604 pthread_mutex_unlock (&p->lock);
606 } /* }}} int population_start_listen_thread */
608 void *population_get_random (population_t *p) /* {{{ */
613 pthread_mutex_lock (&p->lock);
615 if (p->individuals_num < 1)
617 pthread_mutex_unlock (&p->lock);
623 i = (size_t) (((double) p->individuals_num)
624 * (rand() / (RAND_MAX + 1.0)));
625 if (p->individuals[i].ptr == NULL)
628 ret = p->copy (p->individuals[i].ptr);
631 pthread_mutex_unlock (&p->lock);
634 } /* }}} void *population_pick_random */
636 void *population_get_fittest (population_t *p) /* {{{ */
643 pthread_mutex_lock (&p->lock);
645 if (p->fittest.ptr == NULL)
647 pthread_mutex_unlock (&p->lock);
651 ret = p->copy (p->fittest.ptr);
653 pthread_mutex_unlock (&p->lock);
656 } /* }}} void *population_get_fittest */
658 int population_insert (population_t *p, void *pi_orig) /* {{{ */
671 pi = p->copy (pi_orig);
674 fprintf (stderr, "population_insert: p->copy failed.\n");
679 * With a small chance, send this individual to somewhere else.
680 * `sent_to_peer = -1' is used to signal the following code that this
681 * individual has been sent to somewhere else and doesn't go into the local
685 if (p->peers_num > 0)
689 prob = ((double) rand ()) / (((double) RAND_MAX) + 1.0);
692 population_send_to_peer (p, pi);
697 pi_rating = p->rate (pi);
699 pthread_mutex_lock (&p->lock);
701 /* Keep track of the all time best. */
702 if ((p->fittest.ptr == NULL) || (p->fittest.rating >= pi_rating))
709 if (p->fittest.ptr != NULL)
710 p->free (p->fittest.ptr);
711 p->fittest.ptr = temp;
712 p->fittest.rating = pi_rating;
716 if ((sent_to_peer != 0) || (p->individuals_num <= 0))
718 pthread_mutex_unlock (&p->lock);
731 j = (size_t) (((double) p->individuals_num) * (rand() / (RAND_MAX + 1.0)));
733 if (p->individuals[j].ptr == NULL)
735 p->individuals[j].ptr = pi;
736 p->individuals[j].rating = pi_rating;
741 /* large distance from fittest => high probability of losing. */
742 chance_j = 1 + p->individuals[j].rating - p->fittest.rating;
743 chance_pi = 1 + pi_rating - p->fittest.rating;
745 chance_j = chance_j * chance_j;
746 chance_pi = chance_pi * chance_pi;
748 chance = (int) (((double) (chance_j + chance_pi))
749 * (rand() / (RAND_MAX + 1.0)));
750 if (chance < chance_j) /* j looses ;) */
755 temp0 = p->individuals[j].ptr;
756 p->individuals[j].ptr = pi;
759 temp1 = p->individuals[j].rating;
760 p->individuals[j].rating = pi_rating;
765 pthread_mutex_unlock (&p->lock);
771 } /* }}} int population_insert */
773 /* vim: set sw=2 sts=2 et fdm=marker : */