mkirchner / linked-list-good-taste Goto Github PK

The images / diagrams seem to be extremely good to look at.
Can you share how you made them?

with **p:

static inline list_item **find_indirect(list *l, list_item *target)
{
        list_item **p = &l->head;
        while (*p != target)
                p = &(*p)->next;
        return p;
}

without **p:

static inline list_item **find_indirect(list *l, list_item *target)
{
        while (l->head != target)
                l = &(l->head)->next;
        return l;
}

It works, but it introduces a warning:

Incompatible pointer types assigning to 'list *' (aka 'struct list *') from 'struct list_item **'

I'm not familiar with C, I don't know whether it's better or worse, what do you think?

As knowing the node to remove, why traverse the linked list instead of doing something such as:

target->value=target->next->value;
target->next=target->next->next;

gcc (Ubuntu 10.2.0-13ubuntu1) 10.2.0

reports

$make test
gcc -Wall -O2 -o test_list test_list.c
test_list.c:7:20: error: variably modified ‘items’ at file scope
    7 | static IntListItem items[n];
      |                    ^~~~~
make: *** [Makefile:7: test] Error 1

in line 6 n is defined as a const size_t, C requires compile-time constant expressions, const in C doesn't mean that

by changing

const size_t n = 1000;

to

#define n 1000

the problem gets fixed

I couldn't help noticing that the technique used here is related to the same used (in a functional setting) of the concept of a derivative of a data structure, aka "zipper" https://en.wikipedia.org/wiki/Zipper_(data_structure) . The idea is to use a "hole", an indirection, to hang onto the context of a place where things may be modified. It can be applied (and in a mechanically standardized way, "differentiation") to all kinds of tree structures beyond lists. Very elegant indeed. You may want to point to the literature on derivatives of data structures.

Since you're quoting Linus Torvalds about his opinions of what is good and bad taste, I'd like to point out that he consider typedef struct list_item list_item; to be very bad taste.

Please don’t use things like vps_t. It’s a mistake to use typedef for structures and pointers. When you see a
vps_t a;
in the source, what does it mean? In contrast, if it says
struct virtual_container *a;
you can actually tell what a is.

Lots of people think that typedefs help readability. Not so. They are useful only for:
[Some listed rules. See link to read them.]
Maybe there are other cases too, but the rule should basically be to NEVER EVER use a typedef unless you can clearly match one of those rules.

In general, a pointer, or a struct that has elements that can reasonably be directly accessed should never be a typedef.

https://www.kernel.org/doc/html/v4.10/process/coding-style.html#typedefs

I was confused for the longest time why pointers were being tested for equality, rather than the value. was there a specific reason for this?

seems a bit silly to need to know memory location of target to remove it, and it renders the value element to be unnecessary in this example, along with the whole thing about the integers being randomized.

Will both examples (CS101 and elegant) result in memory leaks because the target not is not freed after being removed from the list?

Both versions of the removal code fail when passed a null or non-existent target.

I agree that the indirect handle approach has a subjective beauty to it.

There is also something to be said for code that can be understood with a cursory glance, and do not require explanations.

To me elegant code is not only efficient but also bulletproof.

remove_elegant will crash if:

1. List is empty, and head is NULL
2. target is not on the list. (does not check for final node's NULL)

There is NO NULL testing in there at all. It totally assumes the list is never null and target is always on it.
Poor code IMO.