[舊文]list_head 的用法

三年前寫的文章
有機會再來討論一下這個好玩的東西


引言回覆
發表 list_head 的用法
在 linux kernel 之中做double link list 時有個東西實在是又好用，又強大，速度又快。
那就是 list head
其實這個東西和我們在資料結構中學的沒兩樣。
只是這個玩意運用了 struct 的結構性，及 C 語言本身的低階能力，使得速度變得很快。

struct list_head {
　struct list_head *prev,*next;
};

他的內容只有 list_head 的 兩個 pointer.也只能指 list_head
在運用時，有個 macro 叫
list_entry

他可以以 list_head 的位址，及這個 list_head 在物件中的位址，算出物件的位址。
也就是說，假設有一個物件叫 ABC 以下是內容：

struct ABC {
　int index;
　char *name;
　int score;
　struct list_head lh;
}

如果你今天拿到一個 ABC物件中的 lh 的位址(lhpt)的話，你就可以從這裏拿到該物件的位址。
e.q. struct ABC *abc = list_entry(lhpt, struct ABC,lh);
如此，list_head 就會依 lh 在 ABC 的相對位置，及 lhpt 的位址算出 這個 ABC 的位址。

當有 list_head 的物件被 allocate 出來時，要記得初始化 prev 和 next
e.q. INIT_LIST_HEAD(&abc->lh);

加入串列中的用法是
list_add(&abc->lh,head);
or
list_add_tail(&abc->lh,head);

刪除是
list_del(&abc->lh);
但是，有一點一定要記得 list_del 不會清掉 abc->lh 的內容
但是會清掉 abc->lh->prev 的 next 和 abc->lh->next 的 prev
如果要清得乾淨一點，就要用 list_del_init(&abc->lh);
那就會 abc->lh->prev == abc->lh->next==&abc->lh

--
會不會寫得太難懂啦 ~_~

星期五 二月 20, 2004 8:18 am