PostgreSQL Source Code  git master
geqo_pool.c File Reference
#include "postgres.h"
#include <float.h>
#include <limits.h>
#include <math.h>
#include "optimizer/geqo_copy.h"
#include "optimizer/geqo_pool.h"
#include "optimizer/geqo_recombination.h"
Include dependency graph for geqo_pool.c:

Go to the source code of this file.

Functions

static int compare (const void *arg1, const void *arg2)
 
Poolalloc_pool (PlannerInfo *root, int pool_size, int string_length)
 
void free_pool (PlannerInfo *root, Pool *pool)
 
void random_init_pool (PlannerInfo *root, Pool *pool)
 
void sort_pool (PlannerInfo *root, Pool *pool)
 
Chromosomealloc_chromo (PlannerInfo *root, int string_length)
 
void free_chromo (PlannerInfo *root, Chromosome *chromo)
 
void spread_chromo (PlannerInfo *root, Chromosome *chromo, Pool *pool)
 

Function Documentation

◆ alloc_chromo()

Chromosome* alloc_chromo ( PlannerInfo root,
int  string_length 
)

Definition at line 162 of file geqo_pool.c.

163 {
164  Chromosome *chromo;
165 
166  chromo = (Chromosome *) palloc(sizeof(Chromosome));
167  chromo->string = (Gene *) palloc((string_length + 1) * sizeof(Gene));
168 
169  return chromo;
170 }
int Gene
Definition: geqo_gene.h:30
void * palloc(Size size)
Definition: mcxt.c:1304
Gene * string
Definition: geqo_gene.h:34

References palloc(), and Chromosome::string.

Referenced by geqo().

◆ alloc_pool()

Pool* alloc_pool ( PlannerInfo root,
int  pool_size,
int  string_length 
)

Definition at line 42 of file geqo_pool.c.

43 {
44  Pool *new_pool;
45  Chromosome *chromo;
46  int i;
47 
48  /* pool */
49  new_pool = (Pool *) palloc(sizeof(Pool));
50  new_pool->size = (int) pool_size;
51  new_pool->string_length = (int) string_length;
52 
53  /* all chromosome */
54  new_pool->data = (Chromosome *) palloc(pool_size * sizeof(Chromosome));
55 
56  /* all gene */
57  chromo = (Chromosome *) new_pool->data; /* vector of all chromos */
58  for (i = 0; i < pool_size; i++)
59  chromo[i].string = palloc((string_length + 1) * sizeof(Gene));
60 
61  return new_pool;
62 }
int i
Definition: isn.c:73
Definition: geqo_gene.h:39
int string_length
Definition: geqo_gene.h:42
int size
Definition: geqo_gene.h:41
Chromosome * data
Definition: geqo_gene.h:40

References Pool::data, i, palloc(), Pool::size, and Pool::string_length.

Referenced by geqo().

◆ compare()

static int compare ( const void *  arg1,
const void *  arg2 
)
static

◆ free_chromo()

void free_chromo ( PlannerInfo root,
Chromosome chromo 
)

Definition at line 176 of file geqo_pool.c.

177 {
178  pfree(chromo->string);
179  pfree(chromo);
180 }
void pfree(void *pointer)
Definition: mcxt.c:1508

References pfree(), and Chromosome::string.

Referenced by geqo().

◆ free_pool()

void free_pool ( PlannerInfo root,
Pool pool 
)

Definition at line 69 of file geqo_pool.c.

70 {
71  Chromosome *chromo;
72  int i;
73 
74  /* all gene */
75  chromo = (Chromosome *) pool->data; /* vector of all chromos */
76  for (i = 0; i < pool->size; i++)
77  pfree(chromo[i].string);
78 
79  /* all chromosome */
80  pfree(pool->data);
81 
82  /* pool */
83  pfree(pool);
84 }

References Pool::data, i, pfree(), and Pool::size.

Referenced by geqo().

◆ random_init_pool()

void random_init_pool ( PlannerInfo root,
Pool pool 
)

Definition at line 91 of file geqo_pool.c.

