鏈表是基本數(shù)據(jù)結(jié)構(gòu)， 一開始學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)朦佩， 我一般這么定義并思， 對(duì)應(yīng)實(shí)現(xiàn)從頭或尾插入的處理函數(shù)，
struct int_node_old {
int val;
struct int_node_old *next;
};
void old_list_insert(struct int_node_old *head, struct int_node_old *new)
{
new->next = head->next;
head->next = new;
}
void old_list_insert_tail(struct int_node_old *head, struct int_node_old *new)
{
struct int_node_old *list = head;
for (; list->next != NULL; list = list->next);
list->next = new;
new->next = NULL;
}
但是發(fā)現(xiàn)语稠， 如果這么定義的話宋彼，每次實(shí)現(xiàn)一個(gè)list的結(jié)構(gòu)， 都需要重新對(duì)應(yīng)編寫處理函數(shù)仙畦， 重復(fù)輪子输涕。
想起前段時(shí)間， 看到FreeRTOS提供的鏈表處理方式（《 FreeRTOS 任務(wù)調(diào)度 List 組織 》）慨畸， 將鏈表結(jié)構(gòu)定義和實(shí)際使用時(shí)具體節(jié)點(diǎn)數(shù)據(jù)內(nèi)容分開定義莱坎， 供系統(tǒng)各個(gè)模塊使用。
查看linux的源碼寸士， 發(fā)現(xiàn)linux中也為我們提供了相似的實(shí)現(xiàn)（源碼）, 把一些共性統(tǒng)一起來檐什。 類是 python 中for_each處理，有些意思弱卡。
linux 下的鏈表定義在文件 include/linux/types.h乃正， 采用的是雙向列表
struct list_head {
struct list_head *next, *prev;
};
在文件list.h, 提供了一常用的接口，
根據(jù)自己的需求婶博， 定義節(jié)點(diǎn)node瓮具， 建立 list 并添加節(jié)點(diǎn)后， 看到的組織如圖所示 ：
利用這個(gè)定義凡蜻， 我定義了一個(gè)自己的list數(shù)據(jù)結(jié)構(gòu)搭综， 并copy了一些接口實(shí)現(xiàn)，感受下划栓，linux 是如何管理鏈表的兑巾。
// list 節(jié)點(diǎn)結(jié)構(gòu)定義
struct int_node {
int val;
struct list_head list;
};
// 新建一個(gè)list head， 初始化其指針指向自身
#define LIST_HEAD(name) \
struct list_head name = {&(name), &(name)};
// 將新節(jié)點(diǎn)插入到指定兩個(gè)節(jié)點(diǎn)之間
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
// 將新節(jié)點(diǎn)插入到鏈表頭
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
// 將新節(jié)點(diǎn)插入到鏈表尾
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
// 正序遍歷宏忠荞，
#define list_for_each(pos, head) \
for ((pos) = (head)->next; (pos) != (head); (pos) = (pos)->next)
// 逆序遍歷宏
#define list_for_each_prev(pos, head) \
for ((pos) = (head)->prev; (pos) != (head); (pos) = (pos)->prev)
// 已知一個(gè)結(jié)構(gòu)的成員蒋歌，獲取該成員所屬結(jié)構(gòu)體地址
#define container_of(ptr, type, menber) \
(type *)((char*)ptr - (char*) &(((type *)0)->menber))
#define list_entry(ptr, type, menber) container_of(ptr, type, menber)
通過 container_of帅掘， 可以取得我們當(dāng)前正在操作鏈表所屬結(jié)構(gòu)體地址，進(jìn)而對(duì)具體數(shù)據(jù)進(jìn)行處理堂油， 利用c語言的一個(gè)小技巧修档， 把結(jié)構(gòu)體投影到地址為0的地方，那么成員的絕對(duì)地址就是偏移量府框， 得到偏移量后吱窝，根據(jù)成員的p指針反算出結(jié)構(gòu)體的首地址。 另外一種做法是定義list_head中迫靖， 包含一個(gè)成員變量院峡，指向其所屬，F(xiàn)reeRTOS是如此做的系宜。
int main(void)
{
LIST_HEAD(my_list);
struct int_node a, b, c;
a.val = 1;
b.val = 2;
c.val = 3;
list_add(&(a.list), &my_list);
list_add(&(b.list), &my_list);
list_add_tail(&(c.list), &my_list);
struct list_head *plist;
struct int_node *pnode;
list_for_each(plist, &my_list) {
pnode = list_entry(plist, struct int_node, list);
printf("%d ", pnode->val);
}
printf("\n");
list_for_each_prev(plist, &my_list) {
pnode = list_entry(plist, struct int_node, list);
printf("%d ", pnode->val);
}
printf("\n");
return 0;
}
雖然比較簡單照激，記錄下，學(xué)習(xí)linux 代碼盹牧， 程序員的自我修養(yǎng)俩垃。
