首页 / REDIS / redis6.0源码学习（三）adlist

redis6.0源码学习（三）adlist

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了redis6.0源码学习（三）adlist，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5182字，纯文字阅读大概需要8分钟。

内容图文

redis6.0源码学习（三）adlist

文章目录

redis6.0源码学习（三）adlist

1、数据结构

下面是adlist主要结构体：

typedef struct listNode {
    struct listNode *prev; //prev指针，指向前一个节点
    struct listNode *next;//next指针，指向下一个节点
    void *value;
} listNode;
//迭代器
typedef struct listIter {
    listNode *next;
    int direction; //迭代器方向
} listIter;

typedef struct list {
    listNode *head; //head指针指向链表头部
    listNode *tail; //head指针指向链表头部
    void *(*dup)(void *ptr); //自定义节点值的复制函数，如果不定义，默认策略的复制操作会让原链表和新链表共享同一个数据域
    void (*free)(void *ptr);//自定义节点free操作 
    int (*match)(void *ptr, void *key);//search操作的时候比较两个value是否相等，默认策略是比较两个指针的值
    unsigned long len; //记录链表的长度，获取长度操作可以O(1)返回
} list;

下面是插入了“hello“、”world“、”redis“ 三个元素的示意图：
redis6.0源码学习（三）adlist - 文章图片

2、创建

listCreate 创建一个空元素的链表, 结构体中元素都赋0值。

/* Create a new list. The created list can be freed with
 * AlFreeList(), but private value of every node need to be freed
 * by the user before to call AlFreeList().
 *
 * On error, NULL is returned. Otherwise the pointer to the new list. */
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;
}

3、插入节点

redis双向链表插入实现了三种插入方法，分别是头插入，尾插入，特定节点前后插入。下面分别来看下三种方法：

3.1 链表头插入

/* Add a new node to the list, to head, containing the specified 'value'
 * pointer as value.
 *
 * On error, NULL is returned and no operation is performed (i.e. the
 * list remains unaltered).
 * On success the 'list' pointer you pass to the function is returned. */
list *listAddNodeHead(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL) //先申请一个新的node节点大小的内存给新node节点使用
        return NULL;
    node->value = value;
    if (list->len == 0) { //链表为空的情况
        list->head = list->tail = node; //step 1 对应下图中的圈1
        node->prev = node->next = NULL; //step 2 对应下图中的圈2
    } else {//链表不为空
        node->prev = NULL; //step1
        node->next = list->head; //step2
        list->head->prev = node; //step3
        list->head = node; //step4
    }
    list->len++;//更新链表长度
    return list;
}

下面是链表头插入两种情况的图示：

1、链表为空的情况

redis6.0源码学习（三）adlist - 文章图片

2、链表不为空的情况

redis6.0源码学习（三）adlist - 文章图片

3.2 链表尾插入

在链表尾部插入和在链表头部插入一样，也是分为两种情况：1、链表为空的情况， 2、链表不为空的情况。其中链表为空的情况时和在链表头插入一样。

list *listAddNodeTail(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)//先申请一个新的node节点大小的内存给新node节点使用
        return NULL;
    node->value = value;
    if (list->len == 0) {
        list->head = list->tail = node;//和链表头插入逻辑一样
        node->prev = node->next = NULL;
    } else {
        node->prev = list->tail;//step1
        node->next = NULL; //step2
        list->tail->next = node;//step3
        list->tail = node;//step4
    }
    list->len++; //更新链表长度
    return list;
}

链表为空的示意图参考在头部插入的示意图，下图为链表不为空时在尾部插入的示意图：

redis6.0源码学习（三）adlist - 文章图片

3.3 链表某节点前后插入

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

    if ((node = zmalloc(sizeof(*node))) == NULL) //先申请一个新的node节点大小的内存给新node节点使用
        return NULL;
    node->value = value;
    if (after) {//在指定节点后面插入
        node->prev = old_node; //让新节点prev指向旧节点
        node->next = old_node->next;//让新节点的next指向旧节点的next
        if (list->tail == old_node) { //有可能是在尾节点后插入新的节点，退化成了尾节点后插入的情况，示意图见上图3
            list->tail = node;
        }
    } else {//默认在指定节点前面插入
        node->next = old_node;//step1
        node->prev = old_node->prev; //step2
        if (list->head == old_node) {//有可能是在首节点前插入新节点， 退化成了头节点前面插入的情况，示意图建上图2
            list->head = node;//step3
        }
    }

    if (node->prev != NULL) {
        //在指定节点后面插入时，更新旧节点的next指向新节点
        node->prev->next = node;
    }
    if (node->next != NULL) {
        //在指定节点前面插入时，更新旧节点的pre指向新节点
        node->next->prev = node;//step4
    }
    list->len++;//更新长度
    return list;
}

示意图如下，圈中的数字对应代码中的step
redis6.0源码学习（三）adlist - 文章图片

4、删除节点

/* Remove the specified node from the specified list.
 * It's up to the caller to free the private value of the node.
 *
 * This function can't fail. */
