This article is a tutorial on C memory management. It is intended for people who have no experience with memory management at all, though I believe many people will find it useful.
I have been “learning” C at uni, but I thought my teacher explained pointers and memory management in C in a way that seemed rather less intuitive to me. Pointers and memory management are understood to be highly personal, so I felt like doing my fellow students a favour by explaining C memory management from a different angle. I’m posting this article on my blog since I believe it is not just useful to my fellow students, but anyone learning C.
Here’s how text in this post is formatted:
This is what code looks like.
/* this is a comment */
This line contains some highlighted parts.This is some sample output.
Pass by Value
Suppose we have the following scenario: we have a program that deals with dictionaries. It has few features: we can add and remove words from a dictionary, and we can print the dictionary. Assuming we have defined a dictionary_t typedef’ed struct before (the way it is defined is not important), we could implement this as follows:
void test(void)
{
dictionary_t d;
dictionary_add(d, "ice", "something cool");
dictionary_add(d, "coffee", "something hot");
dictionary_print(d);
}The output may be surprising: the dictionary is empty! What happened?
Here’s another example with the same effect:
void test(void)
{
int a = 10;
printf("a is now %i.\n", a);
increment(a);
printf("a is now %i.\n", a);
}
void increment(int x)
{
x = x + 1;
}The output of this little program is:
a is now 10. a is now 10.
Hey!
you say. I incremented a!
Nope, wrong.
When the statement increment(a) is executed, the application takes the value of the variable a, creates a new variable x, puts that value into the variable x, and then passes the variable x as an argument to the increment() function. The variable x ends up being incremented, not the variable a.
(This method of passing the values of arguments is called (gasp!) “pass by value”. Some languages allow arguments to be “passed by reference”, where no new variables are created when calling a function. When using “pass by reference”, the above example would work. C doesn’t have this, so don’t try it.)
Aha!
you say. Maybe if I rename x to a, it’ll work!
. Nope, wrong again. This piece of code is no different than the previous one:
void test(void)
{
int a = 10;
printf("a is now %i.\n", a);
increment(a);
printf("a is now %i.\n", a);
}
void increment(int a)
{
a = a + 1;
}What happens here is that you have two variables called a. The value of the old a is copied into the new a, and the latter is passed to the increment() function.
In the dictionary example, the dictionary itself is not passed, but a copy of it is. Two words are added to two copies, but the original dictionary is still empty.
Pointers
Peter Hosey has written an excellent article about C pointers called Everything you need to know about pointers in C. Memory management has everything to do with pointers, so read his article before continuing this tutorial. I’ll wait.
Done? Good.
The problem with the examples above is that when calling a function, its function arguments are copied. We’ll fix this by passing the address of our dictionary to these functions instead of the dictionary itself. This way, the address is copied instead of the dictionary. This is how our functions will access our dictionary.
Here’s a working implementation:
void test(void)
{
dictionary_t d;
dictionary_add(&d, "ice", "something cool");
dictionary_add(&d, "coffee", "something hot");
dictionary_print(&d);
}Both dictionary_add() and dictionary_print() now take a pointer to a dictionary, not the dictionary itself. That way, the original dictionary can be referenced, and changed. This means that our example works.
Let’s see if we can write that differently. Here’s another implementation:
void test(void)
{
dictionary_t *d;
dictionary_add(d, "ice", "something cool");
dictionary_add(d, "coffee", "something hot");
dictionary_print(d);
}But this won’t work. In fact, it will likely crash! The statement dictionary_t *d does not create a new dictionary, but merely a pointer to a dictionary. This pointer doesn’t actually point anywhere; it is a dangling pointer, and you should be very careful with those.
Here’s a way to fix it:
void test(void)
{
dictionary_t d;
dictionary_t *dp = &d;
dictionary_add(dp, "ice", "something cool");
dictionary_add(dp, "coffee", "something hot");
dictionary_print(dp);
}The dictionary pointer now points to a real dictionary. This example works, and is virtually identical to the first example in this section. In fact, the first example is shorter, a bit cleaner, and you don’t have to create a pointer, so it’s less redundant.
One more example:
dictionary_t *dictionary_create(void)
{
dictionary_t d;
return &d;
}
void test(void)
{
dictionary_t *d = dictionary_create();
/* ... more stuff here ... */
}Will this work? Nope. It’ll probably crash, too.
Let’s run through our application. First, we declare a pointer to a dictionary. Then, we call dictionary_create(), which creates a dictionary and returns its address. This address is then assigned to our pointer in our test() function. And we already did something wrong.
In dictionary_create(), we create a dictionary. We can play with it as long as we’re still in dictionary_create(). But once we’re not in dictionary_create() anymore, we can’t use it anymore, since it is gone. This is called a local variable: it is created when we enter the function, and it is destroyed when we leave it. So, once we are back in test(), we are assigning the address of a destroyed dictionary to our pointer. Oops.
Meet malloc()
malloc() is a function that you use to request memory from the system. You tell it how many bytes you want, and it’ll return a pointer to a newly allocated block of memory. Here’s an example of how you can use it:
void *foo = malloc(1500);Of course, simply allocating 1500 doesn’t make much sense. If we have a struct called foo_t, we can ask malloc to give us exactly enough memory to put a single foo_t in. Here’s how:
void *foo = malloc(sizeof(foo_t));The memory you allocate using malloc() is always accessible. No matter what function you are in, the memory will never be destroyed. Unless you explicitly tell the system to get rid of your block of memory, of course. Here’s how you do it:
/* get rid of our block of memory */
free(foo);Always free() pointers you receive from malloc(). If you don’t, and keep requesting memory from the system, your application will use more and more memory (they say your application has a “memory leak” or a “memleak”). Eventually, your application will have taken up all the memory on your system: you’ll start getting strange errors, apps will start crashing randomly, your computer will lock up, etc. So, always free the memory you allocated as soon as you don’t need it anymore.
And while I’m ranting: you should always check to make sure malloc() doesn’t return NULL. If it does, the system refused to give you memory, probably because there’s not enough memory available. It is okay to safely terminate your application if a malloc() fails; a simple exit() will work. In more advanced programs, especially ones with a GUI, it is better to first show an error message explaining why the application needs to be terminated.
So what’s so cool about malloc()? I’ll tell you in a bit, but first I’ll rewrite one of the dictionary examples to use malloc():
void test(void)
{
dictionary_t *d = malloc(sizeof(dictionary_t));
dictionary_add(d, "ice", "something cool");
dictionary_add(d, "coffee", "something hot");
dictionary_print(d);
}On the first line, we allocate enough memory to put a single dictionary into. This line is very similar to the following two:
dictionary_t d;
dictionary_t *dp = &d;The difference is, that our dictionary d no longer exists once we have left the test() function. malloc()ed memory, on the other hand, is always accessible.
We can now write a working dictionary_create() function:
void test(void)
{
/* create a dictionary */
dictionary_t *dictionary = dictionary_create();
/* do something with the dictionary */
/* ... */
}
dictionary_t *dictionary_create(void)
{
dictionary_t *d = malloc(sizeof(dictionary_t));
return d;
}The example using malloc() works perfectly, but is incomplete. Once we are done with out dictionary, we should get rid of the memory allocated for it. So let’s add this line at the end of our test() function:
free(d);Save Memory
A dictionary can potentially be very, very large. You could have a dictionary_t type that looks like this:
typedef struct tuple_s {
char word[100];
char explanation[900];
} tuple_t;
typedef struct dictionary_s {
tuple_t tuples[100000];
} dictionary_t;A dictionary has enough space for 100,000 words. A word can be 100 bytes at most, and an explanation can be up to 900 bytes long. A quick calculation teaches us that our dictionary is using 100,000,000 bytes. That’s about a hundred megabytes, used for… nothing.
Even an empty dictionary uses that much memory. Oh, and can you imagine how much we’d be using if we weren’t passing around the address, but the dictionary value itself?
Wouldn’t it be nice to only use the memory you really need? You can, and malloc() is what you need.
Dynamic Arrays
As you have read in the pointer tutorial I told you to read, arrays decay into pointers at times. We can use this to create “fake” arrays by using malloc(): we allocate memory and then pretend the pointer to our newly allocated block of memory is an array that already decayed into a pointer.
If this sounds confusing, let’s just give an example of what I mean. In the next example, I’ll first create a single foo_t, then I’ll create an array of 10 foo_t’s:
void test(void)
{
/* create a single foo_t */
foo_t *foo1 = malloc(sizeof(foo_t));
/* create an array of foo_t's */
foo_t *foo2 = malloc(10 * sizeof(foo_t));
}See that? Instead of allocating memory for a single foo_t, I allocate memory enough to hold ten foo_t’s.
How is it possible that you can do two vastly different things, creating a single foo_t and creating an array of foo_t’s, with very similar code? Well, as it turns out, it is no different at all. In fact, creating a single foo_t is simply creating an array big enough to hold only one.
Once you have allocated the array, you can use it just like any normal array. You can even use the single foo_t as an array. For example:
void test(void)
{
/* create a single foo_t */
foo_t *foo1 = malloc(sizeof(foo_t));
/* create an array of foo_t's */
foo_t *foo2 = malloc(10 * sizeof(foo_t));
/* do something with the first (and only)
* foo_t in the first "array" */
/* foo1[0] = ...; */
/* do something with the third
* foo_t in the second array */
/* foo2[2] = ...; /*
}Example: A Dynamic Dictionary
You now know the basics of memory management in C. Let’s put that to use by writing a dictionary using malloc(). Here’s the structures we’ll beusing:
typedef struct tuple_s {
char *word;
char *explanation;
} tuple_t;
typedef struct dictionary_s {
tuple_t *tuples;
int tuple_count;
} dictionary_t;The dictionary_t type now contains a dynamic array of tuple_t’s called tuples. It also contains the number of tuples in the array; C doesn’t keep track of the number of items in an array so I’ll do that myself.
The tuple_t type now contains two dynamic arrays of char’s called word and explanation. I don’t keep track of how many bytes I allocated for these strings, because I can easily get the length of a string using strlen(). (Remember, strings in C are arrays of char, and a string is terminated by a 0 byte.)
Creating a dictionary takes a bit more work than simply saying…
dictionary_t d;… because we have to take care of allocating memory where we need to. Our dictionary-creating function looks like this:
dictionary_t *dictionary_create(void)
{
/* allocate dictionary */
dictionary_t *d = malloc(sizeof(dictionary_t));
/* initialize dictionary */
d->tuple_count = 0;
d->tuples = NULL;
return d;
}No surprise here. We allocate our dictionary, set some default values, then return it. Note that we don’t allocate the tuples array, because an empty dictionary shouldn’t take up much space; we’ll create the tuples array when it’s necessary.
Next up is a function that adds a word and its explanation to the dictionary. Here’s the first part of the function, which creates or expands the tuples array:
void dictionary_add(
dictionary_t *d,
char *word,
char *explanation
)
{
/* this variable will be used later */
tuple_t *tmp_array;
/* check whether we already have
* an array of tuples */
if(NULL == d->tuples)
{
/* we don't have an array of tuples yet
* so allocate it */
d->tuples = malloc(sizeof(tuple_t));
/* set the number of tuples to 1 */
d->tuple_count = 1;
}
else
{
/* we already have a tuples array
* but it's not big enough
* so allocate a new temporary one */
tmp_array = malloc(
(d->tuple_count+1) * sizeof(tuple_t)
);
/* then copy our old tuples array
* into the new tuples array */
memcpy(
tmp_array,
d->tuples,
d->tuple_count * sizeof(tuple_t)
);
/* then destroy the old tuples array,
* since we don't need it anymore */
free(d->tuples);
/* then let the dictionary use
* the new tuples array */
d->tuples = tmp_array;
/* finally, increase the tuple count */
d->tuple_count++;
}
/* more code below */The comments in the code explain what’s going on, so read them. (And you should always comment your own code as well!)
But this piece of code can be written more cleanly by using realloc(). This function re-allocates an array, changing the size to the new size you specify, but preserving its contents. Using realloc(), our function becomes:
void dictionary_add(
dictionary_t *d,
char *word,
char *explanation
)
{
/* check whether we already have
* an array of tuples */
if(NULL == d->tuples)
{
/* ... */
}
else
{
/* we already have a tuples array
* but it's not big enough
* so allocate a new temporary one */
d->tuples = realloc(
d->tuples,
(d->tuple_count+1) * sizeof(tuple_t)
);
/* then, increase the tuple count */
d->tuple_count++;
}
/* ... */Note that I’ve also gotten rid of the tmp_array declaration since it’s not used anymore.
We can simplify our code even more. realloc(NULL, x) is the same as malloc(x), so we don’t need the if statement:
void dictionary_add(
dictionary_t *d,
char *word,
char *explanation
)
{
/* (re)allocate the tuples array */
d->tuples = realloc(
d->tuples,
(d->tuple_count+1) * sizeof(tuple_t)
);
/* then, increase the tuple count */
d->tuple_count++;
/* ... */Next, we create our tuple with our two strings:
d->tuples[d->tuple_count-1].word
= duplicate_string(word);
d->tuples[d->tuple_count-1].explanation
= duplicate_string(explanation);Our code uses a duplicate_string() function, which we haven’t written yet. This function will take a string as argument, allocate enough memory to contain a string of the same length, and copy the old string into the newly allocated memory. Here’s the implementation:
char *duplicate_string(char *string)
{
/* create a new string
* big enough to hold the contents
* of the original string */
char *new_string = malloc(
(strlen(string)+1) * sizeof(char)
);
/* copy the old string into the new string */
strcpy(new_string, string);
return new_string;
}(There also is a strdup() function which does exactly that, but it’s not “standard”, meaning that some compilers don’t have that function. Which is why I wrote my own.)
And here’s our final function:
void dictionary_add(
dictionary_t *d,
char *word,
char *explanation
)
{
/* (re)allocate the tuples array */
d->tuples = realloc(
d->tuples,
d->tuple_count+1) * sizeof(tuple_t)
);
/* then, increase the tuple count */
d->tuple_count++;
/* copy the word and its explanation
* into the tuple */
d->tuples[d->tuple_count-1].word
= duplicate_string(word);
d->tuples[d->tuple_count-1].explanation
= duplicate_string(explanation);
}One could write many more functions for querying or changing the dictionary. These functions could be quite useful, for example:
/* finds and returns
* the explanation for the given word */
char *dictionary_find(dictionary_t *d, char *word);
/* removes a tuple with the given word */
void dictionary_remove(dictionary_t *d, char *word);
/* removes all tuples */
void dictionary_empty(dictionary_t *d);
/* deallocates the dictionary and its contents */
void dictionary_destroy(dictionary_t *d);I’ll write out dictionary_destroy(); I’ll leave the other functions as an exercise for the reader.
void dictionary_destroy(dictionary_t *d)
{
int i;
/* loop through all tuples */
for(i = 0; i < d->tuple_count; ++i)
{
/* destroy the word */
free(d->tuples[i].word);
/* destroy the explanation */
free(d->tuples[i].explanation);
}
/* destroy the array of tuples */
free(d->tuples);
}This function deallocates everything that was allocated before, which means that there are no memory leaks in our little application.
Further Enhancements
The above code works (or should work) but it is inefficient at times. Of course, I’ve written this tutorial with the C memory management newbie in mind; it would have been unfair to start optimizing the dictionary straight away.
For example, the dictionary always re-allocates the array of tuples when a word is added. Allocating is a somewhat expensive operation, so it is better to allocate space for many tuples at once. Adding another tuple afterwards will not need an extra memory allocation anymore.
Of course, there’s more optimizations you can perform. For example, instead of using an array, maybe a linked list, or a tree, or a hash map could be used. All this is left as an exercise to the reader. (If you can do that, I think you can safely say you’ve mastered C.)
The Final Word
I enjoyed writing this tutorial. I hope you enjoyed reading it too. I also hope, of course, that this tutorial was useful to you.
If you have any remarks on my tutorial—maybe something isn’t clear, or maybe something is wrong—don’t hesitate to contact me. You can either leave a comment using the form below, or contact me directly.
I would like to thank Peter Hosey for his excellent tutorial on pointers, which inspired me to write this article. Many thanks as well to all people who have proof-read. And thanks to you for reading!
May you create many large C programs using malloc(), dear reader!