分析list_head結構＆建立雙向鏈表的一種常見方法
2024-07-21 02:36:00
供稿：網友
作者：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 *)0)->member)))
list_for_each(entry,head) : 遍歷鏈表
for (entry = (head)->next; entry != (head); entry = entry->next)
========================================================
建立雙向鏈表的一種常見方法 作者：西安交通大學 王灝
========================================================
在分析內核時經常碰到以“pprev”作為尾綴的二次指針和帶有“next”尾綴的一次指針。而且在鏈表治理時使用這么一對指針。這里以網絡bind哈希表建立為例解釋（內核2.2.18）。
代碼:
struct **skp = &udp_hash[sk->num & (UDP_HTABLE_SIZE -1)]
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雙向鏈表的計算結點起始位置的宏）。這使得這種鏈表只是在鏈表建立和鏈表刪除時有雙向鏈表的效率，而查找時僅是單向鏈表的效率。但是這種鏈表通常用在哈希表中，這樣雖然查找是單向鏈表的效率，但是由于具有同一個哈希值的鏈較短，所以執行效率也非常好，而且兼有雙向鏈表的插入刪除效率。
