About head of kernel linked list structure

About head of kernel linked list structure

[Huaicheng Li]

In my understanding, the head initialised using LIST_HEAD_INIT or defined by LIST_HEAD corresponds to no *real* data field. 
But it *does* have its own _next_ and _prev_ pointers. The _next_ pointer points to the first real node in the doubly linked list,
and the _prev_ pointer points to the last real node. 

I'm wondering if the picture shown at the very bottom of http://kernelnewbies.org/FAQ/LinkedLists is wrong about this. Because
I believe head's _prev_ should point to the last node, which is at the very right. And the last node's _next_ should point to the head.
Just as shown like the red line.

Am I right?



--
Best Regards
Huaicheng Li






-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20150506/5cd631c4/attachment-0001.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: linked_list_example copy.png
Type: image/png
Size: 37281 bytes
Desc: not available
Url : http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20150506/5cd631c4/attachment-0001.png 

About head of kernel linked list structure

[Robert P. J. Day]

On Wed, 6 May 2015, Huaicheng Li wrote:

> In my understanding, the head initialised using LIST_HEAD_INIT or
> defined by LIST_HEAD corresponds to no *real* data field.

  correct. a better way to describe it would be that it corresponds to
no real enclosing payload, so it should never be dereferenced to get
to said payload.

> But it *does* have its own _next_ and _prev_ pointers. The _next_
> pointer points to the first real node in the doubly linked list, and
> the _prev_ pointer points to the last real node.

  so far, so good -- by "real", you mean list heads that actually
correspond to an enclosing payload.

> I'm wondering if the picture shown at the very bottom of
> http://kernelnewbies.org/FAQ/LinkedLists is wrong about this.
> Because

> I believe head's _prev_ should point to the last node, which is at
> the very right. And the last node's _next_ should point to the head.
> Just as shown like the red line.
>
> Am I right?

  it looks fine to me, although my standard is to show next pointers
going to the right, and prev to the left, but this way looks fine.
maybe i'm misunderstanding your objection.

  i once wrote a tutorial on LLs:

http://www.crashcourse.ca/introduction-linux-kernel-programming/intermission-lets-talk-about-linked-lists-and-containerof-free

rday

-- 

========================================================================
Robert P. J. Day                                 Ottawa, Ontario, CANADA
                        http://crashcourse.ca

Twitter:                                       http://twitter.com/rpjday
LinkedIn:                               http://ca.linkedin.com/in/rpjday
========================================================================

About head of kernel linked list structure

[Huaicheng Li]

Hi Robert,

You got my point and I?m sorry for not stating it in a clear way. You are right about the "prev-to-left" and "next-to-right" when drawing the line. At that time, I just wanted to show which node they were pointing at.  Anyway, you solved my puzzle. Also thanks for your excellent article.

--
Best Regards
Huaicheng Li






> On May 7, 2015, at 3:45 AM, Robert P. J. Day <rpjday@crashcourse.ca> wrote:
> 
> On Wed, 6 May 2015, Huaicheng Li wrote:
> 
>> In my understanding, the head initialised using LIST_HEAD_INIT or
>> defined by LIST_HEAD corresponds to no *real* data field.
> 
>  correct. a better way to describe it would be that it corresponds to
> no real enclosing payload, so it should never be dereferenced to get
> to said payload.
> 
>> But it *does* have its own _next_ and _prev_ pointers. The _next_
>> pointer points to the first real node in the doubly linked list, and
>> the _prev_ pointer points to the last real node.
> 
>  so far, so good -- by "real", you mean list heads that actually
> correspond to an enclosing payload.
> 
>> I'm wondering if the picture shown at the very bottom of
>> http://kernelnewbies.org/FAQ/LinkedLists is wrong about this.
>> Because
> 
>> I believe head's _prev_ should point to the last node, which is at
>> the very right. And the last node's _next_ should point to the head.
>> Just as shown like the red line.
>> 
>> Am I right?
> 
>  it looks fine to me, although my standard is to show next pointers
> going to the right, and prev to the left, but this way looks fine.
> maybe i'm misunderstanding your objection.
> 
>  i once wrote a tutorial on LLs:
> 
> http://www.crashcourse.ca/introduction-linux-kernel-programming/intermission-lets-talk-about-linked-lists-and-containerof-free
> 
> rday
> 
> -- 
> 
> ========================================================================
> Robert P. J. Day                                 Ottawa, Ontario, CANADA
>                        http://crashcourse.ca
> 
> Twitter:                                       http://twitter.com/rpjday
> LinkedIn:                               http://ca.linkedin.com/in/rpjday
> ========================================================================

