c语言是如何实现泛型链表

　　最近有看一点Linux内核源码，发现内核里大量使用了list_head结构体。百度查了一下，原来内核利用这个结构体实现了泛型。

　　自认为对链表已经很熟悉的我，决定自己实现一下。

　　下面以Node和list_head为例。

　　上图就是循环链大致思路了。（画的不好）

　　我们通过list_head对链表进行移动操作。

　　这里存在几个问题：

　　　　首先通过list_head得到的指针，它指向的list_head的结构体，但我们其实想要使用的是Node结构体。

　　　　再有，我们要设计一个泛型的链表，那么，我就不可以在实现链表时有任何对Node的操作。

　　解决办法：

　　　　1、通过计算，找到node结构体的首地址。（我们通过一个宏来实现）

 #define list_entry(ptr, type, member) \
     ((type *)((char *)(ptr) - (char *)(&(((type *))->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

 /*************************************************************************
     > File Name: dlist_head.h
     > Author: gaozy
     > Mail: [e-mail]
     > Created Time: 2016年12月24日 星期六 10时11分22秒
  ************************************************************************/

 /*
  *这是我自己实现的一个泛型循环链表
  *使用者只需要把dclist_head_t 这个结构体加入到自己的结构体中就可以使用这个链表了。
  *在使用时，需要使用者创建一个头节点，之后使用init函数初始化。（当然，你也可以自己对他进行初始化操作）
  *它很重要，否则无法使用这个链表。
  *链表给使用者提供了四个函数
  *init 刚刚已经说过了，我们用它初始化链表
  *append 这是一个向链表中添加节点的函数，需要我们传入链表的头和新节点的dclist_head_t部分的指针
  *treaverse 正如火函数名一样，它的作用是遍历链表，它需要我们提供一个函数指针
  *这个指针的作用是对节点进行操作，参数是一个dclist_head_t 类型的指针，我们同过list_entry这个宏获取
  *使用者自定义的数据类型。
  *dc_remove这个函数用来释放链表，类似treaverse函数，需要我们自己实现删除j节点函数。
  *它会释放链表中的所有节点，只有头结点例外，头需要我们自己释放
  */

 #ifndef DLIST_HEAD
 #define    DLIST_HEAD

 #define list_entry(ptr, type, member) \
     ((type *)((char *)(ptr) - (char *)(&(((type *))->member))))

 typedef struct dclist_head {
     struct dclist_head * prev;
     struct dclist_head * next;
 } dclist_head_t;

 void init(dclist_head_t *head);
 void append(dclist_head_t *head, dclist_head_t *node);
 void treaverse(dclist_head_t *head, void (*pfun)(dclist_head_t *node) );
 void dc_remove(dclist_head_t *head, void (*pfun)(dclist_head_t *node) );

 #endif

dclist_head.c

 /*************************************************************************
     > File Name: dclist_head.c
     > Author: gaozy
     > Mail: [e-mail]
     > Created Time: 2016年12月24日 星期六 10时19分49秒
  ************************************************************************/

 #include <stdio.h>
 #include <stdlib.h>

 #include "dclist_head.h"

 void init(dclist_head_t *head)
 {
     if ( head != NULL ) {
         head->prev = NULL;
         head->next = NULL;
     }
 }

 void append(dclist_head_t *head, dclist_head_t *node)
 {
     if ( head == NULL ) {
         printf("error\n");
         exit();
     }

     if ( head->prev == NULL && head->next == NULL ) {
         head->prev = node;
         head->next = node;
         node->prev = head;
         node->next = head;
     } else {
         dclist_head_t *tmp = head->prev;
         tmp->next = node;
         node->prev = tmp;
         node->next = head;
         head->prev = node;
     }
 }

 void treaverse(dclist_head_t *head, void (*pfun)(dclist_head_t *node) )
 {
     if ( head == NULL || head->next == NULL )
         return;

     dclist_head_t *tmp = head->next;
     while ( tmp != head ) {
         pfun(tmp);
         tmp = tmp->next;
     }
 }

 void dc_remove(dclist_head_t *head, void (*pfun)(dclist_head_t *node) )
 {
     treaverse(head, pfun);
 }

测试代码

main.c

 /*************************************************************************
     > File Name: main.c
     > Author: gaozy
     > Mail: [e-mail]
     > Created Time: 2016年12月24日 星期六 11时11分25秒
  ************************************************************************/

 #include <stdio.h>
 #include <stdlib.h>

 #include "dclist_head.h"

 typedef struct {
     int id;
     dclist_head_t entry;
 } student_t;

 void print(dclist_head_t *ptr)
 {
     student_t *stu = list_entry(ptr, student_t, entry);
     if ( stu == NULL )
         return;
     printf("student id = %d\n", stu->id);
 }

 void free_node(dclist_head_t *ptr)
 {
     if (ptr == NULL )
         return;

     student_t *node = list_entry(ptr, student_t, entry);
     free(node);
 }

 student_t* make_node(int id)
 {
     student_t *stu = (student_t *)malloc(sizeof(student_t));
     if ( stu != NULL ) {
         stu->id = id;
     }

     return stu;
 }

 int main(void)
 {
     dclist_head_t list;

     init(&list);

     int i;
     student_t *stu;
     for ( i=; i<; i++ ) {
         stu = make_node(i);
         if ( stu != NULL )
             append(&list, &stu->entry);
     }

     treaverse(&list, print);
     dc_remove(&list, free_node);

     return ;
 }

水平有限，还请大神多多指点。