WARNING: These are old, buggy notes from many years ago, badly converted to wiki format. Even the code examples are broken in various ways. For more up-to-date notes on the subject, see C/Pointers.

1. Dynamic storage allocation in C

2. Overview

The C programming language does not provide a built-in mechanism for allocating space at run-time. Instead, the standard library contains three functions for managing a region of memory called the heap. The implementation of these functions is similar to the implementation of the alloc function in Section 5.3 of K&R. They are declared in stdlib.h, so you will need to #include that header file before using them.

3. Allocating space with malloc

The function for allocating space is malloc. Its declaration is:

   1 void *malloc(size_t size);

The return type, (void *), is the generic pointer type in C; it can be cast freely to and from other pointer types, and is intended to represent an address unadorned with any knowledge of what is stored at that address. The argument is of type size_t (which is typically an alias for unsigned long declared using typedef), and indicates how many bytes of storage you want to grab. You can find out how many bytes you need using sizeof; for example, if you want to allocate an array of n values of type int, you could write:

   1 int *a;
   2 
   3 a = malloc(sizeof(int) * n);

After executing the malloc operation, you can treat a as an ordinary array of ints, just as if you had declared it with int a[10];.

3.1. Testing the return value of malloc

It is generally a good idea to test the return value of malloc, since it might return a null pointer if it can't get you the space you asked for. Here is a typical test:

   1 a = malloc(sizeof(*a) * SOME_HUGE_VALUE);
   2 if(a == 0) {
   3 /* respond to the disastrous error gracefully */
   4 fprintf(stderr, "AAAAAARGGHGGHHGH!\n");
   5 abort();
   6 }

4. Freeing space with free

The free function has the opposite purpose of malloc; given something you've previous allocated, you can call free to give it up.

The declaration for free looks like this:

   1 void free(void *);

And a typical use might be:

   1 int *a;
   2 
   3 a = malloc(sizeof(*a) * n);
   4 /* use a for a while */
   5 free(a);

4.1. Storage allocation discipline

It is very important to free everything you allocate when you are done with it. Failure to do this causes storage leaks, bugs in which a program slowly consumes more and more memory over time until it can't allocate any more. Whenever you allocate something, you should have a plan for how to get rid of it. Some typical cases: 1.A block is allocated within some function and used only inside that function. In this case it should be freed before the function returns. 1.A block is allocated inside a function and then returned to the function's caller. The caller is now responsible for freeing the block (and you should put a comment on the function to this effect). If a function constructs some complicated data structure that can't simply be fed to free, it is polite to provide a second destructor function that tears down the data structure and frees all of its internal pieces. The same discipline that applies to malloc and free applies to constructors and destructors; if you make something by calling a constructor function you are responsible for making sure that the destructor is called when you are done with it.

Though it is not a problem to have un-freed blocks when a program exits, since the operating system will recover all space the program used at this point, good programming style dictates freeing your storage on the way out. This will keep you disciplined about balancing calls to malloc and free, and becomes especially important if somebody takes your program and rewrites it as a subroutine in a larger program. When using constructors and destructors, calling the destructor also takes care of any additional housekeeping the destructor might do.

4.2. Perils of buffer overflows

Writing off the end of a block allocated with malloc is particularly dangerous, since it is likely to overwrite internal state used by the storage allocator. Such bugs can be very hard to find, since the symptom of such a bug may be that malloc or free mysteriously segfaults on some completely unrelated call much later in the execution of the program.

One particular trap of this sort that is easy to fall into is to forget to allocate an extra byte to store the '\0' character at the end of the string. Here is an example of the right way to do this: {{{/* returns a malloc'd copy of its argument, or 0 if malloc fails */ char * my_strdup(const char *s) { char *s2;

s2 = malloc(strlen(s)+1); +1 for terminating null if(s2 == 0) return 0; else strcpy(s2, s); return s2; } }}}

4.3. The lingering curse of referencing freed blocks

A common error is to free a block and then reference it. Don't do this; you don't know if malloc has already given out the storage to somebody else, or if free scribbled over part of the block as part of its internal operations. If you need information from a block that you are about to free, copy it somewhere else first.

5. Dynamic arrays using realloc

Some languages provide a dynamic array type whose size can be changed after the array is created. C does not, but a similar effect can be obtained using the realloc function. This function takes a block that was previously obtained from malloc and changes its size. If there is not enough room to keep the block where it is, realloc makes a new copy of the block and frees the original. In either case it returns a pointer to the new location. Like malloc, realloc returns 0 if it fails; however, in this case the original block is not changed or freed.

