鏈表是基本數據結構， 一開始學習數據結構時， 我一般這么定義， 對應實現從頭或尾插入的處理函數，
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;}但是發現， 如果這么定義的話，每次實現一個list的結構， 都需要重新對應編寫處理函數， 重復輪子。
想起前段時間， 看到FreeRTOS提供的鏈表處理方式（《 FreeRTOS 任務調度 List 組織 》）， 將鏈表結構定義和實際使用時具體節點數據內容分開定義， 供系統各個模塊使用。
查看linux的源碼， 發現linux中也為我們提供了相似的實現（源碼）, 把一些共性統一起來。 類是 python 中for_each處理，有些意思。
linux 下的鏈表定義在文件 include/linux/types.h， 采用的是雙向列表
在文件list.h, 提供了一常用的接口， 根據自己的需求， 定義節點node， 建立 list 并添加節點后， 看到的組織如圖所示 ：
利用這個定義， 我定義了一個自己的list數據結構， 并copy了一些接口實現，感受下，linux 是如何管理鏈表的。
// list 節點結構定義struct int_node { int val; struct list_head list;};// 新建一個list head， 初始化其指針指向自身#define LIST_HEAD(name) / struct list_head name = {&(name), &(name)};// 將新節點插入到指定兩個節點之間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;}// 將新節點插入到鏈表頭static inline void list_add(struct list_head *new, struct list_head *head){ __list_add(new, head, head->next);}// 將新節點插入到鏈表尾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)// 已知一個結構的成員，獲取該成員所屬結構體地址#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， 可以取得我們當前正在操作鏈表所屬結構體地址，進而對具體數據進行處理， 利用c語言的一個小技巧， 把結構體投影到地址為0的地方，那么成員的絕對地址就是偏移量， 得到偏移量后，根據成員的p指針反算出結構體的首地址。 另外一種做法是定義list_head中， 包含一個成員變量，指向其所屬，FreeRTOS是如此做的。
雖然比較簡單，記錄下，學習linux 代碼， 程序員的自我修養。
新聞熱點
疑難解答
