C Heap Arrays and Libc Qsort

Background

Years ago I had a solution for the subject problem, but I deleted it when I started using C++ and the STL and didn't need to worry about it any more. However, I now help with a large Open Source project (BRL-CAD), the core of which is still programmed in C (and likely to remain so). Consequently, I recently needed to use qsort on a heap array of pointers and the nightmare cropped up again.

Once more I tried to find a good example that worked and couldn't. All the examples I found used arrays on the stack and they didn't use arrays of pointers. Eventually, I found the solution through some grunt testing and trial and error. I hope someone can use my example now.

The code

#include 
#include 
#include 

const int debug = 0;
/* Define an array of critters to sort. */

typedef struct crit
{
  const char* name;
  int         index;
} crit_t;

const crit_t dat[] =
{
  {"Gonzo",          3},
  {"Fozzie",         3},
  {"Kermit",         1},
  {"Piggy",          2},
  {"Sam",            3},

#if 0
  {"Robin",          6},
  {"Animal",         8},
  {"Camilla",        8},
  {"Sweetums",       9},
  {"Dr. Strpork",   10},
  {"Link Hogthrob", 11},
  {"Zoot",          12},
  {"Dr. Honeydew",  13},
  {"Beaker",        14},
  {"Swedish Chef",  15},
#endif

};
const int ncrits = sizeof(dat)/sizeof(crit_t);

// the sort functions MUST have this signature
int
crit_index_sort(const void* p1, const void* p2)
{
  // cast args into the desired type
  const crit_t* c1 = *(crit_t**)p1;
  const crit_t* c2 = *(crit_t**)p2;

  // now do comparisons
  if (c1->index < c2->index)
    return -1;
  else if (c1->index > c2->index)
    return +1;
  else
    return strcmp(c1->name, c2->name);
}

int
crit_name_sort(const void* p1, const void* p2)
{
  // cast args into the desired type
  const crit_t* c1 = *(crit_t**)p1;
  const crit_t* c2 = *(crit_t**)p2;

  // now do comparisons
  if (debug) {
    printf("DEBUG: comparing %s and %s\n", c1->name, c2->name);
  }
  int ncmp = strcmp(c1->name, c2->name);
  if (ncmp) {
    return ncmp;
  }
  else if (c1->index < c2->index)
    return -1;
  else if (c1->index > c2->index)
    return +1;
  else
    return 0;
}

int
main(int argc, char** argv)
{
  int i;
  // an array from the heap
  crit_t** muppets = (crit_t**)malloc(sizeof(crit_t*) * ncrits);

  // fill it
  for (i = 0; i < ncrits; ++i) {
    crit_t* c = (crit_t*)malloc(sizeof(crit_t));
    c->name = strdup(dat[i].name);
    c->index = dat[i].index;
    muppets[i] = c;
  }

  // show it
  printf("\nUnsorted array:\n");
  for (i = 0; i < ncrits; ++i) {
    printf("  %2d  %s\n", muppets[i]->index, muppets[i]->name);
  }

  // output
#if 0
Unsorted array:
   3  Gonzo
   3  Fozzie
   1  Kermit
   2  Piggy
   3  Sam
#endif

  // alpha sort
  qsort(muppets, ncrits, sizeof(crit_t*), crit_name_sort);

  // show it
  printf("\nSorted by name:\n");
  for (i = 0; i < ncrits; ++i) {
    printf("  %2d  %s\n", muppets[i]->index, muppets[i]->name);
  }

  // index sort
  qsort(muppets, ncrits, sizeof(crit_t*), crit_index_sort);

  // output
#if 0
Sorted by name:
   3  Fozzie
   3  Gonzo
   1  Kermit
   2  Piggy
   3  Sam
#endif

  // show it
  printf("\nSorted by index:\n");
  for (i = 0; i < ncrits; ++i) {
    printf("  %2d  %s\n", muppets[i]->index, muppets[i]->name);
  }

  // output
#if 0
Sorted by index:
   1  Kermit
   2  Piggy
   3  Fozzie
   3  Gonzo
   3  Sam
#endif

}

(to be continued)