By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,570 Members | 1,245 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,570 IT Pros & Developers. It's quick & easy.

calling qsort

P: n/a
K&R has three different versions of qsort, and the ultimate one is supposed
to be like the one in the std library. I'm trying to implement the first,
which is in 4.10.

I think I'm pretty close with this:

void qsort(int v[], int left, int right)
{

int i, last;
void swap(int v[], int i, int j);

if (left >= right)
return;
swap (v, left, (left + right)/2);
last = left;
for (i = left+ 1; i <= right; i++)
if (v[i] < v[left])
swap (v, ++last, i);
swap(v, left, last);
qsort(v, left, last - 1);
qsort(v, last + 1, right);

}

void swap(int v[], int i, int j)
{
int temp;

temp = v[i];
v[i] = v[j];
v[j] = temp;
}

#include <stdio.h>
#define size 9

int main(void)
{
int m[size], i;

for (i=0; i < size; ++ i)
{
m[i] = i - size;
printf(" %d \n ", m[i]);
}

qsort (m[], 0, size - 1);

for (i=0; i < size; ++ i) printf(" %d \n ", m[i]);

return 0;
}

// gcc -o sort c5.c

gcc objects with:

F:\gfortran\source>gcc -o sort c5.c
c5.c: In function 'main':
c5.c:42: error: expected expression before ']' token

If I count correctly, this is the qsort call. I'm not surprised that gcc
objects, as I'm not sure about this syntax at all.

I guess that's question one. The other is how to call the stdlib version
of qsort, whose syntax is given in appdx B5:

void qsort(void *base, size_t n, size_t size,
int (*cmp)(const void *, const void *)

Beautiful night here in New Mexico. I can hear and even smell the state
fair. cheers,
--
We are here and it is now. Further than that, all human knowledge is
moonshine. 3
H. L. Mencken
Sep 9 '08 #1
Share this Question
Share on Google+
61 Replies


P: n/a
Hi Ron,

made few changes and it worked. :)

< changes
Yours
diff qsort_samp.c original_qsort.c
1,3d0
< #include <stdio.h>
< #define size 9
<
32a30,32
#include <stdio.h>
#define size 9
39c39
< m[i] = size - i;
---
m[i] = i - size;
43c43
< qsort (m, 0, size - 1);
---
qsort (m[], 0, size - 1);

Regards,
Dhilip
Sep 9 '08 #2

P: n/a
On 9 Sep, 06:30, Ron Ford <r...@example.invalidwrote:
K&R has three different versions of qsort, and the ultimate one is supposed
to be like the one in the std library.
note the calling interafec may be similar but the guts don't
have to be. qsort() does not have to implement Quick Sort.

*I'm trying to implement the first,
which is in 4.10.
I don't understand "trying to implement". Why not copy the code
provided.

I think I'm pretty close with this:

void qsort(int v[], int left, int right)
{

* int i, last;
* void swap(int v[], int i, int j);

* if (left >= right)
* * return;
* swap (v, left, (left + right)/2);
* last = left;
* for (i = left+ 1; i <= right; i++)
* * if (v[i] < v[left])
* * * swap (v, ++last, i);
* * swap(v, left, last);
* * qsort(v, left, last - 1);
* * qsort(v, last + 1, right);

}

void swap(int v[], int i, int j)
{
* int temp;

* temp = v[i];
* v[i] = v[j];
* v[j] = temp;

} *
that looks identical to K&R (except you stripped the comments)

#include <stdio.h>
#define size 9

int main(void)
{
* int m[size], i;

* for (i=0; i < size; ++ i)
* * {
* * * * m[i] = i - size;
* * * * printf(" %d \n ", m[i]);
* * }

* qsort (m[], 0, size - 1);
go and reread about arrays. eg K&R page 29

>
* for (i=0; i < size; ++ i) *printf(" %d \n ", m[i]);

* return 0;

}

// gcc -o sort c5.c

gcc objects with:

F:\gfortran\source>gcc -o sort c5.c
c5.c: In function 'main':
c5.c:42: error: expected expression before ']' token

If I count correctly, this is the qsort call. *I'm not surprised that gcc
objects, as I'm not sure about this syntax at all.
good. because it's wrong

I guess that's question one. *The other is how to call the stdlib version
of qsort, whose syntax is given in appdx B5:

void qsort(void *base, size_t n, size_t size,
* * * * * *int (*cmp)(const void *, const void *)

Beautiful night here in New Mexico. *I can hear and even smell the state
fair. *cheers,
horrid morning here in Xshire. It's precipitating it down.
--
Nick Keighley

C++: "an octopus made by nailing extra legs onto a dog"
-- Steve Taylor, 1998
Sep 9 '08 #3

P: n/a
On Tue, 9 Sep 2008 01:14:50 -0700 (PDT), s.***********@gmail.com posted:
Hi Ron,

made few changes and it worked. :)

< changes
>Yours

diff qsort_samp.c original_qsort.c
1,3d0
< #include <stdio.h>
< #define size 9
<
32a30,32
>#include <stdio.h>
#define size 9
39c39
< m[i] = size - i;
---
> m[i] = i - size;
43c43
< qsort (m, 0, size - 1);
---
> qsort (m[], 0, size - 1);


Regards,
Dhilip
Thanks for your response, Phil. Removing the braces from m in the qsort
call and reversing i and size while populating m gives me the output I was
looking for:
F:\gfortran\source>sort
9
8
7
6
5
4
3
2
1
1
2
3
4
5
6
7
8
9
--
We are here and it is now. Further than that, all human knowledge is
moonshine. 3
H. L. Mencken
Sep 9 '08 #4

P: n/a
On Tue, 9 Sep 2008 01:28:09 -0700 (PDT), Nick Keighley posted:
On 9 Sep, 06:30, Ron Ford <r...@example.invalidwrote:
>K&R has three different versions of qsort, and the ultimate one is supposed
to be like the one in the std library.

note the calling interafec may be similar but the guts don't
have to be. qsort() does not have to implement Quick Sort.
I think there's two issues here. An implementation could modify the call
to qsort. Chris Torek says this about that:

%- 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.

Or, the qsort in the library might not be a quicksort. Where can I look to
see the source for a gcc install? A search with qsort*.* only turns up a
forbidding-looking creature called qsort_c_module:

GFORTRAN module created from freeformat50.f95 on Wed Aug 27 17:16:03 2008
MD5:2948eeeeb93405ec66df04faa2275dfe -- If you edit this, you'll get what
you deserve.

(() () () () () () () () () () () () () () () () () () () () () () () ()
() () ())

()

()

()

()

