参考资料：http://www.redisbook.com
Redis实现了双向链表，它是Redis的基本数据结构List（列表）的底层实现之一，为实现列表的一系列操作(如：LPUSH,RPUSH,LLEN等)提供了底层的接口。

文件依赖

adlist.c adlist.h zmalloc.h

链表实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 int len;					/* 存储链表中的结点书 */
    listIter iter;						/* 链表的迭代器 */
} list;

每个结点中有两个指针，这样可以使用迭代器进行正向和逆向访问。
有个疑问，listIter中的direction成员只有两个值，0和1，那么采用char类型存储是否更好？毕竟redis是内存数据库，一个list能节省三字节，对于整个数据库来说，节省下来的内存还是很客观的。
list结构示意图：

用宏实现的函数

对于一些比较简单的函数，用宏实现可以避免函数调用带来的开销，提高效率。
都是一些很简单的宏 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 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)) /* dup函数指针绑定函数 */
#define listSetFreeMethod(l,m) ((l)->free = (m)) /* free函数指针绑定函数 */
#define listSetMatchMethod(l,m) ((l)->match = (m)) /* match函数指针绑定函数 */

#define listGetDupMethod(l) ((l)->dup) /* 得到dup指针指向的函数 */
#define listGetFree(l) ((l)->free)	   /* 得到free指针指向的函数 */
#define listGetMatchMethod(l) ((l)->match) /* 得到match函数指向的函数 */

剩余函数的详细注释

1. listCreate

