On Sun, 2008-03-23 at 08:49 -0400, Robert P. J. Day wrote:
> 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
> }
Yes, writing list_empty without 'head' would be pretty impossible with
the current implementation.
> 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.
Yes, I totally agree with you.
Avishay
--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx
Please read the FAQ at http://kernelnewbies.org/FAQ
