offset 1 list indexing

[Michael Press]

I want to index into a list using offset one indexing.
The obvious thing to do is make a pointer that points
one element before the list.

void work_on_stuff(int *offset0, int length)
{
int offset1 = offset0 - 1;

for(idx = 1; idx <= length; idx++)
{
... offset1[idx] ...
}
}

Is this likely to fail? Possible to fail?
Very unlikely to fail? Not guaranteed by the standard?

 

[Malcolm McLean]

I want to index into a list using offset one indexing.
The obvious thing to do is make a pointer that points
one element before the list.

void work_on_stuff(int *offset0, int length)
{
    int offset1 = offset0 - 1;

    for(idx = 1; idx <= length; idx++)
    {
         ... offset1[idx] ...
    }

}

Is this likely to fail? Possible to fail?
Very unlikely to fail? Not guaranteed by the standard?

Moderately unlikely to fail. (I presume offset1 is an int * and this
is just a typo).

offset0 is a pointer to a valid chunk of memory. offset1 points to an
invalid chunk of memory before it. It may be occupied by another
variable, or it might be used for something else. The most likely
problem is that you have segmented memory and offset0 happens to be at
the start of a segment. offset1 might then turn into a wild pointer.
However a really sophisticated compiler with bounds checking might
trap offset1 as an illegal pointer. The standard makes no guarantees
that even storing offset0 - 1 will do what you intend. You're unlikely
to be running on either type of system, however.

 

[Nobody]

I want to index into a list using offset one indexing.
The obvious thing to do is make a pointer that points
one element before the list.

Is this likely to fail?
No.

Possible to fail?
Yes.

Very unlikely to fail?

Depends upon the platform. On a typical flat-memory architecture, it's
unlikely to fail, although I suppose that it could fail if the function is
inlined and the compiler is being especially clever.

Not guaranteed by the standard?

AFAICT, it's okay by the standard so long as offset0 actually points at
least one element into an array. If it points to the first element of an
array, the behaviour is undefined.

Whether or not it works practice comes down to whether the architecture
cares about referencing invalid memory locations rather than actually
accessing them, e.g. segmented memory, trap representations, etc.

 

[Tim Rentsch]

I want to index into a list using offset one indexing.
The obvious thing to do is make a pointer that points
one element before the list.

void work_on_stuff(int *offset0, int length)
{
int offset1 = offset0 - 1;

for(idx = 1; idx <= length; idx++)
{
... offset1[idx] ...
}
}

Is this likely to fail? Possible to fail?
Very unlikely to fail? Not guaranteed by the standard?

