参考资料: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代表的尾结点的前一个结点,依次类推。

返回对应索引的结点。

(双向链表部分结束)