(2 'qsort_c_module' 'qsort_c_module' 'qsort_c_module' 1 ((MODULE
UNKNOWN-INTENT UNKNOWN-PROC UNKNOWN UNKNOWN) (UNKNOWN 0 0 0 UNKNOWN ())
0 0 () () 0 () () 0 0)
3 'qsortc' 'qsort_c_module' 'qsortc' 1 ((PROCEDURE UNKNOWN-INTENT
MODULE-PROC DECL UNKNOWN SUBROUTINE RECURSIVE ALWAYS_EXPLICIT) (UNKNOWN
0 0 0 UNKNOWN ()) 4 0 (5) () 0 () () 0 0)
5 'a' '' 'a' 4 ((VARIABLE INOUT UNKNOWN-PROC UNKNOWN UNKNOWN DIMENSION
DUMMY) (INTEGER 8 0 0 INTEGER ()) 0 0 () (1 ASSUMED_SHAPE (CONSTANT (
INTEGER 4 0 0 INTEGER ()) 0 '1') ()) 0 () () 0 0)
)

('qsort_c_module' 0 2 'qsortc' 0 3)

! end excerpt
>
>*I'm trying to implement the first,
which is in 4.10.

I don't understand "trying to implement". Why not copy the code
provided.
snip
that looks identical to K&R (except you stripped the comments)
I'll be the first to own up to speaking elliptically on occasion. I don't
see it there.

go and reread about arrays. eg K&R page 29
I leafed through pp25-100 and didn't see it.
>If I count correctly, this is the qsort call. *I'm not surprised that gcc
objects, as I'm not sure about this syntax at all.

good. because it's wrong
No, it was the brackets on m in the qsort call that was the culprit on line
42.

--
We are here and it is now. Further than that, all human knowledge is
moonshine. 3
H. L. Mencken
Sep 9 '08 #5

P: n/a

"Ron Ford" <ro*@example.invalidwrote in message
Or, the qsort in the library might not be a quicksort. Where can I look
to
see the source for a gcc install? A search with qsort*.* only turns up a
forbidding-looking creature called qsort_c_module:
That's typical. Bread and butter code is written portably and with an
emphasis on readability and maintainablility (in an ideal world). Libraries
are written for speed, often using many platform-dependent shortcuts.

However there are plenty of implementations of the quicksort algorithm on
the web. The main thing to remember is to use the same interface as the
stdlib function. This is a bit of extra work, but the added generality is
worth it.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Sep 9 '08 #6

P: n/a
Malcolm McLean wrote, On 09/09/08 21:38:
>
"Ron Ford" <ro*@example.invalidwrote in message
>Or, the qsort in the library might not be a quicksort. Where can I
look to
see the source for a gcc install? A search with qsort*.* only turns up a
forbidding-looking creature called qsort_c_module:
gcc in general uses whatever library the system happens to provide. So
you need to be more specific and also address the question to a
group/list dedicated to your implementation.
That's typical. Bread and butter code is written portably and with an
emphasis on readability and maintainablility (in an ideal world).
Not sure what you mean by "bread and butter code" here.
Libraries are written for speed, often using many platform-dependent
shortcuts.
True.
However there are plenty of implementations of the quicksort algorithm
on the web.
Yes, but quicksort is not necessarily the best algorithm to use.
The main thing to remember is to use the same interface as
the stdlib function. This is a bit of extra work, but the added
generality is worth it.
Whether you want to use the same interface or something different
depends on what you want to achieve.
--
Flash Gordon
Sep 9 '08 #7

P: n/a
On Tue, 09 Sep 2008 22:19:58 +0100, Flash Gordon posted:
>> Where can I
look to
see the source for a gcc install?

gcc in general uses whatever library the system happens to provide. So
you need to be more specific and also address the question to a
group/list dedicated to your implementation.
I asked for more info in gnu.gcc.help.

The part I don't get right now is why the call to qsort worked without
#include <stdlib.h>

?
--
What men value in this world is not rights but privileges. 7
H. L. Mencken
Sep 9 '08 #8

P: n/a
Ron Ford <ro*@example.invalidwrites:
[...]
The part I don't get right now is why the call to qsort worked without
#include <stdlib.h>

?
Luck (arguably bad luck).

In C90, if you call a function with no visible declaration, the
compiler will assume that it returns int, and that it expects
arguments of the promoted types of the arguments you actually gave it.
If the generated code happens to work with the the actual function,
you can get what appear to be correct results. If not, arbitrarily
bad things can happen.

C99 dropped implicit int, so an attempt to call qsort with no visible
declaration would result in a mandatory diagnostic. But there are few
conforming C99 compilers yet.

But most compilers will warn you about such a call with the right
options. I advise you to find out what those options are for your
compiler, and get into the habit of using them.

Another possibility is that you might have included some other file
that directly or indirectly included <stdlib.h>. That would work, but
IMHO it's better style to have an explicit #include <stdlib.hin the
file that contains the qsort call.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Sep 10 '08 #9

P: n/a
could you be a bit less heavy handed with your snips?
Try to leave enough context in so your post can be understood
standalone.
On 9 Sep, 21:00, Ron Ford <r...@example.invalidwrote:
On Tue, 9 Sep 2008 01:28:09 -0700 (PDT), Nick Keighley posted:
On 9 Sep, 06:30, Ron Ford <r...@example.invalidwrote:
K&R has three different versions of qsort, and the ultimate one is supposed
to be like the one in the std library.
note the calling interafec may be similar but the guts don't
have to be. qsort() does not have to implement Quick Sort.

I think there's two issues here. *An implementation could modify the call
to qsort. *Chris Torek says this about that:

%- 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.
I don't understand what "modify calls to qsort()" means.

<snip>
*I'm trying to implement the first, which is in 4.10.
I don't understand "trying to implement". Why not copy the code
provided.

snip
that looks identical to K&R (except you stripped the comments)

I'll be the first to own up to speaking elliptically on occasion. *I don't
see it there.
again, we don't seem to be speaking the same version of english.
You don't see what where? By "implement" you mean cut-and-paste?
go and reread about arrays. eg K&R page 29

I leafed through pp25-100 and didn't see it.
p29 of my k&R has a function called getline() which takes a char[]
argument. Just above that is main() which calls getline() on line 16.
This call uses the correct syntax.

If I count correctly, this is the qsort call. *I'm not surprised that gcc
objects, as I'm not sure about this syntax at all.
good. because it's wrong

No, it was the brackets on m in the qsort call that was the culprit on line
42.
Note the bit I commented on was "If I count correctly, this is the
qsort call."
So I told you the quicksort call was wrong, so where does the "No"
above come from?
--
NIck Keighley

"You fell victim to one of the classic blunders.
The most famous is 'Never get involved in a land war in Asia,' "
Sep 10 '08 #10

