最近有看一點Linux內核源碼，發現內核裡大量使用了list_head結構體。百度查了一下，原來內核利用這個結構體實現了泛型。
自認為對鏈表已經很熟悉的我，決定自己實現一下。
下面以Node和list_head為例。
上圖就是循環鏈大致思路了。（畫的不好）
我們通過list_head對鏈表進行移動操作。
這裡存在幾個問題：
首先通過list_head得到的指針，它指向的list_head的結構體，但我們其實想要使用的是Node結構體。
再有，我們要設計一個泛型的鏈表，那麼，我就不可以在實現鏈表時有任何對Node的操作。
解決辦法：
1、通過計算，找到node結構體的首地址。（我們通過一個宏來實現）
1 #define list_entry(ptr, type, member) \ 2 ((type *)((char *)(ptr) - (char *)(&(((type *)0)->member))))
這個宏看起來可能點亂，但我們把思路縷清就不亂了。
我們只知道entry的指針，如何求出Node的指針呢？
如果我們可以知道entry的相對位置，那麼
Node的實際位置 = entry的實際位置 - entry的相對位置。
entry的相對位置 = (&((（Node *）0)->entry)) 又蒙了麼？ 這裡，我們先將 0轉換為（Node *)類型的指針，再用這個指針指向entry，最後取它的地址。這時我們就得到了entry的相對位置。
宏中把他們強轉成char * 是為了進行減法。最後再強轉成Node類型，這時我就得到了Node的指針。
2、讓用戶自己定義特定數據的操作，我們只提供一個函數接口（我們通過函數指針來實現）
在我們的鏈表裡，只涉及到了list_head 裡的內容，所以，不能對Node進行操作。參數也都是list_head的指針。這就需要用戶在使用時，通過上面的宏來完成從list_head 到 Node的轉換。在稍後例子中會了解到。
源碼
dclist_head.h
1 /*************************************************************************
2 > File Name: dlist_head.h
3 > Author: gaozy
4 > Mail: 44523253@qq.com
5 > Created Time: 2016年12月24日 星期六 10時11分22秒
6 ************************************************************************/
7
8 /*
9 *這是我自己實現的一個泛型循環鏈表
10 *使用者只需要把dclist_head_t 這個結構體加入到自己的結構體中就可以使用這個鏈表了。
11 *在使用時，需要使用者創建一個頭節點，之後使用init函數初始化。（當然，你也可以自己對他進行初始化操作）
12 *它很重要，否則無法使用這個鏈表。
13 *鏈表給使用者提供了四個函數
14 *init 剛剛已經說過了，我們用它初始化鏈表
15 *append 這是一個向鏈表中添加節點的函數，需要我們傳入鏈表的頭和新節點的dclist_head_t部分的指針
16 *treaverse 正如火函數名一樣，它的作用是遍歷鏈表，它需要我們提供一個函數指針
17 *這個指針的作用是對節點進行操作，參數是一個dclist_head_t 類型的指針，我們同過list_entry這個宏獲取
18 *使用者自定義的數據類型。
19 *dc_remove這個函數用來釋放鏈表，類似treaverse函數，需要我們自己實現刪除j節點函數。
20 *它會釋放鏈表中的所有節點，只有頭結點例外，頭需要我們自己釋放
21 */
22
23 #ifndef DLIST_HEAD
24 #define DLIST_HEAD
25
26 #define list_entry(ptr, type, member) \
27 ((type *)((char *)(ptr) - (char *)(&(((type *)0)->member))))
28
29 typedef struct dclist_head {
30 struct dclist_head * prev;
31 struct dclist_head * next;
32 } dclist_head_t;
33
34 void init(dclist_head_t *head);
35 void append(dclist_head_t *head, dclist_head_t *node);
36 void treaverse(dclist_head_t *head, void (*pfun)(dclist_head_t *node) );
37 void dc_remove(dclist_head_t *head, void (*pfun)(dclist_head_t *node) );
38
39 #endif
dclist_head.c
1 /*************************************************************************
2 > File Name: dclist_head.c
3 > Author: gaozy
4 > Mail: 44523253@qq.com
5 > Created Time: 2016年12月24日 星期六 10時19分49秒
6 ************************************************************************/
7
8 #include <stdio.h>
9 #include <stdlib.h>
10
11 #include "dclist_head.h"
12
13
14 void init(dclist_head_t *head)
15 {
16 if ( head != NULL ) {
17 head->prev = NULL;
18 head->next = NULL;
19 }
20 }
21
22 void append(dclist_head_t *head, dclist_head_t *node)
23 {
24 if ( head == NULL ) {
25 printf("error\n");
26 exit(1);
27 }
28
29 if ( head->prev == NULL && head->next == NULL ) {
30 head->prev = node;
31 head->next = node;
32 node->prev = head;
33 node->next = head;
34 } else {
35 dclist_head_t *tmp = head->prev;
36 tmp->next = node;
37 node->prev = tmp;
38 node->next = head;
39 head->prev = node;
40 }
41 }
42
43 void treaverse(dclist_head_t *head, void (*pfun)(dclist_head_t *node) )
44 {
45 if ( head == NULL || head->next == NULL )
46 return;
47
48 dclist_head_t *tmp = head->next;
49 while ( tmp != head ) {
50 pfun(tmp);
51 tmp = tmp->next;
52 }
53 }
54
55 void dc_remove(dclist_head_t *head, void (*pfun)(dclist_head_t *node) )
56 {
57 treaverse(head, pfun);
58 }
測試代碼
main.c
1 /*************************************************************************
2 > File Name: main.c
3 > Author: gaozy
4 > Mail: 44523253@qq.com
5 > Created Time: 2016年12月24日 星期六 11時11分25秒
6 ************************************************************************/
7
8 #include <stdio.h>
9 #include <stdlib.h>
10
11 #include "dclist_head.h"
12
13 typedef struct {
14 int id;
15 dclist_head_t entry;
16 } student_t;
17
18 void print(dclist_head_t *ptr)
19 {
20 student_t *stu = list_entry(ptr, student_t, entry);
21 if ( stu == NULL )
22 return;
23 printf("student id = %d\n", stu->id);
24 }
25
26 void free_node(dclist_head_t *ptr)
27 {
28 if (ptr == NULL )
29 return;
30
31 student_t *node = list_entry(ptr, student_t, entry);
32 free(node);
33 }
34
35 student_t* make_node(int id)
36 {
37 student_t *stu = (student_t *)malloc(sizeof(student_t));
38 if ( stu != NULL ) {
39 stu->id = id;
40 }
41
42 return stu;
43 }
44
45 int main(void)
46 {
47 dclist_head_t list;
48
49 init(&list);
50
51 int i;
52 student_t *stu;
53 for ( i=0; i<5; i++ ) {
54 stu = make_node(i);
55 if ( stu != NULL )
56 append(&list, &stu->entry);
57 }
58
59
60 treaverse(&list, print);
61 dc_remove(&list, free_node);
62
63
64 return 0;
65 }
水平有限，還請大神多多指點。
