#include "population.h"
#include <stdlib.h>
+#include <errno.h>
#include <stdint.h>
#include <inttypes.h>
#include <string.h>
#include <limits.h>
#include <pthread.h>
#include <math.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <sys/types.h>
+#include <sys/socket.h>
+#include <netdb.h>
/*
* Data types
*/
+struct individual_s
+{
+ void *ptr;
+ int rating;
+};
+typedef struct individual_s individual_t;
+
struct population_s
{
pthread_mutex_t lock;
pi_free_f free;
pi_copy_f copy;
- void **individuals;
+ /* Optional serialization */
+ pi_serialize_f serialize;
+ pi_unserialize_f unserialize;
+
+ int *peers;
+ size_t peers_num;
+
+ individual_t fittest;
+
+ individual_t *individuals;
size_t individuals_num;
};
/*
+ * Private functions
+ */
+static int population_send_to_peer (population_t *p, void *pi) /* {{{ */
+{
+ char buffer[1450];
+ size_t buffer_size;
+ size_t buffer_free;
+ char *buffer_ptr;
+
+ int fd;
+ int i;
+ int status;
+
+ if (p == NULL)
+ return (-1);
+
+ if (pi == NULL)
+ return (-1);
+
+ buffer_size = sizeof (buffer);
+ memset (buffer, 0, buffer_size);
+
+ pthread_mutex_lock (&p->lock);
+
+ if (p->serialize == NULL)
+ {
+ pthread_mutex_unlock (&p->lock);
+ fprintf (stderr, "population_send_to_peer: Cannot send to peer without "
+ "serialization function!\n");
+ return (-1);
+ }
+
+ i = (int) (((double) p->peers_num) * (rand() / (RAND_MAX + 1.0)));
+ fd = p->peers[i];
+
+ buffer_ptr = buffer;
+ buffer_free = sizeof (buffer);
+ status = p->serialize (pi, &buffer_ptr, &buffer_free);
+ if (status != 0)
+ {
+ pthread_mutex_unlock (&p->lock);
+ fprintf (stderr, "population_send_to_peer: p->serialize failed "
+ "with status %i.\n", status);
+ return (-1);
+ }
+
+ buffer_size = sizeof (buffer) - buffer_free;
+ if (buffer_size < 1)
+ {
+ pthread_mutex_unlock (&p->lock);
+ fprintf (stderr, "population_send_to_peer: p->serialize didn't put "
+ "anything into the buffer..\n");
+ return (-1);
+ }
+
+ /* write should not block - hopefully */
+ status = send (fd, buffer, buffer_size, MSG_DONTWAIT | MSG_NOSIGNAL);
+ if (status < 0)
+ {
+ pthread_mutex_unlock (&p->lock);
+ status = errno;
+ if (status != ECONNREFUSED)
+ {
+ fprintf (stderr, "population_send_to_peer: Writing to socket failed: "
+ "send(2) returned with error %i.\n", status);
+ }
+ return (-1);
+ }
+ else if (((size_t) status) != buffer_size)
+ {
+ pthread_mutex_unlock (&p->lock);
+ fprintf (stderr, "population_send_to_peer: Writing to socket failed: "
+ "send(2) returned %i (expected %zu).\n",
+ status, buffer_size);
+ return (-1);
+ }
+
+ pthread_mutex_unlock (&p->lock);
+ return (0);
+} /* }}} int population_send_to_peer */
+
+/*
* Constructor and destructor
*/
population_t *population_create (pi_rate_f rate, pi_copy_f copy, /* {{{ */
pi_free_f f)
{
population_t *p;
+ size_t i;
p = (population_t *) malloc (sizeof (population_t));
if (p == NULL)
p->copy = copy;
p->free = f;
- p->individuals = (void **) malloc (32 * sizeof (void *));
+ p->fittest.ptr = NULL;
+ p->fittest.rating = -1;
+
+ p->individuals = malloc (32 * sizeof (p->individuals[0]));
if (p->individuals == NULL)
{
free (p);
return (NULL);
}
- memset (p->individuals, 0, 32 * sizeof (void *));
+ memset (p->individuals, 0, 32 * sizeof (p->individuals[0]));
p->individuals_num = 32;
+ for (i = 0; i < p->individuals_num; i++)
+ {
+ p->individuals[i].ptr = NULL;
+ p->individuals[i].rating = -1;
+ }
+
return (p);
} /* }}} population_t *population_create */
if (p == NULL)
return;
+ if (p->fittest.ptr != NULL)
+ p->free (p->fittest.ptr);
+ p->fittest.ptr = NULL;
+ p->fittest.rating = -1;
+
if (p->individuals_num > 0)
{
size_t i;
for (i = 0; i < p->individuals_num; i++)
{
- p->free (p->individuals[i]);
- p->individuals[i] = NULL;
+ if (p->individuals[i].ptr != NULL)
+ p->free (p->individuals[i].ptr);
+ p->individuals[i].ptr = NULL;
+ p->individuals[i].rating = -1;
}
free (p->individuals);
size_t population_size)
{
size_t i;
- void **temp;
+ individual_t *temp;
if (p == NULL)
return (-1);
for (i = population_size; i < p->individuals_num; i++)
{
- p->free (p->individuals[i]);
- p->individuals[i] = NULL;
+ p->free (p->individuals[i].ptr);
+ p->individuals[i].ptr = NULL;
+ p->individuals[i].rating = -1;
}
- temp = (void **) realloc (p->individuals, population_size * sizeof (void *));
+ temp = (individual_t *) realloc (p->individuals,
+ population_size * sizeof (p->individuals[0]));
if (temp == NULL)
{
pthread_mutex_unlock (&p->lock);
p->individuals = temp;
for (i = p->individuals_num; i < population_size; i++)
- p->individuals[i] = NULL;
+ {
+ p->individuals[i].ptr = NULL;
+ p->individuals[i].rating = -1;
+ }
p->individuals_num = population_size;
return (0);
} /* }}} */
+int population_set_serialization (population_t *p,
+ pi_serialize_f serialize, pi_unserialize_f unserialize) /* {{{ */
+{
+ if (p == NULL)
+ return (-1);
+
+ pthread_mutex_lock (&p->lock);
+
+ p->serialize = serialize;
+ p->unserialize = unserialize;
+
+ pthread_mutex_unlock (&p->lock);
+ return (0);
+} /* }}} int population_set_serialization */
+
+int population_add_peer (population_t *p, const char *node, /* {{{ */
+ const char *port)
+{
+ struct addrinfo ai_hints;
+ struct addrinfo *ai_list;
+ struct addrinfo *ai_ptr;
+ int status;
+
+ if (p == NULL)
+ return (-1);
+
+ if (node == NULL)
+ return (-1);
+
+ if (port == NULL)
+ port = POPULATION_DEFAULT_PORT;
+
+ ai_list = NULL;
+
+ memset (&ai_hints, 0, sizeof (ai_hints));
+ ai_hints.ai_flags = 0;
+#ifdef AI_ADDRCONFIG
+ ai_hints.ai_flags |= AI_ADDRCONFIG;
+#endif
+ ai_hints.ai_family = AF_UNSPEC;
+ ai_hints.ai_socktype = SOCK_DGRAM;
+ ai_hints.ai_protocol = 0;
+
+ status = getaddrinfo (node, port, &ai_hints, &ai_list);
+ if (status != 0)
+ {
+ fprintf (stderr, "population_add_peer: getaddrinfo (%s) failed: %s\n",
+ node, gai_strerror (status));
+ return (-1);
+ }
+
+ pthread_mutex_lock (&p->lock);
+
+ for (ai_ptr = ai_list; ai_ptr != NULL; ai_ptr = ai_ptr->ai_next)
+ {
+ int *temp;
+
+ temp = (int *) realloc (p->peers, sizeof (int) * (p->peers_num + 1));
+ if (temp == NULL)
+ {
+ fprintf (stderr, "population_add_peer: realloc failed.\n");
+ continue;
+ }
+ p->peers = temp;
+
+ p->peers[p->peers_num] = socket (ai_ptr->ai_family, ai_ptr->ai_socktype,
+ ai_ptr->ai_protocol);
+ if (p->peers[p->peers_num] < 0)
+ continue;
+
+ status = connect (p->peers[p->peers_num],
+ ai_ptr->ai_addr, ai_ptr->ai_addrlen);
+ if (status != 0)
+ {
+ fprintf (stderr, "population_add_peer: connect(2) failed.\n");
+ close (p->peers[p->peers_num]);
+ continue;
+ }
+
+ status = fcntl (p->peers[p->peers_num], F_SETFL, O_NONBLOCK);
+ if (status != 0)
+ {
+ fprintf (stderr, "population_add_peer: fcntl (F_SETFL, O_NONBLOCK) "
+ "failed. Will use the socket with blocking.\n");
+ }
+
+ p->peers_num++;
+ }
+ pthread_mutex_unlock (&p->lock);
+
+ freeaddrinfo (ai_list);
+
+ return (0);
+} /* }}} int population_add_peer */
+
void *population_get_random (population_t *p) /* {{{ */
{
void *ret = NULL;
{
i = (size_t) (((double) p->individuals_num)
* (rand() / (RAND_MAX + 1.0)));
- if (p->individuals[i] == NULL)
+ if (p->individuals[i].ptr == NULL)
continue;
- ret = p->copy (p->individuals[i]);
+ ret = p->copy (p->individuals[i].ptr);
}
pthread_mutex_unlock (&p->lock);
void *population_get_fittest (population_t *p) /* {{{ */
{
void *ret = NULL;
- int best_rating;
- size_t i;
if (p == NULL)
return (NULL);
pthread_mutex_lock (&p->lock);
- best_rating = INT_MAX;
- for (i = 0; i < p->individuals_num; i++)
+ if (p->fittest.ptr == NULL)
{
- int rating;
-
- if (p->individuals[i] == NULL)
- continue;
-
- rating = p->rate (p->individuals[i]);
- if (rating < best_rating)
- {
- void *temp;
-
- temp = p->copy (p->individuals[i]);
- if (temp != NULL)
- {
- if (ret != NULL)
- p->free (ret);
- ret = temp;
- best_rating = rating;
- }
- }
+ pthread_mutex_unlock (&p->lock);
+ return (NULL);
}
+ ret = p->copy (p->fittest.ptr);
+
pthread_mutex_unlock (&p->lock);
return (ret);
pthread_mutex_lock (&p->lock);
+ if (p->peers_num > 0)
+ {
+ double prob;
+
+ prob = ((double) rand ()) / (((double) RAND_MAX) + 1.0);
+ if (prob < 0.01)
+ {
+ pthread_mutex_unlock (&p->lock);
+ population_send_to_peer (p, pi);
+ pthread_mutex_lock (&p->lock);
+ }
+ }
+
+ /* Keep track of the all time best. */
+ if ((p->fittest.ptr == NULL) || (p->fittest.rating > pi_rating))
+ {
+ void *temp;
+
+ temp = p->copy (pi);
+ if (temp != NULL)
+ {
+ if (p->fittest.ptr != NULL)
+ p->free (p->fittest.ptr);
+ p->fittest.ptr = temp;
+ p->fittest.rating = pi_rating;
+ }
+ }
+
if (p->individuals_num <= 0)
{
pthread_mutex_unlock (&p->lock);
return (-1);
}
- num_tries = (int) ceil (log (p->individuals_num) / log (2.0));
- for (i = 0; i < num_tries; i++)
+ do
{
size_t j;
- int j_rating;
+
+ int chance_j;
+ int chance_pi;
+ int chance;
j = (size_t) (((double) p->individuals_num) * (rand() / (RAND_MAX + 1.0)));
- if (p->individuals[j] == NULL)
+ if (p->individuals[j].ptr == NULL)
{
- p->individuals[j] = pi;
+ p->individuals[j].ptr = pi;
+ p->individuals[j].rating = pi_rating;
pi = NULL;
break;
}
- j_rating = p->rate (p->individuals[j]);
+ /* large distance from fittest => high probability of losing. */
+ chance_j = 1 + p->individuals[j].rating - p->fittest.rating;
+ chance_pi = 1 + pi_rating - p->fittest.rating;
- if (pi_rating < j_rating)
+ chance = (int) (((double) (chance_j + chance_pi))
+ * (rand() / (RAND_MAX + 1.0)));
+ if (chance < chance_j) /* j looses ;) */
{
- void *temp;
+ void *temp0;
+ int temp1;
- temp = p->individuals[j];
- p->individuals[j] = pi;
- pi = temp;
+ temp0 = p->individuals[j].ptr;
+ p->individuals[j].ptr = pi;
+ pi = temp0;
- pi_rating = j_rating;
+ temp1 = p->individuals[j].rating;
+ p->individuals[j].rating = pi_rating;
+ pi_rating = temp1;
}
- }
+ } while (0);
pthread_mutex_unlock (&p->lock);
projects / libpopulation.git / blobdiff