92 {
93  Chromosome *chromo = (Chromosome *) pool->data;
94  int i;
95  int bad = 0;
96 
97  /*
98  * We immediately discard any invalid individuals (those that geqo_eval
99  * returns DBL_MAX for), thereby not wasting pool space on them.
100  *
101  * If we fail to make any valid individuals after 10000 tries, give up;
102  * this probably means something is broken, and we shouldn't just let
103  * ourselves get stuck in an infinite loop.
104  */
105  i = 0;
106  while (i < pool->size)
107  {
108  init_tour(root, chromo[i].string, pool->string_length);
109  pool->data[i].worth = geqo_eval(root, chromo[i].string,
110  pool->string_length);
111  if (pool->data[i].worth < DBL_MAX)
112  i++;
113  else
114  {
115  bad++;
116  if (i == 0 && bad >= 10000)
117  elog(ERROR, "geqo failed to make a valid plan");
118  }
119  }
120 
121 #ifdef GEQO_DEBUG
122  if (bad > 0)
123  elog(DEBUG1, "%d invalid tours found while selecting %d pool entries",
124  bad, pool->size);
125 #endif
126 }
#define DEBUG1
Definition: elog.h:30
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:224
Cost geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
Definition: geqo_eval.c:57
void init_tour(PlannerInfo *root, Gene *tour, int num_gene)
while(p+4<=pend)
static pg_noinline void Size size
Definition: slab.c:607

References Pool::data, DEBUG1, elog, ERROR, geqo_eval(), i, init_tour(), size, Pool::size, Pool::string_length, while(), and Chromosome::worth.

Referenced by geqo().

◆ sort_pool()

void sort_pool ( PlannerInfo root,
Pool pool 
)

Definition at line 135 of file geqo_pool.c.

136 {
137  qsort(pool->data, pool->size, sizeof(Chromosome), compare);
138 }
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
#define qsort(a, b, c, d)
Definition: port.h:449

References compare(), Pool::data, qsort, and Pool::size.

Referenced by geqo().

◆ spread_chromo()

void spread_chromo ( PlannerInfo root,
Chromosome chromo,
Pool pool 
)

Definition at line 187 of file geqo_pool.c.

188 {
189  int top,
190  mid,
191  bot;
192  int i,
193  index;
194  Chromosome swap_chromo,
195  tmp_chromo;
196 
197  /* new chromo is so bad we can't use it */
198  if (chromo->worth > pool->data[pool->size - 1].worth)
199  return;
200 
201  /* do a binary search to find the index of the new chromo */
202 
203  top = 0;
204  mid = pool->size / 2;
205  bot = pool->size - 1;
206  index = -1;
207 
208  while (index == -1)
209  {
210  /* these 4 cases find a new location */
211 
212  if (chromo->worth <= pool->data[top].worth)
213  index = top;
214  else if (chromo->worth == pool->data[mid].worth)
215  index = mid;
216  else if (chromo->worth == pool->data[bot].worth)
217  index = bot;
218  else if (bot - top <= 1)
219  index = bot;
220 
221 
222  /*
223  * these 2 cases move the search indices since a new location has not
224  * yet been found.
225  */
226 
227  else if (chromo->worth < pool->data[mid].worth)
228  {
229  bot = mid;
230  mid = top + ((bot - top) / 2);
231  }
232  else
233  { /* (chromo->worth > pool->data[mid].worth) */
234  top = mid;
235  mid = top + ((bot - top) / 2);
236  }
237  } /* ... while */
238 
239  /* now we have index for chromo */
240 
241  /*
242  * move every gene from index on down one position to make room for chromo
243  */
244 
245  /*
246  * copy new gene into pool storage; always replace worst gene in pool
247  */
248 
249  geqo_copy(root, &pool->data[pool->size - 1], chromo, pool->string_length);
250 
251  swap_chromo.string = pool->data[pool->size - 1].string;
252  swap_chromo.worth = pool->data[pool->size - 1].worth;
253 
254  for (i = index; i < pool->size; i++)
255  {
256  tmp_chromo.string = pool->data[i].string;
257  tmp_chromo.worth = pool->data[i].worth;
258 
259  pool->data[i].string = swap_chromo.string;
260  pool->data[i].worth = swap_chromo.worth;
261 
262  swap_chromo.string = tmp_chromo.string;
263  swap_chromo.worth = tmp_chromo.worth;
264  }
265 }
void geqo_copy(PlannerInfo *root, Chromosome *chromo1, Chromosome *chromo2, int string_length)
Definition: geqo_copy.c:45
Definition: type.h:95

References Pool::data, geqo_copy(), i, Pool::size, Chromosome::string, Pool::string_length, and Chromosome::worth.

Referenced by geqo().