← | ↑ |
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.
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.
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.
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).
Scan the entire array of nodes, setting all of the mark bits to 0.
Call markall(t) for each tree t in the symbol table.
Call markall(*p) for each pointer p that is in the remember-list.
Scan the entire array of nodes. Each node that has a mark bit of 0 is inaccessible. Add it to the free space list.
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