473,890 Members | 1,360 Online

pointer-in-array test

Hi,

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?

Ike
Nov 14 '05 #1
67 4506
On Wed, 07 Apr 2004 02:17:47 GMT, Ike Naar <no****@nospam. invalid>
wrote:
Hi,

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?

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>>
Nov 14 '05 #2
On Wed, 07 Apr 2004 02:17:47 GMT, Ike Naar <no****@nospam. invalid>
wrote:
Hi,

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?

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>>
Nov 14 '05 #3
Ike Naar wrote:

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

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

Obviously, this algorithm is terribly slow for large max.

A more efficient algorithm is

int ptrInArrUnsafe( T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
int j=p-a; /* possibly undefined */
return 0<=j && j<max && a+j==p;
}
.... snip ...
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 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 (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
Nov 14 '05 #4
Ike Naar wrote:

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

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

Obviously, this algorithm is terribly slow for large max.

A more efficient algorithm is

int ptrInArrUnsafe( T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
int j=p-a; /* possibly undefined */
return 0<=j && j<max && a+j==p;
}
.... snip ...
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 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 (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
Nov 14 '05 #5
Barry Schwarz <sc******@deloz .net> writes:
On Wed, 07 Apr 2004 02:17:47 GMT, Ike Naar <no****@nospam. invalid>
wrote:
Hi,

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?

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 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. \_/
Nov 14 '05 #6
Barry Schwarz <sc******@deloz .net> writes:
On Wed, 07 Apr 2004 02:17:47 GMT, Ike Naar <no****@nospam. invalid>
wrote:
Hi,

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?

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 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. \_/
Nov 14 '05 #7
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[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

Nov 14 '05 #8
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[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

Nov 14 '05 #9
Bernhard Holzmayer <ho************ ****@deadspam.c om> 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[max-1]) return 0; /* out */

So does this.

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

This thread has been closed and replies have been disabled. Please start a new discussion.