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!

while( !feof() ) is wrong. feof will return false, the loop will be entered, the scanf will fail to read data, debug[ count ] will contain bogus data, and then feof will return true. You can fix this case by doing count-- after the loop, but in general you should simply never do while( !feof()) — William Pursell
– William Pursell, Commented Mar 20, 2011 at 19:12
Where does it segfault? It is a good exercise to examine the core dump to determine where the segfault happens, as that usually tells you what the problem is. — William Pursell
– William Pursell, Commented Mar 20, 2011 at 19:14

Jeff Mercado · Accepted Answer · 2011-03-20 20:49:05Z

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);

DarkDust · Accepted Answer · 2011-03-21 07:16:34Z

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);
}

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related