Jesse Lawson

Bestselling author and open-source evangelist.

Apr 23, 2019 - Tutorials Lecture Notes

Dynamic Strings in C and a Crash Course in Pointers (Lecture Notes)

Since C has no string type, we use arrays of characters to represent something like a full name, a bio, or even dynamically sized lines of text–like a JSON string. Imagine a system where we needed to dynamically create strings whose lengths we do not know at compile time. How might we go about doing that?

The answer lies in pointers, pointer-pointers, and memory allocation.

This is a crash course in pointers, memory managment, and dynamic strings in C.

Psst!
Just looking for the code?
You can download the dstring library from Github here (GPLv3)
But listen: if you are not confident with pointers and memory management, please continue reading!

Dynamic strings in C are made possible by allocating heap space during runtime. Recall that stack memory requirements are determined at compile-time, and that heap memory requirements are those that arise during the running of the program. We can access heap memory for dynamic address allocation by using the C functions malloc, realloc, and free–but once variables are assigned on the stack, they are no longer assignable. In other words, if you want to have a variable whose value can be changed during runtime, you need to store that variable on the heap.

Dynamically allocating and deallocating memory, and then accessing those dynamic blocks of memory through pointers, is what some call “memory management” and what others call “why I write in Java/C#/literally anything other than C.”

Memory management in C is one of the reasons C is a Swiss army knife of general-purpose languages, but writing code at that low of a level can be frustrating without a good sense of what’s going on and why. Whole books can be written about pointers and memory in C, so I am going to only focus on dynamic arrays of characters here. The key takeaway here is that, although we are covering character arrays, the rules and ideas around pointers and memory are the same regardless of what kind of variables we are working with.

I promise that the intuition we are developing here will save you many hours of frustration down the road.

So what is a pointer?

A pointer is a special kind of variable that “points to” an address. It is able to give us the value of a different variable by “referencing” that variable, and it does this by pointing at the referenced variable’s address.

Consider the following:

char full_name[] = "Jesse Lawson";

Here we have a variable full_name whose value is set and stored in stack memory. This is fine if we want to store the value of “Jesse Lawson” as a default, but this also means that the maximum amount of characters that can fit in full_name is strlen(full_name).

What if we wanted to change the value of full_name to something longer, like "Jesse Happy Bubble Fun Club Lawson"? Well, we would get an error:

error: array type 'char [13]' is not assignable
  full_name = "Jesse Happy Bubble Fun Club Lawson";
  ~~~~~~~~~ ^

The array full_name is not assignable because it is stored in stack memory, which you’ll remember is stored at compile-time and not changeable. We need to declare full_name on the heap in order to modify its contents. We can do that by declaring a pointer to a string literal instead:

char* full_name = "Jesse Lawson";

If we do this, you might be tempted to try to treat full_name like a dynamic string:

char* full_name = "Jesse Lawson";
//...
full_name = "Jesse Happy Bubble Fun Club Lawson";

While this may seem fine because your program will compile and run just fine, what’s actually happening here is considered “Undefined Behavior”–code word in the C specificiations manual for “you will likely shoot yourself in the foot.” Do not attempt to modify the contents of a pointer to a string literal; for a detailed explanation why, click on the Deep Dive link below. Otherwise, just remember that string literals are expected by the compiler to be treated as const.

💭 Deep dive: What happens when you modify a pointer to a string literal?

In C, arrays decay into pointers. That means that a pointer to a character array, like this:

char full_name[] = "Jesse Lawson";
char* ptr_to_name = full_name;

is equivalent to this:

char full_name[] = "Jesse Lawson";
char* ptr_to_name = &full_name[0];

Put another way, any pointer to a character array will always point to the address of the first character in that array.

char* full_name = "Jesse Lawson";
  ^                ^
  |                |
pointer         first element
                in full_name
                (i.e., full_name[0])

That’s how C knows to treat char* pointers as a string of characters: go to the memory address pointed to by the pointer; read all characters up to the null terminator. Boom. You got yourself a string.

Knowing this, we can now see the “behind the scenes” of what’s going on when we do this:

char* full_name = "Jesse Lawson";
full_name = "Jesse Happy Bubble Fun Club Lawson";