About head of kernel linked list structure

[Mulyadi Santosa]

On Wed, May 6, 2015 at 5:39 PM, Huaicheng Li <lhcwhu@gmail.com> wrote:

> In my understanding, the head initialised using LIST_HEAD_INIT or defined
> by LIST_HEAD corresponds to no *real* data field.
> But it *does* have its own _next_ and _prev_ pointers. The _next_ pointer
> points to the first real node in the doubly linked list,
> and the _prev_ pointer points to the last real node.
>
> I'm wondering if the picture shown at the very bottom of *http://kernelnewbies.org/FAQ/LinkedLists
> <http://kernelnewbies.org/FAQ/LinkedLists>* is wrong about this. Because
> I believe head's _prev_ should point to the last node, which is at the
> very right. And the last node's _next_ should point to the head.
> Just as shown like the red line.
>
> Am I right?
>
>
>
>

Hi Huachieng

AFAIK, if the linked list is not circular one, the last node's next should
point to NULL, so does the head prev's. This is done so you know when you
hit head i.e

if !(head.prev)
{
      // we're at head
}



> --
> Best Regards
> Huaicheng Li
>
>
>
>
>
>
>
> _______________________________________________
> Kernelnewbies mailing list
> Kernelnewbies at kernelnewbies.org
> http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
>
>


-- 
regards,

Mulyadi Santosa
Freelance Linux trainer and consultant

blog: the-hydra.blogspot.com
training: mulyaditraining.blogspot.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20150507/b43227d9/attachment-0001.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: linked_list_example copy.png
Type: image/png
Size: 37281 bytes
Desc: not available
Url : http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20150507/b43227d9/attachment-0001.png 

About head of kernel linked list structure

[Mulyadi Santosa]

On Wed, May 6, 2015 at 5:39 PM, Huaicheng Li <lhcwhu@gmail.com> wrote:

> In my understanding, the head initialised using LIST_HEAD_INIT or defined
> by LIST_HEAD corresponds to no *real* data field.
> But it *does* have its own _next_ and _prev_ pointers. The _next_ pointer
> points to the first real node in the doubly linked list,
> and the _prev_ pointer points to the last real node.
>
> I'm wondering if the picture shown at the very bottom of *http://kernelnewbies.org/FAQ/LinkedLists
> <http://kernelnewbies.org/FAQ/LinkedLists>* is wrong about this. Because
> I believe head's _prev_ should point to the last node, which is at the
> very right. And the last node's _next_ should point to the head.
> Just as shown like the red line.
>
> Am I right?
>
>
>
>

Hi Huachieng

AFAIK, if the linked list is not circular one, the last node's next should
point to NULL, so does the head prev's. This is done so you know when you
hit head i.e

if !(head.prev)
{
      // we're at head
}



-- 
regards,

Mulyadi Santosa
Freelance Linux trainer and consultant

blog: the-hydra.blogspot.com
training: mulyaditraining.blogspot.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20150507/a7d3605c/attachment-0001.html 

About head of kernel linked list structure

[Robert P. J. Day]

On Thu, 7 May 2015, Huaicheng Li wrote:

> Hi Robert,
>
> You got my point and I?m sorry for not stating it in a clear way.
> You are right about the "prev-to-left" and "next-to-right" when
> drawing the line. At that time, I just wanted to show which node
> they were pointing at.  Anyway, you solved my puzzle. Also thanks
> for your excellent article.

  it's a moderately common mistake to not realize that the "head" of a
list is represented by just another "struct list_head" like all the
other elements in the list, but it's a special list_head in the sense
that it does ***not*** represent a valid enclosing data payload, and
should never be dereferenced.

  the way i normally demonstrate this is to show the following macro
from include/linux/list.h:

/**
 * list_for_each        -       iterate over a list
 * @pos:        the &struct list_head to use as a loop cursor.
 * @head:       the head for your list.
 */
#define list_for_each(pos, head) \
        for (pos = (head)->next; pos != (head); pos = pos->next)

  note well how iteration over a list starts from "(head)->next" and
