Redis源码详解2:列表

Redis支持5种数据结构

  • string
  • list
  • hash
  • set
  • zset

由于经过了大量的测试和商业使用,这5种数据结构被看作是十分经典的C语言实现,性能优良,可以为其他软件的开发提供借鉴。

Redis中使用了多种列表结构,有adlist,ziplist,quicklist和skiplist,各有各的特点。先来看一个简单的列表实现adlist,因为结构比较简单,在这里先做介绍。列表数据结构的源代码在adlist.hadlist.c。先来看头文件adlist.h,首先定义了3个结构体

// 双向链表节点
typedef struct listNode {
    // 前一节点
    struct listNode *prev;
    // 后一节点
    struct listNode *next;
    // 节点储存的值
    void *value;
} listNode;

// 链表迭代器
typedef struct listIter {
    // 下一节点
    listNode *next;
    // 迭代方向
    int direction;
} listIter;

// 链表数据结构
typedef struct list {
    // 头尾节点
    listNode *head;
    listNode *tail;
    // 复制函数指针
    void *(*dup)(void *ptr);
    // 释放函数指针
    void (*free)(void *ptr);
    // 匹配函数指针
    int (*match)(void *ptr, void *key);
    // len链表长度
    unsigned long len;
} list;

可以看出Redis的列表数据结构是用双向链表实现的。

然后是一组宏定义的函数

// 宏定义的函数
#define listLength(l) ((l)->len)
#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))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))

#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)

接下来是一组普通函数声明

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);
void listDelNode(list *list, listNode *node);
listIter *listGetIterator(list *list, int direction);
listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter);
list *listDup(list *orig);
listNode *listSearchKey(list *list, void *key);
listNode *listIndex(list *list, long index);
void listRewind(list *list, listIter *li);
void listRewindTail(list *list, listIter *li);
void listRotate(list *list);
void listJoin(list *l, list *o);

最后是迭代方向的宏定义

// 从头部开始迭代
#define AL_START_HEAD 0
// 从尾部开始迭代
#define AL_START_TAIL 1

发表评论

电子邮件地址不会被公开。 必填项已用*标注