What makes this example from the previous section interesting is that it demonstrates how pointers and arrays are actually the same thing. But, you might be asking, we were only able to find the first item of the array with the pointer, what if we want to access the other items? To do that, we can use pointer arithmetic.

Pointer arithmetic is the process of using pointer values computation to alter and access memory for programming tasks. Let's continue the example from above, but this time, let's now use p to change the value in index 1 of the array, a[1].

int a[5] = {10,20,30,40,50}; //inex is value
int * p = a+1; // (1)
*p = 5; //(2)
printf("%d\n", a[1]); //prints 5 !!

      STACK (1)         |        STACK  (2)
      .----.----.       |       .----.----.   
      | a  |  .-+--.    |       | a  |  .-+--.
      |----|----|  |    |       |----|----|  |
a[0]  |    | 10 |<-.    | a[0]  |    | 10 |<-.
      |----|----|       |       |----|----| 
a[1]  |    | 20 |<-.    | a[1]  |    | 5  |<-.
      |----|----|  |    |       |----|----|  |
      :    :    :  |    |       :    :    :  |
      .    .    .  |    |       .    .    .  |
      :    :    :  |    |       :    :    :  |
      |----|----|  |    |       |----|----|  |
a[4]  |    | 50 |  |    | a[4]  |    | 50 |  |
      |----|----|  |    |       |----|----|  |
      | p  |  .-+--'    |       | p  |  .-+--'
      '----'----'       |       '----'----'

At point (1) in the code, we assign the pointer value to the a+1. Reviewing the stack diagram, you can see that a points to the start of the array, so 1 more then the start of the array is the second index of the array. Thus, p references a[1] and the dereferenced assignment of p changes the second value in the array.

Wait? There may seem like there's something a bit off with this example. We know that an integer is 4-bytes in size, so wouldn't the value 1 added to a memory address shift the pointer by just 1-byte, which would point into the middle of an integer? Like below, where we expand each memory block in the stack diagram to represent a single byte.

(WRONG INTERPRETATION: each block is a byte)  

         .-------------------------------.
  a   .--|   |   |   |   |   |   |   |   |      //pointers are 8 bytes
      |  |................................
 a[0] '->|   |   |   |   |                      //integers are 4 bytes
         |...............|                   
         :     ^         :
      .--------' 
      |  :               :
      |  |...............|
 a[4] |  |   |   |   |   |     
      |  |................................
  p   '--|   |   |   |   |   |   |   |   |      //p points to 2nd byte of
         '-------------------------------'      //of a[0] ??

The answer, of course, is no. The above does not happen and it's because pointer arithmetic is different than numeric arithmetic computation. When you add numeric values to pointers, like p+1, the C compiler recognizes this as pointer arithmetic and knows that you don't actually want to refer to individual bytes of the larger type, like the second byte of an integer. Instead, it converts the pointer arithmetic into an increment of the pointer value by the memory size of the type the pointer references. For example,

p = a + 1; //increments the pointer value by the size of an int

Pointer arithmetic also lies at the heart of array indexing, and if you've ever wondered why arrays are indexed at 0, it's because of pointer arithmetic. Let's first consider what an index with [] must mean in the context of arrays, for example, when we say a[0] for an integer array.

Well a is just a pointer to the start of the array, and a[0] returns the integer value there. So a[0] is the same as dereferencing the pointer a. Now consider a[1]. In this case we want to return the second value of the array, and we know from pointer arithmetic that the second value exists at a+1. If we dereference a+1, then we will return the value at index 1. Which means that *(a+1), the dereference of the pointer value incremented by 1, is the same as a[1]. We can continue this further for the rest of the array indexes, and we find that the index operation is the same as pointer arithmetic with a dereference, like in the diagram below:

      .---.
a --> |   |  a[0] == *(a+0) 
      +---+
      |   |  a[1] == *(a+1) 
      +---+
      |   |  a[2] == *(a+2)
      +---+
      :   :  etc.
      '   '

Now that you understand pointer arithmetic a bit better and how it accounts for the size of the types being referenced, you might be wondering, what if I want to access individual bytes of the referenced daya type? Like, the second byte of an integer? To do this, you can use pointer casting and pointer arithmetic using a type that is 1-byte in size, such as a char.

int a = 3;
char *p = (char *) &a; //p now points to a, 
                       //but treats the memory 
                       //like an array of chars

printf("%x\n", p[3]); //prints the 4th byte of int a

After assigning p the address of a, you can now think of the 4-byte integer memory as a 4-byte array of chars, since each char is 1 byte. This then allows us to use the [] indexing to acces the individual bytes.

You should feel a bit dirty doing this. Having a char * reference an integer is wrong, right? It is wrong, but probably not for the reasons you think. It's actually perfectly reasonable with respect to pointers. A pointer is just a memory address. The memory address of an int or a char is the same size, 8-bytes, so who cares what it is called. In fact, this is exactly the kind of memory manipulation power in C that makes it great … and terrible. What's wrong about this code is that it is nonintuitive and relies on peculiarities of C. Just because you can do something in C doesn't make it the right choice.

Because allocating items as an array is so common, we have a special function for it.

int *p = (int *) calloc(5, sizeof(int));

While allocating arrays with malloc() is simple and effective, it can be problematic. First off, malloc() makes no guarantee that memory allocated will be clean — it can be anything. For example, consider this simple program:

//allocate a 20 byte array
int * a = (int *) malloc(20 * sizeof(int));
int i;
for(i = 0; i < 20; i++){
  printf("%d\n",i);
}

