List-based n-queens solver with mark-sweep GC written in C++

gistfile1.cpp

#include <vector>
#include <iostream>
#include <stdio.h>
#include <tchar.h>
#include <windows.h>
#include "Allocator.h"
#include "MarkSweep.h"

#define OPTIMIZED
#define SHADOWSTACK

#ifdef SHADOWSTACK
#define SAVE int stackDepth = shadowStack.size()
#define RESTORE shadowStack.resize(stackDepth)
//#define SAVE int stackDepth = shadowStack.size(); Ref *oldSP=sp
//#define RESTORE shadowStack.resize(stackDepth); sp=oldSP
#else
#define SAVE
#define RESTORE
#endif

using namespace std;
using namespace Allocator;

/// Shadow stack.
vector<Ref *> shadowStack;

/// Mark every reference on the shadow stack.
void roots(void (* root)(Ref *)) {
	for (vector<Ref *>::iterator it=shadowStack.begin(); it!=shadowStack.end(); ++it)
		root(*it);
}

/// Read barrier.
Ref *gcLocalRef(Ref *r) {
#ifdef SHADOWSTACK
	if (r) shadowStack.push_back(r);
#endif
	return r;
}

/// A board position.
typedef pair<char, char> coord;

/// A cons cell.
typedef pair<coord, Ref *> Cons;

/// The empty list.
Ref *empty = NULL;

/// Visit function for a cons cell.
void visitCons(Ref *r, void (* root)(Ref *r)) {
	Ref *t = ((Cons *)(r->data))->second;
	if (t) root(t);
}

vector<Cons *> freeList;

/// Finalizer deallocates the data that a reference points to.
void finalizeCons(Ref *r) {
	*(Cons *)r->data = Cons();
	freeList.push_back((Cons *)r->data);
}

/// Construct a cons cell.
// This would be generated inline so we do not decorate with SAVE, RESTORE etc.
Ref *cons(coord h, Ref *t) {
	Cons *r;
	if (freeList.size() > 0)
	{
		r = freeList.back();
		freeList.pop_back();
		*r = Cons(h, t);
	}
	else
		r = new Cons(h, t);
	return allocRef(&visitCons, &finalizeCons, r);
}

int quota = 0, gcCycles = 0;

void gcCollect() {
#ifdef SHADOWSTACK
	++gcCycles;
	gc(roots);
	quota = 4 * count();
#endif
}

/// Is one position safe from a queen at another position.
bool safe(coord a, coord b) {
	return a.first!=b.first && a.second!=b.second &&
		a.first+a.second!=b.first+b.second && a.first-a.second!=b.first-b.second;
}

/// Filter safe positions from a list of positions.
/*
Function("filter", Tuple["q", Tuple[Int; Int]; "list", Ref],
			If(Var "list" <>. NULL,
				
*/
Ref *filter(coord q, Ref *list) {
#ifndef OPTIMIZED
	SAVE;
	gcLocalRef(list);
	//cout << stackDepth << " " << list << endl;
	if (list)
		{
			Cons node = *(Cons *)list->data;
			gcLocalRef(node.second);
			if (safe(q, node.first))
			{
				Ref *list2 = gcLocalRef(filter(q, node.second)); // Not needed
				RESTORE; // Restore before tail call
				return cons(node.first, list2); // Not needed.
			}
			else
			{
				RESTORE; // Restore before tail call
				return filter(q, node.second); // Tail call
			}
		}
	RESTORE;
	return empty;
#else
	if (!list) return empty;

	if (count() > quota) {
		gcLocalRef(list);
		gcCollect();
	}

	Cons node = *(Cons *)list->data;
	coord xy = node.first;
	Ref *tail = node.second;
	// Remainder uses node.second
	SAVE;
	gcLocalRef(tail);
	if (safe(q, node.first))
	{
		Ref *list2 = filter(q, tail);
		RESTORE; // TCO
		return cons(xy, list2);
	}
	else
	{
		RESTORE; // TCO
		return filter(q, tail);
	}
#endif
}

/// Search for solutions to the n-queens problem.
int search(int n, int nqs, Ref *qs, Ref *ps, int i) {
#ifndef OPTIMIZED
	SAVE;
	gcLocalRef(qs);
	gcLocalRef(ps);
	if (!ps)
	{
		RESTORE;
		return (nqs==n ? i+1 : i);
	}
	coord q = ((Cons *)ps->data)->first;
	Ref *ps2 = gcLocalRef(((Cons *)ps->data)->second);
	Ref *qs2 = gcLocalRef(cons(q, qs));
	Ref *ps3 = gcLocalRef(filter(q, ps2));
	int i2 = search(n, nqs+1, qs2, ps3, i);
	RESTORE;
	return search(n, nqs, qs, ps2, i2); // Tail call
#else
	if (!ps) return (nqs==n ? i+1 : i);
	// Remaining code uses qs and ps2 (but not ps)
	SAVE;
	gcLocalRef(qs);

	if (count() > quota) {
		gcLocalRef(ps);
		gcCollect();
	}

	coord q = ((Cons *)ps->data)->first;
	Ref *ps2 = gcLocalRef(((Cons *)ps->data)->second); // Must keep for final call
	Ref *qs2 = cons(q, qs); // Callee will push
	Ref *ps3 = filter(q, ps2); // Callee will push
	int i2 = search(n, nqs+1, qs2, ps3, i);
	RESTORE;
	return search(n, nqs, qs, ps2, i2); // Tail call
#endif
}

/// Construct a list of all board positions.
Ref *ps(int n) {
	Ref *list = empty;
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=n; ++j)
			list = cons(coord(i, j), list);
	return list;
}

int main() {
	__int64 freq, tStart, tStop;
	unsigned long TimeDiff;
	QueryPerformanceFrequency((LARGE_INTEGER *)&freq);
	QueryPerformanceCounter((LARGE_INTEGER *)&tStart);

	for (int n=1; n<11; ++n) {
		cout << search(n, 0, empty, ps(n), 0) << " solutions to the " << n << "-queens problem" << endl;
		cout << "Used " << count() << " references" << endl;
		//cout << "Marking " << shadowStack.size() << " global roots" << endl;
		gc(roots);
		//cout << "Used " << count() << " references" << endl;
		cout << "Ran " << gcCycles << " GC cycles" << endl;
	}

	QueryPerformanceCounter((LARGE_INTEGER *)&tStop);
	TimeDiff = (unsigned long)(((tStop - tStart) * 1000000) / freq);
	cout << "Took " << TimeDiff/1e6 << "s" << endl;
	getc(stdin);
	return 0;
}