Beautiful Code

In a recent TED Talk Linus Torvalds gave a simple example for beautiful code; the kind of code he aims for within Linux. It is the kind of code that everyone should strive for.

The particular example was as simple as deleting an entry from a singly linked list. Here is the (adapted) code.

typedef struct list_node {
	void *payload;
	struct list_node *next;
} list_node;

list_node *head;

remove_list_entry(entry)
{
	prev = NULL;
	walk = head;

	while (walk != entry) {
		prev = walk;
		walk = walk->next;
	}

	if (!prev) {
		head = entry->next;
	} else {
		prev->next = entry->next;
	}
}

The list itself is defined straightforward: It consists of nodes with a payload and a next pointer. The head points to the first entry in the list. The removal function iterates over all entries, until the correct one is found and then removes it by modifying the next pointer of the previous element. When the head has to be removed an extra branch is taken as the head has no previous entry.

The trick that turns this into beautiful code is to remove the extra branch by adding an indirection. This also drops the need for keeping a prev pointer.

remove_list_entry(entry)
{
	indirect = &head;

	while ((*indirect) != entry) {
		indirect = &(*indirect)->next;
	}

	*indirect = entry->next
}

The idea here is that we don’t actually care about the entry we want to remove, but just about the thing pointing to it. For each entry there is a list_node * pointing to it. That one has to be changed. So if we want to remove the head indirect corresponds to &head and &(prev->next) otherwise.

The nice thing is that this indirection make the code shorter and less code contains less errors. It also contains less branches and may even run faster.