/*  lil-gp Genetic Programming System, version 1.0, 11 July 1995
 *  Copyright (C) 1995  Michigan State University
 * 
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of version 2 of the GNU General Public License as
 *  published by the Free Software Foundation.
 * 
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 * 
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *  
 *  Douglas Zongker       (zongker@isl.cps.msu.edu)
 *  Dr. Bill Punch        (punch@isl.cps.msu.edu)
 *
 *  Computer Science Department
 *  A-714 Wells Hall
 *  Michigan State University
 *  East Lansing, Michigan  48824
 *  USA
 *  
 *  This parallel version based on PVM is an extension of version 1.1
 *  of Lil-gp.
 *
 *  Johan Parent        (johan@info.vub.ac.be)
 *
 *  Faculty of Applied Sciences (Engineering Faculty)
 *  Building K, Computer Science Department
 *  Vrije Universiteit Brussel
 *  Pleinlaan 2, 1050 Etterbeek
 *  Belgium
 *
 */

#include <lilgp.h>

/* total counts of ERCs used and freed */
int ercused = 0;
int ercfree = 0;
int ercalloc = 0;

/* the active list. */
ephem_const *active_head;
int active_count;

/* the free list. */
ephem_const *free_head;
int free_count;

/* pointers for the allocated blocks for ERCs. */
ephem_const **block_list;
int block_list_size;
int block_count;

/* initialize_ephem_const()
 *
 * allocate and set up the first block of ERCs, the free list,
 * etc.
 */

void initialize_ephem_const ( void )
{
     int i;
     int size;

     oputs ( OUT_SYS, 30, "    ephemeral random constants.\n" );

     active_head = (ephem_const *)MALLOC ( sizeof ( ephem_const ) );
     active_head->refcount = 1;
     active_head->next = NULL;
     
     free_head = (ephem_const *)MALLOC ( sizeof ( ephem_const ) );
     free_head->refcount = 1;
     free_head->next = NULL;
     
     /** how many block >>pointers<< to allocate (not blocks). **/
     block_list_size = EPHEM_METABLOCKSIZE;
     block_list = (ephem_const **)MALLOC ( block_list_size *
					  sizeof ( ephem_const * ) );

     /* allocate the first block. */
     size = EPHEM_STARTSIZE;
     block_count = 1;
     block_list[0] = (ephem_const *)MALLOC ( size *
                                                  sizeof ( ephem_const ) );
     free_count = ercalloc = size;

     /* chain all the ERC records in the block together. */
     for ( i = 0; i < size-1; ++i )
          block_list[0][i].next = block_list[0]+i+1;
     block_list[0][size-1].next = NULL;

     /* add the chain to the free list. */
     free_head->next = block_list[0];
}

/* free_ephem_const()
 *
 * free all the memory allocated to hold ERCs.
 */

void free_ephem_const ( void )
{
     int i;

     ephem_const_gc();
     
     for ( i = 0; i < block_count; ++i )
          FREE ( block_list[i] );
     FREE ( block_list );

     FREE ( active_head );
     FREE ( free_head );
}

/* enlarge_ephem_space()
 *
 * allocate a new block of ERCs, and add all the records in it
 * to the free list.
 */

void enlarge_ephem_space ( void )
{
     int i;
     int size = EPHEM_GROWSIZE;

     /** if we've allocated too many blocks, we need to lengthen the
       list that holds block pointers. **/
     if ( block_count == block_list_size )
     {
          block_list_size += EPHEM_METABLOCKSIZE;
          block_list = (ephem_const **)REALLOC ( block_list,
						block_list_size *
						sizeof ( ephem_const *));
     }

     /* allocate the new block. */
     block_list[block_count] =
          (ephem_const *)MALLOC ( size * sizeof ( ephem_const ) );
     free_count += size;
     ercalloc += size;

     /* chain together all the records in it. */
     for ( i = 0; i < size-1; ++i )
          block_list[block_count][i].next =
               block_list[block_count]+i+1;
     
     block_list[block_count][size-1].next = free_head->next;
     free_head->next = block_list[block_count];
     
     ++block_count;
}
     
/* new_ephemeral_const()
 *
 * create a new ERC, corresponding to the given function.
 */

ephem_const *new_ephemeral_const ( function *f )
{
     ephem_const *p;

     /* make sure we have enough space. */
     while ( free_count <= 0 )
          enlarge_ephem_space();

     /* take the next record off the free list. */
     p = free_head->next;
     free_head->next = free_head->next->next;
     --free_count;

     /* call user code to generate the constant, placing
	the value in the new record. */
     f->ephem_gen ( &(p->d) );
     p->f = f;

     /* no references yet. */
     p->refcount = 0;

     /* add this record to the linked list of active ERCs. */
     p->next = active_head->next;
     active_head->next = p;
     ++active_count;

     ++ercused;
     
     return p;
}
     
/* ephem_const_gc()
 *
 * traverse the linked list of active ERCs, removing those with
 * a reference count of 0.
 */

void ephem_const_gc ( void )
{
     ephem_const *p = active_head->next;
     ephem_const *m = active_head;

     while ( p != NULL )
     {
          if ( p->refcount == 0 )
          {
	       /* patch the linked list to skip this record. */
               m->next = p->next;

	       /* add this record to the free list. */
               p->next = free_head->next;
	       free_head->next = p;
               ++free_count;
               ++ercfree;
	       --active_count;
	       
               p = m->next;
          }
          else
          {
	       /* move past this record. */
               m = p;
               p = p->next;
          }
     }

}
               
