How do I write functions which accept two-dimensional arrays when the width is not known at compile time?

Question

Is it possible to write a function which accept 2-d array when the width is not known at compile time?

A detailed description will be greatly appreciated.

Answer 1

You can't pass a raw two-dimensional array because the routine won't know how to index a particular element. The 2D array is really one contiguous memory segment.

When you write x[a][b] (when x is a 2d array), the compiler knows to look at the address (x + a * width + b). It can't know how to address the particular element if you don't tell it the width.

As an example, check http://www.dfstermole.net/OAC/harray2.html#offset (which has a table showing how to find the linear index for each element in an int[5][4])

There are two ways to work around the limitation:

1) Make your program work with pointer-to-pointers (char *). This is not the same as char[][]. A char * is really one memory segment, with each value being a memory address to another memory segment.

2) Pass a 1d pointer, and do the referencing yourself. Your function would then have to take a "width" parameter, and you could use the aforementioned formula to reference a particular point

To give a code example:

#include <stdio.h>
int get2(int *x) { return x[2]; }
int main() {
    int y[2][2] = {{11,12},{21,22}};
    printf("%d\n", get2((int *)y));
}

This should print out 21, since y is laid out as { 11, 12, 21, 22 } in memory.

Answer 2

C supports variable-length arrays. You must specify the width from a value known at run-time, which may be an earlier parameter in the function declaration:

void foo(size_t width, int array[][width]);

Answer 3

One way is use the good old "pointer to array of pointers to arrays" trick coupled with a single continuous allocation:

/* Another allocation function
   --------------------------- */
double ** AnotherAlloc2DTable(
 size_t size1, /*[in] Nb of lines */
 size_t size2  /*[in] Nb of values per line */
 )
{
    double ** ppValues;
    size_t const size1x2 = size1*size2;
    if(size1x2 / size2 != size1)
        return NULL; /*size overflow*/

    ppValues = malloc(sizeof(*ppValues)*size1);
    if(ppValues != NULL)
    {
        double * pValues = malloc(sizeof(*pValues)*size1x2);
        if(pValues != NULL)
        {
            size_t i;
            /* Assign all pointers */
            for(i=0 ; i<size1 ; ++i)
                ppValues[i] = pValues + (i*size2);
        }
        else
        {
            /* Second allocation failed, free the first one */
            free(ppValues), ppValues=NULL;
        }
    }/*if*/
    return ppValues;
}

/* Another destruction function
   ---------------------------- */
void AnotherFree2DTable(double **ppValues)
{
    if(ppValues != NULL)
    {
        free(ppValues[0]);
        free(ppValues);
    }
}

Then all you have to do is pass a char ** to your function. The matrix is continuous, and usable as mat[x][y].

Answer 4

Possible accessor functions:

int get_multi(int rows, int cols, int matrix[][cols], int i, int j)
{
    return matrix[i][j];
}

int get_flat(int rows, int cols, int matrix[], int i, int j)
{
    return matrix[i * cols + j];
}

int get_ptr(int rows, int cols, int *matrix[], int i, int j)
{
    return matrix[i][j];
}

An actual multi-dimensional array and a fake one:

int m_multi[5][7];
int m_flat[5 * 7];

Well-defined ways to use the accessor functions:

get_multi(5, 7, m_multi, 4, 2);

get_flat(5, 7, m_flat, 4, 2);

{
    int *m_ptr[5];

    for(int i = 0; i < 5; ++i)
        m_ptr[i] = m_multi[i];

    get_ptr(5, 7, m_ptr, 4, 2);
}

{
    int *m_ptr[5];

    for(int i = 0; i < 5; ++i)
        m_ptr[i] = &m_flat[i * 7];

    get_ptr(5, 7, m_ptr, 4, 2);
}

Technically undefined usage that works in practice:

get(5, 7, (int *)m_multi, 4, 2);

Answer 5

[Warning - this answer addresses the case where the number of columns - the WIDTH - is known]

When working with 2D arrays, the compiler needs to know the number of columns in your array in order to compute indexing. For instance, if you want a pointer p that points to a range of memory to be treated as a two-dimensional set of values, the compiler cannot do the necessary indexing arithmetic unless it knows how much space is occupied by each row of the array.

Things become clearer with a concrete example, such as the one below. Here, the pointer p is passed in as a pointer to a one-dimensional range of memory. You - the programmer - know that it makes sense to treat this as a 2D array and you also know (must know) how many columns are there in this array. Armed with this knowledge, you can write code to create q, that is treated by the compiler as a 2D array with an unknown number of rows, where each row has exactly NB columns.

I usually employ this when I want the compiler to do all the indexing arithmetic (why do it by hand when the compiler can do it?). In the past, I've found this construct to be useful to carry out 2D transposes from one shape to another - note though that generalized 2D transposes that transpose an MxN array into an NxM array are rather beastly.

void
WorkAs2D (double *p)
{
    double (*q)[NB] = (double (*)[NB]) p;

    for (uint32_t i = 0; i < NB; i++)
    {
        for (uint32_t j = 0; j < ZZZ; j++) /* For as many rows as you have in your 2D array */
            q[j][i] = ...
    }
}

Answer 6

I believe a nice solution would be the use of structures. So I have an example for 1d-Arrays:
Definition of the struct:

struct ArrayNumber {
    unsigned char *array;
    int size;
};

Definition of a function:

struct ArrayNumber calcMultiply(struct ArrayNumber nra, struct ArrayNumber nrb);

Init the struct:

struct ArrayNumber rs;
rs.array = malloc(1);
rs.array[0] = 0;
rs.size = 1;
//and adding some size:
rs.size++;
rs.array = realloc(rs.array, rs.size);

hope this could be a solution for you. Just got to change to a 2d Array.