双端链表list的实现 | 自己实现Redis源代码(2)

通过对《Redis 设计与实现》一书的学习，我打算动手自己实现一份“Redis 源代码”作为自己的学习记录。
对 Redis 感兴趣的同学可以查看我的另一篇文章 造个轮子 | 自己动手写一个 Redis。
本章介绍的是 Redis 源代码中的双端链表 list 的实现。

双端链表 list 的实现

list 的 API
（1）创建一个不包含任何结点的新链表
list *listCreate(void);
（2）释放给定链表，以及链表中的所有结点
void listRelease(list *l);
（3）将一个包含给定值的新节点添加到给定链表的表头
list listAddNodeHead(list l, void *value);
（4）将一个包含给定值的新节点添加到给定链表的表尾
list listAddNodeTail(list l, void *value);
（5）将一个包含给定值的新节点添加到给定结点的之前或之后
list listInsertNode(list l, listNode old_node, void value, int after);
（6）从链表中删除给定结点
list listDelNode(list l, listNode *node);
（7）复制一个给定链表的副本
list listDup(list orig);
（8）查找并返回链表中包含给定值的结点
listNode listSearchKey(list l, void *key);
（9）返回链表在给定索引上的结点
listNode listIndex(list l, long index);
（10）将链表结点的表位结点弹出，然后将被弹出的结点插入到链表的表头，成为新的表头结点
void listRotate(list *l);

头文件
#ifndef __ADLIST_H__
#define __ADLIST_H__

// 双端链表

// 双端链表的结点
typedef struct listNode{
struct listNode *prev;// 指向点一个结点的指针
struct listNode *next;// 指向下一个结点的指针
void *value;// 结点存放的值
}listNode;

// 链表
typedef struct list{
listNode *head;// 头结点
listNode *tail;// 尾结点
int len;// 链表的长度

// 用于实现多态链表所需的类型的特定函数
// 函数指针
// 用于复制链表结点所保存的值
void *(*dup)(void *ptr);
// 用于释放链表结点所保存的值
void (*free)(void *ptr);
// 用于对比
int (*match)(void *ptr, void *key);
}list;

// 定义对链表进行操作的宏
// 获取链表长度
#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))
// 设置释放操作的函数指针
#define listSetFreeMethod(l,m) ((l)->free = (m))
// 设置对比操作的函数指针
#define listSetMatchMethod(l,m) ((l)->match = (m))
// 获取复制链表结点的函数指针
#define listGetDupMethod(l) ((l)->dup)
// 获取释放链表结点的函数指针
#define listGetFree(l) ((l)->free)
// 获取比较链表结点的函数指针
#define listGetMatchMethod(l) ((l)->match)

// 创建一个不包含任何结点的新链表
list *listCreate(void);
// 释放给定链表，以及链表中的所有结点
void listRelease(list *l);
// 将一个包含给定值的新节点添加到给定链表的表头
list *listAddNodeHead(list *l, void *value);
// 将一个包含给定值的新节点添加到给定链表的表尾
list *listAddNodeTail(list *l, void *value);
// 将一个包含给定值的新节点添加到给定结点的之前或之后
list *listInsertNode(list *l, listNode *old_node, void *value, int after);
// 从链表中删除给定结点
list *listDelNode(list *l, listNode *node);
// 复制一个给定链表的副本
list *listDup(list *orig);
// 查找并返回链表中包含给定值的结点
listNode *listSearchKey(list *l, void *key);
// 返回链表在给定索引上的结点
listNode *listIndex(list *l, long index);
// 将链表结点的表位结点弹出，然后将被弹出的结点插
// 入到链表的表头，成为新的表头结点
void listRotate(list *l);

#endif

list API 的实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include “adlist.h”

// 创建一个不包含任何结点的新链表
list *listCreate(void){
list* l=(list*)malloc(sizeof(list));
// 没有结点
l->head=NULL;
l->tail=NULL;
l->len=0;
l->dup=NULL;
l->free=NULL;
l->match=NULL;
return l;
}
// 释放给定链表，以及链表中的所有结点
void listRelease(list *l){
if(l==NULL){
return ;
}
// 没有 head(没有结点)
if(l->head==NULL){
return ;
}
// 保证了链表是有结点存在的
// 用来移动的指针，指向第一个结点
listNode*temp=l->head;
while(temp->next!=NULL){
temp=temp->next;
// 使用链表对应释放 value 的 free 来释放 value 的值
if(l->free!=NULL){
l->free(temp->value);
}else{
printf(“PIG Redis WARNING : List->free is not define.\n”);
}
free(temp->prev);
}
free(temp);
l->head=NULL;
l->tail=NULL;
free(l);
l=NULL;
return;
}

