Chinaunix

标题: ( 转 )Linus Torvalds：大多黑客甚至连指针都未理解 [打印本页]

作者: pprpg 时间: 2013-01-10 17:08
标题: ( 转 )Linus Torvalds：大多黑客甚至连指针都未理解
http://www.csdn.net/article/2013 ... wo-star-programming
几周前， 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）又会太过多余。

英文出自：Wordaligned

http://www.csdn.net/article/2013 ... wo-star-programming

作者: liuiang 时间: 2013-01-10 17:28
Mark一下，大神又high level指点了。

作者: zylthinking 时间: 2013-01-10 17:29
他这种写法在内核里面已经好多年了，我看的2.4 内核很多处都是这种写法

作者: starwing83 时间: 2013-01-10 17:31
渣翻译。

其实就是说打破常态，用“跨越式”方法才是hacker们做的……额……我宁愿不当一个hacker，反正这也不是什么好词儿……我宁愿写的更明确点儿

又不是只有这一种方法可以避免条件判断……

作者: pmerofc 时间: 2013-01-10 17:35
提示: 作者被禁止或删除内容自动屏蔽

作者: cokeboL 时间: 2013-01-10 17:43
@liuiang @zylthinking @starwing83 @pmerofc

node * entry = *curr;

复制代码

这句放在for里面好还是外面好？或者，编译之后一样（编译器、优化依赖？）？

作者: cokeboL 时间: 2013-01-10 17:49
本帖最后由 cokeboL 于 2013-01-10 17:50 编辑

@liuiang
@zylthinking
@starwing83
@pmerofc

补充一下，就是

node * entry;
for(...)
{
entry = *node;
}

复制代码

for(...)
{
node * entry = *curr;
}

复制代码

哪个好些？

作者: pmerofc 时间: 2013-01-10 18:08
提示: 作者被禁止或删除内容自动屏蔽

作者: folklore 时间: 2013-01-10 18:13
回复 6# cokeboL

看应用场景，效率或是时间，此外，两者并非100%等价

作者: liuiang 时间: 2013-01-10 18:20
个人对语言理解很浅，编译器则完全不懂。坛里大拿讨论语言，我都是潜水学习的~~~~

作者: wait_rabbit 时间: 2013-01-10 19:07
记得很久以前看过的《C和指针》里就是这种方法。

作者: starwing83 时间: 2013-01-10 19:39
回复 7# cokeboL

后者好。作用域限制。具体性能和写法无关。

刚打了太多字，有点懒，就简单说说好了……

作者: 群雄逐鹿中原 时间: 2013-01-10 19:59
这里有性能问题，大神并非毫无破绽 --
if (rm(entry))
*curr = entry->next;

当连续出现 rm(entry)成立的情况时，对于要删除的节点，不需要往其中写如next指针的。

这里，借助内存记录next指针的动作，就不是很好，
尽量用 CPU寄存器来记录next指针，可以提高效率。

悬赏，谁能给个更好的写法。。

作者: cokeboL 时间: 2013-01-10 20:25
回复 9# folklore

如果是class对象的话，我知道是放循环外面好。

这一个变量，应该是效率上没大差别，但我还是希望能搞明白点

作者: cokeboL 时间: 2013-01-10 20:28
回复 12# starwing83

一个变量的效率影响应该不大，这种简单场景放里面外面对可读性影响也不大。

我知道如果是class对象，放循环里面应该要每次构造，所以放外面效率高些，但是单个变量，不知道
是不是有什么优化之类的背后动作，如果只从效率的角度讲，哪个好些？

作者: hellioncu 时间: 2013-01-10 20:30

cokeboL 发表于 2013-01-10 20:28
回复 12# starwing83

一样的

作者: cokeboL 时间: 2013-01-10 20:30
回复 8# pmerofc

我也这么觉得，而且这个场景，定义外面也不影响可读性，如果代码比较多，定义处和循环出离得稍微远点倒是稍微影响

作者: pmerofc 时间: 2013-01-10 20:39
提示: 作者被禁止或删除内容自动屏蔽

作者: 群雄逐鹿中原 时间: 2013-01-10 21:09
本帖最后由群雄逐鹿中原于 2013-01-10 21:11 编辑

