Getting segmentation fault using qsort and simple strcmp function in C?

Question

GDB print commands suggest that my array and its contents are formatted correctly ('asdf' , '\00000') but I get a segfault in in my qsort call that traces back to the comparison function I pass it. All I can surmise is that I am somehow passing qsort a null pointer, or that my strings are formatted incorrectly which doesn't seem to be the case to me.

/** Word type, used to store elements of the word list,
    with room for a word of up to 20 characters. */
typedef char Word[ WORD_MAX + 1 ];

edit: added definiton of Word to question^^

typedef struct {
/** Number of words in the wordlist. */
int len;
  /** Capacity of the WordList, so we can know when we need to resize. */
  int capacity;
  /** List of words.  Should be sorted lexicographically once the word list
      has been read in. */
  Word *words;
} WordList;

The readWordList function takes in a .txt file that is formatted:

3 the
5 hello
3 foo
...

The integer represents the number of chars in the string that follows it. validChar is just a boolean check to see if the incoming char is within a certain range. I removed some code that doesn't pertain directly to the issue such as fopen and a few initializations.

/**
 * comparison function for qsort in readWordList
 */
static int cmp(const void *p1, const void *p2){
  return strcmp(* (char * const *)  p1, * (char * const *) p2);
}

WordList *readWordList( char const *fname ){
  //malloc space for newList
  WordList *newList = ( WordList * ) malloc( sizeof( WordList ) );
  //set capacity to 10
  newList->capacity = START_CAPACITY;
...
  newList->words = ( Word * ) calloc(newList->capacity, sizeof( Word ) );
...
  while( fscanf( toRead, "%d ", &numChars ) == 1 )
  {
    //realloc space for Word *words if necessary
    if(newList->len >= newList->capacity)
    {
      newList->capacity *= 2;
      //check dereferencing
      newList->words = (Word *)realloc(newList->words, newList->capacity * sizeof(Word));
    }
    //if word is longer than 20 chars skip it
    if(numChars > WORD_MAX)
      continue;
    else
    {
      for(int i = 0; i < numChars; i++)
      {
        ch = fgetc(toRead);
          if(validChar(ch)){
            newList->words[newList->len][i] = ch;
            if(i == numChars-1){
              newList->words[(newList->len)][numChars] = '\0';
            }
          }else{
            continue;
          }
      }
      //debug
      printf("%s\n",newList->words[newList->len]);
      //increase length of wordlist
      newList->len += 1;
    }
  }
  qsort(newList->words, newList->len, sizeof(Word), cmp);
  return newList;
}

Here is my valgrind error: (wordlist.c:76) refers to the qsort call;

==59199== Invalid read of size 1
==59199==    at 0x10000AAC9: _platform_strcmp (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==59199==    by 0x100000C92: cmp (wordlist.c:23)
==59199==    by 0x1001F2BDE: _qsort (in /usr/lib/system/libsystem_c.dylib)
==59199==    by 0x100000C5E: readWordList (wordlist.c:76)
==59199==    by 0x1000007A8: main (pack.c:52)
==59199==  Address 0x656874 is not stack'd, malloc'd or (recently) free'd
==59199== 
==59199== 
==59199== Process terminating with default action of signal 11 (SIGSEGV)
==59199==  Access not within mapped region at address 0x656874
==59199==    at 0x10000AAC9: _platform_strcmp (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==59199==    by 0x100000C92: cmp (wordlist.c:23)
==59199==    by 0x1001F2BDE: _qsort (in /usr/lib/system/libsystem_c.dylib)
==59199==    by 0x100000C5E: readWordList (wordlist.c:76)
==59199==    by 0x1000007A8: main (pack.c:52)
==59199==  If you believe this happened as a result of a stack
==59199==  overflow in your program's main thread (unlikely but
==59199==  possible), you can try to increase the size of the
==59199==  main thread stack using the --main-stacksize= flag.
==59199==  The main thread stack size used in this run was 8388608.

"Address 0x656874" It's reading the string `"\x74\x68\x65"` (`"the"`), including the final `'\0'`, as an address. In other words, it's dereferencing a `char*` twice. Are you sure those `*` in the call to `strcmp` are supposed to be there? — , Nov 12 '15 at 14:10
In C you [should not cast the result of `malloc`](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) or any other function returning `void *` (like e.g. `realloc`). — Some programmer dude, Nov 12 '15 at 14:14
I have added the definition of word - sorry about that. It is simply a char array. — Harrison, Nov 12 '15 at 14:26
The `else { continue; }` is superfluous, but also has no effect on the problem whatsoever. — Jonathan Leffler, Nov 12 '15 at 15:23

Sergey Kalinichenko · Accepted Answer · 2015-11-12T14:33:20.633

3

Your code performs an invalid cast: qsort passes you back a pointer to Word, but your cmp function treats it as a const pointer to a char pointer.

Since Word is a typedef for a fixed-size array of char, it is not the same as a pointer to pointer. You should perform a cast to a pointer to Word in your cmp, not to a pointer to pointer:

static int cmp(const void *p1, const void *p2){
    const Word *lhs = p1;
    const Word *rhs = p2;
    return strcmp((const char*)*lhs, (const char*)*rhs);
}

edited Nov 12 '15 at 14:33

answered Nov 12 '15 at 14:19

Sergey Kalinichenko

714,442
84
1,110
1,523

Doesn't `qsort` pass the pointers to the elements to the compare function? If `Word` is a pointer to `char` then `cmp` should receive a pointer to pointer to `char` – Kevin Nov 12 '15 at 14:22
@Kevin You are right. Now that OP has provided a definition of `Word`, I needed to edit the fix. – Sergey Kalinichenko Nov 12 '15 at 14:30
This was the issue, however, I am not so sure about your usage of lhs and rhs, did you mean to use those in the strcmp call? Regardless... thanks! – Harrison Nov 12 '15 at 14:31
@Harrison Yes, I did mean to use them in `strcmp` call. Thanks for pointing it out. – Sergey Kalinichenko Nov 12 '15 at 14:33

Getting segmentation fault using qsort and simple strcmp function in C?

1 Answers1