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=pa; /* 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, reformat 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 67 4024
On Wed, 07 Apr 2004 02:17:47 GMT, Ike Naar <no****@nospam.invalid>
wrote: 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=pa; /* 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, reformat 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?
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>>
On Wed, 07 Apr 2004 02:17:47 GMT, Ike Naar <no****@nospam.invalid>
wrote: 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=pa; /* 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, reformat 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?
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>>
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=pa; /* possibly undefined */ return 0<=j && j<max && a+j==p; }
.... snip ... 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?
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 undereferenceable, pointer one past
the end of a (value pp) as not within a. This may or may not be
what you want.

Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
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=pa; /* possibly undefined */ return 0<=j && j<max && a+j==p; }
.... snip ... 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?
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 undereferenceable, pointer one past
the end of a (value pp) as not within a. This may or may not be
what you want.

Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Barry Schwarz <sc******@deloz.net> writes: On Wed, 07 Apr 2004 02:17:47 GMT, Ike Naar <no****@nospam.invalid> wrote:
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=pa; /* 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, reformat 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? 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.
You'd still have to fear implementationdefined 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.zerobased.org/ ((_/)o o(\_))
\ `' `'(. .)`'
`. Debian, a variant of the GNU operating system. \_/
Barry Schwarz <sc******@deloz.net> writes: On Wed, 07 Apr 2004 02:17:47 GMT, Ike Naar <no****@nospam.invalid> wrote:
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=pa; /* 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, reformat 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? 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.
You'd still have to fear implementationdefined 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.zerobased.org/ ((_/)o o(\_))
\ `' `'(. .)`'
`. Debian, a variant of the GNU operating system. \_/
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; }
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[max1]) return 0; /* out */
if ( (pa) % 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
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; }
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[max1]) return 0; /* out */
if ( (pa) % 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
Bernhard Holzmayer <ho****************@deadspam.com> writes: 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; }
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*/
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').
if (p> &a[max1]) return 0; /* out */
So does this.
Martin

,. Martin Dickopp, Dresden, Germany ,= ,_. =.
/ , ) http://www.zerobased.org/ ((_/)o o(\_))
\ `' `'(. .)`'
`. Debian, a variant of the GNU operating system. \_/
Bernhard Holzmayer <ho****************@deadspam.com> writes: 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; }
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*/
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').
if (p> &a[max1]) return 0; /* out */
So does this.
Martin

,. Martin Dickopp, Dresden, Germany ,= ,_. =.
/ , ) http://www.zerobased.org/ ((_/)o o(\_))
\ `' `'(. .)`'
`. Debian, a variant of the GNU operating system. \_/
Bernhard Holzmayer 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; }
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[max1]) return 0; /* out */
if ( (pa) % sizeof(T)) return 0; /* not at element start*/
return 1; /* in and on element start */ }
(p<a), (p> &a[max1]), and (pa), are all undefined
if p and a point to bytes of unrelated objects.

pete
Bernhard Holzmayer 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; }
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[max1]) return 0; /* out */
if ( (pa) % sizeof(T)) return 0; /* not at element start*/
return 1; /* in and on element start */ }
(p<a), (p> &a[max1]), and (pa), are all undefined
if p and a point to bytes of unrelated objects.

