NetNews Usenet Archive 1992 #30/NN_1992_30.iso/spool/comp/std/cplus/1853

Text File | 1992-12-21 | 3.5 KB | 102 lines

Newsgroups: comp.std.c++
Path: sparky!uunet!munnari.oz.au!metro!extro.ucc.su.OZ.AU!maxtal
From: [e-mail] (John MAX Skaller)
Subject: Re: Zero-length structures and pointer comparisons
Message-ID: <[e-mail]>
Sender: [e-mail]
Nntp-Posting-Host: extro.ucc.su.oz.au
Organization: MAXTAL P/L C/- University Computing Centre, Sydney
References: <[e-mail]> <[e-mail]> <[e-mail]>
Date: Fri, 18 Dec 1992 19:56:47 GMT
Lines: 89

In article <[e-mail]> uunet.ca!frumious!pat writes:
>[e-mail] (John MAX Skaller) writes:
>|    I'm not yet convinced it need bear ANY relation to
>|    ==, !=, < etc on pointers.
>
>["it" == ptrcmp]
>
>
>Surely one would want to insist on
>
>   p == q   =>   ptrcmp(p,q) == 0
>
>If this weren't true, one wouldn't be able to use ptrcmp as a basis
>for organizing an ordered binary tree for searching.  Are there any
>likely-to-be-common uses of ptrcmp which don't need this assumption?

    Of course: sorts will work perfectly well, as will any
algorithm that doesnt require uniqueness.

    That means this 'unconstrained' version of ptrcmp,
which might well always return 0 as Jim Adcock suggested,
can always be implemented on any machine. Returning 0 always
is a perfectly well defined total order, even if it
makes all pointers look the same.
>
>Unfortunately, meeting this condition might be expensive on
>segmented architectures (according to the many other postings
>on this subject).
>

    Thats not the issue. It might be UNIMPLEMENTABLE on
some architectures. In fact, == is UNIMPLEMENTABLE in general
on the 386 in protected mode, given the sloppy definition
of 'same object' in the ARM. Its quite possible on the 386
to have two logical addresses which convert to the
same linear address, but NOT BE ABLE TO TELL THAT THIS IS THE CASE.
Because to tell implies access to the LDT/GDT and the typical
process is not able to read those tables. A special
operating system function would be required to do this,
and that would make C++ unimplementable on systems not
having this function.

    Now assuming we clean up the ARM definition, we have to
look at

    a == b <==> ptrcmp(a,b)==0

first, before worrying about preserving partial orders that <
may or may not be. I think the above can be done
when a==b is made sensible, but I'm not sure.

    The condition

    a<b <==> ptrcmp(a,b)<0

cannot posibly be acceptable, since no language
in the ARM requires < to be a partial order, or anything else.
(Except if a,b point into the same array).

>
>The converse,
>
>   ptrcmp(p,q) == 0   =>   p == q
>
>seems not quite as essential, but still very useful.  Can anyone
>describe an otherwise reasonable implementation of ptrcmp which
>would _not_ meet this condition?  If not, what's the harm in
>asking for it?
>

    If ptrcmp just compared bits, this might be possible.
But then Jims stipulation that ptrcmp might always return
0 could not hold, and without this possibility a total
order might not be obtainable.

    (Recall this was suggested because some underlying
compaction mechanism might move stuff in memory around,
and adjust the pointers. The we might have

    a<b at time t0
    a>b at time t1

if we just did bit comparisons)

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         [e-mail]
    Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------