redis源码学习_链表

redis的链表是双向链表,该链表不带头结点,具体如下:

主要总结一下adlist.c和adlist.h里面的关键结构体和函数。

链表节点结构如下:

 1 /*
 2  * 双端链表节点
 3  */
 4 typedef struct listNode {
 5
 6     // 前置节点
 7     struct listNode *prev; //如果是list的头结点,则prev指向NULL
 8
 9     // 后置节点
10     struct listNode *next;//如果是list尾部结点,则next指向NULL
11
12     // 节点的值
13     void *value;
14
15 } listNode;

链表结构如下:

 1 /*
 2  * 双端链表结构
 3  */
 4 typedef struct list {
 5
 6     // 表头节点
 7     listNode *head;
 8
 9     // 表尾节点
10     listNode *tail;
11
12     // 节点值复制函数
13     void *(*dup)(void *ptr);
14
15     // 节点值释放函数
16     void (*free)(void *ptr);
17
18     // 节点值对比函数
19     int (*match)(void *ptr, void *key);
20
21     // 链表所包含的节点数量,有了这个我们获得链表长度的时间复杂度就是O(1)了
22     unsigned long len;
23
24 } list;

链表迭代器的结构如下:

 1 /*
 2  * 双端链表迭代器
 3  */
 4 typedef struct listIter {
 5
 6     // 当前迭代到的节点
 7     listNode *next;
 8
 9     // 迭代的方向
10     int direction; //取值AL_START_HEAD等
11
12 } listIter;

里面涉及的函数中,增、删的比较简单,就是结构里面没有带头结点,所以需要单独判断一下头结点的特殊情况。另外对于尾节点的操作也需要考虑一下特殊情况。

listAddNodeHead:将一个包含给定值的新节点添加到给定链表的表头

 1 /* Add a new node to the list, to head, contaning the specified ‘value‘
 2  * pointer as value.
 3  *
 4  * On error, NULL is returned and no operation is performed (i.e. the
 5  * list remains unaltered).
 6  * On success the ‘list‘ pointer you pass to the function is returned. */
 7 /*
 8  * 将一个包含有给定值指针 value 的新节点添加到链表的表头
 9  *
10  * 如果为新节点分配内存出错,那么不执行任何动作,仅返回 NULL
11  *
12  * 如果执行成功,返回传入的链表指针
13  *
14  * T = O(1)
15  */
16 list *listAddNodeHead(list *list, void *value)
17 {
18     listNode *node;
19
20     // 为节点分配内存
21     if ((node = zmalloc(sizeof(*node))) == NULL)
22         return NULL;
23
24     // 保存值指针
25     node->value = value;
26
27     // 添加节点到空链表
28     if (list->len == 0) {
29         list->head = list->tail = node;
30         node->prev = node->next = NULL;
31     // 添加节点到非空链表
32     } else {
33         node->prev = NULL;
34         node->next = list->head;
35         list->head->prev = node;
36         list->head = node;
37     }
38
39     // 更新链表节点数
40     list->len++;
41
42     return list;
43 }

listAddNodeTail:将一个包含给定值的新节点添加到给定链表的表尾

 1 /* Add a new node to the list, to tail, containing the specified ‘value‘
 2  * pointer as value.
 3  *
 4  * On error, NULL is returned and no operation is performed (i.e. the
 5  * list remains unaltered).
 6  * On success the ‘list‘ pointer you pass to the function is returned. */
 7 /*
 8  * 将一个包含有给定值指针 value 的新节点添加到链表的表尾
 9  *
10  * 如果为新节点分配内存出错,那么不执行任何动作,仅返回 NULL
11  *
12  * 如果执行成功,返回传入的链表指针
13  *
14  * T = O(1)
15  */
16 list *listAddNodeTail(list *list, void *value)
17 {
18     listNode *node;
19
20     // 为新节点分配内存
21     if ((node = zmalloc(sizeof(*node))) == NULL)
22         return NULL;
23
24     // 保存值指针
25     node->value = value;
26
27     // 目标链表为空
28     if (list->len == 0) {
29         list->head = list->tail = node;
30         node->prev = node->next = NULL;
31     // 目标链表非空
32     } else {
33         node->prev = list->tail;
34         node->next = NULL;
35         list->tail->next = node;
36         list->tail = node;
37     }
38
39     // 更新链表节点数
40     list->len++;
41
42     return list;
43 }

