Lab #5: Linked Lists

Due Date Wednesday, May 4th at 9pm.

The purpose of this lab is to give you practice working with:

  1. parsing and generating strings,

  2. structures and pointers to structures, and

  3. linked lists.

You’ll also get practice with reusing functions.

You must complete this lab on a CS Linux machine. You can use the machines in CSIL or can use VSCode + ssh on your own machine to get to one of the Linux servers.

Getting Started

You will be using the same repository for all the labs in this course. To pick up the files you need for this lab (aka, the distribution), you should navigate to your cmsc15200/labs-GITHUB_USERID directory (where GITHUB_USERID) is replaced with your GitHub account name and then run:

$ git pull upstream main

(We will use $ to indicate the Linux command-line prompt. It is not part of the command that you will run.)

If this command succeeded, you will have a subdirectory named lab5. You will do all of your work for this lab in this directory. See the file README.md for a description of the files in the distribution.

As in earlier labs, we have provided a Makefile that has targets for compiling your code with tests that you write, for compiling your code with our automated tests, and for cleaning up generated files.

Some useful stuff

This week we encourage you to read through the Valgrind quick start guide before you start this assignment.

Valgrind is very useful when working with pointers and dynamically allocated memory in C and understanding how to read its output will make it easier to debug your code.

Stock Exchange Orders

For the class project, you will be building a stock exchange. This lab is a warm-up for the project. You’ll get to work with the kind of orders that are used in the exchange.

Each order contains the following information:

  • Venue: a one-letter code indicating the source venue. (The standard abbreviations include I: INET (aka NASDAQ), A: ARCA NYSE electronic exchange, Z: BATS, and B: NASDAQ Boston.) (single character)

  • Ticker symbol: a symbol used to identify a stock. (string)

  • Type: A: add limit order; C: cancel all or part of an extant order; P: print book. (single character)

  • Book: B: buy, S: sell. (single character)

  • Shares: the number of shares. (integer)

  • Price: price per share in hundredths of cents. (e.g., 10000 is $1, 250000 is $25) (long long)

  • Order reference number or oref: a unique number that identifies an order. (long long)

  • Time: the time the order was placed. (integer)

We have defined struct (order_t) to hold all the information for an order.

You will not need to understand the purpose of these fields for this lab.

Utility Functions

We have provided some utility functions in util.h and util.c. These functions do the work of checking the return value from malloc and strdup for you.

  • ck_malloc: takes a number of bytes and the name of the calling function, and calls malloc to allocate the requested space. It checks the return value from malloc, and prints a message and fails with if appropriate. If the call to malloc succeeds, the function returns a pointer to the allocated space.

  • ck_strdup: takes a string and the name of the calling function. It duplicates the string, using strdup. It generates an error and fails, if the call strdup failed. Otherwise, it returns a pointer to the duplicate.

  • ck_free: takes a pointer to heap allocated space and frees it.

Deliverables

You are required to reuse provided functions or functions written for earlier tasks in later tasks where appropriate.

Some tasks have testing suggestions. We encourage you to write and test one task at a time and to follow our testing hints.

Part 1: Orders

In the first part of the lab, you will be building tools that will be useful for working with orders. The work for this part of the assignment will be done in order.c.

We have provided two of the functions from the order interface, you will be required to write others. In particular, we have provided:

  • mk_order: which takes the components of an order and returns a pointer to an order structure

  • free_order: which frees up the space associated with an order

Task 1

Complete the function mk_order_from_line, which takes a string describing an order along with the time the order was placed and returns a pointer to an order structure.

The format of the string will be:

Venue,Ticker,Type,Book,Shares,Price,Oref

where venue, type, and book will be a single character each. The ticker symbol will be one or more characters up to a maximum of 10 characters. The shares will be an integer. And the price and oref will be long longs. The fields will be separated by commas with no white space.

You can use sscanf to parse (or pull apart) the pieces of the string. We encourage you to read the documentation on scanf in your textbook or using man sscanf before you get started.

One quirk that is worth mentioning: the sscanf string directive (%s) does not necessarily behave the way you’d expect. You might think that specifying that the string uses commas as delimiters would be sufficient to limit the number of characters matched to the %s, but you would be wrong. To fix this problem, instead of using using %s for the ticker symbol, you can use %[^,], which means match as many characters as you can until you reach the end of the string or a comma.

The function should do some very basic error checking: if the number of fields matched by sscanf is smaller than the number of fields expected (7), your function should return NULL. Other than that you can assume the data in a line is valid (e.g., the fields that should be one character are, the ticker symbol has at least one letter, etc.)

The automated tests include both valid and invalid order strings. The student test code contains two calls to mk_order_from_line.

Valgrind may be useful for this task. To run Valgrind, compile the code using make and then use this command:

valgrind --leak-check=full ./student_test_lab5