1
2
3
4
5
6
7
8
9
10
11
12
13
list *listCreate(void)
{
    struct list *list;

    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

调用zmalloc函为链表分配内存，分配成功后，将链表成员初始化为空。

2. listRelease

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* Free the whole list.
*
* This function can't fail. */
void listRelease(list *list)
{
    unsigned int len;
    listNode *current, *next;

    current = list->head;
    len = list->len;
    while(len--) {
        next = current->next;
        if (list->free) list->free(current->value); /* 如果指定了free函数，对当前结点的value进行free操作*/
        zfree(current);								/* 释放当前结点 */
        current = next;
        }
        zfree(list);				/* 释放整个list */
}

如果指定了list中的free函数成员，先要对listNode中的value进行free操作，最后才释放listNode。释放完所有的listNode，才能释放整个list。

3. listAddNodeHead

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* 向list中的链表头部添加值为value的结点 */
/* Add a new node to the list, to head, contaning the specified 'value'
* pointer as value.
*
* On error, NULL is returned and no operation is performed (i.e. the
* list remains unaltered).
* On success the 'list' pointer you pass to the function is returned. */
list *listAddNodeHead(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (list->len == 0) {		/* 链表是空的 */
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {					/* 链表不为空 */
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    list->len++;				/* 增加链表长度 */
    return list;
}

该函数在链表的头部增加一个结点。

4. listAddNodeTail

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* 在链表的尾部添加值为value的结点 */
/* Add a new node to the list, to tail, contaning the specified 'value'
* pointer as value.
*
* On error, NULL is returned and no operation is performed (i.e. the
* list remains unaltered).
* On success the 'list' pointer you pass to the function is returned. */
list *listAddNodeTail(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (list->len == 0) {		/* 链表是空的 */
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {					/* 链表不为空 */
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    list->len++;				/* 链表的长度加一 */
    return list;
}

该函数在链表的尾部添加一个结点

5. listDelNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 从链表中删除指定的结点 */
/* Remove the specified node from the specified list.
* It's up to the caller to free the private value of the node.
*
* This function can't fail. */
void listDelNode(list *list, listNode *node)
{
    if (node->prev)				/* 删除的不是头结点 */
        node->prev->next = node->next;
    else						/* 删除的是头结点 */
        list->head = node->next;
    if (node->next)				/* 删除的不是尾结点 */
        node->next->prev = node->prev;
    else						/* 删除的是尾结点 */
        list->tail = node->prev;
    if (list->free) list->free(node->value); /* 如果指定了free函数,*/
    /*对当前结点的value进行free操作 */
    zfree(node);							 /* 释放掉整个结点 */
    list->len--;							 /* 链表长度减1 */
}

从链表中删除指定的结点，如果指定了free函数，需要对value进行free操作。

6. listGetIterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 创建指定方向的迭代器 */
/* Returns a list iterator 'iter'. After the initialization every
* call to listNext() will return the next element of the list.
*
* This function can't fail. */
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;
}

生成一个给定方向的迭代器。

7. listReleaseIterator

1
2
3
4
/* Release the iterator memory */
void listReleaseIterator(listIter *iter) {
zfree(iter);
}

释放迭代器。

8. listRewind

1
2
3
4
5
/* Create an iterator in the list private iterator structure */
void listRewind(list *list) {
    list->iter.next = list->head;
    list->iter.direction = AL_START_HEAD;
}

生成一个list私有的迭代器，方向是“从头到尾”。

9. listRewindTail

1
2
3
4
void listRewindTail(list *list) {
    list->iter.next = list->tail;
    list->iter.direction = AL_START_TAIL;
}

生成一个list私有的迭代器，方向是“从尾到头”。

10. listNext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* Return the next element of an iterator.
* It's valid to remove the currently returned element using
* listDelNode(), but not to remove other elements.
*
* The function returns a pointer to the next element of the list,
* or NULL if there are no more elements, so the classical usage patter
* is:
*
* iter = listGetItarotr(list,<direction>);
* while ((node = listNextIterator(iter)) != NULL) {
*     DoSomethingWith(listNodeValue(node));
* }
*
* */
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;
}

返回当前迭代器指向的元素，并将迭代器指向下一个元素。

11. listYield

1
2
3
4
/* List Yield just call listNext() against the list private iterator */
listNode *listYield(list *list) {
    return listNext(&list->iter);
}

返回list私有迭代器当前指向的元素。

12. listDup

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/* 复制list */
/* Duplicate the whole list. On out of memory NULL is returned.
* On success a copy of the original list is returned.
*
* The 'Dup' method set with listSetDupMethod() function is used
* to copy the node value. Otherwise the same pointer value of
* the original node is used as value of the copied node.
*
* The original list both on success or error is never modified. */
list *listDup(list *orig)
{
    list *copy;
    listIter *iter;
    listNode *node;

    if ((copy = listCreate()) == NULL) /* 创建一个list，如果返回为NULL，常见失败 */
        return NULL;             
    copy->dup = orig->dup;        /* 复制原list中的函数成员 */
    copy->free = orig->free;
    copy->match = orig->match;
    iter = listGetIterator(orig, AL_START_HEAD);
    while((node = listNext(iter)) != NULL) {
        void *value;

        if (copy->dup) {        /* 原list指定了dup函数 */
            value = copy->dup(node->value);
            if (value == NULL) { /* dup操作失败，释放已经分配的资源，返回NULL */
                listRelease(copy);
                listReleaseIterator(iter);
                return NULL;
            }
        } else                    /* 没指定dup函数 */
            value = node->value;
        if (listAddNodeTail(copy, value) == NULL) { /* 把orig中结点的value*/
        /*指针赋给copy中的value */
            listRelease(copy);                        /* 如果出错，释放已经分配的资源 */
            listReleaseIterator(iter);
            return NULL;
        }
    }
    listReleaseIterator(iter);    /* 释放迭代器 */
    return copy;
}

赋值一个list，成功的话，返回新的list,失败返回NULL。

如果指定了dup函数，就使用dup函数复制，未指定的话，就将orig lsit中结点的value指针给copy list中的结点。

13. listSearchKey

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/* 返回等于指定key的结点 */
/* Search the list for a node matching a given key.
* The match is performed using the 'match' method
* set with listSetMatchMethod(). If no 'match' method
* is set, the 'value' pointer of every node is directly
* compared with the 'key' pointer.
*
* On success the first matching node pointer is returned
* (search starts from head). If no matching node exists
* NULL is returned. */
listNode *listSearchKey(list *list, void *key)
{
    listIter *iter;
    listNode *node;

    iter = listGetIterator(list, AL_START_HEAD);
    while((node = listNext(iter)) != NULL) {
        if (list->match) {        /* 指定了match函数 */
            if (list->match(node->value, key)) {
                listReleaseIterator(iter);
                return node;
            }
        } else {                /* 未指定match函数 */
            if (key == node->value) {
                listReleaseIterator(iter);
                return node;
            }
        }
    }
    listReleaseIterator(iter);
    return NULL;
}

给定key，遍历list的所有结点，如果指定了match函数，就调用match函数进行比较，如果没有指定match函数，就直接比较两个指针的地址。

14. listIndex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 返回指定索引的结点 */
/* Return the element at the specified zero-based index
* where 0 is the head, 1 is the element next to head
* and so on. Negative integers are used in order to count
* from the tail, -1 is the last element, -2 the penultimante
* and so on. If the index is out of range NULL is returned. */
listNode *listIndex(list *list, int 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;
}

索引0代表头结点，1代表头结点的下一个结点，2，3，4…依次类推。索引-1代表的是尾结点，-2代表的尾结点的前一个结点，依次类推。

返回对应索引的结点。

（双向链表部分结束）