listInsertNode:将一个包含给定值的新节点添加到给定节点的之前或者之后

 1 /*
 2  * 创建一个包含值 value 的新节点,并将它插入到 old_node 的之前或之后
 3  *
 4  * 如果 after 为 0 ,将新节点插入到 old_node 之前。
 5  * 如果 after 为 1 ,将新节点插入到 old_node 之后。
 6  *
 7  * T = O(1)
 8  */
 9 list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
10     listNode *node;
11
12     // 创建新节点
13     if ((node = zmalloc(sizeof(*node))) == NULL)
14         return NULL;
15
16     // 保存值
17     node->value = value;
18
19     // 将新节点添加到给定节点之后
20     if (after) {
21         node->prev = old_node;
22         node->next = old_node->next;
23         // 给定节点是原表尾节点
24         if (list->tail == old_node) {
25             list->tail = node;
26         }
27     // 将新节点添加到给定节点之前
28     } else {
29         node->next = old_node;
30         node->prev = old_node->prev;
31         // 给定节点是原表头节点
32         if (list->head == old_node) {
33             list->head = node;
34         }
35     }
36
37     // 更新新节点的前置指针
38     if (node->prev != NULL) {
39         node->prev->next = node;
40     }
41     // 更新新节点的后置指针
42     if (node->next != NULL) {
43         node->next->prev = node;
44     }
45
46     // 更新链表节点数
47     list->len++;
48
49     return list;
50 }

listDelNode:从链表中删除给定节点

 1 /* Remove the specified node from the specified list.
 2  * It‘s up to the caller to free the private value of the node.
 3  *
 4  * This function can‘t fail. */
 5 /*
 6  * 从链表 list 中删除给定节点 node
 7  *
 8  * 对节点私有值(private value of the node)的释放工作由调用者进行。
 9  *
10  * T = O(1)
11  */
12 void listDelNode(list *list, listNode *node)
13 {
14     // 调整前置节点的指针
15     if (node->prev)
16         node->prev->next = node->next;
17     else
18         list->head = node->next;
19
20     // 调整后置节点的指针
21     if (node->next)
22         node->next->prev = node->prev;
23     else
24         list->tail = node->prev;
25
26     // 释放值
27     if (list->free) list->free(node->value);
28
29     // 释放节点
30     zfree(node);
31
32     // 链表数减一
33     list->len--;
34 }

listGetIterator:创建一个链表迭代器,并根据传入的direction来返回链表的头或尾节点

 1 /* Returns a list iterator ‘iter‘. After the initialization every
 2  * call to listNext() will return the next element of the list.
 3  *
 4  * This function can‘t fail. */
 5 /*
 6  * 为给定链表创建一个迭代器,
 7  * 之后每次对这个迭代器调用 listNext 都返回被迭代到的链表节点
 8  *
 9  * direction 参数决定了迭代器的迭代方向:
10  *  AL_START_HEAD :从表头向表尾迭代
11  *  AL_START_TAIL :从表尾想表头迭代
12  *
13  * T = O(1)
14  */  //获取列表list的首部阶段或者尾部结点
15 listIter *listGetIterator(list *list, int direction)
16 {
17     // 为迭代器分配内存
18     listIter *iter;
19     if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
20
21     // 根据迭代方向,设置迭代器的起始节点
22     if (direction == AL_START_HEAD)
23         iter->next = list->head;
24     else
25         iter->next = list->tail;
26
27     // 记录迭代方向
28     iter->direction = direction;
29
30     return iter;
31 }

