Redis 双端链表

本文涉及的产品
云原生内存数据库 Tair,内存型 2GB
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Redis 版,经济版 1GB 1个月
简介: Redis 双端链表

Redis 链表结构内置了三个指向操作函数的函数指针,先梳理下函数指针用法。


函数指针

Redis 链表结构内置了三个指向操作函数的函数指针,先梳理下函数指针用法。


定义

函数体在编译期间会被存入进程代码段内存的一片连续区域中,而函数名就是该区域的起始地址。可将该地址赋值给函数指针,通过指针间接调用函数。

int sum(int x, int y) { return x + y;}
int main() {
    int (*p)(int, int) = sum;
    printf("%p\n%p\n", sum, p);
    printf("%d\n%d\n%d\n", p(1, 1), (*p)(1, 1), (****p)(1, 1)); // 函数指针可以无限解引用
}

地址相同:


用法

比如 qsort 库函数第四个参数便是函数指针:int (* cmp)(const void *, const void *));,用于自定义排序规则:

int less(const void *a, const void *b) {
    return *(int *) a > *(int *) b; // void* 泛型指针强转为 int* 指针后取值比较
}
int more(const void *a, const void *b) {    
  return *(int *) a < *(int *) b; // 从大到小排序
}
int main() {
    int nums[5] = {4, 1, 5, 3, 2};
    qsort(nums, 5, sizeof(int), less);  debug(nums);
    qsort(nums, 5, sizeof(int), more);  debug(nums);
}


排序结果:


注:void * 为泛型指针,类似 Go 的 interface,本节链表节点的值为 void* 类型,可存储任意类型的值。


区分

根据 () 逐个拆解:

int (*p)(int); // p 是指向 int f(int) 函数的指针
int *(*p)(int); // p 是指向 int* f(int) 函数的指针
int (**p)(int); // p 是指向 int f(int) 函数指针的指针

Redis 双端链表


优缺点

  • 优点:增删节点无需内存重排,直接操作复杂度为 O(1)。维护了 len 字段,取长度操作为 O(1)
  • 缺点:由于各节点在内存上不连续,遍历搜索复杂度为 O(N)。但可以通过空间换时间,使用 O(N) 空间的哈希表,可将搜索复杂度降为 O(1),这点在链表实现 LRU 时有应用。

结构


// 链表节点结构
typedef struct listNode {
    struct listNode *prev; // 前驱节点
    struct listNode *next; // 后继节点
    void *value;           // 节点值,类型为 void*,可保存任意类型的数据
} listNode;
// 双端链表结构,注意是无环的
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;


注意节点的结构标记是 listNode,前驱和后继节点为自引用结构。同时声明该类型的同名变量 listNode


list API 实现

记录几个重要 API 实现,源码:adlist.c


O(1) 操作

#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 listGetDupMethod(l) ((l)->dup) // 返回给定链表的值复制函数
// ...


注意取 list 字段值的简单操作都是宏定义,且对参数 n 加括号避免了展开优先级错乱的问题。


listCreate

// 创建新链表
list *listCreate(void) {
    struct list *list;
    if ((list = zmalloc(sizeof(*list))) == NULL) // 分配内存
        return NULL;
  // ...
    return list;
}


注意 zmalloc 分配内存后返回 void* 指针,可赋值给其他任意类型的指针,在 C 中无需显式强转,但 C++ 中必须显式转换。


listInsertNode

