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

栏目: 数据库 · 发布时间: 4年前

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

通过对《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;
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

结网@改变世界的互联网产品经理

结网@改变世界的互联网产品经理

王坚 / 人民邮电出版社 / 2013-5-1 / 69.00元

《结网@改变世界的互联网产品经理(修订版)》以创建、发布、推广互联网产品为主线,描述了互联网产品经理的工作内容,以及应对每一部分工作所需的方法和工具。产品经理的工作是围绕用户及具体任务展开的,《结网@改变世界的互联网产品经理(修订版)》给出的丰富案例以及透彻的分析道出了从发现用户到最终满足用户这一过程背后的玄机。新版修改了之前版本中不成熟的地方,强化了章节之间的衔接,解决了前两版中部分章节过于孤立......一起来看看 《结网@改变世界的互联网产品经理》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具