2 * libevolve - src/evolve.c
3 * Copyright (C) 2008 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"
74 #include <sys/types.h>
75 #include <sys/socket.h>
86 typedef struct individual_s individual_t;
92 /* Callback functions */
97 /* Optional serialization */
98 pi_serialize_f serialize;
99 pi_unserialize_f unserialize;
104 individual_t fittest;
106 individual_t *individuals;
107 size_t individuals_num;
113 static int population_send_to_peer (population_t *p, void *pi) /* {{{ */
130 buffer_size = sizeof (buffer);
131 memset (buffer, 0, buffer_size);
133 pthread_mutex_lock (&p->lock);
135 if (p->serialize == NULL)
137 pthread_mutex_unlock (&p->lock);
138 fprintf (stderr, "population_send_to_peer: Cannot send to peer without "
139 "serialization function!\n");
143 i = (int) (((double) p->peers_num) * (rand() / (RAND_MAX + 1.0)));
147 buffer_free = sizeof (buffer);
148 status = p->serialize (pi, &buffer_ptr, &buffer_free);
151 pthread_mutex_unlock (&p->lock);
152 fprintf (stderr, "population_send_to_peer: p->serialize failed "
153 "with status %i.\n", status);
157 buffer_size = sizeof (buffer) - buffer_free;
160 pthread_mutex_unlock (&p->lock);
161 fprintf (stderr, "population_send_to_peer: p->serialize didn't put "
162 "anything into the buffer..\n");
166 /* write should not block - hopefully */
167 status = send (fd, buffer, buffer_size, MSG_DONTWAIT | MSG_NOSIGNAL);
170 pthread_mutex_unlock (&p->lock);
172 if (status != ECONNREFUSED)
174 fprintf (stderr, "population_send_to_peer: Writing to socket failed: "
175 "send(2) returned with error %i.\n", status);
179 else if (((size_t) status) != buffer_size)
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);
188 pthread_mutex_unlock (&p->lock);
190 } /* }}} int population_send_to_peer */
193 * Constructor and destructor
195 population_t *population_create (pi_rate_f rate, pi_copy_f copy, /* {{{ */
201 p = (population_t *) malloc (sizeof (population_t));
205 memset (p, 0, sizeof (*p));
206 pthread_mutex_init (&p->lock, /* attr = */ NULL);
212 p->fittest.ptr = NULL;
213 p->fittest.rating = -1;
215 p->individuals = malloc (32 * sizeof (p->individuals[0]));
216 if (p->individuals == NULL)
221 memset (p->individuals, 0, 32 * sizeof (p->individuals[0]));
222 p->individuals_num = 32;
224 for (i = 0; i < p->individuals_num; i++)
226 p->individuals[i].ptr = NULL;
227 p->individuals[i].rating = -1;
231 } /* }}} population_t *population_create */
233 void population_destroy (population_t *p) /* {{{ */
238 if (p->fittest.ptr != NULL)
239 p->free (p->fittest.ptr);
240 p->fittest.ptr = NULL;
241 p->fittest.rating = -1;
243 if (p->individuals_num > 0)
247 for (i = 0; i < p->individuals_num; i++)
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;
255 free (p->individuals);
256 p->individuals = NULL;
257 p->individuals_num = 0;
260 memset (p, 0, sizeof (*p));
262 } /* }}} void population_destroy */
264 int population_set_size (population_t *p, /* {{{ */
265 size_t population_size)
273 pthread_mutex_lock (&p->lock);
275 if (p->individuals_num == population_size)
277 pthread_mutex_unlock (&p->lock);
281 for (i = population_size; i < p->individuals_num; i++)
283 p->free (p->individuals[i].ptr);
284 p->individuals[i].ptr = NULL;
285 p->individuals[i].rating = -1;
288 temp = (individual_t *) realloc (p->individuals,
289 population_size * sizeof (p->individuals[0]));
292 pthread_mutex_unlock (&p->lock);
295 p->individuals = temp;
297 for (i = p->individuals_num; i < population_size; i++)
299 p->individuals[i].ptr = NULL;
300 p->individuals[i].rating = -1;
303 p->individuals_num = population_size;
305 pthread_mutex_unlock (&p->lock);
310 int population_set_serialization (population_t *p,
311 pi_serialize_f serialize, pi_unserialize_f unserialize) /* {{{ */
316 pthread_mutex_lock (&p->lock);
318 p->serialize = serialize;
319 p->unserialize = unserialize;
321 pthread_mutex_unlock (&p->lock);
323 } /* }}} int population_set_serialization */
325 int population_add_peer (population_t *p, const char *node, /* {{{ */
328 struct addrinfo ai_hints;
329 struct addrinfo *ai_list;
330 struct addrinfo *ai_ptr;
340 port = POPULATION_DEFAULT_PORT;
344 memset (&ai_hints, 0, sizeof (ai_hints));
345 ai_hints.ai_flags = 0;
347 ai_hints.ai_flags |= AI_ADDRCONFIG;
349 ai_hints.ai_family = AF_UNSPEC;
350 ai_hints.ai_socktype = SOCK_DGRAM;
351 ai_hints.ai_protocol = 0;
353 status = getaddrinfo (node, port, &ai_hints, &ai_list);
356 fprintf (stderr, "population_add_peer: getaddrinfo (%s) failed: %s\n",
357 node, gai_strerror (status));
361 pthread_mutex_lock (&p->lock);
363 for (ai_ptr = ai_list; ai_ptr != NULL; ai_ptr = ai_ptr->ai_next)
367 temp = (int *) realloc (p->peers, sizeof (int) * (p->peers_num + 1));
370 fprintf (stderr, "population_add_peer: realloc failed.\n");
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)
380 status = connect (p->peers[p->peers_num],
381 ai_ptr->ai_addr, ai_ptr->ai_addrlen);
384 fprintf (stderr, "population_add_peer: connect(2) failed.\n");
385 close (p->peers[p->peers_num]);
389 status = fcntl (p->peers[p->peers_num], F_SETFL, O_NONBLOCK);
392 fprintf (stderr, "population_add_peer: fcntl (F_SETFL, O_NONBLOCK) "
393 "failed. Will use the socket with blocking.\n");
398 pthread_mutex_unlock (&p->lock);
400 freeaddrinfo (ai_list);
403 } /* }}} int population_add_peer */
405 void *population_get_random (population_t *p) /* {{{ */
410 pthread_mutex_lock (&p->lock);
412 if (p->individuals_num < 1)
414 pthread_mutex_unlock (&p->lock);
420 i = (size_t) (((double) p->individuals_num)
421 * (rand() / (RAND_MAX + 1.0)));
422 if (p->individuals[i].ptr == NULL)
425 ret = p->copy (p->individuals[i].ptr);
428 pthread_mutex_unlock (&p->lock);
431 } /* }}} void *population_pick_random */
433 void *population_get_fittest (population_t *p) /* {{{ */
440 pthread_mutex_lock (&p->lock);
442 if (p->fittest.ptr == NULL)
444 pthread_mutex_unlock (&p->lock);
448 ret = p->copy (p->fittest.ptr);
450 pthread_mutex_unlock (&p->lock);
453 } /* }}} void *population_get_fittest */
455 int population_insert (population_t *p, void *pi_orig) /* {{{ */
468 pi = p->copy (pi_orig);
471 fprintf (stderr, "population_insert: p->copy failed.\n");
475 pi_rating = p->rate (pi);
477 pthread_mutex_lock (&p->lock);
479 if (p->peers_num > 0)
483 prob = ((double) rand ()) / (((double) RAND_MAX) + 1.0);
486 pthread_mutex_unlock (&p->lock);
487 population_send_to_peer (p, pi);
488 pthread_mutex_lock (&p->lock);
492 /* Keep track of the all time best. */
493 if ((p->fittest.ptr == NULL) || (p->fittest.rating > pi_rating))
500 if (p->fittest.ptr != NULL)
501 p->free (p->fittest.ptr);
502 p->fittest.ptr = temp;
503 p->fittest.rating = pi_rating;
507 if (p->individuals_num <= 0)
509 pthread_mutex_unlock (&p->lock);
514 num_tries = (int) ceil (log (p->individuals_num) / log (2.0));
515 for (i = 0; i < num_tries; i++)
519 j = (size_t) (((double) p->individuals_num) * (rand() / (RAND_MAX + 1.0)));
521 if (p->individuals[j].ptr == NULL)
523 p->individuals[j].ptr = pi;
524 p->individuals[j].rating = pi_rating;
529 if (pi_rating < p->individuals[j].rating)
534 temp0 = p->individuals[j].ptr;
535 p->individuals[j].ptr = pi;
538 temp1 = p->individuals[j].rating;
539 p->individuals[j].rating = pi_rating;
544 pthread_mutex_unlock (&p->lock);
553 } /* }}} int population_insert */
555 /* vim: set sw=2 sts=2 et fdm=marker : */