国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

struct hlist_head {
　　　 struct hlist_node *first;
};

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

　　這個數(shù)據(jù)結(jié)構(gòu)與一般的hash-list數(shù)據(jù)結(jié)構(gòu)定義有以下的區(qū)別:

　　1) 首先,hash的頭節(jié)點僅存放一個指針,也就是first指針,指向的是list的頭結(jié)點,沒有tail指針也就是指向list尾節(jié)點的指針,這樣的考慮是為了節(jié)省空間--尤其在hash bucket很大的情況下可以節(jié)省一半的指針空間.

　　2) list的節(jié)點有兩個指針,但是需要注意的是pprev是指針的指針,它指向的是前一個節(jié)點的next指針(見下圖).

　　現(xiàn)在疑問來了:為什么pprev不是prev也就是一個指針,用于簡單的指向list的前一個指針呢?這樣即使對于first而言,它可以將prev指針指向list的尾結(jié)點.

　　主要是基于以下幾個考慮:

　　1) hash-list中的list一般元素不多(如果太多了一般是設(shè)計出現(xiàn)了問題),即使遍歷也不需要太大的代價,同時需要得到尾結(jié)點的需求也不多.

　　2) 如果對于一般節(jié)點而言,prev指向的是前一個指針,而對于first也就是hash的第一個元素而言prev指向的是list的尾結(jié)點,那么在刪除一個元素的時候還需要判斷該節(jié)點是不是first節(jié)點進(jìn)行處理.而在hlist提供的刪除節(jié)點的API中,并沒有帶上hlist_head這個參數(shù),因此做這個判斷存在難度.

　　3) 以上兩點說明了為什么不使用prev,現(xiàn)在來說明為什么需要的是pprev,也就是一個指向指針的指針來保存前一個節(jié)點的next指針--因為這樣做即使在刪除的節(jié)點是first節(jié)點時也可以通過*pprev = next;直接修改指針的指向.來看刪除一個節(jié)點和修改list頭結(jié)點的兩個API:

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;　//此時n是hash的first指針,因此它的pprev指向的是hash的first指針的地址
}

static　inline　void　__hlist_del(struct　hlist_node　*n)
{
　　　　struct　hlist_node　*next　=　n->next;
　　　　struct　hlist_node　**pprev　=　n->pprev;
　　　　*pprev　=　next;　//　pprev指向的是前一個節(jié)點的next指針,而當(dāng)該節(jié)點是first節(jié)點時指向自己,因此兩種情況下不論該節(jié)點是一般的節(jié)點還是頭結(jié)點都可以通過這個操作刪除掉所需刪除的節(jié)點
　　　　if　(next)
　　　　　　　　next->pprev　=　pprev;
}