linus教你写链表

秒速五厘米 2022-08-05 16:22 197阅读 0赞

## [Two star programming][] ##

2013-01-08 • [C][], [Torvalds][], [Algorithms][] • [46 Comments][]

A few weeks ago [Linus Torvalds answered some 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.

> 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
> 
>     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`.

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

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][]!

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.

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

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][] would be one too many.

[Two star programming]: http://wordaligned.org/articles/two-star-programming
[C]: http://wordaligned.org/tag/c
[Torvalds]: http://wordaligned.org/tag/torvalds
[Algorithms]: http://wordaligned.org/tag/algorithms
[46 Comments]: http://wordaligned.org/articles/two-star-programming#disqus_thread
[Linus Torvalds answered some questions]: http://meta.slashdot.org/story/12/10/11/0030249/linus-torvalds-answers-your-questions
[interview questions]: https://www.google.com/search?q=linked+list+interview+questions
[third star]: http://c2.com/cgi/wiki?ThreeStarProgrammer