The article is a detailed introduction to Dynamic memory allocation; starting with pointers, it works its way up to the nub of memory handling. It carefully explains the working of pointers, arrays, and their applications.

Pointer Introduction

A pointer is a variable used to store the address of another variable. Pointers, like other variables, are allocated memory in the memory stack.

The syntax for declaring a pointer of a specific data type is as simple as,

<data_type> <*pointer_name>;

A statement of this syntax declares a pointer of <data_type> with the name,<pointer_name>.

As said before, the value stored in a pointer is the memory address of another variable. Before starting with a simple code, let's visualize a pointer,

Pointer p stores the memory address of the variable, a. De-referencing it using the asterisk(*), outputs a's value, 4.

#include <stdio.h>

int main(void)
{
    int a=1;

    int *p;
    p=&a;                                          //Store a's memory address in pointer p

    printf("Address of a is %d\n",p);              //Prints the address of a
    printf("Address of a is %d\n",&a);             //Prints the address of a
    printf("Address of pointer p is %d\n",&p);     //Prints the address of the pointer
    printf("a =  %d\n",*p);                        //Dereferencing a pointer

    //Modifying variable through pointer p
    *p = 7;
    printf("a = %d",*p);

    return 0;
}

Declaring and initializing a pointer can be simplified to,

int *p = &a; //or
int *p = a;

Pointer Arithmetic

The data type plays a crucial role in pointer arithmetic. However, the arithmetic operations are usually limited to increments and decrements. The table below is as per the 64-bit architecture.

Incrementing/decrementing a pointer is the same as moving forward/backward by the size allocated to a particular data type. For instance, incrementing an integer pointer by 1, adds 4 bytes to the memory address stored in the respective pointer.

//This program demonstrates pointer arithmetic
#include <stdio.h>

int main(void)
{
    int a = 10;     // if the address of a is 2008,
    int b = 5;      // address of b will be 2004, and    
    int c = 2;      // address of c will be 2000

    int *p;
    p = &a;

    //Pointer arithmetic
    printf("Address of a is: %d\n",&a);
    printf("Address of b is: %d\n",&b);
    printf("Address of c is: %d\n\n",&c);

    printf("Address of p is: %d\n",p);
    printf("Size of integer data types is: %d\n",sizeof(int));
    printf("Address of p-1 is: %d\n",p-1);                          //decrements by 4 bytes

    p--;
    printf("Deferenced pointer value is: %d",*p);                   //should print b's value

    return 0;
}

Datatype manipulation

When a pointer of a smaller data type points to a variable of a bigger data type, only a part of the bigger data type is pointed to. The case is best explained with an example,

#include <stdio.h>

int main(void)
{
    int a = 1025;

    int *p = &a;
    printf("Address of a is: %d\nValue of a is: %d\n",p,*p);

    char *p1 = (char*)p;    // Explicitly convert integer pointer to char pointer
    printf("Address of b is: %d\nValue of a is: %d\n",p1,*p1);      //Value is 1

    //Follows little-endian and binary representation of 1025 is  00000000 00000000 00000100 00000001

    p1 += 1;
    printf("Address of b is: %d\nValue of a is: %d\n",p1,*p1);      //Value is 4

    return 0;
}

De-referencing the pointer *p1 prints the value at address 2000, 1. (Addresses used are arbitrary).

Void pointers

Void pointers store the address of variables of any data type; there is no need for explicit typecasting when linking them with a variable. Arithmetic operations and de-referencing cannot be performed. Pointer arithmetic such as (p+1) is invalid.

//void pointers store the address of a variable of any data type. Arithmetic ops and de-referencing cannot be performed
//There is no need for explicit typecasting when linking them with a variable

#include <stdio.h>

int main(void)
{
    int a = 0;
    void *p = &a;

    printf("Address of a = %d\n",p); 
    printf("Value of a = %d\n",&a);

    //printf("Value of a = %d",*p);             De-referencing is not allowed
    //printf("PtrArithmetic of a = %d",(p+1));  Pointer arithmetic is invalid

    return 0;
}

Double pointers

Consider a case where a pointer is pointing to a variable. The first pointer stores the address of the variable. A second pointer to this is called a double-pointer. It shall store the value of the first pointer. The idea is extrapolated further by adding pointers in succession.

#include <stdio.h>

int main(void)
{
    int a = 5;
    int *p = &a;
    int **q = &p;
    int ***r = &q;

    printf("Address of a: %d\n",&a);
    printf("Value stored in pointer p: %d\n\n",p);

    printf("Address of pointer p: %d\n",&p);
    printf("Value stored in pointer q: %d\n",q);
    printf("Address of variable a de-referenced by q:%d\n\n",*q);

    printf("Address of pointer q: %d\n",&(q));
    printf("Value stored in pointer r: %d\n",r);
    printf("Address of pointer p de-referenced by r: %d\n\n",*r);

    return 0;
}

