adlist 阅读
author： Pei Xingxin (xingxinpei@gmail.com)
background
这里其实想谈谈为什么要做redis的source code reading & analysing。动机有点尴尬，因为在大厂的工作中，开源的工具使用较少，时间长了竟然会成为一个被外部人员低看一眼的理由。当然，对于面试应该考察什么这个话题，我也一肚子槽想吐，找个机会会一并写出。
话不多说，言归正传
adlist是什么
adlist - A generic doubly linked list implementation，就是一个通用的双向列表实现。
adlist的数据结构
一个典型的list，一定会有node，这个实现比较完备，同时提供了iterator。于是这里至少有三个数据结构
listNode
Node是链表中的每个节点的定义与抽象，其中value可以是更丰富的类型
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
listIter
迭代器用于遍历整个list
typedef struct listIter {
listNode *next;
int direction;
} listIter;
list
list是真正对外操作的数据结构，有几个重要的参数，head，tail用于分别表示头节点和尾节点，len是用于记录当前的链表长度，这样length操作就是O（1）的时间复杂度。另外，为了使链表更有通用性，即基于value的复杂性，提供了dup，free，match三个特殊的函数指针用于专门操作value部分
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;
list操作部分，宏部分
这部分操作是可以根据list的成员变量直接获得的，定义函数的好处是，接口更统一易读
/* Functions implemented as macros */
#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)
iterator的操作方向，也是宏定义
/* Directions for iterators */
#define AL_START_HEAD 0
#define AL_START_TAIL 1
函数操作的部分，需要代码实现部分的对于接口定义
接口的定义基本上都非常的通俗易懂，大部分其意自明。这里重点描述一下几个函数
listRewind, 表示把迭代器指向头部，并且从头部开始遍历
listRewindTail，把迭代器指向尾部，遍历方向设置为从尾部开始
listRotate，表示把最后一个元素挪到第一个去
listSearchKey，表示在链表中找到value = key 的节点
listIndex，表示链表从头或者从尾部，找到第index个节点
/* Prototypes */
list *listCreate(void);
void listRelease(list *list);
list *listAddNodeHead(list *list, void *value);
list *listAddNodeTail(list *list, void *value);
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
void listDelNode(list *list, listNode *node);
listIter *listGetIterator(list *list, int direction);
listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter);
list *listDup(list *orig);
listNode *listSearchKey(list *list, void *key);
listNode *listIndex(list *list, long index);
void listRewind(list *list, listIter *li);
void listRewindTail(list *list, listIter *li);
void listRotate(list *list);
函数操作的实现部分
这部分都在adlist.c中，代码实现很优美，建议日常的链表操作都可以参考这里代码实现。举一个实现比较优雅的例子
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;
}
