对话Linus大神：大多黑客连指针没弄明白 -小弟我没弄没明白这文章本身

对话Linus大神：大多黑客连指针没弄明白 ---我没弄没明白这文章本身
摘要：Linus Torvalds坦言那些狡诈的通过文件名查找高速缓存，然后又抱怨自己能力一般的内核“恶魔”才是他欣赏的；相反，很多人连低水平的内核编程都还没学好。
几周前， Linus Torvalds在Slashdot上回答了一些问题。其中有一条引发了开发者们的强烈关注，当被问到他心目中的内核黑客时，他说自己这些日子已经不怎么看代码了，除非是帮别人审查。他稍微暂停了一下，坦言那些“狡猾”的通过文件名查找高速缓存又抱怨自己能力一般的内核“恶魔”（黑客）才是他欣赏的。

他说：
相反，很多人连低水平的内核编程都还没学好。像lockless用名字查找（name lookup）功能即使不大也不复杂，却是指针到指针的一个简单及良好的使用方法。比如，我曾看见过许多人通过跟踪上一页条目删除一个单向链接的列表项，然后删除该条目。例如：
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)
{
for (node * prev = NULL, * curr = head; curr != NULL; )
{
node * next = curr->next;
if (rm(curr))
{
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)
{
for (node** curr = head; *curr; )
{
node * entry = *curr;
if (rm(entry))
{
*curr = entry->next;
free(entry);

}
else
curr = &entry->next;
}
}
好多了！最关键的部分在于：链表中的链接都是指针，因此指针到指针是修改链表的首选方案。
改进版的remove_if()是一个使用双重星号的例子，双重星号象征着两重间接寻址，再加一个星（third star）又会太过多余。
-------------------------------我是分割线-----------------------------------------------
问题1：文章里的rm函数想实现什么功能呢？看样子是返回bool值，如果是判断rm（a)的a是否为NULL，那for循环里的判断还有毛用？
问题2：“比如，我曾看见过许多人通过跟踪上一页条目删除一个单向链接的列表项，然后删除该条目。”为啥要跟踪上一个啊？这里的prev指针意义何在？
问题3：后面用到了一个二级指针实现删除链表，为啥要二级指针啊？传进来head，判断head是否为空，不空free掉，head指向下一个结点，继续判断不就行了，我看自己的教材上就这么实现的，二级指针意义何在？指针链表二级指针 free
[解决办法]
下面是我的看法：
1.
根据typedef bool (* remove_fn)(node const * v); 这一句，我能猜测到rm其实是一个函数指针，这个函数能够判断是否删除当前节点。
2.
如果你不懂prev这个变量干什么用的话，证明你没有看懂那代码，而且看书没有看明白，并且没有做过链表的删除操作之类的实践。你不知道没有了prev会导致断链。
3.
至于第三个问题，我也看了比较长的时间那个代码才想明白的。
这个可以分为两步：
1）


node * entry = *curr; 
//和
rm(entry)

这两句可以看出他是预先向后操作，也就是curr指针为当前节点，但删除的是curr后面的节点，这样就不用判断curr前面的节点是否为head指针了，少一个判断，提高效率。（普通人的代码是curr指向当前节点，然后删除当前节点，这样容易脱节，必须跟踪上一节点）
2)二级指针操作更加直接，比如我有a,b,c三个连续的节点，我要删除b，那么正常人的思维应该是:


a-&gt;next = b-&gt;next;
free(b);
//此时算法的curr指向b结构体

大神的思维是这样的：


node **p = a-&gt;next;
*p = b-&gt;next;
free(b);
//此时大神算法的curr指向a-&gt;next，结构体的next成员的地址，此处才是精华

现在就对比一下二级指针的好处：
如果不用二级指针，那么我们每一次操作都必须通过一个结构体指针来计算出next成员的地址，而我们对链表的删除操作无非就是对结构体的next成员的操作，用二级指针直接指向next成员，免得每次都需要通过结构体的指针来计算next成员的偏移地址，操作就变得更加直接了。我们正常人的思维其实是绕弯了。
[解决办法]
rm是判断curr是否为空，你这个理解不对，remove_if嘛，故名思议是有数据部分符合条件的做移除...
[解决办法]
看这篇文章吧。
[解决办法]

引用:

假如这是个不带头结点的单链表，rm是判断curr是否为空。初始prev指向NULL，curr指向第一个结点，next指向第二个结点，然后判断curr不为空进入第一个if，判断prev为空进入else，head指向第二个结点，然后释放第一个结点，然后curr指向第二个结点，第一次循环结束。
第二次循环，prev还是指向NULL，curr指向第二个结点，next指向第三个结点，之后prev会一直指向NULL，我就不明白这个prev是干什么了。

rm不是判断是否为空，而是判断节点是否为删除的节点，
rm其实是属于这样一个函数


typedef struct node  
{  
    struct node * next;  
    int data;  //假设节点的定义为这样
} node;  

//rm函数类似于下面的定义，如果你想删除链表中data为5的节点的话
remove_fn check_node(node const * v){
 if(v.data == 5){//删除data的值为5的节点
   return TRUE;
 }
 
 return FALSE;
}

对话Linus大神：大多黑客连指针没弄明

热点推荐