Redis list 源码

Posted on Thu 08 December 2016 in Redis, C

Files

  • adlist.h 头文件,定义 list 数据结构,一些宏以及函数原型声明。
  • adlist.c 函数的实现

Data Structure

list 节点的数据结构 listNode

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

prev 指向前一个节点,next指向下一个节点,value存储数据的指针。

list 迭代器的数据结构 listIter

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

next 指向下一个返回的节点,direction 指定迭代的方向:AL_START_HEAD从头开始迭代,而AL_START_TAIL 从尾部开始迭代。

list 类型的数据结构 list

typedef list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

head 指向第一个节点, tail 指向最后一个节点。dup 复制一个节点,返回一个void *,free 释放一个节点,match 判断节点是否与 key 匹配;len 存储list的长度。

Functions

list数据结构的创建、插入以及删除:

  • list *listCreate(void)创建一个空的list。
  • listReleast释放一个list,在函数中调用free释放节点的内存。
  • list *listAddNodeHead(list *list, void *value)在list头部插入数据。
  • list *listAddNodeTail(list *list, void *value)在list尾部插入数据。
  • list *listInsertNode(list *list, listNode *old_node, void *value, int after)在old_node节点前面或这后面插入一个节点。
  • void listDelNode(list *list, listNode *node)删除节点node。

迭代器相关的函数:

  • listIter *listGetIterator(list *list, int direction)指定direction的方向返回一个listIter迭代器。
  • void listReleaseIterator(listIter *iter)释放迭代器iter。
  • void listRewind(list *list, listIter *li)迭代器li跳到开头的位置。
  • void listRewindTail(list *list, listIter *li)将迭代器li跳到list的末尾。
  • listNode *listNext(listIter *iter)返回迭代器的下一个值。

list 的复制、匹配以及反转的操作:

  • list *listDup(list *orig)复制一个list,调用dup复制每一个节点,在没有dup函数指针的情况下,直接复制节点数据的指针。
  • listNode *listSearchKey(list *list, void *key)按照key调用match对list进行匹配。
  • listNode *listIndex(list *list, long index)取第index个节点。
  • void listRotate(list *list)反转最后一个节点,并将其放到第一个节点。

总结

list 是 Redis 中比较简单的数据结构,实现也比较简单易懂,主要是一些链表的指针操作。