comparing ptrs/mmap

[Bill Pursell]

This question involves code relying on mmap, and thus
is not maximally portable. Undoubtedly, many will
complain that my question is not topical...

I have two pointers, the first of which is mmapped
to a single page. I want to determine if the second
is on the page. I'd like to do:

#include "platform_appropriate_definition_of_PAGESIZE.h "
int compare1(const char *a, const char *b)
{
return (b>=a && b-a < PAGESIZE);
}

but this is clearly not legal, since I'm comparing
pointers that may not be comparable.

I'm further tempted to something like:

int compare2(const void *a, const void *b)
{
return ( ((int)b & PAGE_MASK) == (int)a);
}

I believe compare2 will work on any platform which
satisfies sizeof (int) == sizeof (void *) and on which
one can provide a suitable definition of PAGE_MASK.

I want to know if there are any language issues
involved with compare2() of which I should be aware.
Also, is there a way to write compare1() that is safe?

Finally, where in the FAQ is the question:
when is it safe to compare pointers? My understanding
is that a < b is safe if a and b point into the same object,
but I don't find that in the FAQ anywhere.

--
Bill Pursell

[robertwessel2]

Bill Pursell wrote:

This question involves code relying on mmap, and thus
is not maximally portable. Undoubtedly, many will
complain that my question is not topical...

I have two pointers, the first of which is mmapped
to a single page. I want to determine if the second
is on the page. I'd like to do:

#include "platform_appropriate_definition_of_PAGESIZE.h "
int compare1(const char *a, const char *b)
{
return (b>=a && b-a < PAGESIZE);
}

but this is clearly not legal, since I'm comparing
pointers that may not be comparable.

I'm further tempted to something like:

int compare2(const void *a, const void *b)
{
return ( ((int)b & PAGE_MASK) == (int)a);
}

I believe compare2 will work on any platform which
satisfies sizeof (int) == sizeof (void *) and on which
one can provide a suitable definition of PAGE_MASK.

I want to know if there are any language issues
involved with compare2() of which I should be aware.
Also, is there a way to write compare1() that is safe?

Finally, where in the FAQ is the question:
when is it safe to compare pointers? My understanding
is that a < b is safe if a and b point into the same object,
but I don't find that in the FAQ anywhere.

While the OT mmap may introduce guarantees about the nature of
pointers, there are certainly platforms that do not implement pointers
in a way that would allow compare1() or compare2() to produce the
result you want. Perhaps the most familiar is x86 segmented
addressing, uncommon on 32 bit OS, but universal on older 16 bit OSs.
Such a pointer consists of a segment ID and offset within the specified
segment. The actual relationship between segments and pages is up to
the OS, and may be quite complex. Thus 1234:0123, 2345:0123 and
3456:9876 might refer to the same location, different locations on the
same page, or different pages entirely (assuming that the system has
pages).

And fundamentally, the result of casting a pointer to an int is
specifically not portable.

BTW, compare2() needs to mask the value on the right side of the
comparison too.

[Herbert Rosenau]

On Thu, 2 Nov 2006 06:57:18 UTC, "Bill Pursell"
<bi**********@gmail.comwrote:

This question involves code relying on mmap, and thus
is not maximally portable. Undoubtedly, many will
complain that my question is not topical...

I have two pointers, the first of which is mmapped
to a single page. I want to determine if the second
is on the page. I'd like to do:

#include "platform_appropriate_definition_of_PAGESIZE.h "
int compare1(const char *a, const char *b)
{
return (b>=a && b-a < PAGESIZE);
}

but this is clearly not legal, since I'm comparing
pointers that may not be comparable.

That is clearly absolutely legal. At least when the assumption the
whole procedure does is true that both pointers are referencing to the
same object.

I'm further tempted to something like:

int compare2(const void *a, const void *b)
{
return ( ((int)b & PAGE_MASK) == (int)a);
}

And that is absolutely illegal because there is nothing that can
guarantee that pointer can ever casted to int. compare() will work on
each system, compare2 ends in undefined behavior.

I believe compare2 will work on any platform which
satisfies sizeof (int) == sizeof (void *) and on which
one can provide a suitable definition of PAGE_MASK.

Nowhay. There is nothing that guaratees that size_t matches sizof
void* or even sizeof int. You're here deep inside the lands of
undefined behavior.

I want to know if there are any language issues
involved with compare2() of which I should be aware.
Also, is there a way to write compare1() that is safe?

The way you showed us is well defined on any system solong both
pointers are coming in as they should by the definition of the system.
When not there is absolutely no way you can work with any realtion of
both pointers.

