kernel- hash list

The overall structure of the hash list in kernel is shown as blow.

Here is the data structure.

struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next, **pprev;
};

Kernel provides some interface to build a whole hash list quickly and they are more useful.

Some figures are illustrated to desrcbie how to use these function calls for the hash list. 

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    struct hlist_node *first = h->first;
    n->next = first;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    n->pprev = &h->first;
}

Insert  a node to the head of hash list.

There are 2 case for this operation and please see below.

Case 1:

no any node exists in the hash list.

Case 2:

Otherwise , there are  more than one nodes  at least in the list.

static inline void hlist_add_before(struct hlist_node *n,
                    struct hlist_node *next)
{
    n->pprev = next->pprev;
    n->next = next;
    next->pprev = &n->next;
    *(n->pprev) = n;
}

Add the node N before the Node next.

 

static inline void hlist_add_after(struct hlist_node *n,
                    struct hlist_node *next)
{
    next->next = n->next;
    n->next = next;
    next->pprev = &n->next;

    if(next->next)
        next->next->pprev  = &next->next;
}

Add the node Next after node N.

static inline void hlist_del(struct hlist_node *n)
{
    __hlist_del(n);
    n->next = LIST_POISON1;
    n->pprev = LIST_POISON2;
}

Remove the node N from the list.

Linux kernel - contain_of

This marco is mostly used in kernel .
The figure is illustrated to descible how the marco "contain_of" work.

The following is the  source code using the marco "contain_of".

#include <stdio.h>

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({            \
     const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
     (type *)( (char *)__mptr - offsetof(type,member) );})

struct  St_Inner{
    int         dw_a;
};

struct St_Outer {
    int         dw_a;
    struct St_Inner    St_b;
    int         dw_c;
};

     
int main ()
{
    struct St_Outer  src;
    struct St_Outer  *p_dest;
    struct  St_Inner *p_Inner;
    p_Inner = &src.St_b;
    
    
    p_dest = container_of (p_Inner,struct St_Outer, St_b);
    
    printf ("p_dest %x == src %x\n",p_dest,&src);
    return 0;
}