几周前,Linus Torvalds在Slashdot上回答了一些问题。其中有一条引发了开发者们的强烈关注,当被问到他心目中的内核开发者时,他说自己这些日子已经不怎么看代码了,除非是帮别人审查。他稍微暂停了一下,坦言那些“狡猾”的通过文件名查找高速缓存又抱怨自己能力一般的内核“恶魔”(黑客)才是他欣赏的。
他说:
我真的希望更多人能理解真正核心的低层代码。不是无锁名字查找那种大而复杂的代码,只是正确的使用指针的指针而已。比如,我曾看见过许多人通过跟踪上一页条目删除一个单向链接的列表项,然后删除该条目。

例如:

if (prev)  
    prev->next = entry->next;  
else  
    list_head = entry->next;

每当我看到这些的代码,我会说:“此人不了解指针”。这还是一个可悲的、常见的问题。
如果开发者能够理解指针,只需要使用“指向该条目的指针”并初始化list_head,然后贯穿列表,此时无需使用任何条件语句即可删除该条目,只需通过 *pp = entry->next。
我想我理解指针,但不幸的是,如果要实现删除函数,我会一直保持跟踪前面的列表节点。这里是代码草稿:

不理解指针的人做法:

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)  //rm是判定这个结点要不要删除
{  
    for (node * prev = NULL, * curr = head; curr != NULL; )  
    {  
        node * next = curr->next;  
        if (rm(curr))    //如果满足rm就删除curr,如果curr是头结点就把head指向curr->next
        {  
            if (prev)                   
                prev->next = curr->next;  
            else  
                head = curr->next;  
            free(curr);  
        }  
        else             //如果不满足就向下遍历
            prev = curr;  
            curr = next;  
    }  
    return head;         //看起来感觉没毛病
} 

这个链表很简单,但可以把每个节点的指针和sentinel值构建成了一个完美的结构体,但是修改这个表的代码需要很精妙。难怪链表功能会常出现在许多面试环节中。
上面执行的代码是处理从列表头中删除任何节点所需的条件。
现在,让我们好好记住Linus Torvalds的执行代码。在这种情况下,我们通过一个指针指向列表头来贯穿列表遍历修改。

Two star programming:

void remove_if(node ** head, remove_fn rm)  //Linus的方法是用二重指针遍历链表
{  
    for (node** curr = head; *curr; )  
    {  
        node * entry = *curr;              //使用一个指针记录当前结点
        if (rm(entry))  
        {  
            *curr = entry->next;           //注意关键来了:如果满足rm,将二重指针当前指向的值改写为下个结点,然后删除当前结点
            free(entry);  
        }  
        else  
            curr = &entry->next;           //如果不满足就使用二重指针向下遍历
    }  
} 

好多了!最关键的部分在于:链表中的链接都是指针,因此二重指针是修改链表的首选方案。
改进版的remove_if()是一个使用双重星号的例子,双重星号象征着两重间接寻址,再加一个星(third star)又会太过多余。

个人认为其实这篇文章的根本是在说遍历一个类似的容器时,应该使用指针进行遍历,同时通过指针访问结点值进行修改。即便是数组这种最基本的结构,本质上还是靠指向元素的指针来访问元素。即使上例中所谓“不理解指针的人”的做法非常普遍,甚至绝大多数大公司和教材中都是用这样的方法遍历链表,但仔细想想这种方法每次都要操作两个结构体指针一个元素一个元素地往下赋值,效率并没有使用二重指针高。