Dynamic multidimensional array on the heap

Question

I want to create a function which can allocate a multidimensional array on the heap with only one call to malloc. (Pointer array) So a function call would look like this:

size_t dim[2]  = {2, 4};
int **_2darray = alloc_array(sizeof(int), dim, 2);
// ^ should be the "same" as:
int __2darray[2][4];

What I have so far is the SIZE computation of the whole block needed to hold the array and the pointers:

void *alloc_array(size_t element_size, size_t dimensions[static 1], size_t ndims)
{
    unsigned char *DATA = NULL;
    size_t SIZE         = 0;
    size_t multiplicators[ndims];

    // Calculate for each dimension the multiplier 
    // SIZE 3d array:  (N1 * sizeof(T **) + (N1 * N2 + sizeof(T *) + (N1 * N2 * n3 + sizeof(T))
    //                  ^- first mulitplier ^ second multiplier      ^ third multiplier

    for (size_t i = 0;  i < ndims; ++i) {
        multiplicators[i] = dimensions[i];

        for (size_t j = 0; j < i; ++j) {
            multiplicators[i] *= dimensions[j];
        }
    }

    SIZE = 0;
    for (size_t dimI = 0; dimI < ndims; ++dimI) {
        size_t mulval = multiplicators[dimI];

        // The elements are in the "last" dimension
        if (dimI+1 == ndims) {
            SIZE += element_size * mulval;
        } else {
            // All other elements are pointers to the specific element
            SIZE += sizeof(void *) * mulval;
        }
    }

    DATA = malloc(SIZE);
    return DATA;
}

So by now the SIZE calculation works. But now I'm stuck with setting the pointers to the right element. I know it's easy with dealing with static dimensions but I want this to be done with dynamic dimensions.

I don't get it. Why not just malloc(sizeof(T) * dim1 * dim2) and be done with it? Then index by computed offset like (row + col*nrows). — John Zwinck
I want it to be dynamic, so that it works for any dimension. 2d,3d,4d..5d arrays.. I think you get the point. — marco-a
No I don't. Of course you should multiply sizeof(T) by all the dimensions. That's a trivial "for" loop. But your code is more complicated because you are dealing with pointers which I don't think you need to use. If you malloc(sizeof(T) * dim1 * dim2 * dim3) then you index as (idx1 + idx2 * dim1 + idx3 * dim1 * dim2) or similar. — John Zwinck
When I started thinking through a generic nDimension space model, my head exploded... Each new dimension adds several additional layers of offset. Coding functions for 2D is doable, but tedious. Implementing a generic set would be a doctoral thesis. — David C. Rankin

n. 1.8e9-where's-my-share m. n. 1.8e9-where's-my-share m. · Accepted Answer · 2014-09-27T14:56:46

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

void fill_array_pointers (void** pointers, char* elements, 
                  size_t element_size, size_t total_elements_size, 
                  size_t dimensions[], size_t ndims)
{
    if (ndims == 2)
    {
        size_t i;
        for (i = 0; i < dimensions[0]; ++i)
        {
            pointers[i] = elements + i * element_size * dimensions[1];
        }
    }
    else
    {
        size_t i;
        size_t block_size = total_elements_size / dimensions[0];
        for (i = 0; i < dimensions[0]; ++i)
        {
            pointers[i] = pointers + dimensions[0] + i * dimensions[1];
            fill_array_pointers (pointers + dimensions[0] 
                                          + i * dimensions[1], 
                                  elements + block_size * i, 
                                  element_size, block_size, 
                                  dimensions+1, ndims-1);
        }
    }
}

void* alloc_array (size_t element_size, size_t dimensions[], 
                    size_t ndims)
{
    size_t total_elements_size = element_size;
    int i;

    // total size of elements

    for (i = 0; i < ndims; ++i)
        total_elements_size *= dimensions[i];

    // total size of pointers

    size_t total_pointers_size = 0;
    int mulval = 1;
    for (i = 0; i < ndims-1; ++i)
    {
        total_pointers_size += dimensions[i] * sizeof(void*) * mulval;
        mulval *= dimensions[i];
    }

    size_t total_size = total_pointers_size;
    size_t oddball = total_pointers_size % element_size; 
                // really needs to be alignof but we don't have it
    if (oddball) total_size += (element_size - oddball);
    total_size += total_elements_size;

    void* block = malloc (total_size);
    void** pointers = block;
    char* elements = (char*)block + total_size - total_elements_size;

    fill_array_pointers (pointers, elements, element_size,
                         total_elements_size, dimensions, ndims);
    return block;
}

Test drive:

int main ()
{
    size_t dims[] = { 2, 3, 4 };
    int*** arr = alloc_array(sizeof(int), dims, 3);


    int i, j, k;
    for (i = 0; i < dims[0]; ++i)
        for (j = 0; j < dims[1]; ++j)
            for (k = 0; k < dims[2]; ++k)
            {
                arr[i][j][k] = i*100+j*10+k;
            }

    for (i = 0; i < dims[0]*dims[1]*dims[2]; ++i)
    {
        printf ("%03d ", (&arr[0][0][0])[i]);
    }
    printf ("\n");

    free (arr);
}

This will not work for multidimensional char arrays on systems where sizeof(char*) != sizeof(char**); such systems exist but are rare. Multidimensional char arrays are pointless anyway.

The test runs cleanly under valgrind.

This is more an intellectual exercise than anything else. If you need maximum performance, don't use arrays of pointers, use a flat array and ugly but efficient explicit index calculations. If you need clear and concise code, you are probably better off allocating each level separately.

Dynamic multidimensional array on the heap

1 Answers