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.