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;
}