貌似看错了

作者: Ager 时间: 2013-01-10 23:41

pprpg 发表于 2013-01-10 17:08
http://www.csdn.net/article/2013 ... wo-star-programming
几周前， Linus Torvalds在Slashdot上回答了一些问题。其中有一条引发了开发者们的强烈关注，当被问到他心目中的内核黑客时，他说自己这些日子已经不怎么看代码了，除非是帮别人审查。他稍微暂停了一下，坦言那些“狡猾”的通过文件名查找高速缓存又抱怨自己能力一般的内核“恶魔”（黑客）才是他欣赏的。

如果 Linus Torvalds 真的说“此人（黑客）不了解指针”的话，

那么，我为这些黑客喊个冤！

因为这些黑客不了解的，不是指针，

而是链表！

:wink:

作者: fallening_cu 时间: 2013-01-11 07:40

pprpg 发表于 2013-01-10 17:08
http://www.csdn.net/article/2013 ... wo-star-programming
几周前， Linus Torvalds在Slashd ...

都是闲得？

void remove_if(node * head, remove_fn rm);
{
if ( !head ) return;
node* new_head = head->next;
if ( rm(head) ) free(head);
remove_if( new_head, rm );
}

复制代码

作者: fender0107401 时间: 2013-01-11 08:55
不会吧，搞内核开发的都应该懂数据结构吧，懂数据结构都应该懂指针吧。

作者: freshxman 时间: 2013-01-11 08:59
提示: 作者被禁止或删除内容自动屏蔽

作者: pprpg 时间: 2013-01-11 09:08
回复 18# pmerofc

好, 又少了一个中间变量, 而且更容易理解了.

作者: cokeboL 时间: 2013-01-11 09:11
回复 21# fallening_cu

递归不大好吧

作者: pprpg 时间: 2013-01-11 09:18
21F连尾递归用上了, 挺超前的.

作者: pmerofc 时间: 2013-01-11 09:39
提示: 作者被禁止或删除内容自动屏蔽

作者: starwing83 时间: 2013-01-11 10:16
回复 27# pmerofc

你也举得应该是node**罗？

作者: cokeboL 时间: 2013-01-11 10:53
@pmerofc
@starwing83

才细看，21楼那个，改node ** 后，free之后，也还少一句吧？

作者: cokeboL 时间: 2013-01-11 10:54
回复 21# fallening_cu

这应该是错的

作者: pmerofc 时间: 2013-01-11 11:00
提示: 作者被禁止或删除内容自动屏蔽

作者: starwing83 时间: 2013-01-11 11:01
回复 29# cokeboL

你是没细看，我是压根儿就没看。只是从常识上来说，单链表的删除肯定是有可能会修改头指针的，所以要么会return一个node*，要么就得从参数改。怎么都不会是void remove_if(node* n, ...这种的。

作者: pmerofc 时间: 2013-01-11 11:03
提示: 作者被禁止或删除内容自动屏蔽

作者: starwing83 时间: 2013-01-11 11:05
回复 31# pmerofc

貌似的说的只有类型吧~~名字倒是无所谓的……

作者: pmerofc 时间: 2013-01-11 11:07
提示: 作者被禁止或删除内容自动屏蔽

作者: selfrun 时间: 2013-01-11 11:08
递归不能用，链表长点就栈溢出啦;
用node**，是一次处理了整个链表;用node*,函数调完还要擦屁股，这是接口设计上的问题。

作者: starwing83 时间: 2013-01-11 11:09
回复 35# pmerofc

没，我仅指类型，要么返回一个node*，要么参数是node**而不是node*，不然这个删除肯定有问题。既然有问题就用不着看实现了。所以那一层楼我根本就没看，就看到你引用的那一小段我就知道肯定不对头了。

作者: pmerofc 时间: 2013-01-11 11:15
提示: 作者被禁止或删除内容自动屏蔽

作者: bsdc 时间: 2013-01-11 11:22
大牛为何要用两种写法：*head = entry->next; 和 head= &entry->next; 有啥区别吗？

作者: celise 时间: 2013-01-11 11:26
linus的代码习惯一向不是很好

作者: cokeboL 时间: 2013-01-11 12:01
回复 33# pmerofc

我也是，就像你改过的，直接操作head，我之前还发帖子说那种写法，但是看到循环里面的变量先引起疑问，

我就把后面的忽略了

思维太容易被打断了，最近想事情比较多，想一个过一会就忘，看来我又应该

随身带纸笔了

作者: cokeboL 时间: 2013-01-11 12:03
回复 39# bsdc

一个是给二级指针指向者即一级指针赋值，一个是给二级指针赋值

作者: zylthinking 时间: 2013-01-11 12:18
本帖最后由 zylthinking 于 2013-01-11 13:44 编辑

pmerofc 发表于 2013-01-10 20:39
回复 1# pprpg

我大乐，将 for 改成 while 就自以为牛了，还自以为少了一个中间变量而自鸣得意？？？
1. 首先， linus 批判的是不使用双重指针而只能在代码内使用变量记住前一个元素地址的代码，因此，所有本质上和linus 思路一致的都别舔着脸自以为是；
2. 代码改的也是 bug 侧漏，至少与 linus 原来代码不一致；看来经过了这么久，专家的编码水平还是原地踏步

还想着给人解毒呢？？？你就不能不被人揪小辫子么

防止专家改代码，及方便比较，作个备份，专家代码

void remove_if(node ** head, remove_fn rm)
{
node * entry ;
while( (entry = *head)!=NULL )
{
if (rm(entry))
{
*head = entry->next;
free(entry);
}
else
head= &entry->next;
}
}

复制代码

linus 原来代码：

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;
}
}

