LCOV - code coverage report
Current view: top level - src/backend/optimizer/geqo - geqo_pool.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 61 79 77.2 %
Date: 2019-11-13 22:07:24 Functions: 8 8 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*------------------------------------------------------------------------
       2             :  *
       3             :  * geqo_pool.c
       4             :  *    Genetic Algorithm (GA) pool stuff
       5             :  *
       6             :  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
       7             :  * Portions Copyright (c) 1994, Regents of the University of California
       8             :  *
       9             :  * src/backend/optimizer/geqo/geqo_pool.c
      10             :  *
      11             :  *-------------------------------------------------------------------------
      12             :  */
      13             : 
      14             : /* contributed by:
      15             :    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
      16             :    *  Martin Utesch              * Institute of Automatic Control      *
      17             :    =                             = University of Mining and Technology =
      18             :    *  utesch@aut.tu-freiberg.de  * Freiberg, Germany                   *
      19             :    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
      20             :  */
      21             : 
      22             : /* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
      23             : 
      24             : #include "postgres.h"
      25             : 
      26             : #include <float.h>
      27             : #include <limits.h>
      28             : #include <math.h>
      29             : 
      30             : #include "optimizer/geqo_copy.h"
      31             : #include "optimizer/geqo_pool.h"
      32             : #include "optimizer/geqo_recombination.h"
      33             : 
      34             : 
      35             : static int  compare(const void *arg1, const void *arg2);
      36             : 
      37             : /*
      38             :  * alloc_pool
      39             :  *      allocates memory for GA pool
      40             :  */
      41             : Pool *
      42           4 : alloc_pool(PlannerInfo *root, int pool_size, int string_length)
      43             : {
      44             :     Pool       *new_pool;
      45             :     Chromosome *chromo;
      46             :     int         i;
      47             : 
      48             :     /* pool */
      49           4 :     new_pool = (Pool *) palloc(sizeof(Pool));
      50           4 :     new_pool->size = (int) pool_size;
      51           4 :     new_pool->string_length = (int) string_length;
      52             : 
      53             :     /* all chromosome */
      54           4 :     new_pool->data = (Chromosome *) palloc(pool_size * sizeof(Chromosome));
      55             : 
      56             :     /* all gene */
      57           4 :     chromo = (Chromosome *) new_pool->data; /* vector of all chromos */
      58         260 :     for (i = 0; i < pool_size; i++)
      59         256 :         chromo[i].string = palloc((string_length + 1) * sizeof(Gene));
      60             : 
      61           4 :     return new_pool;
      62             : }
      63             : 
      64             : /*
      65             :  * free_pool
      66             :  *      deallocates memory for GA pool
      67             :  */
      68             : void
      69           4 : free_pool(PlannerInfo *root, Pool *pool)
      70             : {
      71             :     Chromosome *chromo;
      72             :     int         i;
      73             : 
      74             :     /* all gene */
      75           4 :     chromo = (Chromosome *) pool->data; /* vector of all chromos */
      76         260 :     for (i = 0; i < pool->size; i++)
      77         256 :         pfree(chromo[i].string);
      78             : 
      79             :     /* all chromosome */
      80           4 :     pfree(pool->data);
      81             : 
      82             :     /* pool */
      83           4 :     pfree(pool);
      84           4 : }
      85             : 
      86             : /*
      87             :  * random_init_pool
      88             :  *      initialize genetic pool
      89             :  */
      90             : void
      91           4 : random_init_pool(PlannerInfo *root, Pool *pool)
      92             : {
      93           4 :     Chromosome *chromo = (Chromosome *) pool->data;
      94             :     int         i;
      95           4 :     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           4 :     i = 0;
     106         264 :     while (i < pool->size)
     107             :     {
     108         256 :         init_tour(root, chromo[i].string, pool->string_length);
     109         256 :         pool->data[i].worth = geqo_eval(root, chromo[i].string,
     110             :                                         pool->string_length);
     111         256 :         if (pool->data[i].worth < DBL_MAX)
     112         256 :             i++;
     113             :         else
     114             :         {
     115           0 :             bad++;
     116           0 :             if (i == 0 && bad >= 10000)
     117           0 :                 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           4 : }
     127             : 
     128             : /*
     129             :  * sort_pool
     130             :  *   sorts input pool according to worth, from smallest to largest
     131             :  *
     132             :  *   maybe you have to change compare() for different ordering ...
     133             :  */
     134             : void
     135           4 : sort_pool(PlannerInfo *root, Pool *pool)
     136             : {
     137           4 :     qsort(pool->data, pool->size, sizeof(Chromosome), compare);
     138           4 : }
     139             : 
     140             : /*
     141             :  * compare
     142             :  *   qsort comparison function for sort_pool
     143             :  */
     144             : static int
     145         252 : compare(const void *arg1, const void *arg2)
     146             : {
     147         252 :     const Chromosome *chromo1 = (const Chromosome *) arg1;
     148         252 :     const Chromosome *chromo2 = (const Chromosome *) arg2;
     149             : 
     150         252 :     if (chromo1->worth == chromo2->worth)
     151         252 :         return 0;
     152           0 :     else if (chromo1->worth > chromo2->worth)
     153           0 :         return 1;
     154             :     else
     155           0 :         return -1;
     156             : }
     157             : 
     158             : /* alloc_chromo
     159             :  *    allocates a chromosome and string space
     160             :  */
     161             : Chromosome *
     162           8 : alloc_chromo(PlannerInfo *root, int string_length)
     163             : {
     164             :     Chromosome *chromo;
     165             : 
     166           8 :     chromo = (Chromosome *) palloc(sizeof(Chromosome));
     167           8 :     chromo->string = (Gene *) palloc((string_length + 1) * sizeof(Gene));
     168             : 
     169           8 :     return chromo;
     170             : }
     171             : 
     172             : /* free_chromo
     173             :  *    deallocates a chromosome and string space
     174             :  */
     175             : void
     176           8 : free_chromo(PlannerInfo *root, Chromosome *chromo)
     177             : {
     178           8 :     pfree(chromo->string);
     179           8 :     pfree(chromo);
     180           8 : }
     181             : 
     182             : /* spread_chromo
     183             :  *   inserts a new chromosome into the pool, displacing worst gene in pool
     184             :  *   assumes best->worst = smallest->largest
     185             :  */
     186             : void
     187         256 : spread_chromo(PlannerInfo *root, Chromosome *chromo, Pool *pool)
     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         256 :     if (chromo->worth > pool->data[pool->size - 1].worth)
     199           0 :         return;
     200             : 
     201             :     /* do a binary search to find the index of the new chromo */
     202             : 
     203         256 :     top = 0;
     204         256 :     mid = pool->size / 2;
     205         256 :     bot = pool->size - 1;
     206         256 :     index = -1;
     207             : 
     208         768 :     while (index == -1)
     209             :     {
     210             :         /* these 4 cases find a new location */
     211             : 
     212         256 :         if (chromo->worth <= pool->data[top].worth)
     213         256 :             index = top;
     214           0 :         else if (chromo->worth == pool->data[mid].worth)
     215           0 :             index = mid;
     216           0 :         else if (chromo->worth == pool->data[bot].worth)
     217           0 :             index = bot;
     218           0 :         else if (bot - top <= 1)
     219           0 :             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           0 :         else if (chromo->worth < pool->data[mid].worth)
     228             :         {
     229           0 :             bot = mid;
     230           0 :             mid = top + ((bot - top) / 2);
     231             :         }
     232             :         else
     233             :         {                       /* (chromo->worth > pool->data[mid].worth) */
     234           0 :             top = mid;
     235           0 :             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         256 :     geqo_copy(root, &pool->data[pool->size - 1], chromo, pool->string_length);
     250             : 
     251         256 :     swap_chromo.string = pool->data[pool->size - 1].string;
     252         256 :     swap_chromo.worth = pool->data[pool->size - 1].worth;
     253             : 
     254       16640 :     for (i = index; i < pool->size; i++)
     255             :     {
     256       16384 :         tmp_chromo.string = pool->data[i].string;
     257       16384 :         tmp_chromo.worth = pool->data[i].worth;
     258             : 
     259       16384 :         pool->data[i].string = swap_chromo.string;
     260       16384 :         pool->data[i].worth = swap_chromo.worth;
     261             : 
     262       16384 :         swap_chromo.string = tmp_chromo.string;
     263       16384 :         swap_chromo.worth = tmp_chromo.worth;
     264             :     }
     265             : }

Generated by: LCOV version 1.13