pointer-in-array test

[Keith Thompson]

Re: pointer-in-array test

Irrwahn Grausewitz <irrwahn33@free net.de> writes:[color=blue]
> Bernhard Holzmayer <holzmayer.bern hard@deadspam.c om> wrote:[color=green]
> >Irrwahn Grausewitz wrote:
> >[color=darkred]
> >> Bernhard Holzmayer <holzmayer.bern hard@deadspam.c om> wrote:[/color][/color]
> <snip>[color=green][color=darkred]
> >>> 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.[/color]
> >What a pity. Then, I guess, it's up to the caller of the function,
> >to make sure p is a valid pointer ;-)[/color]
> <snip>
>
> That's indeed the best solution. ;-)
>[color=green][color=darkred]
> >>> /* 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.[/color]
> >I read this, and got it like you. However, it's not my experience
> >when working with real compilers.
> >[color=darkred]
> >>>Although I never found a compiler doing this,
> >>
> >> Then you only found non-conforming compilers up until now.[/color]
> >one is gcc 2.95.3, tried on a struct with sizeof(T)==8[/color]
> <snip>
>
> Uck. IIRC gcc 2.xx is indeed broken in several ways.[/color]
[...]

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(dou ble));
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("Somethi ng 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_Keit h) kst-u@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]

Re: pointer-in-array test

Ike Naar <nospam@nospam. invalid> wrote:[color=blue]
>
> 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.[/color]

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]

Re: pointer-in-array test

On Wed, 07 Apr 2004 06:17:22 GMT, CBFalconer wrote:[color=blue]
>Ike Naar wrote:[color=green]
>> 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;
>> }
>>[/color]
>... 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 undereferenceab le, pointer one past
>the end of a (value pp) as not within a. This may or may not be
>what you want.[/color]

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=ptr InArrSafe(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]

Re: pointer-in-array test

Old Wolf wrote:[color=blue]
> Ike Naar <nospam@nospam. invalid> wrote:[color=green]
>>
>> If p does not point to an element of a[max],[/color][/color]

(or to "one past the end" of a)
[color=blue][color=green]
>> 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.[/color]
>
> Is it actually undefined behaviour (ie. program can crash), or
> just "undefined result" (ie. unspecified behaviour).[/color]

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.
[color=blue]
> 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.[/color]

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.