Recitation 5: Structs and Objects

C does not natively support object-oriented programming, but we can achieve many of the same programming patterns using structs.

For this exercise, we will implement our own heap-allocated string object. Instead of using a null terminator byte like C strings, our string objects contain a field to keep track of the length, in addition to a pointer to the heap-allocated byte array that carries the string data.

Since this is a coding exercise, you may find it helpful to complete it on a computer rather than doing it on paper. You can obtain the skeleton code on CLAC by cloning it from my examples directory:

git clone ~j-hui/cs3157-pub/examples/mystr

Here is our string object’s struct definition:

struct mystr {
    size_t len;   // Length of the string
    char *data;   // Pointer to array of characters; not null-terminated

To get us started, here are some basic functions used to construct and destroy struct mystr objects:

/** Constructor for struct mystr.
 *  The parameter s is a C string that we initialize the struct mystr with.
 *  This constructor returns a pointer to the newly allocated struct mystr
 *  object.
 *  Note that both the struct mystr and the char data it points to are
 *  heap-allocated.  mystr objects should be destroyed using mystr_delete().
 *  All other struct mystr methods should ensure against memory leaks.
struct mystr *mystr_new(const char *s) {
    struct mystr *this = malloc(sizeof(struct mystr));

    this->len = strlen(s);

    if (this->len == 0) {
        // We are initializing an empty string.
        this->data = NULL;
        return this;

    this->data = malloc(this->len);

    for (int i = 0; i < this->len; i++)
        this->data[i] = s[i];

    return this;

/** Destructor for struct mystr.
 *  Frees the heap memory associated with a struct mystr object and its data.
 *  The caller is responsible for ensuring that dangling pointers to the
 *  now-freed struct mystr aren't used after this is deleted.
void mystr_delete(struct mystr *this) {

You’ll notice that when we try to construct a struct mystr using an empty string, we set the .len field to 0 and the .data field to NULL. Let’s decide that the .len field is 0 if and only if the .data field is NULL, and create a helper to test the emptiness of a struct mystr:

/** Whether this is an empty string. */
int mystr_is_empty(const struct mystr *this) {
    return this->len == 0;

    // return this->data == NULL;
    // ^ this->data should be NULL when this->len is 0

This helper might not seem like it’s doing much, but it’ll make other code more self-documenting when checking whether a struct mystr is an empty string.

By the way, you may have noticed by now that I always name one of the parameters this. That is because these functions represent methods of an object named this. In fact, when we write myobject.mymethod(a, b, c) in many object-oriented languages, what you are really doing under the hood is something more like mymethod(myobject, a, b, c), where the first parameter is the “receiver” of the method. If you’ve used Python for object-oriented programming before, this works the same way as Python’s self parameter that is passed into object methods.

Remember, the heap data that a struct mystr points to is not null-terminated, so we can’t directly use it with functions that expect a C string. To remedy that limitation, here is a method that extracts a heap-allocated C string from a struct mystr:

/** "Export" a struct mystr as a heap-allocated C string.
 *  Returns a pointer to a heap-allocated, null-terminated C string with
 *  this->data.
 *  The caller is responsible for freeing the allocated C string.
char *mystr_to_str(const struct mystr *this) {
    char *buf = malloc(this->len + 1);
    for (int i = 0; i < this->len; i++)
        buf[i] = this->data[i];
    buf[this->len] = '\0';
    return buf;

Now, your first task is to implement the copy() method, which creates a copy of a struct mystr. Though not the most efficient, you should try implementing this without directly accessing this’s fields, i.e., only using previously defined methods:

/** Make a copy of this struct mystr. */
struct mystr *mystr_copy(const struct mystr *this) {
    /* (5.1) Your implementation here. */

Next, implement equals(), which compares the contents of two struct mystr objects. Some hints:

  • You can do this with or without strcmp(); our solutions do it without.
  • Remember that the .data buffers are not null-terminated, so strlen() (and other C string library functions) won’t work on it directly; how else might you get the length?
/** Compare two struct mystr objects for equality.
 *  Returns 1 if the contents of l and r are identical; returns 0 otherwise.
int mystr_equals(const struct mystr *this, const struct mystr *r) {
    /* (5.2) Your implementation here. */

So far, we can create and destroy objects, but we’ve not written anything to modify them. Your following task is to implement the append() method, which concatenates the contents of this and another struct mystr. Some hints:

  • Since you are growing the size of this, you will need to heap-allocate a new .data buffer for it.
  • Remember none of the .data buffers are null-terminated.
  • Don’t forget to free the old .data buffer.
  • The edge case where both strings are empty is handled for you.
/** Append the contents of r to this. */
void mystr_append(struct mystr *this, const struct mystr *r) {
    if (mystr_is_empty(this) && mystr_is_empty(r))
        // If both strings are empty, don't do anything.

    /* (5.3) Your implementation here. */

Finally, implement the truncate() method, which shortens a struct mystr according to an inclusive begin index and an exclusive end index.

  • Like with append(), you will need to allocate a new, appropriately-sized .data buffer on the heap.
  • When begin and end overlap, truncate() will produce an empty string. These edge cases have been handled for you; you may assume that begin and end point to a valid range within this->data.
/** Shorten this from an inclusive begin index and an exclusive end index. */
void mystr_truncate(struct mystr *this, size_t begin, size_t end) {
    if (mystr_is_empty(this))

    if (begin >= this->len || end <= 0 || end <= begin) {
        this->len = 0;
        this->data = NULL;

    if (end > this->len)
      end = this->len;

    /* (5.4) Your implementation here. */