/* DLIFE Copyright (C) 2000 Richard W.M. Jones <rich@annexia.org>
 * and other authors listed in the ``AUTHORS'' file.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * $Id: soup.c,v 1.2 2002/04/05 16:47:13 rich Exp $
 */

#include "config.h"

#include <stdio.h>
#include <stdlib.h>

#ifdef HAVE_UNISTD_H
#include <unistd.h>
#endif

#ifdef HAVE_ASSERT_H
#include <assert.h>
#endif

#include "types.h"
#include "soup.h"
#include "cell.h"
#include "random.h"
#include "state.h"
#include "crc.h"

#define TRACE_SOUP_ALLOCATIONS 0

void
soup_init (struct state *state, int _soup_size)
{
  int i;

  state->soup_size = _soup_size;
  state->soup_free = _soup_size;
  state->soup = malloc (_soup_size);
  if (state->soup == 0) { perror ("malloc"); abort (); }

  /* Fill the soup with entropy. */
  for (i = 0; i < _soup_size; ++i)
    {
      state->soup[i] = get_rand_byte ();
    }
}

/* Allocate a new fragment of soup. */
struct soup_frag *
soup_frag_malloc (struct state *state,
		  struct soup_frag *mother_frag, reg_t len)
{
  struct soup_frag *p, *t;
  int offset;
  int is_first_cell = state->soup_free == state->soup_size;

#if TRACE_SOUP_ALLOCATIONS
  printf ("soup alloc: want %d bytes ", len);
#endif

  p = malloc (sizeof (struct soup_frag));
  if (p == 0) { perror ("malloc"); abort (); }

  /* Common fields. */
  p->len = len;
  state->soup_free -= len;

  /* The first cell is allocated specially. */
  if (is_first_cell)
    {
      p->next = p;
      p->prev = p;
      p->base = 0;

#if TRACE_SOUP_ALLOCATIONS
      printf ("first cell 0 OK\n");
#endif

      return p;
    }

  /* If a cell has no parent, we can insert it anywhere. */
  if (mother_frag == 0)
    {
      /* Need to go and grab a cell at random, then search indefinitely
       * for a free space.
       */
      mother_frag = _cell_get_any_frag (state);
      t = mother_frag;
      offset = 0;

      do
	{
	  int diff;

#if TRACE_SOUP_ALLOCATIONS
	  printf ("[%d,%d:%d,%d] ",
		  t->base, t->base + t->len,
		  t->next->base, t->next->base + t->next->len);
#endif

	  /* Handle the wrap-around case gracefully. */
	  if (t->next->base > t->base)
	    diff = t->next->base - (t->base + t->len);
	  else
	    diff = t->next->base - (t->base + t->len) + state->soup_size;

	  /* Is there space after this fragment? */
	  if (diff >= len)
	    {
	      /* Yes: insert the cell here. */
	      p->prev = t;
	      p->next = t->next;
	      p->base = (t->base + t->len) & (state->soup_size-1);
	      t->next->prev = p;
	      t->next = p;

#if TRACE_SOUP_ALLOCATIONS
	      printf ("%d OK\n", p->base);
#endif

	      return p;
	    }

	  offset += diff + t->len;
	  t = t->next;
	}
      while (offset <= state->soup_size && t != mother_frag);

      /* No space for it. */
      state->soup_free += len;
      free (p);

#if TRACE_SOUP_ALLOCATIONS
      printf ("FAILED\n");
#endif

      return 0;
    }

  /* Find a suitable fragment near the mother. */

  /* Search forwards first. */
  t = mother_frag;
  offset = 0;
  do
    {
      int diff;

#if TRACE_SOUP_ALLOCATIONS
      printf ("[%d,%d:%d,%d] ",
	      t->base, t->base + t->len,
	      t->next->base, t->next->base + t->next->len);
#endif

      /* Handle the wrap-around case gracefully. */
      if (t->next->base > t->base)
	diff = t->next->base - (t->base + t->len);
      else
	diff = t->next->base - (t->base + t->len) + state->soup_size;

      /* Is there space after this fragment? */
      if (diff >= len)
	{
	  /* Yes: insert the cell here. */
	  p->prev = t;
	  p->next = t->next;
	  p->base = (t->base + t->len) & (state->soup_size-1);
	  t->next->prev = p;
	  t->next = p;

#if TRACE_SOUP_ALLOCATIONS
  printf ("%d OK\n", p->base);
#endif

	  return p;
	}

      offset += diff + t->len;
      t = t->next;
    }
  while (offset <= MAX_SPAWN_DISTANCE && t != mother_frag);

  /* Search backwards. */
  t = mother_frag;
  offset = 0;
  do
    {
      int diff;

#if TRACE_SOUP_ALLOCATIONS
      printf ("[%d,%d:%d,%d] ",
	      t->prev->base, t->prev->base + t->prev->len,
	      t->base, t->base + t->len);
#endif

      /* Handle the wrap-around case gracefully. */
      if (t->prev->base < t->base)
	diff = t->base - (t->prev->base + t->prev->len);
      else
	diff = t->base - (t->prev->base + t->prev->len) + state->soup_size;

      /* Is there space before this fragment? */
      if (diff >= len)
	{
	  /* Yes: insert the cell here. */
	  p->prev = t->prev;
	  p->next = t;
	  p->base = (t->base - len) & (state->soup_size-1);
	  p->len = len;
	  t->prev->next = p;
	  t->prev = p;

#if TRACE_SOUP_ALLOCATIONS
  printf ("%d OK\n", p->base);
#endif

	  return p;
	}

      offset += diff + t->prev->len;
      t = t->prev;
    }
  while (offset <= MAX_SPAWN_DISTANCE && t != mother_frag);

