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

251–260 of 339 posts

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

#251

Post by JulianMorrison »

yarcob wrote: post #216
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…

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.

Then it ought to document that it assumes that entry exists and that this walk will not hit the end of the list. Which also implies the list is not empty.

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

#252

Post by veddox »

munificent wrote: post #135
macspoofing wrote: post #7

I understand the general point (and value) of reframing the problem or the solution in a way that removes special cases ... but in this case I would actually prefer the first solution over the second. The second solutions reminds me of the old-school perl culture, and JavaScript culture, where 'cleverness' (which always manifests itself as terseness as if lines of code were expensive), takes precedence over maintaina…

One way to define "clever" is something you can do but that relies on something you don't expect most readers to have already loaded into their head. Like a riddle, it makes sense if you know the trick it relies on but is baffling if you don't. The difference between "clever" and "smart" then is based in large part on what you expect your readers to already know. Different people have different expectations there and…

Yes, I think that's the key.

I'm not a C programmer, and though I do have a basic understanding of pointers, I still find them rather confusing because of the indirection they introduce. I could follow the first example just fine (because I know how to deal with linked lists from Lisp), but the second gave me rather a headache (two levels of indirection!).

However, I think that once you've really understood the concept of pointers - and I'd expect that from all kernel developers - the second example really wouldn't be any harder to understand than the first. And yes, then it is the cleaner way of doing things, and therefore to be preferred.

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

#253

Post by majewsky »

rocqua wrote: post #248
Hammershaft wrote: post #194

Earlier quoted context omitted.

Hacker news would benefit from code blocks.

Hacker news has code blocks. Have the block indented by for spaces. this line has 4 spaces in front of it. What Hacker news could use instead are quote blocks. Now people often use the code blocks as quote blocks.

HN codeblocks are just two spaces indented. Any extra spaces indent further.

  This has no superfluous indentations.

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

#255

Post by user-the-name »

cmroanirgo wrote: post #218
muro wrote: post #215

Earlier quoted context omitted.

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.

I highly doubt that any modern compiler would generate different code with or without the !!. Not even sure why an old compiler would do that? It's the exact same semantics, surely.

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

#256

Post by user-the-name »

nitrogen wrote: post #219
muro wrote: post #215

Earlier quoted context omitted.

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.

Well, yes, but that does absolutely nothing in this code, as it is immediately used as the argument to an if statement.

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

#257

Post by eps »

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

That had nothing to do with pedantry.

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

#258

Post by buserror »

I used to use linux's list.h quite a bit, that is the "good taste" implementation, where the head is the same as the elements. My only problem with that implementation is the fact it is non-typed. Heads are generic, and the code using them has to use container_of() macros to recover the containing type.

I've since discovered bsd/queue.h [0], which is very similar in purpose, but is not "good taste" (which I don't mind at all) on the other hand it is type safe, has quite a few variants for single and double lists, and oh also, it's not GPL.

[0]: https://github.com/freebsd/freebsd/blob/master/sys/sys/queue...

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

#259

Post by red_admiral »

The "avoid special cases" argument comes up a lot in math too. For example in combinatorics, some people define 0^0 = 1, so that lots of formulas with "if x == 0 then this else that" just collapse into "that". (Other people insist on inventing a different symbol for this "special exponentiation", but I think that's unnecessary myself.)

For the same reason, an empty sum is defined as 0 and an empty product as 1, so your base cases of some inductions don't require an extra "if".

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

#260

Post by BoorishBears »

adrianN wrote: post #235
larsrc wrote: post #229

Earlier quoted context omitted.

Are you arguing that we should leave known crash bugs in the code?

I'm arguing that we should use asserts or similar defensive coding mechanisms to ensure that preconditions are met instead of merrily continuing to run our program with cascading error effects.

I've had this argument a ton with people used to new high level languages that make null safety "too easy" like:

  next?.doThing()
Where doThing is never called if next is null.

Languages that do this use "scary" operators to crash on null:

  next!!.doThing()
And it's drilled into people's heads the latter is a Bad Thing (tm)

-

You really need to consider context in null handling.

Imagine an app that alerts a nurse when the patients heartbeat is out of range.

In an application where the UI context might have been closed out, it's common to see

  someUiContext?.showAlert()
But what actually happens if the context is gone?

It's better to crash and have part of your startup procedure be communicating that a crash occurred, and the doctor should check that something went wrong, than silently continuing.

-

The problem is when you tell people this, the kneejerk reaction is always "are you saying we intentionally add crashes"!

Because safe null handling was specifically added to avoid the situation where that crashes...

(For example, if the app was a news reader and the alert was "Article failed to load", you wouldn't want the app to crash just because the user left a certain page before the alert was shown)

But I think the pendulum has swung too far at this point, people are so used to just sweeping nulls under the rug, and it's not great for finding issues

Post reply on HN