Memory

This chapter focuses on getting you familiar with the memory management in C. This is a very important topic as it is the base of all the data structures and algorithms. First, lets see a very basic overview of your application' memory.

As discussed in the previous entry, the application memory is divided into 4 segments. The stack, the heap, the static and the code. The stack is used for storing the local variables, the heap is used for dynamic memory allocation, the static is used for storing the global and static variables and the code is used for storing the instructions.

Let us write some demo code to understand the memory management in C.

#include <stdio.h>
 
int total = 0; // global variable
 
int square(int x) {
    int y = x * x; // local variable
    return y;
}
 
int sumofsquares(int a, int b) {
    int x = square(a);
    int y = square(b);
    return x + y;
}
 
int main() {
    int a = 3, b = 4;
    total = sumofsquares(a, b);
    printf("Total: %d\n", total);
    return 0;
}

For this example the memory would look something like this:

In the stack, we start from the main function, as the sumofsquares function is called, the main stack frame is paused and another stack frame of sumofsquares is made.

In the sumofsquares function, the square function is called, so another stack frame is made for the square function.

The square function returns the value to the sumofsquares function and then the sumofsquares function returns the value to the main function. As soon as a function returns a value, its stack frame is popped off the stack.

If our call stack grows beyond the given size, it creates a condition called Stack Overflow and it will cause the program to crash. This happens frequently when writing bad recursion code.

Limitations of stack // Heap

1. The stack is of fixed size. It cannot grow during runtime.
2. The allocation and deallocation happens by a fixed rule of appending and popping. It is not possible to manipulate the scope of a variable
3. The stack is not flexible. It is not possible to allocate memory at runtime.

Unlike stack, heap is not fixed. It's size can vary during the lifetime of the program. Devs get the full control of the memory allocation and deallocation. The heap will continue to grow until the system itself runs out of memory (this can be dangerous). The heap is also called the free store. Using the heap is also called

Dynamic Memory Allocation

Now let us take a deep dive at dynamic memory allocation with this code. It might get a bit confusing from here.

int main() {
    int a; // this goes on the stack
    int *p;
    p = (int *)malloc(sizeof(int)); // this goes on the heap
 
    *p = 37;
 
    p = (int *)malloc(sizeof(int));
    *p = 45;
}

In the above code, we use the malloc function to allocate 4 bytes (sizeof int) on the heap. The malloc function returns a pointer to the allocated memory. And then we assigned the value of 37 to the memory location pointed by p.

So far this is how our memory would look like

Now, we allocate another 4 bytes on the heap and assign the value of 45 to it. Notice the word another. This means that the previous memory location still lives on the heap and we wasting memory.

To free this memory we use the free function.

int main() {
    int a; // this goes on the stack
    int *p;
    p = (int *)malloc(sizeof(int)); // this goes on the heap
 
    *p = 37;
 
    free(p); // free the memory
 
    p = (int *)malloc(sizeof(int));
    *p = 45;
}

Malloc, Calloc and Realloc

Malloc takes in a single argument, of type size_t, which is a fancy way to say positive integer. That arguement is how many bytes we want to allocate in our memory. Malloc returns a void pointer to the allocated memory that we can cast to any type.

What if we want to allocate memory for an array of integers with malloc? We can do that by multiplying the size of an integer by the number of elements we want in the array.

int no_of_elements = 5;
int *arr = (int *)malloc(no_of_elements * sizeof(int));
 
// now we can access the elements of the array like this
*arr = 1; // arr[0] = 1
*(arr + 1) = 2; // arr[1] = 2

This will allocate consecutive memory locations for 5 integers. Normally you do not want to allocate random number of bytes, and that is why we use sizeof operator.

Calloc is kind of similar to malloc, but instead of one, it takes in two arguments. The first argument is the number of elements we want to allocate memory for and the second argument is the size of each element.

IMP: Calloc initializes the memory to zero while if we do not initialize the memory allocated by malloc, it will contain garbage values.

int no_of_elements = 5;
int *arr = (int *)calloc(no_of_elements, sizeof(int));

Realloc is used to resize the memory block. It takes in two arguments, the pointer to the memory block and the new size of the memory block. If the new size is greater than the old size, it will allocate new memory and copy the old memory to the new memory. If the new size is smaller than the old size, it will truncate the memory.

// Changing the size of the memory block from 100 to 1000
char *ptr;
ptr = malloc(100);
ptr = realloc(ptr,1000);

Example code: take a integer from the user and make an array of that size from 0.

int main() {
    // take in user input
    int n;
    printf("Enter the size of the array: ");
    scanf("%d", &n);
 
    // allocate memory for the array with calloc
    int *arr = (int *)calloc(n, sizeof(int));
    for (int i = 0; i < n; i++) {
        arr[i] = i;
    }
 
    // print the array
    for (int i = 0; i < n; i++) {
        // If we haven't already set the values in array, it would print 0
        // If we did this with malloc, it would print garbage values
        printf("%d ", arr[i]);
    }
 
    // free the memory
    free(arr);
 
    return 0
}

Memory Leaks

Memory leaks is a very common occurence with poorly managed dynamic memory allocation. It happens when the programmer forgets to free the memory allocated on the heap. This can lead to the program running out of memory and crashing. To avoid memory leaks, always free the memory after you are done with it.

If you have trouble finding memory leaks in your code, you can use tools like Valgrind to help you find them.

$ valgrind  --leak-check=full ./executable

Well these are the core concepts of memory management in C. These should be enough to get you started in DSA.