复制代码

日了日了，是我搞错了，被抓住小辫子了

作者: zylthinking 时间: 2013-01-11 12:24

群雄逐鹿中原发表于 2013-01-10 19:59
这里有性能问题，大神并非毫无破绽 --
if (rm(entry))
*curr = entry->next;

这个 *cur = XXX 也未必一定要在内存记录 next 指针，编译器的优化未必不能做

作者: 群雄逐鹿中原 时间: 2013-01-11 12:39

zylthinking 发表于 2013-01-11 12:24
这个 *cur = XXX 也未必一定要在内存记录 next 指针，编译器的优化未必不能做

除非编译时能理解 free 函数的语义。难。。

作者: zylthinking 时间: 2013-01-11 12:50

群雄逐鹿中原发表于 2013-01-11 12:39
除非编译时能理解 free 函数的语义。难。。

是的，但就算不能优化存在所谓的性能问题，也是算法问题，在一次循环中不处理当前节点而去寻找下几个节点是否一样应该被删除，就算存在这样的方法，就可读性而言，也不是什么好事；而且，这样存在分支判断，就处理器流水线而言，不是什么好事；相反， *curr = entry->next; 之前， *cur 已经在 entry 赋值时被访问过，缓存不命中的可能性很小。

嗯，我就是你和我谈C语言，我和你谈编译器及体系结构的典型

作者: sqfasd 时间: 2013-01-11 12:59
回复 43# zylthinking

没看懂。。。。
能不能请教下您说的pm修改后的bug和不一致在什么地方？

作者: zylthinking 时间: 2013-01-11 13:19

sqfasd 发表于 2013-01-11 12:59
回复 43# zylthinking

没看懂。。。。

*head 在 linus 代码下没有被修改，专家的改了；不要说应该改，不再使用了之类的，然后将这个 bug 算在 linus 头上，或者我吹毛求疵之类的， linus 在先，那么后继就应该严格保证行为一致

作者: hellioncu 时间: 2013-01-11 13:24

zylthinking 发表于 2013-01-11 13:19
*head 在 linus 代码下没有被修改，专家的改了；不要说应该改，不再使用了之类的，然后将这个 bug ...

何必耿耿于怀，应当视而不见

作者: liuiang 时间: 2013-01-11 13:24
我实在无法理解为什么pm一直执着于 “节省一个局部变量”，之前批小乔的时候也是：

xx printxx(struct st * head, ...)
{
struct st * node = head;
for ()
node....
}

复制代码

他就痛批node不应该声明。

在这个贴里面，依然“节省一个局部变量”，而用head进行迭代。用head迭代本来就违背了head的意思。太执着了~~~~~~