Sample Output:

De-referencing Double Pointers

De-referencing a double pointer is analogous to the normal pointer method. Yet, the use of asterisks could get tricky.

// demonstrates pointer to pointer de-referencing and data manipulation
#include <stdio.h>

int main(void)
{
    int a = 1;

    int *p = &a;
    int **q = &p;
    int ***r = &q;

    printf("\n*p = %d\n",*p);                      //1
    printf("*(*q) or **q = %d\n",**q);             //1
    printf("*(*(*r))) or ***r = %d\n",***r);       //1

    return 0;
}

Functions

When working with functions, the parameters are passed either by using, the

• Call by value method, or,
• Call by reference.

Call by reference is an efficient way of passing arguments to a function. It eliminates the need for parameter variables that are local to the function. The address of the variables to be passed is stored in a pointer, and these variables in the function call are directly accessed through the pointer.

#include <stdio.h>

int add(int*,int*);

int main(void)
{
    int a=1, b=2;

    printf("Sum of %d and %d =  %d\n",a,b,add(&a,&b));  //order of precedence in print statement assignments is from right to left

    return 0;
}

int add(int *a, int *b)
{
    *a += 1;
    return (*a+*b);
}

Arrays and Pointers

The relationship between arrays and pointers

An array is a basic data structure where the data is stored in contiguous memory locations. Array data types determine the space allocated for each member of the array.

//The program demonstrates the contiguous nature of an array

#include <stdio.h>

int main(void)
{
    int a[10];
    for(int i=0;i<10;i++)
        printf("Address of element a[%d] = %d\n",i,(a+i));
    return 0;
}

The elements of an array can be easily accessed by creating a pointer to the first element and subsequently incrementing it until we reach the last member.

#include <stdio.h>

int main(void)
{
    int a[] = {1,2,3,4,5};
    int *p = a;   //create a pointer to the first element of array, a 

    for(int i=0;i<5;i++)
        printf("a[%d] = %d\n",i,*(p+i));    //increment in steps of 1 to access the elements

    return 0;
}

Intrinsically, the name of the array is a constant pointer to the first element. Hence it's redundant to use another pointer to access the different elements. Bear in mind that the increments on the array pointer are invalid as it's a constant.

//increments on a are invalid because a is a constant pointer eg. a++
//however it can be assigned to another pointer as p and performed

#include <stdio.h>

int main(void)
{
    int a[] = {1,2,3,4,5};

    for(int i=0;i<5;i++)
    {
        printf("Address of a[%d] = %d\n",i,(a+i));
        printf("*a+%d or a[%d] = %d\n",i,i,*(a+i));
    }
    return 0;
}

Example programs

1. A program to add all the elements in an array

#include <stdio.h>

int sum(int*,int);

int main(void)
{
    int size;
    int a[20];

    printf("Enter the number of elements: ");
    scanf("%d",&size);

    printf("Enter the array elements: ");
    for(int i=0;i<size;i++)
        scanf("%d",a+i);

    printf("Sum of array elements: %d",sum(a,size));

    return 0;
}

int sum(int *a, int size)
{
    if(size==0)
        return 0;
    return (*a+sum(a+1,size-1));
}

1. A program to double all the elements of an array

#include <stdio.h>

void dbler(int*,int);

int main(void)
{
    int size;
    int a[20];

    printf("Enter the number of array elements: ");
    scanf("%d",&size);

    printf("Enter the array elements: ");

    for(int i=0;i<size;i++)
        scanf("%d",a+i);

    dbler(a,size);

    for(int i=0;i<size;i++)
        printf("a[%d] or *(a+%d) = %d\n",i,i,*(a+i));

    return 0;
}

void dbler(int *a, int size)
{
    if(size==0)
        return;
    *a *= 2;
    dbler(a+1,size-1);
}

Character Arrays

A character array is a sequence of characters stored in a contiguous memory location. However, when the array is not terminated, there are all kinds of unwanted characters that show up as we print the array, because of the garbage characters present in the un-initialized part of the array. A string is a character array, terminated by a null character(\0). In C we assume, that every string has a null character termination.

// In C, the string is a character array, with the assumption that it is terminated by a null character 

#include <stdio.h>
#include <string.h>

