鏈表是我們學(xué)習(xí)C語言避不開的問題，就讓我們一起飛過去看看吧：
1 定義鏈表
鏈表是C語言編程中常用的數(shù)據(jù)結(jié)構(gòu)，比如我們要建一個(gè)整數(shù)鏈表，一般可能這么定義：
struct int_node {
int val;
struct int_node *next;
};
2 定義功能函數(shù)
為了實(shí)現(xiàn)鏈表的插入、刪除、遍歷等功能，另外要再實(shí)現(xiàn)一系列函數(shù)，比如：
void insert_node(struct int_node **head, int val);
void delete_node(struct int_node *head, struct int_node *current);
void access_node(struct int_node *head)
{
struct int_node *node;
for (node = head; node != NULL; node = node->next) {
// do something here
}
}
如果我們的代碼里只有這么一個(gè)數(shù)據(jù)結(jié)構(gòu)的話，這樣做當(dāng)然沒有問題，但是當(dāng)代碼的規(guī)模足夠大，需要管理很多種鏈表，難道需要為每一種鏈表都要實(shí)現(xiàn)一套插入、刪除、遍歷等功能函數(shù)嗎？
熟悉C++的同學(xué)可能會(huì)說，我們可以用標(biāo)準(zhǔn)模板庫(kù)啊，但是，我們這里談的是C，在C語言里有沒有比較好的方法呢？
Linux內(nèi)核中一般使用雙向鏈表，聲明為struct list_head，這個(gè)結(jié)構(gòu)體是在include/linux/types.h中定義的，鏈表的訪問是以宏或者內(nèi)聯(lián)函數(shù)的形式在include/linux/list.h中定義。
struct list_head {
struct list_head *next, *prev;
};
Linux內(nèi)核為鏈表提供了一致的訪問接口。
void INIT_LIST_HEAD(struct list_head *list)；
void list_add(struct list_head *new, struct list_head *head)；
void list_add_tail(struct list_head *new, struct list_head *head)；
void list_del(struct list_head *entry);
int list_empty(const struct list_head *head)
；
以上只是從Linux內(nèi)核里摘選的幾個(gè)常用接口，更多的定義請(qǐng)參考Linux內(nèi)核源代碼。
3 處理鏈表
我們先通過一個(gè)簡(jiǎn)單的實(shí)作來對(duì)Linux內(nèi)核如何處理鏈表建立一個(gè)感性的認(rèn)識(shí)。
#include <stdio.h>
#include "list.h"
struct int_node {
int val;
struct list_head list;
};
int main()
{
struct list_head head, *plist;
struct int_node a, b;
a.val = 2;
b.val = 3;
INIT_LIST_HEAD(&head);
list_add(&a.list, &head);
list_add(&b.list, &head);
list_for_each(plist, &head) {
struct int_node *node = list_entry(plist, struct int_node, list);
printf("val = %d\n", node->val);
}
return 0;
}
看完這個(gè)實(shí)作，是不是覺得在C代碼里管理一個(gè)鏈表也很簡(jiǎn)單呢？
代碼中包含的頭文件list.h是我從Linux內(nèi)核里抽取出來并做了一點(diǎn)修改的鏈表處理代碼，現(xiàn)附在這里給大家參考，使用的時(shí)候只要把這個(gè)頭文件包含到自己的工程里即可。
4 代碼
list_head通常是嵌在數(shù)據(jù)結(jié)構(gòu)內(nèi)使用，在上文的實(shí)作中我們還是以整數(shù)鏈表為例，int_node的定義如下：
struct int_node {
int val;
struct list_head list;
};
使用list_head組織的鏈表的結(jié)構(gòu)如下圖所示：
遍歷鏈表是用宏list_for_each來完成。
#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)
在這里，pos和head均是struct list_head。在遍歷的過程中如果需要訪問節(jié)點(diǎn)，可以用list_entry來取得這個(gè)節(jié)點(diǎn)的基址。
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
我們來看看container_of是如何實(shí)現(xiàn)的。如下圖所示，我們已經(jīng)知道TYPE結(jié)構(gòu)中MEMBER的地址，如果要得到這個(gè)結(jié)構(gòu)體的地址，只需要知道MEMBER在結(jié)構(gòu)體中的偏移量就可以了。如何得到這個(gè)偏移量地址呢？這里用到C語言的一個(gè)小技巧，我們不妨把結(jié)構(gòu)體投影到地址為0的地方，那么成員的絕對(duì)地址就是偏移量。得到偏移量之后，再根據(jù)ptr指針指向的地址，就可以很容易的計(jì)算出結(jié)構(gòu)體的地址。
list_entry就是通過上面的方法從ptr指針得到我們需要的type結(jié)構(gòu)體。
現(xiàn)在我們就從菜鳥變成不那么菜的鳥了，當(dāng)然，如果還有疑問的小伙伴可以直接聯(lián)系我，也可以加群710520381，邀請(qǐng)碼：柳貓，跟你們不見不散……
