首页 > 数据库 > Redis 源码解析之通用双向链表(adlist)

Redis 源码解析之通用双向链表(adlist)

时间:2023-04-08 12:13:29浏览次数:54  
标签:node Redis list value next 链表 源码 节点

Redis 源码解析之通用双向链表(adlist)

概述

Redis源码中广泛使用 adlist(A generic doubly linked list),作为一种通用的双向链表,用于简单的数据集合操作。adlist提供了基本的增删改查能力,并支持用户自定义深拷贝、释放和匹配操作来维护数据集合中的泛化数据 value

adlist 的数据结构

  1. 链表节点 listNode, 作为双向链表, prev, next 指针分别指向前序和后序节点。void* 指针类型的 value 用于存放泛化的数据类型(如果数据类型的 size 小于 sizeof(void*), 则可直接存放在 value中。 否则 value 存放指向该泛化类型的指针)。
// in adlist.h
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;
  1. 链表迭代器 listIter, 其中 next 指针指向下一次访问的链表节点。direction 标识当前迭代器的方向是 AL_START_HEAD(从头到尾遍历) 还是 AL_START_TAIL(从尾到头遍历)
// in adlist.h
typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

/* Directions for iterators */
#define AL_START_HEAD 0
#define AL_START_TAIL 1
  1. 双向链表结构 list。 其中, headtail 指针分别指向链表的首节点和尾节点。len 记录当前链表的长度。函数指针 dup, freematch 分别代表业务注册的对泛化类型 value 进行深拷贝,释放和匹配操作的函数。(如果没有注册 dup, 则默认进行浅拷贝。 如果没有注册 free, 则不对 value 进行释放。如果没有注册 match 则直接比较 value 的字面值)
// in adlist.h
typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

adlist 的基本操作

  1. 创建: listCreate 初始化相关字段为零值。可以通过 listSetDupMethod, listSetFreeMethod, listSetMatchMethod来注册该链表泛化类型 valuedup, freematch 函数。
/* Create a new list. The created list can be freed with
 * listRelease(), but private value of every node need to be freed
 * by the user before to call listRelease(), or by setting a free method using
 * listSetFreeMethod.
 *
 * 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;
}

#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))

image

  1. 在链表首插入新节点: listAddNodeHead
  • 在空链表插入新节点: 为 value 创建新节点,并让 listheadtail 都指向新节点。
    image

  • 在非空链表插入新节点:
    (1) 将新节点的 next 指向当前首节点(当前首节点将成为第二节点, 将会是新节点的后继节点)
    (2) 将当前节点的 prev 指向新节点, 新节点作为新的首节点将成为原首节点的前驱节点。
    (3) 将 head 从原本指向旧的首节点改为指向新节点, 将新节点作为链表首。
    (4) 链表总计数加一
    image

/* 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)
        return NULL;
    node->value = value;
    listLinkNodeHead(list, node);
    return list;
}

/*
 * Add a node that has already been allocated to the head of list
 */
void listLinkNodeHead(list* list, listNode *node) {
    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++;
}
  1. 在链表尾插入新节点: listAddNodeTail
  • 在空链表插入新节点: 逻辑与 listAddNodeHead 实现一致。
  • 在非空链表插入新节点:
    (1) 将新节点的 prev 指向当前首节点(当前尾节点将成为倒数第二节点, 将会是新节点的前驱节点)
    (2) 将当前节点的 next 指向新节点, 新节点作为新的尾节点将成为原尾节点的后继节点。
    (3) 将 tail 从原本指向旧的尾节点改为指向新节点, 将新节点作为链表尾。
    (4) 链表总计数加一

image

/* Add a new node to the list, to tail, 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 *listAddNodeTail(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    listLinkNodeTail(list, node);
    return list;
}

/*
 * Add a node that has already been allocated to the tail of list
 */
