Redis源码剖析-链表list

谁借莪１个温暖的怀抱￠ 2022-06-08 00:21 191阅读 0赞

Redis另一个基础的数据结构是链表，C并没有内置的链表结构，因此Redis自己实现了一个列表。

除了链表键之外， 发布与订阅、慢查询、监视器等功能也用到了链表， Redis 服务器本身还使用链表来保存多个客户端的状态信息， 以及使用链表来构建客户端输出缓冲区。

## List结构 ##

双端链表结点定义如下：

typedef struct listNode {
        struct listNode *prev; // 指向前一个结点
        struct listNode *next;  // 指向后一个结点
        void *value;   // 结点值
    } listNode;

链表迭代器定义如下：

typedef struct listIter {  // 链表迭代器
        listNode *next;   // 指向下一个结点
        int direction;    // 标记迭代方向
    } listIter;

关于迭代器的方向标记，定义的全局变量用来标记：

/* Directions for iterators */
    #define AL_START_HEAD 0
    #define AL_START_TAIL 1

双端列表定义如下：

// 双端列表定义
    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;

## 链表操作 ##

### 链表初始化 ###

/* Create a new list. The created list can be freed with * AlFreeList(), but private value of every node need to be freed * by the user before to call AlFreeList(). * * On error, NULL is returned. Otherwise the pointer to the new list. */
    list *listCreate(void)
    {
        struct list *list;  // 定义链表指针
        // 分配内存，如果分配失败，返回NULL
        if ((list = zmalloc(sizeof(*list))) == NULL)
            return NULL;
        // 链表头尾初始化
        list->head = list->tail = NULL;
        // 长度赋初值
        list->len = 0;
        // 复制函数、释放函数、匹配函数初始化为NULL
        list->dup = NULL;
        list->free = NULL;
        list->match = NULL;
        return list;
    }

### 链表清空 ###

/* Remove all the elements from the list without destroying the list itself. */
    void listEmpty(list *list)
    {
        unsigned long len;
        listNode *current, *next;
    
        current = list->head;
        len = list->len;
        // 根据链表长度循环
        while(len--) {
            next = current->next;
            // 如果定义了链表释放函数，用释放函数释放结点
            if (list->free) list->free(current->value);
            zfree(current);
            current = next;
        }
        // 清空链表头尾结点及长度
        list->head = list->tail = NULL;
        list->len = 0;
    }

### 链表头部插入结点 ###

list *listAddNodeHead(list *list, void *value)
    {
        listNode *node;  // 新建链表结点
    
        if ((node = zmalloc(sizeof(*node))) == NULL)  // 初始化结点，如果失败返回NULL
            return NULL;
        // 将value赋值给结点
        node->value = value;
        if (list->len == 0) {
            // 如果是第一个结点，头尾都指向该结点，该结点前后结点都为空
            list->head = list->tail = node;
            node->prev = node->next = NULL;
        } else {
            // 否则，将结点插入到链表头部
            node->prev = NULL;
            node->next = list->head;
            list->head->prev = node;
            list->head = node;
        }
        // 链表长度加1
        list->len++;
        return list;
    }

### 往任意位置插入结点 ###

list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
        listNode *node;  // 新建结点
    
        if ((node = zmalloc(sizeof(*node))) == NULL) //分配空间，失败返回NULL
            return NULL;
        node->value = value;
        if (after) {
            // 如果有after标记，将新结点放在old_node后边；如果old_node是尾部，调整tail指向
            node->prev = old_node;
            node->next = old_node->next;
            if (list->tail == old_node) {
                list->tail = node;
            }
        } else {
            // 否则，将新结点放在old_node前边， 如果old_node是头部，调整head指向
            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;
    }

同时还提供了往链表尾部插入结点的函数，也是类似的操作。

### 结点释放函数 ###

void listDelNode(list *list, listNode *node)
    {
        if (node->prev)
            // 如果结点有前置结点，即非head结点，调整前置结点的next指向
            node->prev->next = node->next;
        else
            // 否则，是head结点，调整head结点指向
            list->head = node->next;
        if (node->next)
            // 如果结点有后置结点，即非tail结点，调整后置结点的prev指向
            node->next->prev = node->prev;
        else
            // 否则，是tail结点，调整tail结点指向
            list->tail = node->prev;
        // 如果定义了free函数，调用本身的free函数释放
        if (list->free) list->free(node->value);
        zfree(node);
        list->len--;
    }

### 获得链表的迭代器 ###

listIter *listGetIterator(list *list, int direction)
    {
        listIter *iter; // 定义迭代器指针
    
        if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;  // 分配空间，失败返回NULL
        if (direction == AL_START_HEAD)
            // 如果从头开始，迭代器的next指向head
            iter->next = list->head;
        else
            // 否则，从尾部开始，迭代器的next指向tail
            iter->next = list->tail;
        iter->direction = direction;
        return iter;
    }

### 获得迭代器的下一个结点 ###

listNode *listNext(listIter *iter)
    {
        listNode *current = iter->next; // 根据迭代器的next指针得到下一个结点
    
        if (current != NULL) {
            // 根据迭代器的方向，获得next的指向
            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;
        // 得到头结点的迭代器
        listRewind(orig, &iter);
        while((node = listNext(&iter)) != NULL) {
            void *value;
            // 如果有定义自己的复制函数，调用其进行复制
            if (copy->dup) {
                value = copy->dup(node->value);
                if (value == NULL) {
                    listRelease(copy);
                    return NULL;
                }
            } else
                // 否则，直接复制结点值
                value = node->value;
            // 将结点加入到目标的尾部
            if (listAddNodeTail(copy, value) == NULL) {
                listRelease(copy);
                return NULL;
            }
        }
        return copy;
    }

### 链表旋转 ###

其实就是将尾结点拿下来，放到头部

/* Rotate the list removing the tail node and inserting it to the head. */
    void listRotate(list *list) {
        listNode *tail = list->tail;  // 得到尾结点
    
        if (listLength(list) <= 1) return; // 如果只有一个结点，无需进行后续的操作
    
        /* Detach current tail */
        list->tail = tail->prev;  // 链表的tail指向原来tail结点的前置结点，同时置next为空
        list->tail->next = NULL;
        /* Move it as head */
        list->head->prev = tail;  // 将尾部挪下来的结点放到头部，将原来的head结点后移一个位置
        tail->prev = NULL;
        tail->next = list->head;
        list->head = tail;
    }