Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #149807

Re: template(ish) qsort() function possible in language standard?

Show key headers only | View raw

mathog <dmathog@gmail.com> writes:
> Keith Thompson wrote:
>> mathog <dmathog@gmail.com> writes:
>> [...]
>>> In a similar vein, there is no memswap(), analogous to memcpy() or
>>> memmove(). For the example above:
>>>
>>>     memswap(*(p+k), *(p+k+size), sizeof(char));
>>>
>>> Dogma has it that memswap() isn't needed very often, so it need not be
>>> part of the language.  (Overlaps would also be an issue, with my vote
>>> being that overlaps would be a fatal error.)
>>
>> What exactly do you mean by "fatal error"?  Detecting overlap at
>> compile time is in general not possible.  Detecting overlap at run
>> time would add overhead; the compiler would have to generate code
>> to compare the addresses and size (almost certainly in a manner
>> that would not be guaranteed to work in user-written code).
>>
>> memcpy() has undefined behavior on overlap.
>>
>>      If copying takes place between objects that overlap, the behavior is
>>      undefined.
>>
>> If memswap() were standardized, it would make sense to do the same
>> thing.
>
> Yes, it would normally be a run time check.  The user can add a check
> before calling memswap() if it might be a problem, as when calling it
> with two pointers to arrays.  The compiler could catch some overlaps
> though and generate a warning if it can tell at compile time that
> memswap() may be called with an overlap.  Like:
>
>    memswap(array, array+M, array_element_size*N)
>
> if there is some execution path where M<N.

How can the user check in general whether the arrays overlap,
given that relational operators on pointers to distinct objects
have undefined behavior?

Sure, an implementation *can* perform a runtime check (and do what
if it fails?).  That's consistent with it having undefined behavior.

>> Note that memcpy()ing an object to itself has undefined behavior, though
>> I'd guess that it works as expected in most or all implementation
>
> memswap() a pointer to itself should do nothing except waste CPU
> cycles. At least that would be the case for any swap mechanism that
> uses a temporary intermediate value.  Agreed that memswap() two
> pointers that are offset with overlapping data would be undefined.

The standard *could* specify, as a special case, that memcpy()
or memswap() with two identical pointers has defined behavior.  It
currently doesn't do so; it just talks about "objects that overlap",
which implies that memcpy(arr, arr, size) has undefined behavior.
(Doing nothing is of course consistent with undefined behavior.)

Note that the xor swap trick fails if you use it to swap an object
with itself.  I doubt that xor would be a good way to implement
memswap(), so this might not matter, but it's something to consider.

[...]

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

template(ish) qsort() function possible in language standard? mathog <dmathog@gmail.com> - 2020-02-05 12:25 -0800
  Re: template(ish) qsort() function possible in language standard? Robert Wessel <robertwessel2@yahoo.com> - 2020-02-05 18:25 -0600
    Re: template(ish) qsort() function possible in language standard? mathog <dmathog@gmail.com> - 2020-02-06 10:02 -0800
      Re: template(ish) qsort() function possible in language standard? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-02-06 13:20 -0800
        Re: template(ish) qsort() function possible in language standard? mathog <dmathog@gmail.com> - 2020-02-06 15:24 -0800
          Re: template(ish) qsort() function possible in language standard? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-02-06 15:38 -0800
  Re: template(ish) qsort() function possible in language standard? Bonita Montero <Bonita.Montero@gmail.com> - 2020-02-06 20:56 +0100
  Re: template(ish) qsort() function possible in language standard? Anton Shepelev <anton.txt@gmail.com> - 2020-02-08 17:50 +0300

csiph-web