QSORT function in C

Question

In the following code, once I remove the commented part which compares strings, I am getting a seg 11 fault. I am unable to understand why! Rest of the code is working fine. Any help is appreciated!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare_scores_desc(const void* scorea, const void* scoreb){
int a = *(int*)scorea;
int b = *(int*)scoreb;
return a-b;
}

int compare_names(const void* namea, const void* nameb){
char** a = *(char**)namea;
char** b = *(char**)nameb;
return strcmp(*a,*b);
}

int main(int argc, char* argv[]){
int scores[7] = {456,234,65,563,67,19,100};
int i;
qsort(scores,7,sizeof(int),compare_scores_desc);
puts("\nThese are the scores in order : \n");
for(i=0;i<7;i++)
    printf("%i\n",scores[i]);
char *names[] = {"Krishna","Rama","Bhishma","Arjuna"};
/*qsort(names,4,sizeof(char*),compare_names);*/
puts("------------------");
puts("The names in order are : \n");
for(i=0;i<4;i++)
    printf("%s\n",names[i]);
return 0;
}

jxh · Accepted Answer · 2013-08-14T23:48:22.683

6

In compare_names(), you are inappropriately dereferencing the arguments after the cast. The types for the local variables are type char **, but you are casting the arguments as char ** and dereferencing that results in a char *.

namea and nameb are pointers to the elements of your array names[] declared in main(). That means, their types are actually pointer to char *. When you dereferenced these arguments but assigned them to a char **, you cause the local variable to treat the char * as a char ** (your compiler should have issued a diagnostic warning you about this problem). Now, you take a pointer value that is a char *, and dereference it when you pass it to strcmp(). This causes the program to treat sizeof(char *) bytes of the string as a pointer value for the strcmp() function. Since 4 or 8 (or whatever sizeof(char *) is) bytes consisting of printable characters reinterpreted as a pointer value rarely yields a valid pointer, when strcmp() tries to use those pointers, a segmentation fault occurs.

One possible fix is to not dereference when you initialize your local variables. However, the arguments are const void *, so you can avoid the cast altogether if you declare your local variables to be a pointer to a const type:

int compare_names(const void* namea, const void* nameb){
char* const * a = namea;
char* const * b = nameb;
return strcmp(*a,*b);
}

Note that your implementation of compare_scores_desc() fails if a - b results in signed integer overflow. For example, if a is INT_MAX and b is -1. You should fix your implementation to work for all cases.

int compare_scores_desc(const void* scorea, const void* scoreb){
const int *a = scorea;
const int *b = scoreb;
return (*a > *b) - (*a < *b);
}

edited Aug 14 '13 at 23:48

answered Aug 14 '13 at 21:04

jxh

69,070
8
110
193

@Kaz: I had seen it before, but I really took it to heart when i read [Ambroz's answer](http://stackoverflow.com/a/10997428/315052). – jxh Aug 15 '13 at 00:50
There is no need for this `char * const *` business here at all. The pointers inside the array are not const qualified (and the array cannot possibly be sorted if they are!). The callback function passes const-qualified pointers for some unclear reason, perhaps to say "please don't modify the array elements while I am sorting them because I will get confused". – Kaz Aug 15 '13 at 05:17
@Kaz: There is no need for it except to get the assignment to work without a cast. – jxh Aug 15 '13 at 05:18
The `const` in `char* const * a = namea;` matches properly with `const` in `const void* namea,`. Amen to that. But the dereferencing of `*a` results in `char *`, which is OK for `strcmp(const char *, ...)` and _unfortunately_ OK for functions like `foo(char *, ...)`. But `*a`, points to values like `"Krishna"` which is type `const char *`. Thus the best declaration for 'a' is `const char* const * a = namea;` This would flag usages of functions like `foo(char *, ...)`. – chux - Reinstate Monica Aug 15 '13 at 13:17
@chux: I was aware of this, but I chose to allow the `compare_names()` type to match the type used for `names[]` in `main()`. It is unfortunate that C allows string literals to be assigned to `char *` without complaint, but it does. – jxh Aug 15 '13 at 14:28
Thanks. I mentally had put a `const` before `char *names[]` for I did not known one could initialize in this fashion. It appears I am wrong. `names[0]` is a pointer to `char *` memory that is _initialized_ to "Krishna". `names[0]` is _not_ a pointer to `const char *` memory that contains "Krishna". Do you concur? – chux - Reinstate Monica Aug 15 '13 at 16:31
@chux: The type of `names[0]` is `char *`, it is pointing to a string literal with which it was initialized. Apparently, string literals are special. They define an array of `char` (**not** `const char`), but attempts to modify the array contents results in undefined behavior. See C.11 §6.4.5 ¶6-7. – jxh Aug 15 '13 at 17:32

score 2 · Answer 2 · answered Aug 15 '13 at 00:16

The problem is in your string comparison function, and here is probably the minimal way to fix it:

int compare_names(const void* namea, const void* nameb){
char* a = *(char**)namea;
char* b = *(char**)nameb;
return strcmp(a,b);
}

The namea and nameb arguments are pointers into the string vector. You understand this, which is why you used the char ** type.

However, all you have to do in the function is retrieve the char * pointers from that array. These char * pointers are already strings. You do not have to dereference them again; just pass them to strcmp.

Your original code has a constraint violation which requires a diagnostic. That should have tipped you off:

/* originally */
char** a = *(char**)namea; /* error: initialization from incompatible type */

You're dereferencing a char **, which produces char *, but you're storing that in a char ** again and dereferencing again, thereby wrongly treating the character data as a pointer.

QSORT function in C

2 Answers2