P: n/a
On Wed, 10 Sep 2008 02:44:37 -0700 (PDT), Nick Keighley posted:
could you be a bit less heavy handed with your snips?
Try to leave enough context in so your post can be understood
standalone.
On 9 Sep, 21:00, Ron Ford <r...@example.invalidwrote:
>On Tue, 9 Sep 2008 01:28:09 -0700 (PDT), Nick Keighley posted:
>>On 9 Sep, 06:30, Ron Ford <r...@example.invalidwrote:
>>>K&R has three different versions of qsort, and the ultimate one is supposed
to be like the one in the std library.
>>note the calling interafec may be similar but the guts don't
have to be. qsort() does not have to implement Quick Sort.

I think there's two issues here. *An implementation could modify the call
to qsort. *Chris Torek says this about that:

%- 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.

I don't understand what "modify calls to qsort()" means.
I'm appropriately uncomfortable trying to elaborate on what Chris, in a
slightly differing context, writes. I think the idea is that if you printf
the word "hi," your implementation could instead putchar h and i.

again, we don't seem to be speaking the same version of english.
You don't see what where? By "implement" you mean cut-and-paste?
If you cut and paste with a book, you destroy its future value.
"Implement" means making the necessary keystrokes to make code work.

>>go and reread about arrays. eg K&R page 29

I leafed through pp25-100 and didn't see it.

p29 of my k&R has a function called getline() which takes a char[]
argument. Just above that is main() which calls getline() on line 16.
This call uses the correct syntax.
The calls on pg 29 are for char arrays and have brackets. My error was
that I had to lose the brackets.
>
>>>If I count correctly, this is the qsort call. *I'm not surprised that gcc
objects, as I'm not sure about this syntax at all.
>>good. because it's wrong

No, it was the brackets on m in the qsort call that was the culprit on line
42.

Note the bit I commented on was "If I count correctly, this is the
qsort call."
So I told you the quicksort call was wrong, so where does the "No"
above come from?
--
NIck Keighley

"You fell victim to one of the classic blunders.
The most famous is 'Never get involved in a land war in Asia,' "
The error on line 42 no longer exists. It just occured to me that "don't
get in a land war in Asia" is precisely what the texans did.
--
What men value in this world is not rights but privileges. 7
H. L. Mencken
Sep 11 '08 #11

P: n/a
On Tue, 09 Sep 2008 18:26:41 -0700, Keith Thompson posted:
Ron Ford <ro*@example.invalidwrites:
[...]
>The part I don't get right now is why the call to qsort worked without
#include <stdlib.h>

?

Luck (arguably bad luck).

In C90, if you call a function with no visible declaration, the
compiler will assume that it returns int, and that it expects
arguments of the promoted types of the arguments you actually gave it.
If the generated code happens to work with the the actual function,
you can get what appear to be correct results. If not, arbitrarily
bad things can happen.

C99 dropped implicit int, so an attempt to call qsort with no visible
declaration would result in a mandatory diagnostic. But there are few
conforming C99 compilers yet.

But most compilers will warn you about such a call with the right
options. I advise you to find out what those options are for your
compiler, and get into the habit of using them.

Another possibility is that you might have included some other file
that directly or indirectly included <stdlib.h>. That would work, but
IMHO it's better style to have an explicit #include <stdlib.hin the
file that contains the qsort call.
Thanks, Keith. I thought I'd crank up the warnings and don't know what I'm
seeing.
F:\gfortran\source>gcc -o sort -Wall -pedantic -ansi c6.c
c6.c: In function 'main':
c6.c:51: error: expected expression before '/' token
c6.c: At top level:
c6.c:58: error: expected identifier or '(' before '/' token

Lines 51 and 58 are comments. Just to see if they would work otherwise, I
compiled with no flags and was successful:

F:\gfortran\source>gcc c6.c

issues no diagnostics. I thought it might be to lack of inclusion of
stdlib.h, but I get the same thing after I add it:

void qsort1(int v[], int left, int right)
{

int i, last;
void swap(int v[], int i, int j);

if (left >= right)
return;
swap (v, left, (left + right)/2);
last = left;
for (i = left+ 1; i <= right; i++)
if (v[i] < v[left])
swap (v, ++last, i);
swap(v, left, last);
qsort1(v, left, last - 1);
qsort1(v, last + 1, right);

}

void swap(int v[], int i, int j)
{
int temp;

temp = v[i];
v[i] = v[j];
v[j] = temp;
}

int mycmp(const void *a, const void *b) {
return (*(const int *)a < *(const int *)b);
}

#include <stdio.h>
#include <stdlib.h>
#define size 9

int main(void)
{
int m[size], i;

for (i=0; i < size; ++ i)
{
m[i] = size - i;
printf(" %d \n ", m[i]);
}

qsort1 (m, 0, size - 1);
for (i=0; i < size; ++ i) printf(" %d \n ", m[i]);

// call library qsort line 52
qsort(m, size, sizeof(int), mycmp);
for (i=0; i < size; ++ i) printf(" %d \n ", m[i]);

return 0;
}

// gcc -o sort -Wall -pedantic -ansi c6.c line 58
F:\gfortran\source>gcc -o sort -Wall -pedantic -ansi c6.c
c6.c: In function 'main':
c6.c:52: error: expected expression before '/' token
c6.c: At top level:
c6.c:59: error: expected identifier or '(' before '/' token

Is '//' not a kosher comment?
--
War will never cease until babies begin to come into the world with larger
cerebrums and smaller adrenal glands. 2
H. L. Mencken
Sep 11 '08 #12

P: n/a
On Sep 12, 12:07 am, Ron Ford <r...@example.invalidwrote:
Is '//' not a kosher comment?
No Ron, // is not a "kosher comment".
Where have you heard that? What is this nonsensical babbling that
frequently appears in your posts?
More importantly, why are some still bothering with you?
Sep 11 '08 #13

