Linus:利用二级指针删除单向链表

Linus:利用二级指针删除单向链表

感谢网友full_of_bull投递此文(注:此文最初发表在这个这里,我对原文后半段修改了许多,并加入了插图)

Linus大婶在slashdot上回答一些编程爱好者的提问,其中一个人问他什么样的代码是他所喜好的,大婶表述了自己一些观点之后,举了一个指针的例子,解释了什么才是core low-level coding

下面是Linus的教学原文及翻译——

“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。(在这段话的最后,我实际上希望更多的人了解什么是真正的核心底层代码。这并不像无锁文件名查询(注:可能是git源码里的设计)那样庞大、复杂,只是仅仅像诸如使用二级指针那样简单的技术。例如,我见过很多人在删除一个单项链表的时候,维护了一个”prev”表项指针,然后删除当前表项,就像这样)”

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”. (了解指针的人会使用链表头的地址来初始化一个“指向节点指针的指针”。当遍历链表的时候,可以不用任何条件判断(注:指prev是否为链表头)就能移除某个节点,只要写)

*pp = entry->next

So there’s lots of pride in doing the small details right. It may not be big and important code, but I do like seeing code where people really thought about the details, and clearly also were thinking about the compiler being able to generate efficient code (rather than hoping that the compiler is so smart that it can make efficient code *despite* the state of the original source code). (纠正细节是令人自豪的事。也许这段代码并非庞大和重要,但我喜欢看那些注重代码细节的人写的代码,也就是清楚地了解如何才能编译出有效代码(而不是寄望于聪明的编译器来产生有效代码,即使是那些原始的汇编代码))。

Linus举了一个单向链表的例子,但给出的代码太短了,一般的人很难搞明白这两个代码后面的含义。正好,有个编程爱好者阅读了这段话,并给出了一个比较完整的代码。他的话我就不翻译了,下面给出代码说明。

如果我们需要写一个remove_if(link*, rm_cond_func*)的函数,也就是传入一个单向链表,和一个自定义的是否删除的函数,然后返回处理后的链接。

这个代码不难,基本上所有的教科书都会提供下面的代码示例,而这种写法也是大公司的面试题标准模板:

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

这里remove_fn由调用查提供的一个是否删除当前实体结点的函数指针,其会判断删除条件是否成立。这段代码维护了两个节点指针prev和curr,标准的教科书写法——删除当前结点时,需要一个previous的指针,并且还要这里还需要做一个边界条件的判断——curr是否为链表头。于是,要删除一个节点(不是表头),只要将前一个节点的next指向当前节点的next指向的对象,即下一个节点(即:prev->next = curr->next),然后释放当前节点。

但在Linus看来,这是不懂指针的人的做法。那么,什么是core low-level coding呢?那就是有效地利用二级指针,将其作为管理和操作链表的首要选项。代码如下:

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

同上一段代码有何改进呢?我们看到:不需要prev指针了,也不需要再去判断是否为链表头了,但是,curr变成了一个指向指针的指针。这正是这段程序的精妙之处。(注意,我所highlight的那三行代码)

让我们来人肉跑一下这个代码,对于——

  • 删除节点是表头的情况,输入参数中传入head的二级指针,在for循环里将其初始化curr,然后entry就是*head(*curr),我们马上删除它,那么第8行就等效于*head = (*head)->next,就是删除表头的实现。
  • 删除节点不是表头的情况,对于上面的代码,我们可以看到——

1)(第12行)如果不删除当前结点 —— curr保存的是当前结点next指针的地址

2)(第5行) entry 保存了 *curr —— 这意味着在下一次循环:entry就是prev->next指针所指向的内存。

3)(第8行)删除结点:*curr = entry->next; —— 于是:prev->next 指向了 entry -> next;

是不是很巧妙?我们可以只用一个二级指针来操作链表,对所有节点都一样。

如果你对上面的代码和描述理解上有困难的话,你可以看看下图的示意:

(全文完)

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

好烂啊有点差凑合看看还不错很精彩 (54 人打了分,平均分: 4.28 )
Loading...

