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)

A contacts and genealogy database

One of my long-term projects has been the desire for a centralized contacts database (DB) that can be used in multiple places. Over the years I've used PDAs, MS Access, etc.

My MS Access database is currently the repository for all my personal contacts, and I have a working process to produce a Christmas mailing list and mailing labels with it: csv dump of selected fields, take csv file to Linux box, use Perl program to generate PostScript files for labels, convert ps to pdf, print pdf file anywhere (if you print from Adobe, remember to select no scaling).

Recently I've started using my Google Mail contacts and have happily discovered that I can get it synched so I can access it from my iPhone, and I have written Perl programs to enable up- and downloading my Google contacts.

But I still don't have exactly what I want. First, I really want my central database completely under my control without Microsoft (or Google) in the way. Second, I realize the flat contact lists I have need to really be a single relational database to accommodate the relational aspects of my contact data as realized in a simple Christmas card list, e.g., children of friends and family grow up and start families of their own, thereby becoming a new entry for the mailing list. Third, I want my database to be available online to friends and family to use and update. And fourth, I want it to be the authoritative source for all my personal contacts and family information.

As I've studied the problem, I've decided that my database really needs to be designed to handle many aspects of a genealogy database, in fact, I think they could really be different views of the same. After reorienting my design plans, I've been searching for an existing, open source database solution and looked at a couple (using the site Database Answers as a helpful guide along the way):

• grubba, a general purpose DB
• GRAMPS, a genealogical DB

but none of them really seem to fit the bill (also I found a good argument that the standard genealogical database format is not ideal).

Then I stumbled upon what I think is the epitome of a good genealogy and contacts DB design, which happens to use PostgreSQL, my RDBMS of choice, in Leif Kristensen's Yggdrasil. Leif has done yeoman's work in designing a genealogy database, necessary functions, and a web interface access to it. His database has provided me practical insights into how to accomplish my goals, and I am indebted to him for showing the way.

To be continued...