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) {
free(this->data);
free(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:
strcmp(); our solutions do it without..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:
this, you will need to heap-allocate
a new .data buffer for it..data buffers are null-terminated..data buffer./** 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.
return;
/* (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.
append(), you will need to allocate a new, appropriately-sized
.data buffer on the heap.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))
return;
if (begin >= this->len || end <= 0 || end <= begin) {
free(this->data);
this->len = 0;
this->data = NULL;
return;
}
if (end > this->len)
end = this->len;
/* (5.4) Your implementation here. */
}