[Mesa-dev] [PATCH 09/13] util/list: Add list_empty and list_length functions

[Neil Roberts]

Ian Romanick <idr at freedesktop.org> writes:

>> For what it's worth, I'm strongly in favour of using these
>> kernel-style lists instead of exec_list. The kernel ones seem much
>> less confusing.
>
> Huh? They're practically identical. The only difference is the
> kernel-style lists have a single sentinel node, and that node is
> impossible to identify "in a crowd." The exec_lists use two sentinel
> nodes, and those nodes have one pointer of overlapping storage (head
> and tail are the next and prev pointers of one node, and tail and
> tail_pred are the next and prev pointers of the other). I thought
> there was some ASCII art in list.h that showed this, but that appears
> to not be the case...

Yes, I understand how they work. But you have to admit that the magic of
making the end sentinel overlap with the head sentinel is a bit more
difficult to get your head around then just having a single sentinel. At
least personally I found that more confusing.

> This gives some convenience that you can walk through a list from any
> node in the list without having a pointer to the list itself. I don't
> know if we still do, but there used to be a few places where we took
> advantage of that.

Ok, that is a good point. However if we can't find any examples of where
we are doing this then maybe it isn't all that important. A counter
advantage of the kernel-style lists is that the sentinel is slightly
smaller (one fewer pointer). That might be an important consideration if
you're using them to build up a tree structure with a lot of lists, like
an AST.

However the main advantage for me is that saying “they're easy, they're
just like in the kernel and Wayland” is a lot more likely to have
meaning for someone than saying “they're just like on the Amiga”!

Regards,
- Neil