redis源码学习之链表

曾经终败给现在 2022-07-11 05:30 175阅读 0赞

链表是经典的数据结构，redis的实现也很经典。

# 双向链表 #

redis的链表是双向链表，也就是说，每个链表节点有一个指向 前一个节点的指针和指向后一个节点的指针。另外，节点的数据域也用指针表示，这样就可以表示各种类型的数据。

typedef struct listNode {
    
        // 前置节点
        struct listNode *prev;
    
        // 后置节点
        struct listNode *next;
    
        // 节点的值
        void *value;
    
    } listNode;

但是在实际使用过程中，并不是直接使用这个结构，而是，用一个**`头节点`**来表示：

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;

这后面有三个函数指针，作用分别有点像：拷贝构造函数、析构函数、比较器。

# 宏定义 #

在redis源码中设计了一些宏定义用来对链表的头信息进行设置，类似set/get方法：

#define listLength(l) ((l)->len)
    // 返回给定链表的表头节点
    // T = O(1)
    #define listFirst(l) ((l)->head)
    // 返回给定链表的表尾节点
    // T = O(1)
    #define listLast(l) ((l)->tail)
    // 返回给定节点的前置节点
    // T = O(1)
    #define listPrevNode(n) ((n)->prev)
    // 返回给定节点的后置节点
    // T = O(1)
    #define listNextNode(n) ((n)->next)
    // 返回给定节点的值
    // T = O(1)
    #define listNodeValue(n) ((n)->value)
    
    // 将链表 l 的值复制函数设置为 m
    // T = O(1)
    #define listSetDupMethod(l,m) ((l)->dup = (m))
    // 将链表 l 的值释放函数设置为 m
    // T = O(1)
    #define listSetFreeMethod(l,m) ((l)->free = (m))
    // 将链表的对比函数设置为 m
    // T = O(1)
    #define listSetMatchMethod(l,m) ((l)->match = (m))
    
    // 返回给定链表的值复制函数
    // T = O(1)
    #define listGetDupMethod(l) ((l)->dup)
    // 返回给定链表的值释放函数
    // T = O(1)
    #define listGetFree(l) ((l)->free)
    // 返回给定链表的值对比函数
    // T = O(1)
    #define listGetMatchMethod(l) ((l)->match)

# 操作 #

看了源码之后，发现都是基本的链表操作。不过redis在迭代链表时自定义了一个迭代器结构，该结构主要包含指向下个位置的指针，和迭代方向（正向迭代还是反向迭代）。这种迭代器结构在源码中应用广泛，比如说，当我们要拷贝一个链表时：

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;
    }

# 总结 #

链表被广泛用于实现Redis的各种功能，比如列表键、发布和订阅、慢查询、监视器等，它的实现是双向链表的节点结构加上管理整个链表的头节点，相关的API都是链表操作。