From 5709694001042586550 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f78e5,e94695845965b249 X-Google-Attributes: gidf78e5,public X-Google-ArrivalTime: 1992-12-19 15:59:34 PST Newsgroups: comp.std.c++ Path: sparky!uunet!munnari.oz.au!metro!extro.ucc.su.OZ.AU!maxtal From: maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) Subject: Re: Zero-length structures and pointer comparisons Message-ID: <1992Dec18.195647.20074@ucc.su.OZ.AU> Sender: news@ucc.su.OZ.AU Nntp-Posting-Host: extro.ucc.su.oz.au Organization: MAXTAL P/L C/- University Computing Centre, Sydney References: <1992Dec14.225659.24225@microsoft.com> <1992Dec16.150144.6004@ucc.su.OZ.AU> Date: Fri, 18 Dec 1992 19:56:47 GMT Lines: 89 In article uunet.ca!frumious!pat writes: >maxtal@extro.ucc.su.OZ.AU (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 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 ab at time t1 if we just did bit comparisons) -- ;---------------------------------------------------------------------- JOHN (MAX) SKALLER, maxtal@extro.ucc.su.oz.au Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA ;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------