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

211–220 of 339 posts

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

#211

Post by kbumsik »

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…

You don't need to check !!indirect. There is no cases that the indirect pointer is NULL:

  while (!!(*indirect) && (*indirect) != entry)
    indirect = &(*indirect)->next;
Also I would rather use * indirect instead of !!(* indirect).

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

#212

Post by cmroanirgo »

shallowthought wrote: post #209
mjevans wrote: post #195

Earlier quoted context omitted.

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 t…

That's a pretty big freakin thing to leave out, though. Code that depends on its context is, some would say, bad.

This is why Linus' code shouldn't be copied verbatim and used in the real world. The Kernel is an extremely isolated and contained system.

At the very least, the code should add comments on the the assumptions that are vital...otherwise n00bs will copy the code as gospel and run into all sorts of problems.

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

#213

Post by axaxs »

shallowthought wrote: post #209
mjevans wrote: post #195

Earlier quoted context omitted.

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 t…

That's a pretty big freakin thing to leave out, though. Code that depends on its context is, some would say, bad.

Simply put, safety slows code down. It's a matter of whether you know what's happening underneath or not. The more you try to make C completely safe, the more you slow it down and therefore remove the need to have written it in C in the first place. Whether that's a good thing or not is an exercise for the implementer.

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

#214

Post by cmroanirgo »

kbumsik wrote: post #211
cmroanirgo wrote: post #191

Earlier quoted context omitted.

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…

You don't need to check !!indirect. There is no cases that the indirect pointer is NULL: while (!!(*indirect) && (*indirect) != entry) indirect = &(*indirect)->next; Also I would rather use * indirect instead of !!( * indirect).

correct. I was just being overly pedantic

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

#215

Post by muro »

cmroanirgo wrote: post #214
kbumsik wrote: post #211

Earlier quoted context omitted.

You don't need to check !!indirect. There is no cases that the indirect pointer is NULL: while (!!(*indirect) && (*indirect) != entry) indirect = &(*indirect)->next; Also I would rather use * indirect instead of !!( * indirect).

correct. I was just being overly pedantic

Why the !! ? I thought that only makes sense in JS.

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

#216

Post by yarcob »

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…

That code is not a general purpose library function; it assumes the element exists.

If you call that method and the element doesn't exist, presumably something has gone wrong already. Adding a NULL pointer check is not going to fix it. You just silently ignore the error. You'll prevent the crash, but there's no mechanism for handling the error.

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

#218

Post by cmroanirgo »

muro wrote: post #215
cmroanirgo wrote: post #214

Earlier quoted context omitted.

correct. I was just being overly pedantic

Why the !! ? I thought that only makes sense in JS.

I'm not sure about the current state of compiler optimisations, but IIRC in the olde-days, a not not in an if() statement would assemble to JZ, saving a clock cycle (& an opcode?), and wouldn't need to stall to load in the full width of the register. Today's branch predicting compilers are beyond me.

I still use it as a clarification that it's a deliberate boolean operation, rather than implicit.

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

#219

Post by nitrogen »

muro wrote: post #215
cmroanirgo wrote: post #214

Earlier quoted context omitted.

correct. I was just being overly pedantic

Why the !! ? I thought that only makes sense in JS.

I thought that only makes sense in JS.

In C any nonzero value is considered "truthy", and on most architectures NULL is defined to be (void * )(0) or similar. The logical not operator AKA bang operator will replace truthiness with 0, and falsiness with 1. So applying it twice collapses all nonzero values to 1.

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

#220

Post by scns »

identity0 wrote: post #149
eperdew wrote: post #122

Earlier quoted context omitted.

All pointers are pointers too, so I don't see much of a difference between "indirect" and "next_ptr", other than the "next" part. In similar situations at my job, I've drawn a small ASCII diagram in the comments, and named the variable something like "splice_point", with a corresponding label in the diagram.

Well "next_ptr" is also a bad name, I agree, but I'm trying to name it something that indicates "this is a pointer to the 'next' pointer in the linked list".

How about next_node?
Post reply on HN