P: n/a
Ron Ford <ro*@example.invalidwrites:
[...]
Is '//' not a kosher comment?
It's a valid comment in C99. It's not a valid comment in C90. The
"-ansi" option (along with "-pedantic" causes gcc to conform to C90.

(You've been hanging out in this group for a while; I'm surprised you
didn't know that.)

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Sep 11 '08 #14

P: n/a
vi******@gmail.com writes:
On Sep 12, 12:07 am, Ron Ford <r...@example.invalidwrote:
>Is '//' not a kosher comment?

No Ron, // is not a "kosher comment".
Where have you heard that? What is this nonsensical babbling that
frequently appears in your posts?
More importantly, why are some still bothering with you?
What on earth are you babbling about? // is a perfectly good comment
prefix.
Sep 11 '08 #15

P: n/a
On Thu, 11 Sep 2008 14:19:46 -0700 (PDT), vi******@gmail.com posted:
On Sep 12, 12:07 am, Ron Ford <r...@example.invalidwrote:
>Is '//' not a kosher comment?

No Ron, // is not a "kosher comment".
Where have you heard that? What is this nonsensical babbling that
frequently appears in your posts?
More importantly, why are some still bothering with you?
[comp.lang.c]
!delete From {vippstar}
--
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
Sep 11 '08 #16

P: n/a
On Thu, 11 Sep 2008 15:06:41 -0700, Keith Thompson posted:
Ron Ford <ro*@example.invalidwrites:
[...]
>Is '//' not a kosher comment?

It's a valid comment in C99. It's not a valid comment in C90. The
"-ansi" option (along with "-pedantic" causes gcc to conform to C90.

(You've been hanging out in this group for a while; I'm surprised you
didn't know that.)
I'm promiscuous with syntax and compilers. Comments are the last thing I
remember; they're almost like comments. Is /* ...*/ the only legal C90
comment?
--
We are here and it is now. Further than that, all human knowledge is
moonshine. 3
H. L. Mencken
Sep 11 '08 #17

P: n/a
On Sep 12, 1:06 am, Keith Thompson <ks...@mib.orgwrote:
Ron Ford <r...@example.invalidwrites:

[...]
Is '//' not a kosher comment?

It's a valid comment in C99. It's not a valid comment in C90. The
"-ansi" option (along with "-pedantic" causes gcc to conform to C90.

(You've been hanging out in this group for a while; I'm surprised you
didn't know that.)
For a while?! Here's a quote from Ron Ford:
Message-ID: <93*****************************@40tude.net>
These made great reading. It's been years since I've read Dan Pop.
Years. He reads Dan Pop, the standard too. (see the message) Yet, //
is a "kosher comment".

Here, in this article, <1l***************@example.invalid>, he
correctly uses the // comment, and compiles with -std=c99.
Why did he choose to change it to -ansi -pedantic, while using //?
Wouldn't he remember that with -std=c99 it worked? Isn't that a hint
that it's a C99 feature?

Here's another article of his, <jk***************@example.invalid>.
In this one, he seems quite confident to claim that // is indeed a
comment.
(He also suggests to look at the 7th chapter of K&R, though //
comments are not mentioned at all in K&R...)
Plus, the usual nonsense.

Keith, why do you still bother? It's your right to do so, if you want,
but it puzzles me.
Sep 11 '08 #18

P: n/a
On Fri, 12 Sep 2008 00:25:01 +0200, Richard posted:
vi******@gmail.com writes:
>On Sep 12, 12:07 am, Ron Ford <r...@example.invalidwrote:
>>Is '//' not a kosher comment?

No Ron, // is not a "kosher comment".
Where have you heard that? What is this nonsensical babbling that
frequently appears in your posts?
More importantly, why are some still bothering with you?

What on earth are you babbling about? // is a perfectly good comment
prefix.
I did a little reading for flags in gcc.pdf, and I think this is what I
wanted for when I didn't have stdlib included:

F:\gfortran\source>gcc -o sort -Wall c6.c
c6.c: In function 'main':
c6.c:53: warning: implicit declaration of function 'qsort'
I looked in stdlib.h and found the declaration for qsort for my
implementation.

_CRTIMP void __cdecl qsort(void*, size_t, size_t,
int (*)(const void*, const void*));

Does this suggest a better search for google to find the source for my
qsort implementation than "qsort.c gcc source?"

--
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
Sep 12 '08 #19

P: n/a
Ron Ford <ro*@example.invalidwrites:
On Thu, 11 Sep 2008 15:06:41 -0700, Keith Thompson posted:
>Ron Ford <ro*@example.invalidwrites:
[...]
>>Is '//' not a kosher comment?

It's a valid comment in C99. It's not a valid comment in C90. The
"-ansi" option (along with "-pedantic" causes gcc to conform to C90.

(You've been hanging out in this group for a while; I'm surprised you
didn't know that.)

I'm promiscuous with syntax and compilers. Comments are the last thing I
remember; they're almost like comments. Is /* ...*/ the only legal C90
comment?
Yes (though #if 0 ... #endif can serve a similar purpose).

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Sep 12 '08 #20

P: n/a
Ron Ford <ro*@example.invalidwrites:
[...]
I looked in stdlib.h and found the declaration for qsort for my
implementation.

_CRTIMP void __cdecl qsort(void*, size_t, size_t,
int (*)(const void*, const void*));

Does this suggest a better search for google to find the source for my
qsort implementation than "qsort.c gcc source?"
gcc doesn't provide qsort; qsort is provided by your C library.

Depending on which system you're using, the source for your C
library's qsort implementation may or may not be available. If it is
available, I suggest asking in a newsgroup that deals with your
operating system.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Sep 12 '08 #21

P: n/a
On Thu, 11 Sep 2008 15:07:10 -0600, Ron Ford <ro*@example.invalid>
wrote:

snip
>int mycmp(const void *a, const void *b) {
return (*(const int *)a < *(const int *)b);
}
qsort requires mycmp to return a negative, zero, or positive value
depending of the result of the comparison. Yours will return 0 for
both equality and "greater than". That should confuse the hell out of
qsort.

--
Remove del for email
Sep 12 '08 #22

P: n/a
On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.invalid>
wrote:
>On Thu, 11 Sep 2008 19:05:28 -0700, Barry Schwarz posted:
>On Thu, 11 Sep 2008 15:07:10 -0600, Ron Ford <ro*@example.invalid>
wrote:

snip
>>>int mycmp(const void *a, const void *b) {
return (*(const int *)a < *(const int *)b);
}

qsort requires mycmp to return a negative, zero, or positive value
depending of the result of the comparison. Yours will return 0 for
both equality and "greater than". That should confuse the hell out of
qsort.

I thought this might address your criticism, but output says differently.

int mycmp(const void *a, const void *b)
{

int compare = 0;
if (a < b) compare = 1;
You are comparing the pointers, not the values they point to.
if (a b) compare = -1;
return (compare);
}
snip
>
Do I need casts on a and b?
Not only casts but a dereference also. You had both in the original
code. Why did you remove them?

--
Remove del for email
Sep 12 '08 #23

P: n/a
On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:
On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.invalid>
wrote:
You are comparing the pointers, not the values they point to.
This seems right and behaves:

int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const int *)a < *(const int *)b) compare = 1;
if (*(const int *)a *(const int *)b) compare = -1;
return (compare);
}
>>
Do I need casts on a and b?

Not only casts but a dereference also. You had both in the original
code. Why did you remove them?
The short answer is that I don't understand them fully. In particular, I
dont understand the second asterisk in
*(const int *)a
.. The first dereferences what 'a' points to. The const int makes the
compiler believe it's an integer. The second is there because that was how
Nate formulated the original return, which I had to change to reflect three
cases instead of two, not because I know why.:-(

Furthermore, the library qsort claims to sort any datatype. Do they all
admit of orderings as do ints where '>' and '<' are well defined?
--
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
Sep 12 '08 #24

P: n/a
On Fri, 12 Sep 2008 14:28:30 -0600, Ron Ford <ro*@example.invalid>
wrote:
>On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:
>On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.invalid>
wrote:
>You are comparing the pointers, not the values they point to.

This seems right and behaves:

int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const int *)a < *(const int *)b) compare = 1;
if (*(const int *)a *(const int *)b) compare = -1;
return (compare);
}
>>>
Do I need casts on a and b?

Not only casts but a dereference also. You had both in the original
code. Why did you remove them?

The short answer is that I don't understand them fully. In particular, I
dont understand the second asterisk in
*(const int *)a
. The first dereferences what 'a' points to. The const int makes the
1 - The first asterisk dereferences its operand which is not exactly
a. a is a void* and you cannot dereference it (because the resulting
type would be void which is a incomplete type that cannot be
completed).

2 - The only allowable operand for the dereference operator is a
pointer. That should be your clue that const int is not the type we
want here.

3 - When deciphering a declaration or cast, you go left to right until
there is a reason to stop. The only reason I can think of at the
moment is a right parenthesis. So the type of the cast is const int *
which is a pointer type that can be dereferenced.
>compiler believe it's an integer. The second is there because that was how
Nate formulated the original return, which I had to change to reflect three
cases instead of two, not because I know why.:-(
The second one is there to avoid the exact problem you describe. You
cannot dereference an int but you can dereference a pointer to int.
>
Furthermore, the library qsort claims to sort any datatype. Do they all
admit of orderings as do ints where '>' and '<' are well defined?
The reason qsort can sort any **array** type is because you provide
the compare function. qsort will pass your compare function the
address of two elements (converted to void* because that is the
generic pointer type that can hold any type of address). Your compare
function must convert each pointer to void to the correct type for
your array elements, perform the compare, and return the appropriate
+/0/- value back to qsort so it can decide whether to swap the
elements or not. (You have almost complete freedom as to what the
word compare means in this context. You could compare the int values
as this code does. You could use the % operator and compare only the
units digits. You could compare absolute values and sort by magnitude
only, ignoring sign. If the array element is a struct type, you could
sort based on one or more elements. If the array element is a pointer
type, you could sort based on the pointer values (addresses) or on the
values the pointers point to...)

--
Remove del for email
Sep 13 '08 #25

P: n/a
vi******@gmail.com wrote:
On Sep 12, 12:07 am, Ron Ford <r...@example.invalidwrote:
>Is '//' not a kosher comment?

No Ron, // is not a "kosher comment".
Not quite right. It is not a kosher comment in C90, which Ron is apparently
using (gcc -o sort -Wall -pedantic -ansi c6.c).

It is perfectly legal in C99 and a common extension in many compilers that
are not C99

Bye, Jojo
Sep 13 '08 #26

P: n/a
Ron Ford wrote:
On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:
>On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.invalid>
wrote:
>You are comparing the pointers, not the values they point to.

This seems right and behaves:

int mycmp(const void *a, const void *b)
{
int compare = 0;

if (*(const int *)a < *(const int *)b) compare = 1;
if (*(const int *)a *(const int *)b) compare = -1;
return (compare);
}
I believe the standard idiom uses some extra variables:
int mycmp(const void *a, const void *b)
{
const int *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = 1;
if (*p1 *p2) compare = -1;
return compare;
}

Saves you all these nasty casts. It's less typing too.

Bye, Jojo
Sep 13 '08 #27

P: n/a
"Joachim Schmitz" <no*********@schmitz-digital.dewrites:
Ron Ford wrote:
>On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:
>>On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.invalid>
wrote:
>>You are comparing the pointers, not the values they point to.

This seems right and behaves:

int mycmp(const void *a, const void *b)
{
int compare = 0;

if (*(const int *)a < *(const int *)b) compare = 1;
if (*(const int *)a *(const int *)b) compare = -1;
return (compare);
}

I believe the standard idiom uses some extra variables:
int mycmp(const void *a, const void *b)
{
const int *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = 1;
if (*p1 *p2) compare = -1;
return compare;
}

Saves you all these nasty casts. It's less typing too.

Bye, Jojo

Why no else or simple returns? Why do the second compare?

Also, is the gcc implementation not standard? Whats wrong with merely

int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}

Sep 13 '08 #28

P: n/a
Richard<rg****@gmail.comwrites:
"Joachim Schmitz" <no*********@schmitz-digital.dewrites:
>Ron Ford wrote:
>>On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:

On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.invalid>
wrote:
You are comparing the pointers, not the values they point to.

This seems right and behaves:

int mycmp(const void *a, const void *b)
{
int compare = 0;

if (*(const int *)a < *(const int *)b) compare = 1;
if (*(const int *)a *(const int *)b) compare = -1;
return (compare);
}

I believe the standard idiom uses some extra variables:
int mycmp(const void *a, const void *b)
{
const int *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = 1;
if (*p1 *p2) compare = -1;
return compare;
}

Saves you all these nasty casts. It's less typing too.

Bye, Jojo


Why no else or simple returns? Why do the second compare?

Also, is the gcc implementation not standard? Whats wrong with merely

int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}
other than the obvious typo of the variable names course ...
Sep 13 '08 #29

P: n/a
Richard wrote:
"Joachim Schmitz" <no*********@schmitz-digital.dewrites:
>Ron Ford wrote:
>>On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:

On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.invalid>
wrote:
You are comparing the pointers, not the values they point to.

This seems right and behaves:

int mycmp(const void *a, const void *b)
{
int compare = 0;

if (*(const int *)a < *(const int *)b) compare = 1;
if (*(const int *)a *(const int *)b) compare = -1;
return (compare);
}

I believe the standard idiom uses some extra variables:
int mycmp(const void *a, const void *b)
{
const int *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = 1;
if (*p1 *p2) compare = -1;
return compare;
}

Saves you all these nasty casts. It's less typing too.

Bye, Jojo


Why no else or simple returns?
To not alter the OP's code too much. To not have more than one extit from
the function
Why do the second compare?
Because that wouldn't work in case both operands are equal
Also, is the gcc implementation not standard? Whats wrong with merely

int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}
At least the syntax 8-)

Bye, Jojo
Sep 13 '08 #30

P: n/a
Richard wrote:
"Joachim Schmitz" <no*********@schmitz-digital.dewrites:
>Ron Ford wrote:
>>On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:

On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.invalid>
wrote:
You are comparing the pointers, not the values they point to.

This seems right and behaves:

int mycmp(const void *a, const void *b)
{
int compare = 0;

if (*(const int *)a < *(const int *)b) compare = 1;
if (*(const int *)a *(const int *)b) compare = -1;
return (compare);
}

I believe the standard idiom uses some extra variables:
int mycmp(const void *a, const void *b)
{
const int *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = 1;
if (*p1 *p2) compare = -1;
return compare;
}

Saves you all these nasty casts. It's less typing too.

Bye, Jojo


Why no else or simple returns? Why do the second compare?

Also, is the gcc implementation not standard? Whats wrong with merely

int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}
Might overflow. The following should fix that:

