[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: hlist in list.h

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




--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx
Please read the FAQ at http://kernelnewbies.org/FAQ