void listLinkNodeTail(list *list, listNode *node) {
    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++;
}
  1. 在链表指定位置插入 value: listInsertNode。如果 after 为非零, 则将新节点作为 old_node 后继节点。否则,新节点作为 old_node 前驱节点。下图以 after 为非零作为例子, 描述了这部分的代码逻辑。
    (1) 将新节点的 prev 指向 old_node(新节点插入在 old_node 之后);
    (2) 将新节点的 next 指向 old_node 的后继节点(old_node 的后继节点将成为新节点的后继节点);
    (3) 将 old_nodenext 指向新节点;
    (4) 将新节点的后继节点的 prev指向新节点(old_node的原后继节点现在成为了新节点的后继节点) 。
    (5) 链表总计数加一

image

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

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (after) {
        node->prev = old_node;
        node->next = old_node->next;
        if (list->tail == old_node) {
            list->tail = node;
        }
    } else {
        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++;
    return list;
}
  1. 删除链表指定节点: listDelNode。 下图以删除中间节点为例,展示了删除的流程。
    (1) 待删除节点的前驱节点的 next 指向待删除节点的后继节点;
    (2) 待删除节点的后继节点的 prev 指向待删除节点的前驱节点;
    (3) 待删除节点的 nextprev 都置为 NULL;
    (4) 链表总计数减一
    (5) 如果有注册 free 函数,则用 free 函数释放待删除节点的 value。然后释放待删除节点。

image


/* Remove the specified node from the specified list.
 * The node is freed. If free callback is provided the value is freed as well.
 *
 * This function can't fail. */
void listDelNode(list *list, listNode *node)
{
    listUnlinkNode(list, node);
    if (list->free) list->free(node->value);
    zfree(node);
}

/*
 * Remove the specified node from the list without freeing it.
 */
void listUnlinkNode(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;

    node->next = NULL;
    node->prev = NULL;

    list->len--;
}

5.链表的 Join 操作: listJoin 在链表l的末尾添加列表o的所有元素。 下图以两个链表都不为 NULL 的场景为例。
(1) o 的首部节点的 prev 指向 l 的尾部节点;
(2) l 的尾部节点的 next 指向 o 的首部节点(1,2 步将两个链表链接起来);
(3) ltail 指向 otail(otail作为新链表的尾部);
(4) l 链表总计数加一;
(5) (6) 清空 o 链表的信息;

image

/* 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->len == 0) return;

    o->head->prev = l->tail;

    if (l->tail)
        l->tail->next = o->head;
    else
        l->head = o->head;

    l->tail = o->tail;
    l->len += o->len;

    /* Setup other as an empty list. */
    o->head = o->tail = NULL;
    o->len = 0;
}
  1. 其他函数: 其他函数实现较为简单,这里简单罗列一下,感兴趣的可以去看下源码。
// 获取 list 的迭代器
listIter *listGetIterator(list *list, int direction);
// 返回迭代器的下一个元素,并将迭代器移动一位。如果已遍历完成, 则返回 NULL
listNode *listNext(listIter *iter);
// 释放迭代器资源
void listReleaseIterator(listIter *iter);

// 拷贝链表
list *listDup(list *orig);

// 在链表中查找与 key 匹配的 value 所在的第一个节点。
// 如果不存在,则返回 NULL。
// 匹配操作由 list->match 函数提供。
// 如果没有注册 match 函数, 则直接比较 key 是否与 value 相等。
listNode *listSearchKey(list *list, void *key);

// 返回指定的索引的元素。 如果超过了链表范围, 则返回 NULL。
// 正整数表示从首部开始计算。
// 0 表示第一个元素, 1 表示第二个元素, 以此类推。
// 负整数表示从尾部开始计算。
// -1 表示倒数第一个元素, -2 表示倒数第二个元素,以此类推。
listNode *listIndex(list *list, long index);

// 返回链表初始化的正向迭代器
void listRewind(list *list, listIter *li);
// 返回链表初始化的反向迭代器
void listRewindTail(list *list, listIter *li);

// 将链表尾部节点移到首部
void listRotateTailToHead(list *list);
// 将链表首部节点移到尾部
void listRotateHeadToTail(list *list);

// 用 value 初始化节点
void listInitNode(listNode *node, void *value);

adlist 的使用 demo

[email protected]:younglionwell/redis-adlist-example.git

关注公众号了解更多 redis 源码细节和其他技术内容。 你的关注是我最大的动力。

image

