🚀 go-pugleaf

  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 ------------------