2 * libsortnetwork - src/sn_population.c
3 * Copyright (C) 2008-2010 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 <ff at octo.it>
22 #ifndef _ISOC99_SOURCE
23 # define _ISOC99_SOURCE
25 #ifndef _POSIX_C_SOURCE
26 # define _POSIX_C_SOURCE 200112L
36 #include "sn_population.h"
37 #include "sn_network.h"
38 #include "sn_random.h"
40 struct sn_population_s
44 sn_network_t *best_network;
47 sn_network_t **networks;
49 uint32_t networks_num;
54 static int rate_network (const sn_network_t *n)
59 rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
60 for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
62 sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
63 rate += SN_STAGE_COMP_NUM (s);
67 } /* int rate_network */
69 static int brute_force_minimize (sn_network_t *n_orig)
74 /* printf ("brute_force_minimize: Running full fledged brute force optimization.\n"); */
77 stage_index < SN_NETWORK_STAGE_NUM (n_orig);
82 s_orig = SN_NETWORK_STAGE_GET (n_orig, stage_index);
84 for (comparator_index = 0;
85 comparator_index < SN_STAGE_COMP_NUM (s_orig);
92 n_copy = sn_network_clone (n_orig);
96 s_copy = SN_NETWORK_STAGE_GET (n_copy, stage_index);
97 sn_stage_comparator_remove (s_copy, comparator_index);
99 status = sn_network_brute_force_check (n_copy);
103 printf ("brute_force_minimize: Removed a comparator "
104 "(stage %i, comparator %i).\n",
105 stage_index, comparator_index);
107 sn_stage_comparator_remove (s_orig, comparator_index);
112 sn_network_destroy (n_copy);
114 } /* for (comparator_index) */
115 } /* for (stage_index) */
117 /* FIXME: Remove this check after debugging. */
118 assert (sn_network_brute_force_check (n_orig) == 0);
121 } /* int brute_force_minimize */
123 sn_population_t *sn_population_create (uint32_t size)
128 p = (sn_population_t *) malloc (sizeof (sn_population_t));
131 memset (p, 0, sizeof (sn_population_t));
134 p->networks = (sn_network_t **) calloc ((size_t) size,
135 sizeof (sn_network_t *));
136 if (p->networks == NULL)
142 p->ratings = (int *) calloc ((size_t) size, sizeof (int));
143 if (p->ratings == NULL)
150 status = pthread_mutex_init (&p->lock, /* attr = */ NULL);
153 fprintf (stderr, "sn_population_create: pthread_mutex_init failed: %i\n",
162 } /* sn_population_t *sn_population_create */
164 void sn_population_destroy (sn_population_t *p)
171 for (i = 0; i < p->size; i++)
172 if (p->networks[i] != NULL)
173 sn_network_destroy (p->networks[i]);
175 pthread_mutex_destroy (&p->lock);
180 } /* void sn_population_destroy */
182 int sn_population_push (sn_population_t *p, sn_network_t *n)
184 sn_network_t *n_copy;
187 n_copy = sn_network_clone (n);
190 fprintf (stderr, "sn_population_push: sn_network_clone failed.\n");
194 rating = rate_network (n_copy);
196 pthread_mutex_lock (&p->lock);
198 if (p->best_rating >= (rating - 4))
200 pthread_mutex_unlock (&p->lock);
202 brute_force_minimize (n_copy);
203 rating = rate_network (n_copy);
205 pthread_mutex_lock (&p->lock);
208 if ((p->best_rating >= rating)
209 || (p->best_network == NULL))
211 sn_network_t *n_copy_best;
213 n_copy_best = sn_network_clone (n);
214 if (n_copy_best != NULL)
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;
223 if (p->networks_num < p->size)
225 p->networks[p->networks_num] = n_copy;
226 p->ratings[p->networks_num] = rating;
232 sn_network_t *n_removed = n_copy;
235 for (i = 0; i < (1 + (p->networks_num / 16)); i++)
237 index = sn_bounded_random (0, p->networks_num - 1);
238 if (p->ratings[index] < rating)
241 n_removed = p->networks[index];
242 p->networks[index] = n_copy;
243 p->ratings[index] = rating;
247 sn_network_destroy (n_removed);
250 pthread_mutex_unlock (&p->lock);
253 } /* int sn_population_push */
255 sn_network_t *sn_population_pop (sn_population_t *p)
258 sn_network_t *n_copy;
260 pthread_mutex_lock (&p->lock);
262 if (p->networks_num <= 0)
264 pthread_mutex_unlock (&p->lock);
268 index = sn_bounded_random (0, p->networks_num - 1);
269 n_copy = sn_network_clone (p->networks[index]);
271 pthread_mutex_unlock (&p->lock);
274 } /* sn_population_t *sn_population_pop */
276 sn_network_t *sn_population_best (sn_population_t *p)
282 sn_network_t *n_copy;
287 pthread_mutex_lock (&p->lock);
289 if (p->networks_num <= 0)
291 pthread_mutex_unlock (&p->lock);
295 for (i = 0; i < p->networks_num; i++)
297 if ((p->ratings[i] < rating) || (rating < 0))
299 rating = p->ratings[i];
304 n_copy = sn_network_clone (p->networks[index]);
306 pthread_mutex_unlock (&p->lock);
309 } /* sn_network_t *sn_population_best */
311 int sn_population_best_rating (sn_population_t *p)
316 pthread_mutex_lock (&p->lock);
318 if (p->networks_num <= 0)
320 pthread_mutex_unlock (&p->lock);
324 for (i = 0; i < p->networks_num; i++)
325 if ((p->ratings[i] < rating) || (rating < 0))
326 rating = p->ratings[i];
328 pthread_mutex_unlock (&p->lock);
331 } /* int sn_population_best_rating */
333 /* vim: set shiftwidth=2 softtabstop=2 : */