Due: Friday, May 1, 2026, at 10pm

Starter code: p2_talloc.zip or p2_talloc.tar
Upload solutions via Gradescope

Goals

This assignment is designed to help you with the following:

• continuing the foundation of your interpreter project
• more practice, as always, with pointers, memory, and C

Collaboration policy

For this assignment, you may work alone or with a partner, but you must type up all of the code yourself. (It is therefore unexpected for two code submissions to be completely identical.)

If you worked with a partner for P1, you must work with the same partner or work alone for P2.

You may also discuss the assignment at a high level with other students.

You should list any student with whom you discussed the assignment, and the manner of discussion (high level, partner, etc.) in your readme.txt file.

If you work alone, you should say so instead.

Assessment

Core requirements:

• all CR tests pass
• a visual inspection of your code shows that you have not hyper-tailored it to pass the tests
• readme.txt contains your collaboration statement, sources, and reflection

Note that hyper-tailoring in this case would be doing things like checking for the exact input from the test, meaning you haven’t written your code in a way that would work for other similar inputs.

Advanced requirements:

• satisfy the Core requirements
• all AD tests pass
• your code is not significantly more complex than needed to accomplish the task
• each function has a comment before it describing its high-level behavior
• your code uses good C coding style

Assignment overview

In the previous assignment, you built a linked list and wrote code that (hopefully) cleaned up the list appropriately. Perhaps you have been missing the convenience of using a language with a garbage collection system that spares you from having to remember to clean individual things up.

For this second part of the interpreter project, we’re going to build an exceedingly simple but effective garbage collector. This garbage collector is so inefficient that this may bother some of you; if so, consider improving the garbage collector to be an optional extension that you can think about when the project is complete (or, I suppose, if you have downtime or are punting other work…).

Tracking malloc

In this assignment you’ll create your own replacement for malloc, which we’ll call talloc (for “track malloc”). From a user’s perspective (that’s you), talloc seems to work just like malloc, in that it allocates memory and returns a pointer to it. Inside your code for talloc, you’ll need to call malloc to do exactly that. Additionally, talloc should store the pointer to that memory in a linked list that we’ll call the “active list” for purposes of discussion. Every time talloc is called, another pointer to memory gets added to that active list.

You’ll then also create a function called tfree, which will free up all memory associated with pointers accumulated from calls to talloc. Calling tfree at arbitrary points in your program would be a complete disaster, as it would free up memory that you may still be using. The idea is that we will be using talloc as a replacement for malloc, then calling tfree at the very end of our main function. You’ll then be able to program with the illusion of using a garbage collector, except that the garbage collection never actually kicks in until the program is about to end.

You’ll also write the function texit, which is a simple replacement for the built-in function exit. Your texit function should call exit after calling tfree. Note that texit should pass the status parameter it gets to exit.

Finally, you’ll then modify your linked list from the previous assignment. The function cleanup that you wrote will be eliminated, as it is no longer necessary. You should also modify reverse so that it no longer duplicates data between the two linked lists. When you reverse a list, that should return a new list with a new set of CONS_TYPE item nodes, but the actual data in that list should not be copied from the old list to the new. This would be a disaster to try to clean up manually, but tfree will handle it easily. This change will make some later aspects of the project much easier. Your linked list code should now exclusively use talloc, and should not use malloc at all.

Storing the active list

One issue you’ll need to think through is where the variable for the head of the active list should be. In an object-oriented language, this would likely be a private static variable in a memory management class. Oops.

You can’t make the active list head a local variable in the talloc function, because then tfree wouldn’t be able to see it. We could make it a paramter to talloc and tfree, but then the programmer (you) using talloc has to keep track of all of this, and could conveivably have multiple active lists, which sounds messy.

This is an occasion in which a global variable makes sense, and so you should use one. A global variable in C is declared outside of any functions. Typically, it is placed near the top of your file, underneath the #include statements and before any functions.

There’s one bit of circular logic you’ve got to untangle. talloc needs to store a pointer (returned by malloc) onto a linked list. Your linked list code, in turn, uses talloc. Rather than trying to make this work in some complex mutally dependent structure, my recommendation is to break the circularity. In your talloc code, the single linked list that you use to store allocated pointers should be a linked list generated via malloc instead of talloc. That means you’ll need to duplicate some of your linked list code. Duplicated code is generally to be avoided, but avoiding this circular nightmare is well worth it.

