how malloc() can be used to create a dynamic array if it allocates only one block of memory which can be stored for only one variable?

Question

malloc() function creates a whole block of memory and then return the pointer of the first byte. If it creates only one block of memory, then it can only store only one element right? But how malloc() stores multiple elements in only one block of memory whereas it makes sense when calloc() creates multiple blocks of memory and it can be used as an dynamic array.

Answer 1

This is bread and butter allocated memory management. It works the same way no matter what type of data you are allocating/reallocating for. The three standard functions provided for dynamic memory allocation are malloc/calloc/realloc. While malloc/calloc are limited to allocating a single block of memory, realloc can also resize a block of memory allowing you to allocate some initial block of storage with malloc/calloc (or you can do it with realloc) and then use realloc to increase or decrease the amount of memory allocated.

As with every function call where you allocate memory, you must validate the call succeeds by checking that the return is not NULL. This is why when using realloc you always realloc with a temporary pointer!. So when (not if) realloc fails because you have run out of memory, you do not overwrite your original pointer with NULL losing the address for the block of memory and creating a memory leak.

For example if you have allocated for int *block = malloc (...), you do NOT realloc as:

block = realloc (block, 2 * n * sizeof *block);    /* to double size */

If realloc fails -- what is returned, and what does block now hold? (hint: NULL). So instead, you use a temporary pointer, e.g.

/* always realloc to a temp pointer, or risk losing pointer */
void *tmp = realloc (block, 2 * n * sizeof *block);   /* doubling size */
if (!tmp) {         /* validate every allocation */
    perror ("realloc-block");
    /* handle error - original pointer still good */
}
block = tmp;        /* assign reallocated block */

(note: the use of void *tmp is done because that is the return type for realloc. It could just a validly be int *tmp to match the type for block. The key is your temporary pointer tmp must be type compatible with block for the assignment of the reallocated block, e.g. block = tmp;. For new C programmers, in C any pointer can be cast to/from void* without an explicit cast. So void *tmp is just a generic temporary type to use, but the type for block would be every bit as correct there)

That way you do not assign the reallocated block until you have validated the call to realloc succeeded. You can increase by any number you like. Doubling is fine, or just adding some fixed number is fine, etc..

The scheme to handle reallocating anything is straight-forward. You allocate a block to hold some number of objects. You keep a counter of the number allocated (say alloced). Then you keep a separate counter of the number of objects used (say used). Then before using the memory for another object if filling in a loop, etc. you simply check if used == alloced, e.g.:

if (used == alloced) {          /* check if realloc needed */
    /* realloc here */
    alloced *= 2;               /* update no. allocated (doubling size here) */
}

You reallocate and then update your alloced counter to the new size, and keep on going...

A short example initially allocating for 2 integers and then reallocating as needed by doubling the current allocation size to read and store and unlimited number of integers is a basic example. As mentioned above, you can increase the allocation size by whatever you like, but avoid reallocating for every addition. Memory allocation is a relatively expensive call. So doubling, e.g. growing the allocation from storage for 2 to storage for 4, 8, 16, 32, 64, 128, ... is a reasonable growth rate that avoids repeated unnecessary reallocation as objects are added.

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

#define MAXI 2                  /* initial number of integer to allocate */

int main (void) {

    size_t  alloced = MAXI,     /* counter to track number allocate */
            used = 0;           /* counter to track number used */
    int val = 0,                /* value to read from stdin */
        *block = malloc (alloced * sizeof *block);  /* initial allocation */

    if (!block) {   /* validate every allocation */
        perror ("malloc-block");
        return 1;
    }

    while (scanf ("%d", &val) == 1) {   /* while integer read */
        if (used == alloced) {          /* check if realloc needed */
            /* always realloc to a temp pointer, or risk losing pointer */
            void *tmp = realloc (block, 2 * alloced * sizeof *block);
            if (!tmp) {         /* validate every allocation */
                perror ("realloc-block");
                if (!used)      /* if no ints stored, exit */
                    return 1;
                break;          /* otherwise original pointer still good */
            }
            block = tmp;        /* assign reallocated block */
            alloced *= 2;       /* update no. of ints allocated */
        }
        block[used++] = val;    /* add value to block and update used */
    }

    printf ("no. of bytes allocated : %zu\n"
            "no. of bytes used      : %zu\n"
            "no. of ints stored     : %zu\n",
            alloced * sizeof *block, used * sizeof *block , used);

    free (block);   /* don't forget to free what you allocate */
}

Example Use/Output

We initially allocated for 2-int, so lets try reading 100000 and see how it goes...

$ ./bin/malloc_realloc < ../dat/100000int.txt
no. of bytes allocated : 524288
no. of bytes used      : 400000
no. of ints stored     : 100000

So you can see we have over-allocated on our last realloc by 124288-bytes. Not bad, but since you know the number of ints used, you can realloc a final time to size the block to hold exactly 100000-int by:

void *tmp = realloc (block, used * sizeof *block);
...

(that is left to you to experiment with -- but you cannot realloc to a size less than the number of stored values)

Memory Use/Error Check

In any code you write that dynamically allocates memory, you have 2 responsibilities regarding any block of memory allocated: (1) always preserve a pointer to the starting address for the block of memory so, (2) it can be freed when it is no longer needed.

It is imperative that you use a memory error checking program to insure you do not attempt to access memory or write beyond/outside the bounds of your allocated block, attempt to read or base a conditional jump on an uninitialized value, and finally, to confirm that you free all the memory you have allocated.

For Linux valgrind is the normal choice. There are similar memory checkers for every platform. They are all simple to use, just run your program through it.

$ valgrind ./bin/malloc_realloc < ../dat/100000int.txt
==28169== Memcheck, a memory error detector
==28169== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==28169== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==28169== Command: ./bin/malloc_realloc
==28169==
no. of bytes allocated : 524288
no. of bytes used      : 400000
no. of ints stored     : 100000
==28169==
==28169== HEAP SUMMARY:
==28169==     in use at exit: 0 bytes in 0 blocks
==28169==   total heap usage: 17 allocs, 17 frees, 1,048,568 bytes allocated
==28169==
==28169== All heap blocks were freed -- no leaks are possible
==28169==
==28169== For counts of detected and suppressed errors, rerun with: -v
==28169== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

(note: the 1,048,568 bytes allocated above is the sum of 2 * sizeof(int), 4 * sizeof(int), ....)

Always confirm that you have freed all memory you have allocated and that there are no memory errors.

Look things over and let me know if you have further questions.

If you want to check the total allocation adds up, you can do that from your shell (presuming POSIX shell) with a for loop and the POSIX mathematics operator, e.g.

sum=0; for i in $(seq 1 17); do sum=$((sum + (1 << i) * 4)); done; echo $sum
1048568

Answer 2

Yes it takes only one block but this one block can be divide in an infinite block too depending on the required size you're asking for.

Answer 3

The way I understand it, malloc() allocates one block of memory, but it is guaranteed to be contiguous. And an array is just a pointer to the first element of contiguous memory (it is up to the programmer to keep track of the size of the array). Note that this is the same thing as the output of malloc(). The one block of memory can contain as many elements as you want, just as long as you created a big enough block for the desired number of elements. calloc() does exactly the same thing, but initializes the block to all zeros, so that makes it a little more convenient for initializing an array.