Stepping through a multidimensional array using pointers in C

Question

As an exercise, I am trying to build a 2 dimensional array of random integers. I want to assign the random numbers by iterating through the array using pointer arithmetic.

I think I'm having trouble with the following For loop, which I lifted from p268 of C Programming by King.

int *p;
for (p = &a[0][0]; p <= &a[NUM_ROWS-1] [NUM_COLUMNS - 1]; p++)

I'm trying to use a similar loop in a program of my own but the program doesn't seem to assign any values.

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

int ** make_array(int in_size );
void read_array( int ** a, int n);

int main(void){
        int size;
        int **p;

        size = 5;
        p = make_array( size );
        read_array( p, size );

        return 0;
}

int ** make_array( int in_size ) {
        int i,  *p, **a;

        srand ((unsigned)time(NULL));

        a = malloc(in_size * sizeof(int*));
        for (i = 0; i < in_size ; i++) {
              a[i] = malloc( in_size * sizeof(int));
        }

        for (p = &a[0][0]; p <= &a[in_size -1 ][in_size - 1]; p++) {
                *p = rand() % 10;
        }

        return a;

}

void read_array( int **a, int n ) {
        int i, *p;
        for (p = &a[0][0] ; p <= &a[n - 1][n - 1]; p++)
                printf("%d ", *p );
}

Now I know I could loop through it pretty easily with nested for loops, this seemed like an elegant way to loop through an array. Any idea what I'm doing wrong?

Answer 1

As you have learned, in C, there are no 2D arrays. There are only ways to simulate indexing for 2D arrays. These fall into two categories, (1) creating an array of pointers to arrays, and (2) creating a normal sequential array and using index arithmetic to reference elements in 2D manner. In each case the arithmetic can be thought of in terms of total number of elements in your array (or size of the array) and the number of columns you want to simulate (or the stride) of the array. Knowing the size and stride of the array, with careful indexing, you can use your C - 1D array as a 2D array. To help finish lifting any issues that remain concerning the two types and the use of pointers and indexes, consider the following:

Array of Pointers to type

First, when you are using an array of pointers to type (e.g. int **array) you allocate ROWS number of pointers to COLS sized arrays of type (essentially you have ROWS number of COLS sized arrays.) Then by dereference, you can index your elements as a 2D array (e.g. array[0][x] where 0 <= x < COLS reads all in the array pointed to by the first pointer, array[1][x], the second pointer, and so on...).

To allocate your array of pointers to type, you allocate ROWS number of pointers (where ROWS are equivalent to the size/stride):

    int **array = NULL;
    ...
    array = xcalloc (size/stride, sizeof *array);

(note: xcalloc is just a function using calloc with error checking to validate allocation)

After allocating your ROWS number of pointers, you allocate a separate column-array of COLS (or stride) number of elements for each original pointer.

    for (i = 0; i < size/stride; i++)
        array[i] = xcalloc (stride, sizeof **array);

After you allocate your array of pointers to type, you will use two loops to fill/manipulate your data in your array:

    for (i = 0; i < size/stride; i++)
        for (j = 0; j < stride; j++)
            array[i][j] = rand() % 1000;

You can access any individual member with simple array[i][j] syntax. Remember you simply consider size/stride as your ROWS and stride as your COLS, so if you are computing the value of ROWS and COLS you could write the above as:

    for (i = 0; i < ROWS; i++)
        for (j = 0; j < COLS; j++)
            array[i][j] = rand() % 1000;

Linear Array Treated as 2D Array

Since you are using a traditional sequential 1D array to hold you data in this case, Declaring and allocating the array is trivial:

    int *array = NULL;
    ...
    array = xcalloc (size, sizeof *array);

note: to access the elements of the array in a simulated 2D fashion, you must store the values in the array using the same logic you will use to access the values, which from the loop standpoint will be exactly the same as you did in the pointers to arrays case above. The only differece will be the computation of the index:

    for (i = 0; i < size/stride; i++)
        for (j = 0; j < stride; j++)
            array[i * stride + j] = rand() % 1000;

Here, a closer look at just how you are simulating array[i][j] access is needed. NOTE: the index for the array:

    array[i * stride + j] = rand() % 1000;