Finally, where in the FAQ is the question:
when is it safe to compare pointers? My understanding
is that a < b is safe if a and b point into the same object,
but I don't find that in the FAQ anywhere.

That is guaranteed by the standard solong b points not outside the
last member of the object and a is inside the range of first and
last+1.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2 Deutsch ist da!

[Bill Pursell]

Herbert Rosenau wrote:

On Thu, 2 Nov 2006 06:57:18 UTC, "Bill Pursell"
<bi**********@gmail.comwrote:

I have two pointers, the first of which is mmapped
to a single page. I want to determine if the second
is on the page. I'd like to do:

#include "platform_appropriate_definition_of_PAGESIZE.h "
int compare1(const char *a, const char *b)
{
return (b>=a && b-a < PAGESIZE);
}

but this is clearly not legal, since I'm comparing
pointers that may not be comparable.

That is clearly absolutely legal. At least when the assumption the
whole procedure does is true that both pointers are referencing to the
same object.

I don't know if the pointers reference the same object, and
that's what I'm trying to cope with. I can remove the issue
of mmap from the thread and re-phrase the question this
way: suppose I have a list of objects and a pointer:

struct obj_list {
struct obj *data;
struct obj_list *next;
} list;

void *b;

I know that b lies in one of the objects, but I don't know
which one. How do I figure out which one it's in? The
obvious thing is to compare b with data for each data
pointer in the list ( b (void *)data && b < (void *)(data + 1)),
but that means that most of the comparisons
are being done on pointers that aren't in the same object.
--
Bill Pursell

[Herbert Rosenau]

On Thu, 2 Nov 2006 07:56:14 UTC, "ro***********@yahoo.com"
<ro***********@yahoo.comwrote:

While the OT mmap may introduce guarantees about the nature of
pointers, there are certainly platforms that do not implement pointers
in a way that would allow compare1() or compare2() to produce the
result you want.

Clearly wrong. compare1() is clearly standard conform and each C
Compiler that is itself a real C compiler, that means it is standard
conform will produce code that lets compare1() flawless until the
assumption the function does is fullifyed. No conforming C compiler
will ever guarantee that compar2() will not end in the lands of
undefined behavior.

Perhaps the most familiar is x86 segmented

Dosn't matter because compare1 is completely conforming.

addressing, uncommon on 32 bit OS, but universal on older 16 bit OSs.
Such a pointer consists of a segment ID and offset within the specified
segment. The actual relationship between segments and pages is up to
the OS, and may be quite complex. Thus 1234:0123, 2345:0123 and
3456:9876 might refer to the same location, different locations on the
same page, or different pages entirely (assuming that the system has
pages).

If the pointers are pointing inside the same array there is no problem
at all with compare1 - but always with compare2().

>
And fundamentally, the result of casting a pointer to an int is
specifically not portable.

Yepp.

BTW, compare2() needs to mask the value on the right side of the
comparison too.

And even then it is not conform.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2 Deutsch ist da!

[Walter Roberson]

In article <wm***************************@JUPITER1.PC-ROSENAU.DE>,
Herbert Rosenau <os****@pc-rosenau.dewrote:

>>>I have two pointers, the first of which is mmapped
to a single page. I want to determine if the second
is on the page. I'd like to do:

>>>#include "platform_appropriate_definition_of_PAGESIZE.h "
int compare1(const char *a, const char *b)
{
return (b>=a && b-a < PAGESIZE);
}

>Clearly wrong. compare1() is clearly standard conform and each C
Compiler that is itself a real C compiler, that means it is standard
conform will produce code that lets compare1() flawless until the
assumption the function does is fullifyed.

I seem to be stuck in a mental loop somewhere, somehow blind to
the standard conformance of compare1(). As it is clear to you, I
would appreciate you pointing out where my logic has gone wrong, or
which section of the standard that I am missing?

The original poster has two pointers, which are NOT necessarily to
the same object.

The compare1() function starts by attempting to compare the functions
using the >= operator. I can't seem to get out of my head that
in C89 the appropriate section of the standard is 3.3.8 "Relational
Operators".

The two types being compared via >= are the same, so there is no
violation of the Constraints subsection of 3.3.8, so we look at the
Semantics section. As the conformance of the code is clear to you,
I must be misreading or misinterpreting that section, as I keep
finding these sentances:

