Project Part 1: Electronic Exchanges: trading a single stock

Part 1 Due Date Friday, May 20th at 9pm. (Note the non-standard due date)

In this assignment, you are going to implement an electronic exchange for a single stock. Your exchange will accept a stream of orders and based on those orders, it will keep track of pending orders, execute trades when possible, and create a set of trading records.

We encourage you to spend time understanding the explanation provided below on the workings of electronic exchanges, exploring the project’s code base, and thinking through your design before you start writing code.

Understanding exchanges

To understand the requirements for the project, you need to know a little bit about stock exchanges. Here are some definitions:

  • exchange: a venue where stocks are traded.

  • listed stocks: the stocks an exchange trades.

  • ticker symbol: a short string used to name a particular stock. TWTR, for example, is the ticker symbol for Twitter.

  • add limit order: an order to buy or sell a specified number of shares of a particular stock. Also known as buy orders and sell orders.

  • order reference number: a unique identifier assigned to each add limit order.

  • buy book: a data structure used to keep track of pending buy orders.

  • sell book: a data structure used to keep track of pending sell orders.

  • booked order: an order from either book.

A trade is made when a buyer and seller agree on a price. A buyer has a maximum amount they are willing to spend. A seller has a minimum price they are willing to accept. The key to understanding how exchanges work is to keep in mind that the person who arrives second to the exchange has the advantage.

Let’s say a seller arrives at the exchange willing to sell \(X\) shares at price \(S\) and finds no waiting buyers. Now, a buyer comes along and wants to buy \(Y\) shares at price \(P\). If \(P >= S\), then a trade can occur. The buyer will buy \(min(X, Y)\) shares at price \(S\). That is, they don’t buy more than they want and they can’t buy more than the seller wants to sell (at least, from this seller). Since the buyer comes second, they get the advantage and may end up paying less for the shares than they had planned.

Let’s look at the opposite situation: A buyer arrives at the exchange willing to buy \(Y\) shares at price \(P\) and finds no waiting sellers. Now, a seller comes along and wants to sell \(X\) shares at price \(S\). If \(S <= P\), then a trade can occur. The seller will sell \(min(X, Y)\) shares at price \(P\). That is, they don’t sell more than they want and they can’t sell more than the buyer wants to buy (at least, from this buyer). Since the seller comes second, they get the advantage and may end up selling their shares for more than they had planned.

That explanation yields a few more defintions:

  • matching order:

    • a booked buy order matches an incoming sell order, if the buy order price is greater than or equal to the sell order price;

    • a booked sell order matches an incoming buy order, if the sell order price is less than or equal to the buy order price.

  • crossing order: an arriving add limit order that has a matching booked order.

  • best price:

    • for a buy order is the lowest price among a set of sell orders that is less than or equal to the buy order’s price;

    • for a sell order is the highest price among a set of buy orders that is greater than or equal to the sell order’s price.

As explained above, the order that arrives at the exchange later determines the pricing model. It also determines how pending orders are sorted in the their respective books. The buy book is ordered to benefit the sellers: from highest price to lowest price. The sell book is ordered to benefit the buyers: from lowest price to highest price. In both cases, ties are broken by the orders’ times: earlier orders have priority.

Note: stock traders use the terms bid and ask for buy and sell, but we will stick to buy and sell to reduce confusion.

Stock Exchange Orders

