redis源代码分析1–链表

先简单介绍下redis中用到的链表，是在文件adlist.c和adlist.h中实现的。

实现中主要用到listNode、list、listIter三个结构，listNode代表链表中的每个节点，list指向整个链表，listIter是为了迭代访问整个list，内部其实就是个listNode指针。

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

listNode提供的prev、next指针将整个list链接成一个双向链表，保存的值是void *类型，对值的复制、释放、匹配操作是用在list中注册的三个函数指针dup、free、match完成的。

在list结构中，除提供对listNode中的值进行操作的三个函数指针外，还提供了head、tail指针，以指向list的头部和尾部。另外list的len保存了整个list的长度，方便对list是否为空的判断(纯属多余吧)。

listIter是为了遍历list，可以从头部、尾部开始遍历。用法可用如下伪代码表示：

iter=listGetIterotr(list, <direction>);
while ((node=listNext(iter)) !=NULL)
{
	DoSomethingWith(listNodeValue(node));
}

另外注意：在提供的增加、删除节点的api（listAddNodeHead、listAddNodeTail、listDelNode）中，并没有分配、释放节点 内部的value所用内存，需要调用者自己分配或者释放value所占的内存（除了分配和释放节点本身的内存外）。

乍一看没有提供修改某个节点的值的方法，但是由于listSearchKey、listIndex等方法返回了节点指针，故可以直接修改节点的value。