在Linux內(nèi)核中，hlist（哈希鏈表）使用非常廣泛。本文將對(duì)其數(shù)據(jù)結(jié)構(gòu)和核心函數(shù)進(jìn)行分析。
和hlist相關(guān)的數(shù)據(jù)結(jié)構(gòu)有兩個(gè)
(1) hlist_head
struct hlist_head {
struct hlist_node *first;
};
(2) hlist_node
struct hlist_node {
struct hlist_node *next, **pprev;
};
顧名思義， hlist_head表示哈希表的頭結(jié)點(diǎn)。 哈希表中每一個(gè)entry(hlist_head)所對(duì)應(yīng)的都是一個(gè)鏈表（hlist)，該鏈表的結(jié)點(diǎn)由hlist_node表示。
hlist_head結(jié)構(gòu)體只有一個(gè)域，即first。 first指針指向該hlist鏈表的第一個(gè)節(jié)點(diǎn)。
hlist_node結(jié)構(gòu)體有兩個(gè)域，next 和pprev。 next指針很容易理解，它指向下個(gè)hlist_node結(jié)點(diǎn)，倘若該節(jié)點(diǎn)是鏈表的最后一個(gè)節(jié)點(diǎn)，next指向NULL。
pprev是一個(gè)二級(jí)指針， 它指向前一個(gè)節(jié)點(diǎn)的next指針。為什么我們需要這樣一個(gè)指針呢？它的好處是什么？
在回答這個(gè)問(wèn)題之前，我們先研究另一個(gè)問(wèn)題：為什么散列表的實(shí)現(xiàn)需要兩個(gè)不同的數(shù)據(jù)結(jié)構(gòu)？
散列表的目的是為了方便快速的查找，所以散列表通常是一個(gè)比較大的數(shù)組，否則“沖突”的概率會(huì)非常大， 這樣也就失去了散列表的意義。如何做到既能維護(hù)一張大表，又能不使用過(guò)多的內(nèi)存呢？就只能從數(shù)據(jù)結(jié)構(gòu)上下功夫了。所以對(duì)于散列表的每個(gè)entry，它的結(jié)構(gòu)體中只存放一個(gè)指針，解決了占用空間的問(wèn)題。現(xiàn)在又出現(xiàn)了另一個(gè)問(wèn)題：數(shù)據(jù)結(jié)構(gòu)不一致。顯然，如果hlist_node采用傳統(tǒng)的next,prev指針， 對(duì)于第一個(gè)節(jié)點(diǎn)和后面其他節(jié)點(diǎn)的處理會(huì)不一致。這樣并不優(yōu)雅，而且效率上也有損失。
hlist_node巧妙地將pprev指向上一個(gè)節(jié)點(diǎn)的next指針的地址，由于hlist_head和hlist_node指向的下一個(gè)節(jié)點(diǎn)的指針類型相同，這樣就解決了通用性！
下面我們?cè)賮?lái)看一看hlist_node這樣設(shè)計(jì)之后，插入 刪除這些基本操作會(huì)有什么不一樣。
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用于刪除節(jié)點(diǎn)n。
首先獲取n的下一個(gè)節(jié)點(diǎn)next， n->pprev指向n的前一個(gè)節(jié)點(diǎn)的next指針的地址， 這樣×pprev就代表n前一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)（現(xiàn)在即n本身），第三行代碼*pprev=next;就將n的前一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)關(guān)聯(lián)起來(lái)了。至此，n節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的關(guān)聯(lián)工作就完成了，現(xiàn)在再來(lái)完成下一個(gè)節(jié)點(diǎn)的關(guān)聯(lián)工作。如果n是鏈表的最后一個(gè)節(jié)點(diǎn)，那么n->next即為空， 則無(wú)需任何操作，否則，next->pprev = pprev。
給鏈表增加一個(gè)節(jié)點(diǎn)需要考慮兩個(gè)條件：(1)是否為鏈表的首個(gè)節(jié)點(diǎn)(2)普通節(jié)點(diǎn)。
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;
}
首先討論條件（1）。
first = h->first; 獲取當(dāng)前鏈表的首個(gè)節(jié)點(diǎn)；
n->next = fist; 將n作為鏈表的首個(gè)節(jié)點(diǎn)，讓first往后靠；
先來(lái)看最后一行 n->pprev - &h->first; 將n的pprev指向hlist_head的first指針，至此關(guān)于節(jié)點(diǎn)n的關(guān)聯(lián)工作就做完了。
再來(lái)看倒數(shù)第二行 h->first = n; 將節(jié)點(diǎn)h的關(guān)聯(lián)工作做完；
最后我們?cè)賮?lái)看原先的第一個(gè)節(jié)點(diǎn)的關(guān)聯(lián)工作，對(duì)于它來(lái)說(shuō)，僅僅需要更新一下pprev的關(guān)聯(lián)信息： first->pprev = &n->next;
接下來(lái)討論條件（2）。 這里也包括兩種情況：a)插在當(dāng)前節(jié)點(diǎn)的前面b)插在當(dāng)前節(jié)點(diǎn)的后面
/* 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;
}
先討論情況a) 將節(jié)點(diǎn)n 插到next之前 （n是新插入的節(jié)點(diǎn))
還是一個(gè)一個(gè)節(jié)點(diǎn)的搞定（一共三個(gè)節(jié)點(diǎn)）， 先搞定節(jié)點(diǎn)n
n->pprev = next->prev; 將 next 的pprev 賦值給n->pprev n取代next的位置
n->next = next; 將next作為n的下一個(gè)節(jié)點(diǎn)， 至此節(jié)點(diǎn)n的關(guān)聯(lián)動(dòng)作完成。
next->pprev = &n->next; next的關(guān)聯(lián)動(dòng)作完成。
*(n->pprev) = n; n->pprev表示n的前一個(gè)節(jié)點(diǎn)的next指針； *(n->pprev)則表示n的前一個(gè)節(jié)點(diǎn)next指針?biāo)赶蛳乱粋€(gè)節(jié)點(diǎn)的內(nèi)容， 這里將n賦值給它，正好完成它的關(guān)聯(liá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;
}
再來(lái)看情況b) 將結(jié)點(diǎn)next插入到n之后 (next是新插入的節(jié)點(diǎn)）
具體步驟就不分析了。 應(yīng)該也很容易。
下面我還要介紹一個(gè)函數(shù)：
static inline int hlist_unhashed(const struct hlist_node *h)
{
return !h->pprev;
}
這個(gè)函數(shù)的目的是判斷該節(jié)點(diǎn)是否已經(jīng)存在hash表中。這里處理得很巧妙。 判斷前一個(gè)節(jié)點(diǎn)的next指向的地址是否為空。
最后我們看一個(gè)具體的例子，Linux內(nèi)核是如何管理pid的。（正好和上一篇介紹pid的文章相呼應(yīng)：）） 基于內(nèi)核3.0.3
內(nèi)核初始化時(shí)要調(diào)用pidhash_init（）創(chuàng)建哈希表。 該函數(shù)會(huì)在 start_kernel()函數(shù)里被調(diào)用(init/main.c Line 509)
void __init pidhash_init(void)
{
int i, pidhash_size;
pid_hash = alloc_large_system_hash("PID", sizeof(*pid_hash), 0, 18,
HASH_EARLY | HASH_SMALL,
&pidhash_shift, NULL, 4096);
pidhash_size = 1 << pidhash_shift;
for (i = 0; i < pidhash_size; i++)
INIT_HLIST_HEAD(&pid_hash[i]);
}
從這個(gè)函數(shù)可以看到內(nèi)核會(huì)在slab上分配一個(gè)大小為pidhash_size的數(shù)組，然后為每一個(gè)entry進(jìn)行初始化（INIT_HLIST_HEAD)
在alloc_pid函數(shù)里
struct pid *alloc_pid(struct pid_namespace *ns)
{
struct pid *pid;
enum pid_type type;
int i, nr;
struct pid_namespace *tmp;
struct upid *upid;
pid = kmem_cache_alloc(ns->pid_cachep, GFP_KERNEL); /* 在slab上分配pid結(jié)構(gòu)體 */
if (!pid)
goto out;
tmp = ns;
for (i = ns->level; i >= 0; i--) { /* 雖然這里是for循環(huán)，實(shí)際只會(huì)運(yùn)行一次，因?yàn)楝F(xiàn)在只支持global namespace即ns->level=0 */
nr = alloc_pidmap(tmp); /* 在各級(jí)pid_namespace上尋找并分配pid的值 */
if (nr < 0)
goto out_free;
pid->numbers[i].nr = nr;
pid->numbers[i].ns = tmp;
tmp = tmp->parent;
}
get_pid_ns(ns);
pid->level = ns->level;
atomic_set(&pid->count, 1);
for (type = 0; type < PIDTYPE_MAX; ++type)
INIT_HLIST_HEAD(&pid->tasks[type]);
upid = pid->numbers + ns->level;
spin_lock_irq(&pidmap_lock);
for ( ; upid >= pid->numbers; --upid)
hlist_add_head_rcu(&upid->pid_chain,
&pid_hash[pid_hashfn(upid->nr, upid->ns)]); /* 將各級(jí)namespace中的upid插入pidhash的哈希表里 */
spin_unlock_irq(&pidmap_lock);
out:
return pid;
out_free:
while (++i <= ns->level)
free_pidmap(pid->numbers + i);
kmem_cache_free(ns->pid_cachep, pid);
pid = NULL;
goto out;
}
在Linux內(nèi)核中，hlist（哈希鏈表）使用非常廣泛。本文將對(duì)其數(shù)據(jù)結(jié)構(gòu)和核心函數(shù)進(jìn)行分析。
和hlist相關(guān)的數(shù)據(jù)結(jié)構(gòu)有兩個(gè)：hlist_head 和 hlist_node
//hash桶的頭結(jié)點(diǎn)struct hlist_head {
struct hlist_node *first;//指向每一個(gè)hash桶的第一個(gè)結(jié)點(diǎn)的指針
};
//hash桶的普通結(jié)點(diǎn)struct hlist_node {
struct hlist_node *next;//指向下一個(gè)結(jié)點(diǎn)的指針
struct hlist_node **pprev;//指向上一個(gè)結(jié)點(diǎn)的next指針的地址
};
結(jié)構(gòu)如下圖所示：
hlist_head結(jié)構(gòu)體只有一個(gè)域，即first。 first指針指向該hlist鏈表的第一個(gè)節(jié)點(diǎn)。
hlist_node結(jié)構(gòu)體有兩個(gè)域，next 和pprev。 next指針很容易理解，它指向下個(gè)hlist_node結(jié)點(diǎn)，倘若該節(jié)點(diǎn)是鏈表的最后一個(gè)節(jié)點(diǎn)，next指向NULL。
pprev是一個(gè)二級(jí)指針， 它指向前一個(gè)節(jié)點(diǎn)的next指針的地址。為什么我們需要這樣一個(gè)指針呢？它的好處是什么？
在回答這個(gè)問(wèn)題之前，我們先研究另一個(gè)問(wèn)題：為什么哈希表的實(shí)現(xiàn)需要兩個(gè)不同的數(shù)據(jù)結(jié)構(gòu)？
哈希表的目的是為了方便快速的查找，所以哈希表中hash桶的數(shù)量通常比較大，否則“沖突”的概率會(huì)非常大，這樣也就失去了哈希表的意義。如何做到既能維護(hù)一張大表，又能不使用過(guò)多的內(nèi)存呢？就只能從數(shù)據(jù)結(jié)構(gòu)上下功夫了。所以對(duì)于哈希表的每個(gè)hash桶，它的結(jié)構(gòu)體中只存放一個(gè)指針，解決了占用空間的問(wèn)題?，F(xiàn)在又出現(xiàn)了另一個(gè)問(wèn)題：數(shù)據(jù)結(jié)構(gòu)不一致。顯然，如果hlist_node采用傳統(tǒng)的next,prev指針，對(duì)于第一個(gè)節(jié)點(diǎn)和后面其他節(jié)點(diǎn)的處理會(huì)不一致。這樣并不優(yōu)雅，而且效率上也有損失。
hlist_node巧妙地將pprev指向上一個(gè)節(jié)點(diǎn)的next指針的地址，由于hlist_head的first域指向的結(jié)點(diǎn)類型和hlist_node指向的下一個(gè)結(jié)點(diǎn)的結(jié)點(diǎn)類型相同，這樣就解決了通用性！
如果要?jiǎng)h除hash桶對(duì)應(yīng)鏈表中的第一個(gè)普通結(jié)點(diǎn)
對(duì)應(yīng)的程序代碼如下：
static inline void __hlist_del(
struct hlist_node *n)
{
struct hlist_node *next = n->next;
//獲取指向第二個(gè)普通結(jié)點(diǎn)的指針 struct hlist_node **pprev = n->pprev;
//保留待刪除的第一個(gè)結(jié)點(diǎn)的pprev域（即頭結(jié)點(diǎn)first域的地址），此時(shí) pprev = &first *pprev = next;
/*
因?yàn)閜prev = &first，所以*pprev = next，相當(dāng)于 first = next
即將hash桶的頭結(jié)點(diǎn)指針指向原來(lái)的第二個(gè)結(jié)點(diǎn)，如上圖中的黑線1
*/ if (next)
//如果第二個(gè)結(jié)點(diǎn)不為空 next->pprev = pprev;
//將第二個(gè)結(jié)點(diǎn)的pprev域設(shè)置為頭結(jié)點(diǎn)first域的地址，如上圖中的黑線2}
如果要?jiǎng)h除hash桶對(duì)應(yīng)鏈表中的非第一個(gè)結(jié)點(diǎn)
對(duì)應(yīng)的程序代碼如下：
static inline void __hlist_del(
struct hlist_node *n)
{
struct hlist_node *next = n->next;
//獲取指向待刪除結(jié)點(diǎn)的下一個(gè)普通結(jié)點(diǎn)的指針 struct hlist_node **pprev = n->pprev;
//獲取待刪除結(jié)點(diǎn)的pprev域 *pprev = next;
//修改待刪除結(jié)點(diǎn)的pprev域，邏輯上使待刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指向待刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)，如上圖中的黑線1 if (next)
//如果待刪除結(jié)點(diǎn)的下一個(gè)普通結(jié)點(diǎn)不為空 next->pprev = pprev;
//設(shè)置下一個(gè)結(jié)點(diǎn)的pprev域，如上圖中的黑線2，保持hlist的結(jié)構(gòu)}
可以看到刪除第一個(gè)普通結(jié)點(diǎn)和刪除非第一個(gè)普通結(jié)點(diǎn)的代碼是一樣的。
下面再來(lái)看看如果hlist_node中包含兩個(gè)分別指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針
很明顯刪除hash桶對(duì)應(yīng)鏈表中的非第一個(gè)普通結(jié)點(diǎn)，只需要如下兩行代碼：
n->next->prev = n->prev;
n->prev->next = n->next;
可是，如果是刪除的hash桶對(duì)應(yīng)鏈表中的第一個(gè)普通結(jié)點(diǎn)：
此時(shí) n->prev->next = n->next 就會(huì)出問(wèn)題，因?yàn)閔ash桶的表頭結(jié)點(diǎn)沒(méi)有next域
所以，明顯在這種情況下刪除hash桶對(duì)應(yīng)鏈表的第一個(gè)普通結(jié)點(diǎn)和非第一個(gè)普通結(jié)點(diǎn)的代碼是不一樣的。
同樣的情況也存在于插入操作。
附一張?jiān)趆ash桶頭結(jié)點(diǎn)之后，插入第一個(gè)普通結(jié)點(diǎn)的圖：
在遍歷上，如果使用hlist_hode, list_node指針進(jìn)行遍歷，兩者過(guò)程大致相似。
#define list_for_each(pos, head)
for (pos = (head)->next; prefetch(pos->next), pos != (head);
pos = pos->next)
#define hlist_for_each(pos, head)
for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; });
pos = pos->next)
如果使用其寄生結(jié)構(gòu)的指針進(jìn)行遍歷，則hlist與list也略有不同，hlist在遍歷時(shí)需要一個(gè)指向hlist_node的臨時(shí)指針，該指針的引入，一是為了遍歷，而list的遍歷在list_entry的參數(shù)中實(shí)現(xiàn)了，更主要的目的在于判斷結(jié)束，因?yàn)?/span>hlist最后一個(gè)節(jié)點(diǎn)的next為NULL，只有hlist_node指向NULL時(shí)才算結(jié)束，而這個(gè)NULL不包含在任何寄生結(jié)構(gòu)內(nèi)，不能通過(guò)tpos->member的方式訪問(wèn)到，故臨時(shí)變量pos的引入時(shí)必須的。
#define list_for_each_entry(pos, head, member)
for (pos = list_entry((head)->next, typeof(*pos), member);
prefetch(pos->member.next), &pos->member != (head);
pos = list_entry(pos->member.next, typeof(*pos), member))
#define hlist_for_each_entry(tpos, pos, head, member)
for (pos = (head)->first;
pos && ({ prefetch(pos->next); 1;}) &&
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});
pos = pos->next)
另外，list和hlist的遍歷都實(shí)現(xiàn)了safe版本，因在遍歷時(shí)，沒(méi)有任何特別的東西來(lái)阻止對(duì)鏈表執(zhí)行刪除操作（通常在使用鏈表時(shí)使用鎖來(lái)保護(hù)并發(fā)訪問(wèn)）。安全版本的遍歷函數(shù)使用臨時(shí)存放的方法使得檢索鏈表時(shí)能不被刪除操作所影響。
#define list_for_each_safe(pos, n, head)
for (pos = (head)->next, n = pos->next; pos != (head);
pos = n, n = pos->next)
#define hlist_for_each_safe(pos, n, head)
for (pos = (head)->first; pos && ({ n = pos->next; 1; });
pos = n)
附上linux內(nèi)核中與hlist相關(guān)的完整代碼：
//hash桶的頭結(jié)點(diǎn)
struct hlist_head {
struct hlist_node *first; //指向每一個(gè)hash桶的第一個(gè)結(jié)點(diǎn)的指針
};
//hash桶的普通結(jié)點(diǎn)
struct hlist_node {
struct hlist_node *next; //指向下一個(gè)結(jié)點(diǎn)的指針
struct hlist_node **pprev; //指向上一個(gè)結(jié)點(diǎn)的next指針的地址
};
//以下三種方法都是初始化hash桶的頭結(jié)點(diǎn)
#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
//初始化hash桶的普通結(jié)點(diǎn)
static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
h->next = NULL;
h->pprev = NULL;
}
//判斷一個(gè)結(jié)點(diǎn)是否已經(jīng)存在于hash桶中
static inline int hlist_unhashed(const struct hlist_node *h)
{
return !h->pprev;
}
//判斷一個(gè)hash桶是否為空
static inline int hlist_empty(const struct hlist_head *h)
{
return !h->first;
}
static inline void __hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next; //獲取指向待刪除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的指針
struct hlist_node **pprev = n->pprev; //保留待刪除結(jié)點(diǎn)的pprev域
*pprev = next; //修改待刪除結(jié)點(diǎn)的pprev域，邏輯上使待刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指向待刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)
if (next)
next->pprev = pprev; //設(shè)置待刪除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的pprev域，保持hlist的結(jié)構(gòu)
}
static inline void hlist_del(struct hlist_node *n)
{
__hlist_del(n); //刪除結(jié)點(diǎn)之后，需要將其next域和pprev域設(shè)置為無(wú)用值
n->next = LIST_POISON1;
n->pprev = LIST_POISON2;
}
static inline void hlist_del_init(struct hlist_node *n)
{
if (!hlist_unhashed(n))
{
__hlist_del(n);
INIT_HLIST_NODE(n);
}
}
//將普通結(jié)點(diǎn)n插入到頭結(jié)點(diǎn)h對(duì)應(yīng)的hash桶的第一個(gè)結(jié)點(diǎn)的位置
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 */
//在next結(jié)點(diǎn)之前插入結(jié)點(diǎn)n，即使next結(jié)點(diǎn)是hash桶中的第一個(gè)結(jié)點(diǎn)也可以
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;
}
//在結(jié)點(diǎn)n之后插入結(jié)點(diǎn)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;
}
/*
* Move a list from one list head to another. Fixup the pprev
* reference of the first entry if it exists.
*/
static inline void hlist_move_list(struct hlist_head *old, struct hlist_head *new)
{
new->first = old->first;
if (new->first)
new->first->pprev = &new->first;
old->first = NULL;
}
//通過(guò)一個(gè)結(jié)構(gòu)體內(nèi)部一個(gè)成員的地址獲取結(jié)構(gòu)體的首地址
#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
#define hlist_for_each(pos, head)
for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; });
pos = pos->next)
#define hlist_for_each_safe(pos, n, head)
for (pos = (head)->first; pos && ({ n = pos->next; 1; });
pos = n)
/**
* hlist_for_each_entry - iterate over list of given type
* @tpos: the type * to use as a loop cursor.
* @pos: the &struct hlist_node to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry(tpos, pos, head, member)
for (pos = (head)->first;
pos && ({ prefetch(pos->next); 1;}) &&
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});
pos = pos->next)
/**
* hlist_for_each_entry_continue - iterate over a hlist continuing after current point
* @tpos: the type * to use as a loop cursor.
* @pos: the &struct hlist_node to use as a loop cursor.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry_continue(tpos, pos, member)
for (pos = (pos)->next;
pos && ({ prefetch(pos->next); 1;}) &&
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});
pos = pos->next)
/**
* hlist_for_each_entry_from - iterate over a hlist continuing from current point
* @tpos: the type * to use as a loop cursor.
* @pos: the &struct hlist_node to use as a loop cursor.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry_from(tpos, pos, member)
for (; pos && ({ prefetch(pos->next); 1;}) &&
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});
pos = pos->next)
/**
* hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
* @tpos: the type * to use as a loop cursor.
* @pos: the &struct hlist_node to use as a loop cursor.
* @n: another &struct hlist_node to use as temporary storage
* @head: the head for your list.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry_safe(tpos, pos, n, head, member)
for (pos = (head)->first;
pos && ({ n = pos->next; 1; }) &&
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});
pos = n)
