#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <yafl_usr.h>
#include <yafl_rnt.h>

#ifdef  YAFL_MICROSOFT
#define unlink _unlink
#endif  

static header * top=NULL;          /* head to the linked allocated 
                                      structure attached to the
                                      non-killable instances */
static header * killable_top=NULL; /* head to the linked allocated structure
                                      attached to the killable instances */

static int gc_count = 0;

#ifdef UNIX
static long max_alloc_mem = 4000000L;
#else
static long max_alloc_mem = 7000000L;
#endif

#ifdef USE_STD_MALLOC
#define yafl_malloc(i) malloc(i)
#define yafl_free(p,size) free(p)
#else
extern void dump_mallocs YARGS((void));
#endif

#ifdef Y_TRACE_GC
FILE * gc_trace = NULL;
static int visit_header(header *h);
#endif


extern void clear_shadows YARGS((void));
extern void y_mark_stack YARGS((void));
extern void y_mark_once YARGS((void));
extern int  kill_required YARGS((void));
extern void garbage_collect YARGS((void));

static long total_alloc_mem = 0L;
static unsigned alloc_count = 0;

static unsigned redundant_access, non_redundant_access;
static unsigned short_dist_collision, long_dist_collision;

static int in_gc = 0;  /* Guard variable which indicated whether
                          we are currently busy with a garbage collection
                          process or not. This variable is used to
                          disable checks regarding the amount of
                          free memory during the eventual (and hopefully
                          small) allocations attached to executing the
                          KILL methods. */
                          
static unsigned user_prefix_size = 0; /* The user_prefix_size gives a 
                                         size (in bytes) of a memory
                                         area which will be allocated
                                         in front of every allocation
                                         performed by the YAFL runtime 
                                         system. It is required by the
                                         persistent version of the YAFL
                                         compiler, and may prove useful
                                         to the debugger as well */

#define CHECK_MEM_CRASH assert(user_prefix_size < 64); \
                        assert(alloc_count <2000000);

#define TO_USER(p) ((header*)(((char *)p)+user_prefix_size))
#define TO_SYSTEM(p) (((char *)p)-user_prefix_size)
                                         
#define IS_KILLABLE(p) ((HEADER_ARRAY_LEVEL(p) == 0) && (p->dual->kill_func))

static int marking_generation;

/*********************************************************/
/*int check_mem(void)
 *{
 *if ((user_prefix_size >= 64) || (alloc_count >2000000))
 * return 1;
 *else
 * return 0;
 *}
 *int dump_mem(void)
 *{
 *char *p;
 *
 *p = (char *) & user_prefix_size;
 *printf ("%s\n", p);
 *assert(0);
 *}
 *********************************************************/
void set_user_prefix_size YPARAMS2(unsigned, size)
{
  user_prefix_size = size;
}
/*********************************************************/
void set_max_alloc_mem YPARAMS2(unsigned long, bytes)
{
  max_alloc_mem = bytes;
}
/*********************************************************/
yint get_max_alloc_mem YPARAMS0
{
  return max_alloc_mem;
}
/*********************************************************/
unsigned long get_total_alloc_mem YPARAMS0
{
  return total_alloc_mem;
}

