首页 博客列表 精选博客 智能问答 chat-GPT 关于我
【redis6.0.6】redis源码慢慢学，慢慢看 -- 第五天：adlist
发布日期：2021-06-30 19:46:21 浏览次数：2 分类：技术文章

本文共 11203 字，大约阅读时间需要 37 分钟。

在这里插入图片描述

文章目录

前言：

先附上人家的版权：

Copyright © 2009 Salvatore Sanfilippo

This file is released under the BSD license, see the COPYING file

考试差不多考完了，我又回来了。

今天起，我们就进入到redis的数据结构模块。
其实吧，这些数据结构我们都写过的，不过看看大佬们写的，也是能收获很多东西的。

先来最基础的链表，它这个是双端链表。

第一次写，有点紧张，我也不知道要怎么排版，嗯，多包涵。

头文件

那就先来个头文件吧。

//结构体：/*listNode：节点结构体listIter：迭代器结构体list：链表结构体我也不知道为啥要有这么多结构体，我平时吧，也就俩结构体，一个节点信息，一个数据信息，放这里看，就是那个listNode里面了不急，看到后面的函数实现就知道了。字面意思我就不注释了啊，看着乱糟糟*/typedef struct listNode {
       struct listNode *prev;    struct listNode *next;    void *value;	//通用链表} listNode;typedef struct listIter {
       listNode *next;	//迭代器当前指向的节点，起了这么个好名字    int direction;	//可以取以下两个值：AL_START_HEAD和AL_START_TAIL} listIter;typedef struct list {
       listNode *head;    listNode *tail;	//这种写法应该不陌生吧，总有人吹牛说用结构体实现类的功能，进去一看就是这个，我时间、流量都花了，就给我看这个？    void *(*dup)(void *ptr);			//复制链表节点保存的值,dup和dup2陌生不？    void (*free)(void *ptr);	    int (*match)(void *ptr, void *key);	//比较链表节点所保存的节点值和另一个输入的值是否相等    unsigned long len;} list;//函数宏#define listLength(l) ((l)->len)	//返回链表l节点数量#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))		//设置链表l的复制函数为m方法#define listSetFreeMethod(l,m) ((l)->free = (m))	#define listSetMatchMethod(l,m) ((l)->match = (m))	#define listGetDupMethod(l) ((l)->dup)		//返回链表l的赋值函数#define listGetFreeMethod(l) ((l)->free)#define listGetMatchMethod(l) ((l)->match)/* Prototypes */list *listCreate(void);void listRelease(list *list);void listEmpty(list *list);list *listAddNodeHead(list *list, void *value);list *listAddNodeTail(list *list, void *value);list *listInsertNode(list *list, listNode *old_node, void *value, int after);	//在list中，根据after在old_node节点前后插入值为value的节点。void listDelNode(list *list, listNode *node);listIter *listGetIterator(list *list, int direction);	//为list创建一个迭代器iteratorlistNode *listNext(listIter *iter);		//返回迭代器iter指向的当前节点并更新itervoid listReleaseIterator(listIter *iter);	list *listDup(list *orig);	//拷贝表头为orig的链表并返回listNode *listSearchKey(list *list, void *key);listNode *listIndex(list *list, long index);	//返回下标为index的节点地址void listRewind(list *list, listIter *li);		//将迭代器li重置为list的头结点并且设置为正向迭代void listRewindTail(list *list, listIter *li);	//将迭代器li重置为list的尾结点并且设置为反向迭代void listRotateTailToHead(list *list);			//将尾节点插到头结点void listRotateHeadToTail(list *list);void listJoin(list *l, list *o);		//把o接在l后面/* Directions for iterators */#define AL_START_HEAD 0     //正向迭代：从表头向表尾进行迭代#define AL_START_TAIL 1     //反向迭代：从表尾到表头进行迭代

源文件

关于空间配置器的问题，在这里：

list *listCreate(void);

list *listCreate(void){
       struct list *list;    if ((list = zmalloc(sizeof(*list))) == NULL)        return NULL;    list->head = list->tail = NULL;    list->len = 0;    list->dup = NULL;    list->free = NULL;    list->match = NULL;    return list;}

看这个没什么问题吧，大家都这么写。

void listEmpty(list *list);

清空链表，但是不删掉

void listEmpty(list *list){
       unsigned long len;    listNode *current, *next;	//不知道为什么还要特地去做个结构体    current = list->head;   //备份头节点地址    len = list->len;        //备份链表元素个数，使用备份操作防止更改原有信息    while(len--) {
             //遍历链表        next = current->next;        if (list->free) list->free(current->value); //如果设置了list结构的释放函数，则调用该函数释放节点值        zfree(current);        current = next;    }    list->head = list->tail = NULL;    list->len = 0;}

void listRelease(list *list);

想了想，还是“斩草除根”吧。

void listRelease(list *list)    //释放list表头和链表{
   	listEmpty(list);    zfree(list);}

list *listAddNodeHead(list *list, void *value);