An example of realloc in action:

   1 int *a;
   2 
   3 a = malloc(sizeof(*a) * 10);        /* now a holds 10 ints */
   4 a = realloc(a, sizeof(*a) * 20);    /* now a holds 20 ints */
   5 free(a);                            /* now a is gone! */

Note that calling realloc a lot can get pretty expensive, since it may need to copy the entire contents of a possibly very large block every time you call it. If you know that you are going to be growing a block many times, one trick is to keep track of its actual size separately from the size of the part of it that is used, and double the actual size only when needed. In this case the amortized cost of the reallocations is just a constant amount for each new element.

6. Example of building a data structure with malloc

Here is an example of a program that includes a constructor and destructor function for a two-dimensional array data structure (implemented as an array of pointers to pointers) that requires many calls to malloc to construct:

6.0.1. malloc2d.c

   1 /* Demo program for malloc'd two-dimensional arrays */
   2 
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 
   6 /* returns a two-dimensional array with num_rows rows and 
   7 * rowsize bytes per row, or 0 on allocation failure.
   8 * The caller is responsible for freeing the result with free2d. */
   9 void **
  10 malloc2d (size_t num_rows, size_t rowsize)
  11 {
  12   void **a;
  13   size_t i;
  14 
  15 /* a is an array of void * pointers that point to the rows */
  16 /* The last element is 0, so free2d can detect the last row */
  17   a = malloc (sizeof (void *) * (num_rows + 1));        /* one extra for sentinel */
  18   if (a == 0)
  19     return 0;
  20 
  21 /* now allocate the actual rows */
  22   for (i = 0; i < num_rows; i++)
  23     {
  24       a[i] = malloc (rowsize);
  25       if (a[i] == 0)
  26         {
  27 /* if we were being really careful, we'd free previous
  28 * rows and a here. */
  29           return 0;
  30         }
  31     }
  32 
  33 /* initialize the sentinel value */
  34   a[num_rows] = 0;
  35 
  36   return a;
  37 }
  38 
  39 /* frees a 2d array created by malloc2d */
  40 void
  41 free2d (void **a)
  42 {
  43   void **row;
  44 
  45 /* notice how we free everything malloc'd in malloc2d in reverse order */
  46   for (row = a; *row != 0; row++)
  47     {
  48       free (*row);
  49     }
  50   free (a);
  51 }
  52 
  53 int
  54 main (int argc, char **argv)
  55 {
  56   int rows;
  57   int cols;
  58   int **a;
  59   int i;
  60   int j;
  61 
  62   if (argc != 3)
  63     {
  64       fprintf (stderr, "Usage: %s rows cols\n", argv[0]);
  65       return 1;
  66     }
  67 /* else */
  68 
  69   rows = atoi (argv[1]);
  70   cols = atoi (argv[2]);
  71 
  72   a = malloc2d (rows, cols * sizeof (int));
  73   if (a == 0)
  74     {
  75       fprintf (stderr, "malloc2d failed, exiting\n");
  76       return 2;
  77     }
  78 
  79   for (i = 0; i < rows; i++)
  80     {
  81       for (j = 0; j < cols; j++)
  82         {
  83           a[i][j] = i - j;
  84         }
  85     }
  86 
  87   for (i = 0; i < rows; i++)
  88     {
  89       for (j = 0; j < cols; j++)
  90         {
  91           printf ("%4d", a[i][j]);
  92         }
  93       putchar ('\n');
  94     }
  95 
  96   free2d (a);                   /* always clean up */
  97 
  98   return 0;
  99 }

6.0.2. Makefile

CC= gcc
CFLAGS=-g3 -ansi -pedantic -Wall

all:

test: malloc2d
        ./malloc2d 4 6
        @echo OK!

malloc2d: malloc2d.o
        $(CC) $(CFLAGS) -o $@ $^

clean:
        rm -f *.o malloc2d

6.0.3. Output of make test

{{{$ make test gcc -g3 -ansi -pedantic -Wall -c -o malloc2d.o malloc2d.c malloc2d.c: In function `main': malloc2d.c:68: warning: assignment from incompatible pointer type malloc2d.c:87: warning: passing arg 1 of `free2d' from incompatible pointer type gcc -g3 -ansi -pedantic -Wall -o malloc2d malloc2d.o ./malloc2d 4 6 0 -1 -2 -3 -4 -5 1 0 -1 -2 -3 -4 2 1 0 -1 -2 -3 3 2 1 0 -1 -2 OK! }}}

CategoryProgrammingNotes