pointer-in-array test

[Ike Naar]

Hi,

Asking your advice on the following subject:

Suppose I want to find out whether a given pointer (say, p) of type *T
points to an element of a given array (say, a) of type T[max].
A way to achieve this would be a linear search through the array:

int ptrInArrSafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
int j=0;
while (j!=max && a+j!=p) ++j;
return j!=max;
}

Obviously, this algorithm is terribly slow for large max.

A more efficient algorithm is

int ptrInArrUnsafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
int j=p-a; /* possibly undefined */
return 0<=j && j<max && a+j==p;
}

If p points to an element of a[max], j will be a valid index and
the return expression will evaluate to true.
If p does not point to an element of a[max], the pointer subtraction may
invoke undefined behaviour; garbage will be stored in j, and at least one
of the conjuncts of the return expression will evaluate to false.

Apart from storing garbage in j, the pointer subtraction could, in theory,
crash the system, re-format the floppy disk or wake up nasal daemons,
but this has not happened so far on any platform with any compiler
(tried several).

My question is, do you experts in this group see any real problem with
the second algorithm? Alternatively, would there be a faster algorithm
than the first one, that does not invoke undefined behaviour?

Thanks in advance,
Ike

[Martin Dickopp]

Bernhard Holzmayer <ho****************@deadspam.com> writes:

Christian Bau wrote:

In article <11****************@holzmayer.ifr.rt>,
Bernhard Holzmayer <ho****************@deadspam.com> wrote:

Sorry,
pardon me for not checking my code intensively enough.
I just checked with a 'gcc -pedantic' which didn't throw an error
:(

What about this solution:
int ptrInArrSafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
long px = (long)p;
long ax = (long)a;
if (px<ax) return 0; /*out*/
if (px> (long)&a[max-1]) return 0; /* out */
if ( (px-ax) % sizeof(T)) return 0; /* not at element
start*/
return 1; /* in and on element start */
}

compiles, links, runs without problems with my gcc.
And, as far as I remember, it's legal, to compare pointers after
conversion to long.

It just isn't guaranteed to produce any meaningful result.

Why. Please give arguments.

6.3.2.3#6:
| Any pointer type may be converted to an integer type. Except as
| previously specified, the result is implementation-defined. If the
| result cannot be represented in the integer type, the behavior is
| undefined. The result need not be in the range of values of any
| integer type.

Martin
--
,--. Martin Dickopp, Dresden, Germany ,= ,-_-. =.
/ ,- ) http://www.zero-based.org/ ((_/)o o(\_))
\ `-' `-'(. .)`-'
`-. Debian, a variant of the GNU operating system. \_/

[Bernhard Holzmayer]

Irrwahn Grausewitz wrote:

Bernhard Holzmayer <ho****************@deadspam.com> wrote:
<snip>

After a close look to K&R 5.3 and additional sources, I'd like
to improve the above a little. What about the following modified
version:

int ptrInArrSafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
long index;

/* as long as a points to a valid array, this is a legal
test for the lower boundary*/
if (p<a) return 0; /*out */
If p and a didn't point into (or one past) the same array in
the first place, you already invoked undefined behaviour here
(C99 6.5.8#5). All bets off.

What a pity. Then, I guess, it's up to the caller of the function,
to make sure p is a valid pointer ;-)

/* evaluation of element's address is valid for all
elements
including the virtual last+1 element, though its content may not
be retrieved, comparison is legal test for upper boundary */
if (!(p<&a[max])) return 0; /* out */
Ditto.

You trapped me.

/* now we can be sure that we are inside array, because
standard requires that array is in a logically "dense" order, from
point of logical addresses they must be accessible in ascending
order */

index = (long)(p - a);
Forget about the cast. Declare index as ptrdiff_t instead.

Sure. Anyhow, I just forgot to remove the line after I realized that
it could be done without explicite cast.

/* as far as I understand, it's possible that p-a returns
the difference in multiples of sizeof(T), so that if element size
were 2, a[2]-a[1] would give 1 instead of 2.
That's not only possible, it's /required/ for a conforming
implementation to behave like this (C99 6.5.6#9): pointer
subtraction always yields values in units of element size.

I read this, and got it like you. However, it's not my experience
when working with real compilers.

Although I never found a compiler doing this,
Then you only found non-conforming compilers up until now.

one is gcc 2.95.3, tried on a struct with sizeof(T)==8

I replace sizeof(T) by
a method which should work in both cases. */
if ( (p-a) % (&a[1]-&a[0]))
Since &a[1]-&a[0] (==a+1-a) always yields 1, the condition
is always false.

However, with gcc, where p-a is 24, if p==&a[3], and &a[1]-&a[0]
==8, this returns true, if p points to an element between
boundaries, so it's useful in both situations on both types of
compilers... which was the intention.

return 0; /* not at element boundary*/

return 1; /* in and on element boundary */
}
End of the story: if you ever need to verify if a specific
pointed-to object is part of a certain array, carry around
the array length plus indices and compare these instead of
some 'raw' pointers. And, IMHO, if one feels the need to
perform the operation desired by the OP, one should first
rethink the algorithm, because it's most probably broken by
design.

I agree.
HTH
Regards

I learned a bit. Thanks.
Bernhard

[Martin Dickopp]

Bernhard Holzmayer <ho****************@deadspam.com> writes:

1) Isn't it correct, that long has to be of the size to hold any
pointer, so that a conversion:
(pType *) --> (void *) ---> (long)
and vice versa is legal?
No. In C99, you have the optional integer types `intptr_t' and
`uintptr_t' which can represent all values of `void *' if they exist at
all. In C89, no integer type is guaranteed to have this property.

