2 * collectd - src/sn_population.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>
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);
102 printf ("brute_force_minimize: Removed a comparator "
103 "(stage %i, comparator %i).\n",
104 stage_index, comparator_index);
105 sn_stage_comparator_remove (s_orig, comparator_index);
110 sn_network_destroy (n_copy);
112 } /* for (comparator_index) */
113 } /* for (stage_index) */
115 /* FIXME: Remove this check after debugging. */
116 assert (sn_network_brute_force_check (n_orig) == 0);
119 } /* int brute_force_minimize */
121 sn_population_t *sn_population_create (uint32_t size)
126 p = (sn_population_t *) malloc (sizeof (sn_population_t));
129 memset (p, 0, sizeof (sn_population_t));
132 p->networks = (sn_network_t **) calloc ((size_t) size,
133 sizeof (sn_network_t *));
134 if (p->networks == NULL)
140 p->ratings = (int *) calloc ((size_t) size, sizeof (int));
141 if (p->ratings == NULL)
148 status = pthread_mutex_init (&p->lock, /* attr = */ NULL);
151 fprintf (stderr, "sn_population_create: pthread_mutex_init failed: %i\n",
160 } /* sn_population_t *sn_population_create */
162 void sn_population_destroy (sn_population_t *p)
169 for (i = 0; i < p->size; i++)
170 if (p->networks[i] != NULL)
171 sn_network_destroy (p->networks[i]);
173 pthread_mutex_destroy (&p->lock);
178 } /* void sn_population_destroy */
180 int sn_population_push (sn_population_t *p, sn_network_t *n)
182 sn_network_t *n_copy;
185 n_copy = sn_network_clone (n);
188 fprintf (stderr, "sn_population_push: sn_network_clone failed.\n");
192 rating = rate_network (n_copy);
194 pthread_mutex_lock (&p->lock);
196 if (p->best_rating >= rating)
198 pthread_mutex_unlock (&p->lock);
200 brute_force_minimize (n_copy);
201 rating = rate_network (n_copy);
203 pthread_mutex_lock (&p->lock);
206 if ((p->best_rating >= rating)
207 || (p->best_network == NULL))
209 sn_network_t *n_copy_best;
211 n_copy_best = sn_network_clone (n);
212 if (n_copy_best != NULL)
214 if (p->best_network != NULL)
215 sn_network_destroy (p->best_network);
216 p->best_network = n_copy_best;
217 p->best_rating = rating;
221 if (p->networks_num < p->size)
223 p->networks[p->networks_num] = n_copy;
224 p->ratings[p->networks_num] = rating;
230 sn_network_t *n_removed = n_copy;
233 for (i = 0; i < (1 + (p->networks_num / 16)); i++)
235 index = sn_bounded_random (0, p->networks_num - 1);
236 if (p->ratings[index] < rating)
239 n_removed = p->networks[index];
240 p->networks[index] = n_copy;
241 p->ratings[index] = rating;
245 sn_network_destroy (n_removed);
248 pthread_mutex_unlock (&p->lock);
251 } /* int sn_population_push */
253 sn_network_t *sn_population_pop (sn_population_t *p)
256 sn_network_t *n_copy;
258 pthread_mutex_lock (&p->lock);
260 if (p->networks_num <= 0)
262 pthread_mutex_unlock (&p->lock);
266 index = sn_bounded_random (0, p->networks_num - 1);
267 n_copy = sn_network_clone (p->networks[index]);
269 pthread_mutex_unlock (&p->lock);
272 } /* sn_population_t *sn_population_pop */
274 sn_network_t *sn_population_best (sn_population_t *p)
280 sn_network_t *n_copy;
285 pthread_mutex_lock (&p->lock);
287 if (p->networks_num <= 0)
289 pthread_mutex_unlock (&p->lock);
293 for (i = 0; i < p->networks_num; i++)
295 if ((p->ratings[i] < rating) || (rating < 0))
297 rating = p->ratings[i];
302 n_copy = sn_network_clone (p->networks[index]);
304 pthread_mutex_unlock (&p->lock);
307 } /* sn_network_t *sn_population_best */
309 int sn_population_best_rating (sn_population_t *p)
314 pthread_mutex_lock (&p->lock);
316 if (p->networks_num <= 0)
318 pthread_mutex_unlock (&p->lock);
322 for (i = 0; i < p->networks_num; i++)
323 if ((p->ratings[i] < rating) || (rating < 0))
324 rating = p->ratings[i];
326 pthread_mutex_unlock (&p->lock);
329 } /* int sn_population_best_rating */
331 /* vim: set shiftwidth=2 softtabstop=2 : */