Optional extensions

The work in this section is 100% optional and does not contribute to your grade in any way. Still, if you’re looking for an extra challenge or ideas on what to practice to study the material, there will be occasional “optional extensions” sections of assignments that contain one or more additional exercises to try.

Write a function that can report a count, in bytes, of how much memory is being used in total by this talloc technique. It should include in its count all of the memory the user asked for when calling talloc as well as all of the additional overhead in scheme_item_t structures that talloc creates for assembling a linked list. Here is a signature for that function, which you can add to your talloc.h file:

int tallocMemoryCount();

Getting started

As before, you should download the starter files as a zip file or tarfile, unzip that file, and copy the folder to where you’ll work (probably your ProgrammingLanguages folder). Refer to the Assignment 1 instructions if you’re unsure what to do.

In the starter code, you should find the following files:

• schemeitem.h: defines the scheme_item_t structure from P1, plus one new type: PTR_TYPE (you’ll need to modify your linked list code to handle this)

• linkedlist.h: provides signatures for functions in linkedlist.c; removes cleanup and changes the documentation for reverse to indicate that the data is not to be copied

• talloc.h: defines the functions you’ll need to write from scratch for this assignment

• main.c: provides tests for your code

• justfile: contains instructions for the command just, which we will use to compile and test your code

• test-cr and test-ad: usual test scripts

• test_utilities.py: contains helper utilities used by test-cr and test-ad

The missing files this time are linkedlist.c, readme.txt, and talloc.c. You should copy both linkedlist.c and readme.txt these from your P1 folder into this one. You’ll create a new file talloc.c for this assignment.

Here are some steps I recommend to get you started:

1. Copy over linkedlist.c and readme.txt.

2. Create a new file talloc.c based on the functions declared in talloc.h. Like before, give each function a return that matches its type (just return; if it’s void).

3. Try building your code using just build at the terminal.

4. Read through the tests to get a feel for what we’re looking for in this assignment.

5. Implement talloc in talloc.c and replace all calls to malloc with talloc in linkedlist.c.

6. Test early and often!

7. Remove cleanup and uses of it from linkedlist.c.

8. Implement the remaining functions in talloc.c.

9. Update reverse as indicated in the comments in linkedlist.h (copy over the new comments, too).

Good luck, and try to have fun with this! If you get stuck, take some time to draw the test cases on a whiteboard/paper and try to use gdb to walk through the code and debug what’s happening. If in doubt, post on the Moodle Q&A forum with any error messages you can’t make sense of!

Testing your work

As with previous assignments, there are CR and AD tests for core and advanced functionality. Look at the instructions from A2 if you want a refresher on how to run these tests.

For the interpreter project, the tests will fail if your code has compiler warnings and/or valgrind errors, so make sure to run the tests in the Docker environment.

Submitting your work

For this assignment, you will submit just one code file. You are strongly encouraged to run ./zipitup to use that script to gather your files for Gradescope.

C code

The files linkedlist.c and talloc.c should contain your functions. Make sure to add a comment above each of your functions (including any helper functions you choose to write) to describe its behavior at a high level (e.g., what it takes as input and what it returns as output). It’s okay to just copy the comments from linkedlist.h and talloc.h, or you can write your own (shorter) descriptions.

Readme

For each assignment for this course you will also need to submit a file readme.txt in which you should write:

1. Your collaborations with anyone on the assignment
2. Your use of any outside sources on the assignment
3. Your reflection

You should be specific about your collaborations and sources – they shouldn’t just be empty or lists of names of people. If you worked alone and/or did not use any outside sources, you should say so.

For your reflection, spend a couple of sentences answering the following:

• Were there any particular issues or challenges you dealt with in completing this assignment?
• How long did you spend on this assignment?

Submitting to Gradescope

As always, use ./zipitup to gather your files. Submit the resulting .zip file to Gradescope.

Note that it is possible (although unlikely) that the tests will pass on your computer but fail on Gradescope. If this happens, it’s probably because you coded something in an unusual way. Double-check that you’re submitted to the correct assignment and then check if any error messages can help you troubleshoot. If you’re still having issues, check with Tanya.