/*********************************************************
* The element_size function returns the amount of memory
* used by a single element of an array of level "level",
* which elements are denoted by the dual "dual".
*********************************************************/
int element_size YPARAMS4(int, level, minimal_dual*, dual)
{
  int is_predef;
  char a[200];
  char *p = 0;

  if(dual->elem_size <= 0)
    {
      sprintf (a, "ElementSize.Bad size: %d for class %s\n", dual->elem_size,
                                             dual->class_name);
      emit_stdout(a);                                             
      /* *p=0; */
      assert(0);
    }
  is_predef = dual->first_sig < 0;
  if ((level == 0)||((level == 1) && is_predef))
    return dual->elem_size;
   else
    return sizeof (obj_ptr);
}
/*********************************************************/
int alloc_size YPARAMS6 (yint,           ar_size,
                        int,            level,
                        minimal_dual *, dual)
{
  char a[200];
  
  int size, i;
  if (ar_size < 0)
    {
      yafl_err(YERR_BAD_ARRAY_SIZE);
      dump_trace();
      exit(1);
    }
  if (ar_size == 0)
    size = 1;
   else
    size = ar_size;
  if (level > 0)
    size ++;
  i = element_size(level, dual) * size;         
  if (i <= 0)
    {
       sprintf (a, "i = %d    size = %d   elem_size = %d\n", i, size,
                     element_size(level, dual));
       emit_stdout(a);                     
       assert(0);
    }
  return i;
}
/*********************************************************/
static void dump_memory_status YPARAMS0
{
  char a[200];
  
  sprintf (a, "Total alloc mem:  %9ld    Max alloc mem: %9ld", 
               total_alloc_mem, max_alloc_mem);
  emit_stdout(a);
  emit_nl();
  sprintf (a, "Total allocations: %9ld   User prefix:   %9ld", 
               (long) alloc_count, (long) user_prefix_size);
  emit_stdout(a);
  emit_nl();               
#ifndef USE_STD_MALLOC
  dump_mallocs();
#endif
}
/*********************************************************/
obj_ptr y_alloc YPARAMS6(YINT, ar_size,
                        int,  level,
                        obj_ptr, dual_ptr)
{
  header *p;
  char * temp_c;
  int size, all_size;
  char a[200];

  p = NULL;
  temp_c = NULL;
  size = sizeof(header) + alloc_size(ar_size, level, dual_ptr);
  total_alloc_mem += size;
  all_size = size + user_prefix_size;
  if ((in_gc) || (total_alloc_mem <= max_alloc_mem))
    temp_c = yafl_malloc(all_size);
  if (!temp_c)
    {

      garbage_collect();
      temp_c = yafl_malloc(all_size);
      if (!temp_c)
        {
          yafl_err(YERR_NO_MEM);
          dump_memory_status();
          sprintf (a, "\nYafl Runtime error: out of memory [%d]\n", size);
          emit_stdout(a);
          dump_trace();
          exit(1);
        }
    }
    
  memset (temp_c, 0, all_size);
  p = TO_USER(temp_c);
  
  p->_array_level = level;
  p->_array_size = ar_size;
  p->dual = (minimal_dual *) dual_ptr;
/*
  p->signature = SIG_VALUE;
*/  
  ((minimal_dual *) dual_ptr) -> inst_count ++;
  if (IS_KILLABLE(p))
    {
      p->next_ptr = (VOID *) killable_top;
      killable_top = p;
    }
   else
    {
      p->next_ptr = (VOID *) top;
      top = p;
    }
  VREG((obj_ptr)(p+1));
  alloc_count ++;
  return (obj_ptr) (p+1);
}
/*********************************************************/
obj_ptr y_realloc YPARAMS2(obj_ptr, p)
{
  int old_size, new_size;
  obj_ptr res;
  header *h;

  h = HEADER(p);
  old_size = HEADER_ARRAY_SIZE(h);
  if (old_size < 32)
    new_size = old_size * 2;
   else
    new_size = (old_size * 3) / 2;
  res = y_alloc (new_size, 
                 HEADER_ARRAY_LEVEL(HEADER(p)),
			     h->dual);
  memcpy (res, p, 
          element_size (HEADER_ARRAY_LEVEL(h), h->dual) * old_size);
  return res;
}
/*********************************************************/
obj_ptr new_string YPARAMS2(char*, a)
{
  obj_ptr p;

  p = y_alloc(strlen(a), 1, (obj_ptr) &YD_CHAR);
  strcpy ((char *)p, a);
  assert(HEADER_ARRAY_LEVEL(HEADER(p)) == 1);
  return p;
}
/********************************************************/
void kill_killable YPARAMS2(int, marking_generation)
{
  header *p, *next, *last;
  
  p = killable_top;
  last = NULL;
  while (p)
    {                 
      next = (header *) p->next_ptr;
      if (HEADER_MARKED(p) != marking_generation)
        {
          /**********************************************
          * apparently, p ought to be deallocated. First,
          * execute the corresponding KILL method; then,
          * link it in the main allocation list so that
          * the garbage collection process can take
          * it into account.
          **********************************************/  
          p->dual->kill_func((obj_ptr) (p+1));
          /**********************************************
          * Store p in the main linked list of instances,
          * in such a way that it can be recovered by
          * the main garbage collection process.
          **********************************************/  
          p->next_ptr = top;
          top = p;
        }
       else
        {
          if (last == NULL)
            killable_top = p;
           else
            last->next_ptr = p;
          last = p;
        }
      /********************************************
      * In any case, it must be unmarked before the
      * garbage collection's second pass
      ********************************************/
      CLEAR_HEADER_MARKED(p);
      p = next;
    }
  if (last)
    last->next_ptr = NULL;
   else
    killable_top = NULL;
  
}
/********************************************************/
void clear_linked_list YPARAMS2(header *, p)
{
  while (p)
    {
      CLEAR_HEADER_MARKED(p);
      p = p->next_ptr;
    }
}
/********************************************************/
void clear_killables YPARAMS0
{
  clear_linked_list(killable_top);
}
/********************************************************/
void clear_non_killables YPARAMS0
{
  clear_linked_list(top);
}
/********************************************************/
void free_unmarked YPARAMS2(int, marking_generation)
{
  header *p, *last, *q, *next;
  int all_size;

  p = top;
  last = NULL;       
  while (p)
    {               
      next = p->next_ptr;
      if (HEADER_MARKED(p) == marking_generation)
        {
          CLEAR_HEADER_MARKED(p);
          total_alloc_mem += sizeof(header) + 
                                    alloc_size(HEADER_ARRAY_SIZE(p),
                                               HEADER_ARRAY_LEVEL(p),
                                               p->dual);
          /****************************
          * If p refers to a killable instance, put it
          * back in the killable linked list.
          ****************************/
          if (IS_KILLABLE(p))
            {  
              p->next_ptr = killable_top;
              killable_top = p;
            }
           else
            {
              if (last == NULL)
                top = p;
               else
                last->next_ptr = (VOID *) p;
              last = p;
            }
        }
       else
        {
          /**********************************
          * Decrement the instance counter attached
          * to the class if the array level is zero
          **********************************/
          if ((HEADER_ARRAY_LEVEL(p) == 0))
            p->dual->inst_count --;
          all_size = sizeof(header) + alloc_size(HEADER_ARRAY_SIZE(p),
                                                 HEADER_ARRAY_LEVEL(p),
                                                 p->dual);
          memset(p, 0, all_size);
          alloc_count --;                                              
          yafl_free(TO_SYSTEM(p), all_size + user_prefix_size);
        }
      p = next;
    }
  if (last)
    last -> next_ptr = NULL;
}
/*******************************************/
void dump_obj_ptr YPARAMS4(FILE*, out, 
                          header*, h)
{
  int size;
  char a[200];

  size = alloc_size (HEADER_ARRAY_SIZE(h), 
                     HEADER_ARRAY_LEVEL(h), h->dual);
  
  sprintf (a, "Lev: %8d ASize: %8d Size: %8d Class: %s\n",
           HEADER_ARRAY_LEVEL(h),
           HEADER_ARRAY_SIZE(h),
           size, h->dual->class_name);
  if (out)
    fprintf (out, "%s", a);
   else
    emit_stdout(a);           
}
/*******************************************/
void dump_memory YPARAMS0
{
  header *p;
  long total;
  int size;
  char a[200];

  p = (header *)top;
  total = 0L;
  emit_stdout ("Memory chain\n------------------------\n");
  while (p)
    {
      size = alloc_size (HEADER_ARRAY_SIZE(p), 
                         HEADER_ARRAY_LEVEL(p), p->dual);
/*
      dump_obj_ptr(NULL, p);
*/      
      total += size;
      p = (header *) p->next_ptr;
    }
  emit_stdout ("\nKillable:\n--------\n");
  p = killable_top;
  while (p)
    {
      size = alloc_size (HEADER_ARRAY_SIZE(p), 
                         HEADER_ARRAY_LEVEL(p), p->dual);
      dump_obj_ptr(NULL, p);
      total += size;
      p = (header *) p->next_ptr;
    }
  sprintf (a, "Total: %ld bytes\n", total);
  emit_stdout(a);
}
/*************************************************/
static obj_ptr pool[POOLSIZE];
static obj_ptr  *pool_first = pool, 
                *pool_last = pool,
                *pool_right = &pool[POOLSIZE-1];
