Memory Allocation & Dynamic Arrays
Tags: c, beginners
Published: 2019-06-27 09:08:40

Let's begin with the solution to the challenge:
```cpp
#include <stdio.h>

void swap(int * x, int * y) {
    *x += *y;     // x == 13
    *y = *x - *y; // y == 10
    *x -= *y;     // x == 3
}

int main() {
    int x = 10;
    int y = 3;
    swap(&x, &y);
    printf("x=%d, y=%d", x, y);
    // Success
    return 0;
}
```
Ok, now to our topic: Memory Allocation, and how to initialize dynamic arrays.

As you remember, in the previous post we learned about memory and pointers. In this post, we will go deeper into the subject of memory. The memory of our computer is divided into two types:  __Stack__ and __Heap__.

### __Stack__
We already familiar with the Stack: any time we have created a variable or a function so far, we allocated it on the Stack. To be more accurate: on the Stack we can allocate things only if __we know exactly how much space we will need to allocate before the compilation process__. That means that the Stack is used only for __static memory allocation__. (remember what we said about Static Arrays?)

Spaces allocated on the Stack are freed ("cleared")  when their block scope is ended. For example, function variables are deleted when the function ended - automatically. (To be more accurate, they are not actually deleted, but "the computer" just let our program to overwrite their spaces - "the computer stops keeping their positions and therefore future memory allocations can run over them").

### __Heap__
The new memory type we will talk about it in this post. We can allocate spaces (for variables) on the Heap __during run-time of any size we want__, (as long that there is enough space left). Moreover, we can reallocate a space or free ("clear") a space at any time we want. Pay attention that this type of memory is not freed unless we make it do so. It's a __good thing__ if we want to save a value of something for a long time (longer than a function scope, for example), but also a __bad thing__ because we must remember to free these spaces, or we will be in trouble. At some point, we may run out of memory and our program will crash. In our case, it does not sound so threatening - "Oh no, our silly program may crash" - but when it comes to a program of a big bank, for example, which every second of downtime can cost the bank millions of dollars, it is really scary! __So, please remember to free any space you allocate on the Heap, at the right time - neither too early nor too late.__


### __Memory allocation__
Ok, so let's see how we can allocate a variable on the Heap:
```cpp
#include <malloc.h>

int * pointer = (int *) malloc(sizeof(int));
```
Or, in general:
```cpp
#include <malloc.h>

[type] [pointer_name] = ([type]) malloc([number_of_bytes_we_want]);
```
Let's divide this into parts:
In the first part, __[type] [pointer_name]__ we just initialize a pointer which points at the space we will allocate on the Heap. The next part, the part which after the '=' is the interesting part. At first, we just convert the type of what the __`malloc`__ function outputs. In C, you can convert a type of variable if you put a type in brackets before it. For example:
```cpp
int x = 10;
double y = (double) x;
```
The __`malloc`__ function's output type is (void *). This type is like a joker type, you can convert it to whatever type you want. Therefore, because we wanted it to match the pointer we converted it to (int *). In other words, we just need to convert the output type so it will match the pointer type.

And the final part, the __`malloc`__ input. The __`malloc`__ function receives a __size__ and returns a __pointer to allocated space__ of this __size__. We can choose whatever size we want, but usually, we use the __`sizeof`__ function which gets a type of variable (__int__, for example) and returns its size in bytes. Normally, the size of __int__ is 4 bytes, but this may change as a result of the advancement of technology and may also vary between operating systems, compilers and various processors, and so on. Therefore, we prefer using __`sizeof`__, and in this way, we have no problem at all getting the size of a variable type.

### __Dynamic Arrays__
Finally, let's see how we can initialize a dynamic array using the __`malloc`__ function:
```cpp
#include <stdio.h>
#include <malloc.h>

#define SIZE 10

int main() {
	// Allocates an array of size SIZE
	int * grades = (int *) malloc(SIZE * sizeof(int));
	// Frees the array
	free(grades);
	// Success
	return 0;
}
```
As you can see, we have just multiplied the size of the variable type in the number of elements we want for our array.

The __`free`__ function in the example above is how we can free our allocated memory. We just have to send it the pointer to our memory allocation as input.

To summarize this post, let's rewrite the example from the [Static Arrays post](https://dev.to/giladri/static-arrays-29m2) (an application which can save student's grades and calculates the average) in a better way:
```cpp
#include <stdio.h>
#include <malloc.h>

#define START_SIZE 2

void getGrades(int * grades, int * index, int * size) {
	int grade;
	printf("Insert the grades. In order to stop, please enter -1\n");
	do {
		printf("Grade #%d: ", *index + 1);
		scanf("%d", &grade);
		// Checks the grade
		if (grade >= 0 && grade <= 100) {
			// Checks if there is enough space in the array
			if (*index >= *size) {
				// There isn't, doubles the size of the array
				*size *= 2;
				realloc(grades, *size * sizeof(int));
				printf("Re-allocated the array to size: %d\n", *size);
			}
			// Inserts the grade into the array and increases the index by 1
			grades[*index] = grade;
			*index += 1;
		} else if (grade == -1) {
			// Stops
			printf("Thank you!\n");
		} else {
			// Error
			printf("Invalid grade, please try again...\n");
		}
	} while (grade != -1);
}

double calcAverage(int * grades, int index) {
	int i;
	int sum = 0;
	for (i = 0; i < index; i++) {
		sum += grades[i];
	}
	return (double) sum / (double) index;
}

int main() {
	int index = 0;
	int size = START_SIZE;
	// Allocates an array of size 'START_SIZE'
	int * grades = (int *) malloc(size * sizeof(int));
	// Gets the grades from the user as input
	getGrades(grades, &index, &size);
	// Prints the average
	printf("Your average is: %.2f\n", calcAverage(grades, index));
	// Frees the array
	free(grades);
	// Success
	return 0;
}
```
Console example:
```
Insert the grades. In order to stop, please enter -1
Grade #1: 100
Grade #2: 90
Grade #3: 95
Re-allocated the array to size: 4
Grade #4: 100
Grade #5: 87
Re-allocated the array to size: 8
Grade #6: 94
Grade #7: 93
Grade #8: 86
Grade #9: 99
Re-allocated the array to size: 16
Grade #10: 88
Grade #11: -1
Thank you!
Your average is: 93.20
```
As you can see, we used the __`realloc`__ function which gets a pointer and a new size and re-allocates a space of the new size we want (and copies all the values from the old space). If you want to know why we __double__ the size each time and don't just add some more space (size + 10, for example) you can read this short [post](https://blog.mozilla.org/nnethercote/2014/11/04/please-grow-your-buffers-exponentially/) of Nicholas Nethercote from 2014.

####__Always remember, it's much C-mpler than you thought!__

Regards,
Gilad