Questions about character array pointers and secondary pointers and the cmp function in the qsort function

Question

//Sort character array lexicographically (main code):
char* words[MAX_SIZE];
qsort(words, len, sizeof(char*), cmp);
int cmp(const void* w1, const void* w2) {
    char** str1 = w1;
    char** str2 = w2;
    return strcmp(*str1, *str2);
    //return strcmp(w1, w2);
}

Why does the cmp function have to define a secondary pointer to output normally? Why can't it directly return strcmp(w1, w2);? Please! Help!

My understanding is that w1 and w2 are pointers (words) pointing to the string head pointer (words[i]), \ is the pointer of the pointer, and needs to be dereferenced to compare. Is it right？

Answer 1

Here’s as visual an answer as I can figure:

What you know vs what qsort() knows

You know that your array is an array of char*.

qsort() only knows it has an array of bytes. That is why you also have to tell it how many bytes each element takes (in our example we are pretending a char* is 4 bytes, though on modern hardware it is almost always 8), in addition to the number of elements in the array.

When qsort() then calls your comparison function, it does not know that it has an array of char*. It has an array of bytes.

Consequently it also cannot pass you the element (the char*) directly. So it passes a pointer to the element. So a pointer to byte 12 is a pointer to the 4^th element (index == 3) of the strings array, meaning it is a pointer to a char*.

A pointer to a pointer to a character: char**.

Remembering still that qsort() does not know (or care) what the pointer points to, you get just a simple void*.

Hence, the comparison function just takes pointers, and inside the function you must turn that pointer into a pointer to the correct thing.

The comparison function (strings)

If your array is an array of strings (char*s), then:

int pstrcmp( void* ptr_to_a, void* ptr_to_b )
{
  // Convert the argument to the correct type of pointer
  char** ptr_to_string_a = ptr_to_a;
  char** ptr_to_string_b = ptr_to_b;

  // Access the pointed-to array element
  char* a = *ptr_to_string_a;
  char* b = *ptr_to_string_b;

  return strcmp( a, b );
}

We can, of course, just reduce that to a simple:

int pstrcmp( void* ptr_to_a, void* ptr_to_b )
{
  return strcmp( *(char**)ptr_to_a, *(char**)ptr_to_b );
}

The comparison function (integers)

For comparison, if our array were an array of integers:

   int integers[5];

Then qsort() would still not know what the elements were, and would still give you a pointer to each element. A pointer to an integer is just int*.

int pcmpint( void* ptr_to_a, void* ptr_to_b )
{
  // Convert the argument to the correct type of pointer
  int* ptr_to_int_a = ptr_to_a;
  int* ptr_to_int_b = ptr_to_b;

  // Access the pointed-to array element
  int a = *ptr_to_int_a;
  int b = *ptr_to_int_b;

  if (a < b) return -1;
  if (b < a) return  1;
  return 0;
}

Or, more succinctly:

int pcmpint( void* ptr_to_a, void* ptr_to_b )
{
  if (*(int*)ptr_to_a < *(int*)ptr_to_b) return -1;
  if (*(int*)ptr_to_b < *(int*)ptr_to_a) return  1;
  return 0;
}

For simple types like integers you will often see the following, just because it is more readable. (The compiler can generate identical code for all these variants.)

int pcmpint( void* ptr_to_a, void* ptr_to_b )
{
  int a = *(int*)ptr_to_a;
  int b = *(int*)ptr_to_b;

  if (a < b) return -1;
  if (b < a) return  1;
  return 0;
}