Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save samrat/84fdb2ffb683a9d0bc50b1b41ab265c6 to your computer and use it in GitHub Desktop.
Save samrat/84fdb2ffb683a9d0bc50b1b41ab265c6 to your computer and use it in GitHub Desktop.
List-based n-queens solver with mark-sweep GC written in C++
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment