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

[Barry Schwarz]

Re: pointer-in-array test

On Wed, 07 Apr 2004 02:17:47 GMT, Ike Naar <nospam@nospam. invalid>
wrote:
[color=blue]
>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?
>[/color]
If your system supports the optional intptr_t type, you can convert p,
a, and a+1 to integers and determine the correct answer without fear
of undefined behavior.


<<Remove the del for email>>

[CBFalconer]

Re: pointer-in-array test

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

This is the sort of thing that you put in a file marked as system
dependant code, and include both versions, controlled by some
define.

However I would look closely at the reason for having such a
routine, and try to avoid it in the first place.

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.

--
Chuck F (cbfalconer@yah oo.com) (cbfalconer@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[Martin Dickopp]

Re: pointer-in-array test

Barry Schwarz <schwarzb@deloz .net> writes:
[color=blue]
> On Wed, 07 Apr 2004 02:17:47 GMT, Ike Naar <nospam@nospam. invalid>
> wrote:
>[color=green]
>>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?
>>[/color]
> If your system supports the optional intptr_t type, you can convert p,
> a, and a+1 to integers and determine the correct answer without fear
> of undefined behavior.[/color]

You'd still have to fear implementation-defined behavior, though. :)

There is no guarantee that (intptr_t)(void *)&a[1] is greater than
(intptr_t)(void *)&a[0].

Martin


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

[Bernhard Holzmayer]

Re: pointer-in-array test

Ike Naar wrote:
[color=blue]
> 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;
> }
>[/color]

Sorry Ike,
if it's a naive question.

If you really have an array, why don't you just use a thing like the
following

int ptrInArrSafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
if (p<a) return 0; /*out*/

if (p> &a[max-1]) return 0; /* out */

if ( (p-a) % sizeof(T)) return 0; /* not at element start*/

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

This should be sufficient, if you want to check only the borders and
that your pointer is at the beginning of an element a[x].

Bernhard

[Martin Dickopp]

Re: pointer-in-array test