int main(void)
{
    char c[20];
    c[0] = 'S';
    c[1] = 'N';
    c[2] = 'E';
    c[3] = 'H';
    c[4] = 'A';
    c[5] = 'L';

    printf("The string is: %s\n",c);
    printf("String length: %d\n",strlen(c));

    c[6] = '\0';
    printf("The string is: %s\n",c);
    printf("String length: %d\n",strlen(c));

    return 0;
}

During the first print statement, the character array is not terminated by a null character. This caused a garbage character('@') after "SNEHAL", resolved on explicit termination(c[6] = '\0'). Bear in mind, that '\0' is ignored by the strlen function.

The following example shows character manipulation in a string using pointers.

 #include <stdio.h>

 int main(void)
 {
    char c[50] = "Snehal";        
    char *c1;

    c1=c;                           //c=c1 is invalid(remember is c1 is a character pointer)

    printf("Name: %s\n",c1);

    *(c+0) = 'A';
    *(c1+1) = 'B';

    printf("Name: %s\n",c1);

    return 0;
 }

Pointers and Multi-dimensional arrays

Before getting into the nitty-gritty of pointer usage in multi-dimensional arrays, let's have a look at the memory allocation and representation in 1D arrays.

Assuming an integer array as shown above, and a pointer, int *p = a

• Printing p will output the memory address 200
• *p de-references the memory address 200, hence outputting 2
• Dereferencing pointer arithmetic increments like (p+i) outputs the corresponding values, Eg.: (p+2) results in 6

2D array

Using pointers to refer to the elements of a 2D array is a little flummoxing to wrap your head around, yet ill try and break them down. Long story short, a 2D array is an array where each element is in itself another array. Memory addressing of an array, int a[2][3] is visualized in the above attachment.

The name of the array, 'a' returns a pointer to a one-dimensional integer array. As a result, using a pointer such as an int p = a is incorrect and will lead to a compilation error. The correct use case of declaring a pointer for the above array will be, ```int (p)[3]```

