2D DMA

[Bogeyman]

This is a C question.

I have dynamically allocated a two dimensional array of characters. The problem is that when I try to enter values into the array, it's skipping over the elements, so I can only enter a few values. I think the problem may have something to do with the fact that my delimiter(line 29) is specified for characters, but the input is also taking i and j, which are integers, into consideration.

Really though I don't know. Any help?

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

int main()
{
    int i = 0, j = 0;
    int rows = 0, cols = 0;
    char *array;

    printf("How many rows? ");
    scanf("%d", &rows);

    printf("How many columns? ");
    scanf("%d", &cols);

    array = malloc(rows * cols * sizeof(char));

    if(array == NULL)
    {
        printf("Memory could not be allocated.\n");
    }
    else
    {
        for(i = 0; i < rows; i++)
        {
            for(j = 0; j < cols; j++)
            {
                printf("Enter value for element %d,%d: ", i, j);
                scanf("%c", array + i + j);
            }
        }

        for(i = 0; i < rows; i++)
        {
            for(j = 0; j < cols; j++)
            {
                printf("%c", *(array + i + j));
            }

            printf("\n");
        }
    }

    free(array);

    return 0;
}

[keskiverto]

It's the pointer math.

You have a continuous block of memory. Lets say that rows=2, cols=4, so the block has 8 characters (allocated on line 16). If you use that block as 1D array, you have indices 0..7:

01234567

Your program pretends that it is a 2D array:

0123
4567

On your nested loop the first row behaves nicely:

i=0, j=0, => array[0]
i=0, j=1, => array[1]
i=0, j=2, => array[2]
i=0, j=3, => array[3]

Then you start the next line:

i=1, j=0, => array[1]
i=1, j=1, => array[2]
i=1, j=2, => array[3]
i=1, j=3, => array[4]

Oh my. That was not what it should. This is what we did expect:

i=1, j=0, => array[4]
i=1, j=1, => array[5]
i=1, j=2, => array[6]
i=1, j=3, => array[7]

Perhaps:
array + i*cols + j


PS. In code like this the i and j are hard to track names. Something more explicit:

for ( row = 0; row < Rows; ++row )
{
  for( col = 0; col < Cols; ++col )
  {
    printf( "%c", *(array + row*Cols + col) );
  }
  printf( "\n" );
}

[Bogeyman]

Thank you for the explanation.

However, I'm not sure if it's just because I haven't implemented what you suggested correctly, but it's still not working.

Why multiply i by cols?

Also, would you explain why, when i increments to 1, it accesses elements 1 through 4 instead of elements 4 through 7?

[keskiverto]

You ask, why adding 1 to i in i+j does add only one to the sum, rather than 4.
You also ask, why to add 1*4 to the sum, when we want to add 4 to the sum.

Does the following shed any light?

#include <stdio.h>

int main() {
  int row, col;
  int Rows = 7;
  int Cols = 5;

  printf( "1D\n" );
  for( col = 0; col < Rows*Cols; ++col )
  {
    printf( "%d ", col );
  }
  printf( "\n\n" );

  printf( "1D, take two\n" );
  for ( row = 0; row < Rows; ++row )
  {
    for( col = 0; col < Cols; ++col )
    {
      printf( "%d ", row*Cols + col );
    }
  }
  printf( "\n\n" );

  printf( "2D\n" );
  for ( row = 0; row < Rows; ++row )
  {
    printf( "Row %d: ", row );
    for( col = 0; col < Cols; ++col )
    {
      printf( "[%d,%d]=%2d ", row, col, row*Cols + col );
    }
    printf( "\n" );
  }
  return 0;
}

[Bogeyman]

I'm sorry but I still don't understand.

Your representation of the 2D array is very nice but I still don't know why you are multiplying the index by the number of columns in the array. I tried to do that when entering the data but it's still skipping indexes.

[keskiverto]

You do calculate the address of a character with: array + x
Lets say that the 2D array has C columns.

What is the x for the first character? 0*C
What is the x for the first character of second row? 1*C
What is the x for the first character of third row? 2*C
What is the x for the first character of fourth row? 3*C

The column index of each first character is 0.


My first loop (lines 9-12) prints the x for consecutive characters.
My second loop (16-21) prints x computed from row and col.
Both loops produce identical results.


Your code did access array element on lines 29 and 37. Did you fix both the same way?

[Bogeyman]

This is what I changed my code to. The elements are still being skipped however.

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

int main()
{
    int i = 0, j = 0;
    int rows = 0, cols = 0;
    char *array;

    printf("How many rows? ");
    scanf("%d", &rows);

    printf("How many columns? ");
    scanf("%d", &cols);

    array = malloc(rows * cols * sizeof(char));

    if(array == NULL)
    {
        printf("Memory could not be allocated.\n");
    }
    else
    {
        for(i = 0; i < rows; i++)
        {
            for(j = 0; j < cols; j++)
            {
                printf("Enter value for element %d,%d: ", i, j);
                scanf("%c", array + i*cols + j);
            }
        }

        for(i = 0; i < rows; i++)
        {
            for(j = 0; j < cols; j++)
            {
                printf("%c", *(array + i*cols + j));
            }

            printf("\n");
        }
    }

    free(array);

    return 0;
}

[keskiverto]

And now we finally see the real culprit. The line 29.

Do you hit Enter after the columns number? After individual characters? I bet you do, and the "read a character" does read and store the newline(s) into the array.

Try:
scanf(" %c", array + i*cols + j);
Just one additional space in the format string, but it does:
http://www.cplusplus.com/reference/cstdio/scanf/

format
C string that contains a sequence of characters that control how characters extracted from the stream are treated:
* Whitespace character: the function will read and ignore any whitespace characters encountered before the next non-whitespace character

