contiguity of arrays

[Wojtek Lerch]

int the_array[2][2];

I'm considering the_array as a single object,
which is four times the size of int and also aligned for type int.

Yes, that's what it is.

I would figure that I could increment a pointer to int
through any object that was aligned for type int and big enough.

You can on most implementations, but the standard doesn't guarantee that.
The range of values you're allowed to add to a pointer is defined in terms
of the array whose element the pointer points to, not in terms of the size
of the whole object that that array belongs to. If you could add three to
the_array[0], the result would point to the_array[1][1], but you can't.

 

[pete]

You can on most implementations,
but the standard doesn't guarantee that.

Well, that's the point.
Thank you and everybody else for straigtening me out on this matter.

Regarding:
http://groups.google.com/groups?&[email protected]

It's time to remove wordset.c from my archive of C programs,
isn't it?

 

[pete]

David Hopwood wrote:

... which is simply wrong if objects don't have types.
Not to mention sheer sloppiness such as "manipulation of objects
whose identifiers have external
linkage" in 5.1.1.1. Since when does an object have an identifier?

The type of an object is the same as the identifier used to access it.

If char_ob is the identifier used to declare an object of type char,

char char_ob;

.... then *(unsigned char*)&char_ob identifies the same object,
as an object of type unsigned char.


N869
6.2.5 Types
[#1] The meaning of a value stored in an object or returned
by a function is determined by the type of the expression
used to access it. (An identifier declared to be an object
is the simplest such expression; the type is specified in
the declaration of the identifier.) Types are partitioned
into object types (types that describe objects), function
types (types that describe functions), and incomplete types
(types that describe objects but lack information needed to
determine their sizes).

 

[Douglas A. Gwyn]

... If you could add three to
the_array[0], the result would point to the_array[1][1], but you can't.

Although in practice, except for certain "debugging" implementations
that take extra pains to enforce bounds checking, it will happen to
work anyway, because 3 is much smaller than the available range of
an offset field. The issue becomes much clearer for something like
int a[4][32766]; // assume 16-bit offset field and see what happens

 

[Douglas A. Gwyn]

The type of an object is the same as the identifier used to access it.

No. Change "identifier" to "expression" and you will be much
nearer to correct.

For the case where "a" identifies an object via the declaration
int a[2][3]; a[0] denotes another related object having type
"array of length 3 of int". The length is part of the type.

 

[David Hopwood]

pete wrote:
....


Citation, please? Those are NOT the restrictions specified in the
section describing pointer arithmetic. It is quite specific: there must
be an array of the pointed-at type, containing the pointed-at object.

There *is* an array of the pointed-at type, containing the pointed-at
object. See the definitions of "array type" and "array of T" in
C99 6.2.5 #20.

The rule describing where p+n points at makes no sense if the array that
it refers to is one whose element type is different from the type of *p.

Not a problem in the case under discussion.

 

[James Kuyper]

David Hopwood wrote:
....

There *is* an array of the pointed-at type, containing the pointed-at
object.

Where? "aligned for type int and big enough" doesn't constitute an
array. For static or automatically allocated memory, you need an
explicit declaration to make it an array. For dynamically allocated
memory, the most recent write to the memory must have been through an
lvalue of a compatible type, to make it an array.

See the definitions of "array type" and "array of T" in
C99 6.2.5 #20.

Those definitions say that "An array type describes a contiguously
allocated non-empty set of objects with a particular member object
type". It does not say that every piece of memory that happens to fits
that description is an array. Every type that describes such a piece of
memory is an array type, but that doesn't mean that every piece of
memory that can be described that way can be used as an array.

 

[Douglas A. Gwyn]

... It does not say that every piece of memory that happens to fits
that description is an array.

Exactly right. There is a tendency for people to treat
descriptions as "macros" and forget that they occur in a
context.

 

[Wojtek Lerch]

... "aligned for type int and big enough" doesn't constitute an array. For
static or automatically allocated memory, you need an explicit declaration
to make it an array. For dynamically allocated memory, the most recent
write to the memory must have been through an lvalue of a compatible type,
to make it an array.

Are you saying that when 6.5.6p8 says "an array object", it's referring to
the effective type of the object? I don't think so. It is OK to do pointer
math on pointers to an allocated object before it has an effective type, or
when its effective type is about to change, isn't it?

void *ptr = malloc( sizeof(long) * sizeof(short) * 3 );
long *lptr = ptr;
long *lp2 = lptr+2;
*lp2 = 1;
short *sptr = ptr;
short *sp2 = sptr+2;
*sp2 = 2;

 

[James Kuyper]

Are you saying that when 6.5.6p8 says "an array object", it's referring to
the effective type of the object? I don't think so. It is OK to do pointer
math on pointers to an allocated object before it has an effective type, or
when its effective type is about to change, isn't it?

Yes, I misspoke. The write that gives a piece of dynamically allocated
memory an effective type is also legal.

 

[Wojtek Lerch]

Yes, I misspoke. The write that gives a piece of dynamically allocated
memory an effective type is also legal.

But my point was about pointer math, not about writing. No matter what
types you have used to write to your allocated object (if any), it is
always OK to take a pointer to the object, convert it to a pointer to
some arbitrary object type, and add integers to it, as long as you're
not trying to reach beyond the allocated size. The validity of
arithmetic on pointers that point into an allocated object does not
depend on the effective type the object may have at the moment.

 

[James Kuyper]

But my point was about pointer math, not about writing. No matter what
types you have used to write to your allocated object (if any), it is
always OK to take a pointer to the object, convert it to a pointer to
some arbitrary object type, and add integers to it, as long as you're
not trying to reach beyond the allocated size. The validity of
arithmetic on pointers that point into an allocated object does not
depend on the effective type the object may have at the moment.

I would agree. You can even mix types:

void *pv = malloc(sizeof(int)*sizeof(double));

if(pv)
{
int *pi = pv;
double *pd = pv;

pi[0] = 1;
pd[sizeof(int)/sizeof(double)+1] = 2.0;
}

But that only works for dynamically allocated memory. And even for such
memory, if we have:

int (*arr)[3] = pv;
pi = arr[0];

It's true that arr[0] points at the same location as (int*)pv, but
because of the declaration of 'arr', arr[0] is allowed to be tagged with
an upper limit that will cause the expression p[5] to abort() your
program. (int*)pv, on the other hand, could only be tagged with an upper
limit that matched the dynamically allocated size of the entire block of
memory.

 

[David Hopwood]

David Hopwood wrote:
....


Where? "aligned for type int and big enough" doesn't constitute an
array. For static or automatically allocated memory, you need an
explicit declaration to make it an array. For dynamically allocated
memory, the most recent write to the memory must have been through an
lvalue of a compatible type, to make it an array.


Those definitions say that "An array type describes a contiguously
allocated non-empty set of objects with a particular member object
type". It does not say that every piece of memory that happens to fits
that description is an array.

Since it's a *definition* of "array type" and "array of T", that's
effectively what it does say.

> Every type that describes such a piece of
memory is an array type, but that doesn't mean that every piece of
memory that can be described that way can be used as an array.

For that to be the case, there would have to be text that explicitly
excludes some "contiguously allocated non-empty sets of objects with
a particular member object type" from being arrays. I can't see any
such text.

 

[James Kuyper]

Both subscription ("[]") and indirection ("*") operators are defined for
pointers, but not for arrays. With a pointer it's possible to determine how
a pointed object large is, but it's impossible to determine what number of
the elements can be legally pointed. That is, the abstract machine can never

I think you're misusing the concept of the "abstract machine". The
abstract machine must behave in a certain way for code with
well-defined behavior; it has no restrictions on how it should behave
with regard to code with undefined behavior. When the standard leaves
behavior undefined, that generally means that it has different
behavior on different implementations. When the behavior is undefined,
it might include formatting the hard disk; the fact that the abstract
machine provides no reason why the hard disk might be formatted,
doesn't mean that a conforming implementation is prohibited from
formatting the hard disk.

It seems to me to be quite feasible for an implementation to arrange
for pointers to carry information inside them which allows an
implementation to impose range validity checks. The fact that the
abstract machine has no such mechanism doesn't make such an
implementation non-conforming. If the behavior is undefined, because
an array bound has been violated, then the implementation is free to
abort() the program, regardless of whether or not the abstract machine
has any reason for aborting it.

 

[James Kuyper]

The original example, well upthread, was ..

int a[2][2] = {{1,2},{3,4}};

.. which declares, defines and initializes a. Do we all agree that there are four int's there? Are they contiguous in memory at ascending addresses? Yes, they are.

void *v = a;
int *b = v;

Does anyone doubt that b[3] == 4 ? Are any rules broken? No. The object

Yes, and Yes.

 

[Wojtek Lerch]

For that to be the case, there would have to be text that explicitly
excludes some "contiguously allocated non-empty sets of objects with
a particular member object type" from being arrays. I can't see any
such text.

I presume that this makes "struct { int a, b, c; }" an array type on most
implementations?

 

[James Kuyper]

I just don't understand what an array has to do
with incrementing a pointer through an object.

The standard defines the meaning of pointer addition in terms of
arrays. If there's no array of the pointed-at type containing both the
pointed-at object and the object that would be pointed at after
addition, then you can't do it legally (I'm simplifying the wording by
ignoring the one-past-the-end case, but that doesn't affect my main
point).

You might want to argue for a more general definition, but that's the
one we've got right now.

 

[David Hopwood]

I presume that this makes "struct { int a, b, c; }" an array type on most
implementations?

If there is no padding between the members, then yes, according to 6.2.5 #20
it is an array type as well as a structure type.

 

[pete]

int the_array[2][2];
int *b = (int*)&the_array; ...
(Another issue is whether
b is actually guaranteed to point to an object.

When the standard says that I can convert one pointer type
type to another, it only cautions about alignment and size.
When the standard says that I can do something,
I take it to mean that that code is defined.

The standard never says what the result of the conversion is,'
or that you can dereference it. It could be a special value that
doesn't point to any
object but magically produces the right pointer
when converted back to the original type.

How do you figure it would convert back to the original value?

It would be nice to have a guarantee that (int*)&the_array
has the same value as (int*)(void*)&the_array, but as far I can tell,
there's no such guarantee in the standard.

Even worse, I can't find any words in the standard that forbid the
conversion to produce a completely bogus value that is never correctly
aligned, making the entire conversion undefined. Can you?

I can't even find any words that define conversion of pointers.

N869
6.3 Conversions
[#1] Doesn't say much
[#2] "compatible types" doesn't really apply
to using a cast to convert one pointer to
another with less strict alignment requirements.

 

[Thomas Stegen]

Wojtek Lerch wrote:


If there is no padding between the members, then yes, according to 6.2.5
#20
it is an array type as well as a structure type.

This seems to be an implementation dependent detail though. Relying on
it will make not a strictly conforming program make.

So it seems to me that according to the abstract machine, it is not an
array.