Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Linus Torvalds' good taste argument for linked lists, explained

github.com

Post reply on HN
Print view View original

191–200 of 339 posts

Re: Linus Torvalds' good taste argument for linked lists, explained

#191

Post by cmroanirgo »

nemetroid wrote: post #19

I'm not sure why the article removed comments from the code and replaced variable names like "indirect" with "p". Here are the two code samples verbatim from Linus's presentation: remove_list_entry(entry) { prev = NULL; walk = head; // Walk the list while (walk != entry) { prev = walk; walk = walk->next; } // Remove the entry by updating the // head or the previous entry if (!prev) head = entry->next; else prev->next…

I can't help but notice how this code, as well as in the article, there's no checks for a) a NULL list or b) that the item is in fact part of the list. A simple fix is:

  while (!!walk && walk != entry) {
     prev = walk;
     walk = walk->next;
  }
or

  while (!!indirect && !!(*indirect) && (*indirect) != entry)
          indirect = &(*indirect)->next;
...because without those checks it's pretty easy to see where you'll crash... but by putting in those checks, perhaps the second method might actually be less 'elegant'.

Edit: did I miss something? Re-checking this, the second method will still crash if/when next is NULL (because you can't get the address of NULL), which means the 'elegant' seems to be a quagmire of lurking faults.

Re: Linus Torvalds' good taste argument for linked lists, explained

#192

Post by cmroanirgo »

ndand wrote: post #184
Thorrez wrote: post #180

Earlier quoted context omitted.

This comment seems wrong to me: // The "indirect" pointer points to the // *address* of the thing we'll update The "indirect" pointer points to the thing we'll update. See at the bottom, it's updating *indirect, so "indirect" points to the thing being updated. On the other hand, "indirect" points to the address of the thing we'll remove. There's a specific item being removed, and there's a specific thing that will be…

The comment is correct. The "thing" is the variable that holds the "entry". The entry is removed by updating the "thing".

Agreed. The 'indirect pointer' points to the memory address of the previous 'next' (or the head). So, as long as neither are NULL, then dereferencing the pointer is the actual head (or the previous 'next').

Re: Linus Torvalds' good taste argument for linked lists, explained

#193

Post by pacaro »

emerged wrote: post #163
hyperpape wrote: post #105

Earlier quoted context omitted.

Question for experienced C programmers (I'm not one). The comments for remove_list_entry strike me as fluff, only suitable for a didactic piece. Would you find the comments in the second version helpful, or should they also be removed? Edit: let me lay my cards on the table. If the comments really are necessary, it doesn’t seem elegant. I’m pro-comments, but that’s because not all code can be readable and elegant all…

For my tastes there is way too much whitespace and I usually only use multi-line comments to describe the high level algorithm for a full function. I prefer to pepper single-line comments which describe the sequence of events in a human-readable way. I've been C/C++ for about 25 years.

My taste is that function level comments describe the "what" and inline comments describe the "why".

So at a function level the comments is giving a highlevel description to the reader as to the functionality contained, and at the line level comments exist only to say describe the programmers intentionality, why it was implemented this way rather than some other way.

I have generally found (there are always exceptions) that if you find yourself needing "what" comments within a function you should be considering breaking it into smaller pieces.

I've been being paid to write c/c++ for about 25 years

Re: Linus Torvalds' good taste argument for linked lists, explained

#194

Post by Hammershaft »

nemetroid wrote: post #19

I'm not sure why the article removed comments from the code and replaced variable names like "indirect" with "p". Here are the two code samples verbatim from Linus's presentation: remove_list_entry(entry) { prev = NULL; walk = head; // Walk the list while (walk != entry) { prev = walk; walk = walk->next; } // Remove the entry by updating the // head or the previous entry if (!prev) head = entry->next; else prev->next…

Hacker news would benefit from code blocks.

Re: Linus Torvalds' good taste argument for linked lists, explained

#195

Post by mjevans »

cmroanirgo wrote: post #191
nemetroid wrote: post #19

I'm not sure why the article removed comments from the code and replaced variable names like "indirect" with "p". Here are the two code samples verbatim from Linus's presentation: remove_list_entry(entry) { prev = NULL; walk = head; // Walk the list while (walk != entry) { prev = walk; walk = walk->next; } // Remove the entry by updating the // head or the previous entry if (!prev) head = entry->next; else prev->next…

I can't help but notice how this code, as well as in the article, there's no checks for a) a NULL list or b) that the item is in fact part of the list. A simple fix is: while (!!walk && walk != entry) { prev = walk; walk = walk->next; } or while (!!indirect && !!(*indirect) && (*indirect) != entry) indirect = &(*indirect)->next; ...because without those checks it's pretty easy to see where you'll crash... but by putt…

I believe the implicit requirement is that the item is known to exist within the list. With that requirement in place the extra guards aren't requisite (they're implicit) and in kernel code this probably offers a performance edge and is a reasonable requirement. Either having an implementation that has an extra check once at the end of the list, or that verifies the presence of the item and passes that node through to a deletion subroutine, would be good alternatives but still utilize the same pointer to structure view.

Re: Linus Torvalds' good taste argument for linked lists, explained

#197

Post by munchbunny »

hyperpape wrote: post #105
nemetroid wrote: post #19

I'm not sure why the article removed comments from the code and replaced variable names like "indirect" with "p". Here are the two code samples verbatim from Linus's presentation: remove_list_entry(entry) { prev = NULL; walk = head; // Walk the list while (walk != entry) { prev = walk; walk = walk->next; } // Remove the entry by updating the // head or the previous entry if (!prev) head = entry->next; else prev->next…

Question for experienced C programmers (I'm not one). The comments for remove_list_entry strike me as fluff, only suitable for a didactic piece. Would you find the comments in the second version helpful, or should they also be removed? Edit: let me lay my cards on the table. If the comments really are necessary, it doesn’t seem elegant. I’m pro-comments, but that’s because not all code can be readable and elegant all…

I would expect to see barely any comments in the "in production" version, other than a comment like:

    // indirect is either &head or &(node->next), so *indirect is equivalent to "next node"
Someone who knows their C should be able to figure it out in a few minutes by just reading the code.

Re: Linus Torvalds' good taste argument for linked lists, explained

#198

Post by penteract »

nemetroid wrote: post #19

I'm not sure why the article removed comments from the code and replaced variable names like "indirect" with "p". Here are the two code samples verbatim from Linus's presentation: remove_list_entry(entry) { prev = NULL; walk = head; // Walk the list while (walk != entry) { prev = walk; walk = walk->next; } // Remove the entry by updating the // head or the previous entry if (!prev) head = entry->next; else prev->next…

The article refers to p about 30 times, including in a diagram, so I can understand why they'd pick a shorter name.

Re: Linus Torvalds' good taste argument for linked lists, explained

#199

Post by Mikhail_Edoshin »

Solutions that feature extra levels of pointing naturally arise in many cases. E.g. you search some data structure for an element. Initially you may do this so that the search returns the element itself or NULL if it's not found, but then you realize you'll also need to use the same searching logic to insert and delete elements. In this light you rewrite the search to return a pointer to the location instead; this way you can use it as a subroutine for all the operations.

Re: Linus Torvalds' good taste argument for linked lists, explained

#200

Post by jdxcode »

aksjfnkajsnd wrote: post #186
greenkey wrote: post #148

Earlier quoted context omitted.

I’m not a fan of everything Bukowski wrote, but I wouldn’t try to censor him so that little Jimmy could read it, and I liked the movie Barfly. Similarly, I’m not a fan of everything Linus wrote, but I wouldn’t enforce bad CS101 code on him so that little Jimmy could read it, and I like Linux.

Who is little Jimmy?

It refers to an old American comicstrip with a little kid that didn’t know much. (I think anyways)

It just sort of means any below-average person.

Post reply on HN