Redis源码阅读笔记（二）list双向链表结构

- list简介

相对于sds来说，list并没有太多新的想法和机制，就和自己实现一个双向链表差不多，主要有节点结构、链表结构和迭代器结构三个部分。
只有一个比较新奇的想法是，因为在存储节点的值时，使用的是一个void * 指针，而对void * 里面的数据则可以自己定义一些节点值的复制、释放和比较函数。但是就C语言来说结构体是不具有成员函数的，为了让节点值操作函数能够和链表绑定，在链表结构中存储了相应和函数指针作为成员变量，以此来达到目的。

- list具体实现 ``` 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 long len; //节点数量
} list;


<h6> - list函数操作

//链表创建，失败返回null，成功返回指向链表的指针
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;

}
//释放链表：包括释放节点中的值，释放节点结构，释放链表结构
void listRelease(list *list)
{
unsigned long len;
listNode *current, *next;

current = list->head;
len = list->len;
while(len--) {
    next = current->next;
    if (list->free) list->free(current->value);   //如果设置了释放函数就调用它，用于释放节点中的value
    zfree(current);  //释放节点结构
    current = next;
}
zfree(list);  //释放链表结构

}
/*

为给定链表创建一个迭代器，是一个单向迭代器
之后每次对这个迭代器调用 listNext 都返回被迭代到的链表节点
direction 参数决定了迭代器的迭代方向：
AL_START_HEAD ：从表头向表尾迭代
AL_START_TAIL ：从表尾想表头迭代
T = O(1)
*/
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;
}
//获取到这个迭代器所指向的节点，其实就是iter->next，用过一次后迭代器就会向后走一步
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;
}

复制整个链表。
复制成功返回输入链表的副本，
如果因为内存不足而造成复制失败，返回 NULL 。
如果链表有设置值复制函数 dup ，那么对值的复制将使用复制函数进行，
否则，新节点将和旧节点共享同一个指针！！！！！！！！！！！！！！！！！！！！！！！！！
无论复制是成功还是失败，输入节点都不会修改。
T = O(N)
*/
list *listDup(list *orig)
{
list *copy;
listIter *iter;
listNode *node;
if ((copy = listCreate()) == NULL) //新建一个空链表
return NULL;
copy->dup = orig->dup; //先设置节点值处理函数
copy->free = orig->free;
copy->match = orig->match;
iter = listGetIterator(orig, AL_START_HEAD); //设置迭代器为从头至尾，并开始迭代复制
while((node = listNext(iter)) != NULL) {
void *value;
//先拷贝值
if (copy->dup) {
value = copy->dup(node->value);
if (value == NULL) {
listRelease(copy);
listReleaseIterator(iter);
return NULL;
}
} else
value = node->value;
//将该值添加进链表
if (listAddNodeTail(copy, value) == NULL) {
listRelease(copy);
listReleaseIterator(iter);
return NULL;
}
}
listReleaseIterator(iter); //记得释放迭代器
return copy;
}

因为list的函数操作基本都很简单，这里就不一一列出了，只提几点值得注意的地方。
1.在进行链表的复制，节点的比较时，如果当前链表定义了值操作函数就要调用值操作来完成相应的复制和比较。
2.在释放链表时，主要有三个步骤，首先若有值释放函数则需要对节点值进行释放，然后对逐个节点结构进行释放，最后要对该链表结构进行释放。
3.在迭代器使用时，因为确保了迭代器内部next指针的有效性，可以对当前节点进行包括删除在内的各种操作，但是不能操作非迭代器指向的节点。同时也正是为了确保有效性，通常在使用迭代器函数时，迭代器都会自动指向下一个节点。

- list简介

- list具体实现 ``` typedef struct listNode { //链表中每个节点的结构 struct listNode *prev; struct listNode *next; void *value; } listNode;

- list具体实现 ``` typedef struct listNode { //链表中每个节点的结构 struct listNode prev; struct listNode next; void *value; } listNode;