int mycmp(const void *a, const void *b)
{
return (*(int *)a)>(*(int *)b)-(*(int *)a)<(*(int *)b));
}

Bye, Jojo
Sep 13 '08 #31

P: n/a
Joachim Schmitz wrote:
Richard wrote:
>"Joachim Schmitz" <no*********@schmitz-digital.dewrites:
>>Ron Ford wrote:
On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:

On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.invalid>
wrote:
>

You are comparing the pointers, not the values they point to.

This seems right and behaves:

int mycmp(const void *a, const void *b)
{
int compare = 0;

if (*(const int *)a < *(const int *)b) compare = 1;
if (*(const int *)a *(const int *)b) compare = -1;
return (compare);
}

I believe the standard idiom uses some extra variables:
int mycmp(const void *a, const void *b)
{
const int *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = 1;
if (*p1 *p2) compare = -1;
return compare;
}

Saves you all these nasty casts. It's less typing too.

Bye, Jojo


Why no else or simple returns? Why do the second compare?

Also, is the gcc implementation not standard? Whats wrong with merely

int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}

Might overflow. The following should fix that:

int mycmp(const void *a, const void *b)
{
return (*(int *)a)>(*(int *)b)-(*(int *)a)<(*(int *)b));
}
Without the superfluos last )...
Sep 13 '08 #32

