Using stdlib's qsort() to sort an array of strings

Question

Some preface: I'm a computer engineering student taking a first class in C after 3 semesters of Java (up to data structures). This question is in relation to a homework assignment, but a few steps removed from solving it for me.

I have an input file that I read into memory such that it is stored in char[9][500]. I read in at most 500 strings of maximum length 8. I am attempting to sort this array using stdlib's built in qsort() function, and am having some memory errors.

Important snippets of code:

char data[4][500][60];
char debug[500][9];
size_t count = 0;

/* initialize file, open for reading */
FILE* pUserlog;
pUserlog = fopen("userlog","r");

while(!feof(pUserlog))
{
    fscanf(pUserlog, "%9s %8s %16s",debug[count], data[1][count], data[2][count]);
    fgets(data[3][count], 60, pUserlog);
    count++;
}

This section reads the data into the arrays. The array of interest in this part is "debug". This is the array specified above. Here is my comparison function for qsort:

int compare(const void* a, const void* b)
{
    const char **ia = (const char **)a;
    const char **ib = (const char **)b;
    puts("I'm in compare!");
    return strncmp(*ia, *ib,8);
}

This is my attempt to call qsort:

size_t debug_len = sizeof(debug)/sizeof(char*);
printf("debug len: %d, count: %d, sizeof(char*): %d\n",debug_len,count,sizeof(char*));
qsort(debug,count, sizeof(char *), compare);

I attempted substituting debug_len in my call where count is, but I am still segfaulting. Here is the output:

$ ./test
debug len: 1125, count: 453, sizeof(char*): 4
I'm in compare!
Segmentation fault (core dumped)

Thank you!

Answer 1

The compare function will receive pointers to the elements that are being compared. You are effectively trying to compare characters using strncmp(). Since you have pointers to each of the strings, cast it to a char * and compare.

int compare(const void* a, const void* b)
{
    const char *ia = (const char *)a;
    const char *ib = (const char *)b;
    puts("I'm in compare!");
    return strncmp(ia, ib, 9);
}

Remember also, it's an array of arrays, not an array of pointers. So the size of an element should be the size of the array, 9 and not of the pointer, 4. At this point, it would be easier to just use sizeof debug[0] since it is a two-dimensional array. If you don't do this with the right sizes, qsort() will just destroy your array.

size_t elemsize = sizeof debug[0];      /*   9 - size of each element */
size_t count = sizeof(debug)/elemsize;  /* 500 - number of elements in array */
qsort(debug, count, elemsize, compare);

Answer 2

What happens here is: you've got 500 strings. Now you pass all 500 to qsort, and it in turn passes each one as first and second argument to your compare function. It's a bit like writing this:

compare(debug[0], debug[1])

The C compiler passes the addresses, not the actual values of course. But now you interpret the pointer-to-void as pointer-to-pointer-to-char. Your code now does a dereference when calling strncmp, but that makes the value (the first 4 bytes) be treated as a pointer in strncmp. But strncmp will now in turn try to dereference the garbage "pointer" (which consists of part of one of your strings) and that makes bang.

To fix this, use char * instead of char **:

int compare(const void* a, const void* b)
{
    puts("I'm in compare!");
    return strncmp((const char *)a, (const char *)b, 8);
}