Thread View: comp.std.c++
4 messages
4 total messages
Started by John MAX Skaller
Sun, 20 Dec 1992 00:03
Pointer Comparisons
Author: John MAX Skaller
Date: Sun, 20 Dec 1992 00:03
Date: Sun, 20 Dec 1992 00:03
229 lines
7984 bytes
7984 bytes
On Pointer Comparisons
----------------------
I propose, not claiming to be the originator of any or all the ideas
here, that the issue of pointer comparisons be resolved as
follows.
1) If two pointers of the same type, (other than void*) compare equal,
then they may be assumed to refer to the same object, subobject,
or component.
Comment.
Allocations by 'new' of empty classes will then require at least one
byte of address space be wasted, otherwise
struct T {};
T* t1=new T;
T* t2=new T;
if(p==q)cout<<"p,q are same object");
gives a false diagnostic.
Inclusion of an empty class in a structure must also have this
property, as must allocations on the stack or in static storage.
The same is true for inheritance:
struct U : public T {};
struct V : public T {}
struct D : public U, public V { ... } d;
T* t1=(U*)&d;
T* t2=(V*)&d;
Alternative.
The alternative rule allows an exception if the classes are empty,
empty meaning either no data members, or better, no data members
and no virtual functions.
This alternative precludes use of empty classes solely to create
unique objects with no operations, but appears to have no other
serious consequences. Since nonempty classes can always be
used to artificially create unique object identities, this
alternative may be viable.
2) Let T be a type. A pointer to T, const T, volatile T, or
const volatile T is called an object pointer. Pointers
to array types are also object pointers.
The address of a function is a function pointer.
A void* is a void pointer.
A pointer obtained by operator new, or taking the address
of a static or auto object, or a pointer explicitly set to 0,
is a domestic pointer (value).
A pointer to a function with external linkage is a domestic
pointer (value).
A domestic pointer is valid if the object from which it was
derived continues to exist, otherwise it is said to dangle,
and is invalid, except that 0 pointers are considered valid.
(If nested functions are introduced, this rule also applied
to them. If dynamic linkage is used, this rule also applies to them)
A function or object pointer obtained by conversion, copying,
or assignment, of a valid domestic pointer is a valid domestic pointer
(except for conversion to void*, which is not a function or object
pointer).
If a (valid) member pointer is bound to a valid non-zero
object pointer, the result is a valid object pointer.
(Appropriate rules for pointers to objects in arrays need
to be included here, allowing for pointer arithmetic).
Two valid domestic pointers of the same type compare equal if they
point to the same object or function.
Two void* compare equal if they were derived from the two
valid domestic pointers that compare equal, and those
pointer values remain valid.
Comment.
These rules explicitly exclude 'foreign' pointers such as those
obtained by operating system calls. In this case the rules
may be obeyed or not, it is implementation defined.
The same applies to invalid pointers, since the memory may be
reclaimed, or the pointers themselves modified by a GC
or compaction algorithm.
3) Combination of (1) and (2) yield an equivalence between
object identity and pointer equality subject to the caveats
mentioned.
Therefore, the inequality operator will be defined by
a!=b <==> !(a==b)
with the same caveats.
Comment
The desired equivalence
a==b <==> a,b refer to the same object
a!=b <==> a,b refer to different objects
is subject to the 3 constraints:
a) nonempty class (if rule 1 alternative is taken)
b) validity (continued existence of the object pointed to)
c) domesticity (exclusion of mangling and foreign suppliers)
4) The operators <,>, <=,>= are implementation defined, unless
the arguments point into the same array or access components
of the same access section in a class, or both, in which
case they reflect the relative positions in the obvious
way (with caveats for empty classes).
(Additional caveats may have to be added here, esp regards
subobject ordering)
If the macro TOTALPTRORDER is defined, the standard pointer
comparisons provide a total order.
5) The standard library function
int ptrorder(void*,void*);
yields a total order as follows:
ptrorder(a,a)==0 (reflexive)
ptrorder(a,b)<0 ==> ptrorder(b,a)>0 (anti-commutative)
ptrorder(a,b)==0 ==> ptrorder(b,a)==0
ptrorder(a,b)<0 && ptrorder(b,c)<0 ==> ptrorder(a,c)<0 (transitive)
If the macro TOTALPTRORDER is defined, ptrorder must
provide the same ordering.
Comment.
ptrorder may return 0 for all arguments. It can be used in algorithms
not requiring any object identity, such as sorts, but not when
equality is required for a uniqeness such as for a b-tree.
6) Ptrorder0
Same as ptrorder, with the additional constraint
ptrorder0(0,a)==0 ==> a==0
Comment.
This function allows 0 to be distinguished. I'm not sure
how useful this is, and whether it should be required or
indicated by a macro variable.
7) ptrcmp
This function returns a total order compatible with ==
ptrcmp(a,b)==0 <==> a==b
It is implementation dependent whether this function is actually
provided or not, if it is, however, it must obey the above
semantics.
To facilitate detection the macro variable PTRCMP is defined
if ptrcmp is available for unrestricted calls, and not otherwise.
If ptrcmp is not available, the user may supply a ptrcmp routine,
which must have the above semantics.
Comment.
ptrcmp is used when object identity is important, for
example an efficient set implementation.
If ptrcmp is not available, it is an indication that in this
environment a client algorithm could not possibly work.
For example in the presence of an incremental compacter that
reordered objects in memory and updated the relevant pointers,
a set implemented by an ordered list could not work,
so the absence of ptrcmp is no loss.
Extension.
The functions
freezeptrcmp()
thawptrcmp()
may also be supplied in systems where pointers may be silently
modified.
The macro FREEZEPTRCMP is defined if these functions are defined.
If the macro PTRCMP is defined, freezing and thawing effects
efficiency only, calls to freezeptrcmp() and thawptrcmp() are optional.
If FREEZEPTRCMP is defined, but PTRCMP is not, then
calling freezeptrcmp() enables ptrcmp to yield a total
order.
After freezptrcmp() is called, the order may be lost.
The freeze function need not stop a compaction routine,
only prevent it destroying a total order.
If PTRCMP is not defined, freezing is mandatory during
sequences of calls to ptrcmp. Inappropriate calls
to ptrcmp may not work if correct freezing and thawing
strategy is not followed.
--
;----------------------------------------------------------------------
JOHN (MAX) SKALLER, maxtal@extro.ucc.su.oz.au
Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------
Re: Pointer Comparisons
Author: Johan Bengtsson
Date: Sun, 20 Dec 1992 21:03
Date: Sun, 20 Dec 1992 21:03
101 lines
4133 bytes
4133 bytes
John MAX Skaller (maxtal@extro.ucc.su.OZ.AU) wrote: : On Pointer Comparisons : ---------------------- : I propose [...] : 1) If two pointers of the same type, (other than void*) compare equal, : then they may be assumed to refer to the same object, subobject, : or component. : Comment. : Allocations by 'new' of empty classes will then require at least one : byte of address space be wasted, otherwise [...] : Inclusion of an empty class in a structure must also have this : property,[...] ==> Only if adjacent to another member with which it has a common base class. : Alternative. : The alternative rule allows an exception if the classes are empty, : empty meaning either no data members, or better, no data members : and no virtual functions. ==> "no virtual functions" is perhaps too restrictive, since that might unnecessarily preclude implementations that don't use the "vtbl" scheme, for example by tagging all pointers with the actual type, or using special hardware (e.g. associative memory). I think "no data members" must be enough to void all guarantees on pointer distinctness (in this alternative to rule (1)). : This alternative precludes use of empty classes solely to create : unique objects with no operations, but appears to have no other : serious consequences. Since nonempty classes can always be : used to artificially create unique object identities, this : alternative may be viable. ==> I would agree, but only for "vtbl" like implementations, since objects under future implementations may very well need zero storage, even if they have virtual functions. Since we do not wish to preclude future non-vtbl implementations (right?), I do _not_ think this alternate rule is a good one. I think the alternate rule (1) must be "You can't rely on pointer equivalence for classes that have no data members" disqualifying among others many abstract base classes (I know you John like MI mix-ins, many of those should be affected too). [...] [ definition of "domestic" pointers deleted ] : Two void* compare equal if they were derived from the two : valid domestic pointers that compare equal, and those : pointer values remain valid. ==> Two void* should also be allowed to compare equal in cases where they are not derived from two domestic pointers that compare equal, i.e. p1==p2 ==> (void*)p1==(void*)p2, but not the other way around. The reverse should only hold if (p1 == p2) is defined, assuming equality comparison is only defined if p1 and p2 are of the same type, or share a common base class. Also note that the common base class of p1 and p2 must not be an empty class (if the alternative rule (1) is adopted). : Comment : The desired equivalence : a==b <==> a,b refer to the same object : a!=b <==> a,b refer to different objects : is subject to the 3 constraints: : a) nonempty class (if rule 1 alternative is taken) : b) validity (continued existence of the object pointed to) : c) domesticity (exclusion of mangling and foreign suppliers) ==> I like the analysis, although I think constraint a) should be removed, since all classes with no data members must be considered "empty". -- -------------------------------------------------------------------------- | Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden | | Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490 | --------------------------------------------------------------------------
Re: Pointer Comparisons
Author: John MAX Skaller
Date: Wed, 23 Dec 1992 17:27
Date: Wed, 23 Dec 1992 17:27
138 lines
5266 bytes
5266 bytes
In article <5451@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
>John MAX Skaller (maxtal@extro.ucc.su.OZ.AU) wrote:
>
>: On Pointer Comparisons
>: ----------------------
[..]
>: Allocations by 'new' of empty classes will then require at least one
>: byte of address space be wasted, otherwise
>[...]
>: Inclusion of an empty class in a structure must also have this
>: property,[...]
>
>==> Only if adjacent to another member with which it has a common
> base class.
Can you have the size different depending ... Yes,
Ok, the size could be zero, and the position of the next object
might be adjusted if required and not otherwise.
>
>: Alternative.
>
>: The alternative rule allows an exception if the classes are empty,
>: empty meaning either no data members, or better, no data members
>: and no virtual functions.
>
>==> "no virtual functions" is perhaps too restrictive, since that
Yes.
> I think "no data members" must be enough to void all
> guarantees on pointer distinctness (in this alternative
> to rule (1)).
> I think the alternate rule (1) must be
>
> "You can't rely on pointer equivalence for classes that have
> no data members"
Fine.
>
> disqualifying among others many abstract base classes (I know
> you John like MI mix-ins, many of those should be affected too).
Well, that just means you want rule(1) and not rule(1A).
There has been disagreement on this so I didnt want to preempt the
outcome here by making a decision. But likely rule 1 will do
because ARM requires non-zero length objects doesnt it?
>
>[ definition of "domestic" pointers deleted ]
I think you mean "definition" of domestic pointers deleted :-)
>
>: Two void* compare equal if they were derived from the two
>: valid domestic pointers that compare equal, and those
>: pointer values remain valid.
>
>==> Two void* should also be allowed to compare equal in
you must mean "required" not "allowed" surely?
> cases where they are not derived from two domestic
> pointers that compare equal, i.e.
>
> p1==p2 ==> (void*)p1==(void*)p2,
Maybe. And maybe this rule is totally wrong!
Consider
class A {} class B : A {}
B* b=new B;
A* a=b;
a==b; // YES after implicit conversion of b to an A
(void*)a == (void*)b; // NO, they point different places
So I think unless I'm wrong here and right before this rule has to
be withdrawn :-(
>
> but not the other way around. The reverse should only hold
> if (p1 == p2) is defined, assuming equality comparison
> is only defined if p1 and p2 are of the same type, or share
> a common base class.
I assume you can only compare pointers of exactly the same
type. All other comparisons must convert one of the pointers first.
>
> Also note that the common base class of p1 and p2 must not
> be an empty class (if the alternative rule (1) is adopted).
>
>: Comment
>
>: The desired equivalence
>
>: a==b <==> a,b refer to the same object
>: a!=b <==> a,b refer to different objects
>
>: is subject to the 3 constraints:
>
>: a) nonempty class (if rule 1 alternative is taken)
>: b) validity (continued existence of the object pointed to)
>: c) domesticity (exclusion of mangling and foreign suppliers)
>
>==> I like the analysis, although I think constraint a) should
> be removed, since all classes with no data members must be
> considered "empty".
If "empty" classes are zero length, you need the caveat, otherwise
you dont.
I really dont know if this sort of thing is viable for the Standard.
The whole of this was to allow certain types of code to be
non-strictly conforming without being non-conforming.
In particular, it might perhaps *allow* vendor supplied
standard routines to muck with pointers without making
programs written using these features non-conforming.
(E.g. Borland and most DOS systems allow construction
and manipulation of pointers with language extensions.).
But I think really all bets might be off. You would
have to replace /pointer/ with /domestic pointer/
throughout most of the standard, eg
x->print(); // x has to be domestic
and what it might ome down to is that all pointers
are assumed domestic in the standard anyhow .. so there
is nothing really to say. Sigh. I'm learning.
Never thought comparing two pointers would be so
hard to understand .. I do it now and then with no great qualms :-)
--
;----------------------------------------------------------------------
JOHN (MAX) SKALLER, maxtal@extro.ucc.su.oz.au
Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------
Re: Pointer Comparisons
Author: Jim Adcock
Date: Thu, 24 Dec 1992 20:37
Date: Thu, 24 Dec 1992 20:37
38 lines
1591 bytes
1591 bytes
In article <1992Dec23.172735.15352@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
|ARM requires non-zero length objects doesnt it?
No, ARM does not make such a requirement. ARM requires sizeof(Ob) to
be greater than zero. And ARM requires new Ob to return a distinct address.
But this is not the same as requiring Ob to have non-zero length.
The basic underlying requirement is that the space that Ob takes as an
element of an array be greater than zero, so that pointers to different
elements in the array have different values. This can be achieved for
zero-length objects by requiring them to have at least one-byte trailing
alignment padding when placed in arrays. When used as a member of a structure,
the object wouldn't necessarily have the same padding and alignment
requirements. For example ARM *explicitly* makes no requirement of
implementations in the following example:
class A {};
class B
{
public:
A a1;
public:
A a2;
};
main()
{
B b;
A* p1 = &(b.a1);
A* p2 = &(b.a2);
if (p1 == p2)
cout << "its undefined according to ARM!\n";
else
cout << "boring case -- but still undefined behavior!\n";
return 0;
}
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads