qsorting type int**

Folks,
>
Attempting to q-sort an array of int pairs, e.g. {{0,1}, {0, 0}, ...}
allocated using malloc/calloc, but the arguments I'm passing to qsort
are producing the incorrect results (see listing 1). Works for auto
object duration (e.g. heap) as in listing 2. Any ideas?
>
Thanks,
BEA
>
/* listing 1 : using malloc/calloc */
>
#include <stdio.h>
#include <stdlib.h>
>
int compare( const void *arg1, const void *arg2 ) {
printf("arg1 %d, %d\n", ((int *) arg1)[0], ((int *) arg1)[1]);
printf("arg2 %d, %d\n", ((int *) arg2)[0], ((int *) arg2)[1]);
fflush(stdout);
>
if (((int *) arg1)[0] ((int *) arg2)[0]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
if (((int *) arg1)[1] ((int *) arg2)[1]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
return 0;
} else if (((int *) arg1)[0] < ((int *) arg2)[0]) {
return 1;
}
} else
return 1;
>
}
>
int main(int argc, char *argv[]) {
int i;
int **x;
>
x = malloc(6 * sizeof(int *));
>
for (i = 0; i < 6; ++i) {
x[i] = calloc(2, sizeof(int));
}
>
/* assignments */
x[0][0] = 1;
x[0][1] = 3;
x[1][0] = 0;
x[1][1] = 2;
x[2][0] = 2;
x[2][1] = 6;
x[3][0] = 0;
x[3][1] = 1;
x[4][0] = 1;
x[4][1] = 7;
x[5][0] = 2;
x[5][1] = 1;
>
for (i = 0; i < 6; ++i)
printf("%d, %d\n", x[i][0], x[i][1]);
printf("\n");
fflush(stdout);
>
/* Sort remaining args using Quicksort algorithm: */
qsort( (void *)x, 6, sizeof( x[0] ), compare );
>
printf("\n");
for (i = 0; i < 6; ++i)
printf("%d, %d\n", x[i][0], x[i][1]);
>
for (i = 0; i < 6; ++i) {
free(x[i]);
}
free(x);
>
}
>
=====
>
/* listing 2: using heap store */
>
#include <stdlib.h>
>
int compare( const void *arg1, const void *arg2 ) {
printf("arg1 %d, %d\n", ((int *) arg1)[0], ((int *) arg1)[1]);
printf("arg2 %d, %d\n", ((int *) arg2)[0], ((int *) arg2)[1]);
>
if (((int *) arg1)[0] ((int *) arg2)[0]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
if (((int *) arg1)[1] ((int *) arg2)[1]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
return 0;
} else if (((int *) arg1)[0] < ((int *) arg2)[0]) {
return 1;
}
} else
return 1;
>
}
>
int main(int argc, char *argv[]) {
int i;
int x[6][2] = {
{1,3},
{0,2},
{2,6},
{0,1},
{1,7},
{2,1}};
>
for (i = 0; i < 6; ++i)
printf("%d, %d\n", x[i][0], x[i][1]);
printf("\n");
>
/* Sort remaining args using Quicksort algorithm: */
qsort( (void *)x, 6, sizeof( x[0] ), compare );
>
printf("\n");
for (i = 0; i < 6; ++i)
printf("%d, %d\n", x[i][0], x[i][1]);
>
}