作者: cokeboL 时间: 2013-01-11 13:24
回复 48# zylthinking

linus的，第一次循环如果rm了，*head也改了吧？

作者: zylthinking 时间: 2013-01-11 13:28

cokeboL 发表于 2013-01-11 13:24
回复 48# zylthinking

linus的，第一次循环如果rm了，*head也改了吧？

我说的＊head 的值啊，哥哥

node* p = head;
remov_if(&head, xxx);
assert(p == head);

你给我两个都试验一遍

作者: pmerofc 时间: 2013-01-11 13:33
提示: 作者被禁止或删除内容自动屏蔽

作者: zylthinking 时间: 2013-01-11 13:34

liuiang 发表于 2013-01-11 13:24
我实在无法理解为什么pm一直执着于 “节省一个局部变量”，之前批小乔的时候也是：他就痛批node不应该声明。 ...

因为他只知道C语言，不知道有堆栈概念（嗯，这个有典故），不知道 add esp, 4 和 add esp, 8 除了在极端情况下，其实没区别

作者: zylthinking 时间: 2013-01-11 13:35

pmerofc 发表于 2013-01-11 13:33
我实在无法理解为什么你们一定要多用一个本来就不需要的变量
其他参见31楼

已经给你指出区别来了，还装作看不见硬指鹿为马？

作者: cokeboL 时间: 2013-01-11 13:37
回复 52# zylthinking

哥，专家的里也有

else
head= &entry->next;

复制代码

如果第一个不rm，head已经不是刚传进来的head了

不试，要试哥你先试！

作者: zylthinking 时间: 2013-01-11 13:38
本帖最后由 zylthinking 于 2013-01-11 13:40 编辑

cokeboL 发表于 2013-01-11 13:37
回复 52# zylthinking

我晕了，你还是试试吧，非要我这么写你才明白么: head 非 *head????

日了，你立功了，抓住我的小辫子了，我他娘的搞错了

作者: liuiang 时间: 2013-01-11 13:38
确实是Z大神所说的，我居然没有意识到这个问题，pfpf

作者: pmerofc 时间: 2013-01-11 13:43
提示: 作者被禁止或删除内容自动屏蔽

作者: cokeboL 时间: 2013-01-11 13:43
回复 57# zylthinking

我对了？

欠我一顿，记账上了

作者: zhengb302 时间: 2013-01-11 13:43

fender0107401 发表于 2013-01-11 08:55
不会吧，搞内核开发的都应该懂数据结构吧，懂数据结构都应该懂指针吧。

你不知道吧，这样的新闻都是一些媒体（像CSDN）为了点击率/流量而发布上来的，一点意义都没有。纯粹就是为了带来流量。然后引起技术人员的大争论。

作者: 群雄逐鹿中原 时间: 2013-01-11 13:45
57楼，看错正常。我在19楼也这样看错了，赶紧删了。

作者: zylthinking 时间: 2013-01-11 13:48

pmerofc 发表于 2013-01-11 13:43
我的看法同51、56楼

行，这次是我错了，有啥关系，错了就认嘛

作者: sqfasd 时间: 2013-01-11 13:52
回复 63# zylthinking

喜欢你的风格
特别是那句“请授我以鱼，不要授我以渔”，我也准备作为我的格言了= =

作者: liuiang 时间: 2013-01-11 14:04
回复 43# zylthinking

我顺带中招，哈哈。

作者: pmerofc 时间: 2013-01-11 14:04
提示: 作者被禁止或删除内容自动屏蔽

作者: zylthinking 时间: 2013-01-11 14:05

pmerofc 发表于 2013-01-11 14:04
欢迎挑错

一个小建议：

哎呦，翘起来了，当年带情绪的时候挑的错也不是一个两个

作者: cokeboL 时间: 2013-01-11 14:10
回复 67# zylthinking

哥，我是支持你的

作者: 群雄逐鹿中原 时间: 2013-01-11 14:12

pmerofc 发表于 2013-01-11 14:04
欢迎挑错

你省掉一个变量是极大的错误，

逻辑上错了，head和curr表征不一样的东西，统一用head，是不对的。

