CMSC313, Computer Organization & Assembly Language Programming, Spring 2013

Project 6: Ciruclar Buffers and Currency Exchange

Due: Tuesday April 9, 2013, 11:59pm

Objective

Background

If you missed the class discussion on circular buffers, look it up on the internet (e.g., Wikipedia) or a data structures textbook.

The data structure you will implement will help a currency trader (let's call him Andreas) summarize the foreign currency exchange data he receives throughout the day. Andreas's data feed looks like this:

Each line is a quote and represents an offer by someone somewhere to exchange currency at a particular rate. Here, USD is U.S. Dollars, EUR is Euros and JPY is the Japanese Yen. The second column is a timestamp and the third column is the actual exchange rate. For example, the line:

The exchange rates can vary dramatically over the course of a trading day — depending on the news of the day and what other currency traders are doing. Andreas can make money trading currencies, for example, if he correctly predicts that the Euro will rise versus the US Dollar today. Then he can buy Euros with dollars in the morning and exchange them back to dollars in the afternoon and end up with more dollars than he started with.

Thus, Andreas needs to pay attention to these quotes but on a busy day there may be thousands of quotes in an hour. That's too much information. He wants you to store the quotes from the last 5 minutes (300 seconds) and report the average exchange rate for him. You will do so by storing the quotes from the last 5 minutes in a circular buffer.

Finally, Andreas cannot tell you how many quotes there will be in 5 minutes. Your data structure should adapt its memory usage accordingly. If your circular buffer is full, you should double the amount of storage allocated. On the other hand, if your circular buffer is using less than a quarter of the storage, you should free up half of the storage.

Assignment

Note: As with Project 5, this project description deliberately avoids using C syntax. This is so you figure out how to look up the syntax of various elements of the C programming language.

You will implement an Abstract Data Type (ADT) to store currency quotes in a circular buffer. Your functions must be compatible with the main programs given below. Memory for the circular buffer must be dynamically allocated. Main programs that use your ADT may use several circular buffers at a time. (Thus, your functions should not rely on global variables.) Your ADT must support the following functions:

• cbuf * cbuf_init() ;

  Initialize a circular buffer and return a pointer that can be used to specify that circular buffer in future function calls.

• void cbuf_delete(cbuf *cb_ptr) ;

  Deallocate all dynamically allocated memory associated with the circular buffer referenced by cb_ptr. The programmer using your ADT promises to never use the value in cb_ptr again.

• void cbuf_update(cbuf *cb_ptr, unsigned int time, double rate) ;

  Add a new currency exchange quote to the specified circular buffer. The time is in seconds since midnight. This function should remove any quotes in the circular buffer that are more than 5 minutes older than this quote. You should assume that the timestamps given to cbuf_update() are in non-decreasing order. During a cbuf_update(), the memory for the circular buffer may have to grow or shrink according to the rules described above.

  To assist in grading, please print out a diagnostic message with the old and new maximum sizes of your circular buffer when you either grow or shrink the buffer.

• double cbuf_average(cbuf *cb_ptr) ;

  Return the average exchange rate of the quotes currently stored in the buffer.

• quote *cbuf_start(cbuf *cb_ptr) ;

  Return a pointer to the earliest quote currently stored in the buffer. (Earliest = smallest timestamp) The programmer using your ADT promises to just "look at" the quote and not alter it in any way.

• quote *cbuf_end(cbuf *cb_ptr) ;

  Return a pointer to the latest quote currently stored in the buffer. (Latest = largest timestamp) The programmer using your ADT promises to just "look at" the quote and not alter it in any way.

• void cbuf_dump(cbuf *cb_ptr) ;

  Print the contents of the circular buffer to standard output. The output should be formatted nicely and also print out the current size, maximum size and the indices of the start and end of the buffer. (See sample runs linked below.)

• void cbuf_stats(cbuf *cb_ptr) ;

  Same as cbuf_dump() but does not print out the quotes.

You will likely implement additional functions used internally by your ADT. (Actually, this is highly recommended.) Programmers using your ADT may not use these additional functions.

You must provide a header file circular.h that contains all the typedefs and function prototypes needed to use your ADT. The header file must be guarded.

Your circular buffer needs to maintain an array of structs of type quote. Each quote struct must have an unsigned int field called time and a double field called rate. The array of quote structs must be dynamically allocated.

Your header file must have a type definition of cbuf. A pointer to cbuf is used to specify the circular buffer to the ADT's functions. The type cbuf itself is most likely a struct (you decide), but the programmer using your ADT is not allowed to assume that. In particular, the programmer is not allowed to manipulate the fields of cbuf.

You should make your declarations and definitions compatible with these sample main programs:

• A simple test of inserting and deleting from a circular buffer that forces it to grow and shrink: main6a.c. (See sample run: main6a.txt).

• A simple test of reporting circular buffer statistics: main6b.c. (See sample run: main6b.txt).

• A stress test using real data: main6c.c. (See sample run: main6c.txt).

The three data files used in the third test, Ticks6am.txt, Ticks2pm.txt and TicksAll.txt are available on the GL filesystem:

Implementation Notes

• Please name your files circular.c and circular.h.

• The functions in your ADT must compile and run with main6a.c, main6b.c and main6c.c without any modifications to the main programs.

• The initial size of the circular buffer must be 10. This size can change after growing and shrinking but should not fall below 10.

• When the circular buffer is full, you should allocate a new array that holds twice as many quotes as before. You should double the size and not just increase by one because there is a lot of copying involved in moving to a new array. You do not want to have to allocate a new array for each call to cbuf_update().

  Similarly, for shrinking, you should allocate a new, smaller, array when the number of quotes in the buffer is less than a quarter of the current maximum size. (Note: that's a quarter and not a half.) The new array should have half the current maximum size. (Note: that's half not a quarter.)

• Remember to free the old buffer after growing or shrinking.

• The realloc() function is of no use when you double the size of the circular buffer, because the data in the buffer might be "wrapped around". In that case, copying the old buffer to the beginning of the new buffer is incorrect. You should write code to copy the old buffer to the beginning of the new buffer in the correct order.

• Yes, you can assign a struct to another struct of the same type.

• There are lots of places where you can use assert().

• When you delete the entire circular buffer in cbuf_delete(), you must free up the dynamically allocated memory associated with that buffer. You should free the array of quotes before you free up the buffer.

• You should practice defensive programming: make sure that the cbuf pointers given to your function are not NULL before using them.

• When looping through the circular buffer, make sure you check for wrap around.

• One problem with circular buffers is that it is hard to tell when the buffer is empty and when it is full. (In both cases, the end index is right before the start index.) Since you have to keep track of the number of quotes stored in the buffer (in order to determine if growing or shrinking is needed), you can use the size to determine if the circular buffer is full or empty.

• Do not mix up the size of the circular buffer (this equals the number of quotes stored currently) with the maximum size (this is determined by the amount of memory requested in the last call to malloc).

Turning in your program

Use the UNIX submit command on the GL system to turn in your project. You must submit the header file circular.h, the implementation circular.c and any test programs you wish to submit (optional): test1.c, test2.c, ...

In addition, submit a typescript file showing that your ADT functions worked with main6a.c, main6b.c and main6c.c.

You may optionally submit a README file explaining anything the graders might need to know about compiling and/or running your programs.

Your submit commands will look like:

submit cs313 proj6 circular.h circular.c
submit cs313 proj6 test1.c test2.c
submit cs313 proj6 typescript README