/*
 *  SPL - The SPL Programming Language
 *  Copyright (C) 2004, 2005  Clifford Wolf <clifford@clifford.at>
 *
 *  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
 *
 *  gc.c: The SPL garbage collector
 */

#include <stdlib.h>

#include "spl.h"

static int gc_node(int gc_pass, struct spl_node *node)
{
	int size = 1;
	if ( !node ) return 0;

	if ( gc_pass ) {
		if (node->dump_tag != 1) return 0;
		node->dump_tag = 2;
	} else {
		if (node->dump_tag == 1) return 0;
		node->dump_tag = 1;
	}

	size += gc_node(gc_pass, node->ctx);
	size += gc_node(gc_pass, node->cls);

	struct spl_node_sub *s = node->subs_begin;
	while (s) {
		size += gc_node(gc_pass, s->node);
		s = s->next;
	}

	return size;
}

static int gc_task(int gc_pass, struct spl_task *task)
{
	int size = 1;
	size += gc_node(gc_pass, task->ctx);

	struct spl_node_stack *s = task->stack;
	while (s) {
		size += gc_node(gc_pass, s->node);
		s = s->next;
	}

	return size;
}

static int gc_vm(int gc_pass, struct spl_vm *vm)
{
	int size = 1;
	size += gc_node(gc_pass, vm->root);

	struct spl_task *t = vm->task_list;
	while (t) {
		size += gc_task(gc_pass, t);
		t = t->next;
	}

	return size;
}

int spl_gc(struct spl_vm *vm)
{
	struct spl_node *n;
	int old_free_counter = spl_state_counter_free_get();

	vm->gc_last_ic = vm->ic;
	vm->gc_last_allsize = spl_state_counter_malloc_get() - spl_state_counter_free_get();

	n = vm->gc_list;
	if (!n) return 0;

	int size = 0;
	for ((void)0; n; n = n->gc_right) size += gc_node(0, n);
	size += gc_vm(0, vm); gc_vm(1, vm);

	vm->gc_last_treesize = size;

rerun_gc:
	(void)0;

	int i, count = 0;
	for (n = vm->gc_list; n; n=n->gc_right)
		if ( n->dump_tag == 1 ) count++;

	struct spl_node **list = malloc( sizeof(struct spl_node *) * count );

	for (i=0, n = vm->gc_list; n; (void)0)
	{
		struct spl_node *nextn = n->gc_right;
		n->flags &= ~SPL_NODE_FLAG_GC;
		n->gc_left = n->gc_right = 0;
		if ( n->dump_tag == 1 ) {
			list[i++] = n;
			n->ref_counter++;
		}
		n = nextn;
	}

	vm->gc_list=0;

	for (i=0; i<count; i++)
	{
		n = list[i];
		n->dump_tag = 2;

		if ( n->ctx ) {
			spl_put(vm, n->ctx);
			n->ctx = 0;
		}

		if ( n->cls ) {
			spl_put(vm, n->cls);
			n->cls = 0;
		}

		struct spl_node_sub *s = n->subs_begin;
		while (s) {
			struct spl_node_sub *sn = s->next;
			spl_put(vm, s->node);
			if (s->module)
				free(s->module);
			free(s->key);
			free(s);
			s=sn;
		}
		if ( n->subs_hash )
			free(n->subs_hash);
		n->subs_hash = 0;
		n->subs_hash_size = 0;
		n->subs_counter = 0;
		n->subs_begin = 0;
		n->subs_end = 0;

		spl_put(vm, n);
	}

	free(list);
	if (vm->gc_list) goto rerun_gc;

	//note: free counter may have changed in threaded environments;
	return spl_state_counter_free_get() - old_free_counter;
}

int spl_gc_maybe(struct spl_vm *vm)
{
	int treesize = vm->gc_last_treesize < 100 ? 100 : vm->gc_last_treesize;
	if (vm->ic - vm->gc_last_ic > treesize * 128) return spl_gc(vm);
	if (spl_state_counter_malloc_get() - spl_state_counter_free_get() > vm->gc_last_allsize * 2) return spl_gc(vm);
	return -1;
}