<![CDATA[import java.util.Random;
class Value {
int value;
Value(int v) {
value = v;
}
}
class Links {
int head = -1, tail = -1;
Links(int h, int t) {
head = h; tail = t;
}
}
class Cell {
boolean atom;
boolean marked = false;
int prev = -1, next = -1;
Object info = null; // either Value or Links;
}
class Heap {
final int maxHeap = 6, maxRoot = 50, empty = -1;
int rootCnt = 0;
boolean OK = true;
Cell[] heap = new Cell[maxHeap];
int[] roots = new int[maxRoot];
int freeCells = empty, nonFreeCells = empty;
Random rd = new Random(10);
Heap() {
for (int i = maxHeap-1; i >= 0; i--) {
heap[i] = new Cell();
freeCells = insert(i,freeCells);
}
for (int i = maxRoot-1; i >= 0; i--)
roots[i] = empty;
}
void updateHead(int p, int q) { // Lisp's rplaca;
if (roots[p] != empty && !heap[roots[p]].atom)
((Links)heap[roots[p]].info).head = roots[q];
}
void updateTail(int p, int q) { // Lisp's rplacd;
if (roots[p] != empty && !heap[roots[p]].atom)
((Links)heap[roots[p]].info).tail = roots[q];
}
int detach(int cell, int list) {
if (heap[cell].next != empty)
heap[heap[cell].next].prev = heap[cell].prev;
if (heap[cell].prev != empty)
heap[heap[cell].prev].next = heap[cell].next;
if (cell == list) // head of the list;
return heap[cell].next;
else return list;
}
int insert(int cell, int list) {
heap[cell].prev = empty;
if (cell == list) // don't create a circular list;
heap[cell].next = empty;
else heap[cell].next = list;
if (list != empty)
heap[list].prev = cell;
return cell;
}
void collect() {
int p, markDescendants = empty, markedCells = empty;
for (p = 0; p < rootCnt; p++) {
if (roots[p] != empty) {
nonFreeCells = detach(roots[p],nonFreeCells);
markDescendants = insert(roots[p],markDescendants);
heap[roots[p]].marked = true;
}
}
printList(markDescendants,"markDescendants C1 "+p);
for (p = markDescendants; p != empty; p = markDescendants) {
markDescendants = detach(p,markDescendants);
markedCells = insert(p,markedCells);
if (!heap[p].atom) {
if (!heap[((Links)heap[p].info).head].marked) {
nonFreeCells = detach(((Links)heap[p].info).head,nonFreeCells);
markDescendants = insert(((Links)heap[p].info).head,markDescendants);
heap[((Links)heap[p].info).head].marked = true;
}
if (!heap[((Links)heap[p].info).tail].marked) {
nonFreeCells = detach(((Links)heap[p].info).tail,nonFreeCells);
markDescendants = insert(((Links)heap[p].info).tail,markDescendants);
heap[((Links)heap[p].info).tail].marked = true;
}
}
}
printList(markedCells,"MarkedCells");
for (p = markedCells; p != empty; p = heap[p].next)
heap[p].marked = false;
freeCells = nonFreeCells;
nonFreeCells = markedCells;
}
boolean allocateAux(int p) {
if (p == maxRoot) {
System.out.println("No room for new roots");
return !OK;
}
if (freeCells == empty)
collect();
if (freeCells == empty) {
System.out.println("No room in heap for new cells");
return !OK;
}
if (p == rootCnt)
rootCnt++;
roots[p] = freeCells;
//System.out.print("roots2: "+p+" "+rootCnt+" "); for (int i = 0; i < rootCnt; i++) System.out.print(roots[i] + " "); System.out.println();
freeCells = detach(roots[p],freeCells);
nonFreeCells = insert(roots[p],nonFreeCells);
return OK;
}
void allocateAtom (int p, int val) { // an instance of Lisp's setf;
//System.out.println("a t o m (" + p + " " + roots[p] + " " + val + " " + rootCnt);
if (allocateAux(p) == OK) {
heap[roots[p]].atom = true;
heap[roots[p]].info = new Value(val);
}
}
void allocateNonAtom(int p, int q, int r) { // Lisp's cons;
if (allocateAux(p) == OK) {
heap[roots[p]].atom = false;
heap[roots[p]].info = new Links(roots[q],roots[r]);
}
}
void deallocate(int p) {
if (rootCnt > 0)
if (Math.abs(rd.nextInt()) % 2 == 0)
roots[p] = roots[--rootCnt]; // remove variable when exiting a block;
else roots[p] = empty; // set variable to null;
}
void printList(int list, String name) {
System.out.print(name + ": ");
int i;
for (i = list; i != empty; i = heap[i].next) {
System.out.print("(" + i + " ");
if (heap[i].atom)
System.out.print(((Value)heap[i].info).value);
else if (heap[i].info != null)
System.out.print(((Links)heap[i].info).head + " " +
((Links)heap[i].info).tail);
System.out.print(") ");
}
System.out.println();
}
void printHeap() {
System.out.print("roots: ");
for (int i = 0; i < rootCnt; i++)
System.out.print(roots[i] + " ");
System.out.println();
for (int i = 0; i < maxHeap; i++) {
System.out.print("(" + i + ": " + heap[i].prev + " "
+ heap[i].next + " "+ heap[i].atom + " " + heap[i].marked + " ");
if (heap[i].atom)
System.out.print(((Value)heap[i].info).value);
else if (heap[i].info != null)
System.out.print(((Links)heap[i].info).head + " " +
((Links)heap[i].info).tail);
System.out.print(") ");
}
System.out.println();
printList(freeCells,"FreeCells");
printList(nonFreeCells,"NonFreeCells");
}
}
]]>