listNext:拿到下一个迭代器节点

 1 /*
 2  * 返回迭代器当前所指向的节点。
 3  *
 4  * 删除当前节点是允许的,但不能修改链表里的其他节点。
 5  *
 6  * 函数要么返回一个节点,要么返回 NULL ,常见的用法是:
 7  *
 8  * iter = listGetIterator(list,<direction>);
 9  * while ((node = listNext(iter)) != NULL) {
10  *     doSomethingWith(listNodeValue(node));
11  * }
12  *
13  * T = O(1)
14  */
15 listNode *listNext(listIter *iter)
16 {
17     listNode *current = iter->next;
18
19     if (current != NULL) {
20         // 根据方向选择下一个节点
21         if (iter->direction == AL_START_HEAD)
22             // 保存下一个节点,防止当前节点被删除而造成指针丢失
23             iter->next = current->next;
24         else
25             // 保存下一个节点,防止当前节点被删除而造成指针丢失
26             iter->next = current->prev;
27     }
28
29     return current;
30 }

前面说了那么多操作,其实就是为了把它们组合起来使用,比如下面这个函数,就是上面的综合体。

listDup:复制链表

 1 /* Duplicate the whole list. On out of memory NULL is returned.
 2  * On success a copy of the original list is returned.
 3  *
 4  * The ‘Dup‘ method set with listSetDupMethod() function is used
 5  * to copy the node value. Otherwise the same pointer value of
 6  * the original node is used as value of the copied node.
 7  *
 8  * The original list both on success or error is never modified. */
 9 /*
10  * 复制整个链表。
11  *
12  * 复制成功返回输入链表的副本,
13  * 如果因为内存不足而造成复制失败,返回 NULL 。
14  *
15  * 如果链表有设置值复制函数 dup ,那么对值的复制将使用复制函数进行,
16  * 否则,新节点将和旧节点共享同一个指针。
17  *
18  * 无论复制是成功还是失败,输入节点都不会修改。
19  *
20  * T = O(N)
21  */
22 list *listDup(list *orig)
23 {
24     list *copy;
25     listIter *iter;
26     listNode *node;
27
28     // 创建新链表
29     if ((copy = listCreate()) == NULL)
30         return NULL;
31
32     // 设置节点值处理函数
33     copy->dup = orig->dup;
34     copy->free = orig->free;
35     copy->match = orig->match;
36
37     // 迭代整个输入链表
38     iter = listGetIterator(orig, AL_START_HEAD);
39     while((node = listNext(iter)) != NULL) {
40         void *value;
41
42         // 复制节点值到新节点
43         if (copy->dup) {
44             value = copy->dup(node->value);
45             if (value == NULL) {
46                 listRelease(copy);
47                 listReleaseIterator(iter);
48                 return NULL;
49             }
50         } else
51             value = node->value;
52
53         // 将节点添加到链表
54         if (listAddNodeTail(copy, value) == NULL) {
55             listRelease(copy);
56             listReleaseIterator(iter);
57             return NULL;
58         }
59     }
60
61     // 释放迭代器
62     listReleaseIterator(iter);
63
64     // 返回副本
65     return copy;
66 }

最后再提一个旋转函数listRotate,也没有什么需要过多解释的。

 1 /* Rotate the list removing the tail node and inserting it to the head. */
 2 /*
 3  * 取出链表的表尾节点,并将它移动到表头,成为新的表头节点。
 4  *
 5  * T = O(1)
 6  */
 7 void listRotate(list *list) {
 8     listNode *tail = list->tail;
 9
10     if (listLength(list) <= 1) return;
11
12     /* Detach current tail */
13     // 取出表尾节点
14     list->tail = tail->prev;
15     list->tail->next = NULL;
16
17     /* Move it as head */
18     // 插入到表头
19     list->head->prev = tail;
20     tail->prev = NULL;
21     tail->next = list->head;
22     list->head = tail;
23 }

总体来说,链表的数据结构是属于比较简单的。

时间: 09-16

redis源码学习_链表的相关文章

redis源码学习_字典

