作者
opera
代碼:
; include/linux/list
h
struct list_head {
struct list_head *next
*prev;
};
list_head結構用於構造雙向環形鏈表
LIST_HEAD(head) : 定義一個空表頭
struct list_head head = {&head
&head};
INIT_LIST_HEAD(head) : 初始化一個已定義的表頭;
head
>next = head;
head
>prev = head;
list_add(entry
head); 將entry添加到head之後
用於構造堆棧
head
>next
>prev = entry;
entry
>next = head
>next;
entry
>prev = head;
head
>next = entry;
list_add_tail(entry
head) : 將entry添加到head之前
用於構造隊列
head
>prev = entry;
entry
>next = head;
entry
>prev = head
>prev;
head
>prev
>next = entry;
list_del(entry) : 刪除entry
entry
>next
>prev = entry
>prev;
entry
>prev
>next = entry
>next;
list_del_init(entry) : 刪除並復位entry
entry
>next
>prev = entry
>prev;
entry
>prev
>next = entry
>next;
entry
>next = entry;
entry
>prev = entry;
list_empty(head) : 測試環形鏈表是否為空
(head
>next == head)
list_splice(list
head) : 將兩個環形鏈表合成一個大表
list
>prev
>next = head
>next;
list
>next
>prev = head;
head
>next
>prev = list
>prev;
head
>next = list
>next;
list_entry(ptr
type
member) :
如果type結構中member的地址是ptr
則返回type結構的地址
((type *)((char *)(ptr)
(unsigned long)(&((type *)
)
>member)))
list_for_each(entry
head) : 遍歷鏈表
for (entry = (head)
>next; entry != (head); entry = entry
>next)
========================================================
建立雙向鏈表的一種常見方法 作者
西安交通大學 王灏
========================================================
在分析內核時常常碰到以
pprev
作為尾綴的二次指針和帶有
next
尾綴的一次指針
而且在鏈表管理時使用這麼一對指針
這裡以網絡bind哈希表建立為例解釋（內核
）
代碼:
struct **skp = &udp_hash[sk
>num & (UDP_HTABLE_SIZE
)]
SOCKHASH_LOCK();
if((sk
>next = *skp) != NULL)
(*skp)
>pprev = &sk
>next;
請注意這裡pprev通常是指向前一個結點的next的地址
*skp = sk;
sk
>pprev =skp;
SOCKHASH_UNLOCK();
第一句賦值語句將skp指向以sk
>num為參數的哈希鏈的起始地址
而哈希數組的每一項都是指向sock結構的指針
所以* skp就是指向哈希鏈中的第一個sock結構
整個if語句完成在第一個sock結點和當前插入結點間的鏈接關系（包括前向指針和後向指針）
後面兩條語句在哈希數組項和當前插入結點之間建立鏈接關系
用這種方法這裡的鏈表通常pprev指針只在鏈表管理時（插入與刪除）使用
而在查找時僅使用next指針
也就是說這種鏈表的查找通常是單向的（pprev通常不指向結點的起始位置
若進行前向查找必須有一個類似於list_head雙向鏈表的計算結點起始位置的宏）
這使得這種鏈表只是在鏈表建立和鏈表刪除時有雙向鏈表的效率
而查找時僅是單向鏈表的效率
但是這種鏈表通常用在哈希表中
這樣雖然查找是單向鏈表的效率
但是由於具有同一個哈希值的鏈較短
所以執行效率也非常好
而且兼有雙向鏈表的插入刪除效率
From:http://tw.wingwit.com/Article/program/Oracle/201311/17725.html