If the objects pointed to are not members of the same aggregate or
union object, the result is undefined, with the following exception.
If the expression P points to an element of an array object and the
expression Q points to the last element of the same array object,
the pointer expression Q+1 compares higher than P, even though Q+1
does not point to an elment of the array object.

Not pointers to the same object, "the result is undefined". Is the
original poster passing in pointers that are certain to be pointing to
the same object, or certain to be fall into the one exception? No. So
if the original poster passes in pointers to different objects, is the
code standard conforming? I, in my mental blindness, keep seeing that
"the result is undefined" section of the C89 standard. But Herbert
says the code is "clearly standard conform", so I must be missing
something.

Ah, I see a possibility: perhaps code can actively use an "undefined"
result, and yet still be standard conforming? Is that it, Herbert?
Are you saying that using a result that is apparently specifically
undefined according to the standard, still "clearly standard conform" ??
Is that where my mental block is, am I just hung up on thinking
that undefined results are *not* standard conforming?? Herbert, is
code that uses undefined behaviour standard conforming unless it
violates a Constraint??
--
All is vanity. -- Ecclesiastes

[Keith Thompson]

"Bill Pursell" <bi**********@gmail.comwrites:
[...]

I don't know if the pointers reference the same object, and
that's what I'm trying to cope with. I can remove the issue
of mmap from the thread and re-phrase the question this
way: suppose I have a list of objects and a pointer:

struct obj_list {
struct obj *data;
struct obj_list *next;
} list;

void *b;

I know that b lies in one of the objects, but I don't know
which one. How do I figure out which one it's in? The
obvious thing is to compare b with data for each data
pointer in the list ( b (void *)data && b < (void *)(data + 1)),
but that means that most of the comparisons
are being done on pointers that aren't in the same object.

Comparing two pointers using a relational operator (<, <=, >, >=)
invokes undefined behavior if the pointers do no point into the same
object or just past the end of it. But any pointers can safely be
compared for equality.

So if you have a collection of distinct objects, and you want to know
whether a given pointer points to, or within, or just past the end of,
one of them (and which one), you can treat each object as an array of
unsigned char and test the pointer for equality against a pointer to
each byte of each object. This avoids undefined behavior, but it's
obviously horrendously inefficient.

If you can live with a bit of undefined behavior, you can use "<" and
">" to see whether the pointer is within the range of addresses for
each object (2 comparisons per object rather than (sizeof obj)
comparisons per object); if you find an apparent match, you can then
confirm it with equality comparisons for each byte. This should work
as long as the undefined behavior of the "<" and ">" operators is no
worse than yielding a possibly incorrect result. Keep the code
isolated and well commented.

In either case, if you know that the pointer points only to a certain
location within the object (to the beginning, or to a certain member),
you can save a lot of effort.

(Or you can throw caution to the wind and assume a linear address
space; your code will probably work on most systems, and won't break
until the most inconvenient possible moment.)

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Clark S. Cox III]

Herbert Rosenau wrote:

On Thu, 2 Nov 2006 06:57:18 UTC, "Bill Pursell"
<bi**********@gmail.comwrote:

>This question involves code relying on mmap, and thus
is not maximally portable. Undoubtedly, many will
complain that my question is not topical...

I have two pointers, the first of which is mmapped
to a single page. I want to determine if the second
is on the page. I'd like to do:

#include "platform_appropriate_definition_of_PAGESIZE.h "
int compare1(const char *a, const char *b)
{
return (b>=a && b-a < PAGESIZE);
}

but this is clearly not legal, since I'm comparing
pointers that may not be comparable.

That is clearly absolutely legal. At least when the assumption the
whole procedure does is true that both pointers are referencing to the
same object.

Yes, but that is exactly the assumption that the OP said he couldn't
make. He doesn't know that they point into (or one past) the same
object. Therefore, compare1 is not legal. Seeing as he is using mmap,
there may be some other guarantees of the ability to compare pointers
given by POSIX or other appropriate standard. But, from a standard C
point of view he is invoking undefined behavior.

>I'm further tempted to something like:

int compare2(const void *a, const void *b)
{
return ( ((int)b & PAGE_MASK) == (int)a);
}

And that is absolutely illegal because there is nothing that can
guarantee that pointer can ever casted to int. compare() will work on
each system, compare2 ends in undefined behavior.

compare2 is implementation defined.

--
Clark S. Cox III
cl*******@gmail.com

[Walter Roberson]

In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.orgwrote:

>Comparing two pointers using a relational operator (<, <=, >, >=)
invokes undefined behavior if the pointers do no point into the same
object or just past the end of it. But any pointers can safely be
compared for equality.

