Trouble with pointers and pointers to pointers

Question

I'm having some trouble understanding why a piece of code works. The following is a comparison function for stdlib's implementation of qsort:

int scmp(const void *p1, const void * p2)
{
  char *v1, *v2;

  v1 = (char *) p1;
  v2 = (char *) p2;
  return strcmp(v1,v2);
}

Naturally, this only works for strings. My question is: why does the code below work?

int scmp(const void *p1, const void * p2)
{
  char *v1, *v2;

  v1 = *(char **) p1;
  v2 = *(char **) p2;
  return strcmp(v1,v2);
}

It seems to me that in the second version, I'm forcefully casting what clearly is a char* to char**. The problem is that the variable will still contain an address to a char variable. When I apply *, it is my understanding that C will process this command by fetching the contents of p1, and then reading 8 bytes (on my arch) following the address stored inside, so that it will ultimately get a value of type char*. This should, in my opinion, lead to conjoining 8 characters into an invalid memory address.

Still, both functions work equally well. Where am I going wrong?

Answer 1

Let's say you want to sort an array of ints using qsort.

int numbers[] = {10, 50, 35, 62, 22};

First, you create a function that can compare two ints.

int intCompare(void* p1, void* p2)
{
   int n1 = *(int*)p1;
   int n2 = *(int*)p2;
   return (n1 < n2);
}

Then, you can use:

qsort(numbers, 5, sizeof(int), intCompare);

When numbers is passed to qsort, it is decayed to a int* and passed as void*. When we need to extract the number from a void* in intCompare, we need to cast it to int* before we dereference the pointer and compare the values.

Taking the analogy to strings, let's say you want to sort:

char* strings[] = { "abc", "xyz", "def" };

The call to qsort will be:

qsort(strings, 3, sizeof(char*), scmp);

When strings is passed to qsort, it is decayed to a char** and passed as void*. The underlying types of the pointers being passed to to scmp by qsort will be of type char**, not char*. Hence, it is correct to use:

int scmp(const void *p1, const void * p2)
{
  char *v1, *v2;

  v1 = *(char **) p1;
  v2 = *(char **) p2;
  return strcmp(v1,v2);
}

The first version works due to lucky coincidence in some cases. Here's an example program that shows couple of cases where it does not work while the second version should always work.

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

// First version of scmp
int scmp1(const void *p1, const void * p2)
{
  char *v1, *v2;

  v1 = (char *) p1;
  v2 = (char *) p2;
  return strcmp(v1,v2);
}

// Second version of scmp
int scmp2(const void *p1, const void * p2)
{
  char *v1, *v2;

  v1 = *(char **) p1;
  v2 = *(char **) p2;
  return strcmp(v1,v2);
}

void test1()
{
   char* strings[] = { "abc", "xyz", "def" };
   qsort(strings,  3, sizeof(char*), scmp1);
   for( int i = 0; i < 3; ++i )
   {
      printf("%s\n", strings[i]);
   }
   printf("\n");
}

void test2()
{
   char* strings[] = { "abc", "xyz", "def" };
   qsort(strings,  3, sizeof(char*), scmp2);
   for( int i = 0; i < 3; ++i )
   {
      printf("%s\n", strings[i]);
   }
   printf("\n");
}

void test3()
{
   char** strings = malloc(3*sizeof(char*));
   strings[0] = "abc";
   strings[1] = "xyz";
   strings[2] = "def";

   qsort(strings,  3, sizeof(char*), scmp1);
   for( int i = 0; i < 3; ++i )
   {
      printf("%s\n", strings[i]);
   }

   free(strings);
   printf("\n");
}

void test4()
{
   char** strings = malloc(3*sizeof(char*));
   strings[0] = "abc";
   strings[1] = "xyz";
   strings[2] = "def";

   qsort(strings,  3, sizeof(char*), scmp2);

   for( int i = 0; i < 3; ++i )
   {
      printf("%s\n", strings[i]);
   }

   free(strings);
   printf("\n");
}

int main()
{
   // Does not work.
   test1();

   // Should work always.
   test2();

   // Does not work.
   test3();

   // Should work always.
   test4();
}

Output (using gcc 4.8.4):

abc
xyz
def

abc
def
xyz

abc
xyz
def

abc
def
xyz