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

101–110 of 339 posts

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

#101

Post by kevin_thibedeau »

m4lvin wrote: post #22

The second version seems more elegant but will scare non-C people away with all those pointers ;-) What I do not understand is why one should use an "IntList" struct in the first place? As the explanation of the second method suggests, a List is the same thing as a pointer to its first element, so why not do this?: typedef struct IntListItem* IntList; Also, could it be that both methods fail terribly (infinite loops?…

Typedefing pointers was done so Pascal programmers didn't have to be scared by C syntax. This is why Microsoft went overboard with this practice. It unfortunately hides the language for no real benefit.

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

#102

Post by orf »

alisonkisk wrote: post #81
zem wrote: post #49

Earlier quoted context omitted.

i think a lot of the reason it looks more "clever" than elegant is because c's syntax makes the "get the address of this field in a struct" operation so hard to read at a glance.

It's a lot easier to "get the address of this field in a struct" in C than in Java or Python or JavaScript.

Not really, but the real question is why would you need or want to in those languages?

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

#104

Post by GuB-42 »

bigyikes wrote: post #71
eloff wrote: post #26

Earlier quoted context omitted.

Looking at the code there are not just fewer lines, but fewer conditionals too. It's much simpler to read and understand. I got it at a glance, whereas I skimmed the typical approach and would still need to go over it more carefully to be sure it is correct. I think Linus is correct on this one.

Linus’ solution seems to add a layer of indirection, which I think is harder to grok than a simple condition.

There is no extra layer of indirection.

The idea here is to make the "p" pointer point on the "next" field of the current element instead of at the structure itself. There is the same amount of indirection in both solutions.

The first solution does pointer->structure->pointer, the "elegant" solution does pointer->pointer->structure. The reason the first one may be easier to read is because the C syntax "prefers" it, as it is a more common construct.

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

#105

Post by hyperpape »

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 the time.

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

#106

Post by furyofantares »

These functions can be thought of as two steps:

1. Find the thing to update

2. Update it

Linus's version does just that.

But the first version is more complex because step 1 instead emits something that may or may not be the thing to update, and so step 2 has to reason about that. Additionally, it introduces a bookkeeping variable -- cur -- which becomes redundant before step 2 (by which point it's equal to target).

IMO Linus is right here. The form of his solution directly matches the problem and allows you to look at the code as two clean steps -- no reasoning about the output of the first step and no bookkeeping cruft variable that you have to ignore or remind yourself that it's the same as another variable after some point in the function. At least once you're used to working with double pointers I think that's a much easier function to read.

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

#107

Post by temac »

seanwilson wrote: post #32

I used to ask during interviews to just describe what a linked list was and less than half the candidates for mid/senior positions could. I think it's a really revealing question. Same with hash tables.

Switch to B-Trees if you ever need to reject all candidates :P (And astonishingly, a comprehensive description of them including the tools for complexity analysis in a form practical for real-world implementers - not just CS student writing toy exercise projects - is very hard to find.)

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

#108

Post by metters »

m_mueller wrote: post #24
andy_ppp wrote: post #23

Earlier quoted context omitted.

I totally agree, it’s about proving you’re clever rather than communicating ideas. Maybe for something hard like Linux kernel development this is a good thing but in most cases it just leads to messy code that people can’t understand or follow.

While there certainly are such cases, I think here it’s just about being proficient in a language. Pointers, referencing and dereferencing are the bread and butter of any C code, and applying them in a way to reduce complexity is certainly something to strive for - if this isn’t readable then I’d argue the reader shouldn’t be touching the codebase anyways.

You are right, for a c programmer this is bread and butter. The readability of the example would increase a lot with better named variables, however.

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

#109

Post by 762236 »

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…

What if entry doesn't exist in the list? You need a special case to handle that too.

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

#110

Post by rightbyte »

Arnavion wrote: post #80
jamesdsadler wrote: post #75

Earlier quoted context omitted.

Both of these implementations seem to be missing a call to `free`, or is that something that the caller should be taking care of?

It's pseudocode. The code as-is is not valid C anyway.

Now you are assuming "remove_list_entry" is not a macro!
Post reply on HN