Redis源码阅读笔记-链表结构

原创
2018/09/06 13:22
阅读数 71

链表

Redis中是自己实现的链表。链表被广泛用于Redis的各种功能,比如列表键、发布于订阅、慢查询、监视器等。

列表键的底层实现之一就是链表(Redis3.2 之前,在Redis3.2 后被换成了快速列表quicklist)。当一个列表建包含了数量比较多的元素,又或者列表中包含的元素都是比较长的字符串时,Reids会使用链表作为列表键的底层实现。(《Redis设计与实现》)

特点

来之《Redis设计与实现》

  • 每个链表结点由一个listNode结构来表示,每个结点都由一个指向前置结点和后置结点的指针,所有Redis的链表实现是双端链表。
  • 每个链表使用一个list结构来表示,这个结构带有表头结点指针、表位结点指针、已经链表长度等信息。
  • 因为链表表头结点的前置节点和表尾结点的后置节点都指向NULL,所以Redis的链表实现是无环链表。
  • 通过为链表设置不同的类型特定函数,Redis的链表可以用于保存各种不同类型的值。

代码结构

// adlist.h

// 链表结点
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;

// 链表的迭代器
typedef struct listIter {
    listNode *next; // 下一个节点
    int direction; // 迭代方向
} listIter;

  • dup函数用于复制链表节点所保存的值;
  • free函数用于释放链表节点所保存的值;
  • match函数用于对比链表节点所保存的值和另一个输入值是否相等;

部分代码解析

  • list *listAddNodeHead(list *list, void *value) 向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;
    	    // 给链表节点的value赋值
    	    node->value = value;
    
    	    if (list->len == 0) {
    	        // 如果list本来没有节点,则将表头节点和表尾节点都设置node
    	        list->head = list->tail = node;
    	        // 且node的前置和后置节点都是NULL
    	        node->prev = node->next = NULL;
    	    } else {
    	        // 如果list本来已经存在节点
    	        // 则将node的前置节点设为NULL
    	        node->prev = NULL;
    	        // 然后将node的后置节点指向list原本的表头节点
    	        node->next = list->head;
    	        // 将list原本的表头节点的前置节点指向node
    	        list->head->prev = node;
    	        // 将node设为list的新表头节点
    	        list->head = node;
    	    }
    	    // list的长度加1
    	    list->len++;
    	    return list;
    	}
    
  • list *listInsertNode(list *list, listNode *old_node, void *value, int after)向list中插入节点value,插入位置是old_nodeafter表示在old_node前还是后:

    	list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    	    listNode *node;
    
    	    // 给要插入的节点node分配内存
    	    if ((node = zmalloc(sizeof(*node))) == NULL)
    	        return NULL;
    	    // node的value赋值
    	    node->value = value;
    
    	    if (after) {
    	        // 插入到old_node后
    	        node->prev = old_node;
    	        node->next = old_node->next;
    	        if (list->tail == old_node) {
    	            // 如果old_node原本是表尾节点,则重新将表尾节点指向node
    	            list->tail = node;
    	        }
    	    } else {
    	        // 插入到old_node前
    	        node->next = old_node;
    	        node->prev = old_node->prev;
    	        if (list->head == old_node) {
    	            // 如果old_node原本是表头节点,则重新将表尾节点指向node
    	            list->head = node;
    	        }
    	    }
    	    if (node->prev != NULL) {
    	        //如果node的前置节点不为NULL,则将node的前置节点的后置节点指向node
    	        node->prev->next = node;
    	    }
    	    if (node->next != NULL) {
    	        //如果node的后置节点不为NULL,则将node的后置节点的前置节点指向node
    	        node->next->prev = node;
    	    }
    	    // list的长度加1
    	    list->len++;
    	    return list;
    	}
    
  • void listDelNode(list *list, listNode *node)删除list中的节点node

    	/* 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有前置节点
    	        // 则将 node前置节点的后置节点 指向 node的后置节点
    	        node->prev->next = node->next;
    	    else
    	        // 如果node没有前置节点,则说明node是表头节点
    	        // 将list的表头节点指向 node的后置节点
    	        list->head = node->next;
    	    if (node->next)
    	        // 如果node有后置节点
    	        // 则将 node的后置节点的前置节点 指向 node的前置节点
    	        node->next->prev = node->prev;
    	    else
    	        // 如果node没有后置节点,则说明node是表尾节点
    	        // 将list的表尾节点指向 node的前置节点
    	        list->tail = node->prev;
    
    	    // 如果list有free函数,则调用free函数释放node中的value
    	    if (list->free) list->free(node->value);
    	    // 释放node的内存
    	    zfree(node);
    	    // list长度减1
    	    list->len--;
    	}
    

链表API

参考之《Redis设计与实现》

函数 作用 时间复杂度
list *listCreate(void) 创建一个不包含任何节点的新链表 O(1)
void listRelease(list *list) 释放整个链表 O(N)
void listEmpty(list *list) 将整个链表的节点情况,不释放链表本身 O(N)
list *listAddNodeHead(list *list, void *value) 将一个包含给定值的新节点添加为链表的表头 O(1)
list *listAddNodeTail(list *list, void *value) 将一个包含给定值的新节点添加为链表的表尾 O(1)
list *listInsertNode(list *list, listNode *old_node, void *value, int after) 将一个包含给定值的新节点添加到链表给定节点的前或者后 O(1)
void listDelNode(list *list, listNode *node) 删除链表中的给定节点 O(1)
listIter *listGetIterator(list *list, int direction) 获取给定链表的迭代器 O(1)
listNode *listNext(listIter *iter) 获取链表迭代器的下一个节点 O(1)
void listReleaseIterator(listIter *iter) 释放链表迭代器 O(1)
list *listDup(list *orig) 复制一个给定链表的副本 O(N)
listNode *listSearchKey(list *list, void *key) 在给定链表中查找并返回链表中包含给定值key的节点 O(N)
listNode *listIndex(list *list, long index) 返回链表中给定索引index上的节点 O(N)
void listRewind(list *list, listIter *li) 将给定迭代器li指定给定的链表list,迭代器li指向的是链表list的表头结点 O(1)
void listRewindTail(list *list, listIter *li) 将给定迭代器li指定给定的链表list,但迭代器li指向的是链表list的表尾结点 O(1)
void listRotate(list *list) 将链表的尾结点弹出,然后将被弹出的节点插入到链表的表头,成为新的表头节点 O(1)
void listJoin(list *l, list *o) 将链表o的节点追加到链表l的表尾后,然后将o设置为空(不是NULL,而是没有节点) O(1)
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部