Why this code using qsort function doesn't work in C?

Question

The sorting part:

 order = (struct order_s **) calloc(pm->len - q, sizeof(struct order_s*)); for (i = 0; i < window_pos; ++i) { order[i] = (struct order_s *) malloc(sizeof(struct order_s)); order[i]->pos = i; order[i]->good = good[i]; } for (i = window_pos + q; i < pm->len; ++i) { order[i-q] = (struct order_s *) malloc(sizeof(struct order_s)); order[i-q]->pos = i; order[i-q]->good = good[i]; } qsort(order, pm->len - q, sizeof(struct order_s *), compare);

The compare function:

int compare (const void * a, const void * b) { if ((((const struct order_s *)a)->good - ((const struct order_s *)b)->good) > 0) return 1; else return -1; }

The stucture:

struct order_s { int pos; double good; };

The values:

(gdb) p pm->len $35 = 20 (gdb) p window_pos $36 = 1 (gdb) p q $37 = 5

Before qsort():

(gdb) p *order[0] $2 = {pos = 0, good = 1.3238653863672125} (gdb) p *order[1] $3 = {pos = 6, good = 0.96180564211148134} (gdb) p *order[2] $4 = {pos = 7, good = 1.0684181637005736} (gdb) p *order[3] $5 = {pos = 8, good = 0.92113662370476379}

After qsort():

(gdb) n (gdb) p *order[0] $6 = {pos = 0, good = 1.3238653863672125} (gdb) p *order[1] $7 = {pos = 6, good = 0.96180564211148134} (gdb) p *order[2] $8 = {pos = 7, good = 1.0684181637005736} (gdb) p *order[3] $9 = {pos = 8, good = 0.92113662370476379}

After the qsort function, the array of structure isn't sorted right and throws the segment fault later.

So what does it do? Do the values look sane if you break inside compare? — Useless
– Useless, Commented Aug 30, 2012 at 15:41
Good test, just stick a printf inside your compare temporarily and look at the values which are getting compared. You may be surprised. — Alan Corey
– Alan Corey, Commented Oct 28, 2018 at 23:34

hmjd · Accepted Answer · 2012-08-30 15:50:47Z

The compare() function arguments are pointers to elements of the array. In this case, the elements of the array are struct order*, which means the arguments to compare() are struct order**, not struct order*.

Change to:

int compare (const void * a, const void * b) { const struct order_s** aa = a; const struct order_s** bb = b; /* Can two 'order_s' instances never be equal ? */ if ( (*aa)->good - (*bb)->good) > 0) return 1; else return -1; }

From the C99 standard section 7.20.5.2 The qsort function:

The contents of the array are sorted into ascending order according to a comparison function pointed to by compar, which is called with two arguments that point to the objects being compared. The function shall return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.

I think compare() still has a problem since it never returns 0. It's conceivable (though unlikely) that qsort could call the comparator with pointers to the same object. If it doesn't get 0 for that, you're gonna have a bad time.

Collectives™ on Stack Overflow

Why this code using qsort function doesn't work in C?

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related