Friday, 9 August 2013

Reuse comparison function

Reuse comparison function

I have builded a binary tree using an AVL and then data is packed in an array
typedef struct {
void **data;
int count;
} t_table;
The comparison function looks like:
int cmp(const void *pa, const void *pb)
{
int a = *(int *)pa;
int b = *(int *)pb;
if (a > b)
return +1;
else
if (b > a)
return -1;
else
return 0;
}
I am inserting in avl-tree and sorting the array of pointers using K&R
qsort without problems.
Now I want to use the sandard function qsort of <stdlib.h> but I am forced
to use a new function for t_table (due to pointer conversion required by
qsort), it looks like:
int cmp(const void *pa, const void *pb)
{
int a = *(int*)(*(void**)pa);
int b = *(int*)(*(void**)pb);
if (a > b)
return +1;
else
if (b > a)
return -1;
else
return 0;
}
I understand why the function must be changed (quoting C-FAQ):
To understand why the curious pointer conversions in a qsort comparison
function are necessary (and why a cast of the function pointer when
calling qsort can't help), it's useful to think about how qsort works.
qsort doesn't know anything about the type or representation of the data
being sorted: it just shuffles around little chunks of memory. (All it
knows about the chunks is their size, which you specify in qsort's third
argument.) To determine whether two chunks need swapping, qsort calls your
comparison function. (To swap them, it uses the equivalent of memcpy.)
But I wonder if there is any alternative (using stdlib qsort) to avoid
having to maintain two comparison functions (one for avl and another for
void **)

No comments:

Post a Comment