Redis 源码--链表。

因为C语言是一个比较底层的语言，库内没有实现链表，于是Redis自己实现了链表。Redis的链表是一个双向链表。

typedef struct listNode
{
        struct listNode* prev ;
        struct listNode* next ;
        void * value;
}
listNode

redis通过一个结构体 list来操作链表，主要是保存长度和头部和尾部。所以redis的取链表的头部和尾部以及长度的操作都变成了O（1）。对于 head指针和tail指针，他们分别指向了链表的实际头和尾部指针，这个list还有一些其他属性，主要是函数指针，用来实现不同语义下的结点释放复制与比较过程。在没有对象这一说的C里通过函数指针实现了类似的多态过程。

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;

与此同时 还实现了自己的一个迭代器,若direction为AL_START_HEAD，则说明是正向遍历的，如果是AL_START_TAIL，则是反向遍历的。

typedef struct listIter {

    // 当前迭代到的节点
    listNode *next;

    // 迭代的方向
    int direction;

} listIter;

对于这个迭代器来说,通过暂存current之后的下一个结点，redis允许当前结点被删除,但是不允许删除非current的结点。那样明显的会导致链表元素的丢失。

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

链表这一段的代码并不长，实现也比较简单，主要对链表有基本的了解，阅读起来没什么大的问题。