COS 371: Programming Languages
Spring 2022
hw8: Vector
Due: Friday, 03/11 at 22:00
This assignment is to be done individually. You can share ideas and thoughts with other people in the class, but you should code your own assignment.
1. Goals
To implement an array-backed list that grows as necessary.2. Introduction
Lists are amazing. We can build our entire Scheme interpreter using a linked list as our only data structure. (This may or may not be the best idea.) Here, we will get a little C practice by working on a different data structure, the vector. A vector is like an array, but can grow larger as needed. (This functionality exists in many languages, such as Python's list and Java's ArrayList.) C has no such built-in vector capability, though it does have fixed-size arrays. Under the hood, our vector is implemented as an array with some room for slack (unused slots). When we use up the slack and try to insert again, the vector will double the size of its internal array and copy over the old values.
3. Instructions
- Read and follow the C style and grading guidelines linked from the course website.
-
We'll again be using Git and GitHub for this assignment. Look for a repository named
username1-username2-vector
, with you and your partner's usernames substituted. (If you are working individually, look for a repository namedusername-vector
.) Clone it. Download the following files:Add them to your repository (and commit, push, etc.).
Your task is to add to the file vector.c, which should contain the implementations for all of the functions prototyped in vector.h. Make sure to read the comments in vector.h carefully and follow all of the instructions.
-
Implement the functions prototyped in
vector.h
.As you start, you need to make the tester more limited. (And my tester doesn't even test
set
!) So start by modifying the tester code so that you can develop and test your code incrementally (as always). For example, you can set the initial size high enough to testadd
before implementing the array resizing feature.To compile, run:
clang vector.c tester.c -o tester
to create an executable file called tester, which you can then run:
./tester
We will be using Clang to test your code, so you should do the same. Make sure that you do not have any compiler errors or warnings under Clang. (Warnings are often a sign that you have a bug, anyway!)
-
Your code should have no memory leaks or memory errors. We will (and therefore you should also) test your code using Valgrind, an open source tool that is available for Linux. (It is somewhat less reliably for Macs, so you will want to run this on Linux. Valgrind is not available on Windows. Similar tools do exist for Windows, but they tend to be quite expensive.)
To use Valgrind, first compile your code with debugging info enabled:
clang -g vector.c tester.c -o tester
Then run your executable through Valgrind as follows:
valgrind --leak-check=full ./tester
You should see reports for every leaked block of memory, including file and line information for when the allocation happened. When you submit, your code should not produce memory errors.
4. Optional Challenges
- Add a function to sort a Vector using, say, merge sort.
- Make the Vector auto-shrink when it becomes less than a quarter full.
5. Submission
Follow the instructions from the previous homework set. That is:- Create a file called
credits.txt
declaring "We didn't get any help" or listing anyone who helped you with the assignment (including lab assistants and classmates), and any websites, books or other sources you used for reference. Also briefly describe how you were helped. Please be thorough. - Add, commit, and push regularly.
- When you are done, double check to make sure you have committed the version you want graded;
tag and push the tag:
git tag hw8 git push --tags
(Recall that a normalgit push
does not push tags. Be sure to check on GitHub to make sure that it received your final submission.)
Assignment written by Dave Musicant, with some updates and improvements by Laura Effinger-Dean, David Liben-Nowell, and Jed Yang.
Start early, have fun, and discuss questions on Moodle.