As you saw in Lab #5, an 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) All of our orders will be for INET ('I').

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

  • Type: A: add limit order; C: cancel all or part of an extant order; (single character) All the orders for Part 1 will be add limit orders ('A')

  • 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 provided the types and basic functions (the ones from Lab #5 and a few others that will be useful) in order.c. See order.h for descriptions and prototypes. While you may not change the functions that we provide, you may add new functions to this data structure. Add the code to the file order.c and the prototypes to the file order.h.

You main task for this assignment will be to process add limit orders.

To process a buy order, consult the sell book to determine whether it contains a matching order. If so, record the trade (see below for how to record trades), decrease the number of shares in the booked order by the number of shares traded, and decrease the number of shares in the crossing buy order by the number of shares traded. If the booked order has no more shares left, remove it from the book. Repeat this process if the number of shares remaining in the buy order is greater than zero.

Once you run out of matching orders in the sell book, add what is left of the incoming order to the buy book. This order is now done.

To process a sell order, consult the buy book to see if it contains a matching order. If so, record the trade, decrease the number of shares in the booked order by the number of shares traded, and decrease the number of shares in the crossing sell order by the number of shares traded. If the booked order has no more share left, remove it from the book. Repeat this process if the number of shares remaining in the sell order is greater than zero.

Once you run out of matching orders in the buy book, add what is left of the incoming order to the sell book. This order is now done.

Notice that processing a sell order is the similar to processing a buy order with the roles reversed.

Sample stream of trades

Here is a sample stream of trading orders for an fictional company with ticker symbol UOCCS sent to INET. Assume that the UOCCS books are initially empty.

First order to arrive:

INET (I) receives: I,UOCCS,A,S,100,550000,1000 at time 10

Steps taken by INET: checks for matching orders in the **buy** book
(finds none), updates its **sell** book for UOCCS to include order 1000.

INET actions recorded:
  100 shares BOOKED (SELL) at price 550000 (1000)


INET UOCCS buy book: empty

INET UOCCS sell book:
  I,UOCCS,A,S,100,550000,1000 @ 10  (best sell price)

Second order to arrive:

INET receives: I,UOCCS,A,B,70,558000,1070 at time 20

Steps taken by INET: checks for matching orders in the **sell** book
(finds order 1000), executes a trade, which reduces the number of
shares available in order 1000 to 30 and completes order 1070.

INET actions recorded:
  70 shares TRADED at 550000 price (1000)

INET UOCCS buy book: empty

INET UOCCS sell book:
  I,UOCCS,A,S,30,550000,1000 @ 10  (best sell price)

Third order to arrive:

INET receives: I,UOCCS,A,S,20,540000,2000 at time 30

Steps taken by INET: checks for matching orders in its UOCCS **buy**
book (finds none), updates its **sell** book for UOCCS to include
order 2000.

INET actions recorded:
  20 shares BOOKED (SELL) at price 540000 (2000)

INET UOCCS buy book: empty

INET UOCCS sell book:
  I,UOCCS,A,S,20,540000,2000 @ 30  (new best sell price)
  I,UOCCS,A,S,30,550000,1000 @ 10

Fourth order to arrive:

INET receives: I,UOCCS,A,S,10,550000,1010 at time 40

Steps taken by INET: checks for a matching order in its UOCCS buy book
(finds none), adds order 1010 to its sell book.

INET actions recorded:
  10 shares BOOKED (SELL) at price 550000 (1010)

INET UOCCS buy book: empty

INET UOCCS sell book:
  I,UOCCS,A,S,20,540000,2000 @ 30   (best sell price)
  I,UOCCS,A,S,30,550000,1000 @ 10
  I,UOCCS,A,S,10,550000,1010 @ 40

Fifth order to arrive:

INET receives: I,UOCCS,A,B,20,555000,1020 at time 45

Steps taken by INET: checks the price of order 1020 against
the **sell** book and determines that a matching order (2000)
exists, executes a trade for 20 shares and then removes order 2000
from its sell book because the number of shares has dropped to zero.
These actions complete order 1020.

INET actions recorded:
  20 shares TRADED at price 540000 (2000)

INET UOCCS buy book: empty

INET UOCCS sell book:
  I,UOCCS,A,S,30,550000,1000 @ 10   (best sell price)
  I,UOCCS,A,S,10,550000,1010 @ 40

Sixth order to arrive:

INET receives: I,UOCCS,A,S,100,570000,2010 at time 50

Steps taken by INET: looks for and cannot find a matching order in its
buy book, so it adds the order to its sell book.

INET actions recorded:
  100 shares BOOKED (SELL) at price 570000 (2010)

INET UOCCS buy book: empty

INET UOCCS sell book:
  I,UOCCS,A,S,30,550000,1000 @ 10    (best sell price)
  I,UOCCS,A,S,10,550000,1010 @ 40
  I,UOCCS,A,S,100,570000,2010 @ 50

Seventh order to arrive:

INET receives: I,UOCCS,A,B,100,560000,1040 at time 60

Steps taken by INET: checks its sell book and finds a matching order
(1000), executes the trade, reduces the number of shares in order
1000 by 30, and reduces the number of shares in order 1040 to 70.
Since the number of shares in order 1000 has dropped to zero, INET
removes order 1000 from its sell book.

Order 1040 has shares remaining after the trade, so INET iterates.
In the second iteration, it finds a matching order (1010), executes
the trade, reduces the number of shares in order 1010 by 10 and
removes it from the sell book, and decreases the number of shares in
order 1040 to 60.

Order 1040 still has shares remaining after the second trade, so
INET iterates.  In the third iteration, INET does not find a
matching order in the sell book (the price listed in Order 2010 is
too high), so INET completes order 1040 order by adding it to the
UOCCS buy book.

INET actions recorded:
  30 shares TRADED at price 550000 (1000)
  10 shares TRADED at price 550000 (1010)
  60 shares BOOKED (BUY) at price 560000 (1040)

INET UOCCS buy book:
  I,UOCCS,A,B,60,560000,1040 @ 60  (best buy price)

INET UOCCS sell book:
  I,UOCCS,A,S,100,570000,2010 @ 50  (best sell price)

Eighth order to arrive:

INET receives: I,UOCCS,A,B,100,565000,1050 at time 70

Steps taken by INET: checks its sell book for a matching order (finds
none), so it adds order 1050 to its buy book.

INET actions recorded:
  100 shares BOOKED (BUY) at price 565000 (1050)

INET UOCCS buy book:
  I,UOCCS,A,B,100,565000,1050 @ 70  (new best buy price)
  I,UOCCS,A,B,60,560000,1040 @ 60

INET UOCCS sell book:
  I,UOCCS,A,S,100,570000,2010 @ 50  (best sell price)

Ninth order to arrive:

INET receives: I,UOCCS,A,B,100,565000,5000 at time 69

Steps taken by INET: checks its sell book for a matching order (finds
none), so it adds order 5000 to its buy book.  Notice that order
5000 arrived a little out of order. So it ends up ahead of order
1050 in the buy book, because they have the same price and it has an
earlier time.

INET actions recorded:
  100 shares BOOKED (BUY) at price 565000 (5000)

INET UOCCS buy book:
  I,UOCCS,A,B,100,565000,5000,69
  I,UOCCS,A,B,100,565000,1050,70
  I,UOCCS,A,B,60,560000,1040,60

INET UOCCS sell book:
  I,UOCCS,A,S,100,570000,2010 @ 50  (best sell price)

Tenth order to arrive:

INET receives: I,UOCCS,A,S,250,562000,7000 at time 80

Steps taken by INET checks its buy book and finds a matching
order (5000) executes the trade, reduces the number of shares in
order 5000 by 100, and reduces the number of shares in order 7000
to 150.  Since the number of shares in order 5000 has dropped to
zero, INET removes order 1000 from its buy book.  Notice that the
trading price comes from the buy book.

Order 7000 has shares remaining after the trade, so INET iterates.
In the second iteration, it finds a matching order (1050) executes
the trade, reduces the number of shares in order 1050 by 100, and
reduces the number of shares in order 7000 to 150.  Since the number
of shares in order 1050 has dropped to zero, INET removes order 1050
from its buy book.

Order 7000 has shares remaining after the trade, so INET iterates.
In the third iteration, INET does not find a matching order (the
price in Order 1040 is too low), so INET add the order to its sell
book.

INET actions recorded:
  100 shares TRADED at price 565000 (5000)
  100 shares TRADED at price 565000 (1050)
  50 shares BOOKED (SELL) at price 562000 (7000)

INET UOCCS buy Book:
  I,UOCCS,A,B,60,560000,1040,60

INET UOCCS sell Book:
  I,UOCCS,A,S,50,562000,7000,80   (new best price)
  I,UOCCS,A,S,100,570000,2010,50

Getting Started

You will be using a new repository for the project. Please follow the instructions in the Ed post “Project Part 1 now available” to set up your project repository. Please work through all of the steps (starting with accepting the assignment thought git push -u origin main) before you start to work on the project!

See README.md for a description of the files in the repository.

Action Reports

As you will see below, the exchange will return an action report after processing an order. We have provided a data structure for this purpose. It has a constructor and free function:

action_report_t *mk_action_report(char *ticker);

void free_action_report(action_report_t *ar);

There are three types of actions you can add to a report:

enum action {BOOKED_BUY, BOOKED_SELL, EXECUTE};

The first two are used to report that you have added an order to a book. The third is used to report that a trade has been executed. Here is the prototype of the function used for adding actions to the report:

void add_action(action_report_t *ar, enum action action,
                long long oref, long long price, int num_shares);

Finally, we have provided a function for printing the contents of an action report:

void print_action_report(action_report_t *ar);

for debugging purposes. See the file action_report.h for more details about the functions.

Deliverables

Your task is to complete these three functions in the Exchange interface:

exchange_t *mk_exchange(char *ticker);

void free_exchange(exchange_t *exchange);

action_report_t *process_order(exchange_t *exchange, char *ord_str, int time);

and you are strongly encouraged, but not required, to implement this function:

void print_exchange(exchange_t *exchange);

We have defined the types needed for an exchange (a struct exchange). You’ll notice that the type expects an exchange to have two books: a sell book and a buy book. The type defined for books (book_t) is opaque, which means that the exchange is not allowed to reach into the representation of a book to perform tasks itself.

You must determine what operations the book data structure needs to provide for use by the exchange. The operations provided by this data structure can and should be simple. Beyond understanding how to keep the book in the order appropriate for its type (in decreasing order by price for the buy book and increasing order by price for the sell book), the book data structure must not include the logic for making trades. Nor should you pass the action report data structure to any of your book functions.

For Part 1, you should use a linked list to track the orders in a book. It is up to you whether you want to use a singly-linked list or a doubly-linked list and whether you want to have a dummy node or not. We recommend against using a circular list, as there are no operations that benefit from being able to go from the last order to the first order in the list.

You will replace this data structure in Part 2 of the project. If you design your interface well, this change will be invisible to your exchange implementation.

Your implementation of the book data structure should be added to the file book.c. The interface for the book data structures, that is, the prototypes for the functions you will need in exchange.c should be added to the file book.h.

Space management

Your code is responsible for allocating and deallocating the space needed for orders, books, and the exchange. An order should be freed when you are completely finished with it. The exchange, the books, and any orders still pending in the books should be freed when free_exchange is called.

Your code is not responsible for freeing the order strings or the action reports.

Part of your grade will depend on whether you have successfully deallocated all the memory allocated by your code.

Testing

Unlike previous assignments, we will not be providing all of the automated tests that will be used to grade your implementation. Instead, we have provided test code (student_test_exchange.c) that can be used with Valgrind and LLDB. You are welcome to add tests to this file. We do not require you to add tests to this file, but we do encourage it.

When you upload your code to gradescope, the initial autograder will run exactly one test case. This test case is available in the distribution in test_exchange.c. This arrangement will allow you to make sure that your code compiles and runs on at least one test in Gradescope. If you see Exchange (1.0/1.0) under Passed Tests, then your code passed the single test. Ignore the 1/75 autograder score. This score will change when we run the final autograder.

We will replace this autograder with actual tests that will be used to verify your code once the deadline passes. We do not promise that the tests provided in student_test_exchange.c and in test_exchange.c cover all the cases that will be covered in the automated tests.

Some testing hints

The student test code contains four different functions that can be used to test different things:

  • Use do_none to check your code for constructing and freeing an empty exchange.

  • Use do_a_few to check your code for different cases. The initial version checks the first two orders in the list of sample orders given in the file. Once this case produces the right answer and does not have any space leaks, we recommend that you change up the number of orders tested, the specific orders tested, and the times of the orders.

  • Use do_all to check your code on all the sample orders.

  • Use do_handout to check your code against the example in the handout.

Utility Functions

As in Lab #5, we have provided some utility functions in util.h and util.c. ck_malloc, in particular, will be useful to you. It takes a number of bytes and the name of the calling function as a string. It then calls malloc to allocate the requested space and checks the return value. It will print a message and fail, if the call to malloc fails. If the call succeeds, the function returns a pointer to the allocated space. The rest of the functions are used by our code and will not be useful in your part of the project.

Grading

For this project, the weights will be:

  • Completeness: 75%

  • Code Quality: 25%

The completeness score will include your performance on automated tests and on whether you successfully avoid memory leaks. Just a reminder, the automated tests will not be available to you as you work on your project.

The code quality score will depend on how well you decompose the problem into pieces, follow the course style guide, and on whether you successfully implement the trading logic.

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 exchange.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 exchange.c, book.c, book.h, order.c, and order.h to GitHub (git -u adds known files that been modified) and then upload your repository to Gradescope under the Project Part #1 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.