That's not clear to me, looking at C89. 3.3.9 Equality Operators
specifies that "Where the operands have types and values suitable
for the relational operators, the semantics detailed in 3.3.8 apply".
3.3.8 on relational operators restricts the definedness of the
comparisons to pointers to the same object (or one past). 3.3.8
does specifically mention equality of pointers, in the paragraph
after saying the result of the relational comparison is undefined
if it isn't the same object (or one past).

C89 3.3.9 does give meaning to comparisons with NULL where 3.3.8
does not. The wording in 3.3.9 about equality of pointers is otherwise
substantially the same as the equality paragraph of 3.3.8. Two
null pointers compare equal. If two pointers compare equal, they
are both null pointers or both point to the same object, or both
point one past the last element of the same array object. But that
statement doesn't say that it is defined for two pointers to different
objects to be compared. So I would say that the reference to the
3.3.8 semantics is in force when not comparing to NULL, and thus that
the result of the equality test is undefined unless it is the same
object (or null or one past the same object.)

--
Programming is what happens while you're busy making other plans.

[Keith Thompson]

ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) writes:

In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.orgwrote:

>>Comparing two pointers using a relational operator (<, <=, >, >=)
invokes undefined behavior if the pointers do no point into the same
object or just past the end of it. But any pointers can safely be
compared for equality.

That's not clear to me, looking at C89. 3.3.9 Equality Operators
specifies that "Where the operands have types and values suitable
for the relational operators, the semantics detailed in 3.3.8 apply".
3.3.8 on relational operators restricts the definedness of the
comparisons to pointers to the same object (or one past). 3.3.8
does specifically mention equality of pointers, in the paragraph
after saying the result of the relational comparison is undefined
if it isn't the same object (or one past).

C89 3.3.9 does give meaning to comparisons with NULL where 3.3.8
does not. The wording in 3.3.9 about equality of pointers is otherwise
substantially the same as the equality paragraph of 3.3.8. Two
null pointers compare equal. If two pointers compare equal, they
are both null pointers or both point to the same object, or both
point one past the last element of the same array object. But that
statement doesn't say that it is defined for two pointers to different
objects to be compared. So I would say that the reference to the
3.3.8 semantics is in force when not comparing to NULL, and thus that
the result of the equality test is undefined unless it is the same
object (or null or one past the same object.)

It's not 100% clear to me either (from the C90 standard). But C99
makes it clearer. C99 6.5.9p3:

The == (equal to) and != (not equal to) operators are analogous to
the relational operators except for their lower precedence.91)
Each of the operators yields 1 if the specified relation is true
and 0 if it is false. The result has type int. For any pair of
operands, exactly one of the relations is true.

C99 6.5.9p6:

Two pointers compare equal if and only if both are null pointers,
both are pointers to the same object (including a pointer to an
object and a subobject at its beginning) or function, both are
pointers to one past the last element of the same array object, or
one is a pointer to one past the end of one array object and the
other is a pointer to the start of a different array object that
happens to immediately follow the first array object in the
address space.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Flash Gordon]

Clark S. Cox III wrote:

Herbert Rosenau wrote:

>On Thu, 2 Nov 2006 06:57:18 UTC, "Bill Pursell"
<bi**********@gmail.comwrote:

<snip>

>>I'm further tempted to something like:

int compare2(const void *a, const void *b)
{
return ( ((int)b & PAGE_MASK) == (int)a);
}

And that is absolutely illegal because there is nothing that can
guarantee that pointer can ever casted to int. compare() will work on
each system, compare2 ends in undefined behavior.

compare2 is implementation defined.

Where the implementation can define it as being undefined. Specifically,
int does not have to be large enough for a pointer to be converted to it
and if it is not the behaviour is, I believe, undefined.
--
Flash Gordon

[Herbert Rosenau]

On Thu, 2 Nov 2006 17:00:24 UTC, "Bill Pursell"
<bi**********@gmail.comwrote:

Herbert Rosenau wrote:

On Thu, 2 Nov 2006 06:57:18 UTC, "Bill Pursell"
<bi**********@gmail.comwrote:

>
I have two pointers, the first of which is mmapped
to a single page. I want to determine if the second
is on the page. I'd like to do:
>
#include "platform_appropriate_definition_of_PAGESIZE.h "
int compare1(const char *a, const char *b)
{
return (b>=a && b-a < PAGESIZE);
}
>
but this is clearly not legal, since I'm comparing
pointers that may not be comparable.

