Project 5: String ADT

EE 312 Project 5 - String ADT

You must complete this assignment by yourself. You cannot work with anyone else in the class or with someone outside the class. You are encouraged to get help from the instructional staff.

Due: Friday, October 6, at 11 pm

Description: The purpose of this assignment is to
1. Develop a String ADT in C
2. Practice using dynamically allocated memory and structs
3. Practice with arrays and pointers in C

In this project, you will provide a new and improved String type for C. In C, strings are just an array of ASCII-encoded characters with a zero on the end. This has some significant disadvantages. Strings are a common source of buffer overflow errors in programs. In order to determine how long a string is, each character from the beginning of a string until the null termination character must be counted. You will provide an improved version of the string in this assignment.

You will use a struct to represent a string. This struct will contain a dynamically allocated array for the string, as well as the length of the string and the size of the array. The struct for your String type is defined in the provided String.h header file, along with the prototypes for the String functions you must implement. You must use this String struct without modification. Its fields are:

capacity: The capacity is one less than the size of the array in which the characters of your string is stored in order to allow space for a null terminating character. If you allocate enough space for 20 characters, then the capacity would be 19. The capacity is the length of the longest string you can store in the data array (with room for '\0' at the end.)
length: This is the length of the string, not including the null-termination character.
data: This is a pointer to a char array, which will contain the characters of the string that your struct represents.

The functions that you will implement are the following.

String *makeString(const char *src): this function is passed a C string, and returns a pointer to a String representation of that string that contains a copy of src. Set the length and capacity of your String based on the number of characters in src. Return a pointer to the String.
String *utStrdup(String *s): This function creates a copy of the String argument s. The returned pointer is to a copy of s. After this function is called, modifying the original string should not change the duplicate, and vice versa.
void utStrfree(String *s): Free the memory for this String.
unsigned int utStrlen(String *s): For String s, return the length of the string stored in the data field of s. The length is stored as a field in the struct. Note that you are not allowed to use any functions from string.h for this project.
String *utStrcpy(String *dst, String *src): Replace the characters in dst with the characters from src. Do not overflow the capacity of the String dst. If the String src is longer than the capacity for dst, copy only as many characters as will fit (that is, copy capacity characters.) Update the length of dst. Return a pointer to dst.
String *utStrcat(String *dst, String *suffix): Append suffix to dst, but do not exceed the capacity of dst.
String *utStrrealloc(String *s, unsigned int newCapacity): If the current capacity is equal to or larger than newCapacity, do nothing and return s. If the current capacity is smaller than newCapacity, return a pointer to a String that has the specified newCapacity. You should only need to allocate new memory for the data field.

You may need to write additional helper functions to eliminate redundancy in your code. The provided tests in Proj5Test.c are weak - you will need to write your own tests to ensure that your code is working correctly.

Write a makefile that builds the executable project5. You will submit a zip file a5.zip with no internal directory structure. Zip together these files: makefile, String.c, String.h

Provided files: String.h, Proj5Test.c

You will implement the functions that are declared in String.h in the file String.c. Place the standard EE 312 project header at the top of your String.c file, as well as these:
#include "String.h"
#include<stdio.h>
#include<stdlib.h>
You may not add other #includes to this file. You may not use any string manipulation functions from stdlib.h. You may not define other structs or define any globals. Do not add anything to this file other than documentation and the implementation of the functions from the provided String.h and any helper functions that you may need.

In the standard EE 312 project header, you must replace <NAME> with your own name and you must modify the project description to describe this project. Include a detailed comment right before each function summarizing what it does, as you always should. Provide comments for any significantly complex chunks of code in your functions.

All of your projects are graded on their design as well as correctness.

Notes:
1. We will not test your code with null pointer arguments.
2. You may not use any functions (e.g., strlen, strcat) from string.h.
3. Write your own tests. The provided tests are not sufficient.
4. Use valgrind to check for memory leaks. We will use valgrind when we test your program.
5. Do not modify String.h. You must use the provided struct and function prototypes.

Checklist: Did you remember to

review the general project requirements?
use comments and follow the EE 312 style guide?
ensure that all your files have the correct names?
work on the assignment individually?
add the standard EE 312 header to your source file?
only use concepts and features of C that we've covered?
ensure that your program does not suffer a compile error or runtime error?
write your own tests?
ensure that your program works correctly on kamek?
ensure that your zip file does not contain an internal directory structure and that it contains your makefile, String.c and String.h?
turn in your a5.zip on Canvas?

Many thanks to Dr. Craig Chase and Dr. Vallath Nandakumar for the idea for this project.