int compare( const void *arg1, const void *arg2 ) {
printf("arg1 %d, %d\n", ((int *) arg1)[0], ((int *) arg1)[1]);
printf("arg2 %d, %d\n", ((int *) arg2)[0], ((int *) arg2)[1]);
fflush(stdout);
>
if (((int *) arg1)[0] ((int *) arg2)[0]) {

return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {

/* Sort remaining args using Quicksort algorithm: */
qsort( (void *)x, 6, sizeof( x[0] ), compare );

/* listing 2: using heap store */

>
Attempting to q-sort an array of int pairs, e.g. {{0,1}, {0, 0}, ...}
allocated using malloc/calloc, but the arguments I'm passing to qsort
are producing the incorrect results (see listing 1). Works for auto
object duration (e.g. heap) as in listing 2. Any ideas?

/* listing 1 : using malloc/calloc */
>
#include <stdio.h>
#include <stdlib.h>
>
int compare( const void *arg1, const void *arg2 ) {
printf("arg1 %d, %d\n", ((int *) arg1)[0], ((int *) arg1)[1]);
printf("arg2 %d, %d\n", ((int *) arg2)[0], ((int *) arg2)[1]);
fflush(stdout);
>
if (((int *) arg1)[0] ((int *) arg2)[0]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
if (((int *) arg1)[1] ((int *) arg2)[1]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
return 0;
} else if (((int *) arg1)[0] < ((int *) arg2)[0]) {
return 1;
}
} else
return 1;
}

int main(int argc, char *argv[]) {
int i;
int **x;
>
x = malloc(6 * sizeof(int *));

for (i = 0; i < 6; ++i) {
x[i] = calloc(2, sizeof(int));

/* assignments */

for (i = 0; i < 6; ++i)
printf("%d, %d\n", x[i][0], x[i][1]);
printf("\n");
fflush(stdout);

/* Sort remaining args using Quicksort algorithm: */
qsort( (void *)x, 6, sizeof( x[0] ), compare );

On Thu, 1 Mar 2007 beagle...@hotmail.com wrote:
>
>
>>
First guess, without even looking at the code: You'll be trying to
treat int[2] as if it were int*, or vice versa. Let's see if I'm right...
>
>
>>>>>
Aaugh! Blecch! Ick! You shouldn't have any casts in your code, and
a straightforward comparison like this should be maybe five lines long,
at most. Here's something equivalent to what you wrote:
>
int compare( const void *va, const void *vb ) {
int *a = va;
int *b = vb;
printf("arg1 %d, %d\n", a[0], a[1]);
printf("arg2 %d, %d\n", b[0], b[1]);
>
if (a[0] b[0]) {
return -1;
} else if (a[0] == b[0]) {
return (a[1] b[1]) ? -1 : (a[0] < b[0]);
} else return 1;
}
>
Now, I notice two things: First, you have a couple of typos; you
write a[0] (or rather, ((int *)arg1)[0]) where you mean a[1] (or
rather, ((int *)arg1)[1]). So my code isn't really doing quite the
same thing as yours, because I'm not invoking undefined behavior
by falling off the end of the function without returning a value.
>
If you had compiled your code with warnings turned on ("gcc -W -Wall"),
you would have found this error at once.
>
The other thing I notice is that you're treating the input
arguments as if they were pointers to int, which is not the case ---
or if it is, then you're comparing different elements of the sorted
array, which isn't kosher at all. Let's see which is the case...
>>>
x = malloc(6 * sizeof *x);
>>
x[i] = malloc(2 * sizeof *x[i]);
'calloc' is only useful if you need the memory zeroed for some reason.
Since you immediately assign new values into it, you don't need it to
be zeroed.
>>
[snip]
>>
You don't need to 'fflush' an output stream if you've just written a
newline to it; the newline flushes the stream by itself already.
>>
qsort(x, 6, sizeof *x, compare);
>
...And here's the problem, exactly as I thought at first. You're trying
to qsort an array of 'int*', but your comparison function is written
(almost) as if you're trying to sort an array of 'int[2]'.
>
The comparison function for 'qsort' should be written this way, in
order to sort an array of T:
>
int compare(const void *va, const void *vb)
{
const T *a = va;
const T *b = vb;
return (*a < *b) ? -1 : (*a *b);
>
}
>
Or if T is a small type, such as your int*:
>
int compare(const void *va, const void *vb)
{
T a = *(const T *)va;
T b = *(const T *)vb;
return (a < b) ? -1 : (a b);
>
}
>
Therefore, what you wanted was:
>
int compare(const void *va, const void *vb)
{
int *a = *(int * const *)va;
int *b = *(int * const *)vb;
if (a[0] < b[0]) return -1;
if (a[0] b[0]) return -1;
return (a[1] < b[1]) ? -1 : (a[1] b[1]);
>
}
>
Five lines --- what'd I tell you? :)
>
HTH,
-Arthur

int compare( const void *va, const void *vb ) {
int *a = va;
int *b = vb;
printf("arg1 %d, %d\n", a[0], a[1]);
printf("arg2 %d, %d\n", b[0], b[1]);
>
if (a[0] b[0]) {
return -1;
} else if (a[0] == b[0]) {
return (a[1] b[1]) ? -1 : (a[0] < b[0]);
} else return 1;
}

>

>
int compare(const void *va, const void *vb)
{
int *a = *(int * const *)va;
int *b = *(int * const *)vb;
if (a[0] < b[0]) return -1;
if (a[0] b[0]) return -1;
return (a[1] < b[1]) ? -1 : (a[1] b[1]);
}

beagle...@hotmail.com writes:>>
You're trying to treat these arguments as if they point to ints.
They don't. They point to int *s. Thus, you should be casting
them to int ** or, better yet, assigning them to a variable of
type "const int **".
>>
[...]
>>
qsort isn't necessarily implemented as a quicksort.
>
The cast here should be unnecessary.
>
[...]
>>
I don't see any use of malloc in this version. Usually that's
what programmers mean when they say "heap".
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

On Thu, 1 Mar 2007 beagle...@hotmail.com wrote:
>
>
>>
First guess, without even looking at the code: You'll be trying to
treat int[2] as if it were int*, or vice versa. Let's see if I'm right...
>
>
>>>>>
Aaugh! Blecch! Ick! You shouldn't have any casts in your code, and
a straightforward comparison like this should be maybe five lines long,
at most. Here's something equivalent to what you wrote:
>
int compare( const void *va, const void *vb ) {
int *a = va;
int *b = vb;
printf("arg1 %d, %d\n", a[0], a[1]);
printf("arg2 %d, %d\n", b[0], b[1]);
>
if (a[0] b[0]) {
return -1;
} else if (a[0] == b[0]) {
return (a[1] b[1]) ? -1 : (a[0] < b[0]);
} else return 1;
}
>
Now, I notice two things: First, you have a couple of typos; you
write a[0] (or rather, ((int *)arg1)[0]) where you mean a[1] (or
rather, ((int *)arg1)[1]). So my code isn't really doing quite the
same thing as yours, because I'm not invoking undefined behavior
by falling off the end of the function without returning a value.
>
If you had compiled your code with warnings turned on ("gcc -W -Wall"),
you would have found this error at once.
>
The other thing I notice is that you're treating the input
arguments as if they were pointers to int, which is not the case ---
or if it is, then you're comparing different elements of the sorted
array, which isn't kosher at all. Let's see which is the case...
>>>
x = malloc(6 * sizeof *x);
>>
x[i] = malloc(2 * sizeof *x[i]);
'calloc' is only useful if you need the memory zeroed for some reason.
Since you immediately assign new values into it, you don't need it to
be zeroed.
>>
[snip]
>>
You don't need to 'fflush' an output stream if you've just written a
newline to it; the newline flushes the stream by itself already.
>>
qsort(x, 6, sizeof *x, compare);
>
...And here's the problem, exactly as I thought at first. You're trying
to qsort an array of 'int*', but your comparison function is written
(almost) as if you're trying to sort an array of 'int[2]'.
>
The comparison function for 'qsort' should be written this way, in
order to sort an array of T:
>
int compare(const void *va, const void *vb)
{
const T *a = va;
const T *b = vb;
return (*a < *b) ? -1 : (*a *b);
>
}
>
Or if T is a small type, such as your int*:
>
int compare(const void *va, const void *vb)
{
T a = *(const T *)va;
T b = *(const T *)vb;
return (a < b) ? -1 : (a b);
>
}
>
Therefore, what you wanted was:
>
int compare(const void *va, const void *vb)
{
int *a = *(int * const *)va;
int *b = *(int * const *)vb;
if (a[0] < b[0]) return -1;
if (a[0] b[0]) return -1;
return (a[1] < b[1]) ? -1 : (a[1] b[1]);
>
}
>
Five lines --- what'd I tell you? :)
>
HTH,
-Arthur