DRAFT

Homework 3 - Data structures in C

In this homework, we practice our C skills by implementing a String data structure, and testing our implementations against each other. An implementation of the String data structure consists of a .o file that provides the following set of functions:

// hw3_string.h
struct String;
struct String* string_new(char* str);
void string_free(struct String* s);
struct String* string_clone(struct String* s);

int string_length(struct String* s);
void string_append(struct String* a, char* b);
char string_charAtIndex(struct String* s, int index);
char* string_range(struct String* s, int start, int length);
char* string_chars(struct String* s);

The template for hw3 is available at svn://bits.cs.uic.edu/cs385s11/notes/homeworks/hw3. This contains the hw3_string.h above, an implementation of the String data structure called simple_string.c, and programs that use String data structures and tests their correctness and runtime performance.

Rope - a binary tree representation of Strings

Your task is to create an alternative implementation of the String data structure, called fast_string.c. The name Rope is more of a guideline than a rule - you may implement your data structure whichever way you please, as long as the following conditions hold:

• it passes all tests run by make testunit
• make testspeed runs in less than 1 second

Do not change the files in the template. Instead, copy simple_string.c to a new file fast_string.c, and edit the first line of the Makefile to use fast_string.c instead. Make and commit your changes to fast_string.c.

Testing correctness and performance

To test the correctness of your code, run make testunit. This performs several unit tests on the String functions declared above. Try running make testunit with STRING_CODE in the Makefile set to simple_string.c to see the expected output.

To test the performance of your code, run make testspeed. This downloads a large book, concatenates the entire book into one large string, line by line, and applies the string functions on the resulting string.