#include <stdio.h>
#include <stdlib.h>

#define MaxHeap  10
#define MaxRoot 100
#define empty    -1
#define atom      1u
#define marked	  1u
#define OK	  1
#define head	  0
#define tail	  1
#define Head(p)	  heap[p].info.links[head]
#define Tail(p)	  heap[p].info.links[tail]
#define Value(p)  heap[p].info.value
#define Prev(p)   heap[p].prev
#define Next(p)   heap[p].next
#define Kind(p)   heap[p].kind
#define Mark(p)   heap[p].mark

struct CellRec  {
		unsigned int kind : 1;
		unsigned int mark : 1;
		int prev, next;
		union {
		      int value;	/* value for atom, 		*/
		      int links[2];	/* head and tail for non-atom;	*/
		      } info;
		} heap[MaxHeap];

int roots[MaxRoot], RootCnt = 0;
int FreeList = empty, NonFreeList = empty;


void
detach (int cell, int *list)
{
    if (Next(cell) != empty)
	Prev(Next(cell)) = Prev(cell);
    if (Prev(cell) != empty)
	Next(Prev(cell)) = Next(cell);
    if (cell == *list)  	/* head of the list; */
	*list = Next(cell);
}

void
insert (int cell, int *list)
{
    Prev(cell) = empty;
    if (cell == *list)    /* don't create a circular list */
	 Next(cell) = empty;
    else Next(cell) = *list;
    if (*list != empty)
	Prev(*list) = cell;
    *list = cell;
}

void
transfer(int cell, int *list1, int *list2)
{
    detach(cell,list1);
    insert(cell,list2);
}

void
collect()
{   register int p;
    int ToBeMarkedList = empty, MarkedList  = empty;

    for (p = 0; p < RootCnt; p++) {
	transfer(roots[p],&NonFreeList,&ToBeMarkedList);
	Mark(roots[p]) = marked;
    }
    for (p = ToBeMarkedList; p != empty; p = ToBeMarkedList) {
	transfer(p,&ToBeMarkedList,&MarkedList);
	if (Kind(p) != atom && Mark(Head(p)) != marked) {
	    transfer(Head(p),&NonFreeList,&ToBeMarkedList);
	    Mark(Head(p)) = marked;
	}
	if (Kind(p) != atom && Mark(Tail(p)) != marked) {
	    transfer(Tail(p),&NonFreeList,&ToBeMarkedList);
	    Mark(Tail(p)) = marked;
	}
    }
    for (p = MarkedList; p != empty; p = Next(p))
	Mark(p) = !marked;
    FreeList = NonFreeList;
    NonFreeList = MarkedList;
}

AllocateAux(int p)
{
    if (p == MaxRoot) {
	 printf("No room for new roots\n");
	 return !OK;
    }
    if (FreeList == empty)
	 collect();
    if (FreeList == empty) {
	 printf("No room in heap for new cells\n");
	 return !OK;
    }
    if (p == RootCnt)
	 roots[RootCnt++] = p;
    roots[p] = FreeList;
    transfer(FreeList,&FreeList,&NonFreeList);
    return OK;
}

void
AllocateAtom (int p, int val)		/* an instance of Lisp's setf; */
{
    if (AllocateAux(p) == OK) {
	Kind(roots[p]) = atom;
	Value(roots[p]) = val;
    }
}

void
AllocateList(int p, int q, int r)	/* Lisp's cons; */
{
    if (AllocateAux(p) == OK) {
	Kind(roots[p]) = !atom;
	Head(roots[p]) = roots[q];
	Tail(roots[p]) = roots[r];
    }
}

void
UpdateHead(int p, int q)		/* Lisp's rplaca; */
{
printf("UpdateHead %d %d %d %d ",p,roots[p],q,roots[q]);
    Head(roots[p]) = roots[q];
}

void
UpdateTail(int p, int q)		/* Lisp's rplacd; */
{
printf("UpdateTail %d %d %d %d ",p,roots[p],q,roots[q]);
    Tail(roots[p]) = roots[q];
}

void
program()
{   static int val = 123;
    int rn = rand() % 100;
    int p = rand() % (RootCnt+1); /* possibly new root; */
    int q = rand() % RootCnt;
    int r = rand() % RootCnt;
    if (rn < 20)
	 AllocateAtom(p,val++);
    else if (rn < 90)
	 AllocateList(p,q,r);
    else if (rn < 95 && Kind(roots[q]) != atom)
	 UpdateHead(q,r);  /* zostawic q */
    else if (Kind(roots[q]) != atom)
	 UpdateTail(q,r);
}

PrintList(int list, char *name)
{   int i;

    printf("%s ",name);
    for (i = list; i != empty; i = Next(i))
	printf ("(%d %d %d) ",i,Head(i),Tail(i));
    putchar('\n');
}

PrintHeap()
{   int i;
    printf("roots: ");
    for (i = 0; i < RootCnt; i++)
	printf("%d ",roots[i]);
    putchar('\n');
    for (i = 0; i < MaxHeap; i++)
	printf("(%d %u %u %d %d %d %d) ",i,Kind(i),Mark(i),
					 Prev(i),Next(i),Head(i),Tail(i));
    putchar('\n');
    PrintList(FreeList,"FreeList");
    PrintList(NonFreeList,"NonFreeList");
}

void main()
{   int i;

    for (i = MaxHeap-1; i >= 0; i--) {
	insert(i,&FreeList);
	Mark(i) = !marked;
    }
    AllocateAtom(0,13);		/* to start off:     */
    AllocateAtom(1,14); 	/* create two atoms  */
    AllocateList(2,0,1);	/* and one non-atom; */
    for (i = 0; i < 30; i++) {
	program();
	PrintHeap();
    }
}