When you have a linear 1D array of elements, the indexing that allows you to treat and access values in 2D fashion is given by array[i * stride + j] where i and j represent ROWS and COLS.

Putting all this into a couple of examples will show you just how all the pieces fit together:

Example - Array of Pointers to type

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

void *xcalloc (size_t n, size_t s);

int main (int argc, char **argv) {

    int **array = NULL;
    int size   = argc > 1 ? (int)strtol(argv[1], NULL, 10) : 36;
    int stride = argc > 2 ? (int)strtol(argv[2], NULL, 10) : 6;
    int i,j;

    /* test valid size/stride */
    if (size < stride || size % stride) {
        fprintf (stderr, "error: invalid stride '%d' for %d element array.\n",
                stride, size);
        return 1;
    }

    srand (time(NULL)); /* initialize seed */

    /* alloc array of pointers to array of integers in memory */
    array = xcalloc (size/stride, sizeof *array);

    /* allocate arrays of integers */
    for (i = 0; i < size/stride; i++)
        array[i] = xcalloc (stride, sizeof **array);

    /* fill with random values */
    for (i = 0; i < size/stride; i++)
        for (j = 0; j < stride; j++)
            array[i][j] = rand() % 1000;

    /* printing in simulated 2D format */
    printf ("\n printing (%d x %d) array\n\n",
            size/stride, stride);

    for (i = 0; i < size/stride; i++) {
        for (j = 0; j < stride; j++)
            printf (" %4d", array[i][j]);
        putchar ('\n');
    }

    /* print a particular element array[1][2] */
    if (stride > 1)
        printf ("\n array[1][1] in (%d x %d) array : %d\n\n",
                size/stride, stride, array[1][1]);

    /* free allocated memory */
    for (i = 0; i < size/stride; i++)
        free (array[i]);
    free (array);

    return 0;
}

/** xcalloc allocates memory using calloc and validates the return.
 *  xcalloc allocates memory and reports an error if the value is
 *  null, returning a memory address only if the value is nonzero
 *  freeing the caller of validating within the body of code.
 */
void *xcalloc (size_t n, size_t s)
{
    register void *memptr = calloc (n, s);
    if (memptr == 0)
    {
        fprintf (stderr, "%s() error: virtual memory exhausted.\n", __func__);
        exit (EXIT_FAILURE);
    }

    return memptr;
}

Example Use/Output

$ ./bin/array_stride_2d 12 2

 printing (6 x 2) array

  535   68
   45  815
  348  480
  417  151
  443  789
  267  738

 array[1][1] in (6 x 2) array : 815

$ ./bin/array_stride_2d 12 3

 printing (4 x 3) array

  841  195  147
  870   18  892
  624  516  820
  250  769  532

 array[1][1] in (4 x 3) array : 18

$ ./bin/array_stride_2d 12 4

 printing (3 x 4) array

  116  275  740  510
  625  122  386  623
  624  879  970  396

 array[1][1] in (3 x 4) array : 122

$ ./bin/array_stride_2d 12 6

 printing (2 x 6) array

  543  631  562  504  307  940
  932   75  225  662  181  990

 array[1][1] in (2 x 6) array : 75

Example - Linear Array Treated as 2D Array

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

void *xcalloc (size_t n, size_t s);

int main (int argc, char **argv) {

    int *array = NULL;
    int size   = argc > 1 ? (int)strtol(argv[1], NULL, 10) : 36;
    int stride = argc > 2 ? (int)strtol(argv[2], NULL, 10) : 6;
    int i,j;

    /* test valid size/stride */
    if (size < stride || size % stride) {
        fprintf (stderr, "error: invalid stride '%d' for %d element array.\n",
                stride, size);
        return 1;
    }

    srand (time(NULL)); /* initialize seed */

    /* alloc array of size sequential in memory */
    array = xcalloc (size, sizeof *array);

    /* fill with random values */
    for (i = 0; i < size/stride; i++)
        for (j = 0; j < stride; j++)
            array[i * stride + j] = rand() % 1000;

    /* printing in simulated 2D format */
    printf ("\n printing (%d x %d) array\n\n",
            size/stride, stride);

    for (i = 0; i < size/stride; i++) {
        for (j = 0; j < stride; j++)
            printf (" %4d", array[i * stride + j]);
        putchar ('\n');
    }

    /* print a particular element array[1][2] */
    if (stride > 1)
        printf ("\n array[1][1] in (%d x %d) array : %d\n\n",
                size/stride, stride, array[1 * stride + 1]);

    free (array);

    return 0;
}