而且，也没必要。变量到实际使用的内存（或寄存器），还是有差距的。
两个变量，可以使用不同的内存，也可以使用同样的内存。

这里你合并了变量，其实是你注意到用同样的内存能达到目的，
编译器分配stack时，会注意不到这一点，造成浪费资源？

作者: zylthinking 时间: 2013-01-11 14:18

群雄逐鹿中原发表于 2013-01-11 14:12
你省掉一个变量是极大的错误，
逻辑上错了，head和curr表征不一样的东西，统一用head，是不对的 ...

这样挑错就没意思了，和专家风格趋于相同

而且，你说的也不对，编译器还真的没办法优化成专家那样子；因为真的我要耍赖，还是我赢的：
linus 的代码是第一个应该被删除时，才会修改 *head, 而专家的是每次都修改，这两份代码真的还是不一样

，
你要编译器怎么能优化成相同的代码呢

作者: pmerofc 时间: 2013-01-11 14:19
提示: 作者被禁止或删除内容自动屏蔽

作者: zylthinking 时间: 2013-01-11 14:25

zylthinking 发表于 2013-01-11 14:18
这样挑错就没意思了，和专家风格趋于相同
而且，你说的也不对，编译器还真的没办法优化成专 ...

不对，这个不是可有可无的小问题， linus 代码保证调用完后 head 指向剩余的链表的头；
而专家不能保证这一点，他的 head 指向最后一个被删除的节点的前一个

哼哼，还是我赢了

作者: 群雄逐鹿中原 时间: 2013-01-11 14:28

zylthinking 发表于 2013-01-11 14:25
不对，这个不是可有可无的小问题， linus 代码保证调用完后 head 指向剩余的链表的头；
而专家不能保 ...

汗，你这么确信？验证过吗？

我19楼开始就这么认为的，后来发觉自己想错了。

作者: zylthinking 时间: 2013-01-11 14:30
本帖最后由 zylthinking 于 2013-01-11 14:33 编辑

群雄逐鹿中原发表于 2013-01-11 14:28
汗，你这么确信？验证过吗？

我19楼开始就这么认为的，后来发觉自己想错了。

啊？我再想想，有点头晕了。。。。。。。

你帮我分析分析吧，我觉得是啊，现在大脑当机了。。。。。。。。。。

作者: liuiang 时间: 2013-01-11 14:30
回复 72# zylthinking

大神，能否给个准信啊，我懒得想了啊~~~~~~

作者: liuiang 时间: 2013-01-11 14:32
回复 69# 群雄逐鹿中原

我说了很多遍，他听不进去的。

作者: cokeboL 时间: 2013-01-11 14:35
回复 72# zylthinking

哥，今天你是酒后逛论坛。。。

remove_if(&head...) 编译器优化的东西我不懂，但这函数实参那个head两份代码结果之后是一样的

作者: cokeboL 时间: 2013-01-11 14:37
回复 74# zylthinking

