Redis设计与实现——链表

6个月前 (05-30) wang 技术杂谈 0评论 已收录 123℃ 浏览数:91

Redis构建了自己的链表实现。在Redis中,列表键的底层实现之一就是链表。当一个列表键包好了数量较多的元素,或者列表中包含的元素都是比较长的字符串时,Redis就是用链表来作为底层实现。

Redis中,发布于订阅、慢查询、监视器、多个客户端的状态信息,构造缓冲区都是使用的链表作为底层实现。

Redis中链表的底层结构如下。

adlist.h/listNode

typedef struct listNode{
    // 前置节点
    struct listNode *perv;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;
}listNode;

仅仅使用多个listNode结构可以组成链表,但是用dlist.h/list来持有链表,操作起来会更方便

typedef struct list{
    // 表头节点
    listNode *head;

    // 表尾节点
    listNode *tail;

    // 链表所包含的结点数量
    unsigned long len;

    // 节点值复制函数
    void *(*dup) (void *ptr);

    // 节点值释放函数
    void *(*free) (void *ptr);

    // 节点值对比函数
    int (*match) (void *ptr, void *key);
}list;

list结构为链表提供了表头指针head,表尾指针tail,以及链表长度计数器len,dup、free和match成员则时永固实现多态链表说需的类型特定函数。

  • dup函数用于复制链表结点所保存的值。
  • free函数用于释放链表结点所保存的值。
  • match用于对比链表保存的值和另一个输入值是否相等。

Redis的链表实现的特性总结如下。

  • 双端(双向链表) 每个结点都有一个前置节点和后置节点。
  • 无环 表头结点的前置结点和表尾结点的后置指针都是NULL。
  • 带表头指针和表尾指针
  • 带链表长度计数器
  • 多态 Redis的链表可以用于保存各种不同类型的值。
博主

Just do it. Now or never.

相关推荐

嗨、骚年、快来消灭0回复。