two_star.txt

A few weeks ago Linus Torvalds answered some questions (http://meta.slashdot.org/story/12/10/11/0030249/linus-torvalds-answers-your-questions) on slashdot. All his responses make good reading but one in particular caught my eye. Asked to describe his favourite kernel hack, Torvalds grumbles he rarely looks at code these days — unless it’s to sort out someone else’s mess. He then pauses to admit he’s proud of the kernel’s fiendishly cunning filename lookup cache before continuing to moan about incompetence.

几周前，Linus Torvalds 在 slashdot 上回答了一些问题。他的所有回答都值得一读，而其中之一尤其引起我的注意。当问及最喜欢的内核技巧，Tarvalds 说道，近来已经很少读代码 -- 除非需要修复他人引发的问题。随后，他承认自己为巧妙精密的文件名查找缓存的实现而自豪，但随即便抱怨起大多数人的能力缺陷。
____
At the opposite end of the spectrum, I actually wish more people understood the really core low-level kind of coding. Not big, complex stuff like the lockless name lookup, but simply good use of pointers-to-pointers etc. For example, I’ve seen too many people who delete a singly-linked list entry by keeping track of the prev entry, and then to delete the entry, doing something like

于此相对的，我其实希望更多人能理解核心的底层编程技巧。非巨大而复杂的技艺如同命名查找，而是像指针的指针这样简单的诀窍。举例说，我见过太多人，通过临时记录先前的节点，根据条件判断，来删除单链表的节点，如下面这样：

[source, c]
----
if (prev)
    prev->next = entry->next;
else
    list_head = entry->next;
----
and whenever I see code like that, I just go “This person doesn’t understand pointers”. And it’s sadly quite common.

任何时候看到这样的代码，我便能断定“这人不懂指针”。遗憾的是，这常常发生。

People who understand pointers just use a ``pointer to the entry pointer'', and initialize that with the address of the `list_head`. And then as they traverse the list, they can remove the entry without using any conditionals, by just doing a `*pp = entry->next`.

懂指针的人，会利用一个 ``指向节点指针的指针'' ，并将其初始化为 `list_head` 的地址。这样在遍历链表时，他们通过简单的 `*pp = entry->next` ，便可以无需任何条件判断而正确删除节点。
____

Well _I thought_ I understood pointers but, sad to say, if asked to implement a list removal function I too would have kept track of the previous list node. Here’s a sketch of the code:

尽管我 _自认为_ 理解指针，但遗憾的是，如果要求我实现一个链表删除的函数，我大可能也会临时记录先前节点的指针。代码框架如下：

.This person doesn’t understand pointers
[source, c]
----
typedef struct node
{
    struct node * next;
    ....
} node;

typedef bool (* remove_fn)(node const * v);

// Remove all nodes from the supplied list for which the 
// supplied remove function returns true.
// Returns the new head of the list.
node * remove_if(node * head, remove_fn rm)
{
    for (node * prev = NULL, * curr = head; curr != NULL; )
    {
        node * const next = curr->next;
        if (rm(curr))
        {
            if (prev)
                prev->next = next;
            else
                head = next;
            free(curr);
        }
        else
            prev = curr;
        curr = next;
    }
    return head;
}
----

The linked list is a simple but perfectly-formed structure built from nothing more than a pointer-per-node and a sentinel value, but the code to modify such lists can be subtle. No wonder linked lists feature in so many interview questions (https://www.google.com/search?q=linked+list+interview+questions) !

这一简单的链表结构，无外乎指向节点的指针及标记（哨兵），但修改节点的代码却很微妙。面试中出现如此多的链表题也就不令人奇怪了。

The subtlety in the implementation shown above is the conditional required to handle any nodes removed from the head of the list.

这一实现的细节在于上面的条件判断，来处理删除表头的情况。

Now let’s look at the implementation Linus Torvalds had in mind. In this case we pass in a pointer to the list head, and the list traversal and modification is done using a pointer to the next pointers.

下面来看 Linus Torvalds 设想的实现。这里我们传入指向链表头的指针，并通过一个指向下一个节点指针的指针来遍历和修改链表。

.Two star programming
[source, c]
----
void remove_if(node ** head, remove_fn rm)
{
    for (node** curr = head; *curr; )
    {
        node * entry = *curr;
        if (rm(entry))
        {
            *curr = entry->next;
            free(entry);
        }
        else
            curr = &entry->next;
    }
}
----

Much better! The key insight is that the links in a linked list are pointers and so pointers to pointers are the prime candidates for modifying such a list.

好多了！关键点在于，连接链表的是指针，于是指针的指针应该是修改这样链表的首选。

'''

The improved version of `remove_if()` is an example of two star programming: the doubled-up asterisks indicate two levels of indirection. A third star (http://c2.com/cgi/wiki?ThreeStarProgrammer) would be one too many.

这一改进的 `remove_if()` 是双星编程的例子：两个星号表达了两层的间接引用。而三星就显得过多了。