P: n/a
Richard wrote:
Richard<rg****@gmail.comwrites:
>Why no else or simple returns? Why do the second compare?

Also, is the gcc implementation not standard? Whats wrong with merely

int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}

other than the obvious typo of the variable names course ...
It is not really advantageous when the result may be "either
implementation-defined or an implementation-defined signal is
raised" (6.3.1.3).

-- Ralf
Sep 13 '08 #33

P: n/a
On Sep 13, 4:49 pm, Ralf Damaschke <rws...@gmx.dewrote:
Richard wrote:
Richard<rgr...@gmail.comwrites:
Why no else or simple returns? Why do the second compare?
Also, is the gcc implementation not standard? Whats wrong with merely
int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}
other than the obvious typo of the variable names course ...

It is not really advantageous when the result may be "either
implementation-defined or an implementation-defined signal is
raised" (6.3.1.3).
6.3.1.3 refers to (int)LONG_MAX for example. (where LONG_MAX >
INT_MAX)
Computing (*(int *)p2)-(*(int *)p1) can result in integer overflow
which invokes undefined behavior.
Another (more clear) example is INT_MAX + 1. Just evaluating such
expression invokes undefined behavior.
Sep 13 '08 #34

P: n/a
On Fri, 12 Sep 2008 21:55:18 -0700, Barry Schwarz posted:
On Fri, 12 Sep 2008 14:28:30 -0600, Ron Ford <ro*@example.invalid>
wrote:
>>On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:
>>On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.invalid>
wrote:
>>You are comparing the pointers, not the values they point to.

This seems right and behaves:

int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const int *)a < *(const int *)b) compare = 1;
if (*(const int *)a *(const int *)b) compare = -1;
return (compare);
}
>>>>
Do I need casts on a and b?

Not only casts but a dereference also. You had both in the original
code. Why did you remove them?

The short answer is that I don't understand them fully. In particular, I
dont understand the second asterisk in
*(const int *)a
. The first dereferences what 'a' points to. The const int makes the

1 - The first asterisk dereferences its operand which is not exactly
a. a is a void* and you cannot dereference it (because the resulting
type would be void which is a incomplete type that cannot be
completed).

2 - The only allowable operand for the dereference operator is a
pointer. That should be your clue that const int is not the type we
want here.

3 - When deciphering a declaration or cast, you go left to right until
there is a reason to stop. The only reason I can think of at the
moment is a right parenthesis. So the type of the cast is const int *
which is a pointer type that can be dereferenced.
Thanks, Barry, for your generous response. I read it, slept on it (don't
tell my girlfriend) and think I get it. Let's see if I do:

1) a comes in as a void pointer, gets a const int * cast, which is
completable, is dereferenced, leaving a const int, which can be compared by
< and >.
>>Furthermore, the library qsort claims to sort any datatype. Do they all
admit of orderings as do ints where '>' and '<' are well defined?

The reason qsort can sort any **array** type is because you provide
the compare function. qsort will pass your compare function the
address of two elements (converted to void* because that is the
generic pointer type that can hold any type of address). Your compare
function must convert each pointer to void to the correct type for
your array elements, perform the compare, and return the appropriate
+/0/- value back to qsort so it can decide whether to swap the
elements or not. (You have almost complete freedom as to what the
word compare means in this context. You could compare the int values
as this code does. You could use the % operator and compare only the
units digits. You could compare absolute values and sort by magnitude
only, ignoring sign. If the array element is a struct type, you could
sort based on one or more elements. If the array element is a pointer
type, you could sort based on the pointer values (addresses) or on the
values the pointers point to...)
I thought I would try my hand at another sort, and this seems to work:
int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a *(const char *)b) compare = -1;
return (compare);
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{

int m;
char s[] = "Constantinople";
printf (" %s \n", s);
m = strlen(s);
printf (" %d \n ", m);
qsort(s, m, sizeof(char), mycmp);
printf (" %s \n", s);
return 0;
}

// gcc -o sort -Wall -std=c99 c9.c

F:\gfortran\source>gcc -o sort -Wall -std=c99 c9.c

F:\gfortran\source>sort
Constantinople
14
ttspoonnnlieaC

F:\gfortran\source>

Does that look right?
--
For every complex problem there is an answer that is clear, simple, and
wrong.
H. L. Mencken
Sep 13 '08 #35

P: n/a
On Sat, 13 Sep 2008 15:18:32 +0200, Joachim Schmitz posted:
Ron Ford wrote:
>On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:
>>On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.invalid>
wrote:
>>You are comparing the pointers, not the values they point to.

This seems right and behaves:

int mycmp(const void *a, const void *b)
{
int compare = 0;

if (*(const int *)a < *(const int *)b) compare = 1;
if (*(const int *)a *(const int *)b) compare = -1;
return (compare);
}

I believe the standard idiom uses some extra variables:
int mycmp(const void *a, const void *b)
{
const int *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = 1;
if (*p1 *p2) compare = -1;
return compare;
}

