Re: hlist in list.h

[Scott Lovenberg <scott.lovenberg@xxxxxxxxx>]

Peter Kerpedjiev wrote:
> Scott Lovenberg wrote:
> > Grob Team wrote:
> > > Hi,
> > >
> > > I was looking the hlist's implementation in the linux kernel 
> > > (linux/include/linux/list.h). The description of hlist_node is:
> > >
> > > struct hlist_node {
> > > struct hlist_node *next, **pprev;
> > > };
> > >
> > > I don't understand why there is a pointer to a pointer (**pprev) for 
> > > the previous node instead of a simple pointer (*pprev). I quickly 
> > > look the general functions in list.h who use this structure and I 
> > > don't see something particular which can explain why we use a 
> > > pointer to a pointer. Can someone explain it to me?
> > >
> > > Thanks
> > I've never looked at any of the list stuff, but I assume it's an 
> > array of pointers.  Just like when you pass in args to your main(argv 
> > char**).  As for why it's like this, I have no clue, but there is 
> > probably a many->1 relationship allowable that needs to trace back 
> > correctly.
> I don't think this is the case here...
>
> Check out this link and search for 'hlist_node':
>
> http://tenyear.net/books/LinuxKernelPrimer/ch02lev1sec1.html
>
> You will see that it was added to allow the head of the list to 
> contain just one pointer (thus saving space). To allow insertion and 
> deletion, however, nodes must still reference the pointers that 
> reference them. They (the pointers) don't need to point to the actual 
> nodes. They just need to point to whatever is pointing to that 
> particular node (the 'first' member of hlist_head, or the 'next' 
> pointer of the previous node).
>
> If it were a single pointer (i.e. struct hlist_node *prev), then that 
> pointer on the first node would be broken since it would be pointing 
> to a struct hlist_head instead of a hlist_node.
>
> If you're really interested you can also take a look at lkml posts 
> introducing this new type of list here:
>
> http://lkml.org/lkml/2000/7/28/10
>
> I hope that helps,
>
> -Peter
You are correct. 
That's what I was attempting to say when I said 'array of pointers', but 
re-reading it a few hours later, I don't think I said what I thought I 
was trying to say...I think. :).  You've explained it very well.  Thank you!
begin:vcard
fn:Scott Lovenberg
n:Lovenberg;Scott
email;internet:scott.lovenberg@xxxxxxxxx
title:Student
tel;cell:570-856-2999
x-mozilla-html:TRUE
url:http://www.scottlovenberg.com
version:2.1
end:vcard