c99 multidimensional arrays contiguous?
pemo
something that said in C99 multidimensional arrays *need not* be laid
out contiguously in memory, i.e., that one should not treat them as a
single contiguous blob of memory!
Was this just a bad dream of mine please??
Andrew Poelstra
> Maybe this was in a nightmare, but I seem to remember reading
> something that said in C99 multidimensional arrays *need not* be laid
> out contiguously in memory, i.e., that one should not treat them as a
> single contiguous blob of memory!
>
Well, the each dimension needs to be contiguous on its own,
and contiguity is transitive, so the entire array /does/ in
fact need to be laid out contiguously in memory.
HOWEVER, it is undefined behavior to rely on this, by, say
accessing array members by bad indices, etc. Basically, the
compiler is allowed to optimize assuming you won't ever do
this, and conversely, it is allowed to do bounds checking
to make sure you don't ever do this.
> Was this just a bad dream of mine please??
>
Why would it be a bad dream? A boring one, perhaps, and
maybe even a waste of a night, if you are that sort of
person.
But not a bad dream, IMHO.
--
Andrew Poelstra
http://www.wpsoftware.net/andrew
Seebs
Sorta yes, sorta no.
1. They must indeed be laid out contiguously in memory.
2. If you derive a pointer from one of the sub-arrays, you should not
then try to derive pointers outside that sub-array from it.
So:
int a[10][10];
int *p = &a[0][0];
p = (int *) a;
p[11] = 0; /* fine, writes to the 12th of 100 members */
p = &a[0][0];
p[11] = 0; /* bad, oversteps boundaries of a[0] */
-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / usenet...@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
pemo
Well because I'd perhaps like to be able to do this, and now I can't -
seems like 'health and safety' or the 'nanny state' creeping up on me.
pemo
On Mar 16, 4:29 pm, Andrew Poelstra <apoels...@localhost.localdomain>
wrote:
pemo
> int *p = &a[0][0];
> p = (int *) a;
pemo
On Mar 16, 4:28 pm, Seebs <usenet-nos...@seebs.net> wrote:
> On 2010-03-16, pemo <peet.mor...@gmail.com> wrote:
>
> > Maybe this was in a nightmare, but I seem to remember reading
> > something that said in C99 multidimensional arrays *need not* be laid
> > out contiguously in memory, i.e., that one should not treat them as a
> > single contiguous blob of memory!
> > Was this just a bad dream of mine please??
>
> Sorta yes, sorta no.
>
> 1. They must indeed be laid out contiguously in memory.
> 2. If you derive a pointer from one of the sub-arrays, you should not
> then try to derive pointers outside that sub-array from it.
>
> So:
>
> int a[10][10];
> int *p = &a[0][0];
> p = (int *) a;
> p[11] = 0; /* fine, writes to the 12th of 100 members */
> p = &a[0][0];
> p[11] = 0; /* bad, oversteps boundaries of a[0] */
>
> -s
> --
> Copyright 2010, all wrongs reversed. Peter Seebach / usenet-nos...@seebs.nethttp://www.seebs.net/log/<-- lawsuits, religion, and funny pictureshttp://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
pemo
pemo
Seebs
>
>> int *p = &a[0][0];
>> p = (int *) a;
I was originally just going to demonstrate the &a[0][0] thing, then
I was going to show the other one, but then I realized that if I
did the "(int *) a" after dreferencing p[12] (aka a[0][12]), that it
would still be undefined behavior because undefined behavior had already
occurred.
Please don't top-post. Quote the material you're responding to, and
put your response under the specific thing you're responding to. Or,
as the .sig goes:
A: Because it breaks the normal flow of communication.
Q: What's wrong with top-posting?
-s
--
Michal Nazarewicz
> Please don't top-post. [...] Or, as the .sig goes:
>
> A: Because it breaks the normal flow of communication.
> Q: What's wrong with top-posting?
Or:
A: Because it breaks the normal flow of communication.
Q: Why is it so bad?
A: Top-posting.
Q: What's the worst thing in Usenet?
--
Best regards, _ _
.o. | Liege of Serenly Enlightened Majesty of o' \,=./ `o
..o | Computer Science, Michal "mina86" Nazarewicz (o o)
ooo +--<mina86*tlen.pl>--<jid:mina86*jabber.org>--ooO--(_)--Ooo--
pemo
On Mar 16, 5:24 pm, Seebs <usenet-nos...@seebs.net> wrote:
> On 2010-03-16, pemo <peet.mor...@gmail.com> wrote:
>
> > Why the initiailser and then the assignment please?
>
> >> int *p = &a[0][0];
> >> p = (int *) a;
>
> I was originally just going to demonstrate the &a[0][0] thing, then
> I was going to show the other one, but then I realized that if I
> did the "(int *) a" after dreferencing p[12] (aka a[0][12]), that it
> would still be undefined behavior because undefined behavior had already
> occurred.
>
> Please don't top-post. Quote the material you're responding to, and
> put your response under the specific thing you're responding to. Or,
> as the .sig goes:
>
> A: Because it breaks the normal flow of communication.
> Q: What's wrong with top-posting?
>
> -s
> --
It's been a while since I've posted: damn it - I deliberately went and
top-posted because I seemed to remember that it *should* be that way
around, rather than the reverse!
Maybe I should have trusted Google's reader's correctness then!
Cheer,
pemo
Andrew Poelstra
>
No, no no no no no no no no. Don't trust Google.
It happens to correct on this point because we (meaning, other
people on Usenet) bitched at them for a few solid years before
they noticed and fixed it.
Johannes Schaub (litb)
> On 2010-03-16, pemo <peet....@gmail.com> wrote:
>> Maybe this was in a nightmare, but I seem to remember reading
>> something that said in C99 multidimensional arrays *need not* be laid
>> out contiguously in memory, i.e., that one should not treat them as a
>> single contiguous blob of memory!
>
>> Was this just a bad dream of mine please??
>
> Sorta yes, sorta no.
>
> 1. They must indeed be laid out contiguously in memory.
> 2. If you derive a pointer from one of the sub-arrays, you should not
> then try to derive pointers outside that sub-array from it.
>
> So:
>
> int a[10][10];
> int *p = &a[0][0];
> p = (int *) a;
> p[11] = 0; /* fine, writes to the 12th of 100 members */
> p = &a[0][0];
> p[11] = 0; /* bad, oversteps boundaries of a[0] */
>
> -s
I must be completely blind, but aren't both cases exactly the same? In fact,
the first may be worse since the cast may yield a different address (int(*)
[10] -> int* - the standard doesn't require the pointer value resulting from
the cast to stay the same, i think). And if it stays the same, it looks like
it does completely the same as the second case: Both are undefined behavior
in C.
What do you say is different here?
Seebs
> Seebs wrote:
>> int a[10][10];
>> int *p = &a[0][0];
(the initializer here is irrelevant).
>> p = (int *) a;
>> p[11] = 0; /* fine, writes to the 12th of 100 members */
>> p = &a[0][0];
>> p[11] = 0; /* bad, oversteps boundaries of a[0] */
> I must be completely blind, but aren't both cases exactly the same?
No.
In one, p is being derived from the address of an object known to contain
at least 100*sizeof(int) bytes of storage, in the other, it's being derived
from the address of an object known to contain at least 10*sizeof(int) bytes
of storage.
> In fact,
> the first may be worse since the cast may yield a different address (int(*)
> [10] -> int* - the standard doesn't require the pointer value resulting from
> the cast to stay the same, i think).
It does. Pointers to the first member of an aggregate must compare equal.
Two pointers compare equal if and only if both are null pointers,
both are pointers to the same object (including a pointer to an
object and a subobject at its beginning) or function, both are
pointers to one past the last element of the same array object, or
one is a pointer to one past the end of one array object and the
other is a pointer to the start of a different array object that
happens to immediately follow the first array object in the address
space.)
> And if it stays the same, it looks like
> it does completely the same as the second case: Both are undefined behavior
> in C.
I don't think so.
> What do you say is different here?
a is an array of 10 arrays of ints. The integers in each array are
necessarily contiguous, and the arrays are necessarily contiguous, so
it's going to point to a region containing 100 integers. If you derive
a pointer from a, it is a pointer into that whole object.
However, each of the sub-objects (a[0], a[1], etcetera) is also an object,
so if you derive a pointer from a[0], it is a pointer only into that
subobject.
The only way they can be in any way different is bounds checking; as
noted above, the standard does guarantee that &(a[0][10]) == &(a[1][0]).
But two pointers can be equal, and not be fully interchangeable, in that
they can have different bounds.
Luca Forlizzi
> a is an array of 10 arrays of ints. The integers in each array are
> necessarily contiguous, and the arrays are necessarily contiguous, so
> it's going to point to a region containing 100 integers. If you derive
> a pointer from a, it is a pointer into that whole object.
>
This conclusion is clear and logical, but is it really deducible from
the standard?
The only sentence in the standard I was able to find to support the
fact that a pointer to an object can be considered to point into the
largest possible array containing the pointed object, is 7.20.3, but
this explicitely refers to objects returned from a memory alloc
function.
On the other hand, the int object p points to is an element of the
array a[0], not of a, which is not an arrat of ints.
Some days ago in a thread about exiting from "double loops" Ben
Bacarisse and Tim Rentsch have the same opinion as you, so I am pretty
sure that there is something in the standard that I do not fully
understand. Could you please enlighten me?
-- Luca Forlizzi
Seebs
> On 17 Mar, 23:01, Seebs <usenet-nos...@seebs.net> wrote:
>> a is an array of 10 arrays of ints. The integers in each array are
>> necessarily contiguous, and the arrays are necessarily contiguous, so
>> it's going to point to a region containing 100 integers. If you derive
>> a pointer from a, it is a pointer into that whole object.
> This conclusion is clear and logical, but is it really deducible from
> the standard?
Yes.
sizeof(<type> [10]) == sizeof(<type>) * 10
There's no room for any padding. The array of 10 ints must have size
precisely 10*sizeof(int). The array of 100 ints must have size
precisely 10*(10*sizeof(int)).
So a is a region of 100*sizeof(int) bytes, while a[0] is a region of
10*sizeof(int) bytes.
Luca Forlizzi
> Yes.
>
> sizeof(<type> [10]) == sizeof(<type>) * 10
>
> There's no room for any padding. The array of 10 ints must have size
> precisely 10*sizeof(int). The array of 100 ints must have size
> precisely 10*(10*sizeof(int)).
>
> So a is a region of 100*sizeof(int) bytes, while a[0] is a region of
> 10*sizeof(int) bytes.
Yes that is clear. I apologise for my bad english, I didn't express my
question well. Let me try again!
According to my knowledge of the standard, the semantics of indexing
is defined in 6.5.6 p. 8
for "a pointer to an element of an array object". It says nothing
about how is the pointer obtained.
So let's take again the example:
int a[10][10];
int *p;
p = (int *) a;
p[11] = 0; /* fine, writes to the 12th of 100 members */
I agree that p points to an integer objects which is the first of a
series of 100 contiguously allocated
integer objects.
But is that series of objects, from the "legal" point of view (i.e.
according to the standard) an array?
Does the standard says that *any* collection of N contigously
allocated objects of type T is an
array of size N of type T ?
The int object pointed by p is indeed an element of an array, but of
a[0]. Can it be at the same time
element of a[0] and of the unnamed array of 100 ints "derived" from
the memory allocated for object a
(which is not an array of 100 ints) ?
IMHO, no, and I don't see why the way p is obtained change the fact
that the object pointed by p is an
element of array a[0]. Therefore the array bound for p should still be
10.
I hope to have clarifyied my reasoning. Which is my mistake?
Luca
Seebs
> According to my knowledge of the standard, the semantics of indexing
> is defined in 6.5.6 p. 8
> for "a pointer to an element of an array object". It says nothing
> about how is the pointer obtained.
> So let's take again the example:
>
> int a[10][10];
> int *p;
> p = (int *) a;
> p[11] = 0; /* fine, writes to the 12th of 100 members */
> I agree that p points to an integer objects which is the first of a
> series of 100 contiguously allocated
> integer objects.
> But is that series of objects, from the "legal" point of view (i.e.
> according to the standard) an array?
It's not an array of integers, but it's an array -- of arrays of integers.
The key is that the object's size is 100*sizeof(int), so pointing inside
it is okay.
> Does the standard says that *any* collection of N contigously
> allocated objects of type T is an
> array of size N of type T ?
No. However, it doesn't have to be.
> The int object pointed by p is indeed an element of an array, but of
> a[0]. Can it be at the same time
> element of a[0] and of the unnamed array of 100 ints "derived" from
> the memory allocated for object a
> (which is not an array of 100 ints) ?
Yes.
> I hope to have clarifyied my reasoning. Which is my mistake?
Bounds checking only allows you to check the bounds of the actual object
you're looking at. If you're looking at a, its bounds are the whole
range from a[0][0] to a[9][9], and anything that is inside that range
is fair game.
Ben Bacarisse
> On 2010-03-21, Luca Forlizzi <luca.f...@gmail.com> wrote:
>> According to my knowledge of the standard, the semantics of indexing
>> is defined in 6.5.6 p. 8
>> for "a pointer to an element of an array object". It says nothing
>> about how is the pointer obtained.
>> So let's take again the example:
>>
>> int a[10][10];
>> int *p;
>> p = (int *) a;
>> p[11] = 0; /* fine, writes to the 12th of 100 members */
>
>> I agree that p points to an integer objects which is the first of a
>> series of 100 contiguously allocated
>> integer objects.
>> But is that series of objects, from the "legal" point of view (i.e.
>> according to the standard) an array?
>
> It's not an array of integers, but it's an array -- of arrays of integers.
> The key is that the object's size is 100*sizeof(int), so pointing inside
> it is okay.
I hope the following clarification helps, because I am not sure we've
got to the bottom of Luca's question. I'm not replying to you to tell
you stuff, I am hanging this post here because this is the place with
the right context.
There are three situations:
int X[10][10];
int *p1 = &X[0][0]; /* or = X[0]; since X[0] gets converted */
int *p2 = (void *)&X[0]; /* or = X; since X gets converted */
int *p3 = (void *)&X;
(I've used void * simply to avoid questions about implementation
defined conversions and I've written the addresses in the most
explicit form I can, without any array to pointer conversions. I've
also used X as the array name because 'a' is confusing in English
text).
I would summarise the majority view as being that p1[10] is an invalid
access and that p3[10] (indeed p3[99]) is valid. Luca's example is
the same as p2 and I think the majority view is that p2[10] is also
fine.
The arguments all revolve around 6.5.6 p8 about adding to a pointer.
That clause defines the result of the addition only when the result is
within the array pointed "into" by the pointer. Specifically: "if the
pointer operand points to an element of an array object, and the array
is large enough...".
"Large enough" can also mean "one past the end" but that pointer can't
be dereferenced and, since array access using []s has an implied
dereference, we can ignore these special "one past the end" pointers
in this discussion.
The array X consists of 11 arrays -- the whole one and 10 sub-arrays.
The central question is what is the array into which the various
p[1-3] pointers point?
p1 points to an element of X[0] so it is natural to deduce the array
over which is ranges is just X[0] and not X as a whole. I don't think
there any support in the standard for the idea that p1 points to an
element of X, at least not formally.
p2 is a converted from a pointer that clearly points to an element of
X (the first one) so here one can reasonably say that the converted
pointer may range of the whole of X.
p3 is interesting. At first sight it seems to fall outside of the
wording altogether. The pointer from which it is converted does not
point to an element of an array -- it points to the single object X.
Here paragraph 7 comes into play:
"For the purposes of these operators, a pointer to an object that is
not an element of an array behaves the same as a pointer to the
first element of an array of length one with the type of the object
as its element type."
So &X is considered (for this purpose) to be a pointer into to the
first element of a one-element array. Thus "the array" referred to in
paragraph 8 is the whole of X.
I hope this helps rather than hinders. If I've made a mistake in
summarising the majority view I will have complicated matters so I
hope I have it straight.
<snip>
--
Ben.
Luca Forlizzi
I redirect to comp.std.c maybe it's more appropiate
> On 2010-03-21, Luca Forlizzi <luca.forli...@gmail.com> wrote:
>
> > According to my knowledge of the standard, the semantics of indexing
> > is defined in 6.5.6 p. 8
> > for "a pointer to an element of an array object". It says nothing
> > about how is the pointer obtained.
> > So let's take again the example:
>
> > int a[10][10];
> > int *p;
> > p = (int *) a;
> > p[11] = 0; /* fine, writes to the 12th of 100 members */
> > I agree that p points to an integer objects which is the first of a
> > series of 100 contiguously allocated
> > integer objects.
> > But is that series of objects, from the "legal" point of view (i.e.
> > according to the standard) an array?
>
> It's not an array of integers, but it's an array -- of arrays of integers.
> The key is that the object's size is 100*sizeof(int), so pointing inside
> it is okay.
I can't deduce this from my reading of the standard. Since, as you
say, the element type of a is not int,
the object pointed by p does not qualify as element of a, although its
adress is inside a. On the other hand, the object pointed by p is an
element of array a[0], therefore we are in the case defined by 6.5.6
p. 8 where
the array is a[0] which has 10 elements.
> > The int object pointed by p is indeed an element of an array, but of
> > a[0]. Can it be at the same time
> > element of a[0] and of the unnamed array of 100 ints "derived" from
> > the memory allocated for object a
> > (which is not an array of 100 ints) ?
>
> Yes.
You have to convince me that this is implied from the standard.
>
> > I hope to have clarifyied my reasoning. Which is my mistake?
>
> Bounds checking only allows you to check the bounds of the actual object
> you're looking at. If you're looking at a, its bounds are the whole
> range from a[0][0] to a[9][9], and anything that is inside that range
> is fair game.
I really would like to share this conclusion.
regards, Luca
Richard Bos
> On 2010-03-20, Luca Forlizzi <luca.f...@gmail.com> wrote:
> > On 17 Mar, 23:01, Seebs <usenet-nos...@seebs.net> wrote:
> >> a is an array of 10 arrays of ints. The integers in each array are
> >> necessarily contiguous, and the arrays are necessarily contiguous, so
> >> it's going to point to a region containing 100 integers. If you derive
> >> a pointer from a, it is a pointer into that whole object.
>
> > This conclusion is clear and logical, but is it really deducible from
> > the standard?
>
> Yes.
>
> sizeof(<type> [10]) == sizeof(<type>) * 10
>
> There's no room for any padding. The array of 10 ints must have size
> precisely 10*sizeof(int). The array of 100 ints must have size
> precisely 10*(10*sizeof(int)).
>
> So a is a region of 100*sizeof(int) bytes, while a[0] is a region of
> 10*sizeof(int) bytes.
Yes, so you have the sizes stitched up neatly. Now consider fat
pointers.
Richard
Keith Thompson
> On 21 Mar, 12:57, Seebs <usenet-nos...@seebs.net> wrote:
>
> I redirect to comp.std.c maybe it's more appropiate
No, you didn't; there was no Followup-To: header in your article.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Luca Forlizzi
> Luca Forlizzi <luca.forli...@gmail.com> writes:
> > On 21 Mar, 12:57, Seebs <usenet-nos...@seebs.net> wrote:
>
> > I redirect to comp.std.c maybe it's more appropiate
>
> No, you didn't; there was no Followup-To: header in your article.
>
ouch... I am a usenet newbe :-)
Do you think it's appropriate to redirect the topic in comp.std.c ?
Luca Forlizzi
> I hope the following clarification helps, because I am not sure we've
> got to the bottom of Luca's question. I'm not replying to you to tell
> you stuff, I am hanging this post here because this is the place with
> the right context.
it does help to me! But I am still not convinced that p2 and p3 can
legally access any int inside X
(see below)
> There are three situations:
>
> int X[10][10];
> int *p1 = &X[0][0]; /* or = X[0]; since X[0] gets converted */
> int *p2 = (void *)&X[0]; /* or = X; since X gets converted */
> int *p3 = (void *)&X;
>
> <snip>
>
> I would summarise the majority view as being that p1[10] is an invalid
> access and that p3[10] (indeed p3[99]) is valid. Luca's example is
> the same as p2 and I think the majority view is that p2[10] is also
> fine.
>
> The arguments all revolve around 6.5.6 p8 about adding to a pointer.
> That clause defines the result of the addition only when the result is
> within the array pointed "into" by the pointer. Specifically: "if the
> pointer operand points to an element of an array object, and the array
> is large enough...".
The problem that I have is not exactly the array size. You informally
say *array pointed into*
but the standard says "pointer operand points to an element of an
array object".
What exactly is an element of an array. In my mind, since X is an
array of arrays, the elements of X are arrays,
so p2 and p3 do not point to element of X (so 6.5.6 p8 does not apply
to them and X).
You (and Peter, too) seem to imply that the int objects that are
elements of the elements of X are also elements
of X (i.e. "being element" is a transitive relation). But I can't find
this in the standard.
Please note that I would love yours to be the right interpretation of
the standard, I find it more
comfortable and close to real usage of the language.
Luca
Luca Forlizzi
sorry in my previous post I mistyped a sentence. Below is the correct
text
>
> The problem that I have is not exactly the array size. You informally
> say *array pointed into*
> but the standard says "pointer operand points to an element of an
> array object".
> What exactly is an element of an array. In my mind, since X is an
> array of arrays, the elements of X are arrays,
> so p2 and p3 do not point to element of X (so 6.5.6 p8 does not apply
> to them and X).
The problem that I have is not exactly the array size. You informally
say *array pointed into* but the standard says "pointer operand points
to an *element* of an
array object". I am not convinced that the objects pointed by p2 and
p3 are elements of X.
What exactly is an element of an array? In my mind, since X is an
Seebs
> I hope the following clarification helps, because I am not sure we've
> got to the bottom of Luca's question. I'm not replying to you to tell
> you stuff, I am hanging this post here because this is the place with
> the right context.
Sounds fine to me. I'm not totally sure I have this right, myself.
> int X[10][10];
> int *p1 = &X[0][0]; /* or = X[0]; since X[0] gets converted */
> int *p2 = (void *)&X[0]; /* or = X; since X gets converted */
> int *p3 = (void *)&X;
> (I've used void * simply to avoid questions about implementation
> defined conversions and I've written the addresses in the most
> explicit form I can, without any array to pointer conversions. I've
> also used X as the array name because 'a' is confusing in English
> text).
Okay.
> I would summarise the majority view as being that p1[10] is an invalid
> access and that p3[10] (indeed p3[99]) is valid. Luca's example is
> the same as p2 and I think the majority view is that p2[10] is also
> fine.
I would agree.
> The array X consists of 11 arrays -- the whole one and 10 sub-arrays.
> The central question is what is the array into which the various
> p[1-3] pointers point?
Good point. This is like those brain-teasers where you see a triangle
subdivided into smaller triangles, and you're supposed to figure out
how many triangles there are.
> p1 points to an element of X[0] so it is natural to deduce the array
> over which is ranges is just X[0] and not X as a whole. I don't think
> there any support in the standard for the idea that p1 points to an
> element of X, at least not formally.
Right.
> p2 is a converted from a pointer that clearly points to an element of
> X (the first one) so here one can reasonably say that the converted
> pointer may range of the whole of X.
Yes. Now, for an illustration of the boundary, consider:
int *p4 = (void *)X[0];
I think that, because "X[0]" decays into "the address of X[0][0]", this
is more like p1 than like p2.
Basically, the "&" jumps you out a level.
int i = X[0][0]; /* not useful as a pointer to anything */
/* = int */
int *q1 = (void *) &X[0][0]; /* a pointer to the contents of X[0] */
/* = pointer to int */
int *q2 = (void *) X[0]; /* a pointer to the contents of X[0] */
/* = array[10] of int, => pointer to int */
int *q3 = (void *) &X[0]; /* a pointer to the contents of X */
/* = pointer to array[10] of int */
int *q4 = (void *) X; /* a pointer to the contents of X */
/* = array[10] of array[10] of int,
=> pointer to array[10] of int */
int *q5 = (void *) &X; /* a pointer to the contents of X */
/* = pointer to array[10] of array[10] of int */
Looking at the types (see the /* = <type> */ comments), you can see
that q1 and q2 have the same type, and q3 and q4 have the same type.
q5's really a different case, but since X itself is not a member
of an array, it's treated as an array[1] of its own type, so everything
still works.
> So &X is considered (for this purpose) to be a pointer into to the
> first element of a one-element array. Thus "the array" referred to in
> paragraph 8 is the whole of X.
Yes! I believe that's the key -- &X is a pointer to a one-element array
of arrays of 10 arrays of 10 integers. So it can be used to point to anything
in any of those 10 arrays of 10 integers.
Seebs
(context)
int X[10][10];
> You (and Peter, too) seem to imply that the int objects that are
> elements of the elements of X are also elements
> of X (i.e. "being element" is a transitive relation). But I can't find
> this in the standard.
It's not immediately obvious, but:
Consider the array object X[1] (not the pointer it decays into the moment
you refer to it in an expression, but the thing that is the operand of
sizeof(X[1]).
Clearly, X[1] is an element of X, so a pointer derived from X can be used
to access X[1].
But what can you do with X[1]? It's an array. You can look at its members.
Basically, you can use a pointer derived from X to look at X[1][5] for the
same reason that you can derive a pointer derived from X[0][0] to iterate
over the individual bytes in the object; once you have access to an object,
you're allowed to access its components.
Think about, as an example:
struct abc { int a, b, c; };
struct abc Y[10] = { { 0 } };
struct abc *p = &Y[0];
++p;
p->a = 1;
In other words: Yes, being an element-of is transitive. If you can access
an aggregate object, you can access its members.
Seebs
> Seebs <usenet...@seebs.net> wrote:
>> sizeof(<type> [10]) == sizeof(<type>) * 10
>>
>> There's no room for any padding. The array of 10 ints must have size
>> precisely 10*sizeof(int). The array of 100 ints must have size
>> precisely 10*(10*sizeof(int)).
>>
>> So a is a region of 100*sizeof(int) bytes, while a[0] is a region of
>> 10*sizeof(int) bytes.
>
> Yes, so you have the sizes stitched up neatly. Now consider fat
> pointers.
The bounds stored in the fat pointers have to match the size of the object,
and casting allows you to view them as different types, as long as you
know for sure what the layout is. Which you do, with arrays.
Ben Bacarisse
> On 21 Mar, 14:17, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>
>> I hope the following clarification helps, because I am not sure we've
>> got to the bottom of Luca's question. I'm not replying to you to tell
>> you stuff, I am hanging this post here because this is the place with
>> the right context.
>
> it does help to me! But I am still not convinced that p2 and p3 can
> legally access any int inside X
> (see below)
>
>> There are three situations:
>>
>> int X[10][10];
>> int *p1 = &X[0][0]; /* or = X[0]; since X[0] gets converted */
>> int *p2 = (void *)&X[0]; /* or = X; since X gets converted */
>> int *p3 = (void *)&X;
>>
>> <snip>
>>
>> I would summarise the majority view as being that p1[10] is an invalid
>> access and that p3[10] (indeed p3[99]) is valid. Luca's example is
>> the same as p2 and I think the majority view is that p2[10] is also
>> fine.
>>
>> The arguments all revolve around 6.5.6 p8 about adding to a pointer.
>> That clause defines the result of the addition only when the result is
>> within the array pointed "into" by the pointer. Specifically: "if the
>> pointer operand points to an element of an array object, and the array
>> is large enough...".
[I have imported a correction from another post (marked with |) into
this paragraph in an attempt to keep everything in one thread.]
> The problem that I have is not exactly the array size. You
> informally say *array pointed into* but the standard says "pointer
> operand points to an element of an array object".
| I am not convinced that the objects pointed by p2 and p3 are
| elements of X.
> What exactly is an element of an array. In my mind, since X is an
> array of arrays, the elements of X are arrays, so p2 and p3 do not
> point to element of X (so 6.5.6 p8 does not apply to them and X).
That's a good point. I don't have any sound chapter an verse to
counter it. What I can do is explain a bit more about the way I read
things.
There is no doubt that &X[0] points to an element of X (the first
sub-array) and so must (void *)&X[0]. (Converting a pointer to void *
does not change what the pointer points to). I would extend that to
the converted int *. In other words, my view would be that p2 is a
pointer to an element of X even though it is not of the natural type
for such a pointer. A similar argument applies to p3 -- it is an
unnatural type for a pointer to one and only element pointer to by
&X.
I fully accept that there is then a leap from this converted pointer
to allowing it to be a "pointer to an element" (of the now converted
type) for the purposes of the pointer arithmetic described in 6.5.6 p8
but it does not seem an unnatural or excessively contrived leap.
> You (and Peter, too) seem to imply that the int objects that are
> elements of the elements of X are also elements
> of X (i.e. "being element" is a transitive relation). But I can't find
> this in the standard.
That's not quite how I see it. I don't think the argument above is
exactly that same as "element of" being transitive. For example, if
the standard included wording that support the idea that an element of
a sub array was an element of the containing array, then p1 would be
able to range over the whole of X. At least, I think that is how I
would then have to read 6.5.6 p8,
> Please note that I would love yours to be the right interpretation of
> the standard, I find it more
> comfortable and close to real usage of the language.
I am not wedded to any particular reading, and your arguments have
made me think again. I'd be happy if "element of" were to be either
defined to be transitive of if that could be deduced from the current
wording. I have no objection to 6.5.6 p8 having a looser meaning
where any pointer into a sub-array can range over the whole array.
I'd be less happy with your very strict reading, though I think I
could live with even that.
BTW, when I say "my reading" and so forth, all I mean is my reading as
coloured by the various arguments on this matter that have happened
here. There is no original interpretation here, just a regurgitation
of those arguments that I've found to be persuasive in the past.
--
Ben.
Seebs
> exactly that same as "element of" being transitive. For example, if
> the standard included wording that support the idea that an element of
> a sub array was an element of the containing array, then p1 would be
> able to range over the whole of X. At least, I think that is how I
> would then have to read 6.5.6 p8,
Ooh, you have a point.
I think the problem is that the *intent* (clearly agreed on by everyone
I've talked to) is that obviously pointers derived from the sub-arrays
can only be used to walk those sub-arrays, while pointers derived from
the big array can be used to walk the whole big array.
It's there to match the intended semantics of bounds checking. Basically,
imagine that you have an array of (array[80] of char) which maps onto the
display for an old greenscreen terminal. Clearly, if you hand someone
a pointer into an 80-character string, you *intend* for it to be a boundary
violation for them to go past the end of that string.
Phil Carmody
> On 2010-03-20, Luca Forlizzi <luca.f...@gmail.com> wrote:
>> On 17 Mar, 23:01, Seebs <usenet-nos...@seebs.net> wrote:
>>> a is an array of 10 arrays of ints. The integers in each array are
>>> necessarily contiguous, and the arrays are necessarily contiguous, so
>>> it's going to point to a region containing 100 integers. If you derive
>>> a pointer from a, it is a pointer into that whole object.
>
>> This conclusion is clear and logical, but is it really deducible from
>> the standard?
>
> Yes.
>
> sizeof(<type> [10]) == sizeof(<type>) * 10
I thought that this was loopholed a few months ago. IIRC, All that is
required explicitly is that (the normative part is to be interpreted
such that):
sizeof(<type>[10])/sizeof(<type>) = 10
where of course division truncates towards zero.
> There's no room for any padding.
less than sizeof(<type>) trailing padding would be permitted, as
the rounding down would make the division in the example yield
the correct count.
Of course, this is bizarre; but I suspect that it's available as a
plugin module for the DS9000.
I'm also sure that within the last 6 months at least one member
of the C standardisation committee has indicated that what you
say was the committee's intention (I'm sure Larry was one).
Phil
--
I find the easiest thing to do is to k/f myself and just troll away
-- David Melville on r.a.s.f1
Ersek, Laszlo
> Seebs <usenet...@seebs.net> writes:
>> On 2010-03-20, Luca Forlizzi <luca.f...@gmail.com> wrote:
>>> On 17 Mar, 23:01, Seebs <usenet-nos...@seebs.net> wrote:
>>>> necessarily contiguous, and the arrays are necessarily contiguous, so
>>>> a pointer from a, it is a pointer into that whole object.
>>
>>> This conclusion is clear and logical, but is it really deducible from
>>> the standard?
>>
>> Yes.
>>
>> sizeof(<type> [10]) == sizeof(<type>) * 10
>
> I thought that this was loopholed a few months ago. IIRC, All that is
> required explicitly is that (the normative part is to be interpreted
> such that):
> sizeof(<type>[10])/sizeof(<type>) = 10
> where of course division truncates towards zero.
>
>> There's no room for any padding.
>
> less than sizeof(<type>) trailing padding would be permitted, as
> the rounding down would make the division in the example yield
> the correct count.
>
> Of course, this is bizarre; but I suspect that it's available as a
> plugin module for the DS9000.
>
> I'm also sure that within the last 6 months at least one member
> of the C standardisation committee has indicated that what you
> say was the committee's intention (I'm sure Larry was one).
X-News: ludens comp.lang.c.moderated:25727
From: "Clive D. W. Feather" <cl...@davros.org>
Subject: Re: [comp.lang.c.moderated] Does "sizeof array" equal "nel * sizeof
Date: Wed, 13 Jan 2010 16:02:02 -0600 (CST)
Message-ID: <clcm-2010...@plethora.net>
X-News: ludens comp.lang.c.moderated:25755
From: "Clive D. W. Feather" <cl...@davros.org>
Subject: Re: [comp.lang.c.moderated] Does "sizeof array" equal "nel * sizeof
Date: Wed, 20 Jan 2010 15:26:17 -0600 (CST)
Message-ID: <clcm-2010...@plethora.net>
I think.
lacos
Phil Carmody
> In article <87ljdkw...@kilospaz.fatphil.org>, Phil Carmody <thefatphi...@yahoo.co.uk> writes:
>> Seebs <usenet...@seebs.net> writes:
>>> sizeof(<type> [10]) == sizeof(<type>) * 10
>> I'm also sure that within the last 6 months at least one member
>> of the C standardisation committee has indicated that what you
>> say was the committee's intention (I'm sure Larry was one).
>
>
> X-News: ludens comp.lang.c.moderated:25727
> From: "Clive D. W. Feather" <cl...@davros.org>
> Subject: Re: [comp.lang.c.moderated] Does "sizeof array" equal "nel * sizeof
> Date: Wed, 13 Jan 2010 16:02:02 -0600 (CST)
> Message-ID: <clcm-2010...@plethora.net>
>
>
> X-News: ludens comp.lang.c.moderated:25755
> From: "Clive D. W. Feather" <cl...@davros.org>
> Subject: Re: [comp.lang.c.moderated] Does "sizeof array" equal "nel * sizeof
> Date: Wed, 20 Jan 2010 15:26:17 -0600 (CST)
> Message-ID: <clcm-2010...@plethora.net>
>
>
> I think.
Thanks for doing the sniffing, that looks like it.
Luca Forlizzi
intent of the standard is
according to your interpretation. I like this because it is then
strictly conforming to
"flatten" a multidimensional array.
On 22 Mar, 00:19, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> I fully accept that there is then a leap from this converted pointer
> [snip]
> That's not quite how I see it. I don't think the argument above is
> exactly that same as "element of" being transitive. For example, if
> the standard included wording that support the idea that an element of
> a sub array was an element of the containing array, then p1 would be
> able to range over the whole of X. At least, I think that is how I
> would then have to read 6.5.6 p8,
>
you are right, it cannot be a transitive relation. If that was the
case there would not be a unique initial element of an array. no no
no. I think that the basic problem is that the intent is that the
validiti of the indexing depends on how the pointer has been
generated, but the wording in 6.5.6 p8 does not say this. It just
refer to a pointer "into" the array, it does not mention how the
pointer has been generated.
I have to say that I would be happier if the next standard could
clarify the intent. English is not my mother language and if I had
just read it without reading also c.l.c. and other newsgroups, I would
have been completely sure of my previous interpretation.
Thanks for your help!
Luca Forlizzi
Your argument suggest me another question:
> There is no doubt that &X[0] points to an element of X (the first
> sub-array) and so must (void *)&X[0]. (Converting a pointer to void *
> does not change what the pointer points to). I would extend that to
> the converted int *. In other words, my view would be that p2 is a
does the standard guarantee that converting (void *)&X[0] to int gives
a pointer to the first of the ints
inside X[0] ? I was only able to find that 6.3.2.3 p7 says that
converting to a character type we have
a pointer to the first byte.
Please note that in the case of the implicit array-to-pointer
conversion this is stated explicitely, and
so is the analogous statement for structs and unions.
The fact that it's not explicit makes me suspect that this is not
guaranteed.
Am I too pedantic? :-)
Barry Schwarz
<luca.f...@gmail.com> wrote:
>On 22 Mar, 00:19, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>
>Your argument suggest me another question:
>
>> There is no doubt that &X[0] points to an element of X (the first
>> sub-array) and so must (void *)&X[0]. �(Converting a pointer to void *
>> does not change what the pointer points to). �I would extend that to
>> the converted int *. �In other words, my view would be that p2 is a
>
>does the standard guarantee that converting (void *)&X[0] to int gives
I assume you meant int* here since converting it to an int will cause
it not to point anywhere.
>a pointer to the first of the ints
>inside X[0] ? I was only able to find that 6.3.2.3 p7 says that
You neglected to tell us what X was since you changed threads but if
it was an N dimensional array of int, then yes.
>converting to a character type we have
>a pointer to the first byte.
>Please note that in the case of the implicit array-to-pointer
>conversion this is stated explicitely, and
>so is the analogous statement for structs and unions.
What implicit conversion are you referring to?
>The fact that it's not explicit makes me suspect that this is not
>guaranteed.
What is not explicit?
>Am I too pedantic? :-)
We won't know till you fill in the holes.
--
Remove del for email
Ben Bacarisse
> On 22 Mar, 00:19, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>
> Your argument suggest me another question:
>
>> There is no doubt that &X[0] points to an element of X (the first
>> sub-array) and so must (void *)&X[0]. (Converting a pointer to void *
>> does not change what the pointer points to). I would extend that to
>> the converted int *. In other words, my view would be that p2 is a
>
> does the standard guarantee that converting (void *)&X[0] to int gives
> a pointer to the first of the ints
> inside X[0] ? I was only able to find that 6.3.2.3 p7 says that
> converting to a character type we have
> a pointer to the first byte.
(1) I would not loose a moment's sleep over it. :-)
(2) Yes, one can probably deduce this from the standard. I'd start
with 6.2.5 ("Types") p27:
"A pointer to void shall have the same representation and alignment
requirements as a pointer to a character type. [...]"
to which is attached a footnote (all together now: "non-normative"):
"The same representation and alignment requirements are meant to
imply interchangeability as arguments to functions, return values
from functions, and members of unions."
> Please note that in the case of the implicit array-to-pointer
> conversion this is stated explicitely, and
> so is the analogous statement for structs and unions.
> The fact that it's not explicit makes me suspect that this is not
> guaranteed.
> Am I too pedantic? :-)
You can't use the above argument for (int *)&X[0], of course but,
again, I wouldn't loose sleep over it.
--
Ben.
Tim Rentsch
> Having read yours and Peter's posts I now fully believe that the
> intent of the standard is
> according to your interpretation. I like this because it is then
> strictly conforming to
> "flatten" a multidimensional array.
>
> [snip]
> I have to say that I would be happier if the next standard could
> clarify the intent. English is not my mother language and if I had
> just read it without reading also c.l.c. and other newsgroups, I would
> have been completely sure of my previous interpretation.
Luca,
Most of what I would have said in this thread has been said
already (comments by Ben Bacarisse are an excellent example),
so I have only a little to add, but I would like to express
those additions.
First, the Standard does not do a good job of clarifying
what is intended here. I have looked and looked for
something that would give some sort of indication for
when accesses are allowed and when they aren't, and there
is precious little to find (or at least that I've found).
As far as I know the only remarks explicitly related to
this general question about multi-dimensional arrays are
non-normative -- I think one is in a footnote and the
other is in a non-normative Annex. And _no_ remarks
anywhere in the Standard (as far as I know) that explicitly
say anything about the specific case of re-interpreting
a multi-dimensional array as a single dimensional array.
Second, the problem is complicated by the Standard using
the word "object" with two related but still very distinct
meanings, namely, one, just as a region of storage, and
two, as _the_ region of storage defined by an identifier
or by a component of that identifier if the top-level
type is an aggregate or union type. To ask a variation
of one of the points brought up in the thread, given the
declaration
int x[100];
how many arrays are there? Hint: the answer is an awful
lot! (Working assumption -- arrays of a given type all
have the same alignment no matter how many elements the
array has. This assumption is not guaranteed by the
Standard but it is true of all implementations that I know
of.) Ready? The answer is there are, at a guess, tens
of thousands of arrays. Just for starters, all the
one-dimensional sub-arrays, such as
*(int (*)[1])x, *(int (*)[2])x, *(int (*)[3])x, ...
*(int (*)[99])x+1, *(int (*)[98])x+2, *(int (*)[97])x+3, ...
... /* you get the idea */
That's about 5000 right there. Now add in all the two-dimensional
sub-arrays, all the three-dimensional sub-arrays, all the four ...
again you get the idea. Each of these different regions of
storage, and also the different dimensional overlays that go
on top of them, can make a different "array object". For example,
the two arrays '*(int (*)[2][5])x' and '*(int (*)[5][2])x' occupy
the same region of storage, and are both two-dimensional, yet are
very different arrays. Which of these thousands of different arrays
count as far as what indexing operations are allowed? The Standard
says almost nothing that elucidates the question.
Given all of this confusion, what are we to conclude?
Speaking for myself, I have concluded two things. One,
this area is one where the Standard is pretty weak in
describing what requirements are intended. It's regrettable
that that's true, but I accept that is probably won't
change much. Two, I think there is a general understanding
"in the community" that what's allowed is determined by
where a pointer value comes from -- where it comes from
in terms of program identifiers if these can be determined
statically, or where the value comes from dynamically if
there is no static analysis available. I believe this
view has even gotten some level of official blessing (I
recall it being discussed in some DR's or something but
I don't have any references), however, whether it has or
not I've decided for myself to take the "communal wisdom"
viewpoint as the official stance for the C language.
(At least, that is, until some later official statement
changes it. :)
> Thanks for your help!
I hope my comments have also helped at least in
explaining why the issue is so murky and why
despite that there is still a pretty strong
consensus about what the Standard "intends" as
requirements for array-reshaping conversions.
Luca Forlizzi
> (1) I would not loose a moment's sleep over it. :-)
agreed :-)
>
> (2) Yes, one can probably deduce this from the standard. I'd start
> with 6.2.5 ("Types") p27:
>
> "A pointer to void shall have the same representation and alignment
> requirements as a pointer to a character type. [...]"
>
> to which is attached a footnote (all together now: "non-normative"):
>
> "The same representation and alignment requirements are meant to
> imply interchangeability as arguments to functions, return values
> from functions, and members of unions."
so this basically mean that converting a pointer p to void* gives a
pointer to the first byte,
just as converting p to unsigned char*, isn't it?
thanks for answering my silly questions!
Luca
Luca Forlizzi
> On Tue, 23 Mar 2010 14:14:03 -0700 (PDT), Luca Forlizzi
> I assume you meant int* here since converting it to an int will cause
> it not to point anywhere.
yes, excuse me
>
> >a pointer to the first of the ints
> >inside X[0] ? I was only able to find that 6.3.2.3 p7 says that
>
> You neglected to tell us what X was since you changed threads but if
> it was an N dimensional array of int, then yes.
yes again
> >converting to a character type we have
> >a pointer to the first byte.
> >Please note that in the case of the implicit array-to-pointer
> >conversion this is stated explicitely, and
> >so is the analogous statement for structs and unions.
>
> What implicit conversion are you referring to?
the convertion described in 6.3.2.1 p.3
> >The fact that it's not explicit makes me suspect that this is not
> >guaranteed.
>
> What is not explicit?
the fact that converting a pointer to an array to the type of an array
element, gives a pointer to the initial element
> We won't know till you fill in the holes.
excuse me for being sloppy.
Anyway, Ben's answer has satisfied my curiosity!
Luca
Luca Forlizzi
wrote:
> Luca,
> I hope my comments have also helped at least in
> explaining why the issue is so murky and why
> despite that there is still a pretty strong
> consensus about what the Standard "intends" as
> requirements for array-reshaping conversions.
yes they have.
I find your conclusions reasonble and covincing.
I will adopt as rule the comminity consensus, unless an official
statement
would adress the issue.
Thanks a lot to all of you for your help
Ben Bacarisse
Not explicitly but it is hard to see what else could be intended.
The trouble is that the standard does not say what a pointer points
to, and it does so for good reason:
extern void *p;
short *sp = p;
int *ip = p;
Provided everything is properly aligned, *sp and *ip refer to
different objects in one sense of the word. In another, they point to
the same object that p pointed to from the start. Tim has expanded on
this in another post, though with reference to the multiple objects in
a single array.
<snip>
--
Ben.
Luca Forlizzi
>
> > so this basically mean that converting a pointer p to void* gives a
> > pointer to the first byte,
> > just as converting p to unsigned char*, isn't it?
>
> Not explicitly but it is hard to see what else could be intended.
ok
>
> The trouble is that the standard does not say what a pointer points
> to, and it does so for good reason:
>
> extern void *p;
> short *sp = p;
> int *ip = p;
>
> Provided everything is properly aligned, *sp and *ip refer to
> different objects in one sense of the word. In another, they point to
> the same object that p pointed to from the start. Tim has expanded on
> this in another post, though with reference to the multiple objects in
> a single array.
I see. It is important to keep in mind this ambiguity in the standard,
thanks
for pointing it out.
I have no more questions for now, thanks a lot!
Luca
David Thompson
> On 2010-03-16, pemo <peet....@gmail.com> wrote:
> > Maybe this was in a nightmare, but I seem to remember reading
> > something that said in C99 multidimensional arrays *need not* be laid
> > out contiguously in memory, i.e., that one should not treat them as a
> > single contiguous blob of memory!
>
> > Was this just a bad dream of mine please??
>
> Sorta yes, sorta no.
>
> 1. They must indeed be laid out contiguously in memory.
> 2. If you derive a pointer from one of the sub-arrays, you should not
> then try to derive pointers outside that sub-array from it.
>
And it's not clear if you meant this to be important to your question,
but this is not new in C99 -- the same was true in C89. Before that,
you always had contiguity (back to 'prehistory' in dmr's terms)
and de facto usually had 'all pointer arithmetic works' based on
the B heritage of a single flat address-space.