two dimensional array via pointer

Question

I would like to create a dynamic array which store permutation sequence, such that

order[0][]={1,2,3}
order[1][]={2,1,3}
order[2][]={2,3,1}

let say order[m][n], m = number of permutation, n = number of term, m and n are identified in real-time.

I did the below, and found that the pointer address is overlapping, resulting in incorrect value storage. How can do it correctly using dynamic array via double pointer?

void permute(int num_permute, int num_term, int** order) {
    int x, y;
    int term[5];

    /* debug only */
    for(y=num_term, x=0; y>0; y--, x++){
        term[x] = y;
    }
    fprintf(stderr, "\n");

    printf("order%12c", ' ');
    for (x=0; x<num_permute; ++x) {
        printf("  %-11d", x);
    }
    printf("\n");
    for(y=0; y<num_permute; y++){
        printf("%-5d%12p", y, (order+y));
        memcpy(&(order[y]), term, sizeof(term));

        for (x=0; x<num_term; x++)
            printf(" %12p", order+y+x);

        printf("\n");

    }
}

int main(){
    int y, z;
    int** x;

    x = (int*) malloc(5*5*sizeof(int*));

    permute(5, 5, x);
    printf("\n");

    printf("x   ");
    for(z=0; z<5; z++){
        printf(" %2d ", z);
    }
    printf("\n");
    for(y=0; y<5; y++){
        printf("%-4d", y);
        for(z=0; z<5; z++){
            printf(" %2d ", *(x+y+z));
        }
        printf("\n");
    }

    free(x);

    return 0;
}

Result: order[0][1] and order[1][0] point to same address... and so do others. With rows as the major axis and columns the minor:

order             0            1            2            3            4           
0     0x100100080 0x100100080  0x100100084  0x100100088  0x10010008c  0x100100090
1     0x100100084 0x100100084  0x100100088  0x10010008c  0x100100090  0x100100094
2     0x100100088 0x100100088  0x10010008c  0x100100090  0x100100094  0x100100098
3     0x10010008c 0x10010008c  0x100100090  0x100100094  0x100100098  0x10010009c
4     0x100100090 0x100100090  0x100100094  0x100100098  0x10010009c  0x1001000a0

x     0   1   2   3   4 
0     5   5   5   5   5 
1     5   5   5   5   4 
2     5   5   5   4   3 
3     5   5   4   3   2 
4     5   4   3   2   1

Note: SO uses a Q&A format. Questions shouldn't contain answers. — outis
– outis, Commented Dec 28, 2011 at 8:43

outis · Accepted Answer · 2011-12-28 08:54:26Z

Source Code:
The code will be something like:

#include <stdlib.h>

int **array;
array = malloc(nrows * sizeof(int *));
if(array == NULL)
{
     fprintf(stderr, "out of memory\n");
     /*exit or return*/
}
for(i = 0; i < nrows; i++)
{
    array[i] = malloc(ncolumns * sizeof(int));
    if(array[i] == NULL)
    {
          fprintf(stderr, "out of memory\n");
         /*exit or return*/
    }
}

Concept:

array is a pointer-to-pointer-to-int: at the first level, it points to a block of pointers, one for each row. That first-level pointer is the first one to be allocated; it has nrows elements, with each element big enough to hold a pointer-to-int, or int *. If the allocation is successful then fill in the pointers (all nrows of them) with a pointer (also obtained from malloc) to ncolumns number of ints, the storage for that row of the array.

Pictorial Depiction:

It is simple to grasp if you visualize the situation as:

pointers to arrays of pointers as multidimensional arrays

Taking this into account, the sample code could be rewritten as:

void permute(int num_permute, int num_term, int** order) {
    int x, y;
    int term[5];
    int* ptr = NULL;

    for (y=num_term, x=0; y>0; y--, x++) {
        term[x] = y;
    }
    printf("\n");

    printf("order%12c", ' ');
    for (x=0; x<num_permute; ++x) {
        printf(" %2d ", x);
    }
    printf("\n");
    for (y=0; y<num_permute; y++) {
        ptr = order[y];
        memcpy(ptr, term, sizeof(term));

        printf("%-5d%12p", y, ptr);
        for (x=0; x<num_term; x++) {
            printf(" %2d ", ptr[x]);
        }
        printf("\n");
    }
}

int main() {
    int y, z;
    int** x = NULL;
    int num_term = 5;
    int num_permutation = 5;
    int* pchk = NULL;

    x = (int**) malloc(num_permutation * sizeof(int*));

    for (y=0; y<num_permutation; y++){
        x[y] = (int*) malloc(num_term * sizeof(int));
        printf("x[%d]: %p\n", y, x[y]);
    }

    permute(num_permutation, num_term, x);

    printf("\nx:  ");
    for(z=0; z<5; z++){
        printf(" %2d ", z);
    }
    printf("\n");

    for(y=0; y<num_permutation; y++){
        pchk = x[y];
        printf("%-4d", y);
        for(z=0; z<num_term; z++){
            printf(" %2d ", pchk[z]);
        }
        printf("\n");
    }

    for (y=0; y<num_permutation; y++) {
        free(x[y]);
    }
    free(x);

    return 0;
}

