src/sn_population.c

   1 /**
   2  * libsortnetwork - src/sn_population.c
   3  * Copyright (C) 2008-2010  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 <ff at octo.it>
  20  **/
  21
  22 #ifndef _ISOC99_SOURCE
  23 # define _ISOC99_SOURCE
  24 #endif
  25 #ifndef _POSIX_C_SOURCE
  26 # define _POSIX_C_SOURCE 200112L
  27 #endif
  28
  29 #include <stdlib.h>
  30 #include <stdio.h>
  31 #include <stdint.h>
  32 #include <string.h>
  33 #include <assert.h>
  34 #include <pthread.h>
  35
  36 #include "sn_population.h"
  37 #include "sn_network.h"
  38 #include "sn_random.h"
  39
  40 struct sn_population_s
  41 {
  42   uint32_t size;
  43
  44   sn_network_t *best_network;
  45   int best_rating;
  46
  47   sn_network_t **networks;
  48   int *ratings;
  49   uint32_t networks_num;
  50
  51   pthread_mutex_t lock;
  52 };
  53
  54 static int rate_network (const sn_network_t *n)
  55 {
  56   int rate;
  57   int i;
  58
  59   rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
  60   for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
  61   {
  62     sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
  63     rate += SN_STAGE_COMP_NUM (s);
  64   }
  65
  66   return (rate);
  67 } /* int rate_network */
  68
  69 static int brute_force_minimize (sn_network_t *n_orig)
  70 {
  71   int stage_index;
  72   int comparator_index;
  73
  74   /* printf ("brute_force_minimize: Running full fledged brute force optimization.\n"); */
  75
  76   for (stage_index = 0;
  77       stage_index < SN_NETWORK_STAGE_NUM (n_orig);
  78       stage_index++)
  79   {
  80     sn_stage_t *s_orig;
  81
  82     s_orig = SN_NETWORK_STAGE_GET (n_orig, stage_index);
  83
  84     for (comparator_index = 0;
  85         comparator_index < SN_STAGE_COMP_NUM (s_orig);
  86         comparator_index++)
  87     {
  88       sn_network_t *n_copy;
  89       sn_stage_t *s_copy;
  90       int status;
  91
  92       n_copy = sn_network_clone (n_orig);
  93       if (n_copy == NULL)
  94         continue;
  95
  96       s_copy = SN_NETWORK_STAGE_GET (n_copy, stage_index);
  97       sn_stage_comparator_remove (s_copy, comparator_index);
  98
  99       status = sn_network_brute_force_check (n_copy);
 100       if (status == 0)
 101       {
 102         /*
 103         printf ("brute_force_minimize: Removed a comparator "
 104             "(stage %i, comparator %i).\n",
 105             stage_index, comparator_index);
 106         */
 107         sn_stage_comparator_remove (s_orig, comparator_index);
 108
 109         comparator_index--;
 110       }
 111
 112       sn_network_destroy (n_copy);
 113       n_copy = NULL;
 114     } /* for (comparator_index) */
 115   } /* for (stage_index) */
 116
 117   /* FIXME: Remove this check after debugging. */
 118   assert (sn_network_brute_force_check (n_orig) == 0);
 119
 120   return (0);
 121 } /* int brute_force_minimize */
 122
 123 sn_population_t *sn_population_create (uint32_t size)
 124 {
 125   sn_population_t *p;
 126   int status;
 127
 128   p = (sn_population_t *) malloc (sizeof (sn_population_t));
 129   if (p == NULL)
 130     return (NULL);
 131   memset (p, 0, sizeof (sn_population_t));
 132   p->size = size;
 133
 134   p->networks = (sn_network_t **) calloc ((size_t) size,
 135       sizeof (sn_network_t *));
 136   if (p->networks == NULL)
 137   {
 138     free (p);
 139     return (NULL);
 140   }
 141
 142   p->ratings = (int *) calloc ((size_t) size, sizeof (int));
 143   if (p->ratings == NULL)
 144   {
 145     free (p->networks);
 146     free (p);
 147     return (NULL);
 148   }
 149
 150   status = pthread_mutex_init (&p->lock, /* attr = */ NULL);
 151   if (status != 0)
 152   {
 153     fprintf (stderr, "sn_population_create: pthread_mutex_init failed: %i\n",
 154         status);
 155     free (p->ratings);
 156     free (p->networks);
 157     free (p);
 158     return (NULL);
 159   }
 160
 161   return (p);
 162 } /* sn_population_t *sn_population_create */
 163
 164 void sn_population_destroy (sn_population_t *p)
 165 {
 166   uint32_t i;
 167
 168   if (p == NULL)
 169     return;
 170
 171   for (i = 0; i < p->size; i++)
 172     if (p->networks[i] != NULL)
 173       sn_network_destroy (p->networks[i]);
 174
 175   pthread_mutex_destroy (&p->lock);
 176
 177   free (p->ratings);
 178   free (p->networks);
 179   free (p);
 180 } /* void sn_population_destroy */
 181
 182 int sn_population_push (sn_population_t *p, sn_network_t *n)
 183 {
 184   sn_network_t *n_copy;
 185   int rating;
 186
 187   n_copy = sn_network_clone (n);
 188   if (n_copy == NULL)
 189   {
 190     fprintf (stderr, "sn_population_push: sn_network_clone failed.\n");
 191     return (-1);
 192   }
 193
 194   rating = rate_network (n_copy);
 195
 196   pthread_mutex_lock (&p->lock);
 197
 198   if (p->best_rating >= (rating - 4))
 199   {
 200     pthread_mutex_unlock (&p->lock);
 201
 202     brute_force_minimize (n_copy);
 203     rating = rate_network (n_copy);
 204
 205     pthread_mutex_lock (&p->lock);
 206   }
 207
 208   if ((p->best_rating >= rating)
 209       || (p->best_network == NULL))
 210   {
 211     sn_network_t *n_copy_best;
 212
 213     n_copy_best = sn_network_clone (n);
 214     if (n_copy_best != NULL)
 215     {
 216       if (p->best_network != NULL)
 217         sn_network_destroy (p->best_network);
 218       p->best_network = n_copy_best;
 219       p->best_rating = rating;
 220     }
 221   }
 222
 223   if (p->networks_num < p->size)
 224   {
 225     p->networks[p->networks_num] = n_copy;
 226     p->ratings[p->networks_num] = rating;
 227     p->networks_num++;
 228   }
 229   else
 230   {
 231     int index;
 232     sn_network_t *n_removed = n_copy;
 233     int i;
 234
 235     for (i = 0; i < (1 + (p->networks_num / 16)); i++)
 236     {
 237       index = sn_bounded_random (0, p->networks_num - 1);
 238       if (p->ratings[index] < rating)
 239         continue;
 240
 241       n_removed = p->networks[index];
 242       p->networks[index] = n_copy;
 243       p->ratings[index] = rating;
 244       break;
 245     }
 246
 247     sn_network_destroy (n_removed);
 248   }
 249
 250   pthread_mutex_unlock (&p->lock);
 251
 252   return (0);
 253 } /* int sn_population_push */
 254
 255 sn_network_t *sn_population_pop (sn_population_t *p)
 256 {
 257   int index;
 258   sn_network_t *n_copy;
 259
 260   pthread_mutex_lock (&p->lock);
 261
 262   if (p->networks_num <= 0)
 263   {
 264     pthread_mutex_unlock (&p->lock);
 265     return (NULL);
 266   }
 267
 268   index = sn_bounded_random (0, p->networks_num - 1);
 269   n_copy = sn_network_clone (p->networks[index]);
 270
 271   pthread_mutex_unlock (&p->lock);
 272
 273   return (n_copy);
 274 } /* sn_population_t *sn_population_pop */
 275
 276 sn_network_t *sn_population_best (sn_population_t *p)
 277 {
 278   uint32_t i;
 279
 280   uint32_t index = 0;
 281   int rating = -1;
 282   sn_network_t *n_copy;
 283
 284   if (p == NULL)
 285     return (NULL);
 286
 287   pthread_mutex_lock (&p->lock);
 288
 289   if (p->networks_num <= 0)
 290   {
 291     pthread_mutex_unlock (&p->lock);
 292     return (NULL);
 293   }
 294
 295   for (i = 0; i < p->networks_num; i++)
 296   {
 297     if ((p->ratings[i] < rating) || (rating < 0))
 298     {
 299       rating = p->ratings[i];
 300       index = i;
 301     }
 302   }
 303
 304   n_copy = sn_network_clone (p->networks[index]);
 305
 306   pthread_mutex_unlock (&p->lock);
 307
 308   return (n_copy);
 309 } /* sn_network_t *sn_population_best */
 310
 311 int sn_population_best_rating (sn_population_t *p)
 312 {
 313   uint32_t i;
 314   int rating = -1;
 315
 316   pthread_mutex_lock (&p->lock);
 317
 318   if (p->networks_num <= 0)
 319   {
 320     pthread_mutex_unlock (&p->lock);
 321     return (-1);
 322   }
 323
 324   for (i = 0; i < p->networks_num; i++)
 325     if ((p->ratings[i] < rating) || (rating < 0))
 326       rating = p->ratings[i];
 327
 328   pthread_mutex_unlock (&p->lock);
 329
 330   return (rating);
 331 } /* int sn_population_best_rating */
 332
 333 /* vim: set shiftwidth=2 softtabstop=2 : */