/* read_ephem_list()
 *
 * read list of ERCs from a checkpoint file. 
 */

ephem_const **read_ephem_list ( FILE *f )
{
     ephem_const **ind;
     ephem_const *p;
     int count;
     int i, j;
     char *buffer;

     /* read the count. */
     fscanf ( f, "%*s %d\n", &count );

     /** if no ERCs, do nothing and return a NULL pointer for the index. **/
     if ( count == 0 )
	  return NULL;

     /* somewhere to place (and ignore) the human-readable forms of
	the ERCs after the hex blocks. */
     buffer = (char *)MALLOC ( MAXCHECKLINELENGTH );

     /* allocate the index translating integers --> addresses. */
     ind = (ephem_const **)MALLOC ( count * sizeof ( ephem_const * ) );
     
     /** allocate a new block to hold all the ERCs we read. **/

     /* we shouldn't EVER need to lengthen the block list while reading
	a checkpoint, but check anyway... */
     if ( block_count == block_list_size )
     {
          block_list_size += EPHEM_METABLOCKSIZE;
          block_list = (ephem_const **)REALLOC ( block_list,
						block_list_size *
						sizeof ( ephem_const *));
     }

     /* allocate the new block. */
     block_list[block_count] =
	  (ephem_const *)MALLOC ( count * sizeof ( ephem_const ) );
     ercalloc += count;
     
     /* read the checkpointed ERCs into the new block. */
     for ( i = 0; i < count; ++i )
     {
	  p = block_list[block_count]+i;
	  fscanf ( f, "%d %d ", &j, &(p->refcount) );
	  ind[j] = p;
	  read_hex_block ( &(p->d), sizeof ( DATATYPE ), f );
	  fgets ( buffer, MAXCHECKLINELENGTH, f );

	  /* chain together all the records. */
	  block_list[block_count][i].next = block_list[block_count]+i+1;
     }
     /* add the chained block to the active list. */
     block_list[block_count][count-1].next = active_head->next;
     active_head->next = block_list[block_count];
     active_count += count;
     ercused += count;
     
     ++block_count;

     FREE ( buffer );
     
     return ind;
     
}
     
/* write_ephem_list()
 *
 * write the active list of ERCs to a checkpoint file.  returns an
 * index listing for translating an ERC address to a unique integer.
 * (we can't store the address directly in the checkpoint, since
 * the ERCs won't be loaded in the same spot in memory on restart.)
 */

ephem_index *write_ephem_list ( FILE *f )
{
     ephem_index *ind;
     ephem_const *p = active_head->next;
     int j;

     ind = (ephem_index *)MALLOC ( active_count * sizeof ( ephem_index ) );
     fprintf ( f, "erc-count: %d\n", active_count );
     
     j = 0;
     while ( p )
     {
	  /* store the index entry. */
          ind[j].e = p;
          ind[j].i = j;

	  /* write the reference count and the value. */
	  fprintf ( f, "%d %d ", j, p->refcount );
	  write_hex_block ( &(p->d), sizeof(DATATYPE), f );
	  fprintf ( f, " %s %s\n", p->f->string, p->f->ephem_str ( p->d ) );

	  /* move down the list. */
          p = p->next;
          ++j;
     }

     /* sort the index by address, so we can use binary searching
	on it. */
     qsort ( ind, active_count, sizeof(ephem_index), ephem_index_comp );

     return ind;
}

/* lookup_ephem()
 *
 * look up an ERC (by address) in an index returned by write_ephem_list()
 * and return its integer index.
 */

int lookup_ephem ( ephem_index *ind, ephem_const *e )
{
     int low = 0;
     int high = (ercused-ercfree);
     int mid;

     while ( low < high-1 )
     {
          mid = (low+high)/2;
          if ( e >= ind[mid].e )
               low = mid;
          else
               high = mid;
     }

     return ind[low].i;
}
     
/* ephem_index_comp()
 *
 * comparison function for using qsort() to order the ERC index by
 * address.
 */

int ephem_index_comp ( const void *a, const void *b )
{
     if ( ((ephem_index *)a)->e < ((ephem_index *)b)->e )
          return -1;
     else
          return 1;
}

/* get_ephem_stats()
 *
 * return ERC statistics.
 */

void get_ephem_stats ( int *used, int *free, int *blocks, int *alloc )
{
     *used = ercused;
     *free = ercfree;
     *blocks = block_count;
     *alloc = ercalloc;
}

#ifdef _PARALLEL_H

/* add_ephemeral_const()
 *
 * add an ERC.
 */

ephem_const *add_ephemeral_const ( function *f, DATATYPE data )
{
     ephem_const *p;

     /* make sure we have enough space. */
     while ( free_count <= 0 )
          enlarge_ephem_space();

     /* take the next record off the free list. */
     p = free_head->next;
     free_head->next = free_head->next->next;
     --free_count;

     /* DO NOT call user code to generate the constant
	INSTEAD put the value in the new record. */
     p->d = data;
     p->f = f;

     /* no references yet. */
     p->refcount = 0;

     /* add this record to the linked list of active ERCs. */
     p->next = active_head->next;
     active_head->next = p;
     ++active_count;

     ++ercused;
     
     return p;
}

#endif