Even if a suitable integer type exists, the conversion is not guaranteed
to preserve the ordering, i.e. while `&a[0] < &a[1]' is always true,
`(long)(&a[0]) < (long)(&a[1])' need not be, even if `long' can
represent the pointer values.
2) Isn't it correct, that arrays must have their elements arranged
subsequently, so that array == &array[0] and
&array[1]>&array[0] are valid?

Yes. Both expression evaluate to true (i.e. 1).

Martin
--
,--. Martin Dickopp, Dresden, Germany ,= ,-_-. =.
/ ,- ) http://www.zero-based.org/ ((_/)o o(\_))
\ `-' `-'(. .)`-'
`-. Debian, a variant of the GNU operating system. \_/

[Irrwahn Grausewitz]

Bernhard Holzmayer <ho****************@deadspam.com> wrote:

pete wrote: <snip>

N869
6.3.2.3 Pointers
[#6] Any pointer type may be converted to an integer
[#type.
Except as previously specified, the result
is
implementation-defined. If the result cannot be
represented
in the integer type, the behavior is undefined. The
result need not be in the range of values of any integer
type.

1) Isn't it correct, that long has to be of the size to hold any
pointer, so that a conversion:
(pType *) --> (void *) ---> (long)
and vice versa is legal?

As is obvious from above quote: no.
2) Isn't it correct, that arrays must have their elements arranged
subsequently, so that array == &array[0] and
&array[1]>&array[0] are valid?

Yes, err no, it's correct.

Regards
--
Irrwahn Grausewitz (ir*******@freenet.de)
welcome to clc: http://www.ungerhu.com/jxh/clc.welcome.txt
clc faq-list : http://www.faqs.org/faqs/C-faq/faq/
clc OT guide : http://benpfaff.org/writings/clc/off-topic.html

[Irrwahn Grausewitz]

Bernhard Holzmayer <ho****************@deadspam.com> wrote:

Bernhard Holzmayer wrote: <snip>Keith, would this hold on your Cray with the strange CHAR
representation, that p-a still returns a reasonable result?
*/

if ( (p-a) % (&a[1]-&a[0]))
return 0; /* not at element boundary*/

<snip>

Well, I'm not Keith, but for two pointers p and a the expression
(p-a) gives a reasonable result if, and only if, both point to
elements of (or one past) the same array object:

ISO/IEC 9899:1999 (E)
6.5.6 Additive operators
[...]
9 When two pointers are subtracted, both shall point to elements of
the same array object, or one past the last element of the array
object; the result is the difference of the subscripts of the two
array elements. The size of the result is implementation-defined,
and its type (a signed integer type) is ptrdiff_t defined in the
<stddef.h> header. If the result is not representable in an object
of that type, the behavior is undefined. In other words, if the
expressions P and Q point to, respectively, the i-th and j-th
elements of an array object, the expression (P)-(Q) has the value
i-j provided the value fits in an object of type ptrdiff_t.
Moreover, if the expression P points either to an element of an
array object or one past the last element of an array object, and
the expression Q points to the last element of the same array
object, the expression ((Q)+1)-(P) has the same value as
((Q)-(P))+1 and as -((P)-((Q)+1)), and has the value zero if the
expression P points one past the last element of the array object,
even though the expression (Q)+1 does not point to an element of
the array object.

HTH
Regards
--
Irrwahn Grausewitz (ir*******@freenet.de)
welcome to clc: http://www.ungerhu.com/jxh/clc.welcome.txt
clc faq-list : http://www.faqs.org/faqs/C-faq/faq/
clc OT guide : http://benpfaff.org/writings/clc/off-topic.html

[Irrwahn Grausewitz]

Bernhard Holzmayer <ho****************@deadspam.com> wrote:

Irrwahn Grausewitz wrote:

Bernhard Holzmayer <ho****************@deadspam.com> wrote: <snip>

if (p<a) return 0; /*out */
If p and a didn't point into (or one past) the same array in
the first place, you already invoked undefined behaviour here
(C99 6.5.8#5). All bets off.

What a pity. Then, I guess, it's up to the caller of the function,
to make sure p is a valid pointer ;-)

<snip>

That's indeed the best solution. ;-)

/* as far as I understand, it's possible that p-a returns
the difference in multiples of sizeof(T), so that if element size
were 2, a[2]-a[1] would give 1 instead of 2.

That's not only possible, it's /required/ for a conforming
implementation to behave like this (C99 6.5.6#9): pointer
subtraction always yields values in units of element size.

I read this, and got it like you. However, it's not my experience
when working with real compilers.

Although I never found a compiler doing this,

Then you only found non-conforming compilers up until now.

one is gcc 2.95.3, tried on a struct with sizeof(T)==8

<snip>

Uck. IIRC gcc 2.xx is indeed broken in several ways.

if ( (p-a) % (&a[1]-&a[0]))

Since &a[1]-&a[0] (==a+1-a) always yields 1, the condition
is always false.

However, with gcc, where p-a is 24, if p==&a[3], and &a[1]-&a[0]
==8, this returns true, if p points to an element between
boundaries, so it's useful in both situations on both types of
compilers... which was the intention.

<snip>

Well, I see your point, but IMHO, if one really has to cater for
broken implementations, I'd try to deal with it in the preprocessing
stage in RealWorld[tm] code (not including throw-away NG examples,
of course).
I learned a bit. Thanks.

</me listening to distant barking sounds>
Hopefully I didn't screw up something this time, but the pack will
eventually jump on it and correct it anyway. ;-)

Regards
--
Irrwahn Grausewitz (ir*******@freenet.de)
welcome to clc: http://www.ungerhu.com/jxh/clc.welcome.txt
clc faq-list : http://www.faqs.org/faqs/C-faq/faq/
clc OT guide : http://benpfaff.org/writings/clc/off-topic.html

[Bernhard Holzmayer]

Irrwahn Grausewitz wrote:

SO/IEC 9899:1999 (E)
6.5.6 Additive operators
[...]
9 When two pointers are subtracted, both shall point to elements
of
the same array object, or one past the last element of the
array

Here it reads "shall", not "must".
That's what I have in mind, and what one can read in several
locations where pointers and pointer arithmetics are handled.

Either ISO should be clearer here, if this means optional like
undefined behaviour.

Otherwise, if it is written on purpose, it's an implicite statement
that at least one of the pointers may point elsewhere.

SCNR,
Bernhard

[Dik T. Winter]

In article <12*****************@holzmayer.ifr.rt> ho****************@deadspam.com writes:

Dik T. Winter wrote: ....

But the result is implementation defined. I know of at least one
system where it will fail to give the correct answer, then T is
char. For instance:
(long)(a + 7) > (long)(a + 8)
when a is an array of type char.

That's not the same.

What is the difference?
Would you please try the following:
(long)(&a[7]) < (long)(&a[8])
Returns false on that system.
this should give the correct result.
Which is the correct result on that system.
Reason for your strange behaviour is possibly the implicite type
cast, which converts a before adding.
No, that is *not* the reason, because there is no implicit type cast.
Instead, the later version increments a as a pointer and then
converts it.

As does the first version. But to clarify, on that system a pointer
(and a long) are 64 bits. In a pointer the lower 48 bits are the
word pointer (a word is also 64 bits), the upper 16 bits are a
relative byte pointer within a word. Casting a pointer to long
performs no conversion at all.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, [phone]
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Irrwahn Grausewitz]

Bernhard Holzmayer <ho****************@deadspam.com> wrote:

Irrwahn Grausewitz wrote:

SO/IEC 9899:1999 (E)
6.5.6 Additive operators
[...]
9 When two pointers are subtracted, both shall point to elements
of
the same array object, or one past the last element of the
array

Here it reads "shall", not "must".
That's what I have in mind, and what one can read in several
locations where pointers and pointer arithmetics are handled.

Either ISO should be clearer here, if this means optional like
undefined behaviour.

Otherwise, if it is written on purpose, it's an implicite statement
that at least one of the pointers may point elsewhere.

"Shall" is Standardese for: "must, under all circumstances,
otherwise demons might fly out of your nose". :-)

Or, as the authors of the standard put it:

ISO/IEC 9899:1999 (E)
4. Conformance
1 In this International Standard, "shall" is to be interpreted as
a requirement on an implementation or on a program; conversely,
"shall not" is to be interpreted as a prohibition.

Regards.
--
Irrwahn Grausewitz (ir*******@freenet.de)
welcome to clc: http://www.ungerhu.com/jxh/clc.welcome.txt
clc faq-list : http://www.faqs.org/faqs/C-faq/faq/
clc OT guide : http://benpfaff.org/writings/clc/off-topic.html

[Martin Dickopp]

Irrwahn Grausewitz <ir*******@freenet.de> writes:

Bernhard Holzmayer <ho****************@deadspam.com> wrote:

Irrwahn Grausewitz wrote:

Bernhard Holzmayer <ho****************@deadspam.com> wrote:
/* as far as I understand, it's possible that p-a returns
the difference in multiples of sizeof(T), so that if element size
were 2, a[2]-a[1] would give 1 instead of 2. ^^^^^^^^^
I assume you mean `&a[2]-&a[1]' here? Otherwise, the statement doesn't
make much sense in this context, as the /contents/ of the array `a' are
not necessarily correlated to the size of its elements.
That's not only possible, it's /required/ for a conforming
implementation to behave like this (C99 6.5.6#9): pointer
subtraction always yields values in units of element size.

I read this, and got it like you. However, it's not my experience
when working with real compilers.

Although I never found a compiler doing this,

Then you only found non-conforming compilers up until now.

one is gcc 2.95.3, tried on a struct with sizeof(T)==8

<snip>

Uck. IIRC gcc 2.xx is indeed broken in several ways.

While gcc 2.95.3 was indeed broken in some ways, it wasn't *that*
broken. :) In fact, I have sucessfully used pointer arithmentic with
more or less every gcc version since at least 2.6.3.

There's likely a different explanation for Bernhard's observation, e.g.
UB at a different position in the program.

Martin
--
,--. Martin Dickopp, Dresden, Germany ,= ,-_-. =.
/ ,- ) http://www.zero-based.org/ ((_/)o o(\_))
\ `-' `-'(. .)`-'
`-. Debian, a variant of the GNU operating system. \_/

