Cool Stuff I Learned on the Job

During the last week, I had the opportunity (after 5 years of Java) to return to writing some C code – yep, you read that right – not even C++, but straight C. I’m sure glad we have C99 and C11 now because I don’t know what I’d do if I couldn’t even declare variables within a for statement.

During this time, I realized that there are some really cool things I learned while working my first engineering job years ago at Novell. I was part of the Novell Directory Services team (later renamed eDirectory). I made a lot of friends in that job and a few of them taught me some really great techniques.

For example, I needed to use a singly linked list and (C being what it is, and all) there just aren’t any library routines for it, so you have to write it yourself. Yes, yes, there are myriad libraries out there at places like github that supply all the code you could want – I’m talking about STANDARD library routines. The most complex function in the C standard library is qsort. After working in the Java world for the last 7 years, I find it hard to go back to a language where you have to write your own data structures.

I needed a way to traverse the list and remove an element matching some search criteria. Now, this is an old problem – people have solved it already, right? So I headed over to my favorite best-solution site, StackOverflow. If you need to know how the majority of folks do stuff, that’s where you go. I found… nothing… well, nothing elegant anyway. There were any number of solutions involving multiple if statements checking various boundary conditions to handle everything perfectly. Then I remembered what my old mentor Dale Olds taught me about this topic – or, rather, I remembered MOST of it. It took me the better part of an hour to remember in enough detail to actually reimplement it.

This blog post will be a running post, updated as I remember little techniques like this. Hopefully, by the time I’m done in a few years, I’ll have a nice library to rely on.

Remove an Element from a Singly Linked List

Let’s consider what we have in a singly linked list. Well, we have a head pointer and nodes with a next pointer. Perhaps a tail pointer, but only if you’re using it like a FIFO queue or something, where you can append to the tail and remove from the head. Let’s just stick to the basics – a head pointer and a next pointer in each node. To traverse from the head to a node matching some search criteria and remove that node, you must keep track of your current node, and the previous node. Or do you? The actual fact is, you only need to keep track of the current node and the previous node’s next pointer and herein lies the elegance. Here’s how we did it back in the day:

static struct node_t *head;
...
struct node_t **pprev, *cur;
for (pprev = &head, cur = *pprev; cur; pprev = &cur->next, cur = *pprev)
    if (is_match(cur) {
        *pprev = cur->next; /* unlink cur */
        break;
    }
return cur;

The really elegant thing about this technique is that head pointer maintenance is automatic. No need to do something special if the matching node is the one pointed to by head. Because you’re only dealing with the address of the previous node’s next pointer, and head looks just like one of those when you’re dealing with its address and not its value. You can treat it just like you would any other next pointer. Cool, huh?

Heads or Tails

This technique loses a bit of its elegance when you decide to maintain a tail pointer. Now you really do need to keep track of the address of the previous node; if the node you decide to remove is the current tail then you need to repoint the tail at the previous node. In short, the address of the previous node’s next pointer is no longer sufficient. Here’s a possible implementation:

static struct node_t *head, *tail;
...
struct node_t **pprev, *prev, *cur;
for (pprev = &head, prev = NULL, cur = *pprev; cur; 
        pprev = &cur->next, prev = cur, cur = *pprev)
    if (is_match(cur) {
        if (cur == tail)
            tail = prev;
        *pprev = cur->next; /* unlink cur */
        break;
    }
return cur;

In this case, we’re tracking all the same information, plus the address of the previous node (which is NULL in case we’re removing the first node).

Advertisements