473,883 Members | 1,769 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
67 4503
In article <11************ ****@holzmayer. ifr.rt> ho************* ***@deadspam.co m 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[max-1]) return 0; /* out */
if ( (px-ax) % sizeof(T)) return 0; /* not at element start*/
return 1; /* in and on element start */
}

compiles, links, runs without problems with my gcc.
And, as far as I remember, it's legal, to compare pointers after
conversion to long.


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/
Nov 14 '05 #31
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=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.
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, 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).
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)
re-examine whether such a test is required, and if it is
you should (b) isolate the test to a system-dependent source
file, not intended to be portable.

--
Er*********@sun .com
Nov 14 '05 #32
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=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.
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, 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).
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)
re-examine whether such a test is required, and if it is
you should (b) isolate the test to a system-dependent source
file, not intended to be portable.

--
Er*********@sun .com
Nov 14 '05 #33
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********@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 #34
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********@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 #35
Hi Eric,

Eric Sosman <Er*********@su n.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=p-a; /* 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 (p-a) 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
Nov 14 '05 #36
Hi Eric,

Eric Sosman <Er*********@su n.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=p-a; /* 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 (p-a) 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
Nov 14 '05 #37
Ike Naar wrote:

Hi Eric,

Eric Sosman <Er*********@su n.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=p-a; /* 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 (p-a) 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 Java-polluted.
: 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*)arr ay + 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 right-shifting
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
Nov 14 '05 #38
Ike Naar wrote:

Hi Eric,

Eric Sosman <Er*********@su n.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=p-a; /* 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 (p-a) 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 Java-polluted.
: 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*)arr ay + 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 right-shifting
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
Nov 14 '05 #39
In article <11************ ****@holzmayer. ifr.rt>,
Bernhard Holzmayer <ho************ ****@deadspam.c om> 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[max-1]) return 0; /* out */
if ( (px-ax) % sizeof(T)) return 0; /* not at element start*/
return 1; /* in and on element start */
}

compiles, links, runs without problems with my gcc.
And, as far as I remember, it's legal, to compare pointers after
conversion to long.


It just isn't guaranteed to produce any meaningful result.
Nov 14 '05 #40

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
7282
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
3540
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
4905
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
10080
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
9944
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
11153
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
10757
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
9583
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...
1
7975
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
7134
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
6002
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
2
4225
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3239
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

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.