[Martin Dickopp]

Irrwahn Grausewitz <ir*******@freenet.de> writes:

Bernhard Holzmayer <ho****************@deadspam.com> wrote:

Irrwahn Grausewitz wrote:

ISO/IEC 9899:1999 (E)
6.5.6 Additive operators
[...]
9 When two pointers are subtracted, both shall point to elements
of the same array object, or one past the last element of the
array

Here it reads "shall", not "must".

"Shall" is Standardese for: "must, under all circumstances,
otherwise demons might fly out of your nose". :-)

Or, as the authors of the standard put it:

ISO/IEC 9899:1999 (E)
4. Conformance
1 In this International Standard, "shall" is to be interpreted as
a requirement on an implementation or on a program; conversely,
"shall not" is to be interpreted as a prohibition.

The standard then goes on:
| 2 If a "shall" or "shall not" requirement that appears outside of
| a constraint is violated, the behavior is undefined.

This is the case here, as 6.5.6#9 is not a constraint.

Undefined behavior is defined in 3.4.3:
| 1 undefined behavior
| behavior, upon use of a nonportable or erroneous program construct
| or of erroneous data, for which this International Standard imposes
| no requirements
|
| 2 NOTE Possible undefined behavior ranges from ignoring the
| situation completely with unpredictable results, to behaving during
| translation or program execution in a documented manner
| characteristic of the environment (with or without the issuance of
| a diagnostic message), to terminating a translation or execution
| (with the issuance of a diagnostic message).

