loading...

Memory Allocation & Dynamic Arrays

giladri profile image Gilad Ri Updated on ・5 min read

C-mpler (13 Part Series)

1) C-mpler Introduction 2) Basic Variables & Operators 3 ... 11 3) Intro to I/O 4) Conditions 5) Practice #1 6) Loops 7) Compilation & Precompilation 8) Static Arrays 9) Practice #2 10) Memory Addresses & Pointers 11) Memory Allocation & Dynamic Arrays 12) Basic Sorting 13) Recursion

Let's begin with the solution to the challenge:

#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:

#include <malloc.h>

int * pointer = (int *) malloc(sizeof(int));

Or, in general:

#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:

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:

#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 (an application which can save student's grades and calculates the average) in a better way:

#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 of Nicholas Nethercote from 2014.

Always remember, it's much C-mpler than you thought!

Regards,
Gilad

C-mpler (13 Part Series)

1) C-mpler Introduction 2) Basic Variables & Operators 3 ... 11 3) Intro to I/O 4) Conditions 5) Practice #1 6) Loops 7) Compilation & Precompilation 8) Static Arrays 9) Practice #2 10) Memory Addresses & Pointers 11) Memory Allocation & Dynamic Arrays 12) Basic Sorting 13) Recursion

Posted on by:

Discussion

markdown guide