linux - hlist

一樣在include/linux/list.h中，開宗明義的說Mostly useful for hash tables where the two pointer list head is too wastful，點出hlist為啥要有hlist_head和hlist_node了。
/* * Double linked lists with a single pointer list head. * Mostly useful for hash tables where the two pointer list head is * too wasteful. * You lose the ability to access the tail in O(1). */ struct hlist_head { struct hlist_node *first; }; struct hlist_node { struct hlist_node *next, **pprev; }; #define HLIST_HEAD_INIT { .first = NULL } #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL } #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) static inline void INIT_HLIST_NODE(struct hlist_node *h) { h->next = NULL; h->pprev = NULL; } HLIST_HEAD_INIT()和HLIST_HEAD()用於未定義的變數，INIT_HLIST_HEAD()用於以定義的變數。

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; } /* next must be != NULL */ 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; } 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; } hlist_add_head()就很是很簡單的將n加到h的第一個node上。

hlist_add_after()是將next加到n的後面去，這裡新加入的node是next。

hlist_add_before()是將n加到next的前面去，這裡新加入的node則是n。


static inline void __hlist_del(struct hlist_node *n) { struct hlist_node *next = n->next; struct hlist_node **pprev = n->pprev; *pprev = next; if (next) next->pprev = pprev; } __hlist_del()就像__list_del()一樣，把要del的node的前後串起來。