void listDelNode(list *list, listNode *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);
    zfree(node);//释放内存
    list->len--;//更新长度
}

5、合并链表

/* 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;
}

6、总结

看代码终究不如自己实现一遍，练习网站奉上，大家可以去这里练习一下，自己实现一遍。

https://leetcode-cn.com/problems/design-linked-list/

内容总结

以上是互联网集市为您收集整理的redis6.0源码学习（三）adlist全部内容，希望文章能够帮你解决redis6.0源码学习（三）adlist所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/867934.html

来源：【匿名】

【上一篇】Redis Cluster集群【下一篇】redis可以做什么？

更多 ►

【redis6.0源码学习（三）adlist】教程文章相关的互联网学习教程文章

redis在windows下启动# Creating Server TCP listening socket 127.0.0.1:6379: bind: No error解决【图】

按顺序输入：1、redis-cli.exe2、shutdown3、exit4、redis-server.exe redis.window.conf 原文：http://www.cnblogs.com/unuai/p/7500150.html

Redis之List【图】

一、Redis之List简介1. List是简单的字符串列表，按照插入顺序排列。2. 一个列表最多可存储232-1个元素（40多亿）。二、Redis之List命令行操作Lrange：获取列表指定区间中的元素。0表示列表第一个元素，-1表示最后一个元素，-2表示倒数第二个元素。所以获取列表所有元素命令为：lrang list_name 0 -1。Lpush：将一个或多个值插入list头部。Rpush：将一个或多个值插入list尾部。若key不存在则先创建一个空列表，若key对应的值不是列...

关于Windows版本的redis启动报错：Creating Server TCP listening socket 127.0.0.1:6379: bind: No error

网上提供的解决方法是的解决方案如下按顺序输入如下命令就可以连接成功1. redis-cli.exe2. shutdown3. exit4. redis-server.exe redis.windows.conf因为报错的次数挺多的，我尝试了这个方法还没有成功过。以下是我的解决方法：1. 查找6379端口的占用情况netstat -ano|findstr 63792. 杀死找到的PID进程taskkill /pid 193548 /f（中间有一次说拒绝访问，把cmd控制台的权限修改为管理员就可以杀死成功）然后重新运行redis-server.exe...

Redis(5)—List、Set【代码】

Redis(5)—List、SetList（列表）在redis里面，我们可以把list玩成，栈、队列、阻塞队列！值可以重复。所有的List命令基本都是用L开头的。LPush key value ：将value值插入到列表的左部。RPush key value ：将value值插入到列表的右部。LRange key start end ：获取key列表中的值。LPop key ：移除key列表中的最左侧元素。RPop key ：移除key列表中的最右侧元素。LIndex key index ：获取key列表中index下标的值。LLen key ：获取...

Redis中LIST列表的相关命令【代码】

Redis中LIST列表的相关命令添加lpush将一个或多个value插入到key的表头,如果存在多个value,那么各个value按从左到右的顺序依次插入表头插入表头:意味着新插入的值在最前列如果list之前不存在,则会创建一个新的list,如果list已存在,则追加,返回值是list的元素数量,也可以理解位最后插入的元素的相对位置127.0.0.1:6379> lpush list2 zhangsan lisi wangwu (integer) 3 127.0.0.1:6379>rpush和lpush功能一样,只不过是从从右往左插入...

Redis数据结构详解之List（二）

序言思来想去感觉redis中的list没什么好写的，如果单写几个命令的操作过于乏味，所以本篇最后我会根据redis中list数据类型的特殊属性，同时对比成熟的消息队列产品rabbitmq，使用redis实现一个消息队列。为啦让本篇更有魅力，我再介绍下redis中list的基本属性，以及为什么使用redis中list列表类型，为什么使用消息队列，为什么不用rabbitmq而使用redis实现消息队列？呢，到这里为止，如果你是大咖，大牛，大神，大爷！不要听我吹牛...

Redis常用命令--Lists【代码】

List是一个双向链表，按照插入顺序排序，可以添加一个元素到头部或者尾部。当对一个空key执行插入操作的时候会创建一个新表。如果要清空列表，则会杀出对应的key空间。在List中保存了头节点和未节点，以及链表包含的节点数量。所以查询链表中节点数量的复杂度为O(1)。在List中保存的每个节点都保存了前一个节点，后一个节点，以及节点本身。头结点的前一个节点为NULL，尾节点的后一个节点为NULL。在Redis中提供了大概17个操作list的...

Redis中hash之ziplist与hashtable性能简单对比

近来遇到一个问题，使用redis的哈希对象存储数据，发现redis的内存耗用是单纯存进去的数据的两倍多，希望能够找到有效的方法缩减这部分多出来的空间。　　经过一番研究，是由于存储的时候，具体的存储结构使用的是hashtable来存储的，hashtable使用的内存大小是数据的两倍。一开始的时候怀疑是SDS预留出来的空间，但是经过测试，发现SDS在初始创建对象的时候是不会预留空间的，只会在出现修改的情况下预留出一倍的空间（数据小于1M...

redis中stringRedisTemplate中opsForList中方法的简单应用【代码】

opsForList操作List集合push操作分为leftpush和rightpush，其中leftpush是在list的左侧添加，即列表的头部，right是在list的左侧添加，即在列表的尾部。可以根据业务酌情选择。pop操作也分为left和right，意思和push一样。pop是获取一个元素，并且删除这个元素。如果只想要查看某个元素。可以使用range，他有三个参数，第一个参数是key，后面是搜索范围，全集合搜索可以用（key,0,-1）；有时候希望给添加的缓存设置生命时间，到期...

redis 底层数据结构压缩列表 ziplist【图】

当一个哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做哈希键的底层实现。压缩列表是Redis为了节约内存而开发的是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值ziplist 数据结构压缩列表节点的构成每个压缩列表节点可以保存一个字节数组或者一个整数值，其中字...

Redis入门到高可用（八）——list【图】

一、结构key - value 结构，value是一个有序队列。可进行左边的添加及弹出，右边的添加及弹出。可获取列表的长度，删除列表中指定元素，获取列表的子列表，按照索引获取列表的指定元素。特点：列表有序、可重复、左右两边插入弹出。主要APIRPUSH ：将一个或多个值 value 插入到列表 key 的表尾(最右边)。LPUSH : 将一个或多个值 value 插入到列表 key 的表头原文：https://www.cnblogs.com/thiaoqueen/p/9086178.html

C#Redis列表List【代码】

一、前戏在Redis中，List类型是按照插入顺序排序的字符串链表。和数据结构中的普通链表一样，我们可以在其头部(left)和尾部(right)添加新的元素。在插入时，如果该键并不存在，Redis将为该键创建一个新的链表。与此相反，如果链表中所有的元素均被移除，那么该键也将会被从数据库中删除。List中可以包含的最大元素数量是4294967295。从元素插入和删除的效率视角来看，如果我们是在链表的两头插入或删除元素，这将会是非常高...

Redis系列（六）：数据结构List双向链表LPUSH、LPOP、RPUSH、RPOP、LLEN命令【代码】【图】

1.介绍redis中的list既实现了栈（先进后出）又实现了队列（先进先出）1.示意图 2.各命令详解LPUSH/RPUSHLPUSH:从队列的左边入队一个或多个元素将所有指定的值插入到存于 key 的列表的头部。如果 key 不存在，那么在进行 push 操作前会创建一个空列表。如果 key 对应的值不是一个 list 的话，那么会返回一个错误。可以使用一个命令把多个元素 push 进入列表，只需在命令末尾加上多个指定的参数。元素是从最左端的到最右端的、一个...

redis 5.0.2 源码阅读——压缩列表ziplist【代码】

redis中压缩列表ziplist相关的文件为：ziplist.h与ziplist.c压缩列表是redis专门开发出来为了节约内存的内存编码数据结构。源码中关于压缩列表介绍的注释也写得比较详细。一、数据结构压缩列表的整体结构如下1/* 2 <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend> 3 */各个部分的含义项类型长度用途zlbytesuint32_t4Bziplist总字节数，包括zlbyteszltailuint32_t4B最后一个entry的偏移量zllenuint16_t2Bentry数量...

