Dynamically allocate contiguous memory for a "rectangular 2d array", without using VLAs-CodePudding

This is one of those questions where there are so many answers, and yet none do the specific thing.

I tried to look at all of these posts — 1 2 3 4 5 6 7 8 9 — and every time the solution would be either using VLAs, using normal arrays with fixed dimensions, or using pointer to pointer.

What I want is to allocate:

dynamically (using a variable set at runtime)
rectangular ("2d array") (I don't need a jagged one. And I guess it would be impossible to do it anyway.)
contiguous memory (in #8 and some other posts, people say that pointer to pointer is bad because of heap stuff and fragmentation)
no VLAs (I heard they are the devil and to always avoid them and not to talk to people who suggest using them in any scenario).

So please, if there is a post I skipped, or didn't read thoroughly enough, that fulfils these requirements, point me to it. Otherwise, I would ask of you to educate me about this and tell me if this is possible, and if so, how to do it.

CodePudding user response：

Suppose you need a 2D array of size W x H containing ints (where H is the number of rows, and W the number of columns).
Then you can do the the following:

Allocation:

int * a = malloc(W * H * sizeof(int));

Access element at location (i,j):

int val = a[j * W   i];
a[j * W   i] = val;

The whole array would occuply a continous block of memory, and can be dynamically allocated (without VLAs). Being a continous block of memory offers an advantage over an array of pointers due to [potentially] less cache misses.

In such an array the term "stride" refers to the offset between one row to another. If you need to use padding e.g. to make sure all lines start at some aligned address, you can use a stride which is bigger than W.

CodePudding user response：

You can dynamically allocate a contiguous 2D array as

int (*arr)[cols] = malloc( rows * sizeof (int [cols]) );

and then access elements as arr[i][j].

If your compiler doesn’t support VLAs, then cols will have to be a constant expression.

CodePudding user response：

Often an array of pointers is allocated and then memory is allocated to each pointer.
This could be inverted. Allocate a large contiguous block of memory. Allocate an array of pointers and assign addresses from within the contiguous block.

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

int **contiguous ( int rows, int cols, int **memory, int **pointers) {
    int *temp = NULL;
    int **ptrtemp = NULL;
    // allocate a large block of memory
    if ( NULL == ( temp = realloc ( *memory, sizeof **memory * rows * cols))) {
        fprintf ( stderr, "problem memory malloc\n");
        return pointers;
    }

    *memory = temp;
    // allocate pointers
    if ( NULL == ( ptrtemp = realloc ( pointers, sizeof *pointers * rows))) {
        fprintf ( stderr, "problem memory malloc\n");
        return pointers;
    }

    pointers = ptrtemp;

    for ( int rw = 0; rw < rows;   rw) {
        pointers[rw] = &(*memory)[rw * cols]; // assign addresses to pointers
    }

    // assign some values
    for ( int rw = 0; rw < rows;   rw) {
        for ( int cl = 0; cl < cols;   cl) {
            pointers[rw][cl] = rw * cols   cl;
        }
    }
    return pointers;
}

int main ( void) {
    int *memory = NULL;
    int **ptrs = NULL;
    int rows = 20;
    int cols = 17;

    if ( ( ptrs = contiguous ( rows, cols, &memory, ptrs))) {
        for ( int rw = 0; rw < rows;   rw) {
            for ( int cl = 0; cl < cols;   cl) {
                printf ( "= ", ptrs[rw][cl]);
            }
            printf ( "\n");
        }

        free ( memory);
        free ( ptrs);
    }
    return 0;
}