list *listAddNodeHead(list *list, void *value)  //将value添加到list链表的头部{
       listNode *node;    if ((node = zmalloc(sizeof(*node))) == NULL)    //为新节点分配空间        return NULL;    node->value = value;    //设置node的value值    if (list->len == 0) {
      //将node头插到空链表        list->head = list->tail = node;        node->prev = node->next = NULL;    } else {
                   //将node头插到非空链表        node->prev = NULL;        node->next = list->head;        list->head->prev = node;        list->head = node;    }    list->len++;    //链表元素计数器加1    return list;}

没什么好说的啊

list *listAddNodeTail(list *list, void *value);

list *listAddNodeTail(list *list, void *value)  //将value添加到list链表的尾部{
       listNode *node;    if ((node = zmalloc(sizeof(*node))) == NULL)    //为新节点分配空间        return NULL;    node->value = value;    //设置node的value值    if (list->len == 0) {
      //将node尾插到空链表        list->head = list->tail = node;        node->prev = node->next = NULL;    } else {
                   //将node头插到非空链表        node->prev = list->tail;        node->next = NULL;        list->tail->next = node;        list->tail = node;    }    list->len++;    //更新链表节点计数器    return list;}

list *listInsertNode(list *list, listNode *old_node, void *value, int after);

list *listInsertNode(list *list, listNode *old_node, void *value, int after)    //在list中，根据after在old_node节点前后插入值为value的节点。{
       listNode *node;    if ((node = zmalloc(sizeof(*node))) == NULL) //为新节点分配空间        return NULL;    node->value = value;    //设置node的value值    if (after) {
       //after 非零，则将节点插入到old_node的后面        node->prev = old_node;        node->next = old_node->next;        if (list->tail == old_node) {
      //目标节点如果是链表的尾节点，更新list的tail指针            list->tail = node;        }    } else {
           //after 为零，则将节点插入到old_node的前面        node->next = old_node;        node->prev = old_node->prev;        if (list->head == old_node) {
      //如果节点如果是链表的头节点，更新list的head指针            list->head = node;        }    }    if (node->prev != NULL) {
      //如果有，则更新node的前驱节点的指针        node->prev->next = node;    }    if (node->next != NULL) {
      //如果有，则更新node的后继节点的指针        node->next->prev = node;    }    list->len++;    //更新链表节点计数器    return list;}

void listDelNode(list *list, listNode *node);

void listDelNode(list *list, listNode *node)    //从list删除node节点{
       if (node->prev) //更新node的前驱节点的指针        node->prev->next = node->next;    else        list->head = node->next;    if (node->next) //更新node的后继节点的指针        node->next->prev = node->prev;    else        list->tail = node->prev;    if (list->free) list->free(node->value);    //如果设置了list结构的释放函数，则调用该函数释放节点值    zfree(node);    //释放节点    list->len--;    //更新链表节点计数器}

咱也不知道该说点啥，咱自个儿也是这么写的。

listIter *listGetIterator(list *list, int direction);

listIter *listGetIterator(list *list, int direction)    //为list创建一个迭代器iterator{
       listIter *iter;    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;   //为迭代器申请空间    if (direction == AL_START_HEAD)     //设置迭代指针的起始位置        iter->next = list->head;    else        iter->next = list->tail;    iter->direction = direction;        //设置迭代方向    return iter;}

listNode *listNext(listIter *iter);

listNode *listNext(listIter *iter)  //返回迭代器iter指向的当前节点并更新iter{
       listNode *current = iter->next; //备份当前迭代器指向的节点    if (current != NULL) {
           if (iter->direction == AL_START_HEAD)   //根据迭代方向更新迭代指针            iter->next = current->next;        else            iter->next = current->prev;    }    return current;     //返回备份的当前节点地址}

void listReleaseIterator(listIter *iter);

void listReleaseIterator(listIter *iter) {
       zfree(iter);}

void listRewind(list *list, listIter *li);

void listRewind(list *list, listIter *li) {
       li->next = list->head;    li->direction = AL_START_HEAD;}

void listRewindTail(list *list, listIter *li);

void listRewindTail(list *list, listIter *li) {
       li->next = list->tail;    li->direction = AL_START_TAIL;}

list *listDup(list *orig); //拷贝表头为orig的链表并返回

内啥，看一下人家的注释吧，虽然是英文，但是不难看懂。

