Challenge: std::string in C

Problem statement

You want to implement a pseudo data structure for storing strings of arbitrary length. The advantage of your string data structure over raw C-style strings is that your data structure will be able to grow, without being limited to a fixed size.

For example, consider the following definition:

char str[256];

The string represented by str can store at most 255 characters and the null terminator. If more storage is needed (say 512 characters), the string can not be used.

To address this, you must implement a string that can resize itself when more space is needed.

The basic principle is the same as the principle behind std::string from C++. Don’t worry if you are not familiar with C++.

Implementation details

You’ll maintain a dynamically allocated string. The string will have an initial size of 10 and will grow when needed by doubling its size.

Note: Doubling the size when we’re out of space is a common implementation for containers such as std::vector or std::string. For example, for std::vector, this approach guarantees an amortized asymptotic complexity of $O(1)$ for appending elements to the array.

To do this, we suggest keeping track of the maximum size of the string and the current number of characters inside the string. We suggest you use two variables:

• length is the current number of characters inside the string.
• size is the maximum capacity of the string.
• You should resize the string when length == size. In other words, when there’s no more space to store characters.

You will implement six functions:

• allocResizableString() will be called only once per test case. Here you can do any needed initialization, like allocating the string and initializing the state variables.
• appendResizableString(const char* data) will append the contents of data to the string you are maintaining internally, resizing the string as needed.
• getResizableStringPtr() will return a pointer to the dynamically allocated string. It’s needed because the evaluation suite must access the string to validate its contents.
• getResiableStringSize() will return the maximum capacity of the string.
• getResizableStringLength() will return the number of characters stored inside the string.
• deallocateResizableString() will be called only once at the end of each test case. In this function, you must free the memory.

Note: We suggest you use realloc to grow the string.

Example execution flow

Lines marked with Tester: are executed by the evaluation code. Lines marked with Your code: are things your implementation must do.

Tester: allocResizableString()
Your code: dynamically allocates a char array of size 10 and initializes any internal state variables. The string looks like this: \0 garbage garbage garbage garbage garbage garbage garbage garbage garbage.

Tester: getResizableStringSize()
Your code: will return 10, the maximum  capacity of the string

Tester: getResizableStringLength()
Your code: will return 0, there are no characters stored inside the string

Tester: getResizableStringPtr()
Your code: returns a pointer to the dynamically allocated string

Tester: appendResizableString("abcd")
Your code appends "abcd" to the string and adds the null terminator after it. The string looks like this: a b c d \0 garbage garbage garbage garbage garbage.

Tester: appendResizableString("efghi")
Your code appends "efghi" to the string and adds the null terminator after it.
The string looks like this: a b c d e f g h i \0.

Tester: appendResizableString("12")
Your code: the string is full (length == capacity). Reallocate the string with a size of 20, and update state variables. Append "12" to the string.
The string looks like this: a b c d e f g h i 1 2 \0 garbage garbage garbage garbage garbage garbage garbage garbage.

Tester: getResiableStringSize()
Your code: will return 20, the maximum capacity of the string

Tester: getResizableStringLength()
Your code: will return 11, there are 11 characters inside the string. The null terminator is not counted by this function.

Tester: deallocateResizableString()
Your code: free the memory, and reset state variables.

It’s guaranteed that each test begins with allocResizableString() and ends with deallocateResizableString().

Be careful to place the null terminator in the proper position and ensure there is enough space to hold both the data and the null terminator. Otherwise, reallocate the string and double its size.

Make sure the string is properly null-terminated even if it’s empty. The result of a print operation should always be a valid string (either empty or containing characters), never garbage.

Don’t forget to check if the allocation fails or not.

To access the dynamically allocated string, the tester will do something like this:

char* rs = getResizableStringPtr();