Martin
--
,--. Martin Dickopp, Dresden, Germany ,= ,-_-. =.
/ ,- ) http://www.zero-based.org/ ((_/)o o(\_))
\ `-' `-'(. .)`-'
`-. Debian, a variant of the GNU operating system. \_/

[Chris Torek]

>Bernhard Holzmayer <ho****************@deadspam.com> wrote:

index = (long)(p - a); [where "p" and "a" are pointers to compatible types]

In article <news:cj********************************@4ax.com >
Irrwahn Grausewitz <ir*******@freenet.de> writes:

Forget about the cast. Declare index as ptrdiff_t instead.

Yes.

Also, the Standard requires (of the programmer) that p and a both
"point into" the same underlying object, and the difference between
two such pointers is the (integral) number of objects separating
them. That is, if p == &a[i] (for any valid i), "p - a" must
produce i.

Compilers generally implement this internally by turning:

(ptr2 - ptr1)

into:

(((intptr_t)ptr2 - (intptr_t)ptr1) / sizeof *ptr1)

This underlying division produces the desired integral answer, and
always has a remainder of zero. Years ago, gcc compiled this code
to ordinary signed integer division, which often became a right-shift
with a "remainder correction" step during optimization. I sent
email to RMS pointing out that the remainder was necessarily zero
-- so that the correction never corrected anything and was a waste
of CPU time -- and he added what is now, in gcc3, the "EXACT_DIV_EXPR"
expression-type. An "exact divide" is one whose remainder is known
in advance to be zero (by the rules of the source language).

Since gcc believes the C programmer got this right, the attempt to
do this:
if ( (p-a) % ...

is fundamentally flawed. Converting both pointers to to long --
or, better but C99-only, intptr_t -- will "do the right thing" on
ordinary byte-addressed machines, though.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) [phone]
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[Christian Bau]

In article <13****************@holzmayer.ifr.rt>,
Bernhard Holzmayer <ho****************@deadspam.com> wrote:

Thomas Stegen wrote:

Bernhard Holzmayer wrote:

Sorry,
pardon me for not checking my code intensively enough.
I just checked with a 'gcc -pedantic' which didn't throw an error
:(

What about this solution:
int ptrInArrSafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
long px = (long)p;
long ax = (long)a;
if (px<ax) return 0; /*out*/
if (px> (long)&a[max-1]) return 0; /* out */
if ( (px-ax) % sizeof(T)) return 0; /* not at element
start*/
return 1; /* in and on element start */
}

After a close look to K&R 5.3 and additional sources, I'd like
to improve the above a little.

Take a copy of the C Standard as an additional source.

What about the following modified
version:

int ptrInArrSafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
long index;

/* as long as a points to a valid array, this is a legal
test for the lower boundary*/
if (p<a) return 0; /*out */
Wrong. That single comparison can invoke undefined behavior and make
your program crash. No need to read any further.

/* evaluation of element's address is valid for all elements
including the virtual last+1 element, though its content may not be
retrieved, comparison is legal test for upper boundary */
if (!(p<&a[max])) return 0; /* out */

/* now we can be sure that we are inside array, because
standard requires that array is in a logically "dense" order, from
point of logical addresses they must be accessible in ascending
order */

index = (long)(p - a);
/* as far as I understand, it's possible that p-a returns
the difference in multiples of sizeof(T), so that if element size
were 2, a[2]-a[1] would give 1 instead of 2.
Although I never found a compiler doing this, I replace sizeof(T) by
a method which should work in both cases. */
if ( (p-a) % (&a[1]-&a[0]))
return 0; /* not at element boundary*/

return 1; /* in and on element boundary */
}

Bernhard

[Christian Bau]

In article <14****************@holzmayer.ifr.rt>,
Bernhard Holzmayer <ho****************@deadspam.com> wrote:

pete wrote:

Bernhard Holzmayer wrote:

IMHO you have to use pointer-to-long which must be well-defined
according to the standard, which means, that a long is big enough
to hold a pointer on that system. An integer might be too short.
Whether or not a pointer can be converted to any integer type
is implementation defined.
The standard does not guarantee that relationships which hold
for two pointers, will also hold for their converted integer
values.

N869
6.3.2.3 Pointers
[#6] Any pointer type may be converted to an integer
[#type.
Except as previously specified, the result
is
implementation-defined. If the result cannot be
represented
in the integer type, the behavior is undefined. The
result need not be in the range of values of any integer
type.

1) Isn't it correct, that long has to be of the size to hold any
pointer, so that a conversion:
(pType *) --> (void *) ---> (long)
and vice versa is legal?

No. It is entirely possible that there is no integer type big enough to
hold all possible pointer values.

2) Isn't it correct, that arrays must have their elements arranged
subsequently, so that array == &array[0] and
&array[1]>&array[0] are valid?

True. But if you compare pointers that don't point into the same array,
all odds are off.

[Keith Thompson]

Irrwahn Grausewitz <ir*******@freenet.de> writes:

Bernhard Holzmayer <ho****************@deadspam.com> wrote:

Irrwahn Grausewitz wrote:

Bernhard Holzmayer <ho****************@deadspam.com> wrote: <snip> if (p<a) return 0; /*out */

If p and a didn't point into (or one past) the same array in
the first place, you already invoked undefined behaviour here
(C99 6.5.8#5). All bets off.

What a pity. Then, I guess, it's up to the caller of the function,
to make sure p is a valid pointer ;-)

<snip>

That's indeed the best solution. ;-)

/* as far as I understand, it's possible that p-a returns
the difference in multiples of sizeof(T), so that if element size
were 2, a[2]-a[1] would give 1 instead of 2.

That's not only possible, it's /required/ for a conforming
implementation to behave like this (C99 6.5.6#9): pointer
subtraction always yields values in units of element size.

I read this, and got it like you. However, it's not my experience
when working with real compilers.

Although I never found a compiler doing this,

Then you only found non-conforming compilers up until now.

one is gcc 2.95.3, tried on a struct with sizeof(T)==8

<snip>

Uck. IIRC gcc 2.xx is indeed broken in several ways.

[...]

I seriously doubt that gcc 2.xx, or any usable C compiler, gets
something as fundamental as pointer arithmetic wrong.

Here's a sample program:

#include <stdio.h>
int main(void)
{
double arr[10];
double *ptr5 = &(arr[5]);
double *ptr8 = &(arr[8]);

/*
* ddiff is the difference between ptr5 and ptr8, interpreted
* as pointers to double.
* cdiff is the difference bewteen ptr5 and ptr8, both interpreted
* as pointers to char.
* The subtraction operator actually yields a result of type ptrdiff_t,
* but it's implicitly converted to int; as long as it's within
* the range, no information is lost.
*/
int ddiff = ptr8 - ptr5;
int cdiff = (char*)ptr8 - (char*)ptr5;

printf("sizeof(double) = %d\n", (int)sizeof(double));
printf("ptr5 = [%p]\n", (void*)ptr5);
printf("ptr8 = [%p]\n", (void*)ptr8);
printf("ddiff = %d\n", ddiff);
printf("cdiff = %d\n", cdiff);

if (cdiff == ddiff * sizeof(double)) {
printf("Looks ok\n");
}
else {
printf("Something is wrong\n");
}

return 0;
}

If it prints "Something is wrong" on your implementation, there is
indeed a serious problem. I just tried it with gcc versions 2.7.2.2,
2.8.1, 2.95.2, 3.0.4, and 3.2.2, and it printed "Looks ok" every time.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
Schroedinger does Shakespeare: "To be *and* not to be"

[Old Wolf]

Ike Naar <no****@nospam.invalid> wrote:

If p does not point to an element of a[max], all comparisons
(p<a), (p>&a[max-1]) and ((p-a)%sizeof(T)) invoke undefined
behaviour and can evaluate to anything, including 'true'.
So your solution may produce a 'false positive' result.

Is it actually undefined behaviour (ie. program can crash), or
just "undefined result" (ie. unspecified behaviour). I was assured
by one of the WG members for C++ recently that in C++ it is
merely unspecified behaviour. It would be notable if the two
languages differed in this respect.

[RoSsIaCrIiLoIA]

On Wed, 07 Apr 2004 06:17:22 GMT, CBFalconer wrote:

Ike Naar wrote:

Suppose I want to find out whether a given pointer (say, p) of type
*T points to an element of a given array (say, a) of type T[max].
A way to achieve this would be a linear search through the array:

int ptrInArrSafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
int j=0;
while (j!=max && a+j!=p) ++j;
return j!=max;
}

Obviously, this algorithm is terribly slow for large max.

A more efficient algorithm is

int ptrInArrUnsafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
int j=p-a; /* possibly undefined */
return 0<=j && j<max && a+j==p;
}

... snip ...
The safe version can possibly be slightly sped up by:

/* check whether p points to an element of a[max] */
int ptrInArrSafe(T *p, const T *a, int max)
{
T *pp;

for (pp = a + max; a < pp; a++)
if (p == a) return 1;
return 0;
}

which treats the valid, but undereferenceable, pointer one past
the end of a (value pp) as not within a. This may or may not be
what you want.

but is it safe compare pointers to different objects?
K&R A7.9 semms to say no. Why?

Is the compare for void* always possible?
Is this better?

size_t ptrInArrSafe(T *p, const T *a, size_t max)
{T *pp;
assert(max!=0);
for (pp = a + max; a < pp; a++)
if( (void*) p == (void*) a ) return (a-pp)+1;
return 0;
}

T a[50], *p, x[89];
p=x; /* p point to a an object != from x */
index_plus1=ptrInArrSafe(p, a, 50);

and if we have
char *a, *b;
a=malloc(39);
b=malloc(59);
is it safe
if((void*) a> (void*) b) ++minor;
or
if( (void*) a == (void*) b) minor = (minor>0 ? 1: -1);
?
Thanks

[Jeremy Yallop]

Old Wolf wrote:

Ike Naar <no****@nospam.invalid> wrote:

If p does not point to an element of a[max],
(or to "one past the end" of a)
all comparisons (p<a), (p>&a[max-1]) and ((p-a)%sizeof(T)) invoke
undefined behaviour and can evaluate to anything, including 'true'.
So your solution may produce a 'false positive' result.
Is it actually undefined behaviour (ie. program can crash), or
just "undefined result" (ie. unspecified behaviour).

It's actual undefined behaviour by (explicit) omission. It falls
under "all other cases" in the following excerpt:

[C99 6.5.8 Relational operators]

5 When two pointers are compared, the result depends on the
relative locations in the address space of the objects pointed
to. If two pointers to object or incomplete types both point to
the same object, or both point one past the last element of the
same array object, they compare equal. If the objects pointed to
are members of the same aggregate object, pointers to structure
members declared later compare greater than pointers to members
declared earlier in the structure, and pointers to array
elements with larger subscript values compare greater than
pointers to elements of the same array with lower subscript
values. All pointers to members of the same union object
compare equal. If the expression P points to an element of an
array object and the expression Q points to the last element of
the same array object, the pointer expression Q+1 compares
greater than P. In all other cases, the behavior is undefined.
I was assured by one of the WG members for C++ recently that in C++
it is merely unspecified behaviour. It would be notable if the two
languages differed in this respect.

Right: it's unspecified behaviour in C++.

[C++98 5.9 Relational operators]

- If two pointers p and q of the same type point to different
objects that are not members of the same object or elements of
the same array or to different functions, or if only one of them
is null, the results of p<q, p>q, p<=q, and p>=q are
unspecified.

I believe the reason is to allow pointers to work reliably as the keys
of associative containers (set, map, etc.), but you should ask in the
C++ groups if you want a more definitive answer.

Jeremy.