2

I need to sort an array of pointers to struc. In fact, I need to do searching among adresses to see if a given pointer to a struct is present in the array. Unfortunately, I don't have nothing "comparable" inside those structures and so I want to sort'em just by address. My code is like that:

item* arr[SIZE];
//something is inserted
qsort(arr, SIZE, sizeof(item*), (void*)compare_funct); 
//CUT
bsearch(curr, arr, SIZE, sizeof(item*), (void*)compare_funct);

I tried creating a compare_funct just casting pointers to int and returning their difference, but it doesn't seem to work. In particular, when I do the bsearch, even if I know that the element is contained inside the array, I always get a NULL as returned value.

alk
  • 69,737
  • 10
  • 105
  • 255
Raffo
  • 1,642
  • 6
  • 24
  • 41

2 Answers2

5
int cmp_items(void const *p, void const *q)
{
    item const *a = *(item const **)p, *b = *(item const **)q;
    return b - a;
}

(Please don't cast compare_funct to void*. That doesn't do anything except turn off type checking provoke undefined behavior.)

EDIT: As @R.. points out, the above exhibits undefined behavior unless a and b point into a common array. For full portability (but at the expense of immediate comprehensibility), you should use

int compare_pointers(void const *p, void const *q)
{
    return memcmp(p, q, sizeof(item *));
}
Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • It's even worse than only turning off type checking: it's undefined behaviour. One can not safely cast a function pointer to a data pointer and vice versa. Imagine what happens on a Harvard architecture machine (separate busses for data and program) or on old DOS compiler in compact (32 bit data, 16 bit function pointer) or medium memory model (16 bit data and 32 bit function pointer). – Patrick Schlüter May 29 '11 at 15:49
  • While we're at it, `b-a` is also undefined behavior unless `b` and `a` happen to point into a common array. The portable version is `memcmp(&a, &b, sizeof a);` - comparing the *representations* of the pointers byte-for-byte rather than trying to take their difference. – R.. GitHub STOP HELPING ICE May 29 '11 at 16:39
  • And you could simplify it to just `memcmp(p, q, sizeof(item *));` – R.. GitHub STOP HELPING ICE May 29 '11 at 16:41
0

Look here.

This one describes it pretty well think of it as pointers to struct instead of pointers to char.

Basically the idea is to pass struct** casted to (void*) then you put it back to struct** dereference to get struct* and then just do a compare.

Getting the cast right with qsort can be tricky.

Community
  • 1
  • 1
Eduard Thamm
  • 942
  • 1
  • 6
  • 7