redis的list取出数据方式速度测试【代码】

redis测试：package business;import java.io.BufferedReader; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStreamReader; import java.io.UnsupportedEncodingException; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.concurrent.ExecutorService;...

REDIS - 技术教程分类

Redis 教程 Redis 简介 Redis 安装 Redis 配置 Redis 数据类型 Redis 命令 Redis 键(key) Redis 字符串(String) Redis 哈希(Hash) Redis 列表(List) Redis 集合(Set) Redis 有序集合(sorted set) Redis HyperLogLog Redis 发布订阅 Redis 事务 Redis 脚本 Redis 连接 Redis 服务器 Redis GEO Redis Stream Redis 数据备份与恢复 Redis 安全 Redis 性能测试 Redis 客户端连接 Redis 分区 Redis 全部

REDIS - 最热教程

redis中批量删除key的方法 redis设置密码，取消密码 node.js利用redis数据库缓存数据 PHP swoole和redis异步任务实现方法分析 Laravel使用Redis共享Session步骤详解 mac下卸载干净redis 如何通过命令行修改redis的配置使用Port Forwarding连接k8s集群的pod（...实现商品秒杀之——Redis Watch机制 redis雪崩、穿透、击穿、热点分别代表什...

首页 / REDIS / redis6.0源码学习（三）adlist

redis6.0源码学习（三）adlist

内容导读

内容图文

redis6.0源码学习（三）adlist

文章目录

1、数据结构

2、创建

3、插入节点

3.1 链表头插入

3.2 链表尾插入

3.3 链表某节点前后插入

4、删除节点

5、合并链表

6、总结

内容总结

内容备注

内容手机端

【redis6.0源码学习（三）adlist】教程文章相关的互联网学习教程文章

REDIS - 技术教程分类

REDIS - 最新教程

REDIS - 最热教程