outis · Accepted Answer · 2011-12-28 08:55:36Z

The code sample only simulates a multidimensional array, and does it incorrectly. To see what's going wrong, start by considering what happens when you declare a multidimensional array:

int foo[3][5];

This allocates a contiguous region of memory of size 3*5*sizeof(int). In an expression such as foo[i], the foo is converted to a int [5] pointer, then the index operator is applied. In other words, foo[i] is equivalent to *( (int (*)[5])foo) + i). Each foo[i] would be considered as having size 5*sizeof(int).

   x,y:  0,0 0,1 0,2 0,3 0,4 1,0 
foo --> | 1 | 2 | 3 | 4 | 5 | 1 |...
        <- 5 * sizeof(int) ->

When you create x in the sample code, you're replicating this type of multidimensional array. The index expression you're using (*(order + y + x)) is thus wrong, as it doesn't properly handle the size of order[y]: order + 1 + 0 == order + 0 + 1, which is the problem you're seeing in the sample output.

The correct expressions are: (order + num_term * y) for the y^th permutation and *(order + num_term * y + x) for element order[y][x].

This suggests another class of error in the sample. For this kind of simulated multidimensional array, the array types are actually pointers to single dimensional arrays. The declared types of x and order should be int*, not int**. This should be reinforced by the type warnings the sample code should generate:

when allocating space for x, the type of the pointer (int*) doesn't match the type of x
when printing the elements of x, the type of *(x+y+z) doesn't match the format "%d".

However, while simulating a multidimensional array saves space, it's more error prone when used (unless you write a function to handle indexing). A solution such as Als' may be safer, as you can use the standard indexing operator.

I agree that using a real 2D array is probably the best here. Only that for the OP the dimension are dynamic and not known at compile time. With C99 one could do a VLA directly on the stack, but this is a bit dangerous when the dimensions are unknown. This is why I use a malloced array in my answer.
@JensGustedt: it's not that twfx should use a 2D array. I'm just using that to explain what's happening in the code.

Jens Gustedt · Accepted Answer · 2011-12-28 08:21:11Z

Emulating a 2D array with pointer arrays is a complete overkill if you have C99 (or C11). Just use

void permute(size_t num_permute, size_t num_term, unsigned order[][num_term]);

as your function signature and allocate your matrix in main with something like

unsigned (*order)[m] = malloc(sizeof(unsigned[n][m]));

Also, as you can see in the examples above, I'd suggest that you use the semantically correct types. Sizes are always best served with size_t and your permutation values look to me as if they will never be negative. Maybe for these you also should start counting from 0.

Sangeeth Saravanaraj · Accepted Answer · 2011-12-28 07:25:54Z

The following code snippet creates a 2d matrix for a given row and column. Please use this as a reference to debug your program.

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

int main()
{
        int row, column;
        int **matrix;
        int i, j, val;

        printf("Enter rows: ");
        scanf("%d", &row);
        printf("Enter columns: ");
        scanf("%d", &column);

        matrix = (int **) malloc (sizeof(int *) * row);
        if (matrix == NULL) {
                printf("ERROR: unable to allocate memory \n");
                return -1;
        }  
        for (i=0 ; i<row ; i++) 
                matrix[i] = (int *) malloc (sizeof(int) * column);

        val=1;
        for (i=0 ; i<row ; i++) {
                for (j=0 ; j<column; j++) {
                        matrix[i][j] = val++;
                }
        }

        for (i=0 ; i<row ; i++) {
                for (j=0 ; j<column; j++) {
                        printf("%3d  ", matrix[i][j]);
                }
                printf("\n");
        }

        return 0;
}

/*
Allocation of 2d matrix with only one call to malloc and 
still get to access the matrix with a[i][j] format

the matrix is divided into headers and data.

headers = metadata to store the rows
data = actual data storage - buffer

allocate one contigious memory for header and data
and then make the elements in the header to point to the data are

        <- headers -----><----------- data -----------

        -----------------------------------------------------------------
        | | | | | |     ..      |
        | | | | | |     ..      |
        -----------------------------------------------------------------
         |                                 ^
         |                                 |
         |-----------------|
        header points to data area

*/

/*
Output:

$ gcc 2darray.c 
$ ./a.out 
Enter rows: 10
Enter columns: 20
  1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20  
 21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40  
 41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60  
 61   62   63   64   65   66   67   68   69   70   71   72   73   74   75   76   77   78   79   80  
 81   82   83   84   85   86   87   88   89   90   91   92   93   94   95   96   97   98   99  100  
101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  
121  122  123  124  125  126  127  128  129  130  131  132  133  134  135  136  137  138  139  140  
141  142  143  144  145  146  147  148  149  150  151  152  153  154  155  156  157  158  159  160  
161  162  163  164  165  166  167  168  169  170  171  172  173  174  175  176  177  178  179  180  
181  182  183  184  185  186  187  188  189  190  191  192  193  194  195  196  197  198  199  200  
$ 

*/

Collectives™ on Stack Overflow

two dimensional array via pointer

4 Answers 4

1 Comment

2 Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

2 Comments

Comments

Comments

Linked

Related