That is clearly absolutely legal. At least when the assumption the
whole procedure does is true that both pointers are referencing to the
same object.

I don't know if the pointers reference the same object, and
that's what I'm trying to cope with. I can remove the issue
of mmap from the thread and re-phrase the question this
way: suppose I have a list of objects and a pointer:

struct obj_list {
struct obj *data;
struct obj_list *next;
} list;

void *b;

I know that b lies in one of the objects, but I don't know
which one. How do I figure out which one it's in? The
obvious thing is to compare b with data for each data
pointer in the list ( b (void *)data && b < (void *)(data + 1)),
but that means that most of the comparisons
are being done on pointers that aren't in the same object.

You would compare the pointer you have with each pointer you get
walking through the list for equivality. That means using the operator
== or != but not <, <= or >, >= and you're always conforming to the
standard.

Assuming your list is setup thet that the last member has a null
pointer to flag that it is the last you'll can do it strictly
conforming easy:

struct obj_list *head = list;

struct obj_list *find_member(struct obj_list *member) {
struct obj_list *p = head;
if (!member) return NULL; /* no member given */
for (; p; p = p->next) {
if (p == member)
return p; /* found */
}
return NULL; /* member not in list or broken */
}
--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2 Deutsch ist da!

[Walter Roberson]

In article <wm***************************@JUPITER1.PC-ROSENAU.DE>,
Herbert Rosenau <os****@pc-rosenau.dewrote:

>On Thu, 2 Nov 2006 17:00:24 UTC, "Bill Pursell"
<bi**********@gmail.comwrote:

>I know that b lies in one of the objects, but I don't know
which one. How do I figure out which one it's in? The
obvious thing is to compare b with data for each data
pointer in the list ( b (void *)data && b < (void *)(data + 1)),
but that means that most of the comparisons
are being done on pointers that aren't in the same object.

>You would compare the pointer you have with each pointer you get
walking through the list for equivality. That means using the operator
== or != but not <, <= or >, >= and you're always conforming to the
standard.

Keith and I went over this a couple of days ago. Comparing pointers
into different objects has undefined results in C89, but defined
results in C99.
--
If you lie to the compiler, it will get its revenge. -- Henry Spencer

[Keith Thompson]

ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) writes:

In article <wm***************************@JUPITER1.PC-ROSENAU.DE>,
Herbert Rosenau <os****@pc-rosenau.dewrote:

>>On Thu, 2 Nov 2006 17:00:24 UTC, "Bill Pursell"
<bi**********@gmail.comwrote:

>>I know that b lies in one of the objects, but I don't know
which one. How do I figure out which one it's in? The
obvious thing is to compare b with data for each data
pointer in the list ( b (void *)data && b < (void *)(data + 1)),
but that means that most of the comparisons
are being done on pointers that aren't in the same object.

>>You would compare the pointer you have with each pointer you get
walking through the list for equivality. That means using the operator
== or != but not <, <= or >, >= and you're always conforming to the
standard.

Keith and I went over this a couple of days ago. Comparing pointers
into different objects has undefined results in C89, but defined
results in C99.

To be precise, relational operators (<, <=, >, >=) invoke undefined
behavior for pointers into different objects, but equality operators
(=, !=) are well defined.

I suspect that equality was meant to be well defined in C89, but the
standard may not have expressed it very well (or maybe I'm not reading
it very well).

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Herbert Rosenau]

On Thu, 2 Nov 2006 19:41:50 UTC, ro******@ibd.nrc-cnrc.gc.ca (Walter
Roberson) wrote:

In article <wm***************************@JUPITER1.PC-ROSENAU.DE>,
Herbert Rosenau <os****@pc-rosenau.dewrote:

>>I have two pointers, the first of which is mmapped
to a single page. I want to determine if the second
is on the page. I'd like to do:

>>#include "platform_appropriate_definition_of_PAGESIZE.h "
int compare1(const char *a, const char *b)
{
return (b>=a && b-a < PAGESIZE);
}

Clearly wrong. compare1() is clearly standard conform and each C
Compiler that is itself a real C compiler, that means it is standard
conform will produce code that lets compare1() flawless until the
assumption the function does is fullifyed.

I seem to be stuck in a mental loop somewhere, somehow blind to
the standard conformance of compare1(). As it is clear to you, I
would appreciate you pointing out where my logic has gone wrong, or
which section of the standard that I am missing?

O.k., also again:

Comparing 2 pointers whereas both are pointing inside the same object
are always legal.

int a[32000];
int b;