Saves you all these nasty casts. It's less typing too.

Bye, Jojo
Thanks, jojo, yours is a cleaner and "better" version. I adapted it to a
charsort:
int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a *(const char *)b) compare = -1;
return (compare);
}

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = -1;
if (*p1 *p2) compare = 1;
return compare;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{

int m;
char s[] = "Constantinople";
printf (" %s \n", s);
m = strlen(s);
printf (" %d \n ", m);
qsort(s, m, sizeof(char), mycmp2);
printf (" %s \n", s);
return 0;
}

// gcc -o sort -Wall -std=c99 c10.c

F:\gfortran\source>gcc -o sort -Wall -std=c99 c10.c

F:\gfortran\source>sort
Constantinople
14
Caeilnnnoopstt

F:\gfortran\source>

Without knowing better, I'd say I know better now.
--
Puritanism. The haunting fear that someone, somewhere, may be happy.
H. L. Mencken
Sep 13 '08 #36

P: n/a
Richard wrote:

Whats wrong with merely
>>
int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}

other than the obvious typo of the variable names course ...
There are about (2 * INT_MAX) situations,
where the result is undefined.

Example:
if (*(int *)p2) equals INT_MAX
and (*(int *)p1) equals (-1),
then your program becomes meaningless.

--
pete
Sep 13 '08 #37

P: n/a
pete said:
Richard wrote:

>Whats wrong with merely
>>>
int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}

other than the obvious typo of the variable names course ...

There are about (2 * INT_MAX) situations,
where the result is undefined.

Example:
if (*(int *)p2) equals INT_MAX
and (*(int *)p1) equals (-1),
then your program becomes meaningless.
I agree with your reasoning but not with your mathematics.

Let's take, for example, a simple four-bit int (with INT_MIN being -INT_MAX
- 1). Sure, it's non-conforming, but it illustrates the point and keeps
the arithmetic simple.

INT_MAX is 7. UB is invoked when the values are:

7 and any of -1, -2, -3, -4, -5, -6, -7, -8
6 and any of -2, -3, -4, -5, -6, -7, -8
5 and any of -3, -4, -5, -6, -7, -8
4 and any of -4, -5, -6, -7, -8
3 and any of -5, -6, -7, -8
2 and any of -6, -7, -8
1 and any of -7, -8
0 and -8

so it does seem that the number of UB cases is S(n + 1) where n is the
value of INT_MAX and S(n) = n(n+1)/2.

For an INT_MAX of 32767, for example, the number of UB cases is 536854528,
which is 16384 * INT_MAX, not 2 * INT_MAX.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Sep 14 '08 #38

P: n/a
On Sun, 14 Sep 2008 00:15:18 +0000, Richard Heathfield posted:
pete said:
>Richard wrote:

>>Whats wrong with merely

int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}

other than the obvious typo of the variable names course ...

There are about (2 * INT_MAX) situations,
where the result is undefined.

Example:
if (*(int *)p2) equals INT_MAX
and (*(int *)p1) equals (-1),
then your program becomes meaningless.

I agree with your reasoning but not with your mathematics.

Let's take, for example, a simple four-bit int (with INT_MIN being -INT_MAX
- 1). Sure, it's non-conforming, but it illustrates the point and keeps
the arithmetic simple.

INT_MAX is 7. UB is invoked when the values are:

7 and any of -1, -2, -3, -4, -5, -6, -7, -8
6 and any of -2, -3, -4, -5, -6, -7, -8
5 and any of -3, -4, -5, -6, -7, -8
4 and any of -4, -5, -6, -7, -8
3 and any of -5, -6, -7, -8
2 and any of -6, -7, -8
1 and any of -7, -8
0 and -8

so it does seem that the number of UB cases is S(n + 1) where n is the
value of INT_MAX and S(n) = n(n+1)/2.

For an INT_MAX of 32767, for example, the number of UB cases is 536854528,
which is 16384 * INT_MAX, not 2 * INT_MAX.
I agree with your mathematics but not your calculation.

S(n+1) is 32768 * 32769/2 = 536887296

, which is 16385 * INT_MAX.

As I've resolved to make it to church tomorrow, I'll cut out with C pretty
soon here and only have fifty percent chance of making it. How do you?
Maybe they serve coffee before service in the Continent.
--
It is now quite lawful for a Catholic woman to avoid pregnancy by a resort
to mathematics, though she is still forbidden to resort to physics or
chemistry.
H. L. Mencken
Sep 14 '08 #39

P: n/a
Ron Ford said:
Richard Heathfield posted:
>pete said:
<snip>
>>>
There are about (2 * INT_MAX) situations,
where the result is undefined. [...]
>I agree with your reasoning but not with your mathematics.
<snip>
I agree with your mathematics but not your calculation.
Touche'. :-)
Maybe they serve coffee before service in the Continent.
During. I take it you've never heard of cafe church?

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Sep 14 '08 #40

P: n/a
Ron Ford wrote:
On Sat, 13 Sep 2008 15:18:32 +0200, Joachim Schmitz posted:
>Ron Ford wrote:
>>On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:

On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.invalid>
wrote:
You are comparing the pointers, not the values they point to.

This seems right and behaves:

int mycmp(const void *a, const void *b)
{
int compare = 0;

if (*(const int *)a < *(const int *)b) compare = 1;
if (*(const int *)a *(const int *)b) compare = -1;
return (compare);
}

I believe the standard idiom uses some extra variables:
int mycmp(const void *a, const void *b)
{
const int *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = 1;
if (*p1 *p2) compare = -1;
return compare;
}

Saves you all these nasty casts. It's less typing too.

Bye, Jojo

Thanks, jojo, yours is a cleaner and "better" version. I adapted it
to a charsort:
int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a *(const char *)b) compare = -1;
return (compare);
}

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = -1;
if (*p1 *p2) compare = 1;
return compare;
}
Still not perfect, overflow might occur. Better:
int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;

return (*p1 *p2) - (*p1 < *p2);
}

Or with the casts:

int mycmp2(const void *a, const void *b)
{
return (*(const char *)a *(const char *)b) - (*(const char *)a < *(const
char *)b);
}

but I like the former better.

Bye, Jojo
Sep 14 '08 #41

P: n/a
"Joachim Schmitz" <no*********@schmitz-digital.dewrites:
Ron Ford wrote:
>On Sat, 13 Sep 2008 15:18:32 +0200, Joachim Schmitz posted:
<snip>
>Thanks, jojo, yours is a cleaner and "better" version. I adapted it
to a charsort:
int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a *(const char *)b) compare = -1;
return (compare);
}

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = -1;
if (*p1 *p2) compare = 1;
return compare;
}

Still not perfect, overflow might occur. Better:
int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;

