13 ms·
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 Li
by nemetroid 6y ago
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 = entry->next;
}
remove_list_entry(entry)
{
// The "indirect" pointer points to the
// *address* of the thing we'll update
indirect = &head;
// Walk the list, looking for the thing that
// points to the entry we want to remove
while ((*indirect) != entry)
indirect = &(*indirect)->next;
// .. and just remove it
*indirect = entry->next;
}
- brainwipe 6y agoThank you, I found that much easier to read than the article posted.
- m463 6y agoMuch clearer when read as Linus intended. Reminds me of the editor(s) who helped "fix" bukowski's poems
- greenkey 6y agoI’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.
- aksjfnkajsnd 6y agoWho is little Jimmy?
- deleted 6y ago[deleted]
- jdxcode 6y agoIt 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.
- aidenn0 6y agoJimmy is a diminutive form of James. It's the sort of thing where parents would call a kid "jimmy" and when they grow up they will ask people to call them "Jim" or "James." Adding "little" in front just stresses the fact that we are talking about a kid, so the references are about dumbing it down for kids. Johnny is probably a bit more common than Jimmy, but I've seen both. See e.g. [1] 1: https://en.wikipedia.org/wiki/Why_Johnny_Can%27t_Read https://en.wikipedia.org/wiki/Why_Johnny_Can%27t_Read
- sundarurfriend 6y agoThe poster-child for the movie "Think of the Children!"
- kleiba 6y agoA 1992 poem Bukowski originally entitled “stone tiger, frozen sea,” was completely reworked with just two lines left unchanged. Its new title: “like a dolphin.” https://www.pbs.org/newshour/arts/poetry/bukowksis-poems-were-mangled-by-editors-after-his-death-now-you-can-read-his-originals https://www.pbs.org/newshour/arts/poetry/bukowksis-poems-wer...
- cambalache 6y agoIt's a small class in good coding 101. Concise, well commented/documented, good variables names vs verbose in explanation , terse in code.
- deleted 6y ago[deleted]
- forrestthewoods 6y agoPerfect. I almost commented to complain that the “elegant” version is harder to read and understand. This is much much better. Comments are important!
- helloycombinat 6y agoI don't think it's the comment. Usually variable names in a loop is the object being manipulated not the address of that pointer which means p isn't a pointer to the object which makes it completely confusing. If the article used pp which is the typical way you describe a pointer to pointer it'd help
- alisonkisk 6y agoThe author also misunderstands what "head" of a list is, adding more bad clutter to the code. (Granted, the code in the original TED talk is broken, as it doesn't define "head".) A linked list in C isn't a struct with a "head"; "head" is just a pointer pointing to the head element. The OP article should be retracted.
- rossitblt 6y agoHow likely it is for code to be misunderstood depends on the code readability as well, not just on the person who gets it wrong. Personally, I find the style of Linux lists unintuitive. To me it seems a case of sacrificing code readability to workaround limitations of the C language.
- djeiasbsbo 6y agoI don't see what you're saying.. the OP added that bit (the IntList struct) himself but it doesn't really change the scenario or take away from what he is trying to explain. But it should be retracted? Really?
- jamesdsadler 6y agoBoth of these implementations seem to be missing a call to `free`, or is that something that the caller should be taking care of?
- Arnavion 6y agoIt's pseudocode. The code as-is is not valid C anyway.
- rightbyte 6y agoNow you are assuming "remove_list_entry" is not a macro!
- jagged-chisel 6y agoDepends on whether the list owns the nodes. I tend to write mine such that it does. Perhaps this code is demonstrative rather than complete.
- arka2147483647 6y agoThe caller could want to move the element from one list to another, in which case the optimum impl would not free or copy the element.
- eperdew 6y agoAs others have said, often you don't want to free the node, you want to do something else with it. E.g., put it in a free list. However, usually if you're not freeing it, you'd null out the next field so that you don't accidentally access it when it's not part of the list (at least I would).
- scoutt 6y agoWhy do you think the values were allocated in the heap?
- hyperpape 6y agoQuestion 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.
- identity0 6y agoThe top pattern is extremely common so comments are somewhat unnecessary since everyone would know what you're doing. In the second one, comments would be less necessary with a type annotation and perhaps a better name. Maybe "next_ptr" instead of "indirect"---all pointers are indirection, so that name is redundant. But the comments are necessary, to me at least.
- eperdew 6y agoAll 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.
- valtism 6y agoThe comments certainly don't detract from the code in my opinion. They may not be _helpful_ per se to an experienced developer, but there may be a chance that a more inexperienced developer will read this code in the future, and it could benefit them.
- 762236 6y agoWhat if entry doesn't exist in the list? You need a special case to handle that too.
- asdfasgasdgasdg 6y agoNormally with an identity-based API like this, you can put it as a requirement that you must not remove items other than those which actually exist in the collection. Another example of an API that doesn't check for presence: c++ iterator-based removal. If you ask a C++ list to remove an iterator element outside its range, it may crash the program. See the exception safety section of this documentation: http://www.cplusplus.com/reference/list/list/erase/ http://www.cplusplus.com/reference/list/list/erase/ If you look at most "remove this object from yourself" APIs in low-level code, it behaves this way, because it's unnecessarily complex to check for presence when that is a fact the program can condition on instead.
- Retric 6y agoUnnecessary is not really the correct term, it’s one of a huge number of tradeoffs. The you don’t want it for safety critical systems, but Linux isn’t designed to be used for such things.
- mehrdadn 6y agoAs the other person said, it's not really about complexity. Complexity isn't all that different here; personally I'd find something like the following to be simpler (I imagine others might disagree): remove_list_entry(entry) { for (p = &head; *p; p = &(*p)->next) { if (*p == entry) { *p = entry->next; break; } } } However, what the choice does objectively impact is performance. Being able to assume the object exists allows you to avoid checking against NULL, which removes instructions in the loop. I'd guess they anticipate this code might be called from performance-critical code, and that might be why they coded it like this.
- azernik 6y agoNot just an instruction, but a branching instruction. Branch predictors will probably do pretty well on this, but still.
- javajosh 6y agoWhat happens at the end of the list? Is next null? And if so, how do either of these methods behave?
- Jasper_ 6y agoThis is a circular linked list, where the ->next pointer points back to the head of the list. It's helpful for iteration tasks, since you can always walk the full list when you get access to one node. In most cases you use a linked list like this, you don't care about the order of things, just that you can iterate over all items in the list.
- r-w 6y agoNo, it's not, as can be seen from the diagrams in the article.
- BalinKing 6y agoI'm kinda confused on how this will behave if we want to remove `head`—if `head` is in the stack frame (assuming it's a parameter to `remove_list_entry`), wouldn't `*(&head) = entry->next;` be a no-op as far as the caller is concerned? (Sorry for the n00b question.)
- kbumsik 6y agoThen you will escape from while((* indirect) != entry) check in the first place and ignore * (&head) = entry->next;.
- foota 6y agoNo, this copies the value from next into the memory occupied by head. For example if the linked list was: &next: (100, 0xFFFF) 0xFFFF: (101, 0xDEFF) 0XDEFF: (102, 0) Then calling remove on head would leave us with: &next: (101, 0xDEFF) 0xFFFF: (101, 0xDEFF) 0XDEFF: (102, 0) (It would be on the caller to free the memory address 0XFFFF)
- Thorrez 6y agoThis 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 updated; the thing being updated comes immediately before the thing being removed; they're not the same thing.
- ndand 6y agoThe comment is correct. The "thing" is the variable that holds the "entry". The entry is removed by updating the "thing".
- cmroanirgo 6y agoAgreed. 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').
- Thorrez 6y ago> The 'indirect pointer' points to the memory address of the previous 'next' (or the head). I don't think so. I think the 'indirect pointer' points to the previous 'next' (or the head). It doesn't point to the address of the previous 'next' (or the head). What you say is adding an additional level of indirection that doesn't exist. Reality: indirect -> previous next -> first element What you're saying: indirect -> address of previous next -> previous next -> first element In reality indirect contains the address of the previous next, but it doesn't point to the address of the previous next.
- ndand 6y agoThe "indirect" variable does not point to a list entry directly, like what "head" and "next" variables do, that's why it's named "indirect".
- cmroanirgo 6y agoI 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.
- mjevans 6y agoI 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.
- shallowthought 6y agoThat's a pretty big freakin thing to leave out, though. Code that depends on its context is, some would say, bad.
- cmroanirgo 6y agoThis 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.
- 6y ago
- Hammershaft 6y agoHacker news would benefit from code blocks.
- rocqua 6y agoHacker 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.
- majewsky 6y agoHN codeblocks are just two spaces indented. Any extra spaces indent further. This has no superfluous indentations.
- deleted 6y ago[deleted]
- penteract 6y agoThe article refers to p about 30 times, including in a diagram, so I can understand why they'd pick a shorter name.