continues until returning back to "(head)" while *not* including that
last address to be dereferenced.

  this also has the (obvious) consequence that you can never forget
which element in a list is the head; otherwise, you'll never know
which element you're not supposed to dereference.

rday

-- 

========================================================================
Robert P. J. Day                                 Ottawa, Ontario, CANADA
                        http://crashcourse.ca

Twitter:                                       http://twitter.com/rpjday
LinkedIn:                               http://ca.linkedin.com/in/rpjday
========================================================================

About head of kernel linked list structure

[Bernd Petrovitsch]

Hi all!

On Don, 2015-05-07 at 17:57 +0700, Mulyadi Santosa wrote:
> On Wed, May 6, 2015 at 5:39 PM, Huaicheng Li <lhcwhu@gmail.com> wrote:
> > In my understanding, the head initialised using LIST_HEAD_INIT or defined
> > by LIST_HEAD corresponds to no *real* data field.
> > But it *does* have its own _next_ and _prev_ pointers. The _next_ pointer
> > points to the first real node in the doubly linked list,
> > and the _prev_ pointer points to the last real node.
[...]
> AFAIK, if the linked list is not circular one, the last node's next should
> point to NULL, so does the head prev's. This is done so you know when you
> hit head i.e
> 
> if !(head.prev)
What programming language?

	Bernd
-- 
"I dislike type abstraction if it has no real reason. And saving
on typing is not a good reason - if your typing speed is the main
issue when you're coding, you're doing something seriously wrong."
    - Linus Torvalds

About head of kernel linked list structure

[Jeff Haran]

From: kernelnewbies-bounces@kernelnewbies.org [mailto:kernelnewbies-bounces at kernelnewbies.org] On Behalf Of Mulyadi Santosa
Sent: Thursday, May 07, 2015 3:53 AM
To: Huaicheng Li
Cc: kernelnewbies
Subject: Re: About head of kernel linked list structure



On Wed, May 6, 2015 at 5:39 PM, Huaicheng Li <lhcwhu at gmail.com<mailto:lhcwhu@gmail.com>> wrote:
In my understanding, the head initialised using LIST_HEAD_INIT or defined by LIST_HEAD corresponds to no *real* data field.
But it *does* have its own _next_ and _prev_ pointers. The _next_ pointer points to the first real node in the doubly linked list,
and the _prev_ pointer points to the last real node.

I'm wondering if the picture shown at the very bottom of http://kernelnewbies.org/FAQ/LinkedLists is wrong about this. Because
I believe head's _prev_ should point to the last node, which is at the very right. And the last node's _next_ should point to the head.
Just as shown like the red line.

Am I right?

[cid:image002.png at 01D089A8.8896F550]


Hi Huachieng
AFAIK, if the linked list is not circular one, the last node's next should point to NULL, so does the head prev's. This is done so you know when you hit head i.e
if !(head.prev)
{
      // we're at head
}

Just pointing out that these lists are circular. Back in the old days we used to call them "rings".

>From list.h:

183 /**
184  * list_empty - tests whether a list is empty
185  * @head: the list to test.
186  */
187 static inline int list_empty(const struct list_head *head)
188 {
189         return head->next == head;
  190 }

Jeff Haran

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20150508/1377f263/attachment.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image002.png
Type: image/png
Size: 11417 bytes
Desc: image002.png
Url : http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20150508/1377f263/attachment.png 

About head of kernel linked list structure

[Mulyadi Santosa]

On Sat, May 9, 2015 at 6:05 AM, Jeff Haran <Jeff.Haran@citrix.com> wrote:

>
> Just pointing out that these lists are circular. Back in the old days we
> used to call them "rings".
>
>
>
> From list.h:
>
>
>
> 183 /**
>
> 184  * list_empty - tests whether a list is empty
>
> 185  * @head: the list to test.
>
> 186  */
>
> 187 static inline int list_empty(const struct list_head *head)
>
> 188 {
>
> 189         return head->next == head;
>
>   190 }
>
>
>
> Jeff Haran
>
>
>


After re-reading the page about linked list in kernelnewbies, I agree it's
circular list. I just didn't realize that even after reading carefully the
first post

-- 
regards,

Mulyadi Santosa
Freelance Linux trainer and consultant

blog: the-hydra.blogspot.com
training: mulyaditraining.blogspot.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20150511/e8abfbe4/attachment.html