redis源码阅读-list数据结构(双向链表)

¶redis源码阅读-list数据结构(双向链表)

¶list数据结构

list底层数据结构是双向链表

¶adlist.h

/* adlist.h - A generic doubly linked list implementation
    *
    * Copyright (c) 2006-2012, Salvatore Sanfilippo <antirez at gmail dot com>
    * All rights reserved.
    *
    * Redistribution and use in source and binary forms, with or without
    * modification, are permitted provided that the following conditions are met:
    *
    *   * Redistributions of source code must retain the above copyright notice,
    *     this list of conditions and the following disclaimer.
    *   * Redistributions in binary form must reproduce the above copyright
    *     notice, this list of conditions and the following disclaimer in the
    *     documentation and/or other materials provided with the distribution.
    *   * Neither the name of Redis nor the names of its contributors may be used
    *     to endorse or promote products derived from this software without
    *     specific prior written permission.
    *
    * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
    * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    * POSSIBILITY OF SUCH DAMAGE.
    */
#ifndef __ADLIST_H__
#define __ADLIST_H__
/* Node, List, and Iterator are the only data structures used currently. */
// 双向链表节点
typedef struct listNode {
    struct listNode *prev; // 前向指针
    struct listNode *next; // 后向指针
    void *value; // 节点值
} listNode; // 结构自定义名
// 列表迭代器
typedef struct listIter {
    listNode *next; // 迭代下一个节点
    int direction; // 迭代方向
} listIter;
// 列表(这个结构体是c++类的雏形，下面的三个函数指针就是类方法，而其他的变量就是类变量)
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;
/* Functions implemented as macros */
/**** 被定义为宏的函数实现 ****/
// 对list结构的操作,输入的"l"是list类型
#define listLength(l) ((l)->len) // 获取列表长度
#define listFirst(l) ((l)->head) // 获取列表头结点
#define listLast(l) ((l)->tail) // 获取列表尾节点
// 对listNode结构的操作,输入的"n"是listNode类型
#define listPrevNode(n) ((n)->prev) // 列表节点前指针
#define listNextNode(n) ((n)->next) // 列表节点后指针
#define listNodeValue(n) ((n)->value) // 列表节点值
//对list结构中的函数进行的操作，就像c++中的set函数. "l"是list类型。
// "m"是一个*(*dup)(void *ptr)类型的函数，在这里被回调
#define listSetDupMethod(l,m) ((l)->dup = (m)) // 设置列表复制函数
#define listSetFreeMethod(l,m) ((l)->free = (m)) // 设置释放列表内存函数
#define listSetMatchMethod(l,m) ((l)->match = (m)) // 设置匹配列表函数
// 对list结构中的函数的get操作,"l"是list结构
#define listGetDupMethod(l) ((l)->dup) // 获取列表的复制函数
#define listGetFree(l) ((l)->free) // 获取列表的释放内存函数
#define listGetMatchMethod(l) ((l)->match) // 获取列表的匹配函数
/* Prototypes */
// 函数原型
list *listCreate(void);  // 列表创建函数
void listRelease(list *list); // 列表释放函数
void listEmpty(list *list); // 清空列表
list *listAddNodeHead(list *list, void *value); // 增加列表头结点
list *listAddNodeTail(list *list, void *value); // 增加列表尾节点
list *listInsertNode(list *list, listNode *old_node, void *value, int after); // 增加列表普通节点
void listDelNode(list *list, listNode *node); // 删除列表节点
listIter *listGetIterator(list *list, int direction); // 获取列表迭代器
listNode *listNext(listIter *iter); // 通过列表迭代器获取列表的下一个节点
void listReleaseIterator(listIter *iter); // 释放列表迭代器
list *listDup(list *orig); // 复制列表
listNode *listSearchKey(list *list, void *key); // 通过key值搜索列表中匹配的节点
listNode *listIndex(list *list, long index); // 通过列表索引获取列表匹配的节点
void listRewind(list *list, listIter *li); // 初始化迭代器(重置迭代器)，也就是将迭代器充值到开始位置，重新迭代
void listRewindTail(list *list, listIter *li); // 将迭代器重置的末尾重新迭代
void listRotate(list *list); // 按方向旋转列表(将头变为尾，将尾变为头)
void listJoin(list *l, list *o); // 将一个列表加入一个列表
/* Directions for iterators */
// 列表方向
#define AL_START_HEAD 0 // 从头遍历
#define AL_START_TAIL 1 // 从尾遍历
#endif /* __ADLIST_H__ */

¶adlist.c

