双向链表

Melon中有两个双向链表实现，读者可自行选用所需的一种。下面，我们分别进行介绍。

第一种实现

头文件

#include "mln_utils.h"

模块名

utils

函数/宏

MLN_CHAIN_FUNC_DECLARE

 MLN_CHAIN_FUNC_DECLARE(scope,prefix,type,func_attr);

描述：本宏用于对双向链表的添加操作和删除操作函数进行声明，其中：

• scope: 为函数的作用域关键字。
• prefix：为两个函数名的前缀，这是为了允许在一个源文件内为多个双向链表进行函数声明。
• type：链表节点的类型
• func_attr：对函数参数的约束（仅限于Linux中），若无则留空即可

MLN_CHAIN_FUNC_DEFINE

MLN_CHAIN_FUNC_DEFINE(scope,prefix,type,prev_ptr,next_ptr);

scope void prefix##_chain_add(type **head, type **tail, type *node);
scope void prefix##_chain_del(type **head, type **tail, type *node);

描述：本宏用于定义双向链表的添加和删除操作函数，其中：

• scope: 为函数的作用域关键字。
• prefix：为两个函数名的前缀，这是为了允许在一个源文件内为多个双向链表进行函数声明。
• type：链表节点的类型
• prev_ptr：链表节点中指向前一节点的指针名
• next_ptr：链表节点中指向后一节点的指针名

chain_add和chain_del分别为添加和删除节点函数，两个函数的参数为：

• head：二级指针，用于在操作函数内对头指针自动修改
• tail：二级指针，用于在操作函数内对尾指针自动修改
• node：被加入的节点指针，其前后指向的指针可能会被修改

示例

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

typedef struct chain_s {
  int             val;
  struct chain_s *prev;
  struct chain_s *next;
} chain_t;

MLN_CHAIN_FUNC_DECLARE(static inline, test, chain_t, );
MLN_CHAIN_FUNC_DEFINE(static inline, test, chain_t, prev, next);

int main(void)
{
  int i;
  chain_t *head = NULL, *tail = NULL, *c;

  for (i = 0; i < 10; ++i) {
    c = (chain_t *)malloc(sizeof(chain_t));
    if (c == NULL) {
        fprintf(stderr, "malloc failed.\n");
        return -1;
    }
    c->val = i;
    c->prev = c->next = NULL;
    test_chain_add(&head, &tail, c);
  }

  for (c = head; c != NULL; c = c->next) {
    printf("%d\n", c->val);
  }
  return 0;
}

第二种实现

头文件

#include "mln_list.h"

除了函数和宏以外，我们只需要知道，如果需要使用该双向链表，则需要在自定义的结构体中加入一个mln_list_t的成员（不是指针）。

模块名

list

函数/宏

mln_list_init

mln_list_init(s)

描述：初始化循环双向链表的哨兵节点s。这是推荐的初始化方式。

返回值：无

mln_list_null

mln_list_null()

描述：用于以花括号初始化器的方式初始化哨兵节点（如 mln_list_t s = mln_list_null();）。首次 mln_list_add 调用时会自动升级为循环链表结构。

返回值：无

mln_list_add

mln_list_add(sentinel, node)

描述：将结点node添加到双向链表sentinel的尾部。此为内联宏实现，性能最优。

返回值：无

mln_list_remove

mln_list_remove(sentinel, node)

描述：将结点node从双向链表sentinel中移除。此为内联宏实现，性能最优。

返回值：无

mln_list_head

mln_list_head(sentinel)

描述：获得双向链表的首结点指针。

返回值：首结点指针，若无则为NULL

mln_list_tail

 mln_list_tail(sentinel)

描述：获得双向链表的尾结点指针。

返回值：尾结点指针，若无则为NULL

mln_list_next

mln_list_next(sentinel, node)

描述：获得链表sentinel中当前结点node的下一个结点指针。

返回值：下一个结点的指针，若无则为NULL

mln_list_prev

mln_list_prev(sentinel, node)

描述：获得链表sentinel中当前结点node的前一个结点指针。

返回值：前一个结点的指针，若无则为NULL

mln_list_for_each

mln_list_for_each(node, sentinel)

描述：遍历链表中所有结点。node为mln_list_t *类型的循环变量，sentinel为哨兵节点指针。遍历期间不要删除结点，如需删除请使用mln_list_for_each_safe。

返回值：无

mln_list_for_each_safe

mln_list_for_each_safe(node, tmp, sentinel)

描述：安全地遍历链表中所有结点，支持遍历期间删除结点。node和tmp为mln_list_t *类型变量，sentinel为哨兵节点指针。

返回值：无

示例

#include "mln_list.h"
#include "mln_utils.h"
#include <stdlib.h>
#include <stdio.h>

typedef struct {
    int        val;
    mln_list_t node;
} test_t;

int main(void)
{
    int i;
    test_t *t;
    mln_list_t sentinel;
    mln_list_init(&sentinel);

    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_each 遍历 */
    mln_list_t *lnode;
    mln_list_for_each(lnode, &sentinel) {
        t = mln_container_of(lnode, test_t, node);
        printf("%d\n", t->val);
    }

    /* 安全删除遍历 */
    mln_list_t *tmp;
    mln_list_for_each_safe(lnode, tmp, &sentinel) {
        t = mln_container_of(lnode, test_t, node);
        mln_list_remove(&sentinel, &t->node);
        free(t);
    }
    return 0;
}

这里使用了mln_utils.h中定义的mln_container_of来获取链结点所属的自定义结构体test_t的指针。