Reference Counting

pub fn reference$\_$counting$($filename: &str$)->$ RefCountMem

This function inputs a text file with a list of actions taken by a program and outputs the memory layout after the program fully executes.

You Will: Build a heap with reference counts for all the data in the file, as well as the corresponding stack.

We give you a read$\_$lines function that takes in a &str and iterates through the lines of the file for you. We also handle the Regex and File I$/$O for you, so all you have to do is implement the logic at each todo! in the file. The comments in this function should guide you.

Important

For reference$\_$counting only, we are going to say that the heap you should create is a set size of $10.$ In every other function, you may be given heaps of any size, and they will remain that size.

Note the main difference between RefCountMem and Memory is that RefCountMem has a place for the reference count rather than the name of the memory address.

There are $2$ possible actions that can be done.

We can:

Ref$($erence$)$ memory from the stack or heap

Pop Removes the most recent stack frame

Ref Heap $<0$ or more integers$>$ allocates memory in the heap in index integer$1.$ In this memory, there should be an option that contains a list with each of the subsequent integers. This is creating references between integer$1$ and all subsequent integers.

Ref Stack $<0$ or more integers$>$ Should add an element to the stack, which references the data on the heap represented by the integer$($s$)$

Pop Removes the most recent stack frame.

If memory is allocated to somewhere on the heap that is not referenced by anything, you can safely "ignore" that line $($It$\text{'}$s reference count would be $0,$ so it would be immediately deallocated$).$ You may also ignore lines that Pop after all stack frames have been removed. Neither of these will result in errors, though.

You will return the RefCountMem struct representing the state of memory after all of the program actions have been taken. See About Memory for more info on this struct and what it represents. If the reference count ever reaches $0,$ deallocate that memory $($change it to None$).$

If an index on the heap is referenced, but never references anything itself, it will be Some$([],)$

Examples:

basic.txt:

Ref Stack $2$ Ref Heap $2034$ Ref Stack $0$ Ref Stack $89$ Ref Heap $052$ Pop Pop

Diagram of each step:

Before any step

Ref Stack $2$

Ref Heap $2034$

Ref Stack $0$

Ref Stack $89$

Ref Heap $052$

Pop

Pop

$//$ reference$\_$counting$("$basic$.$txt$")$ returns RefCountMem $\{$ stack: vec!$[$vec$![2]],$ heap: vec!$[($Some$($vec$![5,2]),1),($None$,0),($Some$($vec$![0,3,4]),2),($Some$($vec$![]),1),($Some$($vec$![]),1),($Some$($vec$![]),1),($None$,0),($None$,0),($None$,0),($None$,0)],\}$

example$2.$txt:

Ref Stack $01$ Ref Heap $1325$ Pop

Ref Stack $01$

Ref Heap $1325$

Pop $($including each free step$)$

This will return:

$//$ reference$\_$counting$("$basic$.$txt$")$ returns RefCountMem $\{$ stack: vec!$[],$ heap: vec!$[($None$,0),($None$,0),($None$,0),($None$,0),($None$,0),($None$,0),($None$,0),($None$,0),($None$,0),($None$,0)],\}$

Mark and Sweep