int *p1 = a; /* -first member of a */
int *p2 = &a[32000]; /* -last member +1 of a */
size_t i;

p1 < p2 /* legal as both pointers inside the allowed
range */
p2++; /* UB as p2 points too far behind the object */
p1 < p2 /* UB */
p2 = &a[31999]; /* p2 points now to the last object in that
array */
p1 <= p2 /* legal as both pointers are pointing inside
the same object */
i = p2 - p1; /* legal, result of subtraction of 2 pointers
pointing inside the same object. Result is
of type size_t */
p1 = &b;
p1 < p2 /* illegal as p1 points not to the same object as
p2 */
p1 p2 /* same */
p1 == p2 /* legal as comparing of equivalence is allowed
*/
p1 != p2 /* legal as comaring of not equivalent is allowed
*/

The original poster has two pointers, which are NOT necessarily to
the same object.

I wrote in my artikle that I assumed that both pointers must are
related together (as common practise is on such functions) to have it
always conforming.

The compare1() function starts by attempting to compare the functions
using the >= operator. I can't seem to get out of my head that
in C89 the appropriate section of the standard is 3.3.8 "Relational
Operators".

So you says that strcmp, memcmp and so on always illegal? The do
exactly that compareing 2 pointers not neccessary pointing to the same
object.

>
The two types being compared via >= are the same, so there is no
violation of the Constraints subsection of 3.3.8, so we look at the
Semantics section. As the conformance of the code is clear to you,
I must be misreading or misinterpreting that section, as I keep
finding these sentances:

When you compares 2 pointers of different types the compiler will
convert ones type to the other. But here the types are equal.

If the objects pointed to are not members of the same aggregate or
union object, the result is undefined, with the following exception.
If the expression P points to an element of an array object and the
expression Q points to the last element of the same array object,
the pointer expression Q+1 compares higher than P, even though Q+1
does not point to an elment of the array object.

Here you cites the standard. That is nothing els I sayed.

Not pointers to the same object, "the result is undefined". Is the
original poster passing in pointers that are certain to be pointing to
the same object, or certain to be fall into the one exception? No. So
if the original poster passes in pointers to different objects, is the
code standard conforming? I, in my mental blindness, keep seeing that
"the result is undefined" section of the C89 standard. But Herbert
says the code is "clearly standard conform", so I must be missing
something.

Hey, compare1 is the same as strcmp or memcmp. The function requires
that both pointers are inside the same object like the standard
functions does.

Ah, I see a possibility: perhaps code can actively use an "undefined"
result, and yet still be standard conforming? Is that it, Herbert?

No.

Are you saying that using a result that is apparently specifically
undefined according to the standard, still "clearly standard conform" ??

No.

Is that where my mental block is, am I just hung up on thinking
that undefined results are *not* standard conforming?? Herbert, is
code that uses undefined behaviour standard conforming unless it
violates a Constraint??

No. You should know that a function comparing 2 pointers of less or
greater still assumes that both are pointing to the same object. That
is the way C works.

Comparing unrelated pointers other than for (un)equal is always UB.
Comaring pointers related together is always strictly conforming.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2 Deutsch ist da!

[Flash Gordon]

Herbert Rosenau wrote:

On Thu, 2 Nov 2006 19:41:50 UTC, ro******@ibd.nrc-cnrc.gc.ca (Walter
Roberson) wrote:

>In article <wm***************************@JUPITER1.PC-ROSENAU.DE>,
Herbert Rosenau <os****@pc-rosenau.dewrote:

>>>>I have two pointers, the first of which is mmapped
to a single page. I want to determine if the second
is on the page. I'd like to do:
#include "platform_appropriate_definition_of_PAGESIZE.h "
int compare1(const char *a, const char *b)
{
return (b>=a && b-a < PAGESIZE);
}

>>Clearly wrong. compare1() is clearly standard conform and each C
Compiler that is itself a real C compiler, that means it is standard
conform will produce code that lets compare1() flawless until the
assumption the function does is fullifyed.

I seem to be stuck in a mental loop somewhere, somehow blind to
the standard conformance of compare1(). As it is clear to you, I
would appreciate you pointing out where my logic has gone wrong, or
which section of the standard that I am missing?

O.k., also again:

Comparing 2 pointers whereas both are pointing inside the same object
are always legal.

int a[32000];
int b;

int *p1 = a; /* -first member of a */
int *p2 = &a[32000]; /* -last member +1 of a */
size_t i;