// 将一个包含给定值的新节点添加到给定链表的表头
list *listAddNodeHead(list *l, void *value){
if(l==NULL){
printf(“PIG Redis ERROR : List NULL.\n”);
return NULL;
}
// 链表中没有结点
if(l->head==NULL){
l->head=(listNode*)malloc(sizeof(listNode));
l->head->next=NULL;
l->head->prev=NULL;
// 使用链表对应复制 value 的 dup 来复制 value 的值
if(l->dup!=NULL){
l->head->value=l->dup(value);
}else{
printf(“PIG Redis WARNING : List->dup is not define.\n”);
l->head->value=value;
}
/* int *c=(int*)(l->head->value);
printf(“%d====\n”,*c);*/
l->len=1;
// 头尾指针都指向新的结点
l->tail=l->head;
return l;
}else{
listNode*newone=(listNode*)malloc(sizeof(listNode));
//newone->value=value;
// 使用链表对应复制 value 的 dup 来复制 value 的值
if(l->dup!=NULL){
newone->value=l->dup(value);
}else{
printf(“PIG Redis WARNING : List->dup is not define.\n”);
newone->value=value;
}
/* int *cc=(int*)(newone->value);
printf(“%d====\n”,*cc);*/

newone->next=l->head;
l->head->prev=newone;
// 新节点设为头结点
l->head=newone;
newone->prev=NULL;
l->len++;
return l;
}
}

// 将一个包含给定值的新节点添加到给定链表的表尾
list *listAddNodeTail(list *l, void *value){
if(l==NULL){
printf(“PIG Redis ERROR : List NULL.\n”);
return NULL;
}
// 链表中没有结点
if(l->head==NULL){
l->head=(listNode*)malloc(sizeof(listNode));
//l->head->value=value;
// 使用链表对应复制 value 的 dup 来复制 value 的值
if(l->dup!=NULL){
l->head->value=l->dup(value);
}else{
printf(“PIG Redis WARNING : List->dup is not define.\n”);
l->head->value=value;
}
l->head->next=NULL;
l->head->prev=NULL;
l->tail=l->head;
l->len=1;
return l;
}else{
listNode*temp=(listNode*)malloc(sizeof(listNode));
//temp->value=value;
// 使用链表对应复制 value 的 dup 来复制 value 的值
if(l->dup!=NULL){
temp->value=l->dup(value);
}else{
printf(“PIG Redis WARNING : List->dup is not define.\n”);
temp->value=value;
}
temp->next=NULL;
temp->prev=l->tail;
l->tail->next=temp;
l->tail=temp;
l->len++;
return l;
}
}

// 将一个包含给定值的新节点添加到给定结点的之前或之后
//after 为 1 表示之后，after 为 0 表示之前
list *listInsertNode(list *l, listNode *old_node, void *value, int after){
listNode *newone=(listNode*)malloc(sizeof(listNode));
//newone->value=value;
// 使用链表对应复制 value 的 dup 来复制 value 的值
if(l->dup!=NULL){
newone->value=l->dup(value);
}else{
printf(“PIG Redis WARNING : List->dup is not define.\n”);
newone->value=value;
}
l->len++;
if(after){
newone->next=old_node->next;
newone->prev=old_node;
old_node->next->prev=newone;
old_node->next=newone;
// 检查原来的 temp 是否为 tail
if(l->tail==old_node){
l->tail=newone;
}
return l;
}else{
newone->next=old_node;
newone->prev=old_node->prev;
old_node->prev->next=newone;
old_node->prev=newone;
// 检查原来的 temp 是否为头结点
if(l->head==old_node){
l->head=newone;
}
return l;
}
}

// 从链表中删除给定结点
list *listDelNode(list *l, listNode *node){
l->len–;
// 使用链表对应释放 value 的 free 来释放 value 的值
if(l->free!=NULL){
l->free(node->value);
}else{
printf(“PIG Redis WARNING : List->free is not define.\n”);
}
// 要删除的是最后一个结点
if(l->head==node&&l->tail==node){
free(node);
l->head=NULL;
l->tail=NULL;
return l;
}else if(l->head==node){
printf(“head\n”);
l->head=node->next;
l->head->prev=NULL;
free(node);
return l;
}else if(l->tail==node){
l->tail=node->prev;
l->tail->next=NULL;
free(node);
return l;
}
node->prev->next=node->next;
node->next->prev=node->prev;
free(node);
return l;
}

