ps:C 语言没有内置的链表, 所以 Redis 构建了自己的链表实现, 研究 Redsi 源码的话链表必须要研究一下!
一. 链表结点的结构(单个结点):
- // listNode 双端链表节点
- typedef struct listNode {
- // 前置节点
- struct listNode *prev;
- // 后置节点
- struct listNode *next;
- // 节点的值
- void *value;
- } listNode;
该链表为双向链表, 由多个 listNode 结点组成的链表结构图如下:
二. 双端链表的结构:
- // list 双端链表
- typedef struct list { // 在 c 语言中, 用结构体的方式来模拟对象是一种常见的手法
- // 表头节点
- listNode *head;
- // 表尾节点
- listNode *tail;
- // 节点值复制函数
- void *(*dup)(void *ptr);
- // 节点值释放函数
- void(*free)(void *ptr);
- // 节点值对比函数
- int(*match)(void *ptr, void *key);
- // 链表所包含的节点数量
- unsigned long len;
- } list;
这种链表的封装实现方法可以说说极具特色了, 由 lsit 结构和 listNode 结点组成的链表结构图如下:
其中封装了 3 个内置函数
1.dup 函数: 复制链表结点所保存的值
2.free 函数: 释放链表结点所保存的值
3.match 函数: 对比链表结点所保存的值和另一个输入值是否相等
这三个函数是用于实现多态链表所需的类型特定函数
三. Redis 链表的特性:
1. 双端: 获取某个结点的前驱和后继结点都是 O(1)
2. 无环: 表头的 prev 指针和表尾的 next 指针都指向 NULL, 对链表的访问都是以 NULL 为终点
3. 带表头指针和表尾指针: 获取表头和表尾的复杂度都是 O(1)
4. 带链表长度计数器: len 属性记录, 获取链表长度 O(1)
5. 多态: 链表结点使用 void * 指针来保存结点的值, 并且可以通过链表结构的三个函数为结点值设置类型特定函数, 所以链表可以保存各种不同类型的值
四. 链表和链表结点的 API
ps: 下面这些 API 中出现的 zmalloc 函数为内存分配模块函数, 暂不探究
先讲一下根据 list 结构宏定义实现的函数:
- /* 作为宏实现的函数 */
- // 获取长度
- #define listLength(l) ((l)->len)
- // 获取头节点
- #define listFirst(l) ((l)->head)
- // 获取尾结点
- #define listLast(l) ((l)->tail)
- // 获取前一个结点
- #define listPrevNode(n) ((n)->prev)
- // 获取后一个结点
- #define listNextNode(n) ((n)->next)
- // 获取结点的值 是一个 void 类型指针
- #define listNodeValue(n) ((n)->value)
- /* 下面 3 个函数主要用来设置 list 结构中 3 个函数指针, 参数 m 为 method 的意思 */
- #define listSetDupMethod(l,m) ((l)->dup = (m))
- #define listSetFreeMethod(l,m) ((l)->free = (m))
- #define listSetMatchMethod(l,m) ((l)->match = (m))
- /* 下面 3 个函数主要用来获取 list 结构的单个函数指针 */
- #define listGetDupMethod(l) ((l)->dup)
- #define listGetFree(l) ((l)->free)
- #define listGetMatchMethod(l) ((l)->match)
ok, 继续讲具体的 API
1)listCreate 函数: 创建一个不包含任何结点的新链表
- /*
- * listCreate 创建一个新的链表
- *
- * 创建成功返回链表, 失败返回 NULL .
- *
- * T = O(1)
- */
- list *listCreate(void)
- {
- struct list *list;
- // 分配内存
- if ((list = zmalloc(sizeof(*list))) == NULL)
- return NULL;// 内存分配失败则返回 NULL
- // 初始化属性
- list->head = list->tail = NULL;// 空链表
- list->len = 0;
- list->dup = NULL;
- list->free = NULL;
- list->match = NULL;
- return list;
- }
注意创建的是不含任何结点的空链表, 内存分配失败返回 NULL
2)listAddNodeHead 函数: 将一个包含给定值的新结点添加到给定链表的表头
- /*
- * listAddNodeHead 将一个包含有给定值指针 value 的新节点添加到链表的表头
- *
- * 如果为新节点分配内存出错, 那么不执行任何动作, 仅返回 NULL
- *
- * 如果执行成功, 返回传入的链表指针
- *
- * T = O(1)
- */
- 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;
- // 该结点的前驱和后继都为 NULL
- node->prev = node->next = NULL;
- }
- else { // 添加节点到非空链表
- node->prev = NULL;
- node->next = list->head;
- list->head->prev = node;
- list->head = node;
- }
- // 更新链表节点数
- list->len++;
- return list;
- }
就是将一个给定的结点插入到指定链表的表头
3)listAddNodeTail 函数: 将一个包含给定值的新结点插入到给定链表的表尾
- /*
- * listAddNodeTail 将一个包含有给定值指针 value 的新节点添加到链表的表尾
- *
- * 如果为新节点分配内存出错, 那么不执行任何动作, 仅返回 NULL
- *
- * 如果执行成功, 返回传入的链表指针
- *
- * T = O(1)
- */
- 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;
- }
4)listInsertNode 函数: 将一个给定值的新结点插入到给定结点之前或者之后
- /*
- * listInsertNode 创建一个包含值 value 的新节点, 并将它插入到 old_node 的之前或之后
- *
- * 如果 after 为 0 , 将新节点插入到 old_node 之前.
- * 如果 after 为 1 , 将新节点插入到 old_node 之后.
- *
- * T = O(1)
- */
- 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;
- }
5)listDelNode 函数: 从指定的 list 中删除给定的结点
- /*
- * listDelNode 从链表 list 中删除给定节点 node
- *
- * 对节点私有值 (private value of the node) 的释放工作由调用者进行. 该函数一定会成功.
- *
- * T = O(1)
- */
- 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--;
- }
6)listRelease 函数: 释放给定链表以及链表中所有结点
- /*
- * listRelease 释放整个链表, 以及链表中所有节点, 这个函数不可能会失败.
- *
- * T = O(N)
- */
- void listRelease(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;
- }
- // 释放链表结构
- zfree(list);
- }
该函数不仅释放了表结点的内存还释放了表结构的内存!
7)listGetIterator 函数: 为给定链表创建一个迭代器
在讲这个函数之前, 我们应该先看看链表迭代器的结构:
- // listIter 双端链表迭代器
- typedef struct listIter {
- // 当前迭代到的节点
- listNode *next;
- // 迭代的方向
- int direction;
- } listIter;
迭起器只有两个重要的属性: 当前迭代到的结点, 迭代的方向
下面再看看链表的迭代器创建函数
- /*
- * listGetIterator 为给定链表创建一个迭代器,
- * 之后每次对这个迭代器调用 listNext 都返回被迭代到的链表节点, 调用该函数不会失败
- *
- * direction 参数决定了迭代器的迭代方向:
- * AL_START_HEAD : 从表头向表尾迭代
- * AL_START_TAIL : 从表尾想表头迭代
- *
- * T = O(1)
- */
- 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;
- }
8)listReleaseIterator 函数: 释放指定的迭代器
- /*
- * listReleaseIterator 释放迭代器
- *
- * T = O(1)
- */
- void listReleaseIterator(listIter *iter) {
- zfree(iter);
- }
9)listRewind 函数和 listRewindTail 函数: 迭代器重新指向表头或者表尾的函数
- /*
- * 将迭代器的方向设置为 AL_START_HEAD,
- * 并将迭代指针重新指向表头节点.
- *
- * T = O(1)
- */
- void listRewind(list *list, listIter *li) {
- li->next = list->head;
- li->direction = AL_START_HEAD;
- }
- /*
- * 将迭代器的方向设置为 AL_START_TAIL,
- * 并将迭代指针重新指向表尾节点.
- *
- * T = O(1)
- */
- void listRewindTail(list *list, listIter *li) {
- li->next = list->tail;
- li->direction = AL_START_TAIL;
- }
10)listNext 函数: 返回当前迭代器指向的结点
- /*
- * 返回迭代器当前所指向的节点.
- *
- * 删除当前节点是允许的, 但不能修改链表里的其他节点.
- *
- * 函数要么返回一个节点, 要么返回 NULL, 常见的用法是:
- *
- * iter = listGetIterator(list,<direction>);
- * while ((node = listNext(iter)) != NULL) {
- * doSomethingWith(listNodeValue(node));
- * }
- *
- * T = O(1)
- */
- 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;
- }
该函数保持了当前结点的下一个结点, 避免了当前结点被删除而迭代器无法继续迭代的尴尬情况
11)listDup 函数: 复制整个链表, 返回副本
- /*
- * 复制整个链表.
- *
- * 复制成功返回输入链表的副本,
- * 如果因为内存不足而造成复制失败, 返回 NULL .
- *
- * 如果链表有设置值复制函数 dup , 那么对值的复制将使用复制函数进行,
- * 否则, 新节点将和旧节点共享同一个指针.
- *
- * 无论复制是成功还是失败, 输入节点都不会修改.
- *
- * T = O(N)
- */
- list *listDup(list *orig)
- {
- list *copy;// 链表副本
- listIter *iter;// 链表迭代器
- listNode *node;// 链表结点
- // 创建新的空链表
- if ((copy = listCreate()) == NULL)
- return NULL;// 创建空的链表失败则返回 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;
- }
如果复制失败则要注意释放副本链表和迭代器, 避免内存泄漏
12)listSearchKey 函数: 查找 list 中值和 key 匹配的结点
- /*
- * 查找链表 list 中值和 key 匹配的节点.
- *
- * 对比操作由链表的 match 函数负责进行,
- * 如果没有设置 match 函数,
- * 那么直接通过对比值的指针来决定是否匹配.
- *
- * 如果匹配成功, 那么第一个匹配的节点会被返回.
- * 如果没有匹配任何节点, 那么返回 NULL .
- *
- * T = O(N)
- */
- listNode *listSearchKey(list *list, void *key)
- {
- listIter *iter;// 链表迭代器
- listNode *node;// 链表结点
- // 获得链表迭代器
- iter = listGetIterator(list, AL_START_HEAD);
- // 遍历整个链表查询
- while ((node = listNext(iter)) != NULL) {
- // 存在比较函数
- if (list->match) {
- // 利用比较函数进行比较
- if (list->match(node->value, key)) {
- // 返回目标结点之前释放迭代器空间, 避免内存泄漏
- listReleaseIterator(iter);
- return node;
- }
- }
- // 不存在比较函数
- else {
- // 直接比较
- if (key == node->value) {
- // 返回目标结点之前释放迭代器空间, 避免内存泄漏
- listReleaseIterator(iter);
- // 找到
- return node;
- }
- }
- }
- // 返回目标结点之前释放迭代器空间, 避免内存泄漏
- listReleaseIterator(iter);
- // 未找到
- return NULL;
- }
13)listIndex 函数: 返回链表在给定索引上的值
- /*
- * 返回链表在给定索引上的值.
- *
- * 索引以 0 为起始, 也可以是负数, -1 表示链表最后一个节点, 诸如此类.
- *
- * 如果索引超出范围(out of range), 返回 NULL .
- *
- * T = O(N)
- */
- listNode *listIndex(list *list, long index) {
- listNode *n;// 链表结点
- /* n 不用设置成 NULL 的原因:
- 如果索引超出范围,
- 那肯定是找到表头或者表尾没有找到,
- 表头的前驱和表尾的后继都是 NULL,
- 所以这里 n 不用设置为 NULL, 直接设置也可以 */
- // 如果索引为负数, 从表尾开始查找
- if (index <0) {
- // 变成正数, 方便索引
- index = (-index) - 1;
- // 从尾部开始找
- n = list->tail;
- // 寻找 因为从尾部开始找, 所以是前驱
- while (index-- && n) n = n->prev;
- }
- // 如果索引为正数, 从表头开始查找
- else {
- // 从头部开始找
- n = list->head;
- // 寻找 因为从头部开始找, 所以是后继
- while (index-- && n) n = n->next;
- }
- return n;
- }
14)listRotate 函数: 取出链表的表尾结点放到表头, 成为新的表头结点
- /*
- * 取出链表的表尾节点, 并将它移动到表头, 成为新的表头节点.
- *
- * T = O(1)
- */
- void listRotate(list *list) {
- // 表尾结点
- listNode *tail = list->tail;
- // 如果链表中只有一个元素, 那么表头就是表尾, 可以直接返回
- if (listLength(list) <= 1) return;
- // 重新设置表尾节点
- list->tail = tail->prev;
- list->tail->next = NULL;
- // 插入到表头
- list->head->prev = tail;
- tail->prev = NULL;
- tail->next = list->head;
- list->head = tail;
- }
总结: Redis 内置的链表实现还是很简单的, 代码也不多, 但是功能都有, 值得学习
来源: http://www.bubuko.com/infodetail-3030620.html