shithub: pprolog

ref: 28e7dd47d568908702264977d70860c25467fb6e
dir: /garbage.c/

#include <u.h>
#include <libc.h>
#include <bio.h>

#include "dat.h"
#include "fns.h"

typedef struct Allocation Allocation;
struct Allocation
{
	ulong size;
	int reachable;
	void *data;
	Allocation *next;
	Allocation *prev;
};

static void mark(void *);
static void freealloc(Allocation *);
static void markmodules(void);
static void markgoalstack(Goal *);
static void markchoicestack(void);
static void markpredicates(Predicate *);
static void markclauses(Clause *);
static void markterm(Term *);
static void markbindings(Binding *);

static Allocation *allocations;

void *
gmalloc(ulong size)
{
	Allocation *a = malloc(sizeof(Allocation));
	a->size = size;
	a->reachable = 1;
	a->data = malloc(size);
	a->prev = nil;
	a->next = allocations;
	if(allocations)
		allocations->prev = a;
	allocations = a;

	return a->data;
}

vlong
collectgarbage(void)
{
	ulong collected = 0;
	Allocation *a;

	/* Start by marking all allocations as unreachable */
	for(a = allocations; a != nil; a = a->next)
		a->reachable = 0;

	/* Go through root pointers and mark all allocations found as reachable.
	   The root pointers are:
		1) The modules
		2) The goalstack
		3) The choicestack
	*/
	markmodules();
	markgoalstack(goalstack);
	markchoicestack();

	/* Free the allocations that were not marked as reachable */
	a = allocations;
	while(a != nil){
		if(a->reachable)
			a = a->next;
		else{
			Allocation *tmp = a;
			collected += a->size;
			a = a->next;
			freealloc(tmp);
		}
	}
	return collected;
}

static void
mark(void *ptr)
{
	if(ptr == nil)
		return;

	Allocation *a;
	for(a = allocations; a != nil; a = a->next){
		if(a->data == ptr)
			a->reachable = 1;
	}
}

static void
freealloc(Allocation *a)
{
	if(a->prev)
		a->prev->next = a->next;
	else
		allocations = a->next;

	if(a->next)
		a->next->prev = a->prev;
	free(a->data);
	free(a);
}

static void 
markmodules(void)
{
	Module *m;
	for(m = modules; m != nil; m = m->next){
		mark(m);
		markpredicates(m->predicates);
	}
}

static void 
markgoalstack(Goal *goals)
{
	Goal *g;
	for(g = goals; g != nil; g = g->next){
		mark(g);
		markterm(g->goal);
		markterm(g->catcher);
	}
}

static void 
markchoicestack(void)
{
	Choicepoint *c;
	for(c = choicestack; c != nil; c = c->next){
		mark(c);
		markgoalstack(c->goalstack);
		markclauses(c->alternative);
		markbindings(c->altbindings);
	}
}

static void
markpredicates(Predicate *preds)
{
	Predicate *p;
	for(p = preds; p != nil; p = p->next){
		mark(p);
		markclauses(p->clauses);
	}
}

static void
markclauses(Clause *clauses)
{
	Clause *c;
	for(c = clauses; c != nil; c = c->next){
		mark(c);
		markterm(c->head);
		markterm(c->body);
	}
}

static void
markterm(Term *term)
{
	Term *t;
	for(t = term; t != nil; t = t->next){
		mark(t);
		markterm(t->children);
	}
}

static void
markbindings(Binding *bindings)
{
	Binding *b;
	for(b = bindings; b != nil; b = b->next){
		mark(b);
		markterm(b->value);
	}
}