Bernhard Holzmayer <holzmayer.bern hard@deadspam.c om> writes:
[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;
>> }
>>[/color]
>
> Sorry Ike,
> if it's a naive question.
>
> If you really have an array, why don't you just use a thing like the
> following
>
> int ptrInArrSafe(T *p,T *a,int max)
> /* check whether p points to an element of a[max] */
> {
> if (p<a) return 0; /*out*/[/color]

As is just being discussed in the thread "pointer equality", this
invokes undefined behavior if `p' does not point into `a' (or to the
location just following the last element of `a').
[color=blue]
> if (p> &a[max-1]) return 0; /* out */[/color]

So does this.

Martin


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

[pete]

Re: pointer-in-array test

Bernhard Holzmayer 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;
> > }
> >[/color]
>
> Sorry Ike,
> if it's a naive question.
>
> If you really have an array, why don't you just use a thing like the
> following
>
> int ptrInArrSafe(T *p,T *a,int max)
> /* check whether p points to an element of a[max] */
> {
> if (p<a) return 0; /*out*/
>
> if (p> &a[max-1]) return 0; /* out */
>
> if ( (p-a) % sizeof(T)) return 0; /* not at element start*/
>
> return 1; /* in and on element start */
> }[/color]

(p<a), (p> &a[max-1]), and (p-a), are all undefined
if p and a point to bytes of unrelated objects.

--
pete

[Ike Naar]

Re: pointer-in-array test

Hi Bernard,

Bernhard Holzmayer <holzmayer.bern hard@deadspam.c om> wrote:
: If you really have an array, why don't you just use a thing like the
: following
:
: int ptrInArrSafe(T *p,T *a,int max)
: /* check whether p points to an element of a[max] */
: {
: if (p<a) return 0; /*out*/
: if (p> &a[max-1]) return 0; /* out */
: if ( (p-a) % sizeof(T)) return 0; /* not at element start*/
: return 1; /* in and on element start */
: }
:
: This should be sufficient, if you want to check only the borders and
: that your pointer is at the beginning of an element a[x].

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.

: Bernhard


--
mail to ike at iae dot nl

[Ike Naar]

Re: pointer-in-array test

CBFalconer <cbfalconer@yah oo.com> 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.
:
: 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.

That's what I want. To be precise, I want to know if there exists an
index j such that 0 <= j < max and &a[j] == p .

But apart from stylistic differences, I see no reason why your
solution would be any faster or slower than mine.
Both algorithms perform a linear search on the array.

: --
: Chuck F (cbfalconer@yah oo.com) (cbfalconer@wor ldnet.att.net)
: Available for consulting/temporary embedded and systems.
: <http://cbfalconer.home .att.net> USE worldnet address!



--
mail to ike at iae dot nl

[Bernhard Holzmayer]

Re: pointer-in-array test

Ike Naar wrote:
[color=blue]
> Hi Bernard,
>
> Bernhard Holzmayer <holzmayer.bern hard@deadspam.c om> wrote:
> : If you really have an array, why don't you just use a thing like
> : the following
> :
> : int ptrInArrSafe(T *p,T *a,int max)
> : /* check whether p points to an element of a[max] */
> : {
> : if (p<a) return 0; /*out*/
> : if (p> &a[max-1]) return 0; /* out */
> : if ( (p-a) % sizeof(T)) return 0; /* not at element start*/
> : return 1; /* in and on element start */
> : }
> :
> : This should be sufficient, if you want to check only the borders
> : and that your pointer is at the beginning of an element a[x].
>
> 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.
>
> : Bernhard
>
>[/color]

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.

Bernhard

[Keith Thompson]

Re: pointer-in-array test

Barry Schwarz <schwarzb@deloz .net> writes:
[...][color=blue]
> If your system supports the optional intptr_t type, you can convert p,
> a, and a+1 to integers and determine the correct answer without fear
> of undefined behavior.[/color]

The only guarantee for intptr_t is that you can convert a void* to
intptr_t and back to void*, and the result will compare equal to the
original void*. It's not clear (to me) that relational operators are
sufficiently well-defined to allow reliably checking whether a pointer
points within an array.

Suppose a char* pointer consists of a word pointer with a byte offset
in the high-order bits, and that pointer-to-integer conversion simply
copies the bits. This satisfies the standard and allows the type
intptr_t to be defined, but doesn't support the kind of comparisons
required. The code (see previous posts) avoids undefined behavior,
but it yields incorrect results.

--
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"

[Bernhard Holzmayer]

Re: pointer-in-array test

Keith Thompson wrote:
[color=blue]
> Barry Schwarz <schwarzb@deloz .net> writes:
> [...][color=green]
>> If your system supports the optional intptr_t type, you can
>> convert p, a, and a+1 to integers and determine the correct
>> answer without fear of undefined behavior.[/color]
>
> The only guarantee for intptr_t is that you can convert a void* to
> intptr_t and back to void*, and the result will compare equal to
> the
> original void*. It's not clear (to me) that relational operators
> are sufficiently well-defined to allow reliably checking whether a
> pointer points within an array.
>
> Suppose a char* pointer consists of a word pointer with a byte
> offset in the high-order bits, and that pointer-to-integer[/color]
pointer-to-integer is not enough.
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.
[color=blue]
> conversion simply
> copies the bits. This satisfies the standard and allows the type
> intptr_t to be defined, but doesn't support the kind of
> comparisons
> required. The code (see previous posts) avoids undefined
> behavior, but it yields incorrect results.
>[/color]

[pete]

Re: pointer-in-array test

Bernhard Holzmayer wrote:
[color=blue]
> 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.[/color]

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.

--
pete

[Thomas Stegen]

Re: pointer-in-array test

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

Can you associate with the value of the pointer whether or not it
points into a certain array when it is set? For example in a hashtable
which maps pointers to arrays? This way you can at least amortize the
cost and have a lookup time roundabout O(1).

--
Thomas.

[Thomas Stegen]

Re: pointer-in-array test

Bernhard Holzmayer wrote:
[color=blue]
> 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 */
> }[/color]

The above is valid in that it does not invoke UB. It does however
depend on implementation defined behaviour and so is not guaranteed
to work for all platforms. But it is definetely the way I would do
it. Just have some conditional compilation which does something that
is guaranteed to work if the platform does not support the above.
[color=blue]
>
> compiles, links, runs without problems with my gcc.
> And, as far as I remember, it's legal, to compare pointers after
> conversion to long.[/color]

It is legal, but the conversion to long is implementation defined.
And unsigned long might be a better choice.

--
Thomas.