On 09 Jul 2003 13:32:48 -0700, Bradford Chamberlain
<br**@cs.washin gton.edu> wrote:
I work a lot with multidimensiona l arrays of dynamic size in C,
implementing them using a single-dimensional C array and the
appropriate multipliers and offsets to index into it appropriately. I
tend to iterate over subsets of these arrays by walking a pointer and
an offset per dimension across their dimensions. I've found that this
tends to result in more performance in a portable manner than doing
explicit indexing calculations and hoping that the compiler hoists
invariant expressions out of the loops.
For example, rather than doing something like:
{
for (i=ilo; i<ihi; i+=istr) {
for (j=jlo; j<jhil j+=jstr) {
... a[(i-ailo)*imult + (j-ajlo)*jmult] ...
}
}
}
I would tend to do:
{
double* aptr = ...;
const int abumpj = ...;
const int abumpi = ...;
for (i=ilo; i<ihi; i+=istr) {
for (j=jlo; j<jhil j+=jstr) {
... *aptr ...
aptr += abumpj;
}
aptr += abumpi;
}
}
My question is motivated by the following desire: If I have an array
of structures, I'd like to be able to walk around *a single field*
within the array in a similar manner. For example, given the
structure:
struct _mystruct {
short x;
double y;
char z;
}
I would like the ability to walk through the "y" fields of the array
using a pointer and offsets.
I've been able to achieve this using a char* pointer as follows:
{
char* xptr = ...; /* point to y field of the initial element */
const int xbumpj = ...; /* express in bytes rather than */
const int xbumpi = ...; /* sizeof(doubles) */
for (i=ilo; i<ihi; i+=istr) {
for (j=jlo; j<jhil j+=jstr) {
... *((double*)xptr ) ...
xptr += xbumpj;
}
xptr += xbumpi;
}
}
I'd really prefer to eliminate the reliance on char* pointers and
pointer casting, however. In particular, I'd like to make xptr a
double*.
My question is therefore the following: does C have any requirements
on structure layout that would ensure that walking from field to field
within an array of structures will be evenly divisible by sizeof()
that field's type?
If not, it seems like my hope is in vain because the additive offsets
will be in terms of sizeof(<field type>) rather than bytes (or I will
have to cast my pointer back to char* before adding a generic offset
to it).
If so, I'm off and running. However, it's hard for me to believe that
C would ensure such rules on padding, which is why I ask.
The only other approach I can think of is to walk a structure pointer
over my array's elements and then dereference the pointer to access
the field. I guess I've avoided this approach simply due to the fact
that it seems more expensive (due to the field offset calculation
involved).
Does anyone have any other suggstions for how I might write such code
without relying on char* pointers?
If you have a struct STRUCT that contains a member (either scalar or
aggregate) of type TYPE and if the alignment for TYPE is the same as
its size (e.g., a double is of size 8 and must be aligned on an 8-byte
boundary), then sizeof(struct STRUCT) is guaranteed to be a multiple
of sizeof(TYPE). Consider
struct STRUCT{
...
TYPE member; /* TYPE could be double to match you example */
...
}
struct STRUCT mystruct[2];
intptr_t is0, is1, im0, im1;
is0 = (intptr_t)&myst ruct[0];
is1 = (intptr_t)&myst ruct[1];
im0 = (intptr_t)&myst ruct[0].member;
im1 = (intptr_t)&myst ruct[1].member;
is1-is0 is the number of characters between the start of
successive elements of the array which is, by definition,
sizeof(struct STRUCT).
im0-is0 is the number of characters from the start of the struct
to the start of member which is, by definition, offsetof(...).
im1-is1 is the same.
im0 == is0 + offsetof(...).
im1 == is1 + offsetof(...).
im1-im0 == is1 + offsetof(...) - is0 - offsetof(...)
== is1-is0
== sizeof(struct STRUCT)
im0 is a multiple of sizeof(TYPE) and can be represented as
k0*sizeof(TYPE) for some integer k0.
Similarly, im1 can be represented as k1*sizeof(TYPE) .
im1-im0 == (k1-k0)*sizeof(TYPE ) == sizeof(struct STRUCT).
(k1-k0) == sizeof(struct STRUCT)/sizeof(TYPE) which is the ratio
of two constants and therefore constant.
Consequently, if you want to step through a particular member for each
element of an array of struct, you can compute the quotient once as
part of program initialization and use it as the increment for your
pointer arithmetic, something like:
TYPE *ptr;
int dim, ratio;
...
ratio = sizeof(struct STRUCT) / sizeof(TYPE);
...
for (dim=0, ptr=&mystruct[0].member;
dim < max_dimension_o f_array;
dim++; ptr+=ratio){
...
}
This will not work if TYPE's alignment is different from its size.
For example, a double has size 8 but alignment 4. Then struct x{int
i1; double d1;} could easily have size 12 which is not a multiple of
8.
Unfortunately, I know of no portable way to test a type's alignment
requirement.
<<Remove the del for email>>