[Bogeyman]

Thank you very much keskiverto.

However, I am still confused as to how

        for(i = 0; i < rows; i++)
        {
            for(j = 0; j < cols; j++)
            {
                printf("Enter value for element %d,%d: ", i, j);
                scanf(" %c", array + i*cols + j);
            }
        }

works.

My logic must be wrong, as the program does in fact work this way, but this is what I think should be happening.

Say I give rows and cols a value of 3.

On the first iteration, i * cols is 0 and j is 0, so you are entering data into element 0,0.
On the second iteration, i * cols is 0 and j is 1, so you are entering data into element 0,1.
On the third iteration, i * cols is 0 and j is 2, so you are entering data into element 0,2.

(From here is where I think it should be going wrong).
On the fourth iteration, i * cols is 3 and j is 0, so you are entering data into element 3,0.
On the fifth iteration, i * cols is 3 and j is 1, so you are entering data into element 3,1.
On the sixth iteration, i * cols is 3 and j is 2, so you are entering data into element 3,2.

On the seventh iteration, i * cols is 6 and j is 0, so you are entering data into element 6,0.
On the eighth iteration, i * cols is 6 and j is 1, so you are entering data into element 6,1.
Finally, on the ninth iteration, i * cols is 6 and j is 2, so you are entering data into element 6,2.

Obviously this is not what is happening, but I feel this is what should be happening. I also feel that the line

scanf(" %c", array + i + j);

should work, but it doesn't.

I'm really confused about this. Would you be willing to explain it to me?

[keskiverto]

Lets try another approach:

// replace
scanf(" %c", array + i*cols + j);

// with
x = i*cols + j; // x is int
scanf(" %c", array + x );

Q: How does the array now know which column and row, because you add only one integer?
A: It does not.

(It never did. Nothing has actually changed; both versions do exactly the same thing.)

[Bogeyman]

Okay, I think I see now.

I thought that the array needed to know what x and y coordinates you wanted to read in.

Am I right in thinking now, however, that the array, even though conceptually it is 2D, is in fact treated as one longer 1D array, and that when you want to read in values, you are simply incrementing the address being read into?

To demonstrate, I changed the code to this;

int x = 0;

for(i = 0; i < rows; i++)
        {
            for(j = 0; j < cols; j++)
            {
                printf("Enter value for element %d,%d: ", i, j);

                scanf(" %c", array + x);

                x++;
            }
        }

and it worked just the same.

The x value is just representing which of the addresses is being read into.

Am I right? Please correct me if I'm wrong.

[keskiverto]

Yes.


Remember, you do create the array:

bytes = rows * cols * sizeof(char); // bytes is integer
array = malloc( bytes );

The malloc knows only the number of bytes. It does not know whether those bytes are used as logical floating point number, 1D array, 2D array, 42D array, etc

[Bogeyman]

Is it the case however that when creating a 2D array at compile time, such as array[3][3], that to access elements of the array, you do need to specify the x and y coordinates when entering data?

For example;

        for(i = 0; i < rows; i++)
        {
            for(j = 0; j < cols; j++)
            {
                printf("Enter value for element %d,%d: ", i, j);
                scanf(" %c", array + i + j);
                OR
                scanf(" %c", array[i][j]);
            }
        }

Or is it the same as with dynamic arrays?

[keskiverto]

Yes, in:

void foo() {
  int Rows = 4;
  int Cols = 3;
  char box[Rows][Cols];

  box[ 2 ][ 1 ] = 'z';
}

the compiler will generate such code that when this function is called, memory is allocated from the stack for two integers and 12 char's. The compiler does need the size(s) during compilation (although latest C standard does support variable length arrays, VLAs, too).

Our line 6 reads: box[ 2 ][ 1 ] = 'z';
We can logically cut it into steps:
1. The box[ 2 ] returns what must behave like a char *. Lets call it tmp1. The address hold in tmp1 is actually the address of the first byte of box plus 2*Cols bytes.

2. The [ 1 ] is thus dereferencing the tmp1.

3. 'z' is written to the element 2,1.

In other words, A and B mean the same:

/* A */
box[2][1]

/* B */
*( &(box[0][0]) + 2*Cols + 1 )

The thing is that when the compiler saw the declaration of box, it did memorize that row length of box is Cols, and when the code contains box[r][c], the compiler adds the value Cols into the calculation, just like we did ourself for our dynamic array.

The scanf requires an address, so the static array:
scanf( " %c", &(array[i][j]) );


Now something almost, but not quite, entirely ...

int main()
{
    int i = 0, j = 0;
    int rows = 3, cols = 4; /* pretend that the user gives these */
    char* *array;

    /* allocate */
    array = malloc( rows * sizeof(char*) ); /* array of pointers */
    array[0] = malloc( rows * cols * sizeof(char) );
    for( i = 1; i < rows; ++i )
    {
      array[i] = array[0] + i*cols;
    }


    /* use */
    for( i = 0; i < rows; ++i )
    {
       for(j = 0; j < cols; j++)
       {
          array[i][j] = 42; /* used like static array */
       }
    }

    /* deallocate */
    free( array[0] );
    free( array );

    return 0;
}

We did allocate an additional array ... of pointers.
The first pointer stores address of the char array.
The other pointers store addresses of the first characters of each logical row.

As result, the "array" can be dereferenced just like a static array. We still do the i*cols on line 12, but the "use" part of the code has the "simpler" syntax.

The "simplicity" has cost though, memory for the pointer array and more pointer dereferencing.

[Bogeyman]

Hmm... that's a lot to take in.

I don't understand much of that, but you've helped me with my original problem and I've learned more about how dynamic arrays work, so I'm happy to leave it at that.

Thank you very much for all your help, it's much appreciated.