#define INC_POOL_PTR(p) {                               \
                        if (p == pool_right)            \
                          p = pool;                     \
                         else                           \
                          p++;                          \
                        }                
/*********************************************************/
void mark YPARAMS2(obj_ptr, p)
{
  header    *h;
  obj_ptr   *q;
  int       arr_level, arr_size;
  int       sig;
  int       i;

  h = HEADER(p);
  arr_level = HEADER_ARRAY_LEVEL(h);
  arr_size = HEADER_ARRAY_SIZE(h);
  sig = h->dual->first_sig;
  if (IS_KILLABLE(h))
    h->dual->shadow_count ++;
  if ((arr_level > 1) || ((arr_level > 0) && (sig >= 0)))
    {
      q = (obj_ptr *) p;
      for (i=1; i <= arr_size; i++)
        {     
          enter_pool(*q);
          if (i % 16 == 0)
            flush_pool();
          q++;
        }
    }
   else
    if (sig >= 0)
      {
      minimal_dual *d;
      int *mark_ptr;
      
      d = h->dual;
      do
        {                   
        mark_ptr = d->mark_tab;
        if (mark_ptr)
          while(*mark_ptr >= 0)
            {   
            enter_pool(*((obj_ptr *) (((char*)p)+*mark_ptr)));
            mark_ptr ++;
            }
        d = (minimal_dual *)d->inherited;
        }
      while (d);
      }
}
/*********************************************************/
static FILE * pool_file = NULL;
#define TEMP_POOL_SIZE (POOLSIZE / 2)
#define POOL_FNAME "pool.gc"
/*********************************************************/
void flush_pool YPARAMS0
{
  obj_ptr p;
  int go_on = FALSE;
  long recs;
  
  do
    {     
      go_on = FALSE;
      while (pool_first != pool_last)
        { 
          p = *pool_first;           
          INC_POOL_PTR(pool_first);
          mark(p);
        }
      if (pool_file != NULL)
        {
          memset(pool, 0, POOLSIZE * sizeof(obj_ptr));
          pool_first = pool;
          recs = fread (pool, sizeof(obj_ptr), TEMP_POOL_SIZE, pool_file);
          if (recs < TEMP_POOL_SIZE)
            {
              fclose (pool_file);
              pool_file = NULL;
              unlink (POOL_FNAME); 
            }
          pool_last = &(pool [recs]);
          go_on = TRUE;
        }
    }
  while (go_on);
  pool_file = NULL;
  pool_first = pool;
  pool_last = pool;
}
/*********************************************************/
void enter_pool YPARAMS2(obj_ptr, p)
{         
  header *h;
  unsigned a_level;
  long old_pos;
  int i;
      
  if (!p)
    return;
  h = HEADER(p);
  if (HEADER_MARKED(h) == marking_generation)
    redundant_access ++;
   else
    {  
      non_redundant_access ++;
      SET_HEADER_MARKED(h, marking_generation);
      a_level = HEADER_ARRAY_LEVEL(h);
      if ((a_level == 1) && (h->dual->first_sig < 0))
        {
#ifdef Y_TRACE_GC    
          visit_header(h);
#endif      
          return;
        }
/*
      if ((a_level == 0) && (! h->dual->requires_marking))
        return;
*/        
      *pool_last = p;
      INC_POOL_PTR(pool_last);
      if (pool_last == pool_first)
        {     
          char a[100];
          
          if (pool_file == NULL)
            {
              pool_file = fopen (POOL_FNAME, "w+b");
              if(pool_file == NULL)
                {
                  sprintf (a, "Error: pool table overflow, cannot create gc file\n");
                  emit_stdout(a);
                  exit(1);
                }
            }
          old_pos = ftell(pool_file);
          fseek(pool_file, 0, SEEK_END);
          sprintf (a, "Warning: pool table overflow [%d -> %d]\n", 
                        POOLSIZE,
                        POOLSIZE + ftell(pool_file) / sizeof(obj_ptr));
          emit_stdout(a);
          fwrite (pool, sizeof(obj_ptr), TEMP_POOL_SIZE, pool_file);
          memset(pool, 0, TEMP_POOL_SIZE * sizeof(obj_ptr));
          
          /*
          for (i=0; i<TEMP_POOL_SIZE; i++)
            assert(pool[i] == NULL);
          for (i=TEMP_POOL_SIZE; i<POOLSIZE; i++)
            assert(pool[i] != NULL);
          */
            
          pool_last = pool;
          pool_first = &(pool[TEMP_POOL_SIZE]);
          fseek(pool_file, old_pos, SEEK_SET);
          
        }
#ifdef Y_TRACE_GC    
      visit_header(h);
#endif      
    }
}
/*********************************************************/
void mark_killables YPARAMS0
{
  header *p = killable_top;
  
  while (p)
    {
      enter_pool((obj_ptr)(p+1));
      flush_pool();
      p = p -> next_ptr;
    }
}
/*********************************************************/
void garbage_collect YPARAMS0
{    
  char a[200];	    
  long old_total_alloc_mem = total_alloc_mem;
  
  /*
  * Handle the critical flag, which indicated whether a garbage collection
  * is in progress or not.
  */ 
  if (in_gc)
    return;	    
  in_gc = 1;          
  gc_count ++;
  
  
#ifdef Y_TRACE_GC
  sprintf (a, "gc.%04d", gc_count);
  gc_trace = fopen(a, "w");
  assertp(gc_trace);
#endif  

  marking_generation = 1;
  
  /* 
    sprintf (a, "Reclaiming memory...[%ld]\n", total_alloc_mem); 
    emit_stdout(a);
    dump_memory(); 
  */
  total_alloc_mem = 0L;
  pool_first = pool;
  pool_last = pool;
  /* 
    check_allocs(); 
    assert (is_unmarked(top));
    assert (is_unmarked(killable_top));
  */                           

  clear_shadows();            /* clear the shadow instance counters,
                                 in such a way that the marking
                                 stack process will count the number
                                 of instances which are effectively 
                                 accessibles */
  y_mark_once();
  y_mark_stack();   	

  if (kill_required())
    { 
#ifdef Y_TRACE_GC
      fprintf (gc_trace, "\n\n\nRevisiting the whole stuff...\n\n");
#endif     
      kill_killable(marking_generation);
      marking_generation = 2;
      y_mark_once();
      y_mark_stack();
      mark_killables();
    }
    
  free_unmarked(marking_generation);
  clear_killables();
  
#ifdef Y_TRACE_GC
  fprintf (gc_trace, "\n\nGc [%3d] %8ld -> %8ld\n", gc_count, 
                                       old_total_alloc_mem, total_alloc_mem);
  printf ("Gc [%3d] %8ld -> %8ld\n", gc_count, 
                                       old_total_alloc_mem, total_alloc_mem);
  fclose (gc_trace);
#endif     

  if ((total_alloc_mem >= max_alloc_mem) ||
      max_alloc_mem / (max_alloc_mem - total_alloc_mem) > 10)
    { 
      dump_memory_status();
      yafl_err(YERR_NO_MEM);
      emit_stdout ("\nYafl Runtime error: out of memory\n");
      dump_trace();
      exit(1);
    }
  in_gc = 0;
}
/********************************************/
header * get_header YPARAMS2(obj_ptr, p)
{ 
  header * h;

  if (!p)
    {
      dump_trace();
      assert(0);
    }  
  h = ((header *)p)-1;
  return h;
}               
/*****************************************/
unsigned allocation_count YPARAMS0
  {
    return alloc_count;
  }
/*****************************************/
#ifdef Y_TRACE_GC
static int is_initial = 0;

void set_initial(void)
{
  is_initial = TRUE;
}

static int visit_header(header *h)
{
  if (HEADER_ARRAY_LEVEL(h) == 0 || is_initial || 
     (HEADER_ARRAY_LEVEL(h) == 1 && h->dual == &YD_CHAR))
    {
    fprintf (gc_trace, "%c\tVisiting: %s", is_initial ? '.' : ' ',
                                             h->dual->class_name);
    if (HEADER_ARRAY_LEVEL(h) == 1 && h->dual == &YD_CHAR)
      fprintf (gc_trace, "[%d] %s", HEADER_ARRAY_SIZE(h), (obj_ptr)(h+1));    
     else
      fprintf (gc_trace, "[%d]", h->dual->elem_size);    
    fprintf (gc_trace, "\n");
    }
  is_initial = FALSE;
}
#endif      

