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.