If the output of this command contains any invalid reads or invalid writes, it is likely that you allocated the wrong amount of memory for an order structure. Take another look at your code and figure out how to resolve this issue now. (Also, think about whether you should be calling malloc or ck_malloc directly in this function at all!)

Task 2

Complete the task to_string_order, which takes an order and generates a string. The fields should be separated by commas and in the same order as the input to mk_order_from_line with the addition of the time at the end of the string.

The string you generate should not include any white space (i.e., spaces, tabs, etc).

When constructing the string, you can use a local character array of length MAX_ORDER_LEN + 1. The string that is returned from the function, though, should be heap allocated and occupy only as much space as is necessary.

The function sprintf will be useful for this task.

The student test code contains two calls to to_string_order.

Part 2: Linked list of orders

In the second part, you will be traversing a linked list, adding nodes to it, and removing nodes from it, and freeing the space associated with the list. The values stored in the list will be pointers to orders (rather than integers as seen in class). The work for this part will be done in order_list.c.

We have defined a structure for the nodes of the linked list. Each node will hold a pointer to an order and a pointer to the next node in the list.

An empty list will be represented by NULL. A non-empty list will be represented by a pointer to the first node in the list.

We will say that a node in the list matches an oref, if the oref of the order associated with the node has the same value.

Task 3

In this task, you will implement the function find_before, which takes a linked list, an oref, and an out parameter found_match.

The function should return NULL if the list is empty, if the first element in the list matches the oref, or if the oref does not match any of the nodes in the list.

If a node after the first one in the list matches the oref, then the function should return a pointer to the node that comes BEFORE the matching node. For example, if the oref matches the third node in the list, the function would return a pointer to the second node in the list.

The out parameter should be set to true if the oref matched one of the nodes in the list and false otherwise.

It may seem odd to start with something other than building the list, but this function will prove useful for later tasks, including adding nodes to the list.

The automated tests use hand-constructed linked lists, so you will be able to test the function before you write the code to add orders to the list.

Task 4

Complete the function add_order_list, which takes a list and an order. If the list contains a matching order, then the function should just return the original list.

If the list does not contain a matching order, the function should add the order to the beginning of the list and return a pointer to the new head of the list.

For this task, we encourage you to try out the automated tests one by one. We also encourage you to add code to the student test file to call your add_order_list function with different combinations of lists and orders. If you follow this advise, you’ll be able to use valgrind to test this task as well. (You can ignore valgrind’s messages space leaks for now. You’ll handle them in the next task.)

Task 5

Complete the function free_order_list, which takes a list of orders and a boolean flag should_free_orders. The function should free the list nodes of the list. If should_free_orders is true, then the function should free the space associated with the orders as well. If should_free_orders is not true, then the list nodes should be freed, but not the orders themselves.

We do not have automated tests for this task. Use valgrind to identify space leaks.

Task 6

Complete the function remove_order_by_oref, which takes a list of orders, an oref, and a boolean should_free_order.

If the list contains a matching order, the function should remove it.

The function should return the head of the original list, unless the first order in the list matched the specified oref, in which case, it should return whatever follows the first order in the list.

If the function removes a node from the list, the space for the node itself should be freed. As in free_order_list, the associated order should be freed only if should_free_order is true.

Grading

For this assignment, the weights will be:

  • Completeness: 80%

  • Code Quality: 20%

The completeness score will be determined by the automated tests. The code quality score will largely be determined by whether your implementation:

  • allocates and deallocates memory properly,

  • reuses functions appropriately, and

  • is free of logic errors, including those that may not have been caught by the test code.

Cleaning up

Before your submit your work, we strongly encourage you to get your directory into a clean state. Run make clean to remove any executables that are laying around and then run git status . to make sure you did not forget to add/commit any of the required files.

Also, remove directives, such as:

// YOUR CODE HERE

// Replace 0.0 with an appropriate return value

from your code. Make sure to recompile and rerun the tests after you clean up. It is easy to introduce a syntax error at this stage.

Submission

Before you upload your submission, make sure you have added the required information to the header comment in order.c:

  • your name,

  • the names of anyone beyond the course staff you discussed the assignment with, and

  • links to any resources that you used other than course materials and the course textbook.

Note: write None in the relevant field, to indicate that you did not use any sources and/or consult anyone beyond the course staff.

To submit your work, you will need to add, commit, and push order.c and order_list.c to GitHub and then upload your repository to Gradescope under the lab5 assignment.

You are welcome to upload your code to Gradescope multiple times before the deadline, but it is wildly inefficient to use Gradescope as a compute server. You should test your code on the CS Linux machines and only upload it when you think you are finished or when you are getting close to the deadline and want to do a “safety” submission.

You are responsible for making sure that the code you upload compiles and runs. You will get zero credit for code that does not compile.

Finally, a reminder that we will not accept late work.