/** xcalloc allocates memory using calloc and validates the return.
 *  xcalloc allocates memory and reports an error if the value is
 *  null, returning a memory address only if the value is nonzero
 *  freeing the caller of validating within the body of code.
 */
void *xcalloc (size_t n, size_t s)
{
    register void *memptr = calloc (n, s);
    if (memptr == 0)
    {
        fprintf (stderr, "%s() error: virtual memory exhausted.\n", __func__);
        exit (EXIT_FAILURE);
    }

    return memptr;
}

Use/Output

$ ./bin/array_stride_1d 12 2

 printing (6 x 2) array

  220  155
  755   51
  427  270
  691  597
  982  995
    4  444

 array[1][1] in (6 x 2) array : 51

$ ./bin/array_stride_1d 12 3

 printing (4 x 3) array

  990  837  473
  153   10  337
  139  940  444
  768  625  457

 array[1][1] in (4 x 3) array : 10

$ ./bin/array_stride_1d 12 4

 printing (3 x 4) array

  617  943  444  396
   38  357  103  441
  646  416   40  586

 array[1][1] in (3 x 4) array : 357

$ ./bin/array_stride_1d 12 6

 printing (2 x 6) array

  364   61  373  723  994  849
  793  332  913  991  999  373

 array[1][1] in (2 x 6) array : 332

Memory Error Check

$ valgrind ./bin/array_stride_1d 12 6
==21560== Memcheck, a memory error detector
==21560== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==21560== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==21560== Command: ./bin/array_stride_1d 12 6
==21560==

 printing (2 x 6) array

  359  841  728  356  563  487
  626   58  823  270  860  896

 array[1][1] in (2 x 6) array : 58

==21560==
==21560== HEAP SUMMARY:
==21560==     in use at exit: 0 bytes in 0 blocks
==21560==   total heap usage: 1 allocs, 1 frees, 48 bytes allocated
==21560==
==21560== All heap blocks were freed -- no leaks are possible
==21560==
==21560== For counts of detected and suppressed errors, rerun with: -v
==21560== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)

Hopefully this has been helpful for your learning that there are basically two schemes for treating arrays as 2D arrays in C. You can even be more creative and create dimensional arrays well beyond 2D, just note the index computation quickly become a bit more involved. Even at the 2D level, you can get quite a bit more out of these methods, like row and column vectors, upper/lower matrices, matrix arithmetic, etc. Let me know if you have any questions.

Answer 2

int *p;
for (p = &a[0][0]; p <= &a[NUM_ROWS-1] [NUM_COLUMNS - 1]; p++)

is valid in two cases:
(1) when 'a' is defined as two dimensional array e.g. int a[NUM_ROWS][NUM_COLUMNS]. In this case, memory chunk is contiguous and hence, it is valid to use pointer variable to iterate through the 2D array elements.

(2) Modify your make_array() function as follows to allocate contiguous chunk of memory to use the above mentioned method.

int ** make_array( int in_size ) 
{
        int i,  *p, **a;
        int *big_chunk;

        srand ((unsigned)time(NULL));

        a = (int **)malloc(in_size * sizeof(int*));
        big_chunk = (int *)malloc(in_size * in_size * sizeof(int));  <-- change done here
        for (i = 0; i < in_size ; i++) 
        {
              a[i] = big_chunk + i * insize;                         <-- change done here
        }

        /* Other code */
}

In your original make_array() function, malloc() does not guarantee contiguous memory chunks in successive iteration of malloc() call. Hence, using pointer to iterate through the 2D array elements will not be correct. e.g. once 'p' reaches a[0][in_size-1] then p = &a[0][in_size] will be different than a[1] -> malloc address for 2nd row.