pete
Hi Bernard,
Bernhard Holzmayer <ho****************@deadspam.com> 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[max1]) return 0; /* out */
: if ( (pa) % 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[max1]) and ((pa)%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
Hi Bernard,
Bernhard Holzmayer <ho****************@deadspam.com> 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[max1]) return 0; /* out */
: if ( (pa) % 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[max1]) and ((pa)%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
CBFalconer <cb********@yahoo.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 undereferenceable, 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 (cb********@yahoo.com) (cb********@worldnet.att.net)
: Available for consulting/temporary embedded and systems.
: <http://cbfalconer.home.att.net> USE worldnet address!

mail to ike at iae dot nl
CBFalconer <cb********@yahoo.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 undereferenceable, 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 (cb********@yahoo.com) (cb********@worldnet.att.net)
: Available for consulting/temporary embedded and systems.
: <http://cbfalconer.home.att.net> USE worldnet address!

mail to ike at iae dot nl
Ike Naar wrote: Hi Bernard,
Bernhard Holzmayer <ho****************@deadspam.com> 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[max1]) return 0; /* out */ : if ( (pa) % 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[max1]) and ((pa)%sizeof(T)) invoke undefined behaviour and can evaluate to anything, including 'true'. So your solution may produce a 'false positive' result.
: Bernhard
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[max1]) return 0; /* out */
if ( (pxax) % 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
Ike Naar wrote: Hi Bernard,
Bernhard Holzmayer <ho****************@deadspam.com> 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[max1]) return 0; /* out */ : if ( (pa) % 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[max1]) and ((pa)%sizeof(T)) invoke undefined behaviour and can evaluate to anything, including 'true'. So your solution may produce a 'false positive' result.
: Bernhard
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[max1]) return 0; /* out */
if ( (pxax) % 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
Barry Schwarz <sc******@deloz.net> writes:
[...] 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.
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 welldefined 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 highorder bits, and that pointertointeger 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_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"
Barry Schwarz <sc******@deloz.net> writes:
[...] 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.
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 welldefined 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 highorder bits, and that pointertointeger 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_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"
Keith Thompson wrote: Barry Schwarz <sc******@deloz.net> writes: [...] 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. 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 welldefined 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 highorder bits, and that pointertointeger
pointertointeger is not enough.
IMHO you have to use pointertolong which must be welldefined
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.
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 wrote: Barry Schwarz <sc******@deloz.net> writes: [...] 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. 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 welldefined 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 highorder bits, and that pointertointeger
pointertointeger is not enough.
IMHO you have to use pointertolong which must be welldefined
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.
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.
Bernhard Holzmayer wrote: IMHO you have to use pointertolong which must be welldefined 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
implementationdefined. 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
Bernhard Holzmayer wrote: IMHO you have to use pointertolong which must be welldefined 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
implementationdefined. 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
Ike Naar wrote: 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:
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.
Ike Naar wrote: 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:
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.
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[max1]) return 0; /* out */ if ( (pxax) % sizeof(T)) return 0; /* not at element start*/ return 1; /* in and on element start */ }
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. 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 is legal, but the conversion to long is implementation defined.
And unsigned long might be a better choice.

Thomas.
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[max1]) return 0; /* out */ if ( (pxax) % sizeof(T)) return 0; /* not at element start*/ return 1; /* in and on element start */ }
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. 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 is legal, but the conversion to long is implementation defined.
And unsigned long might be a better choice.

Thomas.
In article <11****************@holzmayer.ifr.rt> ho****************@deadspam.com writes:
.... 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[max1]) return 0; /* out */ if ( (pxax) % 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.
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.

dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
In article <11****************@holzmayer.ifr.rt> ho****************@deadspam.com writes:
.... 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[max1]) return 0; /* out */ if ( (pxax) % 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.
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.

dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Ike Naar wrote: [...] 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=pa; /* 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.
Agree.
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.
Disagree. Everything seems correct up to the semicolon,
but after that things fall apart:
 First, it is not necessarily the case that garbage will
be stored in j. "Undefined behavior" is "undefined,"
and does not necessarily result in storing anything at
all anywhere at all.
 Second, even if something does get stored into j, it's
not certain that the "something" will be recognizable
as "garbage." For example, the value zero might be
stored into j, just as if you had called
ptrInArrUnsafe(&array[0], array, 1)
 ... and if this (or something like it) happens, the
return expression will evaluate true, not false.
Apart from storing garbage in j, the pointer subtraction could, in theory, crash the system, reformat the floppy disk or wake up nasal daemons, but this has not happened so far on any platform with any compiler (tried several).
Personally, I've never seen demons fly from my nose (they're
awfully fast, and are usually out of sight before I notice them).
But one need not invoke exotic architectures to get weird behavior
out of violating the rules of pointer subtraction. For example,
consider a "plain vanilla" system with nice linear addressing,
where pointers are just unadorned numeric addresses. Now try
this on for size:
typedef char[8] T;
T array[5];
printf ("%d\n", ptrInArrUnsafe(&array[0][1], array, 5));
It is quite likely (not certain, of course: undefined behavior
is undefined) that j will compute as zero inside the function,
leading the function to conclude that the pointer is valid.
The conclusion is utterly wrong, of course: the pointer aims
not at the start of a T object, but one byte past the start
of the first T object in the array.
My question is, do you experts in this group see any real problem with the second algorithm?
Yes, as explained above.
Alternatively, would there be a faster algorithm than the first one, that does not invoke undefined behaviour?
I cannot think of one. As CBF suggests, you should (a)
reexamine whether such a test is required, and if it is
you should (b) isolate the test to a systemdependent source
file, not intended to be portable.
 Er*********@sun.com
Ike Naar wrote: [...] 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=pa; /* 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.
Agree.
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.
Disagree. Everything seems correct up to the semicolon,
but after that things fall apart:
 First, it is not necessarily the case that garbage will
be stored in j. "Undefined behavior" is "undefined,"
and does not necessarily result in storing anything at
all anywhere at all.
 Second, even if something does get stored into j, it's
not certain that the "something" will be recognizable
as "garbage." For example, the value zero might be
stored into j, just as if you had called
ptrInArrUnsafe(&array[0], array, 1)
 ... and if this (or something like it) happens, the
return expression will evaluate true, not false.
Apart from storing garbage in j, the pointer subtraction could, in theory, crash the system, reformat the floppy disk or wake up nasal daemons, but this has not happened so far on any platform with any compiler (tried several).
Personally, I've never seen demons fly from my nose (they're
awfully fast, and are usually out of sight before I notice them).
But one need not invoke exotic architectures to get weird behavior
out of violating the rules of pointer subtraction. For example,
consider a "plain vanilla" system with nice linear addressing,
where pointers are just unadorned numeric addresses. Now try
this on for size:
typedef char[8] T;
T array[5];
printf ("%d\n", ptrInArrUnsafe(&array[0][1], array, 5));
It is quite likely (not certain, of course: undefined behavior
is undefined) that j will compute as zero inside the function,
leading the function to conclude that the pointer is valid.
The conclusion is utterly wrong, of course: the pointer aims
not at the start of a T object, but one byte past the start
of the first T object in the array.
My question is, do you experts in this group see any real problem with the second algorithm?
Yes, as explained above.
Alternatively, would there be a faster algorithm than the first one, that does not invoke undefined behaviour?
I cannot think of one. As CBF suggests, you should (a)
reexamine whether such a test is required, and if it is
you should (b) isolate the test to a systemdependent source
file, not intended to be portable.
 Er*********@sun.com
Ike Naar wrote:
.... snip ... 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.
I did say "possibly". It would depend on the optimization
capabilities of the compiler.

Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Ike Naar wrote:
.... snip ... 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.
I did say "possibly". It would depend on the optimization
capabilities of the compiler.

Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Hi Eric,
Eric Sosman <Er*********@sun.com> wrote:
: Ike Naar wrote:
:> int ptrInArrUnsafe(T *p,T *a,int max)
:> /* check whether p points to an element of a[max] */
:> {
:> int j=pa; /* possibly undefined */
:> return 0<=j && j<max && a+j==p;
:> }
:> [...]
:> 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.
: Disagree. Everything seems correct up to the semicolon,
: but after that things fall apart:
:  First, it is not necessarily the case that garbage will
: be stored in j. "Undefined behavior" is "undefined,"
: and does not necessarily result in storing anything at
: all anywhere at all.
Of course the implementation is free to do anything it wants after
undefined behaviour, but let's pretend that the damage is limited
to whatever is stored in j. If nothing is stored in j, fine. Perhaps
j retains its old value (whatever that was).
:  Second, even if something does get stored into j, it's
: not certain that the "something" will be recognizable
: as "garbage."
It seems that our notions of "garbage" differ.
My garbage can have any value.
: For example, the value zero might be
: stored into j, just as if you had called
: ptrInArrUnsafe(&array[0], array, 1)
:  ... and if this (or something like it) happens, the
: return expression will evaluate true, not false.
If 0<=j<max, the last conjuct (a+j==p) has to be false, due to the
initial assumption that p was not pointing to an element of a .
Conversely, if the return expression evaluates true there would
have been no undefined behaviour, since in that case there exists
an index j such that 0<=j<max and &a[j]==p (that's what the return
expression implies), i.e. p points to an element of a, and
the pointer subtraction (pa) would have been OK.
:> [...]
: But one need not invoke exotic architectures to get weird behavior
: out of violating the rules of pointer subtraction. For example,
: consider a "plain vanilla" system with nice linear addressing,
: where pointers are just unadorned numeric addresses. Now try
: this on for size:
: typedef char[8] T;
<nitpicking  this is C.L.C. after all, isn't it?>
typedef char T[8];
</nitpicking>
: T array[5];
: printf ("%d\n", ptrInArrUnsafe(&array[0][1], array, 5));
This is an extra complication that does not apply to the original problem
where p is supposed to have type T* . &array[0][1] is not a T* .
: It is quite likely (not certain, of course: undefined behavior
: is undefined) that j will compute as zero inside the function,
: leading the function to conclude that the pointer is valid.
: The conclusion is utterly wrong, of course: the pointer aims
: not at the start of a T object, but one byte past the start
: of the first T object in the array.
: 
: Er*********@sun.com

mail to ike at iae dot nl
Hi Eric,
Eric Sosman <Er*********@sun.com> wrote:
: Ike Naar wrote:
:> int ptrInArrUnsafe(T *p,T *a,int max)
:> /* check whether p points to an element of a[max] */
:> {
:> int j=pa; /* possibly undefined */
:> return 0<=j && j<max && a+j==p;
:> }
:> [...]
:> 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.
: Disagree. Everything seems correct up to the semicolon,
: but after that things fall apart:
:  First, it is not necessarily the case that garbage will
: be stored in j. "Undefined behavior" is "undefined,"
: and does not necessarily result in storing anything at
: all anywhere at all.
Of course the implementation is free to do anything it wants after
undefined behaviour, but let's pretend that the damage is limited
to whatever is stored in j. If nothing is stored in j, fine. Perhaps
j retains its old value (whatever that was).
:  Second, even if something does get stored into j, it's
: not certain that the "something" will be recognizable
: as "garbage."
It seems that our notions of "garbage" differ.
My garbage can have any value.
: For example, the value zero might be
: stored into j, just as if you had called
: ptrInArrUnsafe(&array[0], array, 1)
:  ... and if this (or something like it) happens, the
: return expression will evaluate true, not false.
If 0<=j<max, the last conjuct (a+j==p) has to be false, due to the
initial assumption that p was not pointing to an element of a .
Conversely, if the return expression evaluates true there would
have been no undefined behaviour, since in that case there exists
an index j such that 0<=j<max and &a[j]==p (that's what the return
expression implies), i.e. p points to an element of a, and
the pointer subtraction (pa) would have been OK.
:> [...]
: But one need not invoke exotic architectures to get weird behavior
: out of violating the rules of pointer subtraction. For example,
: consider a "plain vanilla" system with nice linear addressing,
: where pointers are just unadorned numeric addresses. Now try
: this on for size:
: typedef char[8] T;
<nitpicking  this is C.L.C. after all, isn't it?>
typedef char T[8];
</nitpicking>
: T array[5];
: printf ("%d\n", ptrInArrUnsafe(&array[0][1], array, 5));
This is an extra complication that does not apply to the original problem
where p is supposed to have type T* . &array[0][1] is not a T* .
: It is quite likely (not certain, of course: undefined behavior
: is undefined) that j will compute as zero inside the function,
: leading the function to conclude that the pointer is valid.
: The conclusion is utterly wrong, of course: the pointer aims
: not at the start of a T object, but one byte past the start
: of the first T object in the array.
: 
: Er*********@sun.com

mail to ike at iae dot nl
Ike Naar wrote: Hi Eric,
Eric Sosman <Er*********@sun.com> wrote: : Ike Naar wrote: :> int ptrInArrUnsafe(T *p,T *a,int max) :> /* check whether p points to an element of a[max] */ :> { :> int j=pa; /* possibly undefined */ :> return 0<=j && j<max && a+j==p; :> } :> :  ... and if this (or something like it) happens, the : return expression will evaluate true, not false.
If 0<=j<max, the last conjuct (a+j==p) has to be false, due to the initial assumption that p was not pointing to an element of a .
Ah, yes. Sorry about that; my reading comprehension
diminishes rapidly once the U.B. alarm bells start ringing.
Conversely, if the return expression evaluates true there would have been no undefined behaviour, since in that case there exists an index j such that 0<=j<max and &a[j]==p (that's what the return expression implies), i.e. p points to an element of a, and the pointer subtraction (pa) would have been OK.
:> [...] : But one need not invoke exotic architectures to get weird behavior : out of violating the rules of pointer subtraction. For example, : consider a "plain vanilla" system with nice linear addressing, : where pointers are just unadorned numeric addresses. Now try : this on for size:
: typedef char[8] T;
<nitpicking  this is C.L.C. after all, isn't it?> typedef char T[8]; </nitpicking>
Right again, and I've clearly become Javapolluted.
: T array[5]; : printf ("%d\n", ptrInArrUnsafe(&array[0][1], array, 5));
This is an extra complication that does not apply to the original problem where p is supposed to have type T* . &array[0][1] is not a T* .
Right again, but this time it was just an editing error.
I'd started with
(T*)((char*)array + 1)
.... and lost the cast when simplifying. The first argument
ought to have been
(T*)&array[0][1]
Now, there are lots of opportunities for things to go wrong
with this. The conversion to T* might garble the address 
but in the example I was assuming a "plain vanilla" machine
on which that wouldn't happen. The pointer subtraction in
the function is still likely to yield zero by (more or less)
subtracting the two addresses to get 1 and then rightshifting
by three bits. It is, I guess, unlikely that a "plain vanilla"
machine would decide that (T*)&array[0][1] and array[0]+0 are
equal  no guarantees, of course, but unlikely.
All in all, I'd say my attempt to express objections has
turned into an awful hash. Nonetheless ("Don't confuse me
with the facts; my mind is made up!") I'll still second CBF's
recommendation that shenanigans of this sort should be avoided,
or at the very least isolated.
 Er*********@sun.com
Ike Naar wrote: Hi Eric,
Eric Sosman <Er*********@sun.com> wrote: : Ike Naar wrote: :> int ptrInArrUnsafe(T *p,T *a,int max) :> /* check whether p points to an element of a[max] */ :> { :> int j=pa; /* possibly undefined */ :> return 0<=j && j<max && a+j==p; :> } :> :  ... and if this (or something like it) happens, the : return expression will evaluate true, not false.
If 0<=j<max, the last conjuct (a+j==p) has to be false, due to the initial assumption that p was not pointing to an element of a .
Ah, yes. Sorry about that; my reading comprehension
diminishes rapidly once the U.B. alarm bells start ringing.
Conversely, if the return expression evaluates true there would have been no undefined behaviour, since in that case there exists an index j such that 0<=j<max and &a[j]==p (that's what the return expression implies), i.e. p points to an element of a, and the pointer subtraction (pa) would have been OK.
:> [...] : But one need not invoke exotic architectures to get weird behavior : out of violating the rules of pointer subtraction. For example, : consider a "plain vanilla" system with nice linear addressing, : where pointers are just unadorned numeric addresses. Now try : this on for size:
: typedef char[8] T;
<nitpicking  this is C.L.C. after all, isn't it?> typedef char T[8]; </nitpicking>
Right again, and I've clearly become Javapolluted.
: T array[5]; : printf ("%d\n", ptrInArrUnsafe(&array[0][1], array, 5));
This is an extra complication that does not apply to the original problem where p is supposed to have type T* . &array[0][1] is not a T* .
Right again, but this time it was just an editing error.
I'd started with
(T*)((char*)array + 1)
.... and lost the cast when simplifying. The first argument
ought to have been
(T*)&array[0][1]
Now, there are lots of opportunities for things to go wrong
with this. The conversion to T* might garble the address 
but in the example I was assuming a "plain vanilla" machine
on which that wouldn't happen. The pointer subtraction in
the function is still likely to yield zero by (more or less)
subtracting the two addresses to get 1 and then rightshifting
by three bits. It is, I guess, unlikely that a "plain vanilla"
machine would decide that (T*)&array[0][1] and array[0]+0 are
equal  no guarantees, of course, but unlikely.
All in all, I'd say my attempt to express objections has
turned into an awful hash. Nonetheless ("Don't confuse me
with the facts; my mind is made up!") I'll still second CBF's
recommendation that shenanigans of this sort should be avoided,
or at the very least isolated.
 Er*********@sun.com
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[max1]) return 0; /* out */ if ( (pxax) % 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.
Bernhard Holzmayer <ho****************@deadspam.com> writes: Keith Thompson wrote:
Barry Schwarz <sc******@deloz.net> writes: [...] 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.
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 welldefined 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 highorder bits, and that pointertointeger pointertointeger is not enough. IMHO you have to use pointertolong which must be welldefined 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.
By "word pointer", I meant a pointer to a word. There's no necessary
relationship between a integer and a pointertointeger  and the
term "integer" includes all integer types, not just int.
The concrete example I have in mind is Cray vector systems. A machine
word is 64 bits; there are no instructions that operate directly on
8bit bytes. Nevertheless, the C implementation has CHAR_BIT==8, so
it needs to have a way to represent pointers to 8bit bytes.
An int* (int is 64 bits) is simply a word pointer with the obvious
representation. If you take an int*, treat it as a 64bit integer,
increment it, and convert it back to int*, the resulting pointer will
point to the 64bit word immediately following the original one.
A char* consists of a word pointer, pointing to the 64bit word
containing the byte, with a 3bit byte offset (value 0..7) stored in
the highorder 3 bits (which would otherwise be zero, since no such
system has a large enough address space to need them).

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"
Dik T. Winter wrote: In article <11****************@holzmayer.ifr.rt> ho****************@deadspam.com writes: ... > 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[max1]) return 0; /* out */ > if ( (pxax) % 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.
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.
Would you please try the following:
(long)(&a[7]) < (long)(&a[8])
this should give the correct result.
Reason for your strange behaviour is possibly the implicite type
cast, which converts a before adding.
Instead, the later version increments a as a pointer and then
converts it.
Bernhard
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[max1]) return 0; /* out */ if ( (pxax) % 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.
Bernhard
In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.org> wrote: By "word pointer", I meant a pointer to a word. There's no necessary relationship between a integer and a pointertointeger  and the term "integer" includes all integer types, not just int.
The concrete example I have in mind is Cray vector systems. A machine word is 64 bits; there are no instructions that operate directly on 8bit bytes. Nevertheless, the C implementation has CHAR_BIT==8, so it needs to have a way to represent pointers to 8bit bytes.
An int* (int is 64 bits) is simply a word pointer with the obvious representation. If you take an int*, treat it as a 64bit integer, increment it, and convert it back to int*, the resulting pointer will point to the 64bit word immediately following the original one.
A char* consists of a word pointer, pointing to the 64bit word containing the byte, with a 3bit byte offset (value 0..7) stored in the highorder 3 bits (which would otherwise be zero, since no such system has a large enough address space to need them).
Take a 16 bit x86 system, using the "huge" memory model: A pointer
consists of 16 bit segment and 16 bit offset. When the offset exceeds
65535, it wraps around to 0 and the segment is increased by eight. So it
can happen that
(unsigned long) p == 0x3241ffff
(unsigned long) (p+1) == 0x32490000
Doing pointer arithmetic on unsigned long would prove fatally wrong. In
the case above, if p and p+1 are both valid pointers to char objects,
then
* (char *) (((unsigned long) p) + 1) = '\0';
might crash your program. It will definitely not write to p [1].
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[max1]) return 0; /* out */ if ( (pxax) % 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. 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 */
/* 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 pa 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 ( (pa) % (&a[1]&a[0]))
return 0; /* not at element boundary*/
return 1; /* in and on element boundary */
}
Bernhard
Bernhard Holzmayer <ho****************@deadspam.com> wrote: Christian Bau wrote: Bernhard Holzmayer <ho****************@deadspam.com> wrote:
<snip> 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;
<snip> 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.
As has already been pointed out upthread (e.g. by pete in message
<40***********@mindspring.com>), it's implementationdefined if
pointer values are meaningfully representable in an object of _any_
integral type at all.
HTH
Regards

Irrwahn Grausewitz (ir*******@freenet.de)
welcome to clc: http://www.ungerhu.com/jxh/clc.welcome.txt
clc faqlist : http://www.faqs.org/faqs/Cfaq/faq/
clc OT guide : http://benpfaff.org/writings/clc/offtopic.html
pete wrote: Bernhard Holzmayer wrote:
IMHO you have to use pointertolong which must be welldefined 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 implementationdefined. 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?
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?
Bernhard Holzmayer 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[max1]) return 0; /* out */ if ( (pxax) % 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. 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;
ignore above line! /* as long as a points to a valid array, this is a legal test for the lower boundary*/ if (p<a) return 0; /*out */ /* 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);
ignore above line! /* as far as I understand, it's possible that pa 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.
Keith, would this hold on your Cray with the strange CHAR
representation, that pa still returns a reasonable result?
*/ if ( (pa) % (&a[1]&a[0])) return 0; /* not at element boundary*/
return 1; /* in and on element boundary */ }
Bernhard
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.
/* 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.
/* 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.
/* as far as I understand, it's possible that pa 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.
Although I never found a compiler doing this,
Then you only found nonconforming compilers up until now.
I replace sizeof(T) by a method which should work in both cases. */ if ( (pa) % (&a[1]&a[0]))
Since &a[1]&a[0] (==a+1a) always yields 1, the condition
is always false.
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
pointedto 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.
HTH
Regards

Irrwahn Grausewitz (ir*******@freenet.de)
welcome to clc: http://www.ungerhu.com/jxh/clc.welcome.txt
clc faqlist : http://www.faqs.org/faqs/Cfaq/faq/
clc OT guide : http://benpfaff.org/writings/clc/offtopic.html
Bernhard Holzmayer <ho****************@deadspam.com> writes: Dik T. Winter wrote:
In article <11****************@holzmayer.ifr.rt> ho****************@deadspam.com writes: ... > 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[max1]) return 0; /* out */ > if ( (pxax) % 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. 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. Would you please try the following: (long)(&a[7]) < (long)(&a[8])
The only difference between these expressions is that the first uses the
`>' operator, while the second uses the `<' operator. But `(long)(a+7)'
is exactly the same as `(long)(&a[7])' (likewise if both 7s are replaced
by 8s).
Also, trying something (in the sense of compiling and running it and
observing what it does) is a very flawed way to determine if something
is correct, as it does not necessarily give the right answer.
this should give the correct result.
The result of the conversion to `long' is implementationdefined, so it
cannot be correct on all possible implementations.
If `long' cannot represent the pointer value, the behavior is undefined.
Reason for your strange behaviour is possibly the implicite type cast,
C does not have implicit type casts. You mean conversion. :)
which converts a before adding.
There's no conversion before adding. This is the `+' operator between a
pointer and an integer type, which results in a pointer type.
Instead, the later version increments a as a pointer and then converts it.
So does the first.
Martin

,. Martin Dickopp, Dresden, Germany ,= ,_. =.
/ , ) http://www.zerobased.org/ ((_/)o o(\_))
\ `' `'(. .)`'
`. Debian, a variant of the GNU operating system. \_/ This discussion thread is closed Replies have been disabled for this discussion. Similar topics
2 posts
views
Thread by Asfand Yar Qazi 
last post: by

5 posts
views
Thread by Niks 
last post: by

27 posts
views
Thread by Riaan Cillié 
last post: by

9 posts
views
Thread by Arun Prasath 
last post: by

16 posts
views
Thread by aegis 
last post: by

33 posts
views
Thread by dough 
last post: by

41 posts
views
Thread by Alexei A. Frounze 
last post: by

10 posts
views
Thread by lovecreatesbeauty 
last post: by

11 posts
views
Thread by TefJlives 
last post: by

11 posts
views
Thread by Antoninus Twink 
last post: by
          