Three-star programming

Here’s an example of three star programming. We start with a structure. We’ll want to put these onto a list, so we’d better include a link.

struct node {
  struct node *next;
  /* other stuff */
};

Cool. Now, suppose we want to build up our list of things. Easy. Start with a list head.

struct node *head = 0;

Now, make up nodes and string them onto the list.

for (/* whatever */) {
  struct node *n = malloc(sizeof(*n));
  if (!n) panic();
  /* fill in n */
  n->next = head;
  head = n;
}

Snag. The list comes out backwards. Maybe you don’t care. I do.

We can make the list come out in the right order by remembering where the end of it is.

struct node **tail = &head;

There: two stars already. And now we can build it forwards.

for (/* whatever */) {
  struct node *n = malloc(sizeof(*n));
  if (!n) panic();
  /* fill in n */
  *tail = n;
  tail = &n->next;
}

Oops. That doesn’t terminate the list.

*tail = 0;

Done.

As noted, we’re now two-star programmers. Now, suppose that we don’t generate all of our list nodes in the same place. Maybe there’s a collection of different functions which need to add their own contributions to our list. Well, now we need to pass in the tail pointer. But, alas, the function needs to update our tail so that we can add more stuff to the end later. So we need to pass the address of tail.

void add_stuff(struct node ***tail)
{
  for (/* whatever */) {
    struct node *n = malloc(sizeof(*n));
    if (!n) panic();
    /* fill in n */
    **tail = n;
    *tail = &n->next;
  }
}

And we’re home.

I don’t think that was particularly tricky. And I’ve had to do this on a number of occasions. It’s almost worth inventing some macrology for, but not quite. Let’s just call it a ‘design pattern’ then.