  /* No space for it. */
  state->soup_free += len;
  free (p);

#if TRACE_SOUP_ALLOCATIONS
  printf ("FAILED\n");
#endif

  return 0;
}

/* Free up a soup fragment. */
void
soup_frag_free (struct state *state,
		struct soup_frag *frag)
{
  /* NB. We ignore the case of freeing up the single last remaining
   * fragment, since that should never happen in real life.
   */
  frag->next->prev = frag->prev;
  frag->prev->next = frag->next;

  state->soup_free += frag->len;

  free (frag);
}

/* Compute the CRC for a frag. */
crc_t
soup_frag_compute_crc32 (const struct state *state,
			 const struct soup_frag *frag)
{
  /* Take care of the case where a cell straddles the end of the soup. */
  if (frag->base + frag->len <= state->soup_size)
    {
      return compute_crc32 (state->soup + frag->base, frag->len);
    }
  else
    {
      crc_t crc = compute_crc32 (state->soup + frag->base,
				 state->soup_size - frag->base);
      return incr_compute_crc32 (crc, state->soup,
				 frag->len - (state->soup_size - frag->base));
    }

}

/* This function checks that the soup is consistent. We are passed
 * one fragment (at random) and walk the circular linked list,
 * examining the fragments to ensure they are in order and do not
 * overlap.
 */
void
soup_check (struct state *state)
{
  const struct soup_frag *start_frag = _cell_get_any_frag (state);
  const struct soup_frag *frag = start_frag;
  int nr_frags = 0;
  int soup_free = state->soup_size;

  do
    {
      assert (0 <= frag->base && frag->base < state->soup_size);
      assert (frag->len > 0);

      assert (frag->next->prev == frag);
      assert (frag->prev->next == frag);

      if (frag->prev->base < frag->base)
	assert (frag->prev->base + frag->prev->len <= frag->base);
      else
	assert (frag->prev->base + frag->prev->len <= frag->base + state->soup_size);

      if (frag->base < frag->next->base)
	assert (frag->base + frag->len <= frag->next->base);
      else
	assert (frag->base + frag->len <= frag->next->base + state->soup_size);

      soup_free -= frag->len;

      frag = frag->next;
      nr_frags++;
    }
  while (frag != start_frag);

  assert (nr_frags == state->nr_cells_allocated);
  assert (soup_free == state->soup_free);
}

/* Dump the soup and soup structures out to a file. This function is
 * non-destructive.
 */
void
soup_state_save (struct state *state, FILE *fp)
{
  struct soup_frag *start_frag, *frag;

  /* Write out the size of the soup. */
  fwrite (&state->soup_size, sizeof state->soup_size, 1, fp);
  fwrite (&state->soup_free, sizeof state->soup_free, 1, fp);

  /* Write out the soup itself. */
  fwrite (state->soup, 1, state->soup_size, fp);

  /* Write out the number of fragments. Note that this is the same
   * as the number of allocated cells.
   */
  fwrite (&state->nr_cells_allocated,
	  sizeof state->nr_cells_allocated, 1, fp);

  /* Write out the fragment list. */
  frag = start_frag = _cell_get_any_frag (state);
  do
    {
      fwrite (frag, sizeof (struct soup_frag), 1, fp);

      frag = frag->next;
    }
  while (frag != start_frag);
}

/* Load the soup state from a previously saved file. */
void
soup_state_load (struct state *state, FILE *fp)
{
  int _soup_size, nr_frags, i;
  struct soup_frag *first_frag = 0, *prev_frag = 0;

  /* Load the size of the soup expected. */
  if (fread (&_soup_size, sizeof _soup_size, 1, fp) != 1)
    {
      fprintf (stderr, "error in soup state\n");
      abort ();
    }
  if (state->soup_size != _soup_size)
    {
      fprintf (stderr, "soup size doesn't match - can't load this soup image\n");
      abort ();
    }
  if (fread (&state->soup_free, sizeof state->soup_free, 1, fp) != 1)
    {
      fprintf (stderr, "error in soup state\n");
      abort ();
    }
  if (state->soup_free > state->soup_size)
    {
      fprintf (stderr, "soup free > soup_size - can't load this soup image\n");
      abort ();
    }

  /* Load the soup itself. */
  if (fread (state->soup, 1, _soup_size, fp) != _soup_size)
    {
      fprintf (stderr, "error in soup state\n");
      abort ();
    }

  /* Load the number of fragments expected. */
  if (fread (&nr_frags, sizeof nr_frags, 1, fp) != 1)
    {
      fprintf (stderr, "error in soup state\n");
      abort ();
    }
  if (nr_frags != state->nr_cells_allocated)
    {
      fprintf (stderr, "nr_frags != nr_cells_allocated - can't load this soup image\n");
      abort ();
    }

  /* Load each fragment. */
  for (i = 0; i < nr_frags; ++i)
    {
      struct soup_frag *p;

      p = malloc (sizeof (struct soup_frag));
      if (p == 0) { perror ("malloc"); abort (); }

      if (fread (p, sizeof (struct soup_frag), 1, fp) != 1)
	{
	  fprintf (stderr, "error in soup state\n");
	  abort ();
	}

      if (i == 0)
	first_frag = p;

      /* Find the cell which references this fragment and fix it up. */
      _cell_fixup_soup_ref (state, p->base, p);

      /* Join the fragments to form a circular linked list. */
      if (prev_frag)
	{
	  p->prev = prev_frag;
	  p->prev->next = p;
	}

      prev_frag = p;
    }

  /* Finish off the circular linked list. */
  first_frag->prev = prev_frag;
  prev_frag->next = first_frag;
}