/* adlist.c - A generic doubly linked list implementation
    *
    * Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com>
    * All rights reserved.
    *
    * Redistribution and use in source and binary forms, with or without
    * modification, are permitted provided that the following conditions are met:
    *
    *   * Redistributions of source code must retain the above copyright notice,
    *     this list of conditions and the following disclaimer.
    *   * Redistributions in binary form must reproduce the above copyright
    *     notice, this list of conditions and the following disclaimer in the
    *     documentation and/or other materials provided with the distribution.
    *   * Neither the name of Redis nor the names of its contributors may be used
    *     to endorse or promote products derived from this software without
    *     specific prior written permission.
    *
    * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
    * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    * POSSIBILITY OF SUCH DAMAGE.
    */
#include <stdlib.h>
#include "adlist.h" // 提供列表结构和操作列表的函数原型
#include "zmalloc.h" // 提供操作内存的函数原型
/* 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; // 创建一个列表结构
    if ((list = zmalloc(sizeof(*list))) == NULL) // 为列表结构分配初始内存
        return NULL;
    // 初始化列表结构中的各个元素
        list->head = list->tail = NULL; 
        list->len = 0;
        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; // 将列表长度赋值给len
        while(len--) {
            next = current->next; // 下一个节点指向当前节点的下一个节点
            if (list->free) list->free(current->value); // 如果free函数指针返回不为空，表示有内存需要释放，通过节点值释放节点
            zfree(current);// 释放当前节点所占内存
            current = next; // 将当前节点指向下一个节点
        }
        list->head = list->tail = NULL; // 当头节点和尾节点之间的节点都释放完毕，就将头节点和尾节点置NULL
        list->len = 0; // 列表长度置0
        // 此时保留列表结构
    }
        /* Free the whole list.
        *
        * This function can't fail. */
    // 释放整个列表，列表元素和列表结构一起释放
    void listRelease(list *list)
    {
        listEmpty(list); // 释放列表元素
        zfree(list); // 释放列表结构
    }
        /* Add a new node to the list, to head, containing the specified 'value'
        * pointer as value.
        *
        * On error, NULL is returned and no operation is performed (i.e. the
        * list remains unaltered).
        * On success the 'list' pointer you pass to the function is returned. */
        // 从头插入新节点(将新节点作为头节点)
    list *listAddNodeHead(list *list, void *value)
    {
        listNode *node;
            // 为新节点分配内存空间
        if ((node = zmalloc(sizeof(*node))) == NULL)
            return NULL;
        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; // 然后让现在的列表头指针指向新节点，让新节点成为头节点
        }
        list->len++;
        return list;
    }
        /* Add a new node to the list, to tail, containing the specified 'value'
        * pointer as value.
        *
        * On error, NULL is returned and no operation is performed (i.e. the
        * list remains unaltered).
        * On success the 'list' pointer you pass to the function is returned. */
        // 从尾加入节点
    list *listAddNodeTail(list *list, void *value)
    {
        listNode *node;
            if ((node = zmalloc(sizeof(*node))) == NULL)
            return NULL;
        node->value = value;
        if (list->len == 0) {
            list->head = list->tail = node;
            node->prev = node->next = NULL;
        } else {
            node->prev = list->tail;
            node->next = NULL;
            list->tail->next = node;
            list->tail = node;
        }
        list->len++;
        return list;
    }
        // 在列表中间新增节点(默认是向指定节点的后方添加节点)
    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;
        }
                /* Remove the specified node from the specified list.
            * It's up to the caller to free the private value of the node.
            *
            * This function can't fail. */
        // 从列表中删除节点
        void listDelNode(list *list, listNode *node)
        {
            if (node->prev) // 如果删除节点的前指针不为空，表示删除节点不是头节点
                node->prev->next = node->next; // 则将删除节点前指针指向的节点的后指针指向删除节点的下一个节点
            else
                list->head = node->next;
            if (node->next) // 如果删除节点不是尾节点
                node->next->prev = node->prev; // 将删除节点的后指针指向的节点的前指针指向删除节点的上一个节点
            else
                list->tail = node->prev;
            if (list->free) list->free(node->value); // 如果列表中的释放内存函数返回值不为空，表示需要释放内存，首先释放节点值内存
            zfree(node); // 然后释放节点结构内存
            list->len--;
        }
                /* Returns a list iterator 'iter'. After the initialization every
            * call to listNext() will return the next element of the list.
            *
            * This function can't fail. */
        // 获取列表迭代器(自定义迭代方向)
        listIter *listGetIterator(list *list, int direction)
        {
            listIter *iter;
                    // 先分配为迭代器分配内存
            if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
            if (direction == AL_START_HEAD) // 如果是从头开始
                iter->next = list->head; // 将迭代器的后指针(指向需要迭代的一个节点)指向列表的头节点，从头开始迭代
            else
                iter->next = list->tail;
            iter->direction = direction; // 这里为迭代器定义迭代方向
            return iter;
        }
                /* Release the iterator memory */
        // 释放迭代器内存
        void listReleaseIterator(listIter *iter) {
            zfree(iter);
        }
                /* Create an iterator in the list private iterator structure */'
        // 在列表私有迭代器结构中创建迭代器
                // 重置迭代器游标，默认重置到头节点，并从头节点开始遍历
        void listRewind(list *list, listIter *li) {
            li->next = list->head;
            li->direction = AL_START_HEAD;
        }
                // 重置迭代器游标到尾节点，并从尾节点开始遍历
        void listRewindTail(list *list, listIter *li) {
            li->next = list->tail;
            li->direction = AL_START_TAIL;
        }
                /* Return the next element of an iterator.
            * It's valid to remove the currently returned element using
            * listDelNode(), but not to remove other elements.
            *
            * The function returns a pointer to the next element of the list,
            * or NULL if there are no more elements, so the classical usage patter
            * is:
            *
            * iter = listGetIterator(list,<direction>);
            * while ((node = listNext(iter)) != NULL) {
            *     doSomethingWith(listNodeValue(node));
            * }
            *
            * */
        // 通过迭代器获取下一个元素
        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; 
            }
                        /* Duplicate the whole list. On out of memory NULL is returned.
                * On success a copy of the original list is returned.
                *
                * The 'Dup' method set with listSetDupMethod() function is used
                * to copy the node value. Otherwise the same pointer value of
                * the original node is used as value of the copied node.
                *
                * The original list both on success or error is never modified. */
            // 复制整个列表
            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;
            }
                        /* Search the list for a node matching a given key.
                * The match is performed using the 'match' method
                * set with listSetMatchMethod(). If no 'match' method
                * is set, the 'value' pointer of every node is directly
                * compared with the 'key' pointer.
                *
                * On success the first matching node pointer is returned
                * (search starts from head). If no matching node exists
                * NULL is returned. */
            // 通过列表值搜索列表节点
            listNode *listSearchKey(list *list, void *key)
            {
                listIter iter;
                listNode *node;
                            listRewind(list, &iter); // 先重置迭代器游标到头节点
                while((node = listNext(&iter)) != NULL) {
                    if (list->match) {
                        if (list->match(node->value, key)) {
                            return node;
                        }
                    } else {
                        if (key == node->value) {
                            return node;
                        }
                    }
                }
                return NULL;
            }
                        /* Return the element at the specified zero-based index
                * where 0 is the head, 1 is the element next to head
                * and so on. Negative integers are used in order to count
                * from the tail, -1 is the last element, -2 the penultimate
                * and so on. If the index is out of range NULL is returned. */
            // 通过索引搜索列表节点(从头节点开始是0,1,2,...;从尾开始则是-1,-2,-3...)
            listNode *listIndex(list *list, long index) {
                listNode *n;
                            if (index < 0) { // 如果从尾开始索引
                    index = (-index)-1; // 相当于i++
                    n = list->tail; // 搜寻节点的初始值是尾节点
                    while(index-- && n) n = n->prev; // index初始大小表名需要遍历多少个节点才能找到
                } else {
                    n = list->head;
                    while(index-- && n) n = n->next;
                }
                return n;
            }
                        /* 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;
                list->tail->next = NULL;
                /* Move it as head */
                list->head->prev = tail;
                tail->prev = NULL;
                tail->next = list->head;
                list->head = tail;
            }
                        /* Add all the elements of the list 'o' at the end of the
                * list 'l'. The list 'other' remains empty but otherwise valid. */
            // 将列表o的元素加入列表l的末尾
            void listJoin(list *l, list *o) {
                            // 1和3只能存在一个如果头节点有值，则与头节点对接，如果只有尾节点，则与尾节点对接
                            /**************************************************
                    前提是两个链表结构都存在
                ***************************************************/
                // 1. 先让o列表与l列表建立关系
                if (o->head) // 如果列表o存在
                    o->head->prev = l->tail; // 列表o的头节点的前指针指向列表l的尾节点
                                    // 2. 让l列表与o列表建立关系
                    if (l->tail) // 如果列表l的尾节点存在
                        l->tail->next = o->head; // 列表l的尾节点的后指针指向列表o的头节点
                    else // 如果尾节点为空，表示l没有元素
                        l->head = o->head; // 使得列表l头节点就是列表o的头节点，也就是新的列表l就是列表o
                                        // 3. 如果o头节点为空,只有尾节点
                    if (o->tail) l->tail = o->tail; // 上面我们已经判断了
                    l->len += o->len;
                                    /* Setup other as an empty list. */
                    o->head = o->tail = NULL;
                    o->len = 0;
                }