The variable full_name is a pointer to the first element address of the string "Jesse Lawson"–but where does that string exist? Well, it has to exist as a string literal on the stack since it was declared and computed at compile time. This means that somehere there is something like this happening behind the scenes:

static char __full_name[] = "Jesse Lawson";
char* full_name = __full_name;

String literals are placed on the stack in a part of read-only memory known as .rodata with the rest of the static variables. It’s intended to be a persistent, constant space, where you store things like the name of the program’s author. That is a string that we are confident wont be changing during runtime. However, when we go and change the value of full_name like this:

char* full_name = "Jesse Lawson";
full_name = "Jesse Happy Bubble Fun Club Lawson";

what we are actually doing is creating a whole new static variable that lives at a different address–both of which will persist in the application’s read-only memory.

So in a nutshell, we don’t change the value of the string–we just create a new string for the pointer to point to. That is not what we want.

To illustrate this, you can run the code in this Gist, which will output the address of full_name every time you change the string literal it points to:

newptr: 0x400688
newptr: 0x4006a8
newptr: 0x4006d0
newptr: 0x400710
newptr: 0x400760

Notice that the addresses are all different–which is why modifying the value of a pointer to a string literal is considered undefined behavior:

String literals are not modifiable (and in fact may be placed in read-only memory such as .rodata). If a program attempts to modify the static array formed by a string literal, the behavior is undefined.

Later, we’ll see a side-by-side example of this method (the wrong way) and the dynamic string method (the right way).

Variables like full_name are arrays of characters. If we were to print out our array, we would get something like this:

for(int i=0; i<strlen(full_name); i++) {
  printf("[%d] %c\n", i, full_name[i]);
}

Output:

[0] J
[1] e
[2] s
[3] s
[4] e
[5]
[6] L
[7] a
[8] w
[9] s
[10] o
[11] n

Each character is assigned to a specific index of the array in order.

The hidden element. There’s a hidden element at the end of character arrays called the null terminator, which looks like this: \0. This character marks the end of the array. You’ll have to remember that the null terminator is a thing for when we decide to make room for longer strings of text. Keep reading!

So a pointer to an array will always point to the address of the first element in the array, and the array value will be every character from the first element up to the null terminator. This gives us a maximum length of 12 for full_name, with the total length of the array actually being 13 (since we have to include the null terminator).

What happens now when we want to change the value of full_name. Well, since full_name was instantiated on the stack, as long as we are setting its value to a string with a length equal to or less than 12 characters we will be fine. But we want to set our full name to Jesse Happy Bubble Fun Club Lawson–which definitely will not fit. A call to strcpy() will cause us to only write the first n characters, where n is equal to the length of the initializer string "Jesse Lawson".

Creating a dynamic character string

To get around the limitations of a character array in stack memory, we have to declare full_name on the heap by using the memory allocation function malloc(). Here’s the code that we’ll use (you’ll want to wrap it in a main() call), followed by a detailed summary:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int length_required = strlen("Jesse Lawson") + 1;
char* full_name = malloc( length_required );
if(full_name == NULL) {
  printf("Couldn't allocate memory!");
} else { 
  strcpy(full_name, "Jesse Lawson");
  printf("full_name == %s\n", full_name);
}
free(full_name);

// Output:
// full_name == Jesse Lawson

Bad Practices. Normally you would never violate the DRY Principle by using a string literal like this, but for instructional purposes I think it helps to illustrate what we’re doing.

Let’s walk through the pertinent lines one at a time.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

Here, we include the standard input/output, string utils, and standard library headers, respectively. The stdlib.h file gives us a cross-platform way of accessing memory allocation and deallocation functions, moreso than the typical memory.h might.

int length_required = strlen("Jesse Lawson") + 1;

Here, we declare an integer to hold the length of the memory block we need to allocate, which is equal to the length of our desired string plus one to account for the null terminator.

char* full_name = malloc( length_required );

Here, we tell the pointer full_name to point to an allocation of memory that has a size equal to the integer length_required. It will return either a valid address to the block of contiguous memory that has been set aside, as requested, or it will return NULL if for some reason it could not allocate the requested amount of memory.

We do a basic check for this via the if-else block:

