双端链表

适用范围

Redis 实现的是一个典型的双端链表， 这个链表具有以下特性：

1. 带有表头和表尾指针，可以在 复杂度内取得表头或者表尾节点
2. 带有节点数量变量，可以在 复杂度内取得链表的节点数量
3. 可以通过指定 dup 、 free 和 match 函数，适应多种类型的值（或结构）
4. 带有一个链表迭代器，通过这个迭代器，可以从表头向表尾或者从表尾向表头进行迭代。

准备工作

1. 从 Redis 源码中复制 adlist.c 、 adlist.h 、 zmalloc.c 和 zmalloc.h 四个文件到目标文件夹。
2. 将 zmalloc.c 中的 #include "config.h" 一行删掉。
3. 添加 #include <stddef.h> 到 zamlloc.h ，解决 size_t 未定义的问题。

测试驱动程序

以下是用作节点值的空对象：

// object.h

typedef struct { } object;

object* create_object(void);
void free_object(object* object);

// object.c

#include "zmalloc.h"
#include "object.h"

object* create_object(void)
{
    return (object*)zmalloc(sizeof(object));
}

void free_object(object* obj)
{
    zfree(obj);
}

以下程序进行了三项测试：

1. 创建一个空双端链表，并检查它的各项属性，然后释放它
2. 创建一个非空双端链表，然后用函数（宏）迭代节点，并检查它们的值
3. 创建一个非空双端链表，然后用迭代器对列表进行迭代，并检查各个节点的值

// main.c

#include <assert.h>
#include <stdlib.h>

#include "adlist.h"
#include "object.h"

void test_empty_list(void)
{
    // 创建一个新链表
    list* l = listCreate();

    // 检查表头和表尾
    assert(
        l->head == NULL &&
        l->tail == NULL
    );

    // 检查节点数量
    assert(
        l->len == 0
    );

    // 检查类型限定函数
    assert(
        l->dup == NULL &&
        l->free == NULL &&
        l->match == NULL
    );

    // 释放链表
    listRelease(l);
}


void test_add_node_and_advance_by_pointer(void)
{

    // 初始化值对象
    object *x = create_object(),
           *y = create_object(),
           *z = create_object();


    // 创建列表
    list* l = listCreate();
    // l = [x]
    listAddNodeHead(l, x);
    // l = [x, z]
    listAddNodeTail(l, z);
    // l = [x, y, z]
    listNode* node_contain_x = listSearchKey(l, x);
    listInsertNode(l, node_contain_x, y, 1);   //insert y after x


    // 手动遍历节点
    listNode* current;

    // x
    current = listFirst(l);
    assert(
        current->value == x
    );

    // y
    current = listNextNode(current);
    assert(
        current->value == y
    );

    // z
    current = listNextNode(current);
    assert(
        current->value == z
    );

    
    // 释放空间
    free_object(x);
    free_object(y);
    free_object(z);

    listRelease(l);
}


void test_iterator(void)
{
    // 初始化值对象
    object *x = create_object(),
           *y = create_object(),
           *z = create_object();


    // 创建列表
    list* l = listCreate();
    listAddNodeTail(l, x);
    listAddNodeTail(l, y);
    listAddNodeTail(l, z);


    // 从表头向表尾遍历节点
    listIter* itertor = listGetIterator(l, AL_START_HEAD);
    listNode* current;
    
    // 第一个节点
    current = listNext(itertor);
    assert(
        current->value == x
    );

    // 第二个节点
    current = listNext(itertor);
    assert(
        current->value == y
    );

    // 第三个节点
    current = listNext(itertor);
    assert(
        current->value == z
    );


    // 释放
    free_object(x);
    free_object(y);
    free_object(z);

    listRelease(l);

    listReleaseIterator(itertor);
}

void main(void)
{
    test_empty_list();

    test_add_node_and_advance_by_pointer();

    test_iterator();
}

完整源码

测试程序的完整源码可以在 这里 的 adlist 文件夹下找到。

留言

comments powered by Disqus