Linus on lists

This is Linux at TED explaining how he traverses linked lists. Can you understand that code?

Other urls found in this thread:

isis.poly.edu/kulesh/stuff/src/klist/
lxr.free-electrons.com/source/include/linux/list.h
twitter.com/NSFWRedditImage

That looks like a fairly typical linked list operation. What's supposed to be so special about it?

Linked list traversal is literally first assignment in first data structures course at any university.

Of course it is. But it's thought like:

while (start != null)
{
node* temp = start;
free(temp);
start = start -> next;
}

Now look at that pointer game and tell me you understand it line by line.

>Can you understand that code?

Anyone with a degree in computer science will understand that code.

It's a little weird that "indirect" is used without declaring it -- implying that it's not a local variable. Normally, you would want "indirect" to be a local. They don't show the data types, but it's obvious that "indirect" would be a pointer to a pointer.

It's also a little weird that the function header doesn't have "void" as a return type.

The code is otherwise correct, but those two irregularities make the code look a little sloppy to me.

What happens if the list doesn't contain the entry?

I don't even know what the fuck a linked list is.

Hello pajeet

Yes, but this is a small fraction of a bigger codebase

it segfaults like any decent C code

kek

I slept through most of a data structures class the semester before withdrawing from college and even I understand this shit four years later.

That is some shit-ass looking code. I can't imagine why anyone would want to write a function like that.

void remove_list_entry(node *head, node *entry)
{
while (head && head->next != entry)
head = head->next;

if (head)
{
head->next = entry->next;
}
}

Presumably, wherever this code lives, it made more sense to pass entry by value.

fpbp

the fuck are you trying to say?

Fuck this autism shit, just type remove_list_entry(entry) when you need.

you free start before you read start->next. While this usually wouldn't matter, surely there's a small chance the memory will be reallocated and changed.

I wouldn't write it this way. It removes first element if the list doesn't contain what you're trying to remove.

With this code you would likely segfault with entry == NULL and with entry == head it wouldn't work

>you would likely segfault with entry == NULL
That's somewhat acceptable, though. Supply a wrong argument -> get a wrong result.

>and with entry == head it wouldn't work
And that one is an actual problem. For this operation, it is inevitable that you use node **head argument (two stars) or a structure different from node entirely.

>That's somewhat acceptable
Yeah I guess I just like writing my C program like fucking bunker to avoid any segfaul

>That's an actual problem
Fun fact I've looked at my C code when I was learning it, and apparently it took my quite a while to grasp this concept

>linked lists
harmful

>if branch
you should go back to python, C folks don't take kindly to that kind of useless bloat

i would say its a simplified code snipped to explain the retarded audience linked lists

they would probably just be more confused if it would say auto indirect etc.

pretty basic pointer shit, are you stupid?

better question, why does he assign indirect at the end, this implies its not a local variable like suggested and the whole thing part of some bigger snippet

lets forget that im retarded, he dereferencing indirect, so makes sense

It is a local variable. Also head is a member of class to which the function belongs. This is pseudocode. You don't have to look for and point out small inconsistencies to demonstrate that your grasp of C is at least at beginner's level.

>and just remove it
>doesn't free memory
So this... is the power of Linux...

Depending on API, this can be correct; user still has the pointer to the entry and can use it for a while before freeing.

The code example Linus provided was an example he provided to explain the types of optimization he likes to do to make code "neat" or whatever the word he chose to use for it.

The reason being that it avoids unnecessary branch points and just does its' thing. Your code example does 2 comparisons per loop (one for head, and another for head->next), while Linus' version only does 1 per loop iteration, and no if statement after the entry has been found.

So the code is designed to die in an unexpected when the entry is not in list. That's extraordinary helpful.

I presume whatever environment it lives in expects to receive only valid arguments.

Right, but as a user of this function, I want it to work regardless. I get it that linus created environment for himself in the kernel where this is acceptable, where this is necessary for smaller image size, for speed, but outside of developing kernel, this kind of thing would be taken very negatively.

Depends on the user. If the user knows the function isn't safe, they'd either sanitize their arguments before passing it (bad idea and misses the point I think), and in other cases you would create extensive helper test cases for everything else to make sure an invalid argument is never generated. Forcing that functionality onto remove_list_entry can be seen as just dodging larger issues in other parts of the code.

In practice, there will almost always be a wrapper that makes the function not fail, and the wrapper will be used in code in place of that function.

When working against a tight time schedule and perfecting the code would take too much time, that much makes sense. But, it's still hiding or otherwise overlooking bigger problems in the code. Wether that matters or not is to be decided on a case-by-case basis.

this is why you use ML/haskell

You're always on a time schedule. If you can make a small tradeoff and give up some speed to not think of whether this or that decision needs to be taken, I see it as a good tradeoff.

>his programming language is so shitty it doesn't even come with an implementation of elementary data structures
Damn.

underrated

The linked list type used in linux is not a regular C implementation. It does help to have an explanation.

isis.poly.edu/kulesh/stuff/src/klist/
lxr.free-electrons.com/source/include/linux/list.h

huh?

it's a reddit meme

If the entry is a huge-ass structure, it may not be a good idea to pass it by value. But I see what you mean, does not compare node values but node pointers values instead, which does not make much sense...
Why would you already have the pointer to the node you want to remove without traversing the linked list first?