/* mem.c: Code to deal with memory management and garbage collection */

/* Copyright (C) 1999 by the Massachusetts Institute of Technology.
 *
 * Permission to use, copy, modify, and distribute this
 * software and its documentation for any purpose and without
 * fee is hereby granted, provided that the above copyright
 * notice appear in all copies and that both that copyright
 * notice and this permission notice appear in supporting
 * documentation, and that the name of M.I.T. not be used in
 * advertising or publicity pertaining to distribution of the
 * software without specific, written prior permission.
 * M.I.T. makes no representations about the suitability of
 * this software for any purpose.  It is provided "as is"
 * without express or implied warranty.
 */

#include <stdlib.h>
#include <string.h>
#include "nawm.h"
#include "lang.h"

/* Failure-protected allocation */

void *xmalloc(size_t size)
{
  void *ptr = malloc(size);
  if (!ptr)
    die("Out of memory.");
  return ptr;
}

void *xrealloc(void *ptr, size_t size)
{
  void *nptr;

  nptr = realloc(ptr, size);
  if (!nptr)
    die("Out of memory.");
  return nptr;
}

char *xstrdup(char *str)
{
  char *dup = strdup(str);
  if (!dup)
    die("Out of memory.");
  return dup;
}


/* Garbage-collected allocation */

typedef struct _mchain {
  void *ptr;
  void (*freer)(void *);
  int refc;
  struct _mchain *next;
} mchain;

static int nchains, ngens, gen;
static mchain **refs, **gens;

void initgc(void)
{
  nchains = ngens = 10;
  refs = xmalloc(nchains * sizeof(mchain *));
  memset(refs, 0, nchains * sizeof(mchain *));
  gens = xmalloc(ngens * sizeof(mchain *));
  gen = -1;
  new_generation();
}

void new_generation(void)
{
  if (++gen == ngens)
    {
      ngens *= 2;
      gens = xrealloc(gens, ngens * sizeof(mchain *));
    }
  gens[gen] = NULL;
}

void end_generation(void)
{
  mchain *m, *mtmp;

  for (m = gens[gen]; m; m = mtmp)
    {
      m->freer(m->ptr);
      mtmp = m->next;
      free(m);
    }
  gen--;
}

void *gcmalloc(size_t size, void (*freeer)(void *))
{
  mchain *m;
  void *ptr = xmalloc(size);

  m = xmalloc(sizeof(mchain));
  m->ptr = ptr;
  m->freer = freeer;
  m->refc = 1;
  m->next = gens[gen];
  gens[gen] = m;

  return ptr;
}

char *gcstrdup(const char *str)
{
  /* Hi, Karl. */
  return strcpy(gcmalloc(strlen(str) + 1, free), str);
}

void *ref(void *ptr)
{
  mchain *m, *mtmp;
  int len, ind = (nawmval)ptr % nchains;

  if (!ptr)
    return ptr;

  for (m = refs[ind], len = 0; m; m = m->next, len++)
    {
      if (m->ptr == ptr)
	{
	  m->refc++;
	  return ptr;
	}
    }

  if (len > 10)
    {
      int nsize, i;
      mchain **nelts;

      /* Need to reorganize */
      nsize = (nchains + 1) * 2 + 1;
      nelts = xmalloc(nsize * sizeof(mchain *));
      memset(nelts, 0, nsize * sizeof(mchain *));

      for (i = 0; i < nchains; i++)
	{
	  for (m = refs[i]; m; m = mtmp)
	    {
	      mtmp = m->next;
	      ind = (nawmval)m->ptr % nsize;
	      m->next = nelts[ind];
	      nelts[ind] = m;
	    }
	}
      free(refs);
      refs = nelts;
      nchains = nsize;
      ind = (nawmval)ptr % nchains;
    }

  for (m = gens[gen], mtmp = NULL; m; mtmp = m, m = m->next)
    {
      if (m->ptr == ptr)
	break;
    }
  if (!m)
    die("GC botch (ref 0x%lx)", ptr);
  if (mtmp)
    mtmp->next = m->next;
  else
    gens[gen] = m->next;

  m->next = refs[ind];
  refs[ind] = m;

  return ptr;
}

void unref(void *ptr)
{
  mchain *m, *mprev;
  int ind = (nawmval)ptr % nchains;

  if (!ptr)
    return;

  for (m = refs[ind], mprev = NULL; m; mprev = m, m = m->next)
    {
      if (m->ptr == ptr)
	{
	  if (--m->refc)
	    return;
	  if (mprev)
	    mprev->next = m->next;
	  else
	    refs[ind] = m->next;
	  m->freer(ptr);
	  free(m);
	  return;
	}
    }

  /* Allow unref of never-reffed pointer. */
  for (ind = gen; ind >= 0; ind--)
    {
      for (m = gens[ind]; m; m = m->next)
	{
	  if (m->ptr == ptr)
	    return;
	}
    }

  die("GC botch! (unref 0x%lx)", ptr);
}