详解Redis中的双链表结构
Redis中双链表实现的基本结构：
1.节点结构
typedefstructlistNode{
structlistNode*prev;//前向节点
structlistNode*next;//后向节点
void*value;//该节点的值
}listNode;
2.双向链表结构
typedefstructlist{
listNode*head;//头节点
listNode*tail;//尾节点
void*(*dup)(void*ptr);//复制函数
void(*free)(void*ptr);//释放函数
int(*match)(void*ptr,void*key);//匹配函数，查找节点使用
unsignedlonglen;//双向链表的长度即节点的个数
}list;
3.双向链表遍历器
typedefstructlistIter{
listNode*next;//下一个节点
intdirection;
}listIter;
方向定义
#defineAL_START_HEAD0//向前查找
#defineAL_START_TAIL1//向后查找
4.宏定义函数
#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)
5.定义函数
list*listCreate(void);//创建一个新的链表。该链表可以使用AlFree（）方法释放。
//但使用AlFree（）方法前需要释放用户释放私有节点的值。
//如果没有创建成功，返回null；创建成功则返回指向新链表的指针。
voidlistRelease(list*list);//释放整个链表，此函数不会执行失败。调用zfree(list*list)方法,定义在Zmalloc.c中。
list*listAddNodeHead(list*list,void*value);//向链表头部中增加一个节点
list*listAddNodeTail(list*list,void*value);//向链表尾部增加一个节点
list*listInsertNode(list*list,listNode*old_node,void*value,intafter);//向某个节点位置插入节点after为方向
voidlistDelNode(list*list,listNode*node);//从链表上删除特定节点，调用者释放特定私用节点的值。
//该函数不会执行失败
listIter*listGetIterator(list*list,intdirection);//返回某个链表的迭代器。
//迭代器的listNext（）方法会返回链表的下个节点。direction是方向
//该函数不会执行失败。
listNode*listNext(listIter*iter);
voidlistReleaseIterator(listIter*iter);//释放迭代器的内存。
list*listDup(list*orig);//复制整个链表。当内存溢出时返回null，成功时返回原链表的一个备份
//不管该方法是否执行成功，原链表不会改变。
listNode*listSearchKey(list*list,void*key);//从特定的链表查找key。成功则返回第一个匹配节点的指针
//如果没有匹配，则返回null。
listNode*listIndex(list*list,longindex);//序号从0开始，链表的头的索引为0.1为头节点的下个节点。一次类推。
//负整数用来表示从尾部开始计数。-1表示最后一个节点，-2倒数第二个节点
//如果超过链表的索引，则返回null
voidlistRewind(list*list,listIter*li){
li->next=list->head;
li->direction=AL_START_HEAD;
}
voidlistRewindTail(list*list,listIter*li){
li->next=list->tail;
li->direction=AL_START_TAIL;
}
voidlistRotate(list*list);//旋转链表，移除尾节点并插入头部。
list结构和listNode结构的API
list和listNode都有它们自己的一族API，这里贴出来学习一下redis的源码(ps:下面的代码都是我仿照redis改写能直接编译运行的代码)
list*listCreate(void)
/**
*创建一个新列表
*
*T=O(1)
*/
list*listCreate(void)
{
structlist*list;
//为列表结构分配内存
list=(structlist*)malloc(sizeof(structlist));
if(list==NULL)
returnNULL;
//初始化属性
list->head=list->tail=NULL;
list->len=0;
list->dup=NULL;
list->free=NULL;
list->match=NULL;
returnlist;
}
voidlistRelease(list*list)
/**
*释放整个列表
*
*T=O(N),N为列表长度
*/
voidlistRelease(list*list)
{
unsignedlonglen;
listNode*current,*next;
current=list->head;
len=list->len;
while(len--){
next=current->next;
//如果列表有自带的free方法，那么先对节点值调用它
if(list->free)list->free(current->value);
//之后释放节点
free(current);
current=next;
}
free(list);
}
list*listAddNodeHead(list*list,void*value)
/**
*新建一个包含给定value的节点，并将它加入到列表的表头
*
*T=O(1)
*/
list*listAddNodeHead(list*list,void*value)
{
listNode*node;
node=(listNode*)malloc(sizeof(listNode));
if(node==NULL)
returnNULL;
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++;
returnlist;
}
list*listAddNodeTail(list*list,void*value)
/**
*新建一个包含给定value的节点，并把它加入到列表的表尾
*
*T=O(1)
*/
list*listAddNodeTail(list*list,void*value)
{
listNode*node;
node=(listNode*)malloc(sizeof(listNode));
if(node==NULL)
returnNULL;
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++;
returnlist;
}
list*listInsertNode(list*list,listNode*old_node,void*value,intafter)
/**
*创建一个包含值value的节点
*并根据after参数的指示，将新节点插入到old_node的之前或者之后
*
*T=O(1)
*/
list*listInsertNode(list*list,listNode*old_node,void*value,intafter)
{
listNode*node;
node=(listNode*)malloc(sizeof(listNode));
if(node==NULL)
returnNULL;
if(after){
//插入到old_node之后
node->prev=old_node;
node->next=old_node->next;
//处理表尾节点
if(list->tail==old_node){
list->tail=node;
}
}else{
//插入到old_node之前
node->next=old_node;
node->prev=old_node->prev;
//处理表头节点
if(list->head==old_node){
list->head=node;
}
}
//更新前置节点和后继节点的指针(这个地方很经典，节约代码)
if(node->prev!=NULL){
node->prev->next=node;
}
if(node->next!=NULL){
node->next->prev=node;
}
//更新列表节点
list->len++;
returnlist;
}
voidlistDelNode(list*list,listNode*node)
/**
*释放列表中给定的节点
*
*T=O(1)
*/
voidlistDelNode(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(node);
//更新列表节点数目
list->len--;
}
迭代器
其实我对迭代器的概念非常陌生，因为我是纯c程序员，不会c++，这里直接跟着学了！
Redis针对list结构实现了一个迭代器，用于对链表进行遍历
迭代器的结构定义如下：
/**
*链表迭代器
*/
typedefstructlistIter{
//下一节点
listNode*next;
//迭代方向
intdirection;
}listIter;
direction决定了迭代器是沿着next指针向后迭代，还是沿着prev指针向前迭代，这个值可以是adlist.h中的AL_START_HEAD常量或AL_START_TAIL常量：
#defineAL_START_HEAD0 #defineAL_START_TAIL1
学习一下迭代器的api实现：
listIter*listGetIterator(list*list,intdirection)
/**
*创建列表list的一个迭代器，迭代方向由参数direction决定
*
*每次对迭代器listNext(),迭代器返回列表的下一个节点
*
*T=O(1)
*/
listIter*listGetIterator(list*list,intdirection)
{
listIter*iter;
iter=(listIter*)malloc(sizeof(listIter));
if(iter==NULL)
returnNULL;
//根据迭代器的方向，将迭代器的指针指向表头或者表尾
if(direction==AL_START_HEAD){
iter->next=list->head;
}else{
iter->next=list->tail;
}
//记录方向
iter->direction=direction;
returniter;
}
voidlistRewind(list*list,listIter*li)
/**
*将迭代器iter的迭代指针倒回list的表头
*
*T=O(1)
*/
voidlistRewind(list*list,listIter*li)
{
li->next=list->head;
li->direction=AL_START_HEAD;
}
voidlistRewindTail(list*list,listIter*li)
/**
*将迭代器iter的迭代指针倒回list的表尾
*
*T=O(1)
*/
voidlistRewindTail(list*list,listIter*li)
{
li->next=list->tail;
li->direction=AL_START_TAIL;
}
listNode*listNext(listIter*iter)
/**
*函数要么返回当前节点，要么返回NULL，因此，常见的用法是：
*iter=listGetIterator(list,<direction>);
*while((node=listNext(iter))!=NULL){
*doSomethingWith(listNodeValue(node));
*}
*
*T=O(1)
*/
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;
}
returncurrent;
}