// 创建 value 新节点,并插入到 old_node 的之前或之后
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    listNode *node;
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    // 添加到 old_node 之后
    if (after) {
        node->prev = old_node;
        node->next = old_node->next;
        if (list->tail == old_node) { // old_node 是表尾节点
            list->tail = node;
        }
        // 添加到 old_node 之前
    } else {
        node->next = old_node;
        node->prev = old_node->prev;
        if (list->head == old_node) { // 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;
}


和刷 LeetCode 时链表题一样,直接画图最好理解。对链表的操作需检查:

  • 链表是否为空
  • 操作的节点是否为头尾节点
  • 调整节点前后指针指向时顺序是否正确


listIter

Redis 为链表封装了一个迭代器:

typedef struct listIter {
    listNode *next; // 当前迭代到的节点
    int direction; // 迭代的方向,常量 0 向后,1 向前
} listIter;


用于链表的搜索等操作:


listNode *listSearchKey(list *list, void *key) {
    listIter *iter;
    listNode *node;
    // 迭代整个链表
    iter = listGetIterator(list, AL_START_HEAD);
    while ((node = listNext(iter)) != NULL) {
        // 定义过值比较函数则调用
        if (list->match) {
            if (list->match(node->value, key)) { // 匹配则释放迭代器
                listReleaseIterator(iter);
                return node;
            }
        } else {
            if (key == node->value) {
                listReleaseIterator(iter); // 否则就强制地址是否相同
                return node;
            }
        }
    }
    listReleaseIterator(iter);
    return NULL; // 未找到
}


此处用到了 match 函数指针,其内部会对类型均为 void* 的 value, key 做类型转换,返回值是否相等的结果。


listIter 负责迭代,list 负责存储,避免了手动迭代中各种临时变量带来的开销,按功能分离模块的设计很优秀。


总结


Redis list 是双向无环链表,节点值类型是 void*,类似于 Go 的 interface,所以在比较节点值时需调用自定义比较函数,故引入了三个函数指针。Redis 还将迭代功能的实现分离到了 listIter,比较巧妙。


相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
目录
相关文章
|
1月前
|
存储 NoSQL Redis
Redis第四弹,Redis实现list时候做出的优化ziplist(压缩链表,元素少的情况),可更好的节省空间list——(内部编码:quicklist)Object encoding
Redis第四弹,Redis实现list时候做出的优化ziplist(压缩链表,元素少的情况),可更好的节省空间list——(内部编码:quicklist)Object encoding
|
2月前
|
存储 机器学习/深度学习 NoSQL
作者推荐 |【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(链表)(二)
作者推荐 |【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(链表)
47 0
|
2月前
|
存储 缓存 NoSQL
作者推荐 |【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(链表)(一)
作者推荐 |【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(链表)
43 0
|
缓存 NoSQL API
【Redis基础知识 六】Redis底层数据编码之链表
【Redis基础知识 六】Redis底层数据编码之链表
46 0
【Redis基础知识 六】Redis底层数据编码之链表
|
机器学习/深度学习 NoSQL API
Redis的设计与实现(2)-链表
链表在 Redis 中的应用非常广泛, 比如列表键的底层实现之一就是链表: 当一个列表键包含了数量比较多的元素, 又或者列表中包含的元素都是比较长的字符串时, Redis 就会使用链表作为列表键的底层实现.
74 0
|
存储 NoSQL Java
Redis-05Redis数据结构--链表( linked-list)
Redis-05Redis数据结构--链表( linked-list)
51 0
|
存储 NoSQL Redis
Redis(八)-Redis的list列表的数据结构-快速链表
数组时需要一块连续的内存空间来存储的,而链表值需要零散的内存碎片,数组的插入和删除的时间复杂度是0(n),查询的某个元素的时间复杂度是O(1)。
86 0
Redis(八)-Redis的list列表的数据结构-快速链表
|
存储 NoSQL Redis
redis链表实现
redis的链表实现 3.0以前:linkedlist(链表)和ziplist(压缩) 3.2+:quicklist(快速列表)
redis链表实现
|
NoSQL Redis
【Redis】Redis关于队列,栈,双向链表的解释
【Redis】Redis关于队列,栈,双向链表的解释
83 0
【Redis】Redis关于队列,栈,双向链表的解释
|
NoSQL Redis
Redis 源码分析链表(list)
Redis 源码分析链表(list)
134 0
Redis 源码分析链表(list)