p1 < p2 /* legal as both pointers inside the allowed
range */
p2++; /* UB as p2 points too far behind the object */
p1 < p2 /* UB */
p2 = &a[31999]; /* p2 points now to the last object in that
array */
p1 <= p2 /* legal as both pointers are pointing inside
the same object */
i = p2 - p1; /* legal, result of subtraction of 2 pointers
pointing inside the same object. Result is
of type size_t */

No it isn't size_t, if it was you could not get negative differences! It
is actually ptrdiff_t.

p1 = &b;
p1 < p2 /* illegal as p1 points not to the same object as
p2 */
p1 p2 /* same */
p1 == p2 /* legal as comparing of equivalence is allowed
*/
p1 != p2 /* legal as comaring of not equivalent is allowed
*/

The rest of this is all true as far as I can see.

>The original poster has two pointers, which are NOT necessarily to
the same object.

I wrote in my artikle that I assumed that both pointers must are
related together (as common practise is on such functions) to have it
always conforming.

However, that was not the problem the OP was trying to solve. I don't
think the following is t0o helpful to the OP:
|| If X can I do Y?
| Y is perfectly OK if !X

>The compare1() function starts by attempting to compare the functions
using the >= operator. I can't seem to get out of my head that
in C89 the appropriate section of the standard is 3.3.8 "Relational
Operators".

So you says that strcmp, memcmp and so on always illegal? The do
exactly that compareing 2 pointers not neccessary pointing to the same
object.

No, strcmp, memcmp etc compare what the pointers point to, not the pointers.

>The two types being compared via >= are the same, so there is no
violation of the Constraints subsection of 3.3.8, so we look at the
Semantics section. As the conformance of the code is clear to you,
I must be misreading or misinterpreting that section, as I keep
finding these sentances:

When you compares 2 pointers of different types the compiler will
convert ones type to the other. But here the types are equal.

> If the objects pointed to are not members of the same aggregate or
union object, the result is undefined, with the following exception.
If the expression P points to an element of an array object and the
expression Q points to the last element of the same array object,
the pointer expression Q+1 compares higher than P, even though Q+1
does not point to an elment of the array object.

Here you cites the standard. That is nothing els I sayed.

However, it is the reason that the OP can't do what he wanted. Because
for the OP the two pointer general are NOT to the same object, or 1 past
its end.

>Not pointers to the same object, "the result is undefined". Is the
original poster passing in pointers that are certain to be pointing to
the same object, or certain to be fall into the one exception? No. So
if the original poster passes in pointers to different objects, is the
code standard conforming? I, in my mental blindness, keep seeing that
"the result is undefined" section of the C89 standard. But Herbert
says the code is "clearly standard conform", so I must be missing
something.

Hey, compare1 is the same as strcmp or memcmp. The function requires
that both pointers are inside the same object like the standard
functions does.

No, compare1 is nothing like strcmp or memcmp. That is like saying
if (*p1 *p2)
is like
if (p1 p1)
Clearly one is undefined if either pointer is a null pointer the other
is undefined if the pointers do not point to the same object or one past
its end.

>Ah, I see a possibility: perhaps code can actively use an "undefined"
result, and yet still be standard conforming? Is that it, Herbert?

No.

>Are you saying that using a result that is apparently specifically
undefined according to the standard, still "clearly standard conform" ??

No.

>Is that where my mental block is, am I just hung up on thinking
that undefined results are *not* standard conforming?? Herbert, is
code that uses undefined behaviour standard conforming unless it
violates a Constraint??

No. You should know that a function comparing 2 pointers of less or
greater still assumes that both are pointing to the same object. That
is the way C works.

Comparing unrelated pointers other than for (un)equal is always UB.
Comaring pointers related together is always strictly conforming.

Well, the OP wanted a function for dealing with UNrelated pointers.
Therefore, when invoked as it is required to be used it invokes UB and
is *not* strictly conforming.
--
Flash Gordon

[Dave Thompson]

On Thu, 02 Nov 2006 20:31:44 GMT, Keith Thompson <ks***@mib.org>
wrote:

"Bill Pursell" <bi**********@gmail.comwrites:
[...]

I don't know if the pointers reference the same object, and
that's what I'm trying to cope with.

<snip other points>

If you can live with a bit of undefined behavior, you can use "<" and
">" to see whether the pointer is within the range of addresses for
each object (2 comparisons per object rather than (sizeof obj)
comparisons per object); if you find an apparent match, you can then
confirm it with equality comparisons for each byte. This should work
as long as the undefined behavior of the "<" and ">" operators is no
worse than yielding a possibly incorrect result. Keep the code
isolated and well commented.

