c語言是如何實現泛型鏈表，c語言泛型

c語言是如何實現泛型鏈表，c語言泛型

　　最近有看一點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: [email protected] 
 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: [email protected] 
 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: [email protected] 
 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 }

水平有限，還請大神多多指點。