return (*p1 *p2) - (*p1 < *p2);
}
Help! How is one less prone to overflow than the other?

--
Ben.
Sep 14 '08 #42

P: n/a
Ben Bacarisse <be********@bsb.me.ukwrites:
"Joachim Schmitz" <no*********@schmitz-digital.dewrites:
>Ron Ford wrote:
>>On Sat, 13 Sep 2008 15:18:32 +0200, Joachim Schmitz posted:
<snip>
>>Thanks, jojo, yours is a cleaner and "better" version. I adapted it
to a charsort:
int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a *(const char *)b) compare = -1;
return (compare);
}

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = -1;
if (*p1 *p2) compare = 1;
return compare;
}

Still not perfect, overflow might occur. Better:
int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;

return (*p1 *p2) - (*p1 < *p2);
}

Help! How is one less prone to overflow than the other?
I have never been so confused in c.l.c as this thread.
Sep 14 '08 #43

P: n/a
Ben Bacarisse wrote:
"Joachim Schmitz" <no*********@schmitz-digital.dewrites:
>Ron Ford wrote:
>>On Sat, 13 Sep 2008 15:18:32 +0200, Joachim Schmitz posted:
<snip>
>>Thanks, jojo, yours is a cleaner and "better" version. I adapted it
to a charsort:
int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a *(const char *)b) compare = -1;
return (compare);
}

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = -1;
if (*p1 *p2) compare = 1;
return compare;
}

Still not perfect, overflow might occur. Better:
int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;

return (*p1 *p2) - (*p1 < *p2);
}

Help! How is one less prone to overflow than the other?
Sorry for the nonsens I wrote ... I meant that using

return *p1 - *p2;

as Richard at one point recommended, might overflow.

However, I'd still prefer

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;

return (*p1 *p2) - (*p1 < *p2);
}

over

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = -1;
if (*p1 *p2) compare = 1;
return compare;
}
Bye, Jojo
Sep 14 '08 #44

P: n/a
Richard wrote:
Ben Bacarisse <be********@bsb.me.ukwrites:
>"Joachim Schmitz" <no*********@schmitz-digital.dewrites:
>>Ron Ford wrote:
On Sat, 13 Sep 2008 15:18:32 +0200, Joachim Schmitz posted:
<snip>
>>>Thanks, jojo, yours is a cleaner and "better" version. I adapted
it to a charsort:
int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a *(const char *)b) compare = -1;
return (compare);
}

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = -1;
if (*p1 *p2) compare = 1;
return compare;
}

Still not perfect, overflow might occur. Better:
int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;

return (*p1 *p2) - (*p1 < *p2);
}

Help! How is one less prone to overflow than the other?

I have never been so confused in c.l.c as this thread.
Sorry about that, my fault. See my other post.
Sep 14 '08 #45

P: n/a
<no name givenwrote:
On Sep 13, 4:49 pm, Ralf Damaschke <rws...@gmx.dewrote:
>Richard wrote:
Richard<rgr...@gmail.comwrites:
int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}
other than the obvious typo of the variable names course ...

It is not really advantageous when the result may be "either
implementation-defined or an implementation-defined signal is
raised" (6.3.1.3).

6.3.1.3 refers to (int)LONG_MAX for example. (where LONG_MAX >
INT_MAX)
Computing (*(int *)p2)-(*(int *)p1) can result in integer overflow
which invokes undefined behavior.
Another (more clear) example is INT_MAX + 1. Just evaluating such
expression invokes undefined behavior.
Hmm, seems my search was too cursory. After doing a longer search
now I only find 6.2.5p9 which somewhat astonishes me as the
fundamental difference between signed and unsigned is introduced
in a mere subordinate clause (in a linguistic sense).

-- Ralf
Sep 14 '08 #46

P: n/a
"Joachim Schmitz" <no*********@schmitz-digital.dewrites:
Ben Bacarisse wrote:
>"Joachim Schmitz" <no*********@schmitz-digital.dewrites:
>>Ron Ford wrote:
On Sat, 13 Sep 2008 15:18:32 +0200, Joachim Schmitz posted:
<snip>
>>>Thanks, jojo, yours is a cleaner and "better" version. I adapted it
to a charsort:
int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a *(const char *)b) compare = -1;
return (compare);
}

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = -1;
if (*p1 *p2) compare = 1;
return compare;
}

Still not perfect, overflow might occur. Better:
int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;

return (*p1 *p2) - (*p1 < *p2);
}

Help! How is one less prone to overflow than the other?

Sorry for the nonsens I wrote ... I meant that using

return *p1 - *p2;

as Richard at one point recommended, might overflow.
It might. But since its a "home rolled" function tend to know the
numbers range. So perfect, and fast, when the ints do not reach ranges
where overflow might occur ....

I wonder what your code looks like where other subtractions with ints
are done. Do you compare them all the time before hand?
Sep 14 '08 #47

P: n/a
On Sep 14, 6:56 pm, Ralf Damaschke <rws...@gmx.dewrote:
<no name givenwrote:
On Sep 13, 4:49 pm, Ralf Damaschke <rws...@gmx.dewrote:
Richard wrote:
Richard<rgr...@gmail.comwrites:
int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}
other than the obvious typo of the variable names course ...
It is not really advantageous when the result may be "either
implementation-defined or an implementation-defined signal is
raised" (6.3.1.3).
6.3.1.3 refers to (int)LONG_MAX for example. (where LONG_MAX >
INT_MAX)
Computing (*(int *)p2)-(*(int *)p1) can result in integer overflow
which invokes undefined behavior.
Another (more clear) example is INT_MAX + 1. Just evaluating such
expression invokes undefined behavior.

Hmm, seems my search was too cursory. After doing a longer search
now I only find 6.2.5p9 which somewhat astonishes me as the
fundamental difference between signed and unsigned is introduced
in a mere subordinate clause (in a linguistic sense).
I'm curious, why "<no name given>"?
Sep 14 '08 #48

P: n/a
vi******@gmail.com writes:
On Sep 14, 6:56 pm, Ralf Damaschke <rws...@gmx.dewrote:
><no name givenwrote:
[25 lines deleted]
>
I'm curious, why "<no name given>"?
Was it necessary to quote the entire article to ask that question?

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Sep 14 '08 #49

P: n/a
On Sep 14, 9:00 pm, Keith Thompson <ks...@mib.orgwrote:
vipps...@gmail.com writes:
On Sep 14, 6:56 pm, Ralf Damaschke <rws...@gmx.dewrote:
<no name givenwrote:
[25 lines deleted]
I'm curious, why "<no name given>"?

Was it necessary to quote the entire article to ask that question?
No... I admit I'm not a good snipper.
Sep 14 '08 #50

61 Replies

This discussion thread is closed

Replies have been disabled for this discussion.