Single dynamic allocation for multi-dimensional array

Question

The basic question is:

For code that expects a pointer to pointer that will be syntactically indexed like a 2-dimensional array, is there a valid way to create such an array using a single allocation?^†

While on the surface, it seems I am asking for how to do so (like in this question), I already understand how it could be done (see below). The problem is that there might be an alignment issue.^&ddagger;

The rest of the text describes some alternatives, and then explains the method under question.

_{† Olaf points out a pointer to pointer is not a 2-dimensional array. The premise of the question is that 3rd party code expects a pointer to pointer passed in, and the 3rd party code will index it as a 2-dimensional array.}

_{&ddagger; ErikNyquist presented a possible duplicate which explains how one might perform such an allocation, but I am questioning the validity of the technique with regards to alignment of the data.}

If I need to dynamically allocate a multi-dimensional array, I typically use a single allocation call to avoid an iteration when I want to free the array later.

If VLA is available, I might code it like this:

int n, m;
n = initialize_n();
m = initialize_m();
double (*array)[m] = malloc(n * sizeof(*array));

array[i][j] = x;

Without VLA, I either rely on a macro on a structure for array accesses, or I add space for the pointer table for code that expects the ** style of two-dimensional array. The macro approach would look like:

struct array_2d {
    int n, m;
    double data[];
};

// a2d is a struct array_2d *
#define GET_2D(a2d, i, j) (a2d)->data[(i) * x->n + (j)]

struct array_2d *array = malloc(sizeof(*array) + n * m * sizeof(double));
array->n = n;
array->m = m;

GET_2D(array, i, j) = x;

The pointer table method is more complicated, because it requires a loop to initialize the table.

struct array_p2d {
    int n, m;
    double *data[];
};

#define GET_P2D(a2d, i, j) (a2d)->data[i][j]

struct array_p2d *array = malloc(sizeof(*array) + n * sizeof(double *)
                                 + n * m * sizeof(double));
for (k = 0; k < n; ++k) {
    array->data[k] = (double *)&array->data[n] + k * m;
}

GET_P2D(array, i, j) = x;
// array->data can also be passed to a function wanting a double **

The problem with the pointer table method is that there might be an alignment issue. As long as whatever type the array is of does not have stricter alignment requirements than a pointer, the code should work.

Is the above expected to always work? If not, is there a valid way to achieve a single allocation for a pointer to pointer style 2-dimensional array?

Something like `int **` is not and cannot be a 2D array (the same for higher dimensions). It can also not point to one. So your question is pointless. Use a modern C compiler and you will have VLAs. Don't try riding a dead horse, it can only result in frustration - at best. — too honest for this site, Jul 28 '16 at 03:53
Looks like an answer to the same question is here http://stackoverflow.com/questions/8740195/how-do-we-allocate-a-2-d-array-using-one-malloc-statement — Erik Nyquist, Jul 28 '16 at 04:11
@ErikNyquist My question is about alignment of the array items that follows the pointer table. — jxh, Jul 28 '16 at 06:47
@Olaf: VLA was required in C.99, but became optional in C.11. Clearly, I am not talking about a strictly defined C array with 2 dimensions, but a pointer that can be indexed as if it were 2 dimensional. — jxh, Jul 28 '16 at 09:43
@jxh: I did not say to use a C11, but a **modern** C compiler for good reasons. It was the worst decision of the commitee to make a mandatory (and very useful) feature optional. That was absolutely against the common practice of the commitee which even still allows to omit function declarations (they have to generate a warning, but it is no error) or still allow aliasing through `char *` - although `void *`, etc. That has the haut-gout of bad influence by a certain compiler vendor which still can't provide a compliant compiler after >17 years. — too honest for this site, Jul 28 '16 at 12:43
A jagged array cannot be indexed "as if it were 2D". It only has the same syntax, but completely different semantics. That **e.g.** can have massive impact on performance and system behaviour. — too honest for this site, Jul 28 '16 at 12:47
@jxh err no, your question is, and I quote "is there a valid way to achieve a single allocation for a pointer to pointer style 2-dimensional array?". If you actual question is different then consider updating your post. — Erik Nyquist, Jul 28 '16 at 17:36
@ErikNyquist: The distinction is made in the 'DR' part of 'TL;DR'. But, I can rearrange some text. — jxh, Jul 28 '16 at 17:46
@Olaf You are preaching to the choir with respect to VLA support. See http://programmers.stackexchange.com/q/314838/81818 — jxh, Jul 28 '16 at 21:11
@jxh: Thanks for the link. We'll never know tht trueth. But fact is one major reason MSVC is not C99 compliant (and never will be) is they don't implement VLAs or other features not support by C++ (IIRC, there even is such a statement). I think that is the main reason behind not implementing these features. Restrictions on embedded, etc are just fake arguments, because on systems the **potential** overhead is relevant have other issues, resp. don't fully support C anyway (e.g. floating point, which is **not** optional but much more often unnecessary). — too honest for this site, Jul 28 '16 at 21:40
As an embedded systems developer, I'd rather see `float` etc. optional than VLAs. IMO this is a business-driven decission, no way technically. — too honest for this site, Jul 28 '16 at 21:42

score 1 · Accepted Answer · answered Jul 28 '16 at 18:24

Well, your malloc allocation is guaranteed to be aligned (unless you're using a non-standard alignment), so all you need to do is to round up the pointer table size to the alignment of the data segment:

const size_t pointer_table_size = n * sizeof(double *);
const size_t data_segment_offset = pointer_table_size +
    ((_Alignof(double) - (pointer_table_size / _Alignof(double))) % _Alignof(double));
double **array = malloc(data_segment_offset + (n * m * sizeof(double));
double *data = (double **)(((char **) array) + data_segment_offset);
for (int i = 0; i != n; ++i)
    array[i] = data + (m * i);

Single dynamic allocation for multi-dimensional array

1 Answers1