开源C语言库Melon双向链表使用

　　本篇主要介绍开源C语言库Melon的双向链表使用，对开源C库感兴趣的读者可以访问：
　　github.com/Water-Melon/Melon。链表简介
　　先简单介绍一下什么是双向链表。可以参考下图：
　　简单来说，链表是将一个一个的结点，通过指针连接起来。而双向链表则是每一个结点不仅记录了指向下一结点的指针，也记录了指向前一结点的指针。
　　Melon中的双向链表属于上图中带有尾部结点的双向链表。
　　双向链表的优势：结点的插入和删除操作的时间复杂度为O(1)，所以应对频繁插入和删除的场景，是非常适合的。双向链表使用
　　我们先定义一个自定义结构体类型：typedef struct test_s {     int val; } test_t;
　　后续的介绍中，我们要做的就是使用Melon的链表组件对这个结构进行改造，将其构建成一个双向链表。
　　在Melon中，双向链表有两种实现。两种实现进行对比也各有其特点，因此读者在了解各自特点后，可根据自己需要进行选择使用。第一种实现
　　我们直接上代码，然后再进行说明：#include  #include  #include ＂mln_defs.h＂  typedef struct test_s {     int val;     struct test_s *prev;     struct test_s *next; } test_t;  MLN_CHAIN_FUNC_DECLARE(test, test_t, static inline void, ); MLN_CHAIN_FUNC_DEFINE(test, test_t, static inline void, prev, next);  int main(void) {   int i;   test_t *head = NULL, *tail = NULL, *t;    for (i = 0; i < 10; ++i) {     t = (test_t *)malloc(sizeof(test_t));     if (t == NULL) {         fprintf(stderr, ＂malloc failed. ＂);         return -1;     }     t->val = i;     t->prev = t->next = NULL;     test_chain_add(&head, &tail, t);   }    for (t = head; t != NULL; t = t->next) {     printf(＂%d ＂, t->val);   }   return 0; }
　　这段代码中，main函数中的内容很简单，利用一个for循环，malloc10个test_t结构，然后将其val填充数值。随后利用test_chain_add函数将这些结点连成一个链表。然后利用for循环遍历结点并打印val的值。
　　下面问题就来了，test_chain_add哪里来的？
　　我们看到main前有两个MLN_CHAIN_FUNC_xxx的宏，这两个宏是在Melon的mln_defs.h头文件中定义的，用来对链表的插入和删除函数进行定义和声明的。MLN_CHAIN_FUNC_DECLARE第一个参数：函数名前缀第二个参数：自定义结构体类型第三个参数：函数返回值及函数类型第四个参数：函数参数限制属性（本例没有使用）MLN_CHAIN_FUNC_DEFINE第一个参数：函数名前缀第二个参数：自定义结构体类型第三个参数：函数返回值及函数类型第四个参数：自定义结构中用于访问前一结点的指针成员名字第五个参数：自定义结构中用于访问下一结点的指针成员名字
　　这两个宏会定义和声明两个函数，分别名为：test_chain_add和test_chain_del，这两个函数的原型类似如下形式：void (*chain_op)(type **head, type **tail, type *node);
　　第一个参数为双向链表首指针的指针，第二个参数为双向链表尾指针的指针，第三个参数为要被操作的结点指针。特点
　　这种实现方案的好处是：插入和删除函数可以被定义成inline或者增加一些其他属性。并且在遍历链表时，只需要访问自定义结点的prev和next指针即可。
　　缺点是：使用者需要知道自定义结构中自己加入的prev和next成员名字，以及如果定义了很多双向链表，则需要配套定义很多插入和删除函数，会增加可执行程序的体积。第二种实现
　　这种实现可能比较常见了。我们直接看代码：#include ＂mln_list.h＂ #include ＂mln_defs.h＂ #include   typedef struct {     int        val;     mln_list_t node; } test_t;  int main(void) {     int i;     test_t *t;     mln_list_t sentinel = mln_list_null();      for (i = 0; i < 3; ++i) {         t = (test_t *)calloc(1, sizeof(*t));         if (t == NULL)             return -1;         mln_list_add(&sentinel, &t->node);         t->val = i;     }     for (t = mln_container_of(mln_list_head(&sentinel), test_t, node);           t != NULL;           t = mln_container_of(mln_list_next(&t->node), test_t, node))     {         printf(＂%d ＂, t->val);     }     return 0; }
　　主函数的行为与第一种实现的代码是完全一样的。差别在于如下几方面：引入了mln_list.h头文件test_t中不再是添加prev和next成员，而是加入一个固定类型的成员，即mln_list_t类型的node成员。双向链表的首尾指针改为了一个名叫sentinel的mln_list_t类型变量。链表插入函数不再是自定义前缀函数，而是一个固定名称的函数名为mln_list_add.访问链表首结点使用mln_list_head宏想获取链表结点所在的宿主结构（即本例的test_t）指针，需要使用mln_defs.h中的mln_container_of宏。特点
　　这种实现的优劣分别是：
　　优势：使用者不需要关心链表的具体实现细节，只需要在自定义类型中引入mln_list_t类型成员即可。并且函数的插入和删除操作都是固定名称的，分别为：mln_list_add和mln_list_remove。
　　劣势：对链表结点所属的宿主结点（test_t）的访问需要借助mln_container_of宏，这看上去并不如第一种实现中那么直观。且链表操作函数都是非inline的，因此频繁调用的开销会高于第一种实现。
　　事实上，感兴趣的读者可能会发现，第二种双向链表（mln_list.c），是使用第一种双向链表来实现的。结语
　　感谢阅读，感兴趣的读者可以访问Melon库查看更多细节，Melon是一个无依赖且开箱即用的开源C语言库，并且有配套的中英文文档。
　　Github传送门：
　　github.com/Water-Melon/Melon