标签:node,Redis,list,value,next,链表,源码,节点
From: https://www.cnblogs.com/yanglingwell/p/17297650.html

相关文章

  • redis内存配置调优
    内存优化配置maxmemory1610612736maxmemory-policyallkeys-lru作用这两个参数对Redis的内存管理非常重要,可以帮助Redis避免因为内存占用过多而导致性能下降或运行崩溃的问题。maxmemory参数可以控制Redis实例的内存上限,防止Redis使用过多内存而导致操作系统的OOM(Out-Of-Memory)杀......
  • redis——缓存双写一致性问题
    缓存双写一致性如果redis中有数据 需要和数据库中的值相同如果redis中无数据数据库中的值是最新值,且准备回写redis缓存按照操作分只读缓存读写缓存同步直写策略写数据库后也同步写redis缓存,缓存中的数据和数据中的一致对于读写缓存来说,要想保证......
  • 链表的回文判断—Java实现
    对于这个题,主要是老是局限于方法内的变量,未想到借助外部变量辅助:具如下,不可用数除法,会溢出异常:即使是取最大的long也会溢出,常规方法不再赘述,具体以代码如下:1packageProblemSolve;23publicclassSolution5{4privateListNodefrontNode;5publicboolean......
  • Spring源码系列一:入门——Hello World
    前言讲解Spring之前,我们首先梳理下Spring有哪些知识点可以进行入手源码分析,比如:SpringIOC依赖注入SpringAOP切面编程SpringBean的声明周期底层原理Spring初始化底层原理SpringTransaction事务底层原理HelloWorld通过这些知识点,后续我们慢慢在深入Spring的使用及原......
  • 最新中国福彩分析大数据分析大师拥有双色球数据展示微信小程序源码支持双色球数据分析
    demo软件园每日更新资源,请看到最后就能获取你想要的: 1.最新中国福彩分析大数据分析大师拥有双色球数据展示微信小程序源码支持双色球数据分析多个接口福彩大数据分析小程序,数据来自于中国福利彩票 拥有双色球数据展示 双色球数据分析多个接口 数据有每日奖金和往期记录......
  • 【Azure Redis 缓存】对于Azure Redis 从 Redis 4 升级到 Redis 6 的一些疑问
    问题描述使用AzureRedis服务,客户端使用Redisson3.X,在近期MicrosoftAzure对Redis服务进行大规模变动升级(Redis版本由4升级到6),对于这次升级的影响有以下的问题? 问题解释问题一:Redis6.0和Redisson3.X之间是否存在任何兼容问题,或任何性能问题?Redis版本6与版......
  • flask源码解析
    flask源码解析本篇主要是针对于以下一些问题进行源码剖析,并补充解释一些python语法的用法与应用场景。flask生命周期流程flask的request、session等都是导入进来的,也就意味着每次请求,我们所用的都是同一个request对象,它为什么能够按照同种方式取到自己request对象值呢flask......
  • 找人写指标 分时预警牛皇预警公式源码
    分时抓涨停预警源码 抓涨停不难分时预警牛皇520预警源码公布源码{牛皇}{副图}{大智慧L2公式}原理解析:A1赋值:((如果(((收盘价/((成交额(元)的历史累和)/((成交量(手)*100)的历史累和)))位于1.05和0.95之间)=0),返回(收盘价的历史简单移动平均),否则返回((成交额(元)的历史累和)/(......
  • 源码共读 | tdesign-vue 初始化组件
    前言Tdesign-vue是一由腾讯开源的Vue.js组件库。我们知道,这些大型的组件库业务覆盖面很广,基本都包含了很多组件,很多组件包含了一些通用性代码,如果每开发一个组件,都去把这些通用性代码复制出来,无疑是非常繁琐的,那么作者在开发这些组件时是如何做的呢?学习目标:新增组件:npmrun......
  • redis-2,redis持久化
    持久化rdb:snapshot快照,持久化快照aof:appendonlyfile写命令操作全部记录下来RDBrdb持久性以指定的时间间隔,执行数据集的时间点快照,全量快照rbd保存到磁盘的文件就是dump.rdb案例配置文件redis.conf在配置文件中找到snapshotting################################SNA......