redis-adlist源码阅读

adlist结构

typedef struct list {

    /** 表头节点 */
    listNode *head;

    /** 表尾节点 */
    listNode *tail;

    /** 节点值复制函数 */
    void *(*dup)(void *ptr);

    /** 节点值释放函数 */
    void (*free)(void *ptr);

    /** 节点值对比函数 */
    int (*match)(void *ptr, void *key);

    /** 链表所包含的节点数量 */
    unsigned long len;

} list;

typedef struct listNode {

    /** 前置节点 */
    struct listNode *prev;

    /** 后置节点 */
    struct listNode *next;

    /** 节点的值 */
    void *value;

} listNode;

双端链表修改注意事项

在进行修改（增，删）双端链表的时候需要考虑这四个方面：

1、修改当前节点的前后指针

2、修改当前节点的相邻节点的前后指针

3、判断当前节点是否是首尾节点，修改list的首尾节点指针

4、修改len值

举个例子：

如果要修改将node2，添加到node1和node3之间（添加之前试想一下只存在node1，node3，node4节点）

操作步奏：

1、将node2的prev指向node1，将node2的next指向node3

2、将node1的next指向node2，将node3的orev指向node2

3、判断不是首尾节点，如果是的话，需要将list的tail或者list的head指向node2

4.len的值加1

示例代码：
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    listNode *node;

    // 创建新节点
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;

    // 保存值
    node->value = value;

    // 将新节点添加到给定节点之后
    if (after) {
        node->prev = old_node;
        node->next = old_node->next;
        // 给定节点是原表尾节点
        if (list->tail == old_node) {
            list->tail = node;
        }
    // 将新节点添加到给定节点之前
    } else {
        node->next = old_node;
        node->prev = old_node->prev;
        // 给定节点是原表头节点
        if (list->head == old_node) {
            list->head = node;
        }
    }

    //这里需要注意的是，两个节点的连接，既要改变当前插入节点的前后节点指针，也要改变相邻节点的指针
    // 更新新节点的前置指针
    if (node->prev != NULL) {
        node->prev->next = node;
    }
    // 更新新节点的后置指针
    if (node->next != NULL) {
        node->next->prev = node;
    }

    // 更新链表节点数
    list->len++;

    return list;
}

双端链表遍历

迭代器相对来说比较简单，首先listIter定义了当前节点，和迭代方向

然后使用listNext进行节点的移动

最后使用len属性和while进行节点的循环遍历

示例代码：
typedef struct listIter {

    /** 当前迭代到的节点 */
    listNode *next;

    /** 迭代的方向 */
    int direction;

} listIter;

listNode *listNext(listIter *iter)
{
    listNode *current = iter->next;

    if (current != NULL) {
        // 根据方向选择下一个节点
        if (iter->direction == AL_START_HEAD)
            // 保存下一个节点，防止当前节点被删除而造成指针丢失
            iter->next = current->next;
        else
            // 保存下一个节点，防止当前节点被删除而造成指针丢失
            iter->next = current->prev;
    }

    return current;
}

list *listDup(list *orig)
{
    list *copy;
    listIter *iter;
    listNode *node;

    // 创建新链表
    if ((copy = listCreate()) == NULL)
        return NULL;

    // 设置节点值处理函数
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;

    // 迭代整个输入链表
    iter = listGetIterator(orig, AL_START_HEAD);
    while((node = listNext(iter)) != NULL) {
        void *value;

        // 复制节点值到新节点
        if (copy->dup) {
            value = copy->dup(node->value);
            if (value == NULL) {
                listRelease(copy);
                listReleaseIterator(iter);
                return NULL;
            }
        } else
            value = node->value;

        // 将节点添加到链表
        if (listAddNodeTail(copy, value) == NULL) {
            listRelease(copy);
            listReleaseIterator(iter);
            return NULL;
        }
    }

    // 释放迭代器
    listReleaseIterator(iter);

    // 返回副本
    return copy;
}