// 复制一个给定链表的副本
list *listDup(list *orig){
if(orig==NULL){
return NULL;
}
// 该链表没有结点
if(orig->head==NULL){
list*l=listCreate();
return l;
}else{
list*l=listCreate();
listNode*temp=orig->head;
while(temp!=NULL){
// 向表尾插入
l=listAddNodeTail(l,temp->value);
temp=temp->next;
}
return l;
}
}

// 查找并返回链表中包含给定值的结点
listNode *listSearchKey(list *l, void *key){
if(l==NULL){
printf(“PIG Redis ERROR : List NULL.\n”);
return NULL;
// 链表中没有结点
}else if(l->head==NULL){
printf(“PIG Redis ERROR : List does’t have nodes.\n”);
return NULL;
}else{
listNode*temp=l->head;
// 检查是否定义了比较 value 的函数
if(l->match==NULL){
printf(“PIG Redis ERROR : List->match is not define.\n”);
return NULL;
}
//match 函数当两者相等时返回 1
while(temp!=NULL&&!(l->match(key,temp->value))){
temp=temp->next;
}
if(temp==NULL){
printf(“PIG Redis ERROR : List doesn’t have this node.\n”);
return NULL;
}else{
return temp;
}
}
}

// 返回链表在给定索引上的结点,index 从 0 开始
listNode *listIndex(list *l, long index){
if(l==NULL){
printf(“PIG Redis ERROR : List NULL.\n”);
return NULL;
}else if(l->head==NULL){
printf(“PIG Redis ERROR : List doesn’t have node.\n”);
return NULL;
}
listNode*temp=l->head;
for(int i=0;i<index&&temp!=NULL;i++){
temp=temp->next;
}
if(temp==NULL){
printf(“PIG Redis ERROR : Subscript out of range.\n”);
return NULL;
}
return temp;
}

// 将链表结点的表尾结点弹出，然后将被弹出的结点插
// 入到链表的表头，成为新的表头结点
void listRotate(list *l){
if(l==NULL){
printf(“PIG Redis ERROR : List NULL.\n”);
return ;
}else if(l->head==NULL){
printf(“PIG Redis ERROR : List doesn’t have node.\n”);
return ;
}else if(l->head==l->tail){
printf(“PIG Redis ERROR : List only have one node.\n”);
return ;
}

listNode*node=l->tail->prev;
l->tail->prev->next=NULL;
l->tail->next=l->head;
l->head->prev=l->tail;
l->head=l->tail;
l->tail=node;
l->head->prev=NULL;
}

int intMatch(void *ptr, void *key){
int *a=(int *)ptr;
int *b=(int *)key;
return (*a==*b)?1:0;
}

void *intDup(void *ptr){
return ptr;
}
int main(){
printf(“listCreate()\n”);
list*l=listCreate();
printf(“%d\n”,l->len);
listSetDupMethod(l,&intDup);

int b=111;
int *a=&b;
l=listAddNodeHead(l,a);
printf(“%d\n”,l->len);
// 使用 void* 指针的时候需要强制转换
int *c=(int *)(l->head->value);
printf(“%d\n”,*c);

int bb=12;
int *aa=&bb;
l=listAddNodeHead(l,aa);
//listInsertNode(l,l->head,a,1);
//l=listAddNodeTail(l,aa);
//printf(“%d\n”,l->len);
//l=listDelNode(l,l->head);
//l=listDelNode(l,l->tail);
//printf(“%d\n”,l->len);
listRotate(l);
// 使用 void* 指针的时候需要强制转换
int *cc=NULL;
listNode*temp=l->tail;
while(temp){
cc=(int *)(temp->value);
printf(“%d\n”,*cc);
temp=temp->prev;
}

/* list*l2=listDup(l);
temp=l2->tail;
while(temp){
cc=(int *)(temp->value);
printf(“%d\n”,*cc);
temp=temp->prev;
}
*/
//listSetMatchMethod(l,&intMatch);
listNode*node=listIndex(l,1);
int *zhu=(int*)node->value;
printf(“*zhu:%d\n”,*zhu);

listRelease(l);
//listRelease(l2);

system(“pause”);
return 0;
}