What is the output of this program? We don't know. It's undefined. The allocated memory from malloc() can have any value, usually whatever value the memory used to have if it was previously allocated. If you don't believe me, try running and executing the program a few times, and you'll see that you can get widely different results.

The second problem with using malloc() is that it is a multi-purpose allocation tool. It is generally designed to allocate memory of a given size that can be used for both arrays and other data types. This means that to allocate an array of the right size, you have to perform an arithmetic computation, like 20 * sizeof(int), which is non-intuitive and reduces the readability of code.

To address these issues, there is a special purpose allocator that is a lot more effective for array allocation. It's calloc() or the counting allocator. It's usage is as follows.

//  The number of items 
//  to be allocated      --.
//                         |
//                         v
  int * a = (int *) calloc(20, sizeof(int));
//                                  ^
//                                  |      
//                            The size of each item

calloc() takes two arguments, the number of items needed and the size of each item. For an array, that is the length of the array, and the size is the sizeof() the array type, which is int in this case. Not only does calloc() make the array allocation more straight forward, it will also zero-out or clean the memory that is allocated. For example, this program will always print 0's.

//allocate a 20 byte array
int * a = (int *) calloc(20, sizeof(int));
int i;
for(i = 0; i < 20; i++){
  printf("%d\n",i); // 0 b/c calloc zeros out allocated memory
}

So far in this lesson we've discussed allocating basic types, but we can also dynamically allocate memory for other types, such as strings and structures. For example, consider the pair_t structure below:

typedef struct{
  int left;
  int right;
} pair_t;

Suppose we want an array of such structures, then we can use dynamic allocation using calloc() to allocate array of pair_t's just like we did to generate an array of int's.

pair_t * pairs = (pair_t *) calloc(10, sizeof(pair_t));

pairs[0].left  =  2;  //do assignment
pairs[0].right = 10;

As you can see, once the array is generated, we can access each individual pair_t using array indexing, and the array was allocated with enough memory for 10 pair_t strucutes we use the . operator to access each item.

This alocation is fine for many circumstances, but it can pose some subtle problems in certain situations. Suppose we wanted to keep track of which pairs have been set and which have not? Could we just look at the array of pairs and know this? We can't because calloc() will zero out all the pairs and we can't tell difference between a pair just stores to zeros and one that was not set. Another problem could occur if we want to be memory efficient. What if we only want to allocate the full pair_t struct as needed?

Adding an extra layer of redirection makes such tasks much easier. Essentially, we wish to construct an array of pointers to the desired type, or a pointer to a pointer, a double pointer. Instead of having an array of pair_t's, we have an array of pointers to pair_t's. Then we can know if the pair_t is set because either the pointer will be NULL or it will reference a pair_t, and we can allocate new pair_t's as needed. The allocation is as follows:

//     .-- Double Pointer -.          array of pair_t pointers
//     |                   |                      |
//     v                   v                      v
pair_t ** pairs = (pair_t **) calloc(10, sizeof(pair_t *));

pairs[0] = malloc(sizeof(pair_t)); //allocate memory for a new pair_t

pairs[0]->left  =  2; //do assignment
pairs[0]->right = 10;

While at first this might seem like a funky and unnecessary way of allocating structure types, but it is quite common in practice. It is often the case that you will need to store and reference a number of structure types, the amount of them is unknown ahead of time. Managing all this data requires careful programing and memory management. Keeping track of what has been allocated, what has been freed, and what resources are newly available are the key to designing good programs.

A common mistake when dealing with double pointers is poor deallocation. Let's extend the above example by modularizing the process of creating the array of pair pointers and the addition of a new pair into functions to simplify the code. This might look like below.

pair_t ** new_pairs(){
    pair_t ** pairs = (pair_t **) calloc(10, sizeof(pair_t *));
    return pairs;
}

pair_t * add_pair(pair_t ** pairs, int left , int right){
  int i;
  for(i=0;i<10;i++){
    if(pairs[i] == NULL){
      pairs[i] = malloc(sizeof(pair_t)); //allocate

      pairs[i]->left = left;//do asignment
      pairs[i]->right = right;

      return pairs[i]; //return the new pair
    }
  }  
  return NULL; //list full, return NULL for eror
}

int main(int argc, char * argv[]){
  pair_t ** pairs = new_pairs(); //create a new pair array

  add_pair(pairs, 2, 10); //assign a new pair
  add_pair(pairs, 0, 3); //assign a new pair
  //...
  // deallocate?
}

Now, the addition of a new pair is as simple as calling add_pair() which will find the first NULL pointer in the pairs array to do the insert. If the array is full, it returns NULL on error.

This is great! We've just generalized our double pointer array into a mini data structure that is memory efficient and easy to use. There's one problem though, how do we properly deallocate the double pointer to make sure we don't have a memory leak? The following will not work:

void delete_pairs(pair_t ** pairs){
   free(pairs); // memory leak!!!  
}

This will cause a memory leak because the index of pairs are pointers which may reference other allocated memory. You can't just free up the larger array without first deallocating any memory referenced from within the array. If you do, then the address of that memory will be lost, thus leaking the memory.

Instead, you have to be more careful and generate a code block to deallocate it properly.

void delete_pairs(pair_t ** pairs){
  int i;

  for(i=0;i<10;i++){
    if (pairs[i] != NULL){ //don't want to free(NULL), cause coredump
       free(pairs[i]); //free allocated memory within array
    }
  }

  free(pairs); //free array
}