# IC221: Systems Programming (SP16)

Home Policy Calendar Resources

# Lec 09: Dynamic Array Allocations and Data Representation Model

## 1 Dynamic Array Allocation

From the last class, we discuss the standard memory allocation situation where we need to allocate memory on the heap.

```int * p = (int *) malloc(sizeof(int));
*p = 10;
```
``` STACK          HEAP
.---.----.     .----.
| p |  .-+---->| 10 |
'---'----'     '----'
```

On the left, we use `malloc()` to allocate enough memory to store an `int`, and we assign the address of that memory to the integer pointer, `p`. On the right, is the stack diagram of this allocation. The pointer `p` exists on the stack, but it now references the memory on the heap.

We now know, in excruciating detail, that arrays and pointers are the same. This idea extends to the dynamic allocation of arrays. If we have an integer pointer `p` it can point to a single integer, or it can point to the start of a sequence of integers. A sequence of contiguous integers is an array. All we need is to allocate enough space to store all those integers, and `malloc()` can do that too.

Consider what's needed to allocate an array of a given size. For example, how many bytes would be needed to allocate an integer array of size 5? There are 4-bytes for each integer, and the array holds 5 integers: 20 bytes. To allocate the array, we just ask `malloc()` to allocate 20 bytes, and cast the result to an `int *`, like below.

```int * p = (int *) malloc(5*sizeof(int));
p[0] = 10;
p[1] = 20;
//...
p[4] = 50;
```
``` STACK          HEAP
.---.----.     .----.
| p |  .-+---->| 10 | p[0]
'---'----'     |----|
| 20 | p[1]
|----|
:    :
.    .
:    :
|----|
| 50 | p[4]
'----'
```

The result of the `malloc()` is 20 bytes of contiguous memory which is referenced by an integer pointer, which is the same as an array! We can even use the array indexing method, `[]`, to access and assign to the array.

### 1.1 Array allocation with `calloc()`

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
}
```

### 1.2 Double Pointer Arrays for Advanced Data Types

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.

### 1.3 Deallocating Double Pointers

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
}
```

## 2 Data Representations

To end this lesson, I want to turn our attention to more pointer and memory issues relating to the underlying data representation. While we might not use this information a ton in the class, it is an integral part of C and how we understand data storage in memory. To start, we'll review the arrays and pointer relationship again, followed by some more peculiar things we can do because of that relationship.

### 2.1 Pointers and Arrays are still the same!

As have been noted a number of times now, arrays and pointers are actually the same, mostly. The only difference is that when you declare an array, e.g., `int array[10]`, the variable array is declared static, as in it cannot change unlike a declared pointer, e.g., `int * p`. However, we have seen how we can use the pointer to act like an array, such as below:

```int a[5] = {10,20,30,40,50}; //inex is value
int * p = a; // (1)
p[0] = 5; //(2)
printf("%d\n", a[0]); //prints 5 !!
```
```      STACK (1)         |        STACK  (2)
.----.----.       |       .----.----.
| a  |  .-+--.    |       | a  |  .-+--.
|----|----|  |    |       |----|----|  |
a[0]  |    | 10 |<-.    | a[0]  |    | 5  |<-.
|    |    |<-.    |       |    |    |<-.
|----|----|  |    |       |----|----|  |
a[1]  |    | 20 |  |    | a[1]  |    | 20 |  |
|----|----|  |    |       |----|----|  |
:    :    :  |    |       :    :    :  |
.    .    .  |    |       .    .    .  |
:    :    :  |    |       :    :    :  |
|----|----|  |    |       |----|----|  |
a[4]  |    | 50 |  |    | a[4]  |    | 50 |  |
|----|----|  |    |       |----|----|  |
| p  |  .-+--'    |       | p  |  .-+--'
'----'----'       |       '----'----'
```

We also took it one step further to demonstrate how the indexing function, e.g., `p[i]`, is really de-reference using pointer arithmetic, `p[i] = *(p+i)`

```int a[5] = {10,20,30,40,50};
int * p = a; // (1)
*(p+1) = 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  |  | <- p+1
|----|----|  |    |       |----|----|  |
:    :    :  |    |       :    :    :  |
.    .    .  |    |       .    .    .  |
:    :    :  |    |       :    :    :  |
|----|----|  |    |       |----|----|  |
a[4]  |    | 50 |  |    | a[4]  |    | 50 |  |
|----|----|  |    |       |----|----|  |
| p  |  .-+--'    |       | p  |  .-+--'
'----'----'       |       '----'----'
```

No surprises so far, but lets take a look a bit more at the pointer arithmetic and de-referencing. For one, an integer is 4 bytes in length, but when we add 1 to the pointer value of `p` we do not actually increase the pointer value by 1 but by 4 bytes to the start of the next integer. We can see this if we add the following line to the program:

```printf("p: %p p+1: %p \n", p,p+1);
```
```#> ./pointer_arithmetic
5
p: 0x7fff585f5a10 p+1: 0x7fff585f5a14
```

Note that the pointer values of p and p+1 is 4 bytes difference. This is what we want it do and not reference a byte within the integer, but we should also be asking ourselves, what if we do want to reference the byte within the integer? To do this, we can take advantage of a peculiarity of pointers in that they can be arbitrarily cast to other pointer types.

### 2.2 Pointer Casting to Access Individual Byes

Pointers are weird. You've seen that already, but now we are going to take a few more steps down the rabbit hole. First consider the program below:

```int main(int argc, char *argv[]){

int a = 10;             //declare an integer
char * p = (char *) &a; //save address of integer as char *

int i;
printf("0x");
for(i=0;i<4;i++){
printf("%02x",p[i]); //print the bytes of the integer in hex!
}
printf("\n");

}
```

The program assigns to `p`, a character pointer, the address of `a`, an integer. 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.

The type of the pointer does impact how we interpret the data the memory address references. When we say `&a` we are providing a memory address that references data for an integer. If we interpret that memory address as a `char *` instead, then we can treat those 4 bytes of the integer as 4 bytes of a character array.

If you follow the program further, we can now go ahead an interpret the individual bytes of the integer and print them out. To do so, we used hexadecimal, which you should recall, two hex-digits can represent one byte. After running the program, we get the following: (Note, we write '0x' as the leading part of hex digits to indicate that this is in hexadecimal.)

```#> ./pointer_cast
0x0a000000
```

Those are the bytes of the integer that stores 10. In hex, the hex-digit 'a' is ten, and we see a 0x0a in the output. However, it doesn't seem to be in the right place. It is at the front instead of the end. Wouldn't 0x00000000a make more sense? Sure, to us measly humans, but to computers, what does it matter if numbers are written forward and backward?

### 2.3 Byte Ordering

Back in the day, there were two major architecture for data representation.: Big Endian and Little Endian. The difference is the order of the bytes in building larger data elements. All major architectures we will use (except for one later in the course) uses Little Endian. In Little Endian, the least significant bytes come before the more significant bytes, which is backward from how humans read numbers.

To see this in action, let's do another example of pointer casting, this time with a larger integer value and one we can recognize more easily; my favorite number, 0xdeadbeef. Here's a program to print the individual bytes of that number:

```int main(int argc, char *argv[]){

unsigned int a = 0xdeadbeef;    //hex number
unsigned char * p = (unsigned char *) &a;

int i;
printf("0x");
for(i=0;i<4;i++){
printf("%02x",p[i]);
}
printf("\n");

}
```

Now the output:

```#> ./deadbeef