shithub: pprolog

ref: 13efe91101a11f41caf6321a8b2fbdd96ef9927a
dir: pprolog/garbage.c

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

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

#define TableSize (1<<16)

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

static int hash(void *);
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 void markoperators(Operator *);

static Allocation *allocationtab[TableSize];

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

	a->next = allocationtab[hash(a->data)];
	if(a->next)
		a->next->prev = a;
	allocationtab[hash(a->data)] = a;

	return a->data;
}

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

	/* Start by marking all allocations as unreachable */
	int i;
	for(i = 0; i < TableSize; i++){
		for(a = allocationtab[i]; 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 */
	for(i = 0; i < TableSize; i++){
		a = allocationtab[i];
		while(a != nil){
			if(a->reachable)
				a = a->next;
			else{
				Allocation *tmp = a;
				collected += a->size;
				a = a->next;
				freealloc(tmp);
			}
		}
	}
	return collected;
}

static int
hash(void *i)
{
	return (uintptr)i % TableSize;
}

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

	Allocation *a;
	for(a = allocationtab[hash(ptr)]; 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
		allocationtab[hash(a->data)] = a->next;

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

static void 
markmodules(void)
{
	Module *m;
	int i;
	for(m = modules; m != nil; m = m->next){
		mark(m);
		markpredicates(m->predicates);
		for(i = 0; i < PrecedenceLevels; i++)
			markoperators(m->operators[i]);
	}
}

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);
	}
}

static void
markoperators(Operator *ops)
{
	Operator *op;
	for(op = ops; op != nil; op = op->next)
		mark(op);
}