Redis源码阅读笔记之链表
链表在Redis中应用广泛，其中列表键的底层实现之一为链表，当列表键包含的元素太多或者其值为较长的内容时会使用链表来实现，比如范围查询： LRANGE nums 0 100。
除了列表键，redis中的发布与订阅，慢查询与监视器等功能都使用到了链表，还有redis本身使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端的输出缓冲区。
单个节点结构
由adlist.h/listNode结构体组成，包括指向前一个节点的指针，后一个节点的指针以及可以访问当前值。因此多个节点组成一个双向链表。
/*
* 双端链表节点
*/
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
//链表节点使用void*指针来保存，因此可以保存各种类型的值（多态）
void *value;
} listNode;
/*
* 双端链表迭代器
*/
typedef struct listIter {
// 当前迭代到的节点
listNode *next;
// 迭代的方向
int direction;
} listIter;
使用adlist.h/list来组成多个链表，这个结构体提供了访问链表的头结点和尾节点的指针，还有计数器len，并且还有操作链表的其他API。并且头结点的前指针以及尾节点后指针指向null，因此为无环链表。源码如下：
/*
* 双端链表结构
*/
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;
还可以为每一个链表创建一个迭代器（有点类似于Java中的List），迭代器可以设置方向来通过头结点或者尾节点来迭代链表。
/*
* 为给定链表创建一个迭代器，
* 之后每次对这个迭代器调用 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;
}
/*
* 返回迭代器当前所指向的节点。
*
* 删除当前节点是允许的，但不能修改链表里的其他节点。
*
* 函数要么返回一个节点，要么返回 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;
}
/*
* 复制整个链表。
*
* 复制成功返回输入链表的副本，
* 如果因为内存不足而造成复制失败，返回 NULL 。
*
* 如果链表有设置值复制函数 dup ，那么对值的复制将使用复制函数进行，
* 否则，新节点将和旧节点共享同一个指针。
*
* 无论复制是成功还是失败，输入节点都不会修改。
*
* T = O(N)
*/
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;
// 迭代整个输入链表
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;
}
/*
* 返回链表在给定索引上的值。
*
* 索引以 0 为起始，也可以是负数， -1 表示链表最后一个节点，诸如此类。
*
* 如果索引超出范围（out of range），返回 NULL 。
*
* T = O(N)
*/
listNode *listIndex(list *list, long index) {
listNode *n;
// 如果索引为负数，从表尾开始查找
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;
}
/* Rotate the list removing the tail node and inserting it to the head. */
/*
* 取出链表的表尾节点，并将它移动到表头，成为新的表头节点。
*
* T = O(1)
*/
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;
}