redis中字典有以下要点: (1)它就是一个键值对,对于hash冲突的处理采用了头插法的链式存储来解决. (2)对rehash,扩展就是取第一个大于等于used * 2的2 ^ n的数作为新的hash表大小:缩紧就是取第一个大于等于used的2 ^ n的数作为新的hash表大小.后面会介绍到dict结构体中是有dictht ht[2]这个成员变量的,为什么是2个呢?就是为了做rehash时交替使用的.那么何时扩展,何时缩紧呢?有个负载因子的概念(负载因子 = used / size,注意这里面

redis源码学习_整数集合

redis里面的整数集合保存的都是整数,有int_16.int_32和int_64这3种类型,和C++中的set容器差不多. 同时具备如下特点: 1.set里面的数不重复,均为唯一. 2.set里面的数是从小到大有序的,这在后面的intsetAdd函数中可以看到. 然后由于我们可以同时存储int_16.int_32和int_64这3种类型,一开始只能为一种类型.假设为int_32,那么我们要插入一个int_16类型的数,只需要找到位置直接插入就可以了:但是我们要插入一个int_64类型的数,我们

Redis源码学习:字符串

Redis源码学习:字符串 1.初识SDS 1.1 SDS定义 Redis定义了一个叫做sdshdr(SDS or simple dynamic string)的数据结构.SDS不仅用于 保存字符串,还用来当做缓冲区,例如AOF缓冲区或输入缓冲区等.如下所示,整数len和free分别表示buf数组中已使用的长度和剩余可用的长度,buf是一个原生C字符串,以\0结尾. sds就是sdshdr中char buf[]的别名,后面能看到,各种操作函数的入参和返回值都是sds而非sdshdr.那sdshd

Redis源码学习-Lua脚本

Redis源码学习-Lua脚本 1.Sublime Text配置 我是在Win7下,用Sublime Text + Cygwin开发的,配置方法请参考<Sublime Text 3下C/C++开发环境搭建>. 要注意的是:在Cygwin中安装Lua解析器后,SublimeClang插件就能识别出可饮用的Lua头文件了,因为Build System中我们已经配置过"-I", "D:\\cygwin64\\usr\\include",而新安装的Lua头文件会

redis源码学习(集群)

集群是一种分布式的思想,把数据存储到各个节点上去提供服务.分布式一个重要的步骤,就是分片.那redis集群是怎么分片的呢,以及集群服务的稳定性和可靠性怎么保证.下面就来剖析下. 1. 集群是怎么创建的,分片怎么设计的? 分片原理: redis的核心数据是个hash table,分片是按照key值来划分,再reds里面叫槽(slot),集群中的各个节点都会分一些槽,用于存储它们的数据. 客户端在请求集群的服务时候,通过查询的key,算出一个hash值,再使用hash值%槽数得到第几个槽,再通过对应

redis源码学习(客户端)

大概介绍 redis 客户端设计主要是存储客户的链接,请求,请求解析的命令,执行结果.先看server的结构和client的结构,server里面有多个client,相当于一个服务端可以连多个客户端,服务端根据事件触发模式依次处理客户端的请求. server结构 struct redisServer { /* General */ // 配置文件的绝对路径 char *configfile; /* Absolute config file path, or NULL */ // serverCr

redis 源码学习(核心数据结构剖析)

redis是个key, value数据库,是个内存数据库.目前是个互联网公司的架构标配. 支持的数据对象有string, list, set, zest和hash object. 数据结构: 数据库的核心结构是dict(实现是使用hashmap): key: string value: string或者list或者set或者zest或者hash object. dict数据结构定义: typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈

Redis源码学习1-sds.c

https://github.com/huangz1990/redis-3.0-annotated/blob/unstable/src/sds.c#L120 1 /* SDSLib, A C dynamic strings library 2 * 3 * Copyright (c) 2006-2012, Salvatore Sanfilippo <antirez at gmail dot com> 4 * All rights reserved. 5 * 6 * Redistribution

Redis源码学习

Redis内置数据结构之双向链表list http://blog.csdn.net/xiejingfa/article/details/50938028 Redis内置数据结构之字符串sds http://blog.csdn.net/xiejingfa/article/details/50972592 Redis内置数据结构之字典dict http://blog.csdn.net/xiejingfa/article/details/51018337 Redis内置数据结构之压缩列表ziplist