• a[0] returns a pointer to the first element of the 1D array, 400.
• a will return the address of the first element of the 1D array, 400.
• a+1 results in 412.
• ```*(a+1) results in 412, however here we start accessing the elements of the 1D array.
• (*a+1) outputs 404(Memory address of a[0][1]), an integer pointer to the elements of the 1D array.
• De-referencing the integer pointers of the 1D array, eg.: (a+1), gives us the value at the memory address, 404, which is, 2.

As a rule of thumb, the following scenarios can be simplified as, a[i][j] = ((&a[i])+j) or a[i][j] = ((a+i)+j)

Example Program

#include <stdio.h>

int main(void)
{
    int a[2][3] = {{1,2,3},{4,5,6}};

    for(int i=0;i<2;i++)
    {
        for(int j=0;j<3;j++)
        {
            printf("&a[%d][%d] or (*(a+%d)+%d) = %d\n",i,j,i,j,(*(a+i)+j));     //Element addresses
            printf("a[%d][%d] or *(*(a+%d)+%d) = %d\n",i,j,i,j,*(*(a+i)+j));    //Elements
        }
    }

    return 0;
}

3D array

The 3D array is an extrapolation of 2D arrays. It is a collection of 2D arrays, wrapped around an external array.

The following diagram represents the memory representation of a 3D array.

• Using the name of the array alone, returns the memory addresses of a[0], a[1], and a[2]. Hence, the resultant of a, a+1, and a+2 is 800, 816, and 832 respectively.
• De-referencing the memory addresses returns the pointer(int *[]) to the internal array, which is a[0][0], a[1][0] and a[2][0].
• Further de-referencing provides an integer pointer(int *) to the final layer of the array and hence outputs the memory address of a[0][0][0], a[1][0][0] and a[2][0][0].
• Another final de-reference prints out the elements.

Program demonstrating the array access

#include <stdio.h>

int main(void)
{
    int a[3][2][2] = {{{1,2},{3,4}},{{5,6},{7,8}},{{9,10},{11,12}}};

    for(int i=0;i<3;i++)
    {
        printf("%d\n",(a+i));                                    //address of a[0], a[1] and a[2]
        for(int j=0;j<2;j++)
        {
            printf("%d\n",(*(a+i)+j));                           //address of a[0][0], a[1][0] and a[2][0]
            for(int k=0;k<2;k++)
            {
                printf("%d\n",*(*(a+i)+j)+k);                    //address of all elements
                printf("Element: %d\n",*(*(*(a+i)+j)+k));        //Print the elements
            }
        }
    }

    return 0;
}

All the results are compiled to obtain a general expression, *(*(*(a+i)+j)+k) for element access in a 3D array.

Passing Arrays to a Function

• 1D array: The name of the array returns an integer pointer to the first element. Eg.: The return type of an int a[5] is int*

#include <stdio.h>

void print(int *a)
{
    for(int i=0;i<3;i++)
        printf("a[%d] = %d\n",i,*(a+i));
}

int main(void)
{
    int a[3] = {1,2,3};
    print(a);
    return 0;
}

• 2D array: The name of the array returns a pointer to an array of integers. Eg.: The return type of int a[5][5] is int (*a)[5] which is analogous to int a[][5]

#include <stdio.h>
void print(int (*)[3]);

void print(int (*a)[3]) //An array of three pointers
{
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
            printf("a[%d][%d] = %d\n",i,j,*(*(a+i)+j));
    }
}

int main(void)
{
    int a[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
    print(a);
    return 0;
}

• 3D array: The name of the array returns a pointer to a 2D array. Eg: The return type of int a[5][2][3] is int (*a)[2][3] which is analogous to int a[][2][3]

#include <stdio.h>
void print(int (*)[2][3]);

void print(int (*a)[2][3])
{
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<2;j++)
        {
            for(int k=0;k<3;k++)
                printf("a[%d][%d][%d] = %d\n",i,j,k,*(*(*(a+i)+j)+k));
        }
    }
}

int main(void)
{
    int a[3][2][3]  = {{{1,2,3},{4,5,6}},{{7,8,9},{10,11,12}},{{13,14,15},{16,17,18}}};
    print(a);
    return 0;
}

Memory in C

Every program post compilation is allocated memory in a bifurcated memory system with each segment having its own intent and use.

A memory stack is also called a function call stack. It stacks function calls and local variables one above the other. Once a method finishes its execution, the method call is flushed out. The data allocated for the memory stack is fixed and exceeding it causes a stack overflow. A classic example of stack overflow is when recursion occurs without termination. The amount of space allocated for a particular function in the stack memory is called the stack frame.

#include <stdio.h>

int a = 5;

int sum(int b)
{
    return (a+5);
}

int main(void)
{
    sum(5);
    printf("Sum = %d",a);

    return 0;
}

Memory representation before stack de-allocation(Function call pop). The function information, such as the function name, local variables, and the return location are all stored in their respective stack frames.

Heaps and Introduction to Dynamic Memory Allocation

A heap is utilized for runtime memory allocation. The size of a heap is not fixed and can vary during program execution. The memory and lifetime of variables in the heap are determined by the user. A heap is also called dynamic memory and employing it in a program is called, dynamic memory allocation . Stack is an implementation of the stack data structure, yet heap and the heap data structure are two different entities.

In C the heap memory can be accessed using the following functions,

• malloc
• calloc
• realloc
• free

Dynamic Memory allocation using malloc(Basic variable)

malloc is used to allocate a block of memory in the heap. It returns a void pointer, pointing to the memory segment in the heap. Type-cast the pointer returned based on how the allocated memory is deployed. Dynamically allocated memory should be cleared explicitly using the function free(<pointer>). If the memory allocation fails, a null character is returned.

Example Program :

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int *p;

    p = (int*)malloc(sizeof(int));  //allocate a memory block in the size of int data type
    *p = 10;

    printf("Address of the memory block: %d\n",p);
    printf("Integer = %d\n",*p);
    free(p);      //de-allocate the heap

    return 0;
}

Dynamic Memory allocation using malloc(Arrays)

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int *p = (int*)malloc(5*sizeof(int));         //sizeof(int)*5 for an array of 5 elements
    printf("Address pointed to by p: %d\n",p);

    printf("Enter 5 array values: ");

    for(int i=0;i<5;i++)
        scanf("%d",(p+i));

    printf("\nThe entered array values are: \n");

    for(int i=0;i<5;i++)
        printf("%d\n",*(p+i));  

    free(p);

    return 0;
}

malloc, calloc, realloc and free

Function Signatures

• malloc : void* malloc(size_t size)
• calloc : void* calloc(size_t units, size_t size): It accepts two arguments, where num corresponds the number of units of required size. Also, calloc initializes the memory allocated to 0.
• realloc: void* realloc(void* ptr, size_t size): The function is used to re-allocate memory. It accepts as input, a void pointer pointing to a memory block and re-allocates as per the size. In cases where re-allocation is not possible, the entire block is copied to an extended memory block.

Note: size_t: unsigned int

Dynamic memory allocation using calloc(Arrays)

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int n;

    printf("Enter the size of the required array: ");
    scanf("%d",&n);

    int *a = (int*)calloc(n,sizeof(int));

    printf("Enter %d integer values: ",n);
    for(int i=0;i<n;i++)
        scanf("%d",(a+i));

    printf("\n");

    for(int i=0;i<n;i++)
        printf("a[%d] = %d\n",i,*(a+i));

    free(a);
    return 0;
}

Dynamic memory extension with realloc(Arrays)

realloc is used to extend an allocated memory block. Dynamic extension happens if there is adequate space following the allocated block, else the entire memory block is copied to a new location, and the previously designated block is de-allocated.

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int n = 5;
    int *a = (int*)calloc(n,sizeof(int));

    printf("Enter 5 elements: ");

    for(int i=0;i<5;i++)
        scanf("%d", (a+i));

    printf("\n");
    printf("Memory Extension\n");

    int *b = (int*)realloc(a,(2*n));

    printf("Memory address of previously allocated block: %x\n",a);
    printf("Memory address of the new block: %x\n",b);

    printf("Enter 5 more elements: ");
    for(int i=5;i<10;i++)
        scanf("%d",(a+i));

    printf("The elements are: \n");
    for(int i=0;i<10;i++)
        printf("%d\n",*(a+i));

    free(a);
    free(b);  

    return 0;
}

Tid-bits :

• int *b = (int*)realloc(a,0); is equivalent to free(a)
• int *b = (int*)realloc(NULL, n*sizeof(int)) is a nuance of the malloc function

Function Pointers in C

Function pointers are used to store the addresses of functions which in turn can be de-referenced to execute.

Address of a function

A program, written in C is converted to machine code by the compiler. This executable file is stored in the Code area of memory. The instructions are stored and executed sequentially(unless there is an explicit jump mentioned by an instruction) in the Code region of the memory. The address pointer points to the entry point of the function.

Syntax to declare a function pointer

int (*<Pointer_name>)(<Function arg types>)
<Pointer_name> = &<Function_name>;             //or <Pointer_name> = <Function_name>

Example Program

//This program prints the elements of an array plying function pointers

#include <stdio.h>

void print(int *a)
{
    for(int i=0;i<3;i++)
        printf("a[%d] = %d\n",i,*(a+i));
}

int main(void)
{
    int a[3] = {1,2,3};
    void (*p)(int*);

    p = print;
    (*p)(a);

    return 0;
}

Function Pointers and callbacks

Name of a function returns a pointer to the function. A callback function is a function passed to another function, which gets invoked inside the outer function block.

A definitive example is a sorting algorithm when the user wants to decide on the ascending or descending order. The code violates DRY(Don't Repeat Yourself) if two separate functions are written for each operation. Instead, only altering the condition check reduces code density. Here's one case where callback functions come in handy.

#include <stdio.h>
#include <stdlib.h>

//Function declaration
int check(int, int, int);
void bubblesort(int*, int, int (*)(int, int));

//callback function
int check(int a, int b, int ch)
{
    if(ch==0)
    {
        printf("Invalid entry!\n");
        exit(-1);
    }
    else if(a>b)
        return (1*ch);
    else    
        return (-1*ch);
}

void bubblesort(int *a, int n, int (*check)(int, int, int))
{
    int ch;

    printf("Do you want the array sorted in the 1) Ascending or 2) Descending order?\n");
    scanf("%d",&ch);

    printf("\n");

    ch = (ch==1)?1:((ch==2)?-1:0);

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<(n-i-1);j++)
        {
            if((*check)(*(a+j),*(a+j+1),ch)>0)  //if((check)(*(a+j),*(a+j+1),ch)>0) 
            {
                *(a+j) += *(a+j+1);
                *(a+j+1) = *(a+j)-*(a+j+1);
                *(a+j) -=*(a+j+1);
            }
        }
    }
}

int main(void)
{
    int n;

    printf("Enter the number of elements: ");
    scanf("%d",&n);

    int *a = (int*)calloc(n,sizeof(int));           //allocate memory for an array of size n

    printf("Enter the array elements: ");
    for(int i=0;i<n;i++)
        scanf("%d",(a+i));

    bubblesort(a,n,&check);                         //bubblesort(a,n,check)

    for(int i=0;i<n;i++)
        printf("%d\n",*(a+i));

    return 0;
}

Memory Leak

A memory leak occurs when the space allocated on the heap memory is not freed. The comeuppance is reduced performance of the computer. It is caused due to improper use of dynamic memory, increasing the memory consumption of a program. Memory on the stack is de-allocated automatically unlike the heap.

References

1. https://www.youtube.com/watch?v=zuegQmMdy8M&t=10932s
2. https://www.tutorialspoint.com/cprogramming/c_pointer_arithmetic.htm
3. https://www.programiz.com/c-programming/c-pointers-arrays
4. https://www.geeksforgeeks.org/stack-vs-heap-memory-allocation/