Use of double pointer in linux kernel Hash list implementation

Use of double pointer in linux kernel Hash list implementation

[Balachandar]

[-- Attachment #1: Type: text/plain, Size: 636 bytes --]

Hi,
  I am trying to understand Linux Kernel implementation of linked list and
hash table. A link to the implementation is
here<http://lxr.linux.no/linux+v2.6.34/include/linux/list.h>.
I understood the linked list implementation. But i am little confused of why
double pointers is being used in hlist (**pprev). Link for hlist is
here<http://lxr.linux.no/linux+v2.6.34/include/linux/list.h#L554>.
I understand that hlist is used in implementation of hash table since head
of the list requires only one pointer and it saves space. Why cant it be
done using single pointer (just *prev like the linked list)? Please help me.

Thanks,
Bala

[-- Attachment #2: Type: text/html, Size: 720 bytes --]

Re: Use of double pointer in linux kernel Hash list implementation

[Namhyung Kim]

[-- Attachment #1: Type: text/plain, Size: 708 bytes --]

2010-06-16 (수), 22:50 -0400, Balachandar:
> Hi,
>   I am trying to understand Linux Kernel implementation of linked list
> and hash table. A link to the implementation is here. I understood the
> linked list implementation. But i am little confused of why double
> pointers is being used in hlist (**pprev). Link for hlist is here. I
> understand that hlist is used in implementation of hash table since
> head of the list requires only one pointer and it saves space. Why
> cant it be done using single pointer (just *prev like the linked
> list)? Please help me.
> 
> 
> Thanks,
> Bala


IMHO **pprev is only needed for fast deletion and/or insertion.


-- 
Regards,
Namhyung Kim


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: Use of double pointer in linux kernel Hash list implementation

[Balachandar]

[-- Attachment #1: Type: text/plain, Size: 888 bytes --]

On Wed, Jun 16, 2010 at 11:32 PM, Namhyung Kim <namhyung@gmail.com> wrote:

> 2010-06-16 (수), 22:50 -0400, Balachandar:
> > Hi,
> >   I am trying to understand Linux Kernel implementation of linked list
> > and hash table. A link to the implementation is here. I understood the
> > linked list implementation. But i am little confused of why double
> > pointers is being used in hlist (**pprev). Link for hlist is here. I
> > understand that hlist is used in implementation of hash table since
> > head of the list requires only one pointer and it saves space. Why
> > cant it be done using single pointer (just *prev like the linked
> > list)? Please help me.
> >
> >
> > Thanks,
> > Bala
>
>
> IMHO **pprev is only needed for fast deletion and/or insertion.
>
>
>
>
My doubt is why not use *prev as it is used in list_head implementation
rather than **pprev.

[-- Attachment #2: Type: text/html, Size: 1403 bytes --]

Re: Use of double pointer in linux kernel Hash list implementation

[Namhyung Kim]

[-- Attachment #1: Type: text/plain, Size: 365 bytes --]

2010-06-17 (목), 10:34 -0400, Balachandar:

> 
> My doubt is why not use *prev as it is used in list_head
> implementation rather than **pprev.  

hlist is simple linked list so there is no need of *prev. **pprev is a
kind of hack and should not be accessed in the outside of hlist. If you
need *prev, just use list_head.

-- 
Regards,
Namhyung Kim


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 198 bytes --]