Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Keith Thompson <Keith.S.Thompson+u@gmail.com>
Newsgroups: comp.lang.c
Subject: Re: Baby X is bor nagain
Date: Thu, 20 Jun 2024 14:57:04 -0700
Organization: None to speak of
Lines: 51
Message-ID: <87msnfwa4v.fsf@nosuchdomain.example.com>
References: <v494f9$von8$1@dont-email.me> <v4emki$28d1b$1@dont-email.me>
	<20240613174354.00005498@yahoo.com> <v4okn9$flpo$2@dont-email.me>
	<20240617002924.597@kylheku.com> <v4pddb$m5th$1@dont-email.me>
	<20240618115650.00006e3f@yahoo.com> <v4rv0o$1b7h1$1@dont-email.me>
	<20240618184026.000046e1@yahoo.com> <v4sd75$1ed31$1@dont-email.me>
	<877celzx14.fsf@nosuchdomain.example.com>
	<v4u85k$1t2pu$2@dont-email.me> <v4ucmn$1u14i$1@dont-email.me>
	<v4v2br$22c0m$1@dont-email.me> <v4v5nu$230rh$2@dont-email.me>
	<v4vfrn$24rv6$1@dont-email.me> <v50n9s$2fkko$1@dont-email.me>
	<v50poh$2g4ha$1@dont-email.me> <87iky3svqh.fsf@bsb.me.uk>
	<874j9nxsdy.fsf@nosuchdomain.example.com> <874j9ns382.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Thu, 20 Jun 2024 23:57:05 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="b9721cdd33060f6c797cf39cb31eeba2";
	logging-data="2908867"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/Xv08zRM0637WoYfhdtTJG"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.2 (gnu/linux)
Cancel-Lock: sha1:wwgxywE7G+M3C0Pjr91KlQ97VEs=
	sha1:yuAu+JLpcbkmdnjGjAYJr2aIyko=
Bytes: 4095

Ben Bacarisse <ben@bsb.me.uk> writes:
> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>> Ben Bacarisse <ben@bsb.me.uk> writes:
>> [...]
>>> On a C language point, I don't think the standard says anything about
>>> sorting with non-order functions like the one above.  Is an
>>> implementation of qsort permitted to misbehave (for example by not
>>> terminating) when the comparison function does not implement a proper
>>> order relation?
>>
>> N1570 7.22.5p4 (applies to bsearch and qsort):
>> """
>> When the same objects (consisting of size bytes, irrespective of
>> their current positions in the array) are passed more than once to
>> the comparison function, the results shall be consistent with one
>> another. That is, for qsort they shall define a total ordering on
>> the array, and for bsearch the same object shall always compare
>> the same way with the key.
>> """
>>
>> That's a "shall" outside a constraint, so violating it results in
>> undefined behavior.
>
> I think it should be clearer.  What the "that is" phrase seems to
> clarify in no way implies a total order, merely that the repeated
> comparisons or the same elements are consistent with one another.  That
> the comparison function defines a total order on the elements is, to me,
> a major extra constraint that should not be written as an apparent
> clarification to something the does not imply it: repeated calls should
> be consistent with one another and, in addition, a total order should be
> imposed on the elements present.

I agree.  The "That is, " should be dropped.

The most obvious meaning of the first sentence is that compar(A, B) must
yield the same result every time it's called (different positive values
are presumably meant to be "consistent", though that also could be
clearer), and that doesn't imply a total ordering.  That requirement is
sufficient for bsearch().

The standard states the requirements correctly, but it's incorrect in
claiming that the second sentence logically follows from the first.

It's possible that the authors intended the first sentence to require a
total ordering.  That depends on a strained interpretation of "same
objects", so it would apply to something like compar(A, B) vs. compar(B, C)
vs. compar(C, A), not allowing all three to return a negative result.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */