473,883 Members | 1,527 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 4502
Bernhard Holzmayer <ho************ ****@deadspam.c om> 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 well-defined to allow reliably checking whether a
pointer points within an array.

Suppose a char* pointer consists of a word pointer with a byte
offset in the high-order bits, and that pointer-to-integer

pointer-to-integer is not enough.
IMHO you have to use pointer-to-long which must be well-defined
according to the standard, which means, that a long is big enough
to hold a pointer on that system. An integer might be too short.


By "word pointer", I meant a pointer to a word. There's no necessary
relationship between a integer and a pointer-to-integer -- 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
8-bit bytes. Nevertheless, the C implementation has CHAR_BIT==8, so
it needs to have a way to represent pointers to 8-bit 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 64-bit integer,
increment it, and convert it back to int*, the resulting pointer will
point to the 64-bit word immediately following the original one.

A char* consists of a word pointer, pointing to the 64-bit word
containing the byte, with a 3-bit byte offset (value 0..7) stored in
the high-order 3 bits (which would otherwise be zero, since no such
system has a large enough address space to need them).

--
Keith Thompson (The_Other_Keit h) 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"
Nov 14 '05 #41
Dik T. Winter wrote:
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.


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
Nov 14 '05 #42
Christian Bau wrote:
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.


Why. Please give arguments.

Bernhard
Nov 14 '05 #43
In article <ln************ @nuthaus.mib.or g>,
Keith Thompson <ks***@mib.or g> wrote:
By "word pointer", I meant a pointer to a word. There's no necessary
relationship between a integer and a pointer-to-integer -- 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
8-bit bytes. Nevertheless, the C implementation has CHAR_BIT==8, so
it needs to have a way to represent pointers to 8-bit 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 64-bit integer,
increment it, and convert it back to int*, the resulting pointer will
point to the 64-bit word immediately following the original one.

A char* consists of a word pointer, pointing to the 64-bit word
containing the byte, with a 3-bit byte offset (value 0..7) stored in
the high-order 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].
Nov 14 '05 #44
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[max-1]) return 0; /* out */
if ( (px-ax) % 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 p-a 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 ( (p-a) % (&a[1]-&a[0]))
return 0; /* not at element boundary*/

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

Bernhard
Nov 14 '05 #45
Bernhard Holzmayer <ho************ ****@deadspam.c om> wrote:
Christian Bau wrote:
Bernhard Holzmayer <ho************ ****@deadspam.c om> 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 implementation-defined if
pointer values are meaningfully representable in an object of _any_
integral type at all.

HTH
Regards
--
Irrwahn Grausewitz (ir*******@free net.de)
welcome to clc: http://www.ungerhu.com/jxh/clc.welcome.txt
clc faq-list : http://www.faqs.org/faqs/C-faq/faq/
clc OT guide : http://benpfaff.org/writings/clc/off-topic.html
Nov 14 '05 #46
pete wrote:
Bernhard Holzmayer wrote:
IMHO you have to use pointer-to-long which must be well-defined
according to the standard, which means, that a long is big enough
to hold a pointer on that system. An integer might be too short.


Whether or not a pointer can be converted to any integer type
is implementation defined.
The standard does not guarantee that relationships which hold
for two pointers, will also hold for their converted integer
values.

N869
6.3.2.3 Pointers
[#6] Any pointer type may be converted to an integer
[#type.
Except as previously specified, the result
is
implementation-defined. If the result cannot be
represented
in the integer type, the behavior is undefined. The
result need not be in the range of values of any integer
type.


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?


Nov 14 '05 #47
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[max-1]) return 0; /* out */
if ( (px-ax) % 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 p-a 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 p-a still returns a reasonable result?
*/ if ( (p-a) % (&a[1]-&a[0]))
return 0; /* not at element boundary*/

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

Bernhard

Nov 14 '05 #48
Bernhard Holzmayer <ho************ ****@deadspam.c om> 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 p-a 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 non-conforming compilers up until now.
I replace sizeof(T) by
a method which should work in both cases. */
if ( (p-a) % (&a[1]-&a[0]))
Since &a[1]-&a[0] (==a+1-a) 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
pointed-to 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*******@free net.de)
welcome to clc: http://www.ungerhu.com/jxh/clc.welcome.txt
clc faq-list : http://www.faqs.org/faqs/C-faq/faq/
clc OT guide : http://benpfaff.org/writings/clc/off-topic.html
Nov 14 '05 #49
Bernhard Holzmayer <ho************ ****@deadspam.c om> writes:
Dik T. Winter wrote:
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.


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 implementation-defined, 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.zero-based.org/ ((_/)o o(\_))
\ `-' `-'(. .)`-'
`-. Debian, a variant of the GNU operating system. \_/
Nov 14 '05 #50

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
7281
by: Niks | last post by:
what is a void pointer?
27
2931
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
2526
by: aegis | last post by:
Given the following: int a = 10; int *p; void *p1; unsigned char *p2; p = &a;
33
4904
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
10077
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
9932
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
9777
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,...
1
10833
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10405
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
9558
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
5782
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...
1
4602
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
4200
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3227
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.