Linus:利用二级指针删除单向链表》的相关评论

  1. 加个间接层,用二级指针屏蔽了prev为空的case,此时二级指针指向head,这技巧不错。不过老实说指针的指针,除了那帮一直搞这个的大婶们能运用自如外,对我等屌丝,这类代码可读性并不高。

  2. 你的理解好像错了,那一句
    curr = &entry->next;
    是不能写成
    curr = (node**)entry的。

    这样定义node,LZ的方法仍然可行,你可以编码试试。
    typedef struct node
    {
    ….
    struct node * next;
    }@viho_he

  3. 程序看完很快懂了,但是总觉得不放心,因为自己写不出来
    然后看了评论 又想了一会才弄明白本质

  4. remember that, in the scope of the loop, curr always points directly to the pointer that pointed you to the current node, whether it was the head of the list or the next pointer of the previous node, so *curr lets you modify that pointer.
    抄过来的:)放在这里帮助大家理解。
    在循环的作用域里,curr永远指向那个引导你到当前结点的指针,无论这个指针是head指针还是prev结点的next指针,所以*curr提供了一种可以操作那个指针的方法。

  5. @ZFang
    你的代码好长。。。我只简单测试了下删除和保留数基本一致的情况,linus的代码比原先那个还要慢5%左右(用gettimeofday取的时间)。

  6. 感觉好像是做了点手脚让第一个指针能像节点一样用而已,然后就按没有头来处理,我能说这是技巧吗?

  7. 大概是现在的CPU分支预测什么的做得很好了吧。linus的代码的确把那个if分支给拿掉了,但是二级指针却导致了更多的访存,而访存的速度。。。@wxd356

  8. 下面这个代码同样去掉了那个if,理解起来也比较容易。
    void remove2(node **phead, func rm)
    {
    node *head = *phead, *prev, *curr;
    for (prev = head, curr = head->next; curr != NULL; )
    {
    node *const next = curr->next;
    if (rm(curr))
    {
    prev->next = next;
    free(curr);
    }
    else
    prev = curr;
    curr = next;
    }
    if (head->val) {
    *phead = head->next;
    free(head);
    }
    }

  9. 多年前我在某本书上看到过,当时激动了半天,没想到一个指针就可以搞定删除

  10. 这个不就是增加一个dummy node(伪节点)来访问修改单链表么?
    无数无数的数据结构教材都讲过,例如严老师那本。

  11. 最近感觉这个细节固然重要
    但是面对越来越复杂的系统
    编译器能隐藏的细节越多越好
    而不是每次都按照特定要求在特定环境优化特定算法

  12. iambic :
    一般这种链表问题,好像加一个dummy head比较好吧,比如
    1234567891011121314151617181920212223242526272829struct Node{    int val;    Node* next;    Node(int v){ val = v; next = NULL; }}; typedef bool (* remove_fn)(int val) ;Node* remove_if(Node* head, remove_fn f){    Node *r=new Node(0);    Node *p=r;    while(head)    {           if(!f(head->val)){            p->next = head;            p=p->next;            head = head->next;            p->next=NULL;        }else{            Node* t=head;             head=head->next;            delete t;        }       }       p=r;    r=r->next;    delete p;//remove dummy head    return r;}

    dumy节点也是一个方法,但没有二级指针干净,原因是多了一个malloc,调用100W次效果你懂的。

  13. Linux这回搞错了,根本不需要这样。给链表戴个头结点,两指针一前一后跑一次就行了。 最后也能返回头结点。Linus没有把方法说清,不评价了。中文方法里,虽然可行,但head返回不了,只能直接带出。

  14. @viho_he
    并不是这样子的,next指针放在结构体的任意地方都可以。
    关键是第12行:curr = &entry->next;
    这里,已经让curr这个二级指针直接指向了next指针的地址。
    循环回来到第8行:*curr = entry->next;
    这时候对curr二级指针的内容进行操作时,已经影响(改变)到了前面结点的next指针所在内存的内容。也就是改变了next域的内容,使其值为正确的下一个结点。

  15. viho_he :
    Linus的这个用法,是利用了链表的一个特性:当这样来定义struct,
    typedef struct node
    {
    struct node * next;
    ….
    }
    即指针next是在struct的最前面时,next指针的存放地址,就等于是这个node本身的存放地址,即
    node == &node->next
    因此那一句
    curr = &entry->next;
    也可以写成
    curr = (node**)entry;
    这个特性,也成了利用二级指针的关键。
    如果链表是这样定义的,linus的做法就行不通了。然而在kernel代码里没人会这样定义链表:
    typedef struct node
    {
    ….
    struct node * next;
    }

    并不是这样子的,next指针放在结构体的任意地方都可以。
    关键是第12行:curr = &entry->next;
    这里,已经让curr这个二级指针直接指向了next指针的地址。
    循环回来到第8行:*curr = entry->next;
    这时候对curr二级指针的内容进行操作时,已经影响(改变)到了前面结点的next指针所在内存的内容。也就是改变了next域的内容,使其值为正确的下一个结点。

  16. 我感觉这两段代码似乎都存在问题,第一段使用if/else的代码,其函数声明方式为:
    node * remove_if(node * head, remove_fn rm)
    这里形参head显然是值传递进来的,调用者传入的实参是无论如何不会改变的,所以这个函数在头需要改变时不会起作用。
    第二种实现中缺乏对空指针的判断,如果传入的是空链表,则*head==NULL,entry==NULL,第8行的
    *curr = entry->next; 将直接崩溃。

    1. 你的理解有误,linux的写法没问题。我猜你以为传入空链表的时候curr==NULL,但实际上传空链表时 *curr==NULL,这样for循环就不会执行,因此没有任何问题。
      linus的写法主要有两个方面不好推广,一是理解起来比较难,正如他所说的,只有对指针非常熟悉的人才可以熟练驾驭这种写法,普通人能理解就已经不容易了;二是效率不一定比普通写法高,因为现代CPU的分支预测做得好,而linus的写法访问指针过多,在处理比较长的链表时会慢一些。
      我认为更好的方法是给链表一个dummy_head,然后prev=&dummy_head, curr=prev->next;这样就不用额外判断真正的第一个节点是不是空啦。

  17. 粗略地看了一下,貌似这两种方式只是删除策略不一样导致的问题而已。
    不用prev策略的话,根本无须使用二级指针也能实现,其实也就是完全不需要用prev语义的一种删除策略而已
    void remove_if(node * head, remove_fn rm)
    {
    for (node* savedpos = head; savedpos; )
    {
    node * entry = savedpos;
    if (rm(entry))
    {
    savedpos->next = entry->next;
    free(entry);
    }
    else
    savedpos = entry;
    }
    }

    简单来说就是需要两个变量保存遍历的位置
    这段代码我未有时间跑一下验证,但是从策略来说好像是正确的
    看明天我有时间的话跑一下这代码

  18. 按照上面说的删除策略,代码应该是这样才对
    void remove_if(node * head, remove_fn rm)
    {
    node *savedpos = head;
    node *curr = savedpos;
    while (curr)
    {
    if (rm(curr))
    {
    /* 删除成功 */
    node *n = curr;
    savedpos->next = curr->next;
    curr = curr->next;
    free(n);
    }
    else
    {
    savedpos = curr;
    curr = curr->next;
    }
    }
    }

    真不知道上面二级指针的那段代码到底是不是对的……,没空去把代码跑起来

  19. 我觉得你的图没有问题,但是你把事实弄复杂了.重点并不在于使用了一个”指向指针的指针”,而是直接在prev时判断prev的next也就是current的删除状况,由此来节约一个指针

  20. 超然 :

    viho_he :
    Linus的这个用法,是利用了链表的一个特性:当这样来定义struct,
    typedef struct node
    {
    struct node * next;
    ….
    }
    即指针next是在struct的最前面时,next指针的存放地址,就等于是这个node本身的存放地址,即
    node == &node->next
    因此那一句
    curr = &entry->next;
    也可以写成
    curr = (node**)entry;
    这个特性,也成了利用二级指针的关键。
    如果链表是这样定义的,linus的做法就行不通了。然而在kernel代码里没人会这样定义链表:
    typedef struct node
    {
    ….
    struct node * next;
    }

    并不是这样子的,next指针放在结构体的任意地方都可以。
    关键是第12行:curr = &entry->next;
    这里,已经让curr这个二级指针直接指向了next指针的地址。
    循环回来到第8行:*curr = entry->next;
    这时候对curr二级指针的内容进行操作时,已经影响(改变)到了前面结点的next指针所在内存的内容。也就是改变了next域的内容,使其值为正确的下一个结点。

    你纠正的对。代码写成
    *curr = &entry->next时,不管next放在node里面的哪个地方,编译器都会正确找出来。

    只有代码写成这种比较hack的方法,next才必须是放在node头部(即&next == &node),但不具有读性,也有移植性的问题:
    *curr = (node **)entry

    在这种写法中,
    *curr = (node **)entry 之所以与 *curr = &entry->next等效,是因为
    entry->next == *entry,因此&entry->next == entry。但前题是next指针的存放地址必须是node本身的地址。
    @TOBY

  21. 终于弄清楚了这个问题的本质,其实上面的描述有很多误导的地方,而且图也没把问题说清楚。
    图只是说明了一种删除策略而已,没有对二级指针的作用表达清楚
    这时一种不用二级指针的替代代码,策略是一模一样的,本质就是一个虚拟头的next
    void remove_if(node * head, remove_fn rm)
    {
    node dummy;
    dummy.next = head;
    node *savedpos = &dummy;

    while (savedpos->next)
    {
    node *entry = savedpos->next;
    if (rm(entry))
    {
    savedpos->next = entry->next;
    free(entry);
    }
    else
    {
    savedpos = savedpos->next;
    }
    }
    }

    本质上,linus方案利用了一个特性,链表头可用一个二级指针存储,作为虚拟头节点中的next字段,从而节省了自己生成虚拟头的功夫,但是这样会多了解引用操作。
    其实linus方案也就是是存储prev->next字段实现删除而已,但这个方案有个缺点,如果需要返回新的头的话,需要额外的工作。也就是如果要返回新的头节点的话,linus方案的代码不比prev方案的代码少多少。
    说起来,linus方案其实是挺没意思的,本来一个很简单的事情,搞得这么复杂。
    本来每种策略就是牺牲了某方便来实现其他方面的,不存在不牺牲任何资源就实现某目标的方法。

  22. @小新
    你两个都说错了
    1,头指针指向的值可以改变就行了,头指针本身不需要改变
    2,如果*head==null 根本就进不去for循环

  23. 精彩。如果还有不懂的同学我在这里总结一下,prev指针的next的值就是next的地址,用一个二级指针**curr的话,*curr就是当前节点, curr同时还是prev->next的地址。

  24. 从内存与地址的角度来看,就一目了然。
    一个变量代表一个存储,这个存储本身有一个地址;而指针也是一个变量,也代表了一个存储,这个存储中的值是另一个存储的地址。

  25. 看了半天才看懂,太菜了。我觉得这个和增加一个头节点的原理是类似的,只不过这个方法操纵的对象变成了指针。不知道对不对…

  26. @card323
    不好意思,第二个确实没仔细看for的条件,空不回进入;但是第一个函数我认为还是有问题的,链表为空时是要改变head本身的值为NULL的,这是head指针本身的值,不是head指向的值。

  27. 小新 :@card323 不好意思,第二个确实没仔细看for的条件,空不回进入;但是第一个函数我认为还是有问题的,链表为空时是要改变head本身的值为NULL的,这是head指针本身的值,不是head指向的值。

    用法不一样。
    第一个函数在函数外部由调用者去用返回值替换head本身的值;
    第二个函数在函数内部直接修改了head本身的值。

  28. 传值和传引用的区别嘛,没什么亮点,还以为是自己忽略了什么技巧,想多了

  29. LZ,无锁文件名查询,应该是内核中文件系统中路径名查询中的代码吧…

  30. 我想说,这玩意儿也算是个花活吧? 大神不是以花活太多为理由抵制c++吗

  31. 这还是一个思考方式的差异吧:
    第一种方法,考察某节点时候,判断该节点是否可删除
    第二种方法,考察A节点时候,判断该节点的下一节点是否可删除

  32. 呵呵,测了一下,发现二级指针竟然没有加一个if来得快,Linus这回也不完全正确。
    因为二级指针导致间接寻址,所以并没有快

  33. 恍然大悟——指针即变量的地址,改变变量的值时候不妨想想通过指针来实现,包括指针变量。

  34. “这并不像无锁文件名查询(注:可能是git源码里的设计)那样庞大、复杂”

    这里是指内核文件系统里面的文件名查询

  35. 这个方法是FreeBSD里基于宏的list实现所用的方法。而linux里的list.h目前是增加dummy头的方法,其通用实现已经被归档到ccan.org里。两种方法各有擅场,从长远角度看,个人倾向后者,代码本身更加容易扩充。

  36. 更正回复中的一个错误,ccan项目域名不是ccan.org,应该是http://ccodearchive.net/,其维护者就是linux里list.h实现的作者。

  37. scaret :
    我觉得你的图没有问题,但是你把事实弄复杂了.重点并不在于使用了一个”指向指针的指针”,而是直接在prev时判断prev的next也就是current的删除状况,由此来节约一个指针

    scaret :
    我觉得你的图没有问题,但是你把事实弄复杂了.重点并不在于使用了一个”指向指针的指针”,而是直接在prev时判断prev的next也就是current的删除状况,由此来节约一个指针

    同意

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注