(Assuming 'offset0' actually points to the start of an array
rather than somewhere further on

Not guaranteed by the Standard, and a bad idea even though
currently it probably works in many (most?) compilers.

As compilers get more aggressive at code improvement, code
like this with undefined behavior gets more likely to cross
over into the compiler equivalent of the Neutral Zone. If
and when that happens, most likely one of two things will
result: one, the optimizer won't realize its assumptions
have been violated, and bogus code will be generated; or
two, the optimizer _will_ realize its assumptions have been
violated, but will fall back to an ultra-conservative
position for code generation, preserving correctness but
sacrificing performance.

Neither of these possibilities is really good, but what's
worse is that they might start happening any time there is a
switch to a new compiler (or a different choice of compiler
options); worse still, unless you are very careful you will
start to get bad results before realizing what has happened.
There's an old Polish proverb that says, Even if you are the
person who buried all the land mines, walking through a
minefield is no fun.


(TIA: "an old Polish proverb" isn't really a Polish
proverb - it's meant to be humorous for the cognoscenti.)

 

[jacob navia]

Le 15/06/11 06:02, Michael Press a écrit :

I want to index into a list using offset one indexing.
The obvious thing to do is make a pointer that points
one element before the list.

void work_on_stuff(int *offset0, int length)
{
int offset1 = offset0 - 1;

for(idx = 1; idx<= length; idx++)
{
... offset1[idx] ...
}
}

Is this likely to fail? Possible to fail?
Very unlikely to fail? Not guaranteed by the standard?

Another evident way is to leave element zero unused and avoid
all problems... Why is that impossible?

 

[Mark Bluemel]

I want to index into a list using offset one indexing.

Why?

 

[gwowen]

Another evident way is to leave element zero unused and avoid
all problems...

.... as long as you remember to make all your arrays one-element-too-
large, to avoid falling of the end.

 

[Eric Sosman]

I want to index into a list using offset one indexing.
The obvious thing to do is make a pointer that points
one element before the list.
[...]

This is Question 6.17 on the comp.lang.c Frequently Asked
Questions (FAQ) page at <http://www.c-faq.com/>.

 

[Shao Miller]

I want to index into a list using offset one indexing.
The obvious thing to do is make a pointer that points
one element before the list.

void work_on_stuff(int *offset0, int length)
{
int offset1 = offset0 - 1;

for(idx = 1; idx<= length; idx++)
{
... offset1[idx] ...
}
}

Is this likely to fail? Possible to fail?
Very unlikely to fail? Not guaranteed by the standard?

How about:

void work_on_stuff(int * array, int length) {
enum {start_pos = 1};
int idx;

for(idx = start_pos; idx <= length; ++idx) {
#define idx (idx - start_pos)
/* Work with array[idx] */
;
#undef idx
}
}

? Have a pleasant day.

 

[Malcolm McLean]

Why?

Many language use 1-based arrays. So do mathematicians.

If you've ever tried fiddling with code written half in Fortran and
half in C you'll realise that sometimes 1-based array indexing can be
tempting.

 

[Joe Pfeiffer]

Many language use 1-based arrays. So do mathematicians.

If you've ever tried fiddling with code written half in Fortran and
half in C you'll realise that sometimes 1-based array indexing can be
tempting.

Giving new life to the old saying, "he can write FORTRAN in any
language".

 

[Keith Thompson]

Giving new life to the old saying, "he can write FORTRAN in any
language".

If I recall correctly, the book "Numerical Recipes in C" uses this trick
to mimic the Fortran versions of the algorithms.

 

[Michael Press]

Why?

Why not? But to humor you: heaps.

 

[Michael Press]

Many language use 1-based arrays. So do mathematicians.

If you've ever tried fiddling with code written half in Fortran and
half in C you'll realise that sometimes 1-based array indexing can be
tempting.

Yes, but when translating Fortran offset-1 code
to C, going to offset-0 loops is a big win. I
have done it, and the C code looks much better.
It becomes obvious in cascaded loops---many fewer,
or no 1's subtracted from array indices.

It is in heaps that offset-1 arrays are neater.

 

[Michael Press]

I want to index into a list using offset one indexing.
The obvious thing to do is make a pointer that points
one element before the list.

void work_on_stuff(int *offset0, int length)
{
int offset1 = offset0 - 1;

for(idx = 1; idx<= length; idx++)
{
... offset1[idx] ...
}
}

Is this likely to fail? Possible to fail?
Very unlikely to fail? Not guaranteed by the standard?

How about:

void work_on_stuff(int * array, int length) {
enum {start_pos = 1};
int idx;

for(idx = start_pos; idx <= length; ++idx) {
#define idx (idx - start_pos)
/* Work with array[idx] */
;
#undef idx
}
}

? Have a pleasant day.

Yes, thanks.

 

[James Kuyper]

If I recall correctly, the book "Numerical Recipes in C" uses this trick
to mimic the Fortran versions of the algorithms.

Yes. I've converted several of them to more idiomatic C; it's quite a pain.

 

[Eric Sosman]

Why not? But to humor you: heaps.

A few months ago, I offered heaps as an example of how some
programmers couldn't do simple index transformations, and were
unable to write zero-based implementations.

Somewhat to my dismay, a few "programmers" in this group did
in fact maintain that it was "too difficult" or "too confusing" or
"too unnatural" to implement heaps in zero-based arrays.

Ye. Flipping. Gods.

"Programmers" who can't do simple arithmetic.

Ye. Flipping. Gods.

 

[Michael Press]

A few months ago, I offered heaps as an example of how some
programmers couldn't do simple index transformations, and were
unable to write zero-based implementations.

Somewhat to my dismay, a few "programmers" in this group did
in fact maintain that it was "too difficult" or "too confusing" or
"too unnatural" to implement heaps in zero-based arrays.

Ye. Flipping. Gods.

"Programmers" who can't do simple arithmetic.

Ye. Flipping. Gods.

You've gone off the deep end. Get a grip;
or else tell me straight on I do not know
how to do simple arithmetic.

 

[Joseph Huber]

Giving new life to the old saying, "he can write FORTRAN in any
language".

After 30 years of Fortran77, and 20 years of Fortran90+ there is no such
thing as 1-based array indexing in Fortran.
It is only the DEFAULT lower bound 1 if nothing is specified in the
declaration:
integer array(0:N)
integer array(-10:N)
integer array(N) is equivalent integer array(1:N)

It's only C being inflexible!

 

[Eric Sosman]

You've gone off the deep end. Get a grip;
or else tell me straight on I do not know
how to do simple arithmetic.

Were you the person in that old thread who maintained that
heaps couldn't/wouldn't/shouldn't be implemented with anything
other than 1-based arrays? I've forgotten. But it's clear that
no important property of a heap depends on the raw numerical
values of the array indices: As long as you can compute the child
indices from the parent's index and vice versa, you can implement
a heap in an N-based array.

And converting between a one-based index and an N-based
index *is* simple arithmetic.