******* INCOMPLETE !!! *******
Arrays and pointers in C
========================
(Thanks a lot to Steve Summit for the very illuminating comments)
This is a short review on arrays and pointers in C with an emphasis
on using multi-dimensional arrays. The seemingly unrelated C rules
are explained as an attempt to unify arrays and pointers, or maybe
even replace arrays and the basic array equation by a new notation
and special rules (see below).
The purpose of the following text is threefold:
1) Help those who mix C modules in their programs to
understand the pointer notation of C and pass arrays
between FORTRAN and C.
2) Show possible workarounds for the lack of adjustable
arrays, one of C technical shortcomings.
3) Show an interesting method of array implementation.
The C language as a "portable assembler"
----------------------------------------
Older operating systems and other system software were written
in assembly language. CPUs were slow and memories very small,
and only assembly language could generate the tight code needed.
However, assembly is difficult to maintain and by definition not
portable, so the advantages of a High Level Language designed
for system programming were clear. Improvements in hardware and
compiler technology made C a success.
Pointers and pointer operators
------------------------------
FORTRAN impose a major restriction on the programmer, you can
reference only named memory locations, i.e. variables.
Pointers make it possible, like in assembly, to reference in
a useful way any memory location.
A pointer is a variable suitable for keeping memory addresses
of other variables, the values you assign to a pointer are
memory addresses of other variables (or other pointers).
How useful are pointers for scientific programming?
Probably less than C fans think. It's well known that having
unrestricted pointers in a programming language makes it
difficult for the compiler to generate efficient code.
C pointers are characterized by their value and data-type.
The value is the address of the memory location the pointer
points to, the type determines how the pointer will be
incremented/decremented in pointer (or subscript) arithmetic
(see below).
Arrays in C and the array equation
----------------------------------
We will use 2D arrays in the following text instead of general
N-dimensional arrays, they can illustrate the subtle points
involved with using arrays and pointers in C, and the arithmetic
will be more manageable.
A 2D array in C is treated as a 1D array whose elements are 1D
arrays (the rows).
For example, a 4x3 array of T (where "T" is some data type) may
be declared by: "T mat[4][3]", and described by the following
scheme:
+-----+-----+-----+
mat == mat[0] ---> | a00 | a01 | a02 |
+-----+-----+-----+
+-----+-----+-----+
mat[1] ---> | a10 | a11 | a12 |
+-----+-----+-----+
+-----+-----+-----+
mat[2] ---> | a20 | a21 | a22 |
+-----+-----+-----+
+-----+-----+-----+
mat[3] ---> | a30 | a31 | a32 |
+-----+-----+-----+
The array elements are stored in memory row after row, so the
array equation for element "mat[m][n]" of type T is (this is
not C notation!):
address(mat[i][j]) = address(mat[0][0]) + (i * n + j) * size(T)
address(mat[i][j]) = address(mat[0][0]) +
i * n * size(T) +
j * size(T)
address(mat[i][j]) = address(mat[0][0]) +
i * size(row of T) +
j * size(T)
A few remarks:
1) The array equation is important, it is the connection
between the abstract data-type and its implementation.
In Fortran (and many other languages) it is "hidden"
from the programmer, the compiler automatically "plants"
the necessary code whenever an array reference is made.
2) For higher-dimensional arrays the equation gets more
and more complicated. In some programming languages
an arbitrary limit on the dimension is imposed,
e.g. Fortran arrays can be 7D at most.
3) Note that it's more efficient to compute the array
equation "iteratively" - not using the distributive
law to eliminate the parentheses (just count the
arithmetical operations in the first two versions
of the array equation above).
The K&R method (see below) works iteratively.
It reminds one of Horner's Rule for computing a
polynomial iterativly, e.g.
a * x**2 + b * x + c = (a * x + b) * x + c
computing the powers of x is eliminated in this way.
4) The number of rows doesn't enter into the array equation,
you don't need it to compute the address of an element.
That is the reason you don't have to specify the first
dimension in a routine that is being passed a 2D array,
just like in Fortran's assumed-size arrays.
The K&R method of reducing arrays to pointers
---------------------------------------------
K&R tried to create a unified treatment of arrays and pointers,
one that would expose rather than hide the array equation in the
compiler's code. They found an elegant solution, albeit a bit
complicated. The "ugly" array equation is replaced in their
formulation by four rules:
1) An array of dimension N is a 1D array with
elements that are arrays of dimension N-1.
2) Pointer addition is defined by:
ptr # n = ptr + n * size(type-pointed-into)
"#" denotes here pointer addition to avoid
confusion with ordinary addition.
The function "size()" returns object's sizes.
3) The famous "decay convention": an array is
treated as a pointer that points to the
first element of the array.
The decay convention shouldn't be applied
more than once to the same object.
4) Taking a subscript with value i is equivalent
to the operation: "pointer-add i and then
type-dereference the sum", i.e.
xxx[i] = *(xxx # i)
When rule #4 + rule #3 are applied recursively
(this is the case of a multi-dimensional array),
only the data type is dereferenced and not the
pointer's value, except on the last step.
K&R rules imply the array equation
----------------------------------
We will show now that the array equation is a consequence
of the above rules (applied recursively) in the case of a
2D array:
mat[i] = *(mat # i) (rule 4)
mat[i][j] = *(*(mat # i) # j) (rule 4)
"mat" is clearly a "2D array of T" and decays by (rule 3)
into a "pointer to a row of T". So we get the first two terms
of the array equation.
mat[i][j] = *(*(mat + i * sizeof(row)) # j)
^^^^^^^^^^^^^^^^^^^^^
Pointer to row of T
Dereferencing the type of "(mat # i)" we get a "row of T".
mat[i][j] = *((mat + i * sizeof(row)) # j)
^^^^^^^^^^^^^^^^^^^^^^^
Row of T
We have now one pointer addition left, using again the
"decay convention", the 1D array "row of T" becomes a
pointer to its first element, i.e. "pointer to T".
We perform the pointer addition, and get the third term
of the array equation:
mat[i][j] = *(mat + i * sizeof(row) + j * sizeof(T))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Pointer to T
address(mat[i][j]) = mat + i * sizeof(row) + j * sizeof(T)
Remember that "mat" actually points to the first element
of the array, so we can write:
address(mat[i][j]) = address(mat[0][0]) +
i * sizeof(row) +
j * sizeof(T)
This is exactly the array equation. QED
Why a double pointer can't be used as a 2D array?
-------------------------------------------------
This is a good example, although the compiler may not complain,
it is wrong to declare: "int **mat" and then use "mat" like
a 2D array. These are two very different data-types and using
them you access different places in memory. On a good machine
(e.g. VAX/VMS) this mistake aborts the program with a "memory
access violation" message.
This mistake is common because it is easy to forget that the
decay convention mustn't be applied recursively (more than
once) to the same array, so a 2D array is NOT equivalent
to a double pointer.
A "pointer to pointer of T" can't serve as a "2D array of T".
The 2D array is "equivalent" to a "pointer to row of T",
and this is very different from "pointer to pointer of T".
When a double pointer that points to the first element of
an array, is used with subscript notation "ptr[0][0]",
it is fully dereferenced two times (see rule #5).
After two full dereferencings the resulting object will
have an address equal to whatever value was found INSIDE
the first element of the array. Since the first element
contains our data, we would have wild memory accesses.
We could take care of the extra dereferencing by having
an intermediary "pointer to T":
type mat[m][n], *ptr1, **ptr2;
ptr2 = &ptr1;
ptr1 = (type *)mat;
but that wouldn't work either, the information on the array
"width" (n), is lost, and we would get right only the first row,
then we will have again wild memory accesses.
A possible way to make a double pointer work with a 2D array
notation is having an auxiliary array of pointers, each of
them points to a row of the original matrix.
type mat[m][n], *aux[m], **ptr2;
ptr2 = (type **)aux;
for (i = 0 ; i < m ; i++)
aux[i] = (type *)mat + i * n;
Of course the auxiliary array could be dynamic.
An example program
------------------
#include <stdio.h>
#include <stdlib.h>
main()
{
long mat[5][5], **ptr;
mat[0][0] = 3;
ptr = (long **)mat;
printf(" mat %p \n", mat);
printf(" ptr %p \n", ptr);
printf(" mat[0][0] %d \n", mat[0][0]);
printf(" &mat[0][0] %p \n", &mat[0][0]);
printf(" &ptr[0][0] %p \n", &ptr[0][0]);
return;
}
The output on VAX/VMS is:
mat 7FDF6310
ptr 7FDF6310
mat[0][0] 3
&mat[0][0] 7FDF6310
&ptr[0][0] 3
We can see that "mat[0][0]" and "ptr[0][0]" are different objects
(they have different addresses), although "mat" and "ptr" have
the same value.
What methods for passing a 2D array to a subroutine are allowed?
----------------------------------------------------------------
Following are 5 alternative ways to handle in C an
array passed from a Fortran procedure or another
c routine.
Various ways to declare and use such an array are
presented by examples with an array made of 5x5
shorts (INTEGER*2). All 5 methods work on a VAX/VMS.
the following 2 "include" statements must be present
in each file that contains these routines:
#include <stdio.h>
#include <stdlib.h>
Method #1 (No tricks, just an array with empty first dimension)
===============================================================
func2d(short mat[][5]) /* You don't have to specify the first dimension! */
{
register short i, j;
printf("\n In the C routine: \n");
printf("\n");
for(i = 0 ; i < 5 ; i++)
{
printf("\n");
for(j = 0 ; j < 5 ; j++)
{
mat[i][j] = i+5;
printf("%11d", mat[i][j]);
}
}
printf("\n");
return;
}
Method #2 (Using a single pointer, the array is "flattened")
============================================================
With this method you can create general-purpose routines.
The dimensions doesn't appear in any declaration, so you
can add them to the formal argument list.
The manual array indexing will probably slow down execution.
func2d(short *mat)
{
register short i, j;
printf("\n In the C routine: \n");
printf("\n");
for(i = 0 ; i < 5 ; i++)
{
printf("\n");
for(j = 0 ; j < 5 ; j++)
{
*(mat+5*i+j) = i+5;
printf("%11d", *(mat+5*i+j));
}
}
printf("\n");
return;
}
Method #3 (double pointer, using an auxiliary array of pointers)
================================================================
With this method you can create general-purpose routines,
if you allocate "index" at run-time.
Add the dimensions to the formal argument list.
func2d(short **mat)
{
short i, j, *index[5];
for (i = 0 ; i < 5 ; i++)
index[i] = (short *)mat + 5*i;
printf("\n In the C routine: \n");
printf("\n");
for(i = 0 ; i < 5 ; i++)
{
printf("\n");
for(j = 0 ; j < 5 ; j++)
{
index[i][j] = i+5;
printf("%11d", index[i][j]);
}
}
printf("\n");
return;
}
Method #4 (single pointer, using an auxiliary array of pointers)
===================================================================
func2d(short *mat[5])
{
short i, j, *index[5];
for (i = 0 ; i < 5 ; i++)
index[i] = (short *)mat + 5*i;
printf("\n In the C routine: \n");
printf("\n");
for(i = 0 ; i < 5 ; i++)
{
printf("\n");
for(j = 0 ; j < 5 ; j++)
{
index[i][j] = i+5;
printf("%11d", index[i][j]);
}
}
printf("\n");
return;
}
Method #5 (pointer to array, second dimension is explicitly specified)
======================================================================
func2d(short (*mat)[5])
{
register short i, j;
printf("\n In the C routine: \n");
printf("\n");
for(i = 0 ; i < 5 ; i++)
{
printf("\n");
for(j = 0 ; j < 5 ; j++)
{
mat[i][j] = i+5;
printf("%11d", mat[i][j]);
}
}
printf("\n");
return;
}
Return to contents page