On Sun, 23 Mar 2008, Avishay Traeger wrote:
> I think that Love is comparing circular linked lists to regular
> singly-linked lists, but it isn't very clear. We can compare the
> cases of how to traverse a list given some element in the list.
>
> With non-circular, singly-linked lists: We need a 'head' pointer so
> that we can access the elements before our element. I think this is
> the special head pointer that we don't need in the kernel
> implementation.
ah, but you *do* need that special, extra element in each kernel list
that is the "head" element. just look at, for example, the query of
whether a list is "empty":
static inline int list_empty(const struct list_head *head)
{
return head->next == head; <- "empty" list contains 1 elt
}
and, as i pointed out before, the list_for_each() list traversal code,
which *requires* you start at the head and not just anywhere in the
list for the traversal to work properly.
> With circular, doubly-linked lists (or singly-linked, doesn't
> matter): Just start wherever you are, and traverse the list. You
> would have to make sure to skip 'head', as you noticed. However,
> there is no need for 'head' to traverse the list from any given
> location. In other words, there is no NEED for a special head
> pointer with a circular linked list, but the implementation still
> uses one to make things cleaner.
i won't argue that having that extra head or "sentinel" (or whatever
you want to call it) makes for a cleaner implementation. but it's
problematic when the documentation then goes on to claim that there's
nothing special about any particular list element, and one is just as
good as another, and it doesn't matter where you start, etc, etc. do
you see my point?
i have no beef with the current implementation -- i have a beef with
the documentation which misrepresents and over-simplifies it.
rday
--
========================================================================
Robert P. J. Day
Linux Consulting, Training and Annoying Kernel Pedantry:
Have classroom, will lecture.
http://crashcourse.ca Waterloo, Ontario, CANADA
========================================================================
--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx
Please read the FAQ at http://kernelnewbies.org/FAQ