If the UB is no worse than yielding false _positive_ matches. If it
gives false negatives, this fails. And I suspect in practice that for
the (relatively few) systems that don't satisfy:

(Or you can throw caution to the wind and assume a linear address
space; your code will probably work on most systems, and won't break
until the most inconvenient possible moment.)

.... false negatives are about as likely as false positives.

- David.Thompson1 at worldnet.att.net

[Keith Thompson]

Dave Thompson <da*************@worldnet.att.netwrites:

On Thu, 02 Nov 2006 20:31:44 GMT, Keith Thompson <ks***@mib.org>
wrote:

>"Bill Pursell" <bi**********@gmail.comwrites:
[...]

I don't know if the pointers reference the same object, and
that's what I'm trying to cope with.

<snip other points>

>If you can live with a bit of undefined behavior, you can use "<" and
">" to see whether the pointer is within the range of addresses for
each object (2 comparisons per object rather than (sizeof obj)
comparisons per object); if you find an apparent match, you can then
confirm it with equality comparisons for each byte. This should work
as long as the undefined behavior of the "<" and ">" operators is no
worse than yielding a possibly incorrect result. Keep the code
isolated and well commented.

If the UB is no worse than yielding false _positive_ matches. If it
gives false negatives, this fails. And I suspect in practice that for
the (relatively few) systems that don't satisfy:

False negatives aren't a problem if, as I said, you confirm with an
equality comparison for each byte.

Suppose ptr is some arbitrary pointer, and you want to know whether it
points to any byte within buf, declared as "char buf[SIZE];". Assume
that "<" and ">" pointer comparisons can yield incorrect results (and
nothing worse) in cases of undefined behavior.

If (ptr >= buf && ptr < buf+SIZE) yields false, you *know* that ptr
doesn't point to any byte of buf. (If it did, the comparisons would
have been well define, and the result would be true.) If it yields
true, it could be a false positive, but you can check for that by
comparing ptr to each address within buf with "==".

Alas, the effect of "<" and ">" on pointers to disjoint objects is not
limited to incorrect results.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Richard Tobin]

In article <b4********************************@4ax.com>,
Dave Thompson <da*************@worldnet.att.netwrote:

>If you can live with a bit of undefined behavior, you can use "<" and
">" to see whether the pointer is within the range of addresses for
each object (2 comparisons per object rather than (sizeof obj)
comparisons per object); if you find an apparent match, you can then
confirm it with equality comparisons for each byte.

>If the UB is no worse than yielding false _positive_ matches. If it
gives false negatives, this fails.

It can't give false negatives. If the pointer does point into the
object, the < and comparisons are not undefined, so they must give
the corect (positive) result.

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[Frederick Gotham]

Keith Thompson:

If (ptr >= buf && ptr < buf+SIZE) yields false, you *know* that ptr
doesn't point to any byte of buf.

I think a more generic/universal method would be to rely on the object
types:

#define BYTE_OF(obj,p) (\
(char const volatile*)(p) >= (char const volatile*)&(obj) \
&& (char const volatile*)(p) < (char const volatile*)(&(obj)+1) )
To get around the problem of multiple argument evaluation -- whilst still
making it thread-safe -- we could do something like:

#include <stddef.h>

int ByteOf(char const volatile *const pobj,size_t const len,
char const volatile *const p)
{
return p>=pobj && p < pobj+len;
}

#define BYTE_OF(obj,p) ByteOf((char const volatile*)&(obj),sizeof (obj),
(p))

I use "char const volatile" instead of plain old "char" to suppress any
potential compiler warnings.

(It was only after writing this entire post that I realised the code was
useless. Ah well.)

--

Frederick Gotham

[Dave Thompson]

On 20 Nov 2006 10:01:17 GMT, ri*****@cogsci.ed.ac.uk (Richard Tobin)
wrote:

In article <b4********************************@4ax.com>,
Dave Thompson <da*************@worldnet.att.netwrote:

If you can live with a bit of undefined behavior, you can use "<" and
">" to see whether the pointer is within the range of addresses for
each object (2 comparisons per object rather than (sizeof obj)
comparisons per object); if you find an apparent match, you can then
confirm it with equality comparisons for each byte.

If the UB is no worse than yielding false _positive_ matches. If it
gives false negatives, this fails.

It can't give false negatives. If the pointer does point into the
object, the < and comparisons are not undefined, so they must give
the corect (positive) result.

Oops! You're right, I didn't think that through.

- David.Thompson1 at worldnet.att.net