if(full_name == NULL) {
  printf("Couldn't allocate memory!");
} else { 

Next, we will copy the string and then print it:

  strcpy(full_name, "Jesse Lawson");
  printf("full_name == %s\n", full_name);
} // end of if-else

The function strcpy() will copy over the contents of any string literal into the full_name variable, but only up to a number of characters equal to length_required.

free(fullname);

This final call before printing the value of our variable does exactly what it seems like it does: it frees up the memory space previous allocated by malloc(). An important rule to remember is that all malloc’d pointers must be freed. Unfreed pointers who have been malloc’d are the root cause of most memory leaks. Avoid them by always typing free() after you write your malloc() calls so that you don’t forget!

At this point we have a working dynamic string in C. Neat!

It’s not very useable, though. For example, what happens when we want to change the value of full_name to something else? We already know that the length of the array gives us a maximum length that we can strcpy() into. In fact, we can represent this by trying to strcpy() a string into full_name that is longer than full_name. What do you think will happen?

If you guessed that only the first \(n\) characters will appear in full_name, where \(n\) is the length of full_name, you would be correct. (I really hope your internal thoughts don’t sound like the start of some math proof…)

That seems like an easy enough problem to solve since we just need a way to reallocate the memory that we’ve requested. However, consider how the complexity of your code will evolve as you add another one, two, three, ten, or twenty+ strings. Are you really going to make individual calls to malloc() and free() for every single string variable?

No way, so to get around this, we need a way to dynamically reallocate the memory block pointed to by our pointer. In order to do that, we’ll pull out the heavy guns–pointer pointers–and make headway on your very own set of dynamic string functions.

Creating a dynamic string library

We’re going to create a set of functions to handle the allocation, reallocation, and deallocation of memory for us, that way we don’t have to call malloc() and free() a bunch of times for different strings, satisfying the principle of “Don’t Repeat Yourself.”

Our goals are three-fold:

  1. Initialize an empty pointer to a contiguous block of memory to store a string.

  2. Dynamically allocate more memory if needed (or less if available) as we request a change of the string’s value.

  3. Deallocate our memory when we are done with it.

We will create three separate functions to accomplish each goal: string_init(), string_set(), and string_free(), respectively. I’ll be referring to each of these as the Initializer, the Setter, and the Cleaner.

Initializer

Functions in C copy the argument variables into the scope of the function, and are then disposed of once the function is done. For this reason, we don’t want to take in a function pointer, like this:

void string_init(char* string_ptr) { //...

It might seem like the right thing to do, but all that’s really happening is that the pointer string_ptr is only existing in function space. So, if you try to malloc that pointer, you’re not going to have the behavior you are intending to have.

Instead, we’ll pass in a pointer-pointer, which looks like this:

void string_init(char** string_ptr) { //... 

This way, we can dereference the pointer-pointer in function scope and get our actual pointer. The full function looks like this:

void string_init(char** string_ptr) {
  // Create a string pointer and allocate memory for it
  char *ptr = malloc(16);
  // Dereference our pointer and set its address to the new contiguous block of memory
  *string_ptr = ptr;
}

With this function, we can do something like this:

char* my_string;
string_init(&my_string);

That will initialize our string. Next, let’s figure out how to free it.

Cleaner

The cleaner function works the exact same way: given a pointer-pointer, dereference the pointer and free the address of memory it was pointing to:

void string_free(char** string_ptr) {
  free(*string_ptr);
}

Setter

The setter is the most complicated function of the three, but understanding it fairly easy if you think about what you are trying to do first. We want to do the following, in order, given a pointer-pointer and a string literal:

  1. Determine the size of the requested string value.
  2. Reallocate the pointer pointed to by our pointer-pointer to fit the new size.
  3. Copy into the memory we just reallocated the requested string value.

The following illustrates the implementation of the steps above:

void string_set(string_t** destination, char* value) {
    int new_size = strlen(value);

    // Add 1 to account for '\0' null terminator
    *destination = realloc(*destination, sizeof(char)*new_size + 1);

    if(*destination == NULL) {
      printf("Unable to realloc() ptr!");
    } else {
      strcpy(*destination, value);
    }
}

With these three functions, you’ve got yourself the workings of a dynamic string library!

A full working example showing the order of and relationship between malloc(), realloc(), and free() can be found on this Gist.

I hope you’ve found this helpful. Good luck!