Redis是一个开源的日志型和Key-Value数据库，用ANSIC语言编写，支持网络，基于内存和持久化，提供多种语言API。Redis的源代码比较小巧紧凑。早期版本只有两万多行代码。即使是本系列使用的5.0.8版本的源码也不过10万行代码，非常适合学习。本系列将从与其他部分联系不紧密的基础数据结构开始，逐步探索Redis系统设计的精妙之处。作为一个初学者，笔者在自己的代码学习过程中也以此作为记录，并以此为师坚持自学。双端链表的基本数据结构定义在src/adlist.h头文件中，定义了Redis双端链表的基本数据结构，包括链表节点的数据结构，被链链表体和链表迭代器typedefstructlistNode{structlistNode*prev;结构列表节点*下一个；void*value;}listNode;listNode.value字段用于保存指向真实数据内存的指针。typedefstructlist{listNode*head;列表节点*尾部；void*(*dup)(void*ptr);void(*free)(void*ptr);int(*match)(void*ptr,void*key);无符号长长度；}列表；上面是双端链表体的数据结构，其中list.len字段维护了链表的长度，这样我们就可以不用遍历整个链表就可以得到链表的长度。这里需要吐槽一下g++4.8.5中计算链表长度的方法其实是通过遍历计算的：size_typesize()const_GLIBCXX_NOEXCEPT{returnstd::distance(begin(),end());}和数据结构中的三个函数指针，可以根据需要赋值，根据不同的数据类型自定义实现不同的功能。typedefstructlistIter{listNode*next;int方向;}listIter;这是链表迭代器的结构体定义，listIter.direction标示了迭代器迭代的方向。宏定义的基本操作|宏定义|含义||#definelistLength(l)((l)->len)|给定一个双端链表，返回其链表的长度||#definelistFirst(l)((l)->head)|给定一个双端链表，返回链表的头节点||#definelistLast(l)((l)->tail)|给定一个双端链表，返回链表尾节点||#definelistPrevNode(n)((n)->prev)|给定一个节点，返回其前导节点指针||#definelistNextNode(n)((n)->next)|给一个节点，返回其后继节点指针||#definelistNodeValue(n)((n)->value)|返回节点的值节点指针||#definelistSetDupMethod(l,m)((l)->dup=(m))|设置链表设置节点复制方式||#definelistSetFreeMethod(l,m)((l)->free=(m))|设置链表节点释放方式||#definelistSetMatchMethod(l,m)((l)->match=(m))|设置链表比较方式||#definelistGetDupMethod(l)((l)->dup)|返回链表复制方式的函数指针||#definelistGetFree(l)((l)->free)|返回链表释放方法的函数指针||#definelistGetMatchMethod(l)((l)->match)|返回链表释放方法的函数指针链表比较方法|双端链表操作接口API链表创建和释放列表*listCreate(void);该函数会调用zmalloc函数动态分配一个双端链表结构。如果分配失败，该函数将返回一个NULL指针；如果分配成功，则对list.head、list.tail、list.len字段进行初始化，成功后返回指向双端链表对象的指针。不过需要注意的是，list.dup、list.free、list.match这三个字段默认设置为NULL。如果有特殊需要设置，可以调用listSetDupMethod、listSetFreeMethod、listGetDupMethod手动设置。voidlistEmpty(列表*列表);该函数将从链表中删除并释放所有节点。如果链表定义了list.free的回调函数，那么在释放节点之前，会调用list.free对节点的listNode.value进行处理；此函数不会释放链表本身。voidlistRelease(list*list);该函数通过调用listEmpty清除链表的元素，并调用zfree释放链表对象的内存。列表*listAddNodeHead(列表*列表,void*value);列表*listAddNodeTail（列表*列表，无效*值）；这两个函数会在链表的头部或尾部插入一个节点，这个节点会把给定的值指针作为该节点的listNode.value。列表*listInsertNode（列表*list，listNode*old_node，void*value，intafter）；向链表的指定位置插入一个新节点，指定位置由old_node节点标记，如果after为1，则表示有一个新节点插入到old_node节点之后，否则插入到节点之前。voidlistDelNode(list*list,listNode*node);从链表列表中删除给定的节点节点。listNode*listSearchKey(list*list,void*key);从list链表中查找listNode.value等于key的节点，这里equal的意思是：如果list链表中设置了list.match接口，则通过list.match判断是否等于。如果没有定义list.match，则直接比较两者是否指向同一块内存。if(list->match){if(list->match(node->value,key)){返回节点；}}else{if(key==node->value){返回节点；}}listNode*listIndex(list*list,longindex);该函数用于索引链表。该索引值可以是从零开始的正向索引，也可以是从-1开始的反向索引。执行后，返回索引对应节点的指针：listNode*listIndex(list*list,longindex){listNode*n;如果（索引<0）{索引=（-索引）-1；n=列表->尾部；while(index--&&n)n=n->prev;}else{n=list->head;while(index--&&n)n=n->next;}returnn;}链表迭代器listIter*listGetIterator(list*list,intdirection);voidlistReleaseIterator(listIter*iter);listNode*listNext(listIter*iter);其中listGetIterator可以根据传入的方向参数生成正向或反向迭代器，方向参数定义在src/adlist.h头文件中：#defineAL_START_HEAD0//用于生成正向迭代器#defineAL_START_TAIL1//用于生成反向迭代器，listReleaseIterator用于释放迭代器；listNext用于更新迭代器执行一次迭代操作，返回迭代器当前指向的节点指针，并根据方向将迭代器移动到下一个操作。上述生成链表迭代器的操作生成的迭代器是在堆空间上动态分配的迭代器。这个迭代器可以传递指针，并且在程序的整个生命周期中都有效，直到它被调用listReleaseIterator释放为止。而当我们只需要将链表迭代器作为函数中的局部变量使用时，我们可以使用如下两个函数在栈上初始化局部迭代器，函数调用结束后系统会自动释放局部迭代器:voidlistRewind(list*list,listIter*li);voidlistRewindTail(list*list,listIter*li);这两个函数分别用于初始化正向迭代器和反向迭代器。其具体用法如下所示：listIteriter;列表节点*节点；listRewind(l,&iter);while((node=listNext(&iter))!=NULL){//TODO:}链表特殊操作list*listDup(list*orig);该函数用于复制整个链表。如果通过listSetDupMethod为链表设置了Dup方法，则会进行深拷贝，即使用list.dup函数构造节点；否则执行一次浅拷贝是将原节点的值指针赋值给新节点，即两个节点都引用同一个值。voidlistRotate(list*list);该函数用于对链表进行翻转操作，即将链表尾节点转移到链表头部，循环调用链表，实现链表翻转操作。voidlistJoin(列表*l,列表*o);该函数用于对两个链表进行连接操作，即将o链表中的元素依次连接到l链表的后面。喜欢的同学可以扫描二维码关注我微信公众号，Machiavelliincoding
