Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   qsort (http://www.velocityreviews.com/forums/t632512-qsort.html)

 Ron Ford 08-27-2008 01:59 AM

qsort

Is qsort an intrinsic for C?
--
We must respect the other fellow's religion, but only in the sense and to
the extent that we respect his theory that his wife is beautiful and his
children smart. 5
H. L. Mencken

 Ron Ford 08-27-2008 02:47 AM

Re: qsort

On Tue, 26 Aug 2008 22:05:01 -0400, Eric Sosman posted:

> Ron Ford wrote:
>>
>> Is qsort an intrinsic for C?

>
> qsort() is a function in C's Standard library, available
> for use in all hosted implementations.
>
> What's an "intrinsic?"

An intrinsic is something that comes with the food in a given syntax.

One of my intrinsics is that I like Hillary. Your mileage may vary.

I don't see qsort in K&R as I leaf through or in the index. Did I
photograph the wrong target when I thought to have read of qsort in K&R?
--
We are here and it is now. Further than that, all human knowledge is
moonshine. 3
H. L. Mencken

 vippstar@gmail.com 08-27-2008 02:55 AM

Re: qsort

On Aug 27, 5:47 am, Ron Ford <r...@example.invalid> wrote:
> On Tue, 26 Aug 2008 22:05:01 -0400, Eric Sosman posted:
>
> > Ron Ford wrote:

>
> >> Is qsort an intrinsic for C?

>
> > qsort() is a function in C's Standard library, available
> > for use in all hosted implementations.

>
> > What's an "intrinsic?"

>
> An intrinsic is something that comes with the food in a given syntax.

No it's not.

> One of my intrinsics is that I like Hillary. Your mileage may vary.

Nonsense.

> I don't see qsort in K&R as I leaf through or in the index. Did I
> photograph the wrong target when I thought to have read of qsort in K&R?

Photograph the wrong target? nonsense.
Which K&R? See Appendix B in K&R2.

 Ron Ford 08-27-2008 04:10 AM

Re: qsort

On Tue, 26 Aug 2008 19:55:00 -0700 (PDT), vippstar@gmail.com posted:

> On Aug 27, 5:47 am, Ron Ford <r...@example.invalid> wrote:
>> On Tue, 26 Aug 2008 22:05:01 -0400, Eric Sosman posted:
>>
>>> Ron Ford wrote:

>>
>>>> Is qsort an intrinsic for C?

>>
>>> qsort() is a function in C's Standard library, available
>>> for use in all hosted implementations.

>>
>>> What's an "intrinsic?"

>>
>> An intrinsic is something that comes with the food in a given syntax.

>
> No it's not.
>
>> One of my intrinsics is that I like Hillary. Your mileage may vary.

>
> Nonsense.
>
>> I don't see qsort in K&R as I leaf through or in the index. Did I
>> photograph the wrong target when I thought to have read of qsort in K&R?

>
> Photograph the wrong target? nonsense.
> Which K&R? See Appendix B in K&R2.

So we have vippstar, who broke his clc cherry to respond to me.

The appendices in K&R are numbered.

--
H. L. Mencken

 Ian Collins 08-27-2008 04:15 AM

Re: qsort

Ron Ford wrote:
>
> The appendices in K&R are numbered.
>

In hex maybe, but certainly not in decimal.

--
Ian Collins.

 Ron Ford 08-27-2008 07:39 AM

Re: qsort

On Wed, 27 Aug 2008 08:56:11 +0200, Sensei posted:

> On 2008-08-27 06:10:21 +0200, Ron Ford <ron@example.invalid> said:
>
>>>> I don't see qsort in K&R as I leaf through or in the index. Did I
>>>> photograph the wrong target when I thought to have read of qsort in K&R?
>>>
>>> Photograph the wrong target? nonsense.
>>> Which K&R? See Appendix B in K&R2.

>>
>> So we have vippstar, who broke his clc cherry to respond to me.
>>
>> The appendices in K&R are numbered.
>>

>
> If by "number" you mean A, B, and C then yes. My own K&R second edition
> shows nice "qsort function" and "qsort library function" lines in the
> index at the end of the book.

I see it now, beginning §4.10.

Dankenstein,
--
When a new source of taxation is found it never means, in practice, that
the old source is abandoned. It merely means that the politicians have two
ways of milking the taxpayer where they had one before. 8
H. L. Mencken

 Richard Bos 08-27-2008 09:51 AM

Re: qsort

cri@tiac.net (Richard Harter) wrote:

> On Tue, 26 Aug 2008 22:05:01 -0400, Eric Sosman
>
> >Ron Ford wrote:
> >>
> >> Is qsort an intrinsic for C?

> > What's an "intrinsic?"

>
> The term is used in Fortran and elsewhere; it means that the
> function in question is an intrinsic part of the language in
> contrast to being part of a library.

"A" library, or _the_ Standard Library? Languages which use the term
"intrinsic" usually don't distinguish between those two. C does.

> So, no, qsort is not an intrinsic; if it were you wouldn't need
> to include stdlib.h nor would you need to link in the standard
> library.

OTOH, qsort _is_ an intrinsic; if it weren't, you couldn't depend on it
existing in every conforming hosted implementation, on any system.

> Nor could you write your own qsort and use it, either by omitting to
> include stdlib.h, or by simply replacing qsort in the standard library.

Guess what: despite the shoot-your-own-foot permission some
implementations may give you, the Standard doesn't guarantee that you
can do that, either.

Richard

 Chris Torek 08-27-2008 07:34 PM

Re: qsort

In article <48b57c3e.695125859@news.sbtc.net>
Richard Harter <cri@tiac.net> wrote:
>You can have intrinsics and still have a standard library. Some
>languages do. Regardless, if something is an intrinsic you don't
>need a library to get it.

That last seems like an odd statement to me, given that (e.g.) the
Fortran systems I have used have relied on a library (the one
automatically included by the "fort" or "f66" or "f77" or whatever
front-end command) to supply the code for most of the various
intrinsics.

(For that matter, the "standard C library" normally does not require
special link options when using the usual front-end commands. The
"-lm" flag to cc/gcc is the glaring annoying exception to this rule.)

>>Guess what: despite the shoot-your-own-foot permission some
>>implementations may give you, the Standard doesn't guarantee that you
>>can [use your own qsort], either.

>
>Quite true, but beside the point. It is not even potentially
>possible for intrinsics, since they aren't in libraries.

Again, in a number of those Fortran systems, it was easy to use
object or library file to the link line (as the default Fortran
library was linked at the end). As in C, this was rarely if ever
officially supported, and sometimes the call you expected got
short-circuited, so (just as with C systems) you had to know what
you were doing. But it was more than just "potentially possible":
sometimes we even did it (to use special instructions, or work
around an implementation bug).
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: gmail (figure it out) http://web.torek.net/torek/index.html

 Ron Ford 09-03-2008 04:00 AM

Re: qsort

On 27 Aug 2008 19:34:20 GMT, Chris Torek posted:

> In article <48b57c3e.695125859@news.sbtc.net>
> Richard Harter <cri@tiac.net> wrote:
>>You can have intrinsics and still have a standard library. Some
>>languages do. Regardless, if something is an intrinsic you don't
>>need a library to get it.

>
> That last seems like an odd statement to me, given that (e.g.) the
> Fortran systems I have used have relied on a library (the one
> automatically included by the "fort" or "f66" or "f77" or whatever
> front-end command) to supply the code for most of the various
> intrinsics.
>
> (For that matter, the "standard C library" normally does not require
> special link options when using the usual front-end commands. The
> "-lm" flag to cc/gcc is the glaring annoying exception to this rule.)

Thanks, Chris, there is definitely a useful contrast here between C and the
common extension that is fortran. I'm reconfiguring my mingw C capability
but think I can call qsort from another syntax. Since C is likely to be
under the hood of many syntaxes that can call C, I wanted to see how to do
this thing that I think is important.

Calling it from a place without every C99 guarantee is a bit of a trick:

%- > Is qsort an intrinsic for C?
%-
%- Yes, but despite the name it isn't guaranteed to
%- implement quicksort.
%-
%- The advantage is that it can sort an array of any kind
%- of data structure given a pointer to the array (usual
%- for C), the length, the length of each array element
%- (which must be in contiguous storage), and a comparison
%- function. The comparison function is given pointers to
%- two elements and returns a positive, zero, or negative
%- value if the first is greater then, equal to, or less
%- than the second. With the appropriate compare function
%- the array can be an array of pointers, or structures
%- containing pointers.
%-
%- To do that in Fortran 2003 might also require a routine
%- to copy such array elements.

Is Glen (quoted) correct?

>
>>>Guess what: despite the shoot-your-own-foot permission some
>>>implementations may give you, the Standard doesn't guarantee that you
>>>can [use your own qsort], either.

>>
>>Quite true, but beside the point. It is not even potentially
>>possible for intrinsics, since they aren't in libraries.

>
> Again, in a number of those Fortran systems, it was easy to use
> object or library file to the link line (as the default Fortran
> library was linked at the end). As in C, this was rarely if ever
> officially supported, and sometimes the call you expected got
> short-circuited, so (just as with C systems) you had to know what
> you were doing. But it was more than just "potentially possible":
> sometimes we even did it (to use special instructions, or work
> around an implementation bug).

I guess the notion of keyword is less sacred in the non C world. They say
you just change what the linker finds first.
--
What men value in this world is not rights but privileges. 7
H. L. Mencken

 Chris Torek 09-05-2008 05:25 AM

Re: qsort

>> In article <48b57c3e.695125859@news.sbtc.net>
>> Richard Harter <cri@tiac.net> wrote:
>>>You can have intrinsics and still have a standard library. Some
>>>languages do. Regardless, if something is an intrinsic you don't
>>>need a library to get it.

>On 27 Aug 2008 19:34:20 GMT, Chris Torek posted:
>> That last seems like an odd statement to me ...

In article <1kgfdwp8e1f62.dlg@example.invalid>
Ron Ford <ron@example.invalid> wrote:
>Thanks, Chris, there is definitely a useful contrast here between C and the
>common extension that is fortran. I'm reconfiguring my mingw C capability
>but think I can call qsort from another syntax. Since C is likely to be
>under the hood of many syntaxes that can call C, I wanted to see how to do
>this thing that I think is important.

I have no idea what you mean by this, so I will ignore it.

>Calling it from a place without every C99 guarantee is a bit of a trick:
>
>%- > Is qsort an intrinsic for C?
>%-
>%- Yes, but despite the name it isn't guaranteed to
>%- implement quicksort.
>%-
>%- The advantage is that it can sort an array of any kind
>%- of data structure given a pointer to the array (usual
>%- for C), the length, the length of each array element
>%- (which must be in contiguous storage), and a comparison
>%- function. The comparison function is given pointers to
>%- two elements and returns a positive, zero, or negative
>%- value if the first is greater then, equal to, or less
>%- than the second. With the appropriate compare function
>%- the array can be an array of pointers, or structures
>%- containing pointers.
>%-
>%- To do that in Fortran 2003 might also require a routine
>%- to copy such array elements.
>
>Is Glen (quoted) correct?

I assume by "(quoted)" you refer to the statements marked "%-"
here.

The first statement (that it is an "intrinsic") is correct *if*
"intrinsic" means, as I would assume in this case, "the compiler
is allowed to recognize the name, and make assumptions about it,
e.g., replacing the call with inline code so that no library routine
is called". The part of the statement that says it is not guaranteed
to implement (Hoare's) Quick Sort is true unconditionally.

(If "intrinsic" means "something that need not use normal function
call syntax" -- as is true of Fortran's power operator, for instance,
even though A**B may call a library routine -- then this part of the
statement is false. There may be several other things people mean
by the word "intrinsic", depending on what language(s) they have
used. For instance, SNOBOL's string operations and success/fail
behavior could be considered its "intrinsics". Under most of these
meanings, I believe C's qsort() would not be an "intrinsic".)

(But there is a constraint on the comparison function: it must be
consistent. That is, the result of (*compar)(A,B) must stay the
same from call to call when A and B indicate the same element,
even if that element moves within the array.)

The third part of the statement, concerning Fortran 2003: I have
no idea. The last time I used Fortran was pre-1990.

[Regarding substituting for "library"-section functions, i.e., stuff
described in section 7 of the C Standard:]

>I guess the notion of keyword is less sacred in the non C world.
>They say you just change what the linker finds first.

Be careful when talking with "them". :-)

As was the case with Fortran through the 1980s at least, this only
*sometimes* works. For instance, with gcc:

#include <stdio.h>

int main(void) {
printf("hello world\n");
return 0;
}

does not always call the library printf() routine. (Sometimes it
calls the library puts() routine, depending on optimization options.)

Similarly, "calls" to sqrt() or memcpy() can be replaced, under
some conditions, with inline instructions. So attempts to subvert
the library need not work, and -- unless you know what you are
doing, or verify quite carefully -- some *do* not work, on real
systems.

That said, I do not know of any C implementations that modify calls
to qsort(). Of course, this does not guarantee that none exist.
(Among other things, to cross comp.lang.c threads a bit, I have
never seen or used a [full] C99 implementation. Perhaps one of
those -- several are rumored to exist -- might substitute some
qsort() calls, for instance.)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: gmail (figure it out) http://web.torek.net/torek/index.html

All times are GMT. The time now is 07:53 PM.