473,890 Members | 1,360 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

pointer-in-array test

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
Nov 14 '05 #1
67 4506
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=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,

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?

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.
<http://cbfalconer.home .att.net> USE worldnet address!
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.
<http://cbfalconer.home .att.net> USE worldnet address!
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,

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?

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,

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?

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.

Similar topics

2
2346
by: Asfand Yar Qazi | last post by:
Hello. Partly for learning purposes, I have written a smart pointer class. Could you please tell me what's wrong with it? (I know there's something wrong with it, but just not what!) Note that, as well as reference counting the stored pointer, it also has the ability to be declared for incomplete types (I think). I.e.: struct Incomplete;
5
7283
by: Niks | last post by:
what is a void pointer?
27
2932
by: Riaan Cillié | last post by:
Hi I'm trying to learn C, but I am struggling with using scanf and a struct. I want to define a structure and declare a variable of that type in int main. This has to be passed to a function and its values have to read and returned from this function. How do you use gets() for this? I just can't figure it out. Here is a bit of code
9
3541
by: Arun Prasath | last post by:
Hi all, I have the following question regd pointer typecasting. Is the following type of pointer typecasting valid? #define ALLOC(type,num) ((type *)malloc(sizeof(type)*num)) /*begin code*/
16
2527
by: aegis | last post by:
Given the following: int a = 10; int *p; void *p1; unsigned char *p2; p = &a;
33
4906
by: dough | last post by:
Is it possible in C to declare and initialize a pointer that points to itself? Why or why not?
41
10081
by: Alexei A. Frounze | last post by:
Seems like, to make sure that a pointer doesn't point to an object/function, NULL (or simply 0) is good enough for both kind of pointers, data pointers and function pointers as per 6.3.2.3: 3 An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant.55) If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed...
10
2293
by: lovecreatesbeauty | last post by:
Why (type*)pointer isn't equal to *(type**)pointer, In the code snippet, it shows that: (int *) == (int **) , (int *) != (*(int **)) . Does type-casting change the address? or doesn't type-casting do anything? 1 int main(void)
11
3501
by: TefJlives | last post by:
Can someone please expain what is a NOP pointer, or give a good link? Thanks. Greg
11
1965
by: Antoninus Twink | last post by:
What's the correct syntax to define a function that returns a pointer to a function? Specifically, I'd like a function that takes an int, and returns a pointer to a function that takes an int and returns a string. I tried this: gchar *(*f(gint n))(gint) { /* logic here */ }
0
9819
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
11222
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10810
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
9625
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
7169
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5845
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
6041
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4674
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4270
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.