NetNews Usenet Archive 1993 #1/NN_1993_1.iso/spool/comp/lang/c/19300

Internet Message Format | 1993-01-06 | 5.9 KB

Path: sparky!uunet!mcsun!sun4nl!and!jos
From: [e-mail] (Jos Horsmeier)
Newsgroups: comp.lang.c
Subject: Re: Moving from Pascal to C, Help please!!!!!!
Message-ID: <[e-mail]>
Date: 6 Jan 93 10:46:18 GMT
References: <[e-mail]> <[e-mail]> <[e-mail]>
Organization: AND Software BV Rotterdam
Lines: 147

In article <[e-mail]> [e-mail] (Dave Eisen) writes:
|In article <[e-mail]> [e-mail] (D. Subramani) writes:
|>
|>I would recommend that you have a look at "Numerical Recipies in C"
|>'cause there they explain how arrays of 2-D are pointers to a pointer
|>and so on which no one else does. Also they have a few routines that
|>allocate memory as per your requirement, ie. [6...26] etc. but be
|>warned, when you do that you will not be able to exploit the advantages
|>of pointer arethmatic fully (it will be too confusing).

|I've never read this book, but I sincerely hope that they do
|not explain that 2D arrays are pointers to pointers because
|they most certainly are not. This distinction is not fully
|understood by a large number of new C programmers and a question
|about it appears here every week or two. I would hate to think
|that popular books like "Numerical Recipes in C" are contributing
|to this misunderstanding.

IMHO `Numerical Recipes in C' is a fine book when one needs to implement
one or more of those nifty, clever numerical algorithms. Also IMHO this
book is a horrible mess when it comes to the usage of the C language.
I've read this book and it gave me the shivers. The authors should have
sticked to FORTRAN or Pascal. They've really made a mess out of things
when they made the transition to C.

|I can tolerate what they do with arrays ranging from 6 to 26 because
|while it is not legal C, it does work on every system I've ever
|heard about. Still, it would be nice if they had gotten this
|right too.

Then you've just been plain lucky and so were the authors of NRC. 99%
of all their pointer fiddling (subtracting the lowest index value from a
pointer) is done with an offset of one. Imagine a segmented memory
architecture as used in a PC. Global arrays are almost never stored
at the beginning of a segment, so the offset of the address of such
an array is always larger than one. Pointer arithmetic is almost always
done using the offset. The segment value is ignored. The same thing is
valid for dynamically allocated memory. Most implementations of the
malloc() function I've seen, prepend the size of the allocated block
in front of that block. This results in an offset of at least two.
In both cases, subracting one from a pointer value, described above,
can do no harm. But if one tries to subtract six (as in your example)
from such a pointer value, please let me know in advance: the behavior
is undefined and no one can tell what's gonna happen then. Maybe the
PC will explode? Who knows ... ;-)

About 2D arrays being an array of pointers, pointing to 1D arrays:
As you wrote, a lot of people get it wrong when they start programming
in C. Lets have a look what the standard has to say about all this:

the standard may cause a bit of confusion when not interpreted
correctly. 3.3.2.1. Array subscripting:

Successive subscript operators designate an element of a multidimensional
array object. If E is an n-dimensional array (n >= 2) with dimensions
i*j* ... *k, then E (used as other than an lvalue) is converted to a
pointer to an (n-1) dimensional array with dimensions j* ... *k. If the
unary * operator is applied to this pointer explicitely, or implicitely
as a result of subscripting, the result is the pointed to (n-1) dimen-
sional array, which itself is converted into a pointer if used as
other than an lvalue. [ ... ]

All this pointer conversion stuff may confuse the reader. All what this
paragraph says, is, that when used in an _expression_, the (partly)
subscripted array is converted to a pointer. Those pointer values
aren't stored anywhere in that array.

Another paragraph takes the confusion away: 3.3.6 Additive operators:

footnote:

Another way to approach pointer arithmetic is first to convert the
pointer(s) to character pointer(s): [ ... ] For pointer subtracion,
the result of the difference between the character pointers is
similarly divided by the size of the object originally pointed to.

Now assume that the following definition:

int a[2][3];

results in a memory layout like this (an array of pointers to arrays):

           p
                  |
     +---+     v
     |   |    +--+--+--+
     | ------>|00|01|02|
     |   |    +--+--+--+
     +---+
     |   |    +--+--+--+
     | ------>|10|11|12|
     |   |    +--+--+--+
     +---+            ^
              |
              q

Lets have a look at the following snippet of code:

int *p= &(a[0][0]);
int *q= &(a[1][2]);

The result of (q-p) has to be 5. But in this implementation, pointers p
and q don't even point to the same object. The same paragraph as quoted
above, reads: 3.3.6. Additive operators:

Unless both pointers point to elements of the same array object, [ ... ]
the behaviour is undefined.

So, the memory layout described above is not a valid implementation
for a 2D array. The array a can simply be implemented as:

     p
     |
     v
    +--+--+--+
    |00|01|02|
    +--+--+--+
    |10|11|12|
    +--+--+--+
                ^
        |
        q

Or, since memory is a linear string of slots (bytes):

     p
     |
     v
    +--+--+--+--+--+--+
    |00|01|02|10|11|12|
    +--+--+--+--+--+--+
                     ^
             |
             q

Now, the pointer subtraction (q-p) is a breeze: simply subtract both
address values and divide the result by the size of an integer.
Subscripting calculations such as a[n][m] is (without further optimi-
zation) done as follows: a[n][m] == *(a+(3*n+m)*sizeof(int)) where a
is considered to be a simple character pointer.

kind regards,

Jos aka [e-mail]

ps. I did not assume a row major ordering, it simply follows from the
    definitions in paragraph 3.3.2.1 described above.