最简单的办法，专家的代码直接操作参数，linus的代码新声明一个 cur = head，然后不用head，用cur改变 *cur/*head，

因为head是临时变量，所以无所谓，所以一样。

不过如果这么看的话，我猜编译器会把两个代码优化成一样。。。

作者: sqfasd 时间: 2013-01-11 14:38
回复 74# zylthinking

在函数体内，两个head是不一样的
函数返回后，是一样的，没有影响

作者: zylthinking 时间: 2013-01-11 14:53

cokeboL 发表于 2013-01-11 14:35
回复 72# zylthinking

操，今天是头晕。。。。。。。。。。。。

作者: pitonas 时间: 2013-01-11 14:55
强烈关注

作者: liuiang 时间: 2013-01-11 14:59
不要带着情绪找问题~~~~

作者: cokeboL 时间: 2013-01-11 15:03
回复 80# zylthinking

知道你晕，趁你病要你命

说了支持你的，一点幽默感都没有，跟金毛狮王似的火爆驴脾气

作者: 群雄逐鹿中原 时间: 2013-01-11 15:06
这是两位大婶的程序的编译结果，-O1优化，

作者: liuiang 时间: 2013-01-11 15:13
楼上不厚道，你就不能编译一个能“省一个变量”的二进制版本支持一下pm？

作者: hellioncu 时间: 2013-01-11 15:15

群雄逐鹿中原发表于 2013-01-11 15:06
这是两位大婶的程序的编译结果，-O1优化，

你就等着受教育吧

作者: fallening_cu 时间: 2013-01-11 16:36
本帖最后由 fallening_cu 于 2013-01-11 16:38 编辑

starwing83 发表于 2013-01-11 11:01
回复 29# cokeboL

算了，我不说了

作者: starwing83 时间: 2013-01-11 18:09
回复 87# fallening_cu

别嘛，有事儿都可以说嘛~说不定我判断失误，这世界上存在一种超能力能够在不修改外界指针而且不告诉你应该改成什么的情况下把外界指针改回来的方式么……如果有我当然洗耳恭听罗~

作者: captivated 时间: 2013-01-11 20:40
本帖最后由 captivated 于 2013-01-11 20:49 编辑

int list_append(node_t **h, void *data, int data_size)
{
node_t *n = malloc(sizeof(node_t));
if (!n)
return -1;
n->data = malloc(data_size);
if (!n->data)
{
free(n);
return -1;
}
memcpy(n->data, data, data_size);
n->next = NULL;
// 单链表, 在链表尾端插入链表节点.
node_t **cur = h;
while (*cur)
{
cur = &(*cur)->next;
}
*cur = n;
return 0;
}

复制代码

好吧, 这就是我的单链表尾插实现.

作者: cokeboL 时间: 2013-01-11 22:18
本帖最后由 cokeboL 于 2013-01-11 22:18 编辑

回复 89# captivated

可是，尾插，没有判断，只需要下一个下一个下一个，用二级指针，没比一级多什么便利。。。

好像反倒多了操作。。

作者: captivated 时间: 2013-01-12 00:05
本帖最后由 captivated 于 2013-01-12 00:25 编辑

回复 90# cokeboL

不是的.
我函数的第一个参数是 node_t **h, 这表示调用方不需要有头节点,
调用方只需要创建一个头指针即可.

node_t *list = NULL;
while (1)
{
...
list_append(&list, data, size);
...
}

复制代码

就可以了.

如果, list_append的原型是这样子:
int list_append(node_t *h, void *data, int size);
那么显然在list_append函数中无法改变调用方的头指针, 于是必须要调用方预先提供一个头节点才行.

如果, list_append的原型是这样子:
node_t *list_append(node_t *h, void *data, int size);
那么, 如果list_append中调用malloc失败, 你将如何告诉调用方你的函数失败? -- 返回NULL是不好的(因为这样调用方要自己用多一个临时指针来判断调用是否失败).

那么, 我们最终的原型是
int list_append(node_t **h, void *data, int size);
这代表, 在list_append中, 那么第一次插入的数据就是头节点(也即, 用户传入的头指针是NULL).
所以, 在list_append中, 你需要判断 *h 究竟是不是NULL. 那么使用一级指针的做法如下:

node_t *tmp = *h;
if (*h == NULL)
{
*h = n;
}
else
{
while (tmp->next != NULL)
tmp = tmp->next;
tmp->next = n;
}

复制代码

那么对比一下使用二级指针的做法:

node_t **cur = h;
while (*cur)
cur = &(*cur)->next;
*cur = n;

复制代码

首先, 二级指针的代码简洁了很多. 其次, 二级指针很明显少了一个判断.

其实, 二级指针之于一级指针, 其优势就是在绝大多数情况下, 都能省略掉使用一级指针时那个多余(exceptional)的判断. 当然, 我这个实例的话有些不够说服力, 因为毕竟不循环单链表尾插什么的, 不过是写着玩儿的. 但是, 这个例子毫无疑问确实地体现了二级指针之于一级指针的真正优点所在[如果在系统性能至关重要并且频繁调用的地方, 这个省去的判断是很重要的, 它能提高CPU分支预测的命中率].

作者: cokeboL 时间: 2013-01-12 12:52
回复 91# captivated

我也喜欢链表都传二级指针，这样至少调用链表函数那一组的格式统一，心里舒服

作者: pmerofc 时间: 2013-01-12 12:58
提示: 作者被禁止或删除内容自动屏蔽

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)