/* Duplicate the whole list. On out of memory NULL is returned. * On success a copy of the original list is returned. * * The 'Dup' method set with listSetDupMethod() function is used * to copy the node value. Otherwise the same pointer value of * the original node is used as value of the copied node. * * The original list both on success or error is never modified. */
list *listDup(list *orig)   //拷贝表头为orig的链表并返回{
       list *copy;    listIter iter;    listNode *node;    if ((copy = listCreate()) == NULL)  //创建一个表头        return NULL;    //设置新建表头的处理函数    copy->dup = orig->dup;    copy->free = orig->free;    copy->match = orig->match;    //迭代整个orig的链表    listRewind(orig, &iter);    //为orig定义一个迭代器并设置迭代方向    while((node = listNext(&iter)) != NULL) {
       //迭代器根据迭代方向不停迭代        void *value;        //复制节点值到新节点        if (copy->dup) {
               value = copy->dup(node->value); //如果定义了list结构中的dup指针，则使用该方法拷贝节点值。            if (value == NULL) {
                   listRelease(copy);                return NULL;            }        } else            value = node->value;    //获得当前node的value值        if (listAddNodeTail(copy, value) == NULL) {
    //将node节点尾插到copy表头的链表中            listRelease(copy);            return NULL;        }    }    return copy;    //返回拷贝副本}

改版之后，把迭代器变成了变量，不再是指针。

listNode *listSearchKey(list *list, void *key);

listNode *listSearchKey(list *list, void *key)  //在list中查找value为key的节点并返回{
       listIter iter;    listNode *node;    listRewind(list, &iter);    //创建迭代器    while((node = listNext(&iter)) != NULL) {
           //迭代整个链表        if (list->match) {
                             //如果设置list结构中的match方法，则用该方法比较            if (list->match(node->value, key)) {
                   return node;            }        } else {
               if (key == node->value) {
                   return node;            }        }    }    return NULL;}

listNode *listIndex(list *list, long index);

listNode *listIndex(list *list, long index) {
      //返回下标为index的节点地址    listNode *n;    if (index < 0) {
           index = (-index)-1;         //如果下标为负数，从链表尾部开始        n = list->tail;        while(index-- && n) n = n->prev;    } else {
           n = list->head;             //如果下标为正数，从链表头部开始        while(index-- && n) n = n->next;    }    return n;}

void listRotateTailToHead(list *list);

void listRotateTailToHead(list *list) {
          //将尾节点插到头结点    if (listLength(list) <= 1) return;  //只有一个节点或空链表直接返回    listNode *tail = list->tail;        /* Detach current tail */    list->tail = tail->prev;        //取出尾节点，更新list的tail指针    list->tail->next = NULL;    /* Move it as head */    list->head->prev = tail;        //将节点插到表头，更新list的head指针    tail->prev = NULL;    tail->next = list->head;    list->head = tail;}

void listRotateHeadToTail(list *list);

void listRotateHeadToTail(list *list) {
       if (listLength(list) <= 1) return;    listNode *head = list->head;    /* Detach current head */    list->head = head->next;    list->head->prev = NULL;    /* Move it as tail */    list->tail->next = head;    head->next = NULL;    head->prev = list->tail;    list->tail = head;}

void listJoin(list *l, list *o);

/* Add all the elements of the list 'o' at the end of the * list 'l'. The list 'other' remains empty but otherwise valid. */
void listJoin(list *l, list *o) {
       if (o->head)        o->head->prev = l->tail;    if (l->tail)        l->tail->next = o->head;    else        l->head = o->head;    if (o->tail) l->tail = o->tail;    l->len += o->len;    /* Setup other as an empty list. */    o->head = o->tail = NULL;    o->len = 0;}

整体感觉

挺好，大家都可以写这个数据结构。

不过嘛，写的也不容易，咱分析的也不容易。

建议收藏，不然刷着刷着就可能找不到了。

在这里插入图片描述

转载地址：https://lion-wu.blog.csdn.net/article/details/108387366 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：别抖，OK? 操作系统抖动现象、网络抖动与延迟、函数抖动之防抖与节流，串讲
下一篇：当下热点词再学：redis缓存预热、更新、降级，限流

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2024年04月28日 07时59分24秒

关于作者

    喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！
-- 愿君每日到此一游！

推荐文章

关于Java继承，重载及运行的顺序的总结 2019-04-30
关于Spring MVC与前端的交互 2019-04-30
Mybatis逆向工程的使用 2019-04-30
关于Hibernate的优缺点 2019-04-30
常用的 Maven 命令 2019-04-30
常用的20个正则表达式 2019-04-30
数据结构之顺序表的实现 2019-04-30
数据结构之线性链表 2019-04-30
JQuery使用validate插件完成校验 2019-04-30
关于java的继承 2019-04-30
关于java的内部类 2019-04-30
关于java的枚举 2019-04-30
一个简单的layui登陆界面 2019-04-30
SQL考试常见题目 2019-04-30
使用Spring Boot写一个简单的Hello World 2019-04-30
Spring Boot整合Servlet使用 2019-04-30
SpringBoot 文件上传 2019-04-30
我居然在Github上找到了一个完整的停车系统（附源码地址） 2019-04-30
大厂经典面试题：Redis为什么这么快？ 2019-04-30
精通Spring？请吃我一狗腿！ 2019-04-30
白红宇的个人博客 - 记录点点滴滴的事 - 您是第 311026674 位访客
访问时间: 2024-05-05 07:01:48 访问IP: 3.15.219.217     Copyright © 2020 - 2023 blog.css8.cn 京ICP备2021015314号-1 手机版