Garbage collection

←

↑

Garbage Collection

Your current implementation will go through memory very quickly. This assignment has you recycle unused memory.

Create files src/gc.c and src/gc.h to hold the garbage collector.

When the program starts, create a large array of tree nodes. You will need to make an arbitrary choice about how large this array is, but make it easy to change that arbitrary choice by defining the array size to be a named constant.
Link all of the tree nodes in the array together into a linked list (for example, using their s1 pointers). That list is called the free space list.
Write a function to allocate a tree node. It should get the first node from the free space list, and remove that node from the list. If there are no more nodes in the free space list then it should call function GarbageCollect(), which can initially be a stub, and try again. If it still can't get a node after calling GarbageCollect it should print a message that the program is out of memory and stop the program.
Modify the tree module so that, whenever it needs a tree node, it calls the function written above to get a node from the free space list. Test your program to ensure that it still works.
Add a field to the tree nodes called the mark bit. It needs to be able to hold 0 or 1.
Create a linked list of tree** pointers. It will hold pointers to local variables in functions that point to trees that need to be remembered. This list should initially be empty.
Write a function getMark() that returns a pointer to the current front of the linked list (or that returns NULL if the linked list is empty).
Write function remember(p) adds tree** pointer p to the beginning of the linked list, and returns a pointer to the list cell that was formerly the start of the linked list, or that returns NULL if the list used to be empty.
Write function forget(q) that takes a pointer that was returned by remember and removes all list cells up to but not including the one pointed to by q from the list.
Modify your functions that work on trees. When a function starts it should do something like
```
  RememberList* mark = getMark();
```
to remember where things were. After it stores a tree into variable t, it should do
```
  remember(&t);
```
to ensure that the tree will be visible to the garbage collector. (If a function changes what is in a variable that has already been remembered, it should not remember that variable again.) When the function is finished, it should do
```
  forget(mark);
```
to remove things that were stored here. It is very important that you do this forget call in every function that did any remember calls.
Write a function markall(t) that sets the mark bit to 1 for every node in tree t. If it encounters a node that is already marked, then markall should skip that node.

If the root of t is not already marked, markall(t) should start by setting the mark bit of the root to 1. Then it should call itself on all subtrees. Use the node kind to determine the subtrees (if any).
Write GarbageCollect. It should work as follows.
1. Scan the entire array of nodes, setting all of the mark bits to 0.
2. Call markall(t) for each tree t in the symbol table.
3. Call markall(*p) for each pointer p that is in the remember-list.
4. Scan the entire array of nodes. Each node that has a mark bit of 0 is inaccessible. Add it to the free space list.

Submitting your work

When you have this working, submit it using the following command.

  ~abrahamsonk/5220/bin/submit gc gc.h gc.c parser.y lexer.lex lexer.h token.h ast.c ast.h symboltable.c symboltable.h stringtable.c stringtable.h interpreter.c interpreter.h simplify.c simplify.y