Re: contiguity of arrays

From: Keith Thompson (kst-u_at_mib.org)
Date: 10/19/04 

Date: Tue, 19 Oct 2004 20:53:04 GMT

Dan.Pop@cern.ch (Dan Pop) writes:
[...]
> Nope. There is nothing magic about dynamically allocated memory. The
> fact that the block of memory allocated by malloc is suitable to store
> any C object that will fit in it is a direct consequence of another
> property of that block, that is explicitly guaranteed by the standard:
> the memory block is correctly aligned for any C object (whether it fits
> inside or not).

Hmm. I'm beginning to think you're right.

C99 7.20.3p1 says:

    The pointer returned if the allocation succeeds is suitably
    aligned so that it may be assigned to a pointer to any type of
    object and then used to access such an object or an array of such
    objects in the space allocated (until the space is explicitly
    deallocated).

The most obvious reading of this is, as Dan says, that the allocated
space can be used for any type of objects *because* it's suitably
aligned, not because of any additional magic. (Of course, there's an
additional requirement that the space has to allow read/write access.)

The counterargument is that a bounds-checking fat-pointer
implementation, given

    int arr[2][2];
    int *ptr = &arr[0][0];

could disallow ptr[3] because the relevant array of int is only 2
elements long, but 7.20.3p1 seems to imply that the alignment and size
of the object arr are enough to make ptr[3] ok.

The language *could* have been consistently defined in a way that
makes evaluating ptr[3] invoke undefined behavior (though most
implementations would still allow it with the obvious semantics by
taking the shortcut of not storing bounds information with pointers).
It would be a good idea, IMHO, for the standard to state this more
explicitly, one way or the other. Aliasing a multidimensional array
as a one-dimensional array is probably common enough that there should
be a clearer statement of whether it's legal. Having to infer it from
a somewhat vague statement describing the semantics of the *alloc()
functions is unsatisfying.

Hmm. What does this say about the "struct hack"?

[...]

>>doesn't make it an array. On many compilers,
>>
>> int a,b,c;
>>
>>will result three contiguous locations in memory being allocated as
>>ints. That doesn't create an array.
>
> This is true: each object lives in its own address space. However, make
> them part of a larger object (thus having them in the same address space)
> and you have an array, as in my example above.

But it's possible to detect whether a, b, and c happen to be
contiguous; this is specifically mentioned in C99 6.5.9p6, discussing
equality operators on pointers. So one could argue that this program:

#include <stdio.h>

int main(void)
{
    int a, b, c;
    int *ptr;
    a = c = 12345;

    if (&a + 1 == &b && &b + 1 == &c) {
        ptr = &a;
        printf("ptr[2] = %d\n", ptr[2]);
    }
    else if (&c + 1 == &b && &b + 1 == &a) {
        ptr = &c;
        printf("ptr[2] = %d\n", ptr[2]);
    }
    else {
        printf("The objects are not contiguous\n");
    }

    return 0;
}

will print either "ptr[2] = 12345" or "The objects are not
contiguous", but in this case I think a bounds-checking implementation
can put its foot down and trap on the evaluation of ptr[2]. (I don't
have chapter and verse for this.) 

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center             <*>  <http://users.sdsc.edu/~kst>
We must do something.  This is something.  Therefore, we must do this.

Relevant Pages

  • Re: Prime Numbers
    ... /*This code finally compiles as a 'c' code ... One more question....if i don't free up the memory allocated at the end ... it would appear that we are best served by an array ... prime numbers can be represented by an unsigned long int. ...
    (comp.lang.c)
  • Re: Java Indexing- Historical question
    ... And when the array is of primitives there should be a dramatic benefit in memory usage as well. ... RestrictedRangeIntegerKeyedMapif you prefer) implements Mapthat only accepted keys in a given range, and stored its elements in an array. ... public ArrayMap(int base, int size) { ...
    (comp.lang.java.programmer)
  • Re: memory and speed
    ... but only handles int to save resource/memory ... The size of the IntVector could grow very big, such as 50000, ... Please comment my code regarding the speed and memory usage, ... Instead of keeping all the values in one array whose ...
    (comp.lang.java.programmer)
  • Re: Standard integer types vs types
    ... Not all integers count things in memory. ... I could simply replace that array with a switch statement with no ... an int to temporarily hold the value of errno when I must preserve it ...
    (comp.lang.c)
  • Re: Struct with fixed-length array member - is it possible?
    ... > int V1; ... > THE SAME MEMORY LAYOUT as the C structure. ... > block and all data, including the array, should be placed in this block. ... > public struct XYZ ...
    (microsoft.public.dotnet.framework)
Loading