从零学习redis（16）--- 源码阅读之链表

redis 内部链表的实现比较简单，包括 3 个结构体：

src/adlist.h

typedef struct listNode {
  struct listNode *prev; // 前一个节点指针
  struct listNode * next; // 后一个节点指针
  void *value; // 节点值
} listNode;

typedef struct listIter {
  listNode *next; // 下一个节点
  int direction; // 遍历的方向(从头到尾或反向)
} listIter;

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;

listNode 结构体表示单个节点的信息，从每个节点包含前一个节点的指针和后一个节点的指针我们可以知道 redis 的链表是双向链表，其中 value 字段是一个 void 指针是为了方便节点可以存放任何类型的值。

list 结构体表示一个链表，链表包含头尾节点的指针(其中 head 的 prev 为 NULL，tail 的 next 为 NULL，也就是说 redis 的链表是无环链表)、节点的长度、和 3 个用于处理节点值的函数。3 个指针函数同样是为了提升链表的可用性，上面说的节点的值 value 字段可以存放任何类型，而 dup、free、match 三个函数分别用于处理节点值的复制、释放、比较。

listIter 结构体用于表示链表的一个单向遍历链表，其中 direction 表示 方向。这个结构体是干什么的呢，因为 redis 的链表是双向链表，那么我们就可以从头到尾遍历数组或从尾到头遍历，而 listIter 就是为了方便这种遍历，redis 提供了函数 listIter listGetIterator(list list, int direction) 获得一个 listIter（其中 direction 指明遍历方向，direction等于0表示从头到尾或者表示从尾到头)，然后我们就可以直接使用函数 listNode listNext(listIter iter) 获得下一个要遍历的节点。（去看下这两个的函数实现就很容易理解）

所有用于链表相关的函数声明如下（函数定义在src/adlist.c）：

// micro 实现struct属性getter/setter
#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)
#define listNodeValue(n) ((n)->value)

#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))

#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)

// 创建一个空list
list *listCreate(void);
// 删除并释放 list 上所有的 listNode
void listRelease(list *list);
// 删除并释放 list 上所有的 listNode
void listEmpty(list *list);
// 添加 value 到列表头部
list *listAddNodeHead(list *list, void *value);
// 添加 value 到列表尾部
list *listAddNodeTail(list *list, void *value);
// 把 value 添加到列表中某一个（old_node）的前面或后面(after=1 or 0)
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
// 删除 list 上的特定 listNode
void listDelNode(list *list, listNode *node);
// 获得 list 上 listNode 遍历的单链表结构 (listIter),方向由 direction 指定
listIter *listGetIterator(list *list, int direction);
// 获得迭代器下一个元素
listNode *listNext(listIter *iter);
// 删除 listIter
void listReleaseIterator(listIter *iter);
// 复制 list
list *listDup(list *orig);
// 在列表中查找一个值，并返回值所在 listNode
listNode *listSearchKey(list *list, void *key);
listNode *listIndex(list *list, long index);
// 返回从头到尾迭代器
void listRewind(list *list, listIter *li);
// 返回从尾到头迭代器
void listRewindTail(list *list, listIter *li);
// 把 list 的最后一个节点转换成 list 的头节点
void listRotate(